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