0d1f75519ea14b80963ff2eabb66c0f0d33469d9
[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 * Efficient use of @code{malloc}::      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 Efficient Use of @code{malloc}
389 @subsection Efficient Use of @code{malloc}
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.  In addition, it needs four bytes before the
397 beginning of each block for record-keeping.
398
399 Therefore, when you call @code{malloc} with argument @var{n}, the amount of
400 space actually used up is the smallest power of two not less than @var{n} +
401 4.  If you are free to choose the size of a block in order to make
402 @code{malloc} more efficient, make it four less than a power of two.
403
404 In addition, the pools for different powers of two remain separate forever;
405 a block of 28 bytes (32 minus 4) can never be split into two blocks of 12
406 bytes (16 minus 4).  So it is good if you manage to use blocks of the same
407 size for as many different purposes as possible.
408
409 @node Allocation with Specified Alignment
410 @subsection Allocation with Specified Alignment
411
412 @cindex page boundary
413 @cindex alignment (with malloc)
414 The address of a block returned by @code{malloc} or @code{realloc} in
415 the GNU system is always a multiple of eight.  If you need a block whose
416 address is a multiple of a higher power of two than that, use
417 @code{memalign} or @code{valloc}.  These functions are declared in
418 @file{<stdlib.h>}.
419
420 @strong{Incomplete:}  @code{memalign} is not actually defined!!
421
422 @deftypefun {void *} memalign (size_t @var{size}, int @var{boundary})
423 The @code{memalign} function allocates a block of @var{size} bytes whose
424 address is a multiple of @var{boundary}.  The @var{boundary} must be a
425 power of two!  It works by calling @code{malloc} to allocate a somewhat
426 larger block, and then returning an address within the block that is on
427 the desired boundary.
428 @end deftypefun
429
430 @comment malloc.h stdlib.h
431 @comment BSD
432 @deftypefun {void *} valloc (size_t @var{size})
433 Using @code{valloc} is like using @code{memalign} and passing the page size
434 as the value of the second argument.  Its advantage is that you don't need
435 to determine the page size explicitly (something which cannot be done
436 portably on Unix systems).
437 @end deftypefun
438
439
440 @node Heap Consistency Checking
441 @subsection Heap Consistency Checking
442
443 @cindex heap consistency checking
444 @cindex consistency checking, of heap
445
446 You can ask @code{malloc} to check the consistency of the heap by using
447 the @code{mcheck} function.  This function is a GNU extension, declared
448 in @file{<malloc.h>}.
449
450 @comment malloc.h
451 @comment GNU
452 @deftypefun void mcheck (void (*@var{abortfn}) (void))
453 Calling @code{mcheck} tells @code{malloc} to perform consistency checks
454 on the heap, which will catch things such as writing past the end of 
455 a @code{malloc}ed block.  
456
457 The @var{abortfn} argument is the function to call when an inconsistency
458 is found.  If you supply a null pointer, the @code{abort} function will
459 be used.
460 @end deftypefun
461
462 Since other library functions (such as the standard i/o functions) may
463 call @code{malloc}, you should do @code{mcheck} before anything else in
464 your program.  In the GNU system, linking with @samp{-lmcheck} will do
465 this automatically.
466
467 @node Storage Allocation Hooks
468 @subsection Storage Allocation Hooks
469
470 The GNU C Library lets you modify the behavior of @code{malloc},
471 @code{realloc}, and @code{free} by specifying appropriate hook
472 functions.  You can use these hooks to help you debug programs that use
473 dynamic storage allocation, for example.
474
475 The hook variables are declared in @file{<malloc.h>}.
476
477 @defvar __malloc_hook
478 The value of this variable is a pointer to function that @code{malloc}
479 uses whenever it is called.  You should define this function to look
480 like @code{malloc}; that is, like:
481
482 @example
483 void *@var{function} (size_t @var{size})
484 @end example
485 @end defvar
486
487 @defvar __realloc_hook
488 The value of this variable is a pointer to function that @code{realloc}
489 uses whenever it is called.  You should define this function to look
490 like @code{realloc}; that is, like:
491
492 @example
493 void *@var{function} (void *@var{ptr}, size_t @var{size})
494 @end example
495 @end defvar
496
497 @defvar __free_hook
498 The value of this variable is a pointer to function that @code{free}
499 uses whenever it is called.  You should define this function to look
500 like @code{free}; that is, like:
501
502 @example
503 void @var{function} (void *@var{ptr})
504 @end example
505 @end defvar
506
507 You must make sure that the function you install as a hook for one of
508 these functions does not call that function recursively without restoring
509 the old value of the hook first!  Otherwise, your program will get stuck
510 in an infinite loop.
511
512 Here is an example showing how to use @code{__malloc_hook} properly.  It
513 installs a function that prints out information every time @code{malloc}
514 is called.
515
516 @example
517 static void *(*old_malloc_hook) (size_t);
518 static void *
519 my_malloc_hook (size_t size)
520 @{
521   void *result;
522   __malloc_hook = old_malloc_hook;
523   result = malloc (size);
524   __malloc_hook = my_malloc_hook;
525   printf ("malloc (%u) returns %p\n", (unsigned int) size, result);
526   return result;
527 @}
528
529 main ()
530 @{
531   ...
532   old_malloc_hook = __malloc_hook;
533   __malloc_hook = my_malloc_hook;
534   ...
535 @}
536 @end example
537
538 The @code{mcheck} function (@pxref{Heap Consistency Checking}) works by
539 installing such hooks.
540
541
542
543 @node Storage Allocation Statistics
544 @subsection Storage Allocation Statistics
545
546 In the GNU C Library, you can get information about dynamic storage
547 allocation by calling the @code{mstats} function.  This function and
548 its associated data type are declared in @file{<malloc.h>}.
549
550 @comment malloc.h
551 @comment GNU
552 @deftp {Data Type} {struct mstats}
553 This structure type is used to return information about the dynamic
554 storage allocator.  It contains the following members:
555
556 @table @code
557 @item size_t bytes_total
558 This is the total size of the heap, in bytes.
559
560 @item size_t chunks_used
561 This is the number of chunks in use.  Remember that the
562 storage allocator internally gets chunks of memory from the operating
563 system, and them carves them up to satisfy individual @code{malloc}
564 requests.
565
566 @item size_t bytes_used
567 This is the number of bytes in use.
568
569 @item size_t chunks_free
570 This is the number of chunks which are free -- that is, that have been
571 allocated by the operating system to your program, but which are not
572 now being used.
573
574 @item size_t bytes_free
575 This is the number of bytes which are free.
576 @end table
577 @end deftp
578
579 @comment malloc.h
580 @comment GNU
581 @deftypefun struct mstats mstats (void)
582 This function returns information about the current dynamic memory usage
583 in a structure of type @code{struct mstats}.
584 @end deftypefun
585
586
587 @node Summary of @code{malloc} and Related Functions
588 @subsection Summary of @code{malloc} and Related Functions
589
590 Here is a summary of the functions that work with @code{malloc}:
591
592 @table @code
593 @item malloc (@var{size})
594 Allocate a block of @var{size} bytes.  @xref{Basic Storage Allocation}.
595
596 @item free (@var{addr})
597 Free a block previously allocated by @code{malloc}.  @xref{Freeing
598 Allocated Memory}.
599
600 @item realloc (@var{addr}, @var{size})
601 Make a block previously allocated by @code{malloc} larger or smaller,
602 possibly by copying it to a new location.  @xref{Changing the Size of a
603 Block}.
604
605 @item calloc (@var{count}, @var{eltsize})
606 Allocate a block of @var{count} * @var{eltsize} bytes using
607 @code{malloc}, and set its contents to zero.  @xref{Allocating Cleared
608 Space}.
609
610 @item valloc (@var{size})
611 Allocate a block @var{size} bytes, starting on a page boundary.
612 @xref{Allocation with Specified Alignment}.
613
614 @item memalign (@var{size}, @var{boundary})
615 Allocate a block @var{size} bytes, starting on an address that is a
616 multiple of @var{boundary}.  @xref{Allocation with Specified Alignment}.
617 @end table
618
619
620 @node Obstacks
621 @section Obstacks
622 @cindex obstacks
623
624 @strong{Incomplete:}  Obstacks are not now part of the GNU C Library.
625
626 @strong{Incomplete:} The functions in this section take @code{int}
627 arguments for sizes.  For consistency, these should all be made
628 @code{size_t} instead.
629
630 An @dfn{obstack} is a pool of memory containing a stack of objects.  You
631 can create any number of separate obstacks, and then allocate objects in
632 specified obstacks.  Within each obstack, the last object allocated must
633 always be the first one freed, but distinct obstacks are independent of
634 each other.
635
636 Aside from this one constraint of order of freeing, obstacks are totally
637 general: an obstack can contain any number of objects of any size.  They
638 are implemented with macros, so allocation is usually very fast as long as
639 the objects are usually small.  And the only space overhead per object is
640 the padding needed to start each object on a suitable boundary.
641
642 @menu
643 * Representation of Obstacks::          How to declare an obstack in your
644                                          program.
645 * Allocation in an Obstack::            Allocating objects in an obstack.
646 * Freeing Objects in an Obstack::       Freeing objects in an obstack.
647 * Preparing to Use Obstacks::           Preparations needed before you can
648                                          use obstacks.
649 * Obstack Functions and Macros::        The obstack functions are both
650                                          functions and macros.
651 * Growing Objects::                     Making an object bigger by stages.
652 * Extra Fast Growing Objects::          Extra-high-efficiency (though more
653                                          complicated) growing.
654 * Status of an Obstack::                Inquiries about the status of an
655                                          obstack.
656 * Alignment of Data in Obstacks::       Controlling alignment of objects
657                                          in obstacks.
658 * Obstack Chunks::                      How obstacks obtain and release chunks.
659                                          Efficiency considerations.
660 * Obstacks and Signal Handling::        Don't try to use obstack functions
661                                          in a signal handler.
662 * Summary of Obstack Functions::        Obstack Summary.
663 @end menu
664
665 @node Representation of Obstacks
666 @subsection Representation of Obstacks
667
668 The utilities for manipulating obstacks are declared in the header
669 file @file{<obstack.h>}.
670
671 @deftp {Data Type} {struct obstack}
672 An obstack is represented by a data structure of type @code{struct
673 obstack}.  This structure has a small fixed size; it records the status
674 of the obstack and how to find the space in which objects are allocated.
675 It does not contain any of the objects themselves.  You should not try
676 to access the contents of the structure directly; use only the functions
677 described in this chapter.
678 @end deftp
679
680 You can declare variables of type @code{struct obstack} and use them as
681 obstacks, or you can allocate obstacks dynamically like any other kind
682 of object.  Dynamic allocation of obstacks allows your program to have a
683 variable number of different stacks.  (You could even allocate an
684 obstack structure in another obstack, but this probably isn't useful.)
685
686 The objects in the obstack are packed into large blocks called
687 @dfn{chunks}.  The @code{struct obstack} structure points to a chain of
688 the chunks currently in use.
689
690 The obstack library obtains a new chunk whenever you allocate an object
691 that won't fit in the previous chunk.  Since the obstack library manages
692 chunks automatically, you don't need to pay much attention to them, but
693 you do need to supply a function which the obstack library should use to
694 get a chunk.  Usually you supply a function which uses @code{malloc}
695 directly or indirectly.
696
697 @deftypefun void obstack_init (struct obstack *@var{obstack})
698 Before you can use a @code{struct obstack} object as an obstack, you must
699 initialize it with the function @code{obstack_init}.
700 @end deftypefun
701
702 Here are two examples of how to allocate the space for an obstack and
703 initialize it.  First, an obstack that is a static variable:
704
705 @example
706 struct obstack myobstack;
707 @dots{}
708 obstack_init (&myobstack);
709 @end example
710
711 @noindent
712 Second, an obstack that is itself dynamically allocated:
713
714 @example
715 struct obstack *myobstack_ptr
716       = ((struct obstack *)
717          xmalloc (sizeof (struct obstack)));
718
719 obstack_init (myobstack_ptr);
720 @end example
721
722 Each source file that uses @code{obstack_init} must contain definitions of
723 @code{obstack_chunk_alloc} and @code{obstack_chunk_free}.
724 @xref{Preparing to Use Obstacks}.
725
726 @node Allocation in an Obstack
727 @subsection Allocation in an Obstack
728 @cindex allocation (obstacks)
729
730 The most direct way to allocate an object in an obstack is with
731 @code{obstack_alloc}, which is invoked almost like @code{malloc}.
732
733 @deftypefun {void *} obstack_alloc (struct obstack *@var{obstack_ptr}, int @var{size})
734 This allocates an uninitialized block of @var{size} bytes and returns its
735 address.  Here @var{obstack_ptr} specifies which obstack to allocate the
736 block in; it is the address of the @code{struct obstack} object which
737 represents the obstack.  Each obstack function or macro requires you to
738 specify an @var{obstack_ptr} as the first argument.
739 @end deftypefun
740
741 For example, here is a function that allocates a copy of a string @var{str}
742 in a specific obstack, which is the variable @code{string_obstack}:
743
744 @example
745 struct obstack string_obstack;
746
747 char *
748 copystring (char *string)
749 @{
750   char *s = (char *) obstack_alloc (&string_obstack,
751                                     strlen (string) + 1);
752   memcpy (s, string, strlen (string));
753   return s;
754 @}
755 @end example
756
757 To allocate a block with specified contents, use the function
758 @code{obstack_copy}, declared like this:
759
760 @deftypefun {void *} obstack_copy (struct obstack *@var{obstack_ptr}, void *@var{address}, int @var{size})
761 This initializes the newly allocated block with a copy of the @var{size}
762 bytes of data starting at @var{address}.
763 @end deftypefun
764
765 @deftypefun {void *} obstack_copy0 (struct obstack *@var{obstack_ptr}, void *@var{address}, int @var{size})
766 The function @code{obstack_copy0} is similar to @code{obstack_copy};
767 the difference is that @code{obstack_copy0} appends an extra byte
768 containing a null character.  This extra byte is not counted in the argument
769 @var{size}.
770 @end deftypefun
771
772 The @code{obstack_copy0} function is convenient for copying a sequence
773 of characters into an obstack as a null-terminated string.  Here is an
774 example of its use:
775
776 @example
777 char *
778 obstack_savestring (char *addr, int size)
779 @{
780   return obstack_copy0 (&myobstack, addr, size);
781 @}
782 @end example
783
784 @noindent
785 Contrast this with the previous example of @code{savestring} using
786 @code{malloc} (@pxref{Basic Storage Allocation}).
787
788 @node Freeing Objects in an Obstack
789 @subsection Freeing Objects in an Obstack
790 @cindex freeing (obstacks)
791
792 To free an object allocated in an obstack, use the function
793 @code{obstack_free}.
794
795 @deftypefun void obstack_free (struct obstack *@var{obstack_ptr}, void *@var{object})
796 If @var{object} is a null pointer, everything allocated in the obstack
797 is freed.  Otherwise, @var{object} must be the address of an object
798 allocated in the obstack.  Then @var{object} is freed, and so is every
799 object that was allocated in the same obstack more recently than
800 @var{object}.
801 @end deftypefun
802
803 Note that if @var{object} is a null pointer, the result is an
804 uninitialize obstack.  To free all storage in an obstack but leave it
805 valid for further allocation, call @code{obstack_free} with the address
806 of the first object allocated on the obstack:
807
808 @example
809 obstack_free (obstack_ptr, first_object_allocated_ptr);
810 @end example
811
812 Recall that the objects in an obstack are grouped into chunks.  When all
813 the objects in a chunk become free, the obstack library automatically
814 frees the chunk (@pxref{Preparing to Use Obstacks}).  Then other
815 obstacks, or non-obstack allocation, can reuse the space of the chunk.
816
817 @node Preparing to Use Obstacks
818 @subsection Preparing to Use Obstacks
819 @cindex header file
820 @cindex linking
821
822 @strong{Incomplete:}  This section needs to be rewritten when it is
823 decided whether obstacks will be part of the C library.
824
825 Each source file in which you plan to use the obstack functions
826 must include the header file @file{obstack.h}, like this:
827
828 @example
829 #include "obstack.h"
830 @end example
831
832 @findex obstack_chunk_alloc
833 @findex obstack_chunk_free
834 Also, if the source file uses the macro @code{obstack_init}, it must
835 declare or define two functions or macros that will be called by the
836 obstack library.  One, @code{obstack_chunk_alloc}, is used to allocate the
837 chunks (large blocks) of memory into which objects are packed.  The other,
838 @code{obstack_chunk_free}, is used to return chunks when the objects in
839 them are freed.
840
841 Usually these are defined to use @code{malloc} via the intermediary
842 @code{xmalloc} (@pxref{Unconstrained Allocation}).  This is done with
843 the following pair of macro definitions:
844
845 @example
846 #define obstack_chunk_alloc xmalloc
847 #define obstack_chunk_free free
848 @end example
849
850 @noindent
851 Though the storage you get using obstacks really comes from @code{malloc},
852 using obstacks is faster because @code{malloc} is called less often, for
853 larger blocks of memory.  @xref{Obstack Chunks}, for full details.
854
855 Finally, when you link your program you must include among the object files
856 the file of obstack support functions, @samp{obstack.o}.  In the actual GNU
857 system, this will no longer be necessary, because these subroutines will be
858 in the C library.
859
860
861 @node Obstack Functions and Macros
862 @subsection Obstack Functions and Macros
863 @cindex macros
864
865 The interfaces for using obstacks may be defined either as functions or as
866 macros, depending on the compiler.
867
868
869
870 If you are using an old-fashioned non-ANSI C compiler, they are actually
871 defined only as macros.  You can call these macros like functions, but
872 you cannot use them in any other way (for example, you cannot take their
873 address).
874
875 Calling the macros requires a special precaution: namely, the first operand
876 (the obstack pointer) may not contain any side effects, because it may be
877 computed more than once.  For example, if you write this:
878
879 @example
880 obstack_alloc (get_obstack (), 4);
881 @end example
882
883 @noindent
884 you will find that @code{get_obstack} may be called several times.
885 If you use @code{*obstack_list_ptr++} as the obstack pointer argument,
886 you will get very strange results since the incrementation may occur
887 several times.
888
889 In ANSI C, each function has both a macro definition and a function
890 definition.  The function definition is used if you take the address of the
891 function without calling it.  An ordinary call uses the macro definition by
892 default, but you can request the function definition instead by writing the
893 function name in parentheses, as shown here:
894
895 @example
896 char *x;
897 void *(*funcp) ();
898 /* @r{Use the macro} */
899 x = (char *) obstack_alloc (obptr, size);
900 /* @r{Call the function} */
901 x = (char *) (obstack_alloc) (obptr, size);
902 /* @r{Take the address of the function} */
903 funcp = obstack_alloc;
904 @end example
905
906 @noindent
907 This is the same situation that exists in ANSI C for the standard library
908 functions.  @xref{Macro Definitions}.
909
910 If you are not using the GNU C compiler, you must observe the precaution
911 of avoiding side effects in the first operand.  But if you use the GNU C
912 compiler, no precautions are necessary, because various language
913 extensions in GNU C allow the macros to be defined in a way that avoids
914 unwanted recalculation.
915
916 @node Growing Objects
917 @subsection Growing Objects
918 @cindex growing objects (in obstacks)
919 @cindex changing size (in obstacks)
920
921 Because storage in obstack chunks is used sequentially, it is possible to
922 build up an object step by step, adding one or more bytes at a time to the
923 end of the object.  With this technique, you do not need to know how much
924 data you will put in the object until you come to the end of it.  We call
925 this the technique of @dfn{growing objects}.  The special functions
926 for adding data to the growing object are described in this section.
927
928 You don't need to do anything special when you start to grow an object.
929 Using one of the functions to add data to the object automatically
930 starts it.  However, it is necessary to say explicitly when the object is
931 finished.  This is done with the function @code{obstack_finish}.
932
933 The actual address of the object thus built up is not known until the
934 object is finished.  Until then, it always remains possible that you will
935 add so much data that the object must be copied into a new chunk.
936
937 While the obstack is in use for a growing object, you cannot use it for
938 ordinary allocation of another object.  If you try to do so, the space
939 already added to the growing object will become part of the other object.
940
941 @deftypefun void obstack_blank (struct obstack *@var{obstack_ptr}, int @var{size})
942 The most basic function for adding to a growing object is
943 @code{obstack_blank}, which adds space without initializing it.
944 @end deftypefun
945
946 @deftypefun void obstack_grow (struct obstack *@var{obstack_ptr}, void *@var{data}, int @var{size})
947 To add a block of initialized space, use @code{obstack_grow}, which is
948 the growing-object analogue of @code{obstack_copy}.
949
950 Here @var{size} is the number of bytes to add, and @var{data} points
951 to the data to initialize them with.
952 @end deftypefun
953
954 @deftypefun void obstack_grow (struct obstack *@var{obstack_ptr}, void *@var{data}, int @var{size})
955 This is the growing-object analogue of @code{obstack_copy0}.  It adds an
956 additional null character after the @var{size} specified bytes.
957 @end deftypefun
958
959 @deftypefun void obstack_1grow (struct obstack *@var{obstack_ptr},
960                     char @var{data_char})
961 To add one character at a time, use the function
962 @code{obstack_1grow}.  
963 A single byte containing @var{data_char} is added to the growing object.
964 @end deftypefun
965
966 @deftypefun {void *} obstack_finish (struct obstack *@var{obstack_ptr})
967 When you are finished growing the object, use the function
968 @code{obstack_finish} to close it off and obtain its final address.
969
970 Once you have finished the object, the obstack is available for ordinary
971 allocation or for growing another object.
972 @end deftypefun
973
974 When you build an object by growing it, you will probably need to know
975 afterward how long it became.  You need not keep track of this as you grow
976 the object, because you can find out the length from the obstack just
977 before finishing the object with the function @code{obstack_object_size},
978 declared as follows:
979
980 @deftypefun int obstack_object_size (struct obstack *@var{obstack_ptr})
981 This function returns the current size of the growing object, in bytes.
982 Remember to call this function @emph{before} finishing the object.  Once
983 you finish the object, @code{obstack_object_size} will return zero.
984 @end deftypefun
985
986 If you have started growing an object and wish to cancel it, you should
987 finish it and then free it, like this:
988
989 @example
990 obstack_free (obstack_ptr, obstack_finish (obstack_ptr));
991 @end example
992
993 @noindent
994 This has no effect if no object was growing.
995
996 @node Extra Fast Growing Objects
997 @subsection Extra Fast Growing Objects
998 @cindex efficiency and obstacks
999
1000 The usual functions for growing objects incur overhead for checking
1001 whether there is room for the new growth in the current chunk.  If you are
1002 frequently construct objects in small steps of growth, this overhead can be
1003 significant.
1004
1005 You can reduce the overhead by using special ``fast growth''
1006 functions that grow the object without checking.  In order to have a
1007 robust program, you must do the checking yourself.  If you do this checking
1008 in the simplest way each time you are about to add data to the object, you
1009 have not saved anything, because that is what the ordinary growth
1010 functions do.  But if you can arrange to check less often, or check
1011 more efficiently, then you make the program faster.
1012
1013 The function @code{obstack_room} returns the amount of room available
1014 in the current chunk.  It is declared as follows:
1015
1016 @deftypefun int obstack_room (struct obstack *@var{obstack_ptr})
1017 This returns the number of bytes that can be added safely to the current
1018 growing object (or to an object about to be started) in obstack
1019 @var{obstack} using the fast growth functions.
1020 @end deftypefun
1021
1022 While you know there is room, you can use these fast growth functions
1023 for adding data to a growing object:
1024
1025 @deftypefun void obstack_1grow_fast (struct obstack *@var{obstack_ptr}, char @var{data_char})
1026 The function @code{obstack_1grow_fast} adds one byte containing the
1027 character @var{data_char} to the growing object @var{obstack_ptr}.
1028 @end deftypefun
1029
1030 @deftypefun void obstack_blank_fast (struct obstack *@var{obstack_ptr}, int @var{size})
1031 The function @code{obstack_blank_fast} adds @code{size} bytes to the
1032 growing object @var{obstack_ptr} without initializing them.
1033 @end deftypefun
1034
1035 When you check for space using @code{obstack_room} and there is not
1036 enough room for what you want to add, the fast growth functions
1037 are not safe.  In this case, simply use the corresponding ordinary
1038 growth function instead.  Very soon this will copy the object to a
1039 new chunk; then there will be lots of room available again. 
1040
1041 So, each time you use an ordinary growth function, check again for
1042 sufficient space using @code{obstack_room}.  Once the object is copied
1043 to a new chunk, there will be enough space again, so you will start
1044 using the fast growth functions again.
1045
1046 Here is an example:
1047
1048 @example
1049 void
1050 add_string (struct obstack *obstack, char *ptr, int len)
1051 @{
1052   while (len > 0)
1053     @{
1054       if (obstack_room (obstack) > len)
1055         @{
1056           /* We have enough room: add everything fast.  */
1057           while (len-- > 0)
1058             obstack_1grow_fast (obstack, *ptr++);
1059         @}
1060       else
1061         @{
1062           /* Not enough room. Add one character slowly,
1063              which may copy to a new chunk and make room.  */
1064           obstack_1grow (obstack, *ptr++);
1065           len--;
1066         @}
1067     @}
1068 @}
1069 @end example
1070
1071 @node Status of an Obstack
1072 @subsection Status of an Obstack
1073 @cindex obstack status
1074 @cindex status of obstack
1075
1076 Here are functions that provide information on the current status of
1077 allocation in an obstack.  You can use them to learn about an object while
1078 still growing it.
1079
1080 @deftypefun {void *} obstack_base (struct obstack *@var{obstack})
1081 This function teturns the tentative address of the beginning of the currently
1082 growing object in @var{obstack}.  If you finish the object
1083 immediately, it will have that address.  If you make it larger first,
1084 it may outgrow the current chunk---then its address will change!
1085
1086 If no object is growing, this value says where the next object you
1087 allocate will start (once again assuming it fits in the current
1088 chunk).
1089 @end deftypefun
1090
1091 @deftypefun {void *} obstack_next_free (struct obstack *@var{obstack})
1092 This function returns the address of the first free byte in the current
1093 chunk of @var{obstack}.  This is the end of the currently growing
1094 object.  If no object is growing, @code{obstack_next_free} returns the
1095 same value as @code{obstack_base}.
1096 @end deftypefun
1097
1098 @deftypefun int obstack_object_size (struct obstack *@var{obstack})
1099 This function returns the size in bytes of the currently growing object.
1100 This is equivalent to
1101
1102 @example
1103 obstack_next_free (@var{obstack}) - obstack_base (@var{obstack})
1104 @end example
1105 @end deftypefun
1106
1107 @node Alignment of Data in Obstacks
1108 @subsection Alignment of Data in Obstacks
1109 @cindex alignment (in obstacks)
1110
1111 Each obstack has an @dfn{alignment boundary}; each object allocated in
1112 the obstack automatically starts on an address that is a multiple of the
1113 specified boundary.  By default, this boundary is 4 bytes.
1114
1115 To access an obstack's alignment boundary, use the macro
1116 @code{obstack_alignment_mask}, whose function prototype looks like
1117 this:
1118
1119 @deftypefun int obstack_alignment_mask (struct obstack *@var{obstack_ptr})
1120 The value is a bit mask; a bit that is 1 indicates that the corresponding
1121 bit in the address of an object should be 0.  The mask value should be one
1122 less than a power of 2; the effect is that all object addresses are
1123 multiples of that power of 2.  The default value of the mask is 3, so that
1124 addresses are multiples of 4.  A mask value of 0 means an object can start
1125 on any multiple of 1 (that is, no alignment is required).
1126
1127 The expansion of the macro @code{obstack_alignment_mask} is an lvalue,
1128 so you can alter the mask by assignment.  For example, this statement:
1129
1130 @example
1131 obstack_alignment_mask (obstack_ptr) = 0;
1132 @end example
1133
1134 @noindent
1135 has the effect of turning off alignment processing in the specified obstack.
1136 @end deftypefun
1137
1138 Note that a change in alignment mask does not take effect until
1139 @emph{after} the next time an object is allocated or finished in the
1140 obstack.  If you are not growing an object, you can make the new
1141 alignment mask take effect immediately by calling @code{obstack_finish}.
1142 This will finish a zero-length object and then do proper alignment for
1143 the next object.
1144
1145 @node Obstack Chunks
1146 @subsection Obstack Chunks
1147 @cindex efficiency of chunks
1148 @cindex chunks
1149
1150 Obstacks work by allocating space for themselves in large chunks, and then
1151 parcelling out space in the chunks to satisfy your requests.  Chunks are
1152 normally 4092 bytes long unless you specify a different chunk size.  The
1153 chunk size includes 8 bytes of overhead that are not actually used for
1154 storing objects.  Regardless of the specified size, longer chunks will be
1155 allocated when necessary for long objects.
1156
1157 The obstack library allocates chunks by calling the function
1158 @code{obstack_chunk_alloc}, which you must define.  When a chunk is no
1159 longer needed because you have freed all the objects in it, the obstack
1160 library frees the chunk by calling @code{obstack_chunk_free}, which you
1161 must also define.
1162
1163 These two must be defined (as macros) or declared (as functions) in each
1164 source file that uses @code{obstack_init} (@pxref{Representation of Obstacks}).
1165 Most often they are defined as macros like this:
1166
1167 @example
1168 #define obstack_chunk_alloc xmalloc
1169 #define obstack_chunk_free free
1170 @end example
1171
1172 Note that these are simple macros (no arguments).  Macro definitions with
1173 arguments will not work!  It is necessary that @code{obstack_chunk_alloc}
1174 or @code{obstack_chunk_free}, alone, expand into a function name if it is
1175 not itself a function name.
1176
1177 The function that actually implements @code{obstack_chunk_alloc} cannot
1178 return ``failure'' in any fashion, because the obstack library is not
1179 prepared to handle failure.  Therefore, @code{malloc} itself is not
1180 suitable.  If the function cannot obtain space, it should either terminate
1181 the process or do a nonlocal exit using @code{longjmp}.
1182
1183 Because chunks are usually obtained with @code{malloc}, the chunk size
1184 should be 4 less than a power of 2.  The default chunk size, 4092, was
1185 chosen because it fits this constraint, and it is long enough to satisfy
1186 many typical requests on the obstack yet short enough not to waste too much
1187 memory the portion of the last chunk not yet used.
1188
1189 @deftypefun int obstack_chunk_size (struct obstack *@var{obstack_ptr})
1190 This returns the chunk size of the given obstack.
1191 @end deftypefun
1192
1193 Since this macro expands to an lvalue, you can specify a new chunk size by
1194 assigning it a new value.  Doing so does not affect the chunks already
1195 allocated, but will change the size of chunk allocated for that particular
1196 obstack in the future.  It is unlikely to be useful to make the chunk size
1197 smaller, but making it larger might improve efficiency if you are
1198 allocating many objects whose size is comparable to the chunk size.  Here
1199 is how to do so cleanly:
1200
1201 @example
1202 if (obstack_chunk_size (obstack_ptr) < @var{new_chunk_size})
1203   obstack_chunk_size (obstack_ptr) = @var{new_chunk_size};
1204 @end example
1205
1206 @node Obstacks and Signal Handling
1207 @subsection Obstacks and Signal Handling
1208 @cindex signals and obstacks
1209
1210 Is it safe to use @code{obstack_alloc} in a signal handler?  Yes, provided
1211 you are careful in the following ways:
1212
1213 @itemize @bullet
1214 @item
1215 Use an obstack that you are certain the interrupted program is not
1216 trying to allocate or free in at the time the signal happens.  (For
1217 example, you may have a special obstack for use in signal handlers.)
1218
1219 @item
1220 Make sure that the @code{obstack_chunk_alloc} function is safe for
1221 use in signal handlers.  This may mean keeping an extra emergency
1222 chunk to allocate when a new chunk is needed within a signal handler,
1223 just to avoid calling @code{malloc} from the signal handler.
1224 @end itemize
1225
1226 The same consideration applies to any of the functions that allocate
1227 or grow objects.
1228
1229 Likewise, you can use @code{obstack_free} in a signal handler provided
1230 you are sure that the interrupted program was not trying to allocate or
1231 free in the same obstack, and provided you can dispose of freed chunks
1232 without calling @code{free} immediately.  You may be able to save the
1233 chunks in a chain and free them later when signal handling is over.
1234
1235 In a multi-threaded program, you must make certain that it never happens
1236 that two threads simultaneously operate on the same obstack.  In addition,
1237 since @code{malloc} and @code{free} are not reentrant, you must design
1238 the @code{obstack_chunk_alloc} and @code{obstack_chunk_free} functions
1239 to interlock so that only one of them can actually call @code{malloc} or
1240 @code{free} at a given time.
1241
1242 @node Summary of Obstack Functions
1243 @subsection Summary of Obstack Functions
1244
1245 Here is a summary of all the functions associated with obstacks.
1246 Each takes the address of an obstack (@code{struct obstack *}) as its first
1247 argument.
1248
1249 @table @code
1250 @item obstack_init (@var{obstack_ptr})
1251 Initialize use of an obstack.  @xref{Representation of Obstacks}.
1252
1253 @item obstack_alloc (@var{obstack_ptr}, @var{size})
1254 Allocate an object of @var{size} uninitialized bytes.
1255 @xref{Allocation in an Obstack}.
1256
1257 @item obstack_copy (@var{obstack_ptr}, @var{address}, @var{size})
1258 Allocate an object of @var{size} bytes, with contents copied from
1259 @var{address}.  @xref{Allocation in an Obstack}.
1260
1261 @item obstack_copy0 (@var{obstack_ptr}, @var{address}, @var{size})
1262 Allocate an object of @var{size}+1 bytes, with @var{size} of them
1263 copied from @var{address}, and a null character at the end.  @xref{Allocation
1264 in an Obstack}.
1265
1266 @item obstack_free (@var{obstack_ptr}, @var{object})
1267 Free @var{object} (and everything allocated more recently than
1268 @var{object}).  @xref{Freeing Objects in an Obstack}.
1269
1270 @item obstack_blank (@var{obstack_ptr}, @var{size})
1271 Add @var{size} uninitialized bytes to a growing object.
1272 @xref{Growing Objects}.
1273
1274 @item obstack_grow (@var{obstack_ptr}, @var{address}, @var{size})
1275 Add @var{size} bytes, copied from @var{address}, to a growing object.
1276 @xref{Growing Objects}.
1277
1278 @item obstack_grow0 (@var{obstack_ptr}, @var{address}, @var{size})
1279 Add @var{size} bytes, copied from @var{address}, to a growing object,
1280 and then add another byte containing a null character.  @xref{Growing
1281 Objects}.
1282
1283 @item obstack_1grow (@var{obstack_ptr}, @var{data_char})
1284 Add one byte containing @var{data_char} to a growing object.
1285 @xref{Growing Objects}.
1286
1287 @item obstack_finish (@var{obstack_ptr})
1288 Finalize the object that is growing and return its permanent address.
1289 @xref{Growing Objects}.
1290
1291 @item obstack_object_size (@var{obstack_ptr})
1292 Get the size of the currently growing object.  @xref{Growing Objects}.
1293
1294 @item obstack_blank_fast (@var{obstack_ptr}, @var{size})
1295 Add @var{size} uninitialized bytes to a growing object without checking
1296 that there is enough room.  @xref{Extra Fast Growing Objects}.
1297
1298 @item obstack_1grow_fast (@var{obstack_ptr}, @var{data_char})
1299 Add one byte containing @var{data_char} to a growing object without
1300 checking that there is enough room.  @xref{Extra Fast Growing Objects}.
1301
1302 @item obstack_room (@var{obstack_ptr})
1303 Get the amount of room now available for growing the current object.
1304 @xref{Extra Fast Growing Objects}.
1305
1306 @item obstack_alignment_mask (@var{obstack_ptr})
1307 The mask used for aligning the beginning of an object.  This is an
1308 lvalue.  @xref{Alignment of Data in Obstacks}.
1309
1310 @item obstack_chunk_size (@var{obstack_ptr})
1311 The size for allocating chunks.  This is an lvalue.  @xref{Obstack Chunks}.
1312
1313 @item obstack_base (@var{obstack_ptr})
1314 Tentative starting address of the currently growing object.
1315 @xref{Status of an Obstack}.
1316
1317 @item obstack_next_free (@var{obstack_ptr})
1318 Address just after the end of the currently growing object.
1319 @xref{Status of an Obstack}.
1320 @end table
1321
1322 @node Automatic Storage with Variable Size
1323 @section Automatic Storage with Variable Size
1324 @cindex automatic freeing
1325
1326 The function @code{alloca} supports a kind of half-dynamic allocation in
1327 which blocks are allocated dynamically but freed automatically.
1328
1329 Allocating a block with @code{alloca} is an explicit action; you can
1330 allocate as many blocks as you wish, and compute the size at run time.  But
1331 all the blocks are freed when you exit the function that @code{alloca} was
1332 called from, just as if they were automatic variables declared in that
1333 function.  There is no way to free the space explicitly.
1334
1335 The prototype for @code{alloca} is in @file{<stdlib.h>}.  This function
1336 is a GNU extension.
1337
1338 @comment stdlib.h
1339 @comment GNU, BSD
1340 @deftypefun {void *} alloca (size_t @var{size});
1341 The return value of @code{alloca} is the address of a block of @var{size}
1342 bytes of storage, allocated in the stack frame of the calling function.
1343 @end deftypefun
1344
1345 @menu
1346 * Alloca Example::                      Example of using @code{alloca}.
1347 * Advantages of @code{alloca}::         Reasons to use @code{alloca}.
1348 * Disadvantages of @code{alloca}::      Reasons to avoid @code{alloca}.
1349 * GNU C Variable-Size Arrays::          Only in GNU C, here is an alternative
1350                                          method of allocating dynamically and
1351                                          freeing automatically.
1352 @end menu
1353
1354 @node Alloca Example
1355 @subsection Alloca Example
1356
1357 As an example of use of @code{alloca}, here is a function that opens a file
1358 name made from concatenating two argument strings, and returns a file
1359 descriptor or minus one signifying failure:
1360
1361 @example
1362 int open2 (char *str1, char *str2, int flags, int mode)
1363 @{
1364   char *name = (char *) alloca (strlen (str1) + strlen (str2) + 1);
1365   strcpy (name, str1);
1366   strcat (name, str2);
1367   return open (name, flags, mode);
1368 @}
1369 @end example
1370
1371 @noindent
1372 Here is how you would get the same results with @code{malloc} and
1373 @code{free}:
1374
1375 @example
1376 int open2 (char *str1, char *str2, int flags, int mode)
1377 @{
1378   char *name = (char *) malloc (strlen (str1) + strlen (str2) + 1);
1379   int desc;
1380   if (name == 0)
1381     fatal ("virtual memory exceeded");
1382   strcpy (name, str1);
1383   strcat (name, str2);
1384   desc = open (name, flags, mode);
1385   free (name);
1386   return desc;
1387 @}
1388 @end example
1389
1390 As you can see, it is simpler with @code{alloca}.  But @code{alloca} has
1391 other, more important advantages, and some disadvantages.
1392
1393 @node Advantages of @code{alloca}
1394 @subsection Advantages of @code{alloca}
1395
1396 Here are the reasons why @code{alloca} may be preferable to @code{malloc}:
1397
1398 @itemize @bullet
1399 @item
1400 Using @code{alloca} wastes very little space or time.
1401
1402 @item
1403 Since @code{alloca} does not have separate pools for different sizes
1404 of block, space used for any size block can be reused for any other
1405 size.
1406
1407 @item
1408 @cindex longjmp
1409 Nonlocal exits done with @code{longjmp} (@pxref{Non-Local Jumps})
1410 automatically free the space allocated with @code{alloca} when they exit
1411 through the function that called @code{alloca}.  This is the most
1412 important reason to use @code{alloca}.
1413
1414 To illustrate this, suppose you have a function
1415 @code{open_or_report_error} which returns a descriptor, like
1416 @code{open}, if it succeeds, but does not return to its caller if it
1417 fails.  If the file cannot be opened, it prints an error message and
1418 jumps out to the command level of your program using @code{longjmp}.
1419 Let's change @code{open2} (@pxref{Alloca Example}) to use this
1420 subroutine:@refill
1421
1422 @example
1423 int open2 (char *str1, char *str2, int flags, int mode)
1424 @{
1425   char *name = (char *) alloca (strlen (str1) + strlen (str2) + 1);
1426   strcpy (name, str1);
1427   strcat (name, str2);
1428   return open_or_report_error (name, flags, mode);
1429 @}
1430 @end example
1431
1432 @noindent
1433 Because of the way @code{alloca} works, the storage it allocates is
1434 freed even when an error occurs, with no special effort required.
1435
1436 By contrast, the previous definition of @code{open2} (which uses
1437 @code{malloc} and @code{free}) would develop a storage leak if it were
1438 changed in this way.  Even if you are willing to make more changes to
1439 fix it, there is no easy way to do so.
1440 @end itemize
1441
1442 @node Disadvantages of @code{alloca}
1443 @subsection Disadvantages of @code{alloca}
1444 @cindex @code{alloca} disadvantages
1445 @cindex disadvantages of @code{alloca}
1446
1447 These are the disadvantages of @code{alloca} in comparison with
1448 @code{malloc}:
1449
1450 @itemize @bullet
1451 @item
1452 If you try to allocate more storage than the machine can provide, you
1453 don't get a clean error message.  Instead you get a fatal signal like
1454 the one you would get from an infinite recursion; probably a
1455 segmentation violation.
1456
1457 @item
1458 Some non-GNU systems fail to support @code{alloca}, so it is less
1459 portable.  However, a slower emulation of @code{alloca} written in C
1460 is available for use on systems with this deficiency.
1461 @end itemize
1462
1463 @node GNU C Variable-Size Arrays
1464 @subsection GNU C Variable-Size Arrays
1465 @cindex variable-sized arrays
1466
1467 In GNU C, you can replace most uses of @code{alloca} with an array of
1468 variable size.  Here is how @code{open2} would look then:
1469
1470 @example
1471 int open2 (char *str1, char *str2, int flags, int mode)
1472 @{
1473   char name[strlen (str1) + strlen (str2) + 1];
1474   strcpy (name, str1);
1475   strcat (name, str2);
1476   return open (name, flags, mode);
1477 @}
1478 @end example
1479
1480 But @code{alloca} is not always equivalent to a variable-sized array, for
1481 several reasons:
1482
1483 @itemize @bullet
1484 @item
1485 A variable size array's space is freed at the end of the scope of the
1486 name of the array.  The space allocated with @code{alloca} usually
1487 remains until the end of the function.
1488
1489 @item
1490 It is possible to use @code{alloca} within a loop, allocating an
1491 additional block on each iteration.  This is impossible with
1492 variable-sized arrays.  On the other hand, this is also slightly
1493 unclean.
1494 @end itemize
1495
1496 If you mix use of @code{alloca} and variable-sized arrays within one
1497 function, exiting a scope in which a variable-sized array was declared
1498 frees all blocks allocated with @code{alloca} during the execution of that
1499 scope.
1500
1501
1502 @node Relocating Allocator
1503 @section Relocating Allocator
1504
1505 @strong{Incomplete:}  Information about the relocating storage allocator
1506 used by Emacs 19 goes here.