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.
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 that is in first in last out fashion, 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.[1]
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. one should not try to access the contents of the structure directly.
Declaration of variables of type struct obstack and using them as obstacks, or can allocate obstacks dynamically is like any other kind of object. Dynamic allocation of obstacks allows the program to have a variable number of different stacks.
All the functions that work with obstacks require the user to specify which obstack to use.one can do this with a pointer of type struct obstack. It is often said that “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 the user allocate an object that won't fit in the previous chunk. Since the obstack library manages chunks automatically, the programmer don't need to pay much attention to them, but the user need to supply a function which the obstack library should use to get a chunk. Usually supply a function which uses malloc directly or indirectly. The user must also supply a function to free a chunk.
Preparing for using Obstack
For using obstack functions the user 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 for allocation of chunks of memory into which objects are stored.
The other function, obstack_chunk_free is used to free the memory initially allocated.For avoiding any errors, these two functions should be included before any use of obstack in the source file.
Usually these are defined to use malloc via the intermediary xmalloc. This is done with the following pair of macro definitions:
#define obstack_chunk_alloc xmalloc
#define obstack_chunk_free free
Though the memory one gets using obstacks really comes from malloc, using obstacks is faster because malloc is called less often, for larger blocks of memory.
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.
Here are two examples of how to allocate the memory space for an obstack and initialize it.
Initially, an obstack that is a static variable:
static struct obstack my_obstack;
...
obstack_init (&my_obstack);
Second, an obstack that is itself has dynamic allocation:
struct obstack *my_obstack_ptr
= (struct obstack *) xmalloc (sizeof (struct obstack));
obstack_init (my_obstack_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 error message and exit. One should supply a function that either calls exit or longjump and doesn't return.
void my_obstack_alloc_failed (void)
...
obstack_alloc_failed_handler = &my_obstack_alloc_failed;
Allocation in an Obstack
A direct way to allocate an object in an obstack is with obsctack_alloc, which is invoked almost like a malloc.
void * obstack_alloc (struct obstack *obstack-ptr, int size)
This will allocate an uninitialized block of memory of size bytes in an obstack and will return its address.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 is required 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, 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. It is declared as given below:
— Function:
void * obstack_copy (struct obstack *obstack-ptr, void *address, int size)
This will allocate a block of memory if new chunk of memory is available and then 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.
Freeing Objects in Obstack
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 ans deallocating objects in 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 );
}
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.
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) ();
/* 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.
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 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 [[Chunking (computing) |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