Back to index

glibc  2.9
obstack.h
Go to the documentation of this file.
00001 /* obstack.h - object stack macros
00002    Copyright (C) 1988-1994,1996-1999,2003,2004,2005
00003        Free Software Foundation, Inc.
00004    This file is part of the GNU C Library.
00005 
00006    The GNU C Library is free software; you can redistribute it and/or
00007    modify it under the terms of the GNU Lesser General Public
00008    License as published by the Free Software Foundation; either
00009    version 2.1 of the License, or (at your option) any later version.
00010 
00011    The GNU C Library is distributed in the hope that it will be useful,
00012    but WITHOUT ANY WARRANTY; without even the implied warranty of
00013    MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
00014    Lesser General Public License for more details.
00015 
00016    You should have received a copy of the GNU Lesser General Public
00017    License along with the GNU C Library; if not, write to the Free
00018    Software Foundation, Inc., 51 Franklin Street, Fifth Floor,
00019    Boston, MA 02110-1301, USA.  */
00020 
00021 /* Summary:
00022 
00023 All the apparent functions defined here are macros. The idea
00024 is that you would use these pre-tested macros to solve a
00025 very specific set of problems, and they would run fast.
00026 Caution: no side-effects in arguments please!! They may be
00027 evaluated MANY times!!
00028 
00029 These macros operate a stack of objects.  Each object starts life
00030 small, and may grow to maturity.  (Consider building a word syllable
00031 by syllable.)  An object can move while it is growing.  Once it has
00032 been "finished" it never changes address again.  So the "top of the
00033 stack" is typically an immature growing object, while the rest of the
00034 stack is of mature, fixed size and fixed address objects.
00035 
00036 These routines grab large chunks of memory, using a function you
00037 supply, called `obstack_chunk_alloc'.  On occasion, they free chunks,
00038 by calling `obstack_chunk_free'.  You must define them and declare
00039 them before using any obstack macros.
00040 
00041 Each independent stack is represented by a `struct obstack'.
00042 Each of the obstack macros expects a pointer to such a structure
00043 as the first argument.
00044 
00045 One motivation for this package is the problem of growing char strings
00046 in symbol tables.  Unless you are "fascist pig with a read-only mind"
00047 --Gosper's immortal quote from HAKMEM item 154, out of context--you
00048 would not like to put any arbitrary upper limit on the length of your
00049 symbols.
00050 
00051 In practice this often means you will build many short symbols and a
00052 few long symbols.  At the time you are reading a symbol you don't know
00053 how long it is.  One traditional method is to read a symbol into a
00054 buffer, realloc()ating the buffer every time you try to read a symbol
00055 that is longer than the buffer.  This is beaut, but you still will
00056 want to copy the symbol from the buffer to a more permanent
00057 symbol-table entry say about half the time.
00058 
00059 With obstacks, you can work differently.  Use one obstack for all symbol
00060 names.  As you read a symbol, grow the name in the obstack gradually.
00061 When the name is complete, finalize it.  Then, if the symbol exists already,
00062 free the newly read name.
00063 
00064 The way we do this is to take a large chunk, allocating memory from
00065 low addresses.  When you want to build a symbol in the chunk you just
00066 add chars above the current "high water mark" in the chunk.  When you
00067 have finished adding chars, because you got to the end of the symbol,
00068 you know how long the chars are, and you can create a new object.
00069 Mostly the chars will not burst over the highest address of the chunk,
00070 because you would typically expect a chunk to be (say) 100 times as
00071 long as an average object.
00072 
00073 In case that isn't clear, when we have enough chars to make up
00074 the object, THEY ARE ALREADY CONTIGUOUS IN THE CHUNK (guaranteed)
00075 so we just point to it where it lies.  No moving of chars is
00076 needed and this is the second win: potentially long strings need
00077 never be explicitly shuffled. Once an object is formed, it does not
00078 change its address during its lifetime.
00079 
00080 When the chars burst over a chunk boundary, we allocate a larger
00081 chunk, and then copy the partly formed object from the end of the old
00082 chunk to the beginning of the new larger chunk.  We then carry on
00083 accreting characters to the end of the object as we normally would.
00084 
00085 A special macro is provided to add a single char at a time to a
00086 growing object.  This allows the use of register variables, which
00087 break the ordinary 'growth' macro.
00088 
00089 Summary:
00090        We allocate large chunks.
00091        We carve out one object at a time from the current chunk.
00092        Once carved, an object never moves.
00093        We are free to append data of any size to the currently
00094          growing object.
00095        Exactly one object is growing in an obstack at any one time.
00096        You can run one obstack per control block.
00097        You may have as many control blocks as you dare.
00098        Because of the way we do it, you can `unwind' an obstack
00099          back to a previous state. (You may remove objects much
00100          as you would with a stack.)
00101 */
00102 
00103 
00104 /* Don't do the contents of this file more than once.  */
00105 
00106 #ifndef _OBSTACK_H
00107 #define _OBSTACK_H 1
00108 
00109 #ifdef __cplusplus
00110 extern "C" {
00111 #endif
00112 
00113 /* We need the type of a pointer subtraction.  If __PTRDIFF_TYPE__ is
00114    defined, as with GNU C, use that; that way we don't pollute the
00115    namespace with <stddef.h>'s symbols.  Otherwise, include <stddef.h>
00116    and use ptrdiff_t.  */
00117 
00118 #ifdef __PTRDIFF_TYPE__
00119 # define PTR_INT_TYPE __PTRDIFF_TYPE__
00120 #else
00121 # include <stddef.h>
00122 # define PTR_INT_TYPE ptrdiff_t
00123 #endif
00124 
00125 /* If B is the base of an object addressed by P, return the result of
00126    aligning P to the next multiple of A + 1.  B and P must be of type
00127    char *.  A + 1 must be a power of 2.  */
00128 
00129 #define __BPTR_ALIGN(B, P, A) ((B) + (((P) - (B) + (A)) & ~(A)))
00130 
00131 /* Similiar to _BPTR_ALIGN (B, P, A), except optimize the common case
00132    where pointers can be converted to integers, aligned as integers,
00133    and converted back again.  If PTR_INT_TYPE is narrower than a
00134    pointer (e.g., the AS/400), play it safe and compute the alignment
00135    relative to B.  Otherwise, use the faster strategy of computing the
00136    alignment relative to 0.  */
00137 
00138 #define __PTR_ALIGN(B, P, A)                                              \
00139   __BPTR_ALIGN (sizeof (PTR_INT_TYPE) < sizeof (void *) ? (B) : (char *) 0, \
00140               P, A)
00141 
00142 #include <string.h>
00143 
00144 struct _obstack_chunk              /* Lives at front of each chunk. */
00145 {
00146   char  *limit;                    /* 1 past end of this chunk */
00147   struct _obstack_chunk *prev;     /* address of prior chunk or NULL */
00148   char contents[4];         /* objects begin here */
00149 };
00150 
00151 struct obstack              /* control current object in current chunk */
00152 {
00153   long chunk_size;          /* preferred size to allocate chunks in */
00154   struct _obstack_chunk *chunk;    /* address of current struct obstack_chunk */
00155   char *object_base;        /* address of object we are building */
00156   char *next_free;          /* where to add next char to current object */
00157   char *chunk_limit;        /* address of char after current chunk */
00158   union
00159   {
00160     PTR_INT_TYPE tempint;
00161     void *tempptr;
00162   } temp;                   /* Temporary for some macros.  */
00163   int   alignment_mask;            /* Mask of alignment for each object. */
00164   /* These prototypes vary based on `use_extra_arg', and we use
00165      casts to the prototypeless function type in all assignments,
00166      but having prototypes here quiets -Wstrict-prototypes.  */
00167   struct _obstack_chunk *(*chunkfun) (void *, long);
00168   void (*freefun) (void *, struct _obstack_chunk *);
00169   void *extra_arg;          /* first arg for chunk alloc/dealloc funcs */
00170   unsigned use_extra_arg:1; /* chunk alloc/dealloc funcs take extra arg */
00171   unsigned maybe_empty_object:1;/* There is a possibility that the current
00172                                chunk contains a zero-length object.  This
00173                                prevents freeing the chunk if we allocate
00174                                a bigger chunk to replace it. */
00175   unsigned alloc_failed:1;  /* No longer used, as we now call the failed
00176                                handler on error, but retained for binary
00177                                compatibility.  */
00178 };
00179 
00180 /* Declare the external functions we use; they are in obstack.c.  */
00181 
00182 extern void _obstack_newchunk (struct obstack *, int);
00183 extern int _obstack_begin (struct obstack *, int, int,
00184                          void *(*) (long), void (*) (void *));
00185 extern int _obstack_begin_1 (struct obstack *, int, int,
00186                           void *(*) (void *, long),
00187                           void (*) (void *, void *), void *);
00188 extern int _obstack_memory_used (struct obstack *);
00189 
00190 void obstack_free (struct obstack *obstack, void *block);
00191 
00192 
00193 /* Error handler called when `obstack_chunk_alloc' failed to allocate
00194    more memory.  This can be set to a user defined function which
00195    should either abort gracefully or use longjump - but shouldn't
00196    return.  The default action is to print a message and abort.  */
00197 extern void (*obstack_alloc_failed_handler) (void);
00198 
00199 /* Exit value used when `print_and_abort' is used.  */
00200 extern int obstack_exit_failure;
00201 
00202 /* Pointer to beginning of object being allocated or to be allocated next.
00203    Note that this might not be the final address of the object
00204    because a new chunk might be needed to hold the final size.  */
00205 
00206 #define obstack_base(h) ((void *) (h)->object_base)
00207 
00208 /* Size for allocating ordinary chunks.  */
00209 
00210 #define obstack_chunk_size(h) ((h)->chunk_size)
00211 
00212 /* Pointer to next byte not yet allocated in current chunk.  */
00213 
00214 #define obstack_next_free(h)       ((h)->next_free)
00215 
00216 /* Mask specifying low bits that should be clear in address of an object.  */
00217 
00218 #define obstack_alignment_mask(h) ((h)->alignment_mask)
00219 
00220 /* To prevent prototype warnings provide complete argument list.  */
00221 #define obstack_init(h)                                        \
00222   _obstack_begin ((h), 0, 0,                                   \
00223                 (void *(*) (long)) obstack_chunk_alloc, \
00224                 (void (*) (void *)) obstack_chunk_free)
00225 
00226 #define obstack_begin(h, size)                                 \
00227   _obstack_begin ((h), (size), 0,                       \
00228                 (void *(*) (long)) obstack_chunk_alloc, \
00229                 (void (*) (void *)) obstack_chunk_free)
00230 
00231 #define obstack_specify_allocation(h, size, alignment, chunkfun, freefun)  \
00232   _obstack_begin ((h), (size), (alignment),                              \
00233                 (void *(*) (long)) (chunkfun),                    \
00234                 (void (*) (void *)) (freefun))
00235 
00236 #define obstack_specify_allocation_with_arg(h, size, alignment, chunkfun, freefun, arg) \
00237   _obstack_begin_1 ((h), (size), (alignment),                         \
00238                   (void *(*) (void *, long)) (chunkfun),              \
00239                   (void (*) (void *, void *)) (freefun), (arg))
00240 
00241 #define obstack_chunkfun(h, newchunkfun) \
00242   ((h) -> chunkfun = (struct _obstack_chunk *(*)(void *, long)) (newchunkfun))
00243 
00244 #define obstack_freefun(h, newfreefun) \
00245   ((h) -> freefun = (void (*)(void *, struct _obstack_chunk *)) (newfreefun))
00246 
00247 #define obstack_1grow_fast(h,achar) (*((h)->next_free)++ = (achar))
00248 
00249 #define obstack_blank_fast(h,n) ((h)->next_free += (n))
00250 
00251 #define obstack_memory_used(h) _obstack_memory_used (h)
00252 
00253 #if defined __GNUC__ && defined __STDC__ && __STDC__
00254 /* NextStep 2.0 cc is really gcc 1.93 but it defines __GNUC__ = 2 and
00255    does not implement __extension__.  But that compiler doesn't define
00256    __GNUC_MINOR__.  */
00257 # if __GNUC__ < 2 || (__NeXT__ && !__GNUC_MINOR__)
00258 #  define __extension__
00259 # endif
00260 
00261 /* For GNU C, if not -traditional,
00262    we can define these macros to compute all args only once
00263    without using a global variable.
00264    Also, we can avoid using the `temp' slot, to make faster code.  */
00265 
00266 # define obstack_object_size(OBSTACK)                                 \
00267   __extension__                                                       \
00268   ({ struct obstack const *__o = (OBSTACK);                           \
00269      (unsigned) (__o->next_free - __o->object_base); })
00270 
00271 # define obstack_room(OBSTACK)                                        \
00272   __extension__                                                       \
00273   ({ struct obstack const *__o = (OBSTACK);                           \
00274      (unsigned) (__o->chunk_limit - __o->next_free); })
00275 
00276 # define obstack_make_room(OBSTACK,length)                            \
00277 __extension__                                                  \
00278 ({ struct obstack *__o = (OBSTACK);                                   \
00279    int __len = (length);                                       \
00280    if (__o->chunk_limit - __o->next_free < __len)                     \
00281      _obstack_newchunk (__o, __len);                                  \
00282    (void) 0; })
00283 
00284 # define obstack_empty_p(OBSTACK)                              \
00285   __extension__                                                       \
00286   ({ struct obstack const *__o = (OBSTACK);                           \
00287      (__o->chunk->prev == 0                                    \
00288       && __o->next_free == __PTR_ALIGN ((char *) __o->chunk,          \
00289                                    __o->chunk->contents,              \
00290                                    __o->alignment_mask)); })
00291 
00292 # define obstack_grow(OBSTACK,where,length)                           \
00293 __extension__                                                  \
00294 ({ struct obstack *__o = (OBSTACK);                                   \
00295    int __len = (length);                                       \
00296    if (__o->next_free + __len > __o->chunk_limit)                     \
00297      _obstack_newchunk (__o, __len);                                  \
00298    memcpy (__o->next_free, where, __len);                      \
00299    __o->next_free += __len;                                    \
00300    (void) 0; })
00301 
00302 # define obstack_grow0(OBSTACK,where,length)                          \
00303 __extension__                                                  \
00304 ({ struct obstack *__o = (OBSTACK);                                   \
00305    int __len = (length);                                       \
00306    if (__o->next_free + __len + 1 > __o->chunk_limit)                 \
00307      _obstack_newchunk (__o, __len + 1);                       \
00308    memcpy (__o->next_free, where, __len);                      \
00309    __o->next_free += __len;                                    \
00310    *(__o->next_free)++ = 0;                                    \
00311    (void) 0; })
00312 
00313 # define obstack_1grow(OBSTACK,datum)                                 \
00314 __extension__                                                  \
00315 ({ struct obstack *__o = (OBSTACK);                                   \
00316    if (__o->next_free + 1 > __o->chunk_limit)                         \
00317      _obstack_newchunk (__o, 1);                               \
00318    obstack_1grow_fast (__o, datum);                                   \
00319    (void) 0; })
00320 
00321 /* These assume that the obstack alignment is good enough for pointers
00322    or ints, and that the data added so far to the current object
00323    shares that much alignment.  */
00324 
00325 # define obstack_ptr_grow(OBSTACK,datum)                       \
00326 __extension__                                                  \
00327 ({ struct obstack *__o = (OBSTACK);                                   \
00328    if (__o->next_free + sizeof (void *) > __o->chunk_limit)           \
00329      _obstack_newchunk (__o, sizeof (void *));                        \
00330    obstack_ptr_grow_fast (__o, datum); })                      \
00331 
00332 # define obstack_int_grow(OBSTACK,datum)                       \
00333 __extension__                                                  \
00334 ({ struct obstack *__o = (OBSTACK);                                   \
00335    if (__o->next_free + sizeof (int) > __o->chunk_limit)              \
00336      _obstack_newchunk (__o, sizeof (int));                           \
00337    obstack_int_grow_fast (__o, datum); })
00338 
00339 # define obstack_ptr_grow_fast(OBSTACK,aptr)                          \
00340 __extension__                                                  \
00341 ({ struct obstack *__o1 = (OBSTACK);                                  \
00342    *(const void **) __o1->next_free = (aptr);                         \
00343    __o1->next_free += sizeof (const void *);                          \
00344    (void) 0; })
00345 
00346 # define obstack_int_grow_fast(OBSTACK,aint)                          \
00347 __extension__                                                  \
00348 ({ struct obstack *__o1 = (OBSTACK);                                  \
00349    *(int *) __o1->next_free = (aint);                                 \
00350    __o1->next_free += sizeof (int);                                   \
00351    (void) 0; })
00352 
00353 # define obstack_blank(OBSTACK,length)                                \
00354 __extension__                                                  \
00355 ({ struct obstack *__o = (OBSTACK);                                   \
00356    int __len = (length);                                       \
00357    if (__o->chunk_limit - __o->next_free < __len)                     \
00358      _obstack_newchunk (__o, __len);                                  \
00359    obstack_blank_fast (__o, __len);                                   \
00360    (void) 0; })
00361 
00362 # define obstack_alloc(OBSTACK,length)                                \
00363 __extension__                                                  \
00364 ({ struct obstack *__h = (OBSTACK);                                   \
00365    obstack_blank (__h, (length));                              \
00366    obstack_finish (__h); })
00367 
00368 # define obstack_copy(OBSTACK,where,length)                           \
00369 __extension__                                                  \
00370 ({ struct obstack *__h = (OBSTACK);                                   \
00371    obstack_grow (__h, (where), (length));                      \
00372    obstack_finish (__h); })
00373 
00374 # define obstack_copy0(OBSTACK,where,length)                          \
00375 __extension__                                                  \
00376 ({ struct obstack *__h = (OBSTACK);                                   \
00377    obstack_grow0 (__h, (where), (length));                            \
00378    obstack_finish (__h); })
00379 
00380 /* The local variable is named __o1 to avoid a name conflict
00381    when obstack_blank is called.  */
00382 # define obstack_finish(OBSTACK)                               \
00383 __extension__                                                  \
00384 ({ struct obstack *__o1 = (OBSTACK);                                  \
00385    void *__value = (void *) __o1->object_base;                        \
00386    if (__o1->next_free == __value)                             \
00387      __o1->maybe_empty_object = 1;                             \
00388    __o1->next_free                                             \
00389      = __PTR_ALIGN (__o1->object_base, __o1->next_free,               \
00390                   __o1->alignment_mask);                       \
00391    if (__o1->next_free - (char *)__o1->chunk                          \
00392        > __o1->chunk_limit - (char *)__o1->chunk)                     \
00393      __o1->next_free = __o1->chunk_limit;                      \
00394    __o1->object_base = __o1->next_free;                               \
00395    __value; })
00396 
00397 # define obstack_free(OBSTACK, OBJ)                                   \
00398 __extension__                                                  \
00399 ({ struct obstack *__o = (OBSTACK);                                   \
00400    void *__obj = (OBJ);                                               \
00401    if (__obj > (void *)__o->chunk && __obj < (void *)__o->chunk_limit)  \
00402      __o->next_free = __o->object_base = (char *)__obj;               \
00403    else (obstack_free) (__o, __obj); })
00404 
00405 #else /* not __GNUC__ or not __STDC__ */
00406 
00407 # define obstack_object_size(h) \
00408  (unsigned) ((h)->next_free - (h)->object_base)
00409 
00410 # define obstack_room(h)           \
00411  (unsigned) ((h)->chunk_limit - (h)->next_free)
00412 
00413 # define obstack_empty_p(h) \
00414  ((h)->chunk->prev == 0                                               \
00415   && (h)->next_free == __PTR_ALIGN ((char *) (h)->chunk,              \
00416                                 (h)->chunk->contents,          \
00417                                 (h)->alignment_mask))
00418 
00419 /* Note that the call to _obstack_newchunk is enclosed in (..., 0)
00420    so that we can avoid having void expressions
00421    in the arms of the conditional expression.
00422    Casting the third operand to void was tried before,
00423    but some compilers won't accept it.  */
00424 
00425 # define obstack_make_room(h,length)                                  \
00426 ( (h)->temp.tempint = (length),                                       \
00427   (((h)->next_free + (h)->temp.tempint > (h)->chunk_limit)            \
00428    ? (_obstack_newchunk ((h), (h)->temp.tempint), 0) : 0))
00429 
00430 # define obstack_grow(h,where,length)                                 \
00431 ( (h)->temp.tempint = (length),                                       \
00432   (((h)->next_free + (h)->temp.tempint > (h)->chunk_limit)            \
00433    ? (_obstack_newchunk ((h), (h)->temp.tempint), 0) : 0),            \
00434   memcpy ((h)->next_free, where, (h)->temp.tempint),                  \
00435   (h)->next_free += (h)->temp.tempint)
00436 
00437 # define obstack_grow0(h,where,length)                                \
00438 ( (h)->temp.tempint = (length),                                       \
00439   (((h)->next_free + (h)->temp.tempint + 1 > (h)->chunk_limit)        \
00440    ? (_obstack_newchunk ((h), (h)->temp.tempint + 1), 0) : 0),        \
00441   memcpy ((h)->next_free, where, (h)->temp.tempint),                  \
00442   (h)->next_free += (h)->temp.tempint,                                \
00443   *((h)->next_free)++ = 0)
00444 
00445 # define obstack_1grow(h,datum)                                       \
00446 ( (((h)->next_free + 1 > (h)->chunk_limit)                            \
00447    ? (_obstack_newchunk ((h), 1), 0) : 0),                            \
00448   obstack_1grow_fast (h, datum))
00449 
00450 # define obstack_ptr_grow(h,datum)                             \
00451 ( (((h)->next_free + sizeof (char *) > (h)->chunk_limit)              \
00452    ? (_obstack_newchunk ((h), sizeof (char *)), 0) : 0),              \
00453   obstack_ptr_grow_fast (h, datum))
00454 
00455 # define obstack_int_grow(h,datum)                             \
00456 ( (((h)->next_free + sizeof (int) > (h)->chunk_limit)                 \
00457    ? (_obstack_newchunk ((h), sizeof (int)), 0) : 0),                 \
00458   obstack_int_grow_fast (h, datum))
00459 
00460 # define obstack_ptr_grow_fast(h,aptr)                                \
00461   (((const void **) ((h)->next_free += sizeof (void *)))[-1] = (aptr))
00462 
00463 # define obstack_int_grow_fast(h,aint)                                \
00464   (((int *) ((h)->next_free += sizeof (int)))[-1] = (aint))
00465 
00466 # define obstack_blank(h,length)                               \
00467 ( (h)->temp.tempint = (length),                                       \
00468   (((h)->chunk_limit - (h)->next_free < (h)->temp.tempint)            \
00469    ? (_obstack_newchunk ((h), (h)->temp.tempint), 0) : 0),            \
00470   obstack_blank_fast (h, (h)->temp.tempint))
00471 
00472 # define obstack_alloc(h,length)                               \
00473  (obstack_blank ((h), (length)), obstack_finish ((h)))
00474 
00475 # define obstack_copy(h,where,length)                                 \
00476  (obstack_grow ((h), (where), (length)), obstack_finish ((h)))
00477 
00478 # define obstack_copy0(h,where,length)                                \
00479  (obstack_grow0 ((h), (where), (length)), obstack_finish ((h)))
00480 
00481 # define obstack_finish(h)                                     \
00482 ( ((h)->next_free == (h)->object_base                                 \
00483    ? (((h)->maybe_empty_object = 1), 0)                               \
00484    : 0),                                                       \
00485   (h)->temp.tempptr = (h)->object_base,                               \
00486   (h)->next_free                                               \
00487     = __PTR_ALIGN ((h)->object_base, (h)->next_free,                  \
00488                  (h)->alignment_mask),                         \
00489   (((h)->next_free - (char *) (h)->chunk                       \
00490     > (h)->chunk_limit - (char *) (h)->chunk)                         \
00491    ? ((h)->next_free = (h)->chunk_limit) : 0),                        \
00492   (h)->object_base = (h)->next_free,                                  \
00493   (h)->temp.tempptr)
00494 
00495 # define obstack_free(h,obj)                                          \
00496 ( (h)->temp.tempint = (char *) (obj) - (char *) (h)->chunk,           \
00497   ((((h)->temp.tempint > 0                                     \
00498     && (h)->temp.tempint < (h)->chunk_limit - (char *) (h)->chunk))   \
00499    ? (int) ((h)->next_free = (h)->object_base                         \
00500            = (h)->temp.tempint + (char *) (h)->chunk)                 \
00501    : (((obstack_free) ((h), (h)->temp.tempint + (char *) (h)->chunk), 0), 0)))
00502 
00503 #endif /* not __GNUC__ or not __STDC__ */
00504 
00505 #ifdef __cplusplus
00506 }      /* C++ */
00507 #endif
00508 
00509 #endif /* obstack.h */