Obstack
An obstack is a stack of objects (data items) which grows dynamically.
Obstack code typically provides C macros which take care of memory allocation and management for the user. Basically, obstacks are used as a form of memory management which can be more efficient and less difficult to implement than malloc/free in several situations.For example, say one needs to set up a stack for handling data items whose number grows for a while and then reach a final form; such a stack could be defined in obstack.h.
Freeing allocated objects
Once the object is allocated a new chunk of memory in obstack it must be freed after its use. To free an object allocated in an obstack, a function obstack_free is used. 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.
If object is a null pointer, the result is an uninitialized obstack. This will free all memory in an obstack but to leave it valid for further allocation, a function obstack_free with the address of the first object allocated on the obstack is called:
obstack_free (obstack_ptr, first_object_allocated_ptr);
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 . Then other obstacks, or non-obstack allocation, can reuse the space of the chunk.
Example of allocating, storing, and deallocating objects in an obstack:
void test(int n) {
struct obstack obst;
obstack_init(&obst);
/* Allocate memory for a string of length n -1 */
char *str = obstack_alloc(&obst, n * sizeof(str[0]));
/* Allocate an array for n nodes */
node_t **nodes = obstack_alloc(&obst, n * sizeof(nodes[0]));
/* Store the current mark of the obstack */
void *mark = obstack_base (&obst);
/* Allocate the nodes */
for (i = 0; i < n; i++)
nodes[i] = obstack_alloc(&obst, sizeof(node[0]));
/* All the marks are gone */
obstack_free(&obst, mark);
/* Everything has gone */
obstack_free(&obst, NULL);
}
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.
In 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.
In ISO C, each function has both a macro definition and a function definition. The function definition is used if the address of the function without calling it is taken. 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)();
x = (char *) obstack_alloc(obptr, size); /* Use the macro. */
x = (char *) (obstack_alloc) (obptr, size); /* Call the function. */
funcp = obstack_alloc; /* Take the address of the function. */
This is the same situation that exists in ISO C for the standard library functions.
Growing Objects
Since the memory chunks in an obstack are used sequentially, it is possible to build up an object by adding data of size 'bytes' at the end of it.This technique of step by step building up of an object is termed as 'growing an object'.
Fast growing Objects
The usual functions for growing objects result in an overhead for checking whether there is space for the new growth in the current chunk.If the objects are constructed frequently in small steps of growth, this overhead can be significant.
The overhead can be reduced by using special “fast growth” functions that grow the object without checking. In order to have a robust program, the checking must be done by the user. If the checking is done each time when data is added to the object, the previous data is not saved, because that is what the ordinary growth functions do. In order to make the program more efficient and fast, this checking should be done less often.
The function obstack_space returns the amount of room available in the current chunk. It is declared as follows:
— Function:
int obstack_space (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.
After checking the return value of the above function,one can use 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_space and there is not enough room for what data to be added, 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; and this results in a large amount of space.
So, each time an ordinary growth function is used,sufficient space is checked for, using obstack_space. Once the object is copied to a new chunk, this results in a plenty of space, so the program starts using the fast growth functions again.
Example:
void
add_string (struct obstack *obstack, const char *ptr, int len)
{
while (len > 0)
{
int space = obstack_space (obstack);
if (space == 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 (space > len)
space = len;
/* Add fast as much as we have room for. */
len -= space;
while (space-- > 0)
obstack_1grow_fast (obstack, *ptr++);
}
}
}
Status of an Obstack
The following function an account of the current status of a dynamically growing obstack.
— 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 the object is finished immediately, it will have that address. If the object is made large at the first instance, 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
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 4 bytes.
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 3, so that 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 the programmer can alter the mask by assignment. For example, the statement:
obstack_alignment_mask (obstack_ptr) = 0;
has the effect of turning off alignment processing in the specified obstack.
A change in alignment mask does not take effect until after the next time an object is allocated or finished in the obstack. If an object is not growing, then one 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 programmer's requests. Chunks are normally 4096 bytes long unless user 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 the user must define. When a chunk is no longer needed because all the objects in it are freed, the obstack library frees the chunk by calling obstack_chunk_free, which should also be defined by the user.
These two must be defined as macros or declared as functions in each source file that uses obstack_init. Most often they are defined as macros like this:
#define obstack_chunk_alloc malloc
#define obstack_chunk_free free
These are simple macros (no arguments). 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 the user allocates 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, user can specify a new [[Chunking (computing) |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 user is allocating many objects whose size is comparable to the chunk size. Example of doing this is:
if (obstack_chunk_size (obstack_ptr) < new-chunk-size)
obstack_chunk_size (obstack_ptr) = new-chunk-size;
References