Formerly stdio/stdio.h.~43~
[kopensolaris-gnu/glibc.git] / manual / memory.texi
1 @node Memory Allocation, Character Handling, Error Reporting, Top
2 @chapter Memory Allocation
3 @cindex memory allocation
4 @cindex storage allocation
5
6 The GNU system provides several methods for allocating memory space
7 under explicit program control.  They vary in generality and in
8 efficiency.
9
10 @iftex
11 @itemize @bullet
12 @item
13 The @code{malloc} facility allows fully general dynamic allocation.
14 @xref{Unconstrained Allocation}.
15
16 @item
17 Obstacks are another facility, less general than @code{malloc} but more
18 efficient and convenient for stacklike allocation.  @xref{Obstacks}.
19
20 @item
21 The function @code{alloca} lets you allocate storage dynamically that
22 will be freed automatically.  @xref{Variable Size Automatic}.
23 @end itemize
24 @end iftex
25
26 @menu
27 * Memory Concepts::             An introduction to concepts and terminology.
28 * Dynamic Allocation and C::    How to get different kinds of allocation in C.
29 * Unconstrained Allocation::    The @code{malloc} facility allows fully general
30                                  dynamic allocation.
31 * Obstacks::                    Obstacks are less general than malloc
32                                  but more efficient and convenient.
33 * Variable Size Automatic::     Allocation of variable-sized blocks
34                                  of automatic storage that are freed when the
35                                  calling function returns.
36 * Relocating Allocator::        Waste less memory, if you can tolerate
37                                  automatic relocation of the blocks you get.
38 * Memory Warnings::             Getting warnings when memory is nearly full.
39 @end menu
40
41 @node Memory Concepts
42 @section Dynamic Memory Allocation Concepts
43 @cindex dynamic allocation
44 @cindex static allocation
45 @cindex automatic allocation
46
47 @dfn{Dynamic memory allocation} is a technique in which programs
48 determine as they are running where to store some information.  You need
49 dynamic allocation when the number of memory blocks you need, or how
50 long you continue to need them, depends on the data you are working on.
51
52 For example, you may need a block to store a line read from an input file;
53 since there is no limit to how long a line can be, you must allocate the
54 storage dynamically and make it dynamically larger as you read more of the
55 line.
56
57 Or, you may need a block for each record or each definition in the input
58 data; since you can't know in advance how many there will be, you must
59 allocate a new block for each record or definition as you read it.
60
61 When you use dynamic allocation, the allocation of a block of memory is an
62 action that the program requests explicitly.  You call a function or macro
63 when you want to allocate space, and specify the size with an argument.  If
64 you want to free the space, you do so by calling another function or macro.
65 You can do these things whenever you want, as often as you want.
66
67 @node Dynamic Allocation and C
68 @section Dynamic Allocation and C
69
70 The C language supports two kinds of memory allocation through the variables
71 in C programs:
72
73 @itemize @bullet
74 @item
75 @dfn{Static allocation} is what happens when you declare a static
76 variable.  Each static variable defines one block of space, of a fixed
77 size.  The space is allocated once, when your program is started, and
78 is never freed.
79
80 @item
81 @dfn{Automatic allocation} happens when you declare an automatic
82 variable, such as a function argument or a local variable.  The space
83 for an automatic variable is allocated when the compound statement
84 containing the declaration is entered, and is freed when that
85 compound statement is exited.
86
87 In GNU C, the length of the automatic storage can be an expression
88 that varies.  In other C implementations, it must be a constant.
89 @end itemize
90
91 Dynamic allocation is not supported by C variables; there is no storage
92 class ``dynamic'', and there can never be a C variable whose value is
93 stored in dynamically allocated space.  The only way to refer to
94 dynamically allocated space is through a pointer.  Because it is less
95 convenient, and because the actual process of dynamic allocation
96 requires more computation time, programmers use dynamic allocation only
97 when neither static nor automatic allocation will serve.
98
99 For example, if you want to allocate dynamically some space to hold a
100 @code{struct foobar}, you cannot declare a variable of type @code{struct
101 foobar} whose contents are the dynamically allocated space.  But you can
102 declare a variable of pointer type @code{struct foobar *} and assign it the
103 address of the space.  Then you can use the operators @samp{*} and
104 @samp{->} on this pointer variable to refer to the contents of the space:
105
106 @example
107 @{
108   struct foobar *ptr
109      = (struct foobar *) malloc (sizeof (struct foobar));
110   ptr->name = x;
111   ptr->next = current_foobar;
112   current_foobar = ptr;
113 @}
114 @end example
115
116 @node Unconstrained Allocation
117 @section Unconstrained Allocation
118 @cindex unconstrained storage allocation
119 @cindex @code{malloc} function
120 @cindex heap, dynamic allocation from
121
122 The most general dynamic allocation facility is @code{malloc}.  It
123 allows you to allocate blocks of memory of any size at any time, make
124 them bigger or smaller at any time, and free the blocks individually at
125 any time (or never).
126
127 @menu
128 * Basic Allocation::            Simple use of @code{malloc}.
129 * Malloc Examples::             Examples of @code{malloc}.  @code{xmalloc}.
130 * Freeing after Malloc::        Use @code{free} to free a block you
131                                  got with @code{malloc}.
132 * Changing Block Size::         Use @code{realloc} to make a block
133                                  bigger or smaller.
134 * Allocating Cleared Space::    Use @code{calloc} to allocate a
135                                  block and clear it.
136 * Efficiency and Malloc::       Efficiency considerations in use of
137                                  these functions.
138 * Aligned Memory Blocks::       Allocating specially aligned memory:
139                                  @code{memalign} and @code{valloc}.
140 * Heap Consistency Checking::   Automatic checking for errors.
141 * Hooks for Malloc::            You can use these hooks for debugging
142                                  programs that use @code{malloc}.
143 * Statistics of Malloc::        Getting information about how much
144                                  memory your program is using.
145 * Summary of Malloc::           Summary of @code{malloc} and related functions.
146 @end menu
147
148 @node Basic Allocation
149 @subsection Basic Storage Allocation
150 @cindex allocation of memory with @code{malloc}
151
152 To allocate a block of memory, call @code{malloc}.  The prototype for
153 this function is in @file{stdlib.h}.
154 @pindex stdlib.h
155
156 @comment malloc.h stdlib.h
157 @comment ANSI
158 @deftypefun {void *} malloc (size_t @var{size})
159 This function returns a pointer to a newly allocated block @var{size}
160 bytes long, or a null pointer if the block could not be allocated.
161 @end deftypefun
162
163 The contents of the block are undefined; you must initialize it yourself
164 (or use @code{calloc} instead; @pxref{Allocating Cleared Space}).
165 Normally you would cast the value as a pointer to the kind of object
166 that you want to store in the block.  Here we show an example of doing
167 so, and of initializing the space with zeros using the library function
168 @code{memset} (@pxref{Copying and Concatenation}):
169
170 @example
171 struct foo *ptr;
172 @dots{}
173 ptr = (struct foo *) malloc (sizeof (struct foo));
174 if (ptr == 0) abort ();
175 memset (ptr, 0, sizeof (struct foo));
176 @end example
177
178 You can store the result of @code{malloc} into any pointer variable
179 without a cast, because ANSI C automatically converts the type
180 @code{void *} to another type of pointer when necessary.  But the cast
181 is necessary in contexts other than assignment operators or if you might
182 want your code to run in traditional C.
183
184 Remember that when allocating space for a string, the argument to
185 @code{malloc} must be one plus the length of the string.  This is
186 because a string is terminated with a null character that doesn't count
187 in the ``length'' of the string but does need space.  For example:
188
189 @example
190 char *ptr;
191 @dots{}
192 ptr = (char *) malloc (length + 1);
193 @end example
194
195 @noindent
196 @xref{Representation of Strings}, for more information about this.
197
198 @node Malloc Examples
199 @subsection Examples of @code{malloc}
200
201 If no more space is available, @code{malloc} returns a null pointer.
202 You should check the value of @emph{every} call to @code{malloc}.  It is
203 useful to write a subroutine that calls @code{malloc} and reports an
204 error if the value is a null pointer, returning only if the value is
205 nonzero.  This function is conventionally called @code{xmalloc}.  Here
206 it is:
207
208 @example
209 void *
210 xmalloc (size_t size)
211 @{
212   register void *value = malloc (size);
213   if (value == 0)
214     fatal ("virtual memory exhausted");
215   return value;
216 @}
217 @end example
218
219 Here is a real example of using @code{malloc} (by way of @code{xmalloc}).
220 The function @code{savestring} will copy a sequence of characters into
221 a newly allocated null-terminated string:
222
223 @example
224 char *
225 savestring (const char *ptr, size_t len)
226 @{
227   register char *value = (char *) xmalloc (len + 1);
228   memcpy (value, ptr, len);
229   value[len] = 0;
230   return value;
231 @}
232 @end example
233
234 The block that @code{malloc} gives you is guaranteed to be aligned so
235 that it can hold any type of data.  In the GNU system, the address is
236 always a multiple of eight; if the size of block is 16 or more, then the
237 address is always a multiple of 16.  Only rarely is any higher boundary
238 (such as a page boundary) necessary; for those cases, use
239 @code{memalign} or @code{valloc} (@pxref{Aligned Memory Blocks}).
240
241 Note that the memory located after the end of the block is likely to be
242 in use for something else; perhaps a block already allocated by another
243 call to @code{malloc}.  If you attempt to treat the block as longer than
244 you asked for it to be, you are liable to destroy the data that
245 @code{malloc} uses to keep track of its blocks, or you may destroy the
246 contents of another block.  If you have already allocated a block and
247 discover you want it to be bigger, use @code{realloc} (@pxref{Changing
248 Block Size}).
249
250 @node Freeing after Malloc
251 @subsection Freeing Memory Allocated with @code{malloc}
252 @cindex freeing memory allocated with @code{malloc}
253 @cindex heap, freeing memory from
254
255 When you no longer need a block that you got with @code{malloc}, use the
256 function @code{free} to make the block available to be allocated again.
257 The prototype for this function is in @file{stdlib.h}.
258 @pindex stdlib.h
259
260 @comment malloc.h stdlib.h
261 @comment ANSI
262 @deftypefun void free (void *@var{ptr})
263 The @code{free} function deallocates the block of storage pointed at
264 by @var{ptr}.
265 @end deftypefun
266
267 @comment stdlib.h
268 @comment Sun
269 @deftypefun void cfree (void *@var{ptr})
270 This function does the same thing as @code{free}.  It's provided for
271 backward compatibility with SunOS; you should use @code{free} instead.
272 @end deftypefun
273
274 Freeing a block alters the contents of the block.  @strong{Do not expect to
275 find any data (such as a pointer to the next block in a chain of blocks) in
276 the block after freeing it.}  Copy whatever you need out of the block before
277 freeing it!  Here is an example of the proper way to free all the blocks in
278 a chain, and the strings that they point to:
279
280 @example
281 struct chain
282   @{
283     struct chain *next;
284     char *name;
285   @}
286
287 void
288 free_chain (struct chain *chain)
289 @{
290   while (chain != 0)
291     @{
292       struct chain *next = chain->next;
293       free (chain->name);
294       free (chain);
295       chain = next;
296     @}
297 @}
298 @end example
299
300 Occasionally, @code{free} can actually return memory to the operating
301 system and make the process smaller.  Usually, all it can do is allow a
302 later later call to @code{malloc} to reuse the space.  In the mean time,
303 the space remains in your program as part of a free-list used internally
304 by @code{malloc}.
305
306 There is no point in freeing blocks at the end of a program, because all
307 of the program's space is given back to the system when the process
308 terminates.
309
310 @node Changing Block Size
311 @subsection Changing the Size of a Block
312 @cindex changing the size of a block (@code{malloc})
313
314 Often you do not know for certain how big a block you will ultimately need
315 at the time you must begin to use the block.  For example, the block might
316 be a buffer that you use to hold a line being read from a file; no matter
317 how long you make the buffer initially, you may encounter a line that is
318 longer.
319
320 You can make the block longer by calling @code{realloc}.  This function
321 is declared in @file{stdlib.h}.
322 @pindex stdlib.h
323
324 @comment malloc.h stdlib.h
325 @comment ANSI
326 @deftypefun {void *} realloc (void *@var{ptr}, size_t @var{newsize})
327 The @code{realloc} function changes the size of the block whose address is
328 @var{ptr} to be @var{newsize}.
329
330 Since the space after the end of the block may be in use, @code{realloc}
331 may find it necessary to copy the block to a new address where more free
332 space is available.  The value of @code{realloc} is the new address of the
333 block.  If the block needs to be moved, @code{realloc} copies the old
334 contents.
335 @end deftypefun
336
337 Like @code{malloc}, @code{realloc} may return a null pointer if no
338 memory space is available to make the block bigger.  When this happens,
339 the original block is untouched; it has not been modified or relocated.
340
341 In most cases it makes no difference what happens to the original block
342 when @code{realloc} fails, because the application program cannot continue
343 when it is out of memory, and the only thing to do is to give a fatal error
344 message.  Often it is convenient to write and use a subroutine,
345 conventionally called @code{xrealloc}, that takes care of the error message
346 as @code{xmalloc} does for @code{malloc}:
347
348 @example
349 void *
350 xrealloc (void *ptr, size_t size)
351 @{
352   register void *value = realloc (ptr, size);
353   if (value == 0)
354     fatal ("Virtual memory exhausted");
355   return value;
356 @}
357 @end example
358
359 You can also use @code{realloc} to make a block smaller.  The reason you
360 would do this is to avoid tying up a lot of memory space when only a little
361 is needed.  Making a block smaller sometimes necessitates copying it, so it
362 can fail if no other space is available.
363
364 If the new size you specify is the same as the old size, @code{realloc}
365 is guaranteed to change nothing and return the same address that you gave.
366
367 @node Allocating Cleared Space
368 @subsection Allocating Cleared Space
369
370 The function @code{calloc} allocates memory and clears it to zero.  It
371 is declared in @file{stdlib.h}.
372 @pindex stdlib.h
373
374 @comment malloc.h stdlib.h
375 @comment ANSI
376 @deftypefun {void *} calloc (size_t @var{count}, size_t @var{eltsize})
377 This function allocates a block long enough to contain a vector of
378 @var{count} elements, each of size @var{eltsize}.  Its contents are
379 cleared to zero before @code{calloc} returns.
380 @end deftypefun
381
382 You could define @code{calloc} as follows:
383
384 @example
385 void *
386 calloc (size_t count, size_t eltsize)
387 @{
388   size_t size = count * eltsize;
389   void *value = malloc (size);
390   if (value != 0)
391     memset (value, 0, size);
392   return value;
393 @}
394 @end example
395
396 We rarely use @code{calloc} today, because it is equivalent to such a
397 simple combination of other features that are more often used.  It is a
398 historical holdover that is not quite obsolete.
399
400 @node Efficiency and Malloc
401 @subsection Efficiency Considerations for @code{malloc}
402 @cindex efficiency and @code{malloc}
403
404 To make the best use of @code{malloc}, it helps to know that the GNU
405 version of @code{malloc} always dispenses small amounts of memory in
406 blocks whose sizes are powers of two.  It keeps separate pools for each
407 power of two.  This holds for sizes up to a page size.  Therefore, if
408 you are free to choose the size of a small block in order to make
409 @code{malloc} more efficient, make it a power of two.
410
411 Once a page is split up for a particular block size, it can't be reused
412 for another size unless all the blocks in it are freed.  In many
413 programs, this is unlikely to happen.  Thus, you can sometimes make a
414 program use memory more efficiently by using blocks of the same size for
415 many different purposes.
416
417 When you ask for memory blocks of a page or larger, @code{malloc} uses a
418 different strategy; it rounds the size up to a multiple of a page, and
419 it can coalesce and split blocks as needed.
420
421 The reason for the two strategies is that it is important to allocate
422 and free small blocks as fast as possible, but speed is less important
423 for a large block since the program normally spends a fair amount of
424 time using it.  Also, large blocks are normally fewer in number.
425 Therefore, for large blocks, it makes sense to use a method which takes
426 more time to minimize the wasted space.
427
428 @node Aligned Memory Blocks
429 @subsection Allocating Aligned Memory Blocks
430
431 @cindex page boundary
432 @cindex alignment (with @code{malloc})
433 @pindex stdlib.h
434 The address of a block returned by @code{malloc} or @code{realloc} in
435 the GNU system is always a multiple of eight.  If you need a block whose
436 address is a multiple of a higher power of two than that, use
437 @code{memalign} or @code{valloc}.  These functions are declared in
438 @file{stdlib.h}.
439
440 With the GNU library, you can use @code{free} to free the blocks that
441 @code{memalign} and @code{valloc} return.  That does not work in BSD,
442 however---BSD does not provide any way to free such blocks.
443
444 @comment malloc.h stdlib.h
445 @comment BSD
446 @deftypefun {void *} memalign (size_t @var{size}, int @var{boundary})
447 The @code{memalign} function allocates a block of @var{size} bytes whose
448 address is a multiple of @var{boundary}.  The @var{boundary} must be a
449 power of two!  The function @code{memalign} works by calling
450 @code{malloc} to allocate a somewhat larger block, and then returning an
451 address within the block that is on the specified boundary.
452 @end deftypefun
453
454 @comment malloc.h stdlib.h
455 @comment BSD
456 @deftypefun {void *} valloc (size_t @var{size})
457 Using @code{valloc} is like using @code{memalign} and passing the page size
458 as the value of the second argument.
459 @end deftypefun
460
461 @node Heap Consistency Checking
462 @subsection Heap Consistency Checking
463
464 @cindex heap consistency checking
465 @cindex consistency checking, of heap
466
467 You can ask @code{malloc} to check the consistency of dynamic storage by
468 using the @code{mcheck} function.  This function is a GNU extension,
469 declared in @file{malloc.h}.
470 @pindex malloc.h
471
472 @comment malloc.h
473 @comment GNU
474 @deftypefun void mcheck (void (*@var{abortfn}) (void))
475 Calling @code{mcheck} tells @code{malloc} to perform occasional
476 consistency checks.  These will catch things such as writing
477 past the end of a block that was allocated with @code{malloc}.
478
479 The @var{abortfn} argument is the function to call when an inconsistency
480 is found.  If you supply a null pointer, the @code{abort} function is
481 used.
482
483 It is too late to begin allocation checking once you have allocated
484 anything with @code{malloc}.  So @code{mcheck} does nothing in that
485 case.  The function returns @code{-1} if you call it too late, and
486 @code{0} otherwise (when it is successful).
487
488 The easiest way to arrange to call @code{mcheck} early enough is to use
489 the option @samp{-lmcheck} when you link your program.
490 @end deftypefun
491
492 @node Hooks for Malloc
493 @subsection Storage Allocation Hooks
494 @cindex allocation hooks, for @code{malloc}
495
496 The GNU C library lets you modify the behavior of @code{malloc},
497 @code{realloc}, and @code{free} by specifying appropriate hook
498 functions.  You can use these hooks to help you debug programs that use
499 dynamic storage allocation, for example.
500
501 The hook variables are declared in @file{malloc.h}.
502 @pindex malloc.h
503
504 @comment malloc.h
505 @comment GNU
506 @defvar __malloc_hook
507 The value of this variable is a pointer to function that @code{malloc}
508 uses whenever it is called.  You should define this function to look
509 like @code{malloc}; that is, like:
510
511 @example
512 void *@var{function} (size_t @var{size})
513 @end example
514 @end defvar
515
516 @comment malloc.h
517 @comment GNU
518 @defvar __realloc_hook
519 The value of this variable is a pointer to function that @code{realloc}
520 uses whenever it is called.  You should define this function to look
521 like @code{realloc}; that is, like:
522
523 @example
524 void *@var{function} (void *@var{ptr}, size_t @var{size})
525 @end example
526 @end defvar
527
528 @comment malloc.h
529 @comment GNU
530 @defvar __free_hook
531 The value of this variable is a pointer to function that @code{free}
532 uses whenever it is called.  You should define this function to look
533 like @code{free}; that is, like:
534
535 @example
536 void @var{function} (void *@var{ptr})
537 @end example
538 @end defvar
539
540 You must make sure that the function you install as a hook for one of
541 these functions does not call that function recursively without restoring
542 the old value of the hook first!  Otherwise, your program will get stuck
543 in an infinite recursion.
544
545 Here is an example showing how to use @code{__malloc_hook} properly.  It
546 installs a function that prints out information every time @code{malloc}
547 is called.
548
549 @example
550 static void *(*old_malloc_hook) (size_t);
551 static void *
552 my_malloc_hook (size_t size)
553 @{
554   void *result;
555   __malloc_hook = old_malloc_hook;
556   result = malloc (size);
557   __malloc_hook = my_malloc_hook;
558   printf ("malloc (%u) returns %p\n", (unsigned int) size, result);
559   return result;
560 @}
561
562 main ()
563 @{
564   ...
565   old_malloc_hook = __malloc_hook;
566   __malloc_hook = my_malloc_hook;
567   ...
568 @}
569 @end example
570
571 The @code{mcheck} function (@pxref{Heap Consistency Checking}) works by
572 installing such hooks.
573
574 @c __morecore, __after_morecore_hook are undocumented
575 @c It's not clear whether to document them.
576
577 @node Statistics of Malloc
578 @subsection Statistics for Storage Allocation with @code{malloc}
579
580 @cindex allocation statistics
581 You can get information about dynamic storage allocation by calling the
582 @code{mstats} function.  This function and its associated data type are
583 declared in @file{malloc.h}; they are a GNU extension.
584 @pindex malloc.h
585
586 @comment malloc.h
587 @comment GNU
588 @deftp {Data Type} {struct mstats}
589 This structure type is used to return information about the dynamic
590 storage allocator.  It contains the following members:
591
592 @table @code
593 @item size_t bytes_total
594 This is the total size of memory managed by malloc, in bytes.
595
596 @item size_t chunks_used
597 This is the number of chunks in use.  (The storage allocator internally
598 gets chunks of memory from the operating system, and then carves them up
599 to satisfy individual @code{malloc} requests; see @ref{Efficiency and
600 Malloc}.)
601
602 @item size_t bytes_used
603 This is the number of bytes in use.
604
605 @item size_t chunks_free
606 This is the number of chunks which are free -- that is, that have been
607 allocated by the operating system to your program, but which are not
608 now being used.
609
610 @item size_t bytes_free
611 This is the number of bytes which are free.
612 @end table
613 @end deftp
614
615 @comment malloc.h
616 @comment GNU
617 @deftypefun {struct mstats} mstats (void)
618 This function returns information about the current dynamic memory usage
619 in a structure of type @code{struct mstats}.
620 @end deftypefun
621
622 @node Summary of Malloc
623 @subsection Summary of @code{malloc}-Related Functions
624
625 Here is a summary of the functions that work with @code{malloc}:
626
627 @table @code
628 @item void *malloc (size_t @var{size})
629 Allocate a block of @var{size} bytes.  @xref{Basic Allocation}.
630
631 @item void free (void *@var{addr})
632 Free a block previously allocated by @code{malloc}.  @xref{Freeing after
633 Malloc}.
634
635 @item void *realloc (void *@var{addr}, size_t @var{size})
636 Make a block previously allocated by @code{malloc} larger or smaller,
637 possibly by copying it to a new location.  @xref{Changing Block Size}.
638
639 @item void *calloc (size_t @var{count}, size_t @var{eltsize})
640 Allocate a block of @var{count} * @var{eltsize} bytes using
641 @code{malloc}, and set its contents to zero.  @xref{Allocating Cleared
642 Space}.
643
644 @item void *valloc (size_t @var{size})
645 Allocate a block @var{size} bytes, starting on a page boundary.
646 @xref{Aligned Memory Blocks}.
647
648 @item void *memalign (size_t @var{size}, size_t @var{boundary})
649 Allocate a block @var{size} bytes, starting on an address that is a
650 multiple of @var{boundary}.  @xref{Aligned Memory Blocks}.
651
652 @item void mcheck (void (*@var{abortfn}) (void))
653 Tell @code{malloc} to perform occasional consistency checks on
654 dynamically allocated memory, and to call @var{abortfn} when an
655 inconsistency is found.  @xref{Heap Consistency Checking}.
656
657 @item void *(*__malloc_hook) (size_t @var{size})
658 A pointer to a function that @code{malloc} uses whenever it is called.
659
660 @item void *(*__realloc_hook) (void *@var{ptr}, size_t @var{size})
661 A pointer to a function that @code{realloc} uses whenever it is called.
662
663 @item void (*__free_hook) (void *@var{ptr})
664 A pointer to a function that @code{free} uses whenever it is called.
665
666 @item void struct mstats mstats (void)
667 Read information about the current dynamic memory usage.
668 @xref{Statistics of Malloc}.
669 @end table
670
671 @node Obstacks
672 @section Obstacks
673 @cindex obstacks
674
675 An @dfn{obstack} is a pool of memory containing a stack of objects.  You
676 can create any number of separate obstacks, and then allocate objects in
677 specified obstacks.  Within each obstack, the last object allocated must
678 always be the first one freed, but distinct obstacks are independent of
679 each other.
680
681 Aside from this one constraint of order of freeing, obstacks are totally
682 general: an obstack can contain any number of objects of any size.  They
683 are implemented with macros, so allocation is usually very fast as long as
684 the objects are usually small.  And the only space overhead per object is
685 the padding needed to start each object on a suitable boundary.
686
687 @menu
688 * Creating Obstacks::           How to declare an obstack in your program.
689 * Preparing for Obstacks::      Preparations needed before you can
690                                  use obstacks.
691 * Allocation in an Obstack::    Allocating objects in an obstack.
692 * Freeing Obstack Objects::     Freeing objects in an obstack.
693 * Obstack Functions::           The obstack functions are both
694                                  functions and macros.
695 * Growing Objects::             Making an object bigger by stages.
696 * Extra Fast Growing::          Extra-high-efficiency (though more
697                                  complicated) growing objects.
698 * Status of an Obstack::        Inquiries about the status of an obstack.
699 * Obstacks Data Alignment::     Controlling alignment of objects in obstacks.
700 * Obstack Chunks::              How obstacks obtain and release chunks;
701                                  efficiency considerations.
702 * Summary of Obstacks::         
703 @end menu
704
705 @node Creating Obstacks
706 @subsection Creating Obstacks
707
708 The utilities for manipulating obstacks are declared in the header
709 file @file{obstack.h}.
710 @pindex obstack.h
711
712 @comment obstack.h
713 @comment GNU
714 @deftp {Data Type} {struct obstack}
715 An obstack is represented by a data structure of type @code{struct
716 obstack}.  This structure has a small fixed size; it records the status
717 of the obstack and how to find the space in which objects are allocated.
718 It does not contain any of the objects themselves.  You should not try
719 to access the contents of the structure directly; use only the functions
720 described in this chapter.
721 @end deftp
722
723 You can declare variables of type @code{struct obstack} and use them as
724 obstacks, or you can allocate obstacks dynamically like any other kind
725 of object.  Dynamic allocation of obstacks allows your program to have a
726 variable number of different stacks.  (You can even allocate an
727 obstack structure in another obstack, but this is rarely useful.)
728
729 All the functions that work with obstacks require you to specify which
730 obstack to use.  You do this with a pointer of type @code{struct obstack
731 *}.  In the following, we often say ``an obstack'' when strictly
732 speaking the object at hand is such a pointer.
733
734 The objects in the obstack are packed into large blocks called
735 @dfn{chunks}.  The @code{struct obstack} structure points to a chain of
736 the chunks currently in use.
737
738 The obstack library obtains a new chunk whenever you allocate an object
739 that won't fit in the previous chunk.  Since the obstack library manages
740 chunks automatically, you don't need to pay much attention to them, but
741 you do need to supply a function which the obstack library should use to
742 get a chunk.  Usually you supply a function which uses @code{malloc}
743 directly or indirectly.  You must also supply a function to free a chunk.
744 These matters are described in the following section.
745
746 @node Preparing for Obstacks
747 @subsection Preparing for Using Obstacks
748
749 Each source file in which you plan to use the obstack functions
750 must include the header file @file{obstack.h}, like this:
751
752 @example
753 #include <obstack.h>
754 @end example
755
756 @findex obstack_chunk_alloc
757 @findex obstack_chunk_free
758 Also, if the source file uses the macro @code{obstack_init}, it must
759 declare or define two functions or macros that will be called by the
760 obstack library.  One, @code{obstack_chunk_alloc}, is used to allocate the
761 chunks of memory into which objects are packed.  The other,
762 @code{obstack_chunk_free}, is used to return chunks when the objects in
763 them are freed.
764
765 Usually these are defined to use @code{malloc} via the intermediary
766 @code{xmalloc} (@pxref{Unconstrained Allocation}).  This is done with
767 the following pair of macro definitions:
768
769 @example
770 #define obstack_chunk_alloc xmalloc
771 #define obstack_chunk_free free
772 @end example
773
774 @noindent
775 Though the storage you get using obstacks really comes from @code{malloc},
776 using obstacks is faster because @code{malloc} is called less often, for
777 larger blocks of memory.  @xref{Obstack Chunks}, for full details.
778
779 At run time, before the program can use a @code{struct obstack} object
780 as an obstack, it must initialize the obstack by calling
781 @code{obstack_init}.
782
783 @comment obstack.h
784 @comment GNU
785 @deftypefun void obstack_init (struct obstack *@var{obstack_ptr})
786 Initialize obstack @var{obstack_ptr} for allocation of objects.
787 @end deftypefun
788
789 Here are two examples of how to allocate the space for an obstack and
790 initialize it.  First, an obstack that is a static variable:
791
792 @example
793 struct obstack myobstack;
794 @dots{}
795 obstack_init (&myobstack);
796 @end example
797
798 @noindent
799 Second, an obstack that is itself dynamically allocated:
800
801 @example
802 struct obstack *myobstack_ptr
803   = (struct obstack *) xmalloc (sizeof (struct obstack));
804
805 obstack_init (myobstack_ptr);
806 @end example
807
808 @node Allocation in an Obstack
809 @subsection Allocation in an Obstack
810 @cindex allocation (obstacks)
811
812 The most direct way to allocate an object in an obstack is with
813 @code{obstack_alloc}, which is invoked almost like @code{malloc}.
814
815 @comment obstack.h
816 @comment GNU
817 @deftypefun {void *} obstack_alloc (struct obstack *@var{obstack_ptr}, size_t @var{size})
818 This allocates an uninitialized block of @var{size} bytes in an obstack
819 and returns its address.  Here @var{obstack_ptr} specifies which obstack
820 to allocate the block in; it is the address of the @code{struct obstack}
821 object which represents the obstack.  Each obstack function or macro
822 requires you to specify an @var{obstack_ptr} as the first argument.
823 @end deftypefun
824
825 For example, here is a function that allocates a copy of a string @var{str}
826 in a specific obstack, which is the variable @code{string_obstack}:
827
828 @example
829 struct obstack string_obstack;
830
831 char *
832 copystring (char *string)
833 @{
834   char *s = (char *) obstack_alloc (&string_obstack,
835                                     strlen (string) + 1);
836   memcpy (s, string, strlen (string));
837   return s;
838 @}
839 @end example
840
841 To allocate a block with specified contents, use the function
842 @code{obstack_copy}, declared like this:
843
844 @comment obstack.h
845 @comment GNU
846 @deftypefun {void *} obstack_copy (struct obstack *@var{obstack_ptr}, void *@var{address}, size_t @var{size})
847 This allocates a block and initializes it by copying @var{size}
848 bytes of data starting at @var{address}.
849 @end deftypefun
850
851 @comment obstack.h
852 @comment GNU
853 @deftypefun {void *} obstack_copy0 (struct obstack *@var{obstack_ptr}, void *@var{address}, size_t @var{size})
854 Like @code{obstack_copy}, but appends an extra byte containing a null
855 character.  This extra byte is not counted in the argument @var{size}.
856 @end deftypefun
857
858 The @code{obstack_copy0} function is convenient for copying a sequence
859 of characters into an obstack as a null-terminated string.  Here is an
860 example of its use:
861
862 @example
863 char *
864 obstack_savestring (char *addr, size_t size)
865 @{
866   return obstack_copy0 (&myobstack, addr, size);
867 @}
868 @end example
869
870 @noindent
871 Contrast this with the previous example of @code{savestring} using
872 @code{malloc} (@pxref{Basic Allocation}).
873
874 @node Freeing Obstack Objects
875 @subsection Freeing Objects in an Obstack
876 @cindex freeing (obstacks)
877
878 To free an object allocated in an obstack, use the function
879 @code{obstack_free}.  Since the obstack is a stack of objects, freeing
880 one object automatically frees all other objects allocated more recently
881 in the same obstack.
882
883 @comment obstack.h
884 @comment GNU
885 @deftypefun void obstack_free (struct obstack *@var{obstack_ptr}, void *@var{object})
886 If @var{object} is a null pointer, everything allocated in the obstack
887 is freed.  Otherwise, @var{object} must be the address of an object
888 allocated in the obstack.  Then @var{object} is freed, along with
889 everything allocated in @var{obstack} since @var{object}.
890 @end deftypefun
891
892 Note that if @var{object} is a null pointer, the result is an
893 uninitialized obstack.  To free all storage in an obstack but leave it
894 valid for further allocation, call @code{obstack_free} with the address
895 of the first object allocated on the obstack:
896
897 @example
898 obstack_free (obstack_ptr, first_object_allocated_ptr);
899 @end example
900
901 Recall that the objects in an obstack are grouped into chunks.  When all
902 the objects in a chunk become free, the obstack library automatically
903 frees the chunk (@pxref{Preparing for Obstacks}).  Then other
904 obstacks, or non-obstack allocation, can reuse the space of the chunk.
905
906 @node Obstack Functions
907 @subsection Obstack Functions and Macros
908 @cindex macros
909
910 The interfaces for using obstacks may be defined either as functions or
911 as macros, depending on the compiler.  The obstack facility works with
912 all C compilers, including both ANSI C and traditional C, but there are
913 precautions you must take if you plan to use compilers other than GNU C.
914
915 If you are using an old-fashioned non-ANSI C compiler, all the obstack
916 ``functions'' are actually defined only as macros.  You can call these
917 macros like functions, but you cannot use them in any other way (for
918 example, you cannot take their address).
919
920 Calling the macros requires a special precaution: namely, the first
921 operand (the obstack pointer) may not contain any side effects, because
922 it may be computed more than once.  For example, if you write this:
923
924 @example
925 obstack_alloc (get_obstack (), 4);
926 @end example
927
928 @noindent
929 you will find that @code{get_obstack} may be called several times.
930 If you use @code{*obstack_list_ptr++} as the obstack pointer argument,
931 you will get very strange results since the incrementation may occur
932 several times.
933
934 In ANSI C, each function has both a macro definition and a function
935 definition.  The function definition is used if you take the address of the
936 function without calling it.  An ordinary call uses the macro definition by
937 default, but you can request the function definition instead by writing the
938 function name in parentheses, as shown here:
939
940 @example
941 char *x;
942 void *(*funcp) ();
943 /* @r{Use the macro}.  */
944 x = (char *) obstack_alloc (obptr, size);
945 /* @r{Call the function}.  */
946 x = (char *) (obstack_alloc) (obptr, size);
947 /* @r{Take the address of the function}.  */
948 funcp = obstack_alloc;
949 @end example
950
951 @noindent
952 This is the same situation that exists in ANSI C for the standard library
953 functions.  @xref{Macro Definitions}.
954
955 @strong{Warning:} When you do use the macros, you must observe the
956 precaution of avoiding side effects in the first operand, even in ANSI
957 C.
958
959 If you use the GNU C compiler, this precaution is not necessary, because
960 various language extensions in GNU C permit defining the macros so as to
961 compute each argument only once.
962
963 @node Growing Objects
964 @subsection Growing Objects
965 @cindex growing objects (in obstacks)
966 @cindex changing the size of a block (obstacks)
967
968 Because storage in obstack chunks is used sequentially, it is possible to
969 build up an object step by step, adding one or more bytes at a time to the
970 end of the object.  With this technique, you do not need to know how much
971 data you will put in the object until you come to the end of it.  We call
972 this the technique of @dfn{growing objects}.  The special functions
973 for adding data to the growing object are described in this section.
974
975 You don't need to do anything special when you start to grow an object.
976 Using one of the functions to add data to the object automatically
977 starts it.  However, it is necessary to say explicitly when the object is
978 finished.  This is done with the function @code{obstack_finish}.
979
980 The actual address of the object thus built up is not known until the
981 object is finished.  Until then, it always remains possible that you will
982 add so much data that the object must be copied into a new chunk.
983
984 While the obstack is in use for a growing object, you cannot use it for
985 ordinary allocation of another object.  If you try to do so, the space
986 already added to the growing object will become part of the other object.
987
988 @comment obstack.h
989 @comment GNU
990 @deftypefun void obstack_blank (struct obstack *@var{obstack_ptr}, size_t @var{size})
991 The most basic function for adding to a growing object is
992 @code{obstack_blank}, which adds space without initializing it.
993 @end deftypefun
994
995 @comment obstack.h
996 @comment GNU
997 @deftypefun void obstack_grow (struct obstack *@var{obstack_ptr}, void *@var{data}, size_t @var{size})
998 To add a block of initialized space, use @code{obstack_grow}, which is
999 the growing-object analogue of @code{obstack_copy}.  It adds @var{size}
1000 bytes of data to the growing object, copying the contents from
1001 @var{data}.
1002 @end deftypefun
1003
1004 @comment obstack.h
1005 @comment GNU
1006 @deftypefun void obstack_grow0 (struct obstack *@var{obstack_ptr}, void *@var{data}, size_t @var{size})
1007 This is the growing-object analogue of @code{obstack_copy0}.  It adds
1008 @var{size} bytes copied from @var{data}, followed by an additional null
1009 character.
1010 @end deftypefun
1011
1012 @comment obstack.h
1013 @comment GNU
1014 @deftypefun void obstack_1grow (struct obstack *@var{obstack_ptr}, char @var{c})
1015 To add one character at a time, use the function @code{obstack_1grow}.
1016 It adds a single byte containing @var{c} to the growing object.
1017 @end deftypefun
1018
1019 @comment obstack.h
1020 @comment GNU
1021 @deftypefun {void *} obstack_finish (struct obstack *@var{obstack_ptr})
1022 When you are finished growing the object, use the function
1023 @code{obstack_finish} to close it off and return its final address.
1024
1025 Once you have finished the object, the obstack is available for ordinary
1026 allocation or for growing another object.
1027 @end deftypefun
1028
1029 When you build an object by growing it, you will probably need to know
1030 afterward how long it became.  You need not keep track of this as you grow
1031 the object, because you can find out the length from the obstack just
1032 before finishing the object with the function @code{obstack_object_size},
1033 declared as follows:
1034
1035 @comment obstack.h
1036 @comment GNU
1037 @deftypefun size_t obstack_object_size (struct obstack *@var{obstack_ptr})
1038 This function returns the current size of the growing object, in bytes.
1039 Remember to call this function @emph{before} finishing the object.
1040 After it is finished, @code{obstack_object_size} will return zero.
1041 @end deftypefun
1042
1043 If you have started growing an object and wish to cancel it, you should
1044 finish it and then free it, like this:
1045
1046 @example
1047 obstack_free (obstack_ptr, obstack_finish (obstack_ptr));
1048 @end example
1049
1050 @noindent
1051 This has no effect if no object was growing.
1052
1053 @cindex shrinking objects
1054 You can use @code{obstack_blank} with a negative size argument to make
1055 the current object smaller.  Just don't try to shrink it beyond zero
1056 length---there's no telling what will happen if you do that.
1057
1058 @node Extra Fast Growing
1059 @subsection Extra Fast Growing Objects
1060 @cindex efficiency and obstacks
1061
1062 The usual functions for growing objects incur overhead for checking
1063 whether there is room for the new growth in the current chunk.  If you
1064 are frequently constructing objects in small steps of growth, this
1065 overhead can be significant.
1066
1067 You can reduce the overhead by using special ``fast growth''
1068 functions that grow the object without checking.  In order to have a
1069 robust program, you must do the checking yourself.  If you do this checking
1070 in the simplest way each time you are about to add data to the object, you
1071 have not saved anything, because that is what the ordinary growth
1072 functions do.  But if you can arrange to check less often, or check
1073 more efficiently, then you make the program faster.
1074
1075 The function @code{obstack_room} returns the amount of room available
1076 in the current chunk.  It is declared as follows:
1077
1078 @comment obstack.h
1079 @comment GNU
1080 @deftypefun size_t obstack_room (struct obstack *@var{obstack_ptr})
1081 This returns the number of bytes that can be added safely to the current
1082 growing object (or to an object about to be started) in obstack
1083 @var{obstack} using the fast growth functions.
1084 @end deftypefun
1085
1086 While you know there is room, you can use these fast growth functions
1087 for adding data to a growing object:
1088
1089 @comment obstack.h
1090 @comment GNU
1091 @deftypefun void obstack_1grow_fast (struct obstack *@var{obstack_ptr}, char @var{c})
1092 The function @code{obstack_1grow_fast} adds one byte containing the
1093 character @var{c} to the growing object in obstack @var{obstack_ptr}.
1094 @end deftypefun
1095
1096 @comment obstack.h
1097 @comment GNU
1098 @deftypefun void obstack_blank_fast (struct obstack *@var{obstack_ptr}, size_t @var{size})
1099 The function @code{obstack_blank_fast} adds @var{size} bytes to the
1100 growing object in obstack @var{obstack_ptr} without initializing them.
1101 @end deftypefun
1102
1103 When you check for space using @code{obstack_room} and there is not
1104 enough room for what you want to add, the fast growth functions
1105 are not safe.  In this case, simply use the corresponding ordinary
1106 growth function instead.  Very soon this will copy the object to a
1107 new chunk; then there will be lots of room available again. 
1108
1109 So, each time you use an ordinary growth function, check afterward for
1110 sufficient space using @code{obstack_room}.  Once the object is copied
1111 to a new chunk, there will be plenty of space again, so the program will
1112 start using the fast growth functions again.
1113
1114 Here is an example:
1115
1116 @example
1117 @group
1118 void
1119 add_string (struct obstack *obstack, char *ptr, size_t len)
1120 @{
1121   while (len > 0)
1122     @{
1123       if (obstack_room (obstack) > len)
1124         @{
1125           /* @r{We have enough room: add everything fast.}  */
1126           while (len-- > 0)
1127             obstack_1grow_fast (obstack, *ptr++);
1128         @}
1129       else
1130         @{
1131           /* @r{Not enough room. Add one character slowly,}
1132              @r{which may copy to a new chunk and make room.}  */
1133           obstack_1grow (obstack, *ptr++);
1134           len--;
1135         @}
1136     @}
1137 @}
1138 @end group
1139 @end example
1140
1141 @node Status of an Obstack
1142 @subsection Status of an Obstack
1143 @cindex obstack status
1144 @cindex status of obstack
1145
1146 Here are functions that provide information on the current status of
1147 allocation in an obstack.  You can use them to learn about an object while
1148 still growing it.
1149
1150 @comment obstack.h
1151 @comment GNU
1152 @deftypefun {void *} obstack_base (struct obstack *@var{obstack_ptr})
1153 This function returns the tentative address of the beginning of the
1154 currently growing object in @var{obstack_ptr}.  If you finish the object
1155 immediately, it will have that address.  If you make it larger first, it
1156 may outgrow the current chunk---then its address will change!
1157
1158 If no object is growing, this value says where the next object you
1159 allocate will start (once again assuming it fits in the current
1160 chunk).
1161 @end deftypefun
1162
1163 @comment obstack.h
1164 @comment GNU
1165 @deftypefun {void *} obstack_next_free (struct obstack *@var{obstack_ptr})
1166 This function returns the address of the first free byte in the current
1167 chunk of obstack @var{obstack_ptr}.  This is the end of the currently
1168 growing object.  If no object is growing, @code{obstack_next_free}
1169 returns the same value as @code{obstack_base}.
1170 @end deftypefun
1171
1172 @comment obstack.h
1173 @comment GNU
1174 @deftypefun size_t obstack_object_size (struct obstack *@var{obstack_ptr})
1175 This function returns the size in bytes of the currently growing object.
1176 This is equivalent to
1177
1178 @example
1179 obstack_next_free (@var{obstack_ptr}) - obstack_base (@var{obstack_ptr})
1180 @end example
1181 @end deftypefun
1182
1183 @node Obstacks Data Alignment
1184 @subsection Alignment of Data in Obstacks
1185 @cindex alignment (in obstacks)
1186
1187 Each obstack has an @dfn{alignment boundary}; each object allocated in
1188 the obstack automatically starts on an address that is a multiple of the
1189 specified boundary.  By default, this boundary is 4 bytes.
1190
1191 To access an obstack's alignment boundary, use the macro
1192 @code{obstack_alignment_mask}, whose function prototype looks like
1193 this:
1194
1195 @comment obstack.h
1196 @comment GNU
1197 @deftypefn Macro int obstack_alignment_mask (struct obstack *@var{obstack_ptr})
1198 The value is a bit mask; a bit that is 1 indicates that the corresponding
1199 bit in the address of an object should be 0.  The mask value should be one
1200 less than a power of 2; the effect is that all object addresses are
1201 multiples of that power of 2.  The default value of the mask is 3, so that
1202 addresses are multiples of 4.  A mask value of 0 means an object can start
1203 on any multiple of 1 (that is, no alignment is required).
1204
1205 The expansion of the macro @code{obstack_alignment_mask} is an lvalue,
1206 so you can alter the mask by assignment.  For example, this statement:
1207
1208 @example
1209 obstack_alignment_mask (obstack_ptr) = 0;
1210 @end example
1211
1212 @noindent
1213 has the effect of turning off alignment processing in the specified obstack.
1214 @end deftypefn
1215
1216 Note that a change in alignment mask does not take effect until
1217 @emph{after} the next time an object is allocated or finished in the
1218 obstack.  If you are not growing an object, you can make the new
1219 alignment mask take effect immediately by calling @code{obstack_finish}.
1220 This will finish a zero-length object and then do proper alignment for
1221 the next object.
1222
1223 @node Obstack Chunks
1224 @subsection Obstack Chunks
1225 @cindex efficiency of chunks
1226 @cindex chunks
1227
1228 Obstacks work by allocating space for themselves in large chunks, and
1229 then parceling out space in the chunks to satisfy your requests.  Chunks
1230 are normally 4096 bytes long unless you specify a different chunk size.
1231 The chunk size includes 8 bytes of overhead that are not actually used
1232 for storing objects.  Regardless of the specified size, longer chunks
1233 will be allocated when necessary for long objects.
1234
1235 The obstack library allocates chunks by calling the function
1236 @code{obstack_chunk_alloc}, which you must define.  When a chunk is no
1237 longer needed because you have freed all the objects in it, the obstack
1238 library frees the chunk by calling @code{obstack_chunk_free}, which you
1239 must also define.
1240
1241 These two must be defined (as macros) or declared (as functions) in each
1242 source file that uses @code{obstack_init} (@pxref{Creating Obstacks}).
1243 Most often they are defined as macros like this:
1244
1245 @example
1246 #define obstack_chunk_alloc xmalloc
1247 #define obstack_chunk_free free
1248 @end example
1249
1250 Note that these are simple macros (no arguments).  Macro definitions with
1251 arguments will not work!  It is necessary that @code{obstack_chunk_alloc}
1252 or @code{obstack_chunk_free}, alone, expand into a function name if it is
1253 not itself a function name.
1254
1255 The function that actually implements @code{obstack_chunk_alloc} cannot
1256 return ``failure'' in any fashion, because the obstack library is not
1257 prepared to handle failure.  Therefore, @code{malloc} itself is not
1258 suitable.  If the function cannot obtain space, it should either
1259 terminate the process (@pxref{Program Termination}) or do a nonlocal
1260 exit using @code{longjmp} (@pxref{Non-Local Exits}).
1261
1262 If you allocate chunks with @code{malloc}, the chunk size should be a
1263 power of 2.  The default chunk size, 4096, was chosen because it is long
1264 enough to satisfy many typical requests on the obstack yet short enough
1265 not to waste too much memory in the portion of the last chunk not yet used.
1266
1267 @comment obstack.h
1268 @comment GNU
1269 @deftypefn Macro size_t obstack_chunk_size (struct obstack *@var{obstack_ptr})
1270 This returns the chunk size of the given obstack.
1271 @end deftypefn
1272
1273 Since this macro expands to an lvalue, you can specify a new chunk size by
1274 assigning it a new value.  Doing so does not affect the chunks already
1275 allocated, but will change the size of chunks allocated for that particular
1276 obstack in the future.  It is unlikely to be useful to make the chunk size
1277 smaller, but making it larger might improve efficiency if you are
1278 allocating many objects whose size is comparable to the chunk size.  Here
1279 is how to do so cleanly:
1280
1281 @example
1282 if (obstack_chunk_size (obstack_ptr) < @var{new_chunk_size})
1283   obstack_chunk_size (obstack_ptr) = @var{new_chunk_size};
1284 @end example
1285
1286 @node Summary of Obstacks
1287 @subsection Summary of Obstack Functions
1288
1289 Here is a summary of all the functions associated with obstacks.  Each
1290 takes the address of an obstack (@code{struct obstack *}) as its first
1291 argument.
1292
1293 @table @code
1294 @item void obstack_init (struct obstack *@var{obstack_ptr})
1295 Initialize use of an obstack.  @xref{Creating Obstacks}.
1296
1297 @item void *obstack_alloc (struct obstack *@var{obstack_ptr}, size_t @var{size})
1298 Allocate an object of @var{size} uninitialized bytes.
1299 @xref{Allocation in an Obstack}.
1300
1301 @item void *obstack_copy (struct obstack *@var{obstack_ptr}, void *@var{address}, size_t @var{size})
1302 Allocate an object of @var{size} bytes, with contents copied from
1303 @var{address}.  @xref{Allocation in an Obstack}.
1304
1305 @item void *obstack_copy0 (struct obstack *@var{obstack_ptr}, void *@var{address}, size_t @var{size})
1306 Allocate an object of @var{size}+1 bytes, with @var{size} of them copied
1307 from @var{address}, followed by a null character at the end.
1308 @xref{Allocation in an Obstack}.
1309
1310 @item void obstack_free (struct obstack *@var{obstack_ptr}, void *@var{object})
1311 Free @var{object} (and everything allocated in the specified obstack
1312 more recently than @var{object}).  @xref{Freeing Obstack Objects}.
1313
1314 @item void obstack_blank (struct obstack *@var{obstack_ptr}, size_t @var{size})
1315 Add @var{size} uninitialized bytes to a growing object.
1316 @xref{Growing Objects}.
1317
1318 @item void obstack_grow (struct obstack *@var{obstack_ptr}, void *@var{address}, size_t @var{size})
1319 Add @var{size} bytes, copied from @var{address}, to a growing object.
1320 @xref{Growing Objects}.
1321
1322 @item void obstack_grow0 (struct obstack *@var{obstack_ptr}, void *@var{address}, size_t @var{size})
1323 Add @var{size} bytes, copied from @var{address}, to a growing object,
1324 and then add another byte containing a null character.  @xref{Growing
1325 Objects}.
1326
1327 @item void obstack_1grow (struct obstack *@var{obstack_ptr}, char @var{data_char})
1328 Add one byte containing @var{data_char} to a growing object.
1329 @xref{Growing Objects}.
1330
1331 @item void *obstack_finish (struct obstack *@var{obstack_ptr})
1332 Finalize the object that is growing and return its permanent address.
1333 @xref{Growing Objects}.
1334
1335 @item size_t obstack_object_size (struct obstack *@var{obstack_ptr})
1336 Get the current size of the currently growing object.  @xref{Growing
1337 Objects}.
1338
1339 @item void obstack_blank_fast (struct obstack *@var{obstack_ptr}, size_t @var{size})
1340 Add @var{size} uninitialized bytes to a growing object without checking
1341 that there is enough room.  @xref{Extra Fast Growing}.
1342
1343 @item void obstack_1grow_fast (struct obstack *@var{obstack_ptr}, char @var{data_char})
1344 Add one byte containing @var{data_char} to a growing object without
1345 checking that there is enough room.  @xref{Extra Fast Growing}.
1346
1347 @item size_t obstack_room (struct obstack *@var{obstack_ptr})
1348 Get the amount of room now available for growing the current object.
1349 @xref{Extra Fast Growing}.
1350
1351 @item int obstack_alignment_mask (struct obstack *@var{obstack_ptr})
1352 The mask used for aligning the beginning of an object.  This is an
1353 lvalue.  @xref{Obstacks Data Alignment}.
1354
1355 @item size_t obstack_chunk_size (struct obstack *@var{obstack_ptr})
1356 The size for allocating chunks.  This is an lvalue.  @xref{Obstack Chunks}.
1357
1358 @item void *obstack_base (struct obstack *@var{obstack_ptr})
1359 Tentative starting address of the currently growing object.
1360 @xref{Status of an Obstack}.
1361
1362 @item void *obstack_next_free (struct obstack *@var{obstack_ptr})
1363 Address just after the end of the currently growing object.
1364 @xref{Status of an Obstack}.
1365 @end table
1366
1367 @node Variable Size Automatic
1368 @section Automatic Storage with Variable Size
1369 @cindex automatic freeing
1370 @cindex @code{alloca} function
1371 @cindex automatic storage with variable size
1372
1373 The function @code{alloca} supports a kind of half-dynamic allocation in
1374 which blocks are allocated dynamically but freed automatically.
1375
1376 Allocating a block with @code{alloca} is an explicit action; you can
1377 allocate as many blocks as you wish, and compute the size at run time.  But
1378 all the blocks are freed when you exit the function that @code{alloca} was
1379 called from, just as if they were automatic variables declared in that
1380 function.  There is no way to free the space explicitly.
1381
1382 The prototype for @code{alloca} is in @file{stdlib.h}.  This function is
1383 a BSD extension.
1384 @pindex stdlib.h
1385
1386 @comment stdlib.h
1387 @comment GNU, BSD
1388 @deftypefun {void *} alloca (size_t @var{size});
1389 The return value of @code{alloca} is the address of a block of @var{size}
1390 bytes of storage, allocated in the stack frame of the calling function.
1391 @end deftypefun
1392
1393 Do not use @code{alloca} inside the arguments of a function call---you
1394 will get unpredictable results, because the stack space for the
1395 @code{alloca} would appear on the stack in the middle of the space for
1396 the function arguments.  An example of what to avoid is @code{foo (x,
1397 alloca (4), y)}.
1398 @c This might get fixed in future versions of GCC, but that won't make
1399 @c it safe with compilers generally.
1400
1401 @menu
1402 * Alloca Example::              Example of using @code{alloca}.
1403 * Advantages of Alloca::        Reasons to use @code{alloca}.
1404 * Disadvantages of Alloca::     Reasons to avoid @code{alloca}.
1405 * GNU C Variable-Size Arrays::  Only in GNU C, here is an alternative
1406                                  method of allocating dynamically and
1407                                  freeing automatically.
1408 @end menu
1409
1410 @node Alloca Example
1411 @subsection @code{alloca} Example
1412
1413 As an example of use of @code{alloca}, here is a function that opens a file
1414 name made from concatenating two argument strings, and returns a file
1415 descriptor or minus one signifying failure:
1416
1417 @example
1418 int
1419 open2 (char *str1, char *str2, int flags, int mode)
1420 @{
1421   char *name = (char *) alloca (strlen (str1) + strlen (str2) + 1);
1422   strcpy (name, str1);
1423   strcat (name, str2);
1424   return open (name, flags, mode);
1425 @}
1426 @end example
1427
1428 @noindent
1429 Here is how you would get the same results with @code{malloc} and
1430 @code{free}:
1431
1432 @example
1433 int
1434 open2 (char *str1, char *str2, int flags, int mode)
1435 @{
1436   char *name = (char *) malloc (strlen (str1) + strlen (str2) + 1);
1437   int desc;
1438   if (name == 0)
1439     fatal ("virtual memory exceeded");
1440   strcpy (name, str1);
1441   strcat (name, str2);
1442   desc = open (name, flags, mode);
1443   free (name);
1444   return desc;
1445 @}
1446 @end example
1447
1448 As you can see, it is simpler with @code{alloca}.  But @code{alloca} has
1449 other, more important advantages, and some disadvantages.
1450
1451 @node Advantages of Alloca
1452 @subsection Advantages of @code{alloca}
1453
1454 Here are the reasons why @code{alloca} may be preferable to @code{malloc}:
1455
1456 @itemize @bullet
1457 @item
1458 Using @code{alloca} wastes very little space and is very fast.  (It is
1459 open-coded by the GNU C compiler.)
1460
1461 @item
1462 Since @code{alloca} does not have separate pools for different sizes of
1463 block, space used for any size block can be reused for any other size.
1464 @code{alloca} does not cause storage fragmentation.
1465
1466 @item
1467 @cindex longjmp
1468 Nonlocal exits done with @code{longjmp} (@pxref{Non-Local Exits})
1469 automatically free the space allocated with @code{alloca} when they exit
1470 through the function that called @code{alloca}.  This is the most
1471 important reason to use @code{alloca}.
1472
1473 To illustrate this, suppose you have a function
1474 @code{open_or_report_error} which returns a descriptor, like
1475 @code{open}, if it succeeds, but does not return to its caller if it
1476 fails.  If the file cannot be opened, it prints an error message and
1477 jumps out to the command level of your program using @code{longjmp}.
1478 Let's change @code{open2} (@pxref{Alloca Example}) to use this
1479 subroutine:@refill
1480
1481 @example
1482 int
1483 open2 (char *str1, char *str2, int flags, int mode)
1484 @{
1485   char *name = (char *) alloca (strlen (str1) + strlen (str2) + 1);
1486   strcpy (name, str1);
1487   strcat (name, str2);
1488   return open_or_report_error (name, flags, mode);
1489 @}
1490 @end example
1491
1492 @noindent
1493 Because of the way @code{alloca} works, the storage it allocates is
1494 freed even when an error occurs, with no special effort required.
1495
1496 By contrast, the previous definition of @code{open2} (which uses
1497 @code{malloc} and @code{free}) would develop a storage leak if it were
1498 changed in this way.  Even if you are willing to make more changes to
1499 fix it, there is no easy way to do so.
1500 @end itemize
1501
1502 @node Disadvantages of Alloca
1503 @subsection Disadvantages of @code{alloca}
1504
1505 @cindex @code{alloca} disadvantages
1506 @cindex disadvantages of @code{alloca}
1507 These are the disadvantages of @code{alloca} in comparison with
1508 @code{malloc}:
1509
1510 @itemize @bullet
1511 @item
1512 If you try to allocate more storage than the machine can provide, you
1513 don't get a clean error message.  Instead you get a fatal signal like
1514 the one you would get from an infinite recursion; probably a
1515 segmentation violation (@pxref{Program Error Signals}).
1516
1517 @item
1518 Some non-GNU systems fail to support @code{alloca}, so it is less
1519 portable.  However, a slower emulation of @code{alloca} written in C
1520 is available for use on systems with this deficiency.
1521 @end itemize
1522
1523 @node GNU C Variable-Size Arrays
1524 @subsection GNU C Variable-Size Arrays
1525 @cindex variable-sized arrays
1526
1527 In GNU C, you can replace most uses of @code{alloca} with an array of
1528 variable size.  Here is how @code{open2} would look then:
1529
1530 @example
1531 int open2 (char *str1, char *str2, int flags, int mode)
1532 @{
1533   char name[strlen (str1) + strlen (str2) + 1];
1534   strcpy (name, str1);
1535   strcat (name, str2);
1536   return open (name, flags, mode);
1537 @}
1538 @end example
1539
1540 But @code{alloca} is not always equivalent to a variable-sized array, for
1541 several reasons:
1542
1543 @itemize @bullet
1544 @item
1545 A variable size array's space is freed at the end of the scope of the
1546 name of the array.  The space allocated with @code{alloca} usually
1547 remains until the end of the function.
1548
1549 @item
1550 It is possible to use @code{alloca} within a loop, allocating an
1551 additional block on each iteration.  This is impossible with
1552 variable-sized arrays.  On the other hand, this is also slightly
1553 unclean.
1554 @end itemize
1555
1556 @strong{Note:} If you mix use of @code{alloca} and variable-sized arrays
1557 within one function, exiting a scope in which a variable-sized array was
1558 declared frees all blocks allocated with @code{alloca} during the
1559 execution of that scope.
1560
1561
1562 @node Relocating Allocator
1563 @section Relocating Allocator
1564
1565 @cindex relocating memory allocator
1566 Any system of dynamic memory allocation has overhead: the amount of
1567 space it uses is more than the amount the program asks for.  The
1568 @dfn{relocating memory allocator} achieves very low overhead by moving
1569 blocks in memory as necessary, on its own initiative.
1570
1571 @menu
1572 * Relocator Concepts::          How to understand relocating allocation.
1573 * Using Relocator::             Functions for relocating allocation.
1574 @end menu
1575
1576 @node Relocator Concepts
1577 @subsection Concepts of Relocating Allocation
1578
1579 @ifinfo
1580 The @dfn{relocating memory allocator} achieves very low overhead by
1581 moving blocks in memory as necessary, on its own initiative.
1582 @end ifinfo
1583
1584 When you allocate a block with @code{malloc}, the address of the block
1585 never changes unless you use @code{realloc} to change its size.  Thus,
1586 you can safely store the address in various places, temporarily or
1587 permanently, as you like.  This is not safe when you use the relocating
1588 memory allocator, because any and all relocatable blocks can move
1589 whenever you allocate memory in any fashion.  Even calling @code{malloc}
1590 or @code{realloc} can move the relocatable blocks.
1591
1592 @cindex handle
1593 For each relocatable block, you must make a @dfn{handle}---a pointer
1594 object in memory, designated to store the address of that block.  The
1595 relocating allocator knows where each block's handle is, and updates the
1596 address stored there whenever it moves the block, so that the handle
1597 always points to the block.  Each time you access the contents of the
1598 block, you should fetch its address anew from the handle.
1599
1600 To call any of the relocating allocator functions from a signal handler
1601 is almost certainly incorrect, because the signal could happen at any
1602 time and relocate all the blocks.  The only way to make this safe is to
1603 block the signal around any access to the contents of any relocatable
1604 block---not a convenient mode of operation.  @xref{Nonreentrancy}.
1605
1606 @node Using Relocator
1607 @subsection Allocating and Freeing Relocatable Blocks
1608
1609 @pindex malloc.h
1610 In the descriptions below, @var{handleptr} designates the address of the
1611 handle.  All the functions are declared in @file{malloc.h}; all are GNU
1612 extensions.
1613
1614 @comment malloc.h
1615 @comment GNU
1616 @deftypefun {void *} r_alloc (void **@var{handleptr}, size_t @var{size})
1617 This function allocates a relocatable block of size @var{size}.  It
1618 stores the block's address in @code{*@var{handleptr}} and returns
1619 a non-null pointer to indicate success.
1620
1621 If @code{r_alloc} can't get the space needed, it stores a null pointer
1622 in @code{*@var{handleptr}}, and returns a null pointer.
1623 @end deftypefun
1624
1625 @comment malloc.h
1626 @comment GNU
1627 @deftypefun void r_alloc_free (void **@var{handleptr})
1628 This function is the way to free a relocatable block.  It frees the
1629 block that @code{*@var{handleptr}} points to, and stores a null pointer
1630 in @code{*@var{handleptr}} to show it doesn't point to an allocated
1631 block any more.
1632 @end deftypefun
1633
1634 @comment malloc.h
1635 @comment GNU
1636 @deftypefun {void *} r_re_alloc (void **@var{handleptr}, size_t @var{size})
1637 The function @code{r_re_alloc} adjusts the size of the block that
1638 @code{*@var{handleptr}} points to, making it @var{size} bytes long.  It
1639 stores the address of the resized block in @code{*@var{handleptr}} and
1640 returns a non-null pointer to indicate success.
1641
1642 If enough memory is not available, this function returns a null pointer
1643 and does not modify @code{*@var{handleptr}}.
1644 @end deftypefun
1645
1646 @node Memory Warnings
1647 @section Memory Usage Warnings
1648 @cindex memory usage warnings
1649 @cindex warnings of memory almost full
1650
1651 @pindex malloc.c
1652 You can ask for warnings as the program approaches running out of memory
1653 space, by calling @code{memory_warnings}.  This is a GNU extension
1654 declared in @file{malloc.h}.
1655
1656 @comment malloc.h
1657 @comment GNU
1658 @deftypefun void memory_warnings (void *@var{start}, void (*@var{warn_func}) (char *))
1659 Call this function to request warnings for nearing exhaustion of virtual
1660 memory.
1661
1662 The argument @var{start} says where data space begins, in memory.  The
1663 allocator compares this against the last address used and against the
1664 limit of data space, to determine the fraction of available memory in
1665 use.  If you supply zero for @var{start}, then a default value is used
1666 which is right in most circumstances.
1667
1668 For @var{warn_func}, supply a function that @code{malloc} can call to
1669 warn you.  It is called with a string (a warning message) as argument.
1670 Normally it ought to display the string for the user to read.
1671 @end deftypefun
1672
1673 The warnings come when memory becomes 75% full, when it becomes 85%
1674 full, and when it becomes 95% full.  Above 95% you get another warning
1675 each time memory usage increases.
1676