189857Sobrien@node Obstacks,Licenses,Functions,Top 289857Sobrien@chapter Obstacks 389857Sobrien@cindex obstacks 489857Sobrien 589857SobrienAn @dfn{obstack} is a pool of memory containing a stack of objects. You 689857Sobriencan create any number of separate obstacks, and then allocate objects in 789857Sobrienspecified obstacks. Within each obstack, the last object allocated must 889857Sobrienalways be the first one freed, but distinct obstacks are independent of 989857Sobrieneach other. 1089857Sobrien 1189857SobrienAside from this one constraint of order of freeing, obstacks are totally 1289857Sobriengeneral: an obstack can contain any number of objects of any size. They 1389857Sobrienare implemented with macros, so allocation is usually very fast as long as 1489857Sobrienthe objects are usually small. And the only space overhead per object is 1589857Sobrienthe padding needed to start each object on a suitable boundary. 1689857Sobrien 1789857Sobrien@menu 1889857Sobrien* Creating Obstacks:: How to declare an obstack in your program. 1989857Sobrien* Preparing for Obstacks:: Preparations needed before you can 2089857Sobrien use obstacks. 2189857Sobrien* Allocation in an Obstack:: Allocating objects in an obstack. 2289857Sobrien* Freeing Obstack Objects:: Freeing objects in an obstack. 2389857Sobrien* Obstack Functions:: The obstack functions are both 2489857Sobrien functions and macros. 2589857Sobrien* Growing Objects:: Making an object bigger by stages. 2689857Sobrien* Extra Fast Growing:: Extra-high-efficiency (though more 2789857Sobrien complicated) growing objects. 2889857Sobrien* Status of an Obstack:: Inquiries about the status of an obstack. 2989857Sobrien* Obstacks Data Alignment:: Controlling alignment of objects in obstacks. 3089857Sobrien* Obstack Chunks:: How obstacks obtain and release chunks; 3189857Sobrien efficiency considerations. 3289857Sobrien* Summary of Obstacks:: 3389857Sobrien@end menu 3489857Sobrien 3589857Sobrien@node Creating Obstacks 3689857Sobrien@section Creating Obstacks 3789857Sobrien 3889857SobrienThe utilities for manipulating obstacks are declared in the header 3989857Sobrienfile @file{obstack.h}. 4089857Sobrien@pindex obstack.h 4189857Sobrien 4289857Sobrien@comment obstack.h 4389857Sobrien@comment GNU 4489857Sobrien@deftp {Data Type} {struct obstack} 4589857SobrienAn obstack is represented by a data structure of type @code{struct 4689857Sobrienobstack}. This structure has a small fixed size; it records the status 4789857Sobrienof the obstack and how to find the space in which objects are allocated. 4889857SobrienIt does not contain any of the objects themselves. You should not try 4989857Sobriento access the contents of the structure directly; use only the functions 5089857Sobriendescribed in this chapter. 5189857Sobrien@end deftp 5289857Sobrien 5389857SobrienYou can declare variables of type @code{struct obstack} and use them as 5489857Sobrienobstacks, or you can allocate obstacks dynamically like any other kind 5589857Sobrienof object. Dynamic allocation of obstacks allows your program to have a 5689857Sobrienvariable number of different stacks. (You can even allocate an 5789857Sobrienobstack structure in another obstack, but this is rarely useful.) 5889857Sobrien 5989857SobrienAll the functions that work with obstacks require you to specify which 6089857Sobrienobstack to use. You do this with a pointer of type @code{struct obstack 6189857Sobrien*}. In the following, we often say ``an obstack'' when strictly 6289857Sobrienspeaking the object at hand is such a pointer. 6389857Sobrien 6489857SobrienThe objects in the obstack are packed into large blocks called 6589857Sobrien@dfn{chunks}. The @code{struct obstack} structure points to a chain of 6689857Sobrienthe chunks currently in use. 6789857Sobrien 6889857SobrienThe obstack library obtains a new chunk whenever you allocate an object 6989857Sobrienthat won't fit in the previous chunk. Since the obstack library manages 7089857Sobrienchunks automatically, you don't need to pay much attention to them, but 7189857Sobrienyou do need to supply a function which the obstack library should use to 7289857Sobrienget a chunk. Usually you supply a function which uses @code{malloc} 7389857Sobriendirectly or indirectly. You must also supply a function to free a chunk. 7489857SobrienThese matters are described in the following section. 7589857Sobrien 7689857Sobrien@node Preparing for Obstacks 7789857Sobrien@section Preparing for Using Obstacks 7889857Sobrien 7989857SobrienEach source file in which you plan to use the obstack functions 8089857Sobrienmust include the header file @file{obstack.h}, like this: 8189857Sobrien 8289857Sobrien@smallexample 8389857Sobrien#include <obstack.h> 8489857Sobrien@end smallexample 8589857Sobrien 8689857Sobrien@findex obstack_chunk_alloc 8789857Sobrien@findex obstack_chunk_free 8889857SobrienAlso, if the source file uses the macro @code{obstack_init}, it must 8989857Sobriendeclare or define two functions or macros that will be called by the 9089857Sobrienobstack library. One, @code{obstack_chunk_alloc}, is used to allocate 9189857Sobrienthe chunks of memory into which objects are packed. The other, 9289857Sobrien@code{obstack_chunk_free}, is used to return chunks when the objects in 9389857Sobrienthem are freed. These macros should appear before any use of obstacks 9489857Sobrienin the source file. 9589857Sobrien 9689857SobrienUsually these are defined to use @code{malloc} via the intermediary 9789857Sobrien@code{xmalloc} (@pxref{Unconstrained Allocation, , , libc, The GNU C Library Reference Manual}). This is done with 9889857Sobrienthe following pair of macro definitions: 9989857Sobrien 10089857Sobrien@smallexample 10189857Sobrien#define obstack_chunk_alloc xmalloc 10289857Sobrien#define obstack_chunk_free free 10389857Sobrien@end smallexample 10489857Sobrien 10589857Sobrien@noindent 10689857SobrienThough the memory you get using obstacks really comes from @code{malloc}, 10789857Sobrienusing obstacks is faster because @code{malloc} is called less often, for 10889857Sobrienlarger blocks of memory. @xref{Obstack Chunks}, for full details. 10989857Sobrien 11089857SobrienAt run time, before the program can use a @code{struct obstack} object 11189857Sobrienas an obstack, it must initialize the obstack by calling 11289857Sobrien@code{obstack_init}. 11389857Sobrien 11489857Sobrien@comment obstack.h 11589857Sobrien@comment GNU 11689857Sobrien@deftypefun int obstack_init (struct obstack *@var{obstack-ptr}) 11789857SobrienInitialize obstack @var{obstack-ptr} for allocation of objects. This 11889857Sobrienfunction calls the obstack's @code{obstack_chunk_alloc} function. If 11989857Sobrienallocation of memory fails, the function pointed to by 12089857Sobrien@code{obstack_alloc_failed_handler} is called. The @code{obstack_init} 12189857Sobrienfunction always returns 1 (Compatibility notice: Former versions of 12289857Sobrienobstack returned 0 if allocation failed). 12389857Sobrien@end deftypefun 12489857Sobrien 12589857SobrienHere are two examples of how to allocate the space for an obstack and 12689857Sobrieninitialize it. First, an obstack that is a static variable: 12789857Sobrien 12889857Sobrien@smallexample 12989857Sobrienstatic struct obstack myobstack; 13089857Sobrien@dots{} 13189857Sobrienobstack_init (&myobstack); 13289857Sobrien@end smallexample 13389857Sobrien 13489857Sobrien@noindent 13589857SobrienSecond, an obstack that is itself dynamically allocated: 13689857Sobrien 13789857Sobrien@smallexample 13889857Sobrienstruct obstack *myobstack_ptr 13989857Sobrien = (struct obstack *) xmalloc (sizeof (struct obstack)); 14089857Sobrien 14189857Sobrienobstack_init (myobstack_ptr); 14289857Sobrien@end smallexample 14389857Sobrien 14489857Sobrien@comment obstack.h 14589857Sobrien@comment GNU 14689857Sobrien@defvar obstack_alloc_failed_handler 14789857SobrienThe value of this variable is a pointer to a function that 14889857Sobrien@code{obstack} uses when @code{obstack_chunk_alloc} fails to allocate 14989857Sobrienmemory. The default action is to print a message and abort. 15089857SobrienYou should supply a function that either calls @code{exit} 15189857Sobrien(@pxref{Program Termination, , , libc, The GNU C Library Reference Manual}) or @code{longjmp} (@pxref{Non-Local 15289857SobrienExits, , , libc, The GNU C Library Reference Manual}) and doesn't return. 15389857Sobrien 15489857Sobrien@smallexample 15589857Sobrienvoid my_obstack_alloc_failed (void) 15689857Sobrien@dots{} 15789857Sobrienobstack_alloc_failed_handler = &my_obstack_alloc_failed; 15889857Sobrien@end smallexample 15989857Sobrien 16089857Sobrien@end defvar 16189857Sobrien 16289857Sobrien@node Allocation in an Obstack 16389857Sobrien@section Allocation in an Obstack 16489857Sobrien@cindex allocation (obstacks) 16589857Sobrien 16689857SobrienThe most direct way to allocate an object in an obstack is with 16789857Sobrien@code{obstack_alloc}, which is invoked almost like @code{malloc}. 16889857Sobrien 16989857Sobrien@comment obstack.h 17089857Sobrien@comment GNU 17189857Sobrien@deftypefun {void *} obstack_alloc (struct obstack *@var{obstack-ptr}, int @var{size}) 17289857SobrienThis allocates an uninitialized block of @var{size} bytes in an obstack 17389857Sobrienand returns its address. Here @var{obstack-ptr} specifies which obstack 17489857Sobriento allocate the block in; it is the address of the @code{struct obstack} 17589857Sobrienobject which represents the obstack. Each obstack function or macro 17689857Sobrienrequires you to specify an @var{obstack-ptr} as the first argument. 17789857Sobrien 17889857SobrienThis function calls the obstack's @code{obstack_chunk_alloc} function if 17989857Sobrienit needs to allocate a new chunk of memory; it calls 18089857Sobrien@code{obstack_alloc_failed_handler} if allocation of memory by 18189857Sobrien@code{obstack_chunk_alloc} failed. 18289857Sobrien@end deftypefun 18389857Sobrien 18489857SobrienFor example, here is a function that allocates a copy of a string @var{str} 18589857Sobrienin a specific obstack, which is in the variable @code{string_obstack}: 18689857Sobrien 18789857Sobrien@smallexample 18889857Sobrienstruct obstack string_obstack; 18989857Sobrien 19089857Sobrienchar * 19189857Sobriencopystring (char *string) 19289857Sobrien@{ 19389857Sobrien size_t len = strlen (string) + 1; 19489857Sobrien char *s = (char *) obstack_alloc (&string_obstack, len); 19589857Sobrien memcpy (s, string, len); 19689857Sobrien return s; 19789857Sobrien@} 19889857Sobrien@end smallexample 19989857Sobrien 20089857SobrienTo allocate a block with specified contents, use the function 20189857Sobrien@code{obstack_copy}, declared like this: 20289857Sobrien 20389857Sobrien@comment obstack.h 20489857Sobrien@comment GNU 20589857Sobrien@deftypefun {void *} obstack_copy (struct obstack *@var{obstack-ptr}, void *@var{address}, int @var{size}) 20689857SobrienThis allocates a block and initializes it by copying @var{size} 20789857Sobrienbytes of data starting at @var{address}. It calls 20889857Sobrien@code{obstack_alloc_failed_handler} if allocation of memory by 20989857Sobrien@code{obstack_chunk_alloc} failed. 21089857Sobrien@end deftypefun 21189857Sobrien 21289857Sobrien@comment obstack.h 21389857Sobrien@comment GNU 21489857Sobrien@deftypefun {void *} obstack_copy0 (struct obstack *@var{obstack-ptr}, void *@var{address}, int @var{size}) 21589857SobrienLike @code{obstack_copy}, but appends an extra byte containing a null 21689857Sobriencharacter. This extra byte is not counted in the argument @var{size}. 21789857Sobrien@end deftypefun 21889857Sobrien 21989857SobrienThe @code{obstack_copy0} function is convenient for copying a sequence 22089857Sobrienof characters into an obstack as a null-terminated string. Here is an 22189857Sobrienexample of its use: 22289857Sobrien 22389857Sobrien@smallexample 22489857Sobrienchar * 22589857Sobrienobstack_savestring (char *addr, int size) 22689857Sobrien@{ 22789857Sobrien return obstack_copy0 (&myobstack, addr, size); 22889857Sobrien@} 22989857Sobrien@end smallexample 23089857Sobrien 23189857Sobrien@noindent 23289857SobrienContrast this with the previous example of @code{savestring} using 23389857Sobrien@code{malloc} (@pxref{Basic Allocation, , , libc, The GNU C Library Reference Manual}). 23489857Sobrien 23589857Sobrien@node Freeing Obstack Objects 23689857Sobrien@section Freeing Objects in an Obstack 23789857Sobrien@cindex freeing (obstacks) 23889857Sobrien 23989857SobrienTo free an object allocated in an obstack, use the function 24089857Sobrien@code{obstack_free}. Since the obstack is a stack of objects, freeing 24189857Sobrienone object automatically frees all other objects allocated more recently 24289857Sobrienin the same obstack. 24389857Sobrien 24489857Sobrien@comment obstack.h 24589857Sobrien@comment GNU 24689857Sobrien@deftypefun void obstack_free (struct obstack *@var{obstack-ptr}, void *@var{object}) 24789857SobrienIf @var{object} is a null pointer, everything allocated in the obstack 24889857Sobrienis freed. Otherwise, @var{object} must be the address of an object 24989857Sobrienallocated in the obstack. Then @var{object} is freed, along with 25089857Sobrieneverything allocated in @var{obstack} since @var{object}. 25189857Sobrien@end deftypefun 25289857Sobrien 25389857SobrienNote that if @var{object} is a null pointer, the result is an 25489857Sobrienuninitialized obstack. To free all memory in an obstack but leave it 25589857Sobrienvalid for further allocation, call @code{obstack_free} with the address 25689857Sobrienof the first object allocated on the obstack: 25789857Sobrien 25889857Sobrien@smallexample 25989857Sobrienobstack_free (obstack_ptr, first_object_allocated_ptr); 26089857Sobrien@end smallexample 26189857Sobrien 26289857SobrienRecall that the objects in an obstack are grouped into chunks. When all 26389857Sobrienthe objects in a chunk become free, the obstack library automatically 26489857Sobrienfrees the chunk (@pxref{Preparing for Obstacks}). Then other 26589857Sobrienobstacks, or non-obstack allocation, can reuse the space of the chunk. 26689857Sobrien 26789857Sobrien@node Obstack Functions 26889857Sobrien@section Obstack Functions and Macros 26989857Sobrien@cindex macros 27089857Sobrien 27189857SobrienThe interfaces for using obstacks may be defined either as functions or 27289857Sobrienas macros, depending on the compiler. The obstack facility works with 27389857Sobrienall C compilers, including both @w{ISO C} and traditional C, but there are 27489857Sobrienprecautions you must take if you plan to use compilers other than GNU C. 27589857Sobrien 27689857SobrienIf you are using an old-fashioned @w{non-ISO C} compiler, all the obstack 27789857Sobrien``functions'' are actually defined only as macros. You can call these 27889857Sobrienmacros like functions, but you cannot use them in any other way (for 27989857Sobrienexample, you cannot take their address). 28089857Sobrien 28189857SobrienCalling the macros requires a special precaution: namely, the first 28289857Sobrienoperand (the obstack pointer) may not contain any side effects, because 28389857Sobrienit may be computed more than once. For example, if you write this: 28489857Sobrien 28589857Sobrien@smallexample 28689857Sobrienobstack_alloc (get_obstack (), 4); 28789857Sobrien@end smallexample 28889857Sobrien 28989857Sobrien@noindent 29089857Sobrienyou will find that @code{get_obstack} may be called several times. 29189857SobrienIf you use @code{*obstack_list_ptr++} as the obstack pointer argument, 29289857Sobrienyou will get very strange results since the incrementation may occur 29389857Sobrienseveral times. 29489857Sobrien 29589857SobrienIn @w{ISO C}, each function has both a macro definition and a function 29689857Sobriendefinition. The function definition is used if you take the address of the 29789857Sobrienfunction without calling it. An ordinary call uses the macro definition by 29889857Sobriendefault, but you can request the function definition instead by writing the 29989857Sobrienfunction name in parentheses, as shown here: 30089857Sobrien 30189857Sobrien@smallexample 30289857Sobrienchar *x; 30389857Sobrienvoid *(*funcp) (); 30489857Sobrien/* @r{Use the macro}. */ 30589857Sobrienx = (char *) obstack_alloc (obptr, size); 30689857Sobrien/* @r{Call the function}. */ 30789857Sobrienx = (char *) (obstack_alloc) (obptr, size); 30889857Sobrien/* @r{Take the address of the function}. */ 30989857Sobrienfuncp = obstack_alloc; 31089857Sobrien@end smallexample 31189857Sobrien 31289857Sobrien@noindent 31389857SobrienThis is the same situation that exists in @w{ISO C} for the standard library 31489857Sobrienfunctions. @xref{Macro Definitions, , , libc, The GNU C Library Reference Manual}. 31589857Sobrien 31689857Sobrien@strong{Warning:} When you do use the macros, you must observe the 31789857Sobrienprecaution of avoiding side effects in the first operand, even in @w{ISO C}. 31889857Sobrien 31989857SobrienIf you use the GNU C compiler, this precaution is not necessary, because 32089857Sobrienvarious language extensions in GNU C permit defining the macros so as to 32189857Sobriencompute each argument only once. 32289857Sobrien 32389857Sobrien@node Growing Objects 32489857Sobrien@section Growing Objects 32589857Sobrien@cindex growing objects (in obstacks) 32689857Sobrien@cindex changing the size of a block (obstacks) 32789857Sobrien 32889857SobrienBecause memory in obstack chunks is used sequentially, it is possible to 32989857Sobrienbuild up an object step by step, adding one or more bytes at a time to the 33089857Sobrienend of the object. With this technique, you do not need to know how much 33189857Sobriendata you will put in the object until you come to the end of it. We call 33289857Sobrienthis the technique of @dfn{growing objects}. The special functions 33389857Sobrienfor adding data to the growing object are described in this section. 33489857Sobrien 33589857SobrienYou don't need to do anything special when you start to grow an object. 33689857SobrienUsing one of the functions to add data to the object automatically 33789857Sobrienstarts it. However, it is necessary to say explicitly when the object is 33889857Sobrienfinished. This is done with the function @code{obstack_finish}. 33989857Sobrien 34089857SobrienThe actual address of the object thus built up is not known until the 34189857Sobrienobject is finished. Until then, it always remains possible that you will 34289857Sobrienadd so much data that the object must be copied into a new chunk. 34389857Sobrien 34489857SobrienWhile the obstack is in use for a growing object, you cannot use it for 34589857Sobrienordinary allocation of another object. If you try to do so, the space 34689857Sobrienalready added to the growing object will become part of the other object. 34789857Sobrien 34889857Sobrien@comment obstack.h 34989857Sobrien@comment GNU 35089857Sobrien@deftypefun void obstack_blank (struct obstack *@var{obstack-ptr}, int @var{size}) 35189857SobrienThe most basic function for adding to a growing object is 35289857Sobrien@code{obstack_blank}, which adds space without initializing it. 35389857Sobrien@end deftypefun 35489857Sobrien 35589857Sobrien@comment obstack.h 35689857Sobrien@comment GNU 35789857Sobrien@deftypefun void obstack_grow (struct obstack *@var{obstack-ptr}, void *@var{data}, int @var{size}) 35889857SobrienTo add a block of initialized space, use @code{obstack_grow}, which is 35989857Sobrienthe growing-object analogue of @code{obstack_copy}. It adds @var{size} 36089857Sobrienbytes of data to the growing object, copying the contents from 36189857Sobrien@var{data}. 36289857Sobrien@end deftypefun 36389857Sobrien 36489857Sobrien@comment obstack.h 36589857Sobrien@comment GNU 36689857Sobrien@deftypefun void obstack_grow0 (struct obstack *@var{obstack-ptr}, void *@var{data}, int @var{size}) 36789857SobrienThis is the growing-object analogue of @code{obstack_copy0}. It adds 36889857Sobrien@var{size} bytes copied from @var{data}, followed by an additional null 36989857Sobriencharacter. 37089857Sobrien@end deftypefun 37189857Sobrien 37289857Sobrien@comment obstack.h 37389857Sobrien@comment GNU 37489857Sobrien@deftypefun void obstack_1grow (struct obstack *@var{obstack-ptr}, char @var{c}) 37589857SobrienTo add one character at a time, use the function @code{obstack_1grow}. 37689857SobrienIt adds a single byte containing @var{c} to the growing object. 37789857Sobrien@end deftypefun 37889857Sobrien 37989857Sobrien@comment obstack.h 38089857Sobrien@comment GNU 38189857Sobrien@deftypefun void obstack_ptr_grow (struct obstack *@var{obstack-ptr}, void *@var{data}) 38289857SobrienAdding the value of a pointer one can use the function 38389857Sobrien@code{obstack_ptr_grow}. It adds @code{sizeof (void *)} bytes 38489857Sobriencontaining the value of @var{data}. 38589857Sobrien@end deftypefun 38689857Sobrien 38789857Sobrien@comment obstack.h 38889857Sobrien@comment GNU 38989857Sobrien@deftypefun void obstack_int_grow (struct obstack *@var{obstack-ptr}, int @var{data}) 39089857SobrienA single value of type @code{int} can be added by using the 39189857Sobrien@code{obstack_int_grow} function. It adds @code{sizeof (int)} bytes to 39289857Sobrienthe growing object and initializes them with the value of @var{data}. 39389857Sobrien@end deftypefun 39489857Sobrien 39589857Sobrien@comment obstack.h 39689857Sobrien@comment GNU 39789857Sobrien@deftypefun {void *} obstack_finish (struct obstack *@var{obstack-ptr}) 39889857SobrienWhen you are finished growing the object, use the function 39989857Sobrien@code{obstack_finish} to close it off and return its final address. 40089857Sobrien 40189857SobrienOnce you have finished the object, the obstack is available for ordinary 40289857Sobrienallocation or for growing another object. 40389857Sobrien 40489857SobrienThis function can return a null pointer under the same conditions as 40589857Sobrien@code{obstack_alloc} (@pxref{Allocation in an Obstack}). 40689857Sobrien@end deftypefun 40789857Sobrien 40889857SobrienWhen you build an object by growing it, you will probably need to know 40989857Sobrienafterward how long it became. You need not keep track of this as you grow 41089857Sobrienthe object, because you can find out the length from the obstack just 41189857Sobrienbefore finishing the object with the function @code{obstack_object_size}, 41289857Sobriendeclared as follows: 41389857Sobrien 41489857Sobrien@comment obstack.h 41589857Sobrien@comment GNU 41689857Sobrien@deftypefun int obstack_object_size (struct obstack *@var{obstack-ptr}) 41789857SobrienThis function returns the current size of the growing object, in bytes. 41889857SobrienRemember to call this function @emph{before} finishing the object. 41989857SobrienAfter it is finished, @code{obstack_object_size} will return zero. 42089857Sobrien@end deftypefun 42189857Sobrien 42289857SobrienIf you have started growing an object and wish to cancel it, you should 42389857Sobrienfinish it and then free it, like this: 42489857Sobrien 42589857Sobrien@smallexample 42689857Sobrienobstack_free (obstack_ptr, obstack_finish (obstack_ptr)); 42789857Sobrien@end smallexample 42889857Sobrien 42989857Sobrien@noindent 43089857SobrienThis has no effect if no object was growing. 43189857Sobrien 43289857Sobrien@cindex shrinking objects 43389857SobrienYou can use @code{obstack_blank} with a negative size argument to make 43489857Sobrienthe current object smaller. Just don't try to shrink it beyond zero 43589857Sobrienlength---there's no telling what will happen if you do that. 43689857Sobrien 43789857Sobrien@node Extra Fast Growing 43889857Sobrien@section Extra Fast Growing Objects 43989857Sobrien@cindex efficiency and obstacks 44089857Sobrien 44189857SobrienThe usual functions for growing objects incur overhead for checking 44289857Sobrienwhether there is room for the new growth in the current chunk. If you 44389857Sobrienare frequently constructing objects in small steps of growth, this 44489857Sobrienoverhead can be significant. 44589857Sobrien 44689857SobrienYou can reduce the overhead by using special ``fast growth'' 44789857Sobrienfunctions that grow the object without checking. In order to have a 44889857Sobrienrobust program, you must do the checking yourself. If you do this checking 44989857Sobrienin the simplest way each time you are about to add data to the object, you 45089857Sobrienhave not saved anything, because that is what the ordinary growth 45189857Sobrienfunctions do. But if you can arrange to check less often, or check 45289857Sobrienmore efficiently, then you make the program faster. 45389857Sobrien 45489857SobrienThe function @code{obstack_room} returns the amount of room available 45589857Sobrienin the current chunk. It is declared as follows: 45689857Sobrien 45789857Sobrien@comment obstack.h 45889857Sobrien@comment GNU 45989857Sobrien@deftypefun int obstack_room (struct obstack *@var{obstack-ptr}) 46089857SobrienThis returns the number of bytes that can be added safely to the current 46189857Sobriengrowing object (or to an object about to be started) in obstack 46289857Sobrien@var{obstack} using the fast growth functions. 46389857Sobrien@end deftypefun 46489857Sobrien 46589857SobrienWhile you know there is room, you can use these fast growth functions 46689857Sobrienfor adding data to a growing object: 46789857Sobrien 46889857Sobrien@comment obstack.h 46989857Sobrien@comment GNU 47089857Sobrien@deftypefun void obstack_1grow_fast (struct obstack *@var{obstack-ptr}, char @var{c}) 47189857SobrienThe function @code{obstack_1grow_fast} adds one byte containing the 47289857Sobriencharacter @var{c} to the growing object in obstack @var{obstack-ptr}. 47389857Sobrien@end deftypefun 47489857Sobrien 47589857Sobrien@comment obstack.h 47689857Sobrien@comment GNU 47789857Sobrien@deftypefun void obstack_ptr_grow_fast (struct obstack *@var{obstack-ptr}, void *@var{data}) 47889857SobrienThe function @code{obstack_ptr_grow_fast} adds @code{sizeof (void *)} 47989857Sobrienbytes containing the value of @var{data} to the growing object in 48089857Sobrienobstack @var{obstack-ptr}. 48189857Sobrien@end deftypefun 48289857Sobrien 48389857Sobrien@comment obstack.h 48489857Sobrien@comment GNU 48589857Sobrien@deftypefun void obstack_int_grow_fast (struct obstack *@var{obstack-ptr}, int @var{data}) 48689857SobrienThe function @code{obstack_int_grow_fast} adds @code{sizeof (int)} bytes 48789857Sobriencontaining the value of @var{data} to the growing object in obstack 48889857Sobrien@var{obstack-ptr}. 48989857Sobrien@end deftypefun 49089857Sobrien 49189857Sobrien@comment obstack.h 49289857Sobrien@comment GNU 49389857Sobrien@deftypefun void obstack_blank_fast (struct obstack *@var{obstack-ptr}, int @var{size}) 49489857SobrienThe function @code{obstack_blank_fast} adds @var{size} bytes to the 49589857Sobriengrowing object in obstack @var{obstack-ptr} without initializing them. 49689857Sobrien@end deftypefun 49789857Sobrien 49889857SobrienWhen you check for space using @code{obstack_room} and there is not 49989857Sobrienenough room for what you want to add, the fast growth functions 50089857Sobrienare not safe. In this case, simply use the corresponding ordinary 50189857Sobriengrowth function instead. Very soon this will copy the object to a 50289857Sobriennew chunk; then there will be lots of room available again. 50389857Sobrien 50489857SobrienSo, each time you use an ordinary growth function, check afterward for 50589857Sobriensufficient space using @code{obstack_room}. Once the object is copied 50689857Sobriento a new chunk, there will be plenty of space again, so the program will 50789857Sobrienstart using the fast growth functions again. 50889857Sobrien 50989857SobrienHere is an example: 51089857Sobrien 51189857Sobrien@smallexample 51289857Sobrien@group 51389857Sobrienvoid 51489857Sobrienadd_string (struct obstack *obstack, const char *ptr, int len) 51589857Sobrien@{ 51689857Sobrien while (len > 0) 51789857Sobrien @{ 51889857Sobrien int room = obstack_room (obstack); 51989857Sobrien if (room == 0) 52089857Sobrien @{ 52189857Sobrien /* @r{Not enough room. Add one character slowly,} 52289857Sobrien @r{which may copy to a new chunk and make room.} */ 52389857Sobrien obstack_1grow (obstack, *ptr++); 52489857Sobrien len--; 52589857Sobrien @} 52689857Sobrien else 52789857Sobrien @{ 52889857Sobrien if (room > len) 52989857Sobrien room = len; 53089857Sobrien /* @r{Add fast as much as we have room for.} */ 53189857Sobrien len -= room; 53289857Sobrien while (room-- > 0) 53389857Sobrien obstack_1grow_fast (obstack, *ptr++); 53489857Sobrien @} 53589857Sobrien @} 53689857Sobrien@} 53789857Sobrien@end group 53889857Sobrien@end smallexample 53989857Sobrien 54089857Sobrien@node Status of an Obstack 54189857Sobrien@section Status of an Obstack 54289857Sobrien@cindex obstack status 54389857Sobrien@cindex status of obstack 54489857Sobrien 54589857SobrienHere are functions that provide information on the current status of 54689857Sobrienallocation in an obstack. You can use them to learn about an object while 54789857Sobrienstill growing it. 54889857Sobrien 54989857Sobrien@comment obstack.h 55089857Sobrien@comment GNU 55189857Sobrien@deftypefun {void *} obstack_base (struct obstack *@var{obstack-ptr}) 55289857SobrienThis function returns the tentative address of the beginning of the 55389857Sobriencurrently growing object in @var{obstack-ptr}. If you finish the object 55489857Sobrienimmediately, it will have that address. If you make it larger first, it 55589857Sobrienmay outgrow the current chunk---then its address will change! 55689857Sobrien 55789857SobrienIf no object is growing, this value says where the next object you 55889857Sobrienallocate will start (once again assuming it fits in the current 55989857Sobrienchunk). 56089857Sobrien@end deftypefun 56189857Sobrien 56289857Sobrien@comment obstack.h 56389857Sobrien@comment GNU 56489857Sobrien@deftypefun {void *} obstack_next_free (struct obstack *@var{obstack-ptr}) 56589857SobrienThis function returns the address of the first free byte in the current 56689857Sobrienchunk of obstack @var{obstack-ptr}. This is the end of the currently 56789857Sobriengrowing object. If no object is growing, @code{obstack_next_free} 56889857Sobrienreturns the same value as @code{obstack_base}. 56989857Sobrien@end deftypefun 57089857Sobrien 57189857Sobrien@comment obstack.h 57289857Sobrien@comment GNU 57389857Sobrien@deftypefun int obstack_object_size (struct obstack *@var{obstack-ptr}) 57489857SobrienThis function returns the size in bytes of the currently growing object. 57589857SobrienThis is equivalent to 57689857Sobrien 57789857Sobrien@smallexample 57889857Sobrienobstack_next_free (@var{obstack-ptr}) - obstack_base (@var{obstack-ptr}) 57989857Sobrien@end smallexample 58089857Sobrien@end deftypefun 58189857Sobrien 58289857Sobrien@node Obstacks Data Alignment 58389857Sobrien@section Alignment of Data in Obstacks 58489857Sobrien@cindex alignment (in obstacks) 58589857Sobrien 58689857SobrienEach obstack has an @dfn{alignment boundary}; each object allocated in 58789857Sobrienthe obstack automatically starts on an address that is a multiple of the 58889857Sobrienspecified boundary. By default, this boundary is 4 bytes. 58989857Sobrien 59089857SobrienTo access an obstack's alignment boundary, use the macro 59189857Sobrien@code{obstack_alignment_mask}, whose function prototype looks like 59289857Sobrienthis: 59389857Sobrien 59489857Sobrien@comment obstack.h 59589857Sobrien@comment GNU 59689857Sobrien@deftypefn Macro int obstack_alignment_mask (struct obstack *@var{obstack-ptr}) 59789857SobrienThe value is a bit mask; a bit that is 1 indicates that the corresponding 59889857Sobrienbit in the address of an object should be 0. The mask value should be one 59989857Sobrienless than a power of 2; the effect is that all object addresses are 60089857Sobrienmultiples of that power of 2. The default value of the mask is 3, so that 60189857Sobrienaddresses are multiples of 4. A mask value of 0 means an object can start 60289857Sobrienon any multiple of 1 (that is, no alignment is required). 60389857Sobrien 60489857SobrienThe expansion of the macro @code{obstack_alignment_mask} is an lvalue, 60589857Sobrienso you can alter the mask by assignment. For example, this statement: 60689857Sobrien 60789857Sobrien@smallexample 60889857Sobrienobstack_alignment_mask (obstack_ptr) = 0; 60989857Sobrien@end smallexample 61089857Sobrien 61189857Sobrien@noindent 61289857Sobrienhas the effect of turning off alignment processing in the specified obstack. 61389857Sobrien@end deftypefn 61489857Sobrien 61589857SobrienNote that a change in alignment mask does not take effect until 61689857Sobrien@emph{after} the next time an object is allocated or finished in the 61789857Sobrienobstack. If you are not growing an object, you can make the new 61889857Sobrienalignment mask take effect immediately by calling @code{obstack_finish}. 61989857SobrienThis will finish a zero-length object and then do proper alignment for 62089857Sobrienthe next object. 62189857Sobrien 62289857Sobrien@node Obstack Chunks 62389857Sobrien@section Obstack Chunks 62489857Sobrien@cindex efficiency of chunks 62589857Sobrien@cindex chunks 62689857Sobrien 62789857SobrienObstacks work by allocating space for themselves in large chunks, and 62889857Sobrienthen parceling out space in the chunks to satisfy your requests. Chunks 62989857Sobrienare normally 4096 bytes long unless you specify a different chunk size. 63089857SobrienThe chunk size includes 8 bytes of overhead that are not actually used 63189857Sobrienfor storing objects. Regardless of the specified size, longer chunks 63289857Sobrienwill be allocated when necessary for long objects. 63389857Sobrien 63489857SobrienThe obstack library allocates chunks by calling the function 63589857Sobrien@code{obstack_chunk_alloc}, which you must define. When a chunk is no 63689857Sobrienlonger needed because you have freed all the objects in it, the obstack 63789857Sobrienlibrary frees the chunk by calling @code{obstack_chunk_free}, which you 63889857Sobrienmust also define. 63989857Sobrien 64089857SobrienThese two must be defined (as macros) or declared (as functions) in each 64189857Sobriensource file that uses @code{obstack_init} (@pxref{Creating Obstacks}). 64289857SobrienMost often they are defined as macros like this: 64389857Sobrien 64489857Sobrien@smallexample 64589857Sobrien#define obstack_chunk_alloc malloc 64689857Sobrien#define obstack_chunk_free free 64789857Sobrien@end smallexample 64889857Sobrien 64989857SobrienNote that these are simple macros (no arguments). Macro definitions with 65089857Sobrienarguments will not work! It is necessary that @code{obstack_chunk_alloc} 65189857Sobrienor @code{obstack_chunk_free}, alone, expand into a function name if it is 65289857Sobriennot itself a function name. 65389857Sobrien 65489857SobrienIf you allocate chunks with @code{malloc}, the chunk size should be a 65589857Sobrienpower of 2. The default chunk size, 4096, was chosen because it is long 65689857Sobrienenough to satisfy many typical requests on the obstack yet short enough 65789857Sobriennot to waste too much memory in the portion of the last chunk not yet used. 65889857Sobrien 65989857Sobrien@comment obstack.h 66089857Sobrien@comment GNU 66189857Sobrien@deftypefn Macro int obstack_chunk_size (struct obstack *@var{obstack-ptr}) 66289857SobrienThis returns the chunk size of the given obstack. 66389857Sobrien@end deftypefn 66489857Sobrien 66589857SobrienSince this macro expands to an lvalue, you can specify a new chunk size by 66689857Sobrienassigning it a new value. Doing so does not affect the chunks already 66789857Sobrienallocated, but will change the size of chunks allocated for that particular 66889857Sobrienobstack in the future. It is unlikely to be useful to make the chunk size 66989857Sobriensmaller, but making it larger might improve efficiency if you are 67089857Sobrienallocating many objects whose size is comparable to the chunk size. Here 67189857Sobrienis how to do so cleanly: 67289857Sobrien 67389857Sobrien@smallexample 67489857Sobrienif (obstack_chunk_size (obstack_ptr) < @var{new-chunk-size}) 67589857Sobrien obstack_chunk_size (obstack_ptr) = @var{new-chunk-size}; 67689857Sobrien@end smallexample 67789857Sobrien 67889857Sobrien@node Summary of Obstacks 67989857Sobrien@section Summary of Obstack Functions 68089857Sobrien 68189857SobrienHere is a summary of all the functions associated with obstacks. Each 68289857Sobrientakes the address of an obstack (@code{struct obstack *}) as its first 68389857Sobrienargument. 68489857Sobrien 68589857Sobrien@table @code 68689857Sobrien@item void obstack_init (struct obstack *@var{obstack-ptr}) 68789857SobrienInitialize use of an obstack. @xref{Creating Obstacks}. 68889857Sobrien 68989857Sobrien@item void *obstack_alloc (struct obstack *@var{obstack-ptr}, int @var{size}) 69089857SobrienAllocate an object of @var{size} uninitialized bytes. 69189857Sobrien@xref{Allocation in an Obstack}. 69289857Sobrien 69389857Sobrien@item void *obstack_copy (struct obstack *@var{obstack-ptr}, void *@var{address}, int @var{size}) 69489857SobrienAllocate an object of @var{size} bytes, with contents copied from 69589857Sobrien@var{address}. @xref{Allocation in an Obstack}. 69689857Sobrien 69789857Sobrien@item void *obstack_copy0 (struct obstack *@var{obstack-ptr}, void *@var{address}, int @var{size}) 69889857SobrienAllocate an object of @var{size}+1 bytes, with @var{size} of them copied 69989857Sobrienfrom @var{address}, followed by a null character at the end. 70089857Sobrien@xref{Allocation in an Obstack}. 70189857Sobrien 70289857Sobrien@item void obstack_free (struct obstack *@var{obstack-ptr}, void *@var{object}) 70389857SobrienFree @var{object} (and everything allocated in the specified obstack 70489857Sobrienmore recently than @var{object}). @xref{Freeing Obstack Objects}. 70589857Sobrien 70689857Sobrien@item void obstack_blank (struct obstack *@var{obstack-ptr}, int @var{size}) 70789857SobrienAdd @var{size} uninitialized bytes to a growing object. 70889857Sobrien@xref{Growing Objects}. 70989857Sobrien 71089857Sobrien@item void obstack_grow (struct obstack *@var{obstack-ptr}, void *@var{address}, int @var{size}) 71189857SobrienAdd @var{size} bytes, copied from @var{address}, to a growing object. 71289857Sobrien@xref{Growing Objects}. 71389857Sobrien 71489857Sobrien@item void obstack_grow0 (struct obstack *@var{obstack-ptr}, void *@var{address}, int @var{size}) 71589857SobrienAdd @var{size} bytes, copied from @var{address}, to a growing object, 71689857Sobrienand then add another byte containing a null character. @xref{Growing 71789857SobrienObjects}. 71889857Sobrien 71989857Sobrien@item void obstack_1grow (struct obstack *@var{obstack-ptr}, char @var{data-char}) 72089857SobrienAdd one byte containing @var{data-char} to a growing object. 72189857Sobrien@xref{Growing Objects}. 72289857Sobrien 72389857Sobrien@item void *obstack_finish (struct obstack *@var{obstack-ptr}) 72489857SobrienFinalize the object that is growing and return its permanent address. 72589857Sobrien@xref{Growing Objects}. 72689857Sobrien 72789857Sobrien@item int obstack_object_size (struct obstack *@var{obstack-ptr}) 72889857SobrienGet the current size of the currently growing object. @xref{Growing 72989857SobrienObjects}. 73089857Sobrien 73189857Sobrien@item void obstack_blank_fast (struct obstack *@var{obstack-ptr}, int @var{size}) 73289857SobrienAdd @var{size} uninitialized bytes to a growing object without checking 73389857Sobrienthat there is enough room. @xref{Extra Fast Growing}. 73489857Sobrien 73589857Sobrien@item void obstack_1grow_fast (struct obstack *@var{obstack-ptr}, char @var{data-char}) 73689857SobrienAdd one byte containing @var{data-char} to a growing object without 73789857Sobrienchecking that there is enough room. @xref{Extra Fast Growing}. 73889857Sobrien 73989857Sobrien@item int obstack_room (struct obstack *@var{obstack-ptr}) 74089857SobrienGet the amount of room now available for growing the current object. 74189857Sobrien@xref{Extra Fast Growing}. 74289857Sobrien 74389857Sobrien@item int obstack_alignment_mask (struct obstack *@var{obstack-ptr}) 74489857SobrienThe mask used for aligning the beginning of an object. This is an 74589857Sobrienlvalue. @xref{Obstacks Data Alignment}. 74689857Sobrien 74789857Sobrien@item int obstack_chunk_size (struct obstack *@var{obstack-ptr}) 74889857SobrienThe size for allocating chunks. This is an lvalue. @xref{Obstack Chunks}. 74989857Sobrien 75089857Sobrien@item void *obstack_base (struct obstack *@var{obstack-ptr}) 75189857SobrienTentative starting address of the currently growing object. 75289857Sobrien@xref{Status of an Obstack}. 75389857Sobrien 75489857Sobrien@item void *obstack_next_free (struct obstack *@var{obstack-ptr}) 75589857SobrienAddress just after the end of the currently growing object. 75689857Sobrien@xref{Status of an Obstack}. 75789857Sobrien@end table 75889857Sobrien 759