Obstack

Introduction

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.

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;

Links

• Creating Obstack