Obstacks
--------

An obstack is a pool of memory containing a stack of objects.  You can create any number of separate obstacks, and then allocate objects in specified obstacks.  Within each obstack, the last object allocated must always be the first one freed, but distinct obstacks are independent of each other.

Aside from this one constraint of order of freeing, obstacks are totally general: an obstack can contain any number of objects of any size.  They are implemented with macros, so allocation is usually very fast as long as the objects are usually small.  And the only space overhead per object is the padding needed to start each object on a suitable boundary.

Creating Obstacks
.................

The utilities for manipulating obstacks are declared in the header file obstack.h.

 -- Data Type: struct obstack
     An obstack is represented by a data structure of type struct obstack.  This structure has a small fixed size; it records the status of the obstack and how to find the space in which objects are allocated. It does not contain any of the objects themselves.  You should not try to access the contents of the structure directly; use only the functions described in this chapter.

You can declare variables of type struct obstack and use them as obstacks, or you can allocate obstacks dynamically like any other kind of object.  Dynamic allocation of obstacks allows your program to have a variable number of different stacks.  (You can even allocate an obstack structure in another obstack, but this is rarely useful.)

All the functions that work with obstacks require you to specify which obstack to use.  You do this with a pointer of type struct obstack *.  In the following, we often say ``an obstack'' when strictly speaking the object at hand is such a pointer.

The objects in the obstack are packed into large blocks called chunks.  The struct obstack structure points to a chain of the chunks currently in use.

The obstack library obtains a new chunk whenever you allocate an object that won't fit in the previous chunk.  Since the obstack library manages chunks automatically, you don't need to pay much attention to them, but you do need to supply a function which the obstack library should use to get a chunk.  Usually you supply a function which uses malloc directly or indirectly.  You must also supply a function to free a chunk. These matters are described in the following section.

Preparing for Using Obstacks
............................

Each source file in which you plan to use the obstack functions must include the header file obstack.h, like this:

     #include <obstack.h>

Also, if the source file uses the macro obstack_init, it must declare or define two functions or macros that will be called by the obstack library.  One, obstack_chunk_alloc, is used to allocate the chunks of memory into which objects are packed.  The other, obstack_chunk_free, is used to return chunks when the objects in them are freed.  These macros should appear before any use of obstacks in the source file.

Usually these are defined to use malloc via the intermediary xmalloc (see Unconstrained Allocation (The GNU C Library Reference Manual)).  This is done with the following pair of macro definitions:

     #define obstack_chunk_alloc xmalloc
     #define obstack_chunk_free free

Though the memory you get using obstacks really comes from malloc, using obstacks is faster because malloc is called less often, for larger blocks of memory.  See Obstack Chunks, for full details.

At run time, before the program can use a struct obstack object as an obstack, it must initialize the obstack by calling obstack_init.

 -- Function: int obstack_init (struct obstack *OBSTACK-PTR)
     Initialize obstack OBSTACK-PTR for allocation of objects.  This function calls the obstack's obstack_chunk_alloc function.  If allocation of memory fails, the function pointed to by obstack_alloc_failed_handler is called.  The obstack_init function always returns 1 (Compatibility notice: Former versions of obstack returned 0 if allocation failed).

Here are two examples of how to allocate the space for an obstack and initialize it.  First, an obstack that is a static variable:

     static struct obstack myobstack;
     ...
     obstack_init (&myobstack);

Second, an obstack that is itself dynamically allocated:

     struct obstack *myobstack_ptr
       = (struct obstack *) xmalloc (sizeof (struct obstack));

     obstack_init (myobstack_ptr);

 -- Variable: obstack_alloc_failed_handler
     The value of this variable is a pointer to a function that obstack uses when obstack_chunk_alloc fails to allocate memory.  The default action is to print a message and abort. You should supply a function that either calls exit (see Program Termination (The GNU C Library Reference Manual)) or longjmp (see Non-Local Exits (The GNU C Library Reference Manual)) and doesn't return.

          void my_obstack_alloc_failed (void)
          ...
          obstack_alloc_failed_handler = &my_obstack_alloc_failed;

Allocation in an Obstack
........................

The most direct way to allocate an object in an obstack is with obstack_alloc, which is invoked almost like malloc.

 -- Function: void * obstack_alloc (struct obstack *OBSTACK-PTR, int SIZE)
     This allocates an uninitialized block of SIZE bytes in an obstack and returns its address.  Here OBSTACK-PTR specifies which obstack to allocate the block in; it is the address of the struct obstack object which represents the obstack.  Each obstack function or macro requires you to specify an OBSTACK-PTR as the first argument.

     This function calls the obstack's obstack_chunk_alloc function if it needs to allocate a new chunk of memory; it calls obstack_alloc_failed_handler if allocation of memory by obstack_chunk_alloc failed.

For example, here is a function that allocates a copy of a string STR in a specific obstack, which is in the variable string_obstack:

     struct obstack string_obstack;

     char *
     copystring (char *string)
     {
       size_t len = strlen (string) + 1;
       char *s = (char *) obstack_alloc (&string_obstack, len);
       memcpy (s, string, len);
       return s;
     }

To allocate a block with specified contents, use the function obstack_copy, declared like this:

 -- Function: void * obstack_copy (struct obstack *OBSTACK-PTR, void *ADDRESS, int SIZE)
     This allocates a block and initializes it by copying SIZE bytes of data starting at ADDRESS.  It calls obstack_alloc_failed_handler if allocation of memory by obstack_chunk_alloc failed.

 -- Function: void * obstack_copy0 (struct obstack *OBSTACK-PTR, void *ADDRESS, int SIZE)
     Like obstack_copy, but appends an extra byte containing a null character.  This extra byte is not counted in the argument SIZE.

The obstack_copy0 function is convenient for copying a sequence of characters into an obstack as a null-terminated string.  Here is an example of its use:

     char *
     obstack_savestring (char *addr, int size)
     {
       return obstack_copy0 (&myobstack, addr, size);
     }

Contrast this with the previous example of savestring using malloc (see Basic Allocation (The GNU C Library Reference Manual)).

Freeing Objects in an Obstack
.............................

To free an object allocated in an obstack, use the function obstack_free.  Since the obstack is a stack of objects, freeing one object automatically frees all other objects allocated more recently in the same obstack.

 -- Function: void obstack_free (struct obstack *OBSTACK-PTR, void *OBJECT)
     If OBJECT is a null pointer, everything allocated in the obstack is freed.  Otherwise, OBJECT must be the address of an object allocated in the obstack.  Then OBJECT is freed, along with everything allocated in OBSTACK since OBJECT.

Note that if OBJECT is a null pointer, the result is an uninitialized obstack.  To free all memory in an obstack but leave it valid for further allocation, call obstack_free with the address of the first object allocated on the obstack:

     obstack_free (obstack_ptr, first_object_allocated_ptr);

Recall that the objects in an obstack are grouped into chunks.  When all the objects in a chunk become free, the obstack library automatically frees the chunk (see Preparing for Obstacks).  Then other obstacks, or non-obstack allocation, can reuse the space of the chunk.

Obstack Functions and Macros
............................

The interfaces for using obstacks may be defined either as functions or as macros, depending on the compiler.  The obstack facility works with all C compilers, including both ISO C and traditional C, but there are precautions you must take if you plan to use compilers other than GNU C.

If you are using an old-fashioned non-ISO C compiler, all the obstack ``functions'' are actually defined only as macros.  You can call these macros like functions, but you cannot use them in any other way (for example, you cannot take their address).

Calling the macros requires a special precaution: namely, the first operand (the obstack pointer) may not contain any side effects, because it may be computed more than once.  For example, if you write this:

     obstack_alloc (get_obstack (), 4);

you will find that get_obstack may be called several times. If you use *obstack_list_ptr++ as the obstack pointer argument, you will get very strange results since the incrementation may occur several times.

In ISO C, each function has both a macro definition and a function definition.  The function definition is used if you take the address of the function without calling it.  An ordinary call uses the macro definition by default, but you can request the function definition instead by writing the function name in parentheses, as shown here:

     char *x;
     void *(*funcp) ();
     /* Use the macro.  */
     x = (char *) obstack_alloc (obptr, size);
     /* Call the function.  */
     x = (char *) (obstack_alloc) (obptr, size);
     /* Take the address of the function.  */
     funcp = obstack_alloc;

This is the same situation that exists in ISO C for the standard library functions.  See Macro Definitions (The GNU C Library Reference Manual).

Warning: When you do use the macros, you must observe the precaution of avoiding side effects in the first operand, even in ISO C.

If you use the GNU C compiler, this precaution is not necessary, because various language extensions in GNU C permit defining the macros so as to compute each argument only once.

Growing Objects
...............

Because memory in obstack chunks is used sequentially, it is possible to build up an object step by step, adding one or more bytes at a time to the end of the object.  With this technique, you do not need to know how much data you will put in the object until you come to the end of it.  We call this the technique of growing objects.  The special functions for adding data to the growing object are described in this section.

You don't need to do anything special when you start to grow an object. Using one of the functions to add data to the object automatically starts it.  However, it is necessary to say explicitly when the object is finished.  This is done with the function obstack_finish.

The actual address of the object thus built up is not known until the object is finished.  Until then, it always remains possible that you will add so much data that the object must be copied into a new chunk.

While the obstack is in use for a growing object, you cannot use it for ordinary allocation of another object.  If you try to do so, the space already added to the growing object will become part of the other object.

 -- Function: void obstack_blank (struct obstack *OBSTACK-PTR, int SIZE)
     The most basic function for adding to a growing object is obstack_blank, which adds space without initializing it.

 -- Function: void obstack_grow (struct obstack *OBSTACK-PTR, void *DATA, int SIZE)
     To add a block of initialized space, use obstack_grow, which is the growing-object analogue of obstack_copy.  It adds SIZE bytes of data to the growing object, copying the contents from DATA.

 -- Function: void obstack_grow0 (struct obstack *OBSTACK-PTR, void *DATA, int SIZE)
     This is the growing-object analogue of obstack_copy0.  It adds SIZE bytes copied from DATA, followed by an additional null character.

 -- Function: void obstack_1grow (struct obstack *OBSTACK-PTR, char C)
     To add one character at a time, use the function obstack_1grow. It adds a single byte containing C to the growing object.

 -- Function: void obstack_ptr_grow (struct obstack *OBSTACK-PTR, void *DATA)
     Adding the value of a pointer one can use the function obstack_ptr_grow.  It adds sizeof (void *) bytes containing the value of DATA.

 -- Function: void obstack_int_grow (struct obstack *OBSTACK-PTR, int DATA)
     A single value of type int can be added by using the obstack_int_grow function.  It adds sizeof (int) bytes to the growing object and initializes them with the value of DATA.

 -- Function: void * obstack_finish (struct obstack *OBSTACK-PTR)
     When you are finished growing the object, use the function obstack_finish to close it off and return its final address.

     Once you have finished the object, the obstack is available for ordinary allocation or for growing another object.

     This function can return a null pointer under the same conditions as obstack_alloc (see Allocation in an Obstack).

When you build an object by growing it, you will probably need to know afterward how long it became.  You need not keep track of this as you grow the object, because you can find out the length from the obstack just before finishing the object with the function obstack_object_size, declared as follows:

 -- Function: int obstack_object_size (struct obstack *OBSTACK-PTR)
     This function returns the current size of the growing object, in bytes. Remember to call this function before finishing the object. After it is finished, obstack_object_size will return zero.

If you have started growing an object and wish to cancel it, you should finish it and then free it, like this:

     obstack_free (obstack_ptr, obstack_finish (obstack_ptr));

This has no effect if no object was growing.

You can use obstack_blank with a negative size argument to make the current object smaller.  Just don't try to shrink it beyond zero length---there's no telling what will happen if you do that.

Extra Fast Growing Objects
..........................

The usual functions for growing objects incur overhead for checking whether there is room for the new growth in the current chunk.  If you are frequently constructing objects in small steps of growth, this overhead can be significant.

You can reduce the overhead by using special ``fast growth'' functions that grow the object without checking.  In order to have a robust program, you must do the checking yourself.  If you do this checking in the simplest way each time you are about to add data to the object, you have not saved anything, because that is what the ordinary growth functions do.  But if you can arrange to check less often, or check more efficiently, then you make the program faster.

The function obstack_room returns the amount of room available in the current chunk.  It is declared as follows:

 -- Function: int obstack_room (struct obstack *OBSTACK-PTR)
     This returns the number of bytes that can be added safely to the current growing object (or to an object about to be started) in obstack OBSTACK using the fast growth functions.

While you know there is room, you can use these fast growth functions for adding data to a growing object:

 -- Function: void obstack_1grow_fast (struct obstack *OBSTACK-PTR, char C)
     The function obstack_1grow_fast adds one byte containing the character C to the growing object in obstack OBSTACK-PTR.

 -- Function: void obstack_ptr_grow_fast (struct obstack *OBSTACK-PTR, void *DATA)
     The function obstack_ptr_grow_fast adds sizeof (void *) bytes containing the value of DATA to the growing object in obstack OBSTACK-PTR.

 -- Function: void obstack_int_grow_fast (struct obstack *OBSTACK-PTR, int DATA)
     The function obstack_int_grow_fast adds sizeof (int) bytes containing the value of DATA to the growing object in obstack OBSTACK-PTR.

 -- Function: void obstack_blank_fast (struct obstack *OBSTACK-PTR, int SIZE)
     The function obstack_blank_fast adds SIZE bytes to the growing object in obstack OBSTACK-PTR without initializing them.

When you check for space using obstack_room and there is not enough room for what you want to add, the fast growth functions are not safe.  In this case, simply use the corresponding ordinary growth function instead.  Very soon this will copy the object to a new chunk; then there will be lots of room available again.

So, each time you use an ordinary growth function, check afterward for sufficient space using obstack_room.  Once the object is copied to a new chunk, there will be plenty of space again, so the program will start using the fast growth functions again.

Here is an example:

     void
     add_string (struct obstack *obstack, const char *ptr, int len)
     {
       while (len > 0)
         {
           int room = obstack_room (obstack);
           if (room == 0)
             {
               /* Not enough room. Add one character slowly,
                  which may copy to a new chunk and make room.  */
               obstack_1grow (obstack, *ptr++);
               len--;
             }
           else
             {
               if (room > len)
                 room = len;
               /* Add fast as much as we have room for. */
               len -= room;
               while (room-- > 0)
                 obstack_1grow_fast (obstack, *ptr++);
             }
         }
     }

Status of an Obstack
....................

Here are functions that provide information on the current status of allocation in an obstack.  You can use them to learn about an object while still growing it.

 -- Function: void * obstack_base (struct obstack *OBSTACK-PTR)
     This function returns the tentative address of the beginning of the currently growing object in OBSTACK-PTR.  If you finish the object immediately, it will have that address.  If you make it larger first, it may outgrow the current chunk---then its address will change!

     If no object is growing, this value says where the next object you allocate will start (once again assuming it fits in the current chunk).

 -- Function: void * obstack_next_free (struct obstack *OBSTACK-PTR)
     This function returns the address of the first free byte in the current chunk of obstack OBSTACK-PTR.  This is the end of the currently growing object.  If no object is growing, obstack_next_free returns the same value as obstack_base.

 -- Function: int obstack_object_size (struct obstack *OBSTACK-PTR)
     This function returns the size in bytes of the currently growing object. This is equivalent to

          obstack_next_free (OBSTACK-PTR) - obstack_base (OBSTACK-PTR)

Alignment of Data in Obstacks
.............................

Each obstack has an alignment boundary; each object allocated in the obstack automatically starts on an address that is a multiple of the specified boundary.  By default, this boundary is aligned so that the object can hold any type of data.

To access an obstack's alignment boundary, use the macro obstack_alignment_mask, whose function prototype looks like this:

 -- Macro: int obstack_alignment_mask (struct obstack *OBSTACK-PTR)
     The value is a bit mask; a bit that is 1 indicates that the corresponding bit in the address of an object should be 0.  The mask value should be one less than a power of 2; the effect is that all object addresses are multiples of that power of 2.  The default value of the mask is a value that allows aligned objects to hold any type of data: for example, if its value is 3, any type of data can be stored at locations whose addresses are multiples of 4.  A mask value of 0 means an object can start on any multiple of 1 (that is, no alignment is required).

     The expansion of the macro obstack_alignment_mask is an lvalue, so you can alter the mask by assignment.  For example, this statement:

          obstack_alignment_mask (obstack_ptr) = 0;

     has the effect of turning off alignment processing in the specified obstack.

Note that a change in alignment mask does not take effect until after the next time an object is allocated or finished in the obstack.  If you are not growing an object, you can make the new alignment mask take effect immediately by calling obstack_finish. This will finish a zero-length object and then do proper alignment for the next object.

Obstack Chunks
..............

Obstacks work by allocating space for themselves in large chunks, and then parceling out space in the chunks to satisfy your requests.  Chunks are normally 4096 bytes long unless you specify a different chunk size. The chunk size includes 8 bytes of overhead that are not actually used for storing objects.  Regardless of the specified size, longer chunks will be allocated when necessary for long objects.

The obstack library allocates chunks by calling the function obstack_chunk_alloc, which you must define.  When a chunk is no longer needed because you have freed all the objects in it, the obstack library frees the chunk by calling obstack_chunk_free, which you must also define.

These two must be defined (as macros) or declared (as functions) in each source file that uses obstack_init (see Creating Obstacks). Most often they are defined as macros like this:

     #define obstack_chunk_alloc malloc
     #define obstack_chunk_free free

Note that these are simple macros (no arguments).  Macro definitions with arguments will not work!  It is necessary that obstack_chunk_alloc or obstack_chunk_free, alone, expand into a function name if it is not itself a function name.

If you allocate chunks with malloc, the chunk size should be a power of 2.  The default chunk size, 4096, was chosen because it is long enough to satisfy many typical requests on the obstack yet short enough not to waste too much memory in the portion of the last chunk not yet used.

 -- Macro: int obstack_chunk_size (struct obstack *OBSTACK-PTR)
     This returns the chunk size of the given obstack.

Since this macro expands to an lvalue, you can specify a new chunk size by assigning it a new value.  Doing so does not affect the chunks already allocated, but will change the size of chunks allocated for that particular obstack in the future.  It is unlikely to be useful to make the chunk size smaller, but making it larger might improve efficiency if you are allocating many objects whose size is comparable to the chunk size.  Here is how to do so cleanly:

     if (obstack_chunk_size (obstack_ptr) < NEW-CHUNK-SIZE)
       obstack_chunk_size (obstack_ptr) = NEW-CHUNK-SIZE;

Summary of Obstack Functions
............................

Here is a summary of all the functions associated with obstacks.  Each takes the address of an obstack (struct obstack *) as its first argument.

void obstack_init (struct obstack *OBSTACK-PTR)
     Initialize use of an obstack.  See Creating Obstacks.

void *obstack_alloc (struct obstack *OBSTACK-PTR, int SIZE)
     Allocate an object of SIZE uninitialized bytes. See Allocation in an Obstack.

void *obstack_copy (struct obstack *OBSTACK-PTR, void *ADDRESS, int SIZE)
     Allocate an object of SIZE bytes, with contents copied from ADDRESS.  See Allocation in an Obstack.

void *obstack_copy0 (struct obstack *OBSTACK-PTR, void *ADDRESS, int SIZE)
     Allocate an object of SIZE+1 bytes, with SIZE of them copied from ADDRESS, followed by a null character at the end. See Allocation in an Obstack.

void obstack_free (struct obstack *OBSTACK-PTR, void *OBJECT)
     Free OBJECT (and everything allocated in the specified obstack more recently than OBJECT).  See Freeing Obstack Objects.

void obstack_blank (struct obstack *OBSTACK-PTR, int SIZE)
     Add SIZE uninitialized bytes to a growing object. See Growing Objects.

void obstack_grow (struct obstack *OBSTACK-PTR, void *ADDRESS, int SIZE)
     Add SIZE bytes, copied from ADDRESS, to a growing object. See Growing Objects.

void obstack_grow0 (struct obstack *OBSTACK-PTR, void *ADDRESS, int SIZE)
     Add SIZE bytes, copied from ADDRESS, to a growing object, and then add another byte containing a null character.  See Growing Objects.

void obstack_1grow (struct obstack *OBSTACK-PTR, char DATA-CHAR)
     Add one byte containing DATA-CHAR to a growing object. See Growing Objects.

void *obstack_finish (struct obstack *OBSTACK-PTR)
     Finalize the object that is growing and return its permanent address. See Growing Objects.

int obstack_object_size (struct obstack *OBSTACK-PTR)
     Get the current size of the currently growing object.  See Growing Objects.

void obstack_blank_fast (struct obstack *OBSTACK-PTR, int SIZE)
     Add SIZE uninitialized bytes to a growing object without checking that there is enough room.  See Extra Fast Growing.

void obstack_1grow_fast (struct obstack *OBSTACK-PTR, char DATA-CHAR)
     Add one byte containing DATA-CHAR to a growing object without checking that there is enough room.  See Extra Fast Growing.

int obstack_room (struct obstack *OBSTACK-PTR)
     Get the amount of room now available for growing the current object. See Extra Fast Growing.

int obstack_alignment_mask (struct obstack *OBSTACK-PTR)
     The mask used for aligning the beginning of an object.  This is an lvalue.  See Obstacks Data Alignment.

int obstack_chunk_size (struct obstack *OBSTACK-PTR)
     The size for allocating chunks.  This is an lvalue.  See Obstack Chunks.

void *obstack_base (struct obstack *OBSTACK-PTR)
     Tentative starting address of the currently growing object. See Status of an Obstack.

void *obstack_next_free (struct obstack *OBSTACK-PTR)
     Address just after the end of the currently growing object. See Status of an Obstack.