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