1 /* obstack.h - object stack macros
2    Copyright (C) 1988-2016 Free Software Foundation, Inc.
3    This file is part of the GNU C Library.
4 
5    The GNU C Library is free software; you can redistribute it and/or
6    modify it under the terms of the GNU Lesser General Public
7    License as published by the Free Software Foundation; either
8    version 2.1 of the License, or (at your option) any later version.
9 
10    The GNU C Library is distributed in the hope that it will be useful,
11    but WITHOUT ANY WARRANTY; without even the implied warranty of
12    MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
13    Lesser General Public License for more details.
14 
15    You should have received a copy of the GNU Lesser General Public
16    License along with the GNU C Library; if not, see
17    <http://www.gnu.org/licenses/>.  */
18 
19 /* Summary:
20 
21    All the apparent functions defined here are macros. The idea
22    is that you would use these pre-tested macros to solve a
23    very specific set of problems, and they would run fast.
24    Caution: no side-effects in arguments please!! They may be
25    evaluated MANY times!!
26 
27    These macros operate a stack of objects.  Each object starts life
28    small, and may grow to maturity.  (Consider building a word syllable
29    by syllable.)  An object can move while it is growing.  Once it has
30    been "finished" it never changes address again.  So the "top of the
31    stack" is typically an immature growing object, while the rest of the
32    stack is of mature, fixed size and fixed address objects.
33 
34    These routines grab large chunks of memory, using a function you
35    supply, called 'obstack_chunk_alloc'.  On occasion, they free chunks,
36    by calling 'obstack_chunk_free'.  You must define them and declare
37    them before using any obstack macros.
38 
39    Each independent stack is represented by a 'struct obstack'.
40    Each of the obstack macros expects a pointer to such a structure
41    as the first argument.
42 
43    One motivation for this package is the problem of growing char strings
44    in symbol tables.  Unless you are "fascist pig with a read-only mind"
45    --Gosper's immortal quote from HAKMEM item 154, out of context--you
46    would not like to put any arbitrary upper limit on the length of your
47    symbols.
48 
49    In practice this often means you will build many short symbols and a
50    few long symbols.  At the time you are reading a symbol you don't know
51    how long it is.  One traditional method is to read a symbol into a
52    buffer, realloc()ating the buffer every time you try to read a symbol
53    that is longer than the buffer.  This is beaut, but you still will
54    want to copy the symbol from the buffer to a more permanent
55    symbol-table entry say about half the time.
56 
57    With obstacks, you can work differently.  Use one obstack for all symbol
58    names.  As you read a symbol, grow the name in the obstack gradually.
59    When the name is complete, finalize it.  Then, if the symbol exists already,
60    free the newly read name.
61 
62    The way we do this is to take a large chunk, allocating memory from
63    low addresses.  When you want to build a symbol in the chunk you just
64    add chars above the current "high water mark" in the chunk.  When you
65    have finished adding chars, because you got to the end of the symbol,
66    you know how long the chars are, and you can create a new object.
67    Mostly the chars will not burst over the highest address of the chunk,
68    because you would typically expect a chunk to be (say) 100 times as
69    long as an average object.
70 
71    In case that isn't clear, when we have enough chars to make up
72    the object, THEY ARE ALREADY CONTIGUOUS IN THE CHUNK (guaranteed)
73    so we just point to it where it lies.  No moving of chars is
74    needed and this is the second win: potentially long strings need
75    never be explicitly shuffled. Once an object is formed, it does not
76    change its address during its lifetime.
77 
78    When the chars burst over a chunk boundary, we allocate a larger
79    chunk, and then copy the partly formed object from the end of the old
80    chunk to the beginning of the new larger chunk.  We then carry on
81    accreting characters to the end of the object as we normally would.
82 
83    A special macro is provided to add a single char at a time to a
84    growing object.  This allows the use of register variables, which
85    break the ordinary 'growth' macro.
86 
87    Summary:
88         We allocate large chunks.
89         We carve out one object at a time from the current chunk.
90         Once carved, an object never moves.
91         We are free to append data of any size to the currently
92           growing object.
93         Exactly one object is growing in an obstack at any one time.
94         You can run one obstack per control block.
95         You may have as many control blocks as you dare.
96         Because of the way we do it, you can "unwind" an obstack
97           back to a previous state. (You may remove objects much
98           as you would with a stack.)
99  */
100 
101 
102 /* Don't do the contents of this file more than once.  */
103 
104 #ifndef _OBSTACK_H
105 #define _OBSTACK_H 1
106 
107 #ifndef _OBSTACK_INTERFACE_VERSION
108 # define _OBSTACK_INTERFACE_VERSION 2
109 #endif
110 
111 #include <stddef.h>             /* For size_t and ptrdiff_t.  */
112 #include <string.h>             /* For __GNU_LIBRARY__, and memcpy.  */
113 
114 #if _OBSTACK_INTERFACE_VERSION == 1
115 /* For binary compatibility with obstack version 1, which used "int"
116    and "long" for these two types.  */
117 # define _OBSTACK_SIZE_T unsigned int
118 # define _CHUNK_SIZE_T unsigned long
119 # define _OBSTACK_CAST(type, expr) ((type) (expr))
120 #else
121 /* Version 2 with sane types, especially for 64-bit hosts.  */
122 # define _OBSTACK_SIZE_T size_t
123 # define _CHUNK_SIZE_T size_t
124 # define _OBSTACK_CAST(type, expr) (expr)
125 #endif
126 
127 /* If B is the base of an object addressed by P, return the result of
128    aligning P to the next multiple of A + 1.  B and P must be of type
129    char *.  A + 1 must be a power of 2.  */
130 
131 #define __BPTR_ALIGN(B, P, A) ((B) + (((P) - (B) + (A)) & ~(A)))
132 
133 /* Similar to __BPTR_ALIGN (B, P, A), except optimize the common case
134    where pointers can be converted to integers, aligned as integers,
135    and converted back again.  If ptrdiff_t is narrower than a
136    pointer (e.g., the AS/400), play it safe and compute the alignment
137    relative to B.  Otherwise, use the faster strategy of computing the
138    alignment relative to 0.  */
139 
140 #define __PTR_ALIGN(B, P, A)						      \
141   __BPTR_ALIGN (sizeof (ptrdiff_t) < sizeof (void *) ? (B) : (char *) 0,      \
142                 P, A)
143 
144 #ifndef __attribute_pure__
145 # if defined __GNUC_MINOR__ && __GNUC__ * 1000 + __GNUC_MINOR__ >= 2096
146 #  define __attribute_pure__ __attribute__ ((__pure__))
147 # else
148 #  define __attribute_pure__
149 # endif
150 #endif
151 
152 #ifdef __cplusplus
153 extern "C" {
154 #endif
155 
156 struct _obstack_chunk           /* Lives at front of each chunk. */
157 {
158   char *limit;                  /* 1 past end of this chunk */
159   struct _obstack_chunk *prev;  /* address of prior chunk or NULL */
160   char contents[4];             /* objects begin here */
161 };
162 
163 struct obstack          /* control current object in current chunk */
164 {
165   _CHUNK_SIZE_T chunk_size;     /* preferred size to allocate chunks in */
166   struct _obstack_chunk *chunk; /* address of current struct obstack_chunk */
167   char *object_base;            /* address of object we are building */
168   char *next_free;              /* where to add next char to current object */
169   char *chunk_limit;            /* address of char after current chunk */
170   union
171   {
172     _OBSTACK_SIZE_T i;
173     void *p;
174   } temp;                       /* Temporary for some macros.  */
175   _OBSTACK_SIZE_T alignment_mask;  /* Mask of alignment for each object. */
176 
177   /* These prototypes vary based on 'use_extra_arg'.  */
178   union
179   {
180     void *(*plain) (size_t);
181     void *(*extra) (void *, size_t);
182   } chunkfun;
183   union
184   {
185     void (*plain) (void *);
186     void (*extra) (void *, void *);
187   } freefun;
188 
189   void *extra_arg;              /* first arg for chunk alloc/dealloc funcs */
190   unsigned use_extra_arg : 1;     /* chunk alloc/dealloc funcs take extra arg */
191   unsigned maybe_empty_object : 1; /* There is a possibility that the current
192                                       chunk contains a zero-length object.  This
193                                       prevents freeing the chunk if we allocate
194                                       a bigger chunk to replace it. */
195   unsigned alloc_failed : 1;      /* No longer used, as we now call the failed
196                                      handler on error, but retained for binary
197                                      compatibility.  */
198 };
199 
200 /* Declare the external functions we use; they are in obstack.c.  */
201 
202 extern void _obstack_newchunk (struct obstack *, _OBSTACK_SIZE_T);
203 extern void _obstack_free (struct obstack *, void *);
204 extern int _obstack_begin (struct obstack *,
205                            _OBSTACK_SIZE_T, _OBSTACK_SIZE_T,
206                            void *(*) (size_t), void (*) (void *));
207 extern int _obstack_begin_1 (struct obstack *,
208                              _OBSTACK_SIZE_T, _OBSTACK_SIZE_T,
209                              void *(*) (void *, size_t),
210                              void (*) (void *, void *), void *);
211 extern _OBSTACK_SIZE_T _obstack_memory_used (struct obstack *)
212   __attribute_pure__;
213 
214 
215 /* Error handler called when 'obstack_chunk_alloc' failed to allocate
216    more memory.  This can be set to a user defined function which
217    should either abort gracefully or use longjump - but shouldn't
218    return.  The default action is to print a message and abort.  */
219 extern void (*obstack_alloc_failed_handler) (void);
220 
221 /* Exit value used when 'print_and_abort' is used.  */
222 extern int obstack_exit_failure;
223 
224 /* Pointer to beginning of object being allocated or to be allocated next.
225    Note that this might not be the final address of the object
226    because a new chunk might be needed to hold the final size.  */
227 
228 #define obstack_base(h) ((void *) (h)->object_base)
229 
230 /* Size for allocating ordinary chunks.  */
231 
232 #define obstack_chunk_size(h) ((h)->chunk_size)
233 
234 /* Pointer to next byte not yet allocated in current chunk.  */
235 
236 #define obstack_next_free(h) ((void *) (h)->next_free)
237 
238 /* Mask specifying low bits that should be clear in address of an object.  */
239 
240 #define obstack_alignment_mask(h) ((h)->alignment_mask)
241 
242 /* To prevent prototype warnings provide complete argument list.  */
243 #define obstack_init(h)							      \
244   _obstack_begin ((h), 0, 0,						      \
245                   _OBSTACK_CAST (void *(*) (size_t), obstack_chunk_alloc),    \
246                   _OBSTACK_CAST (void (*) (void *), obstack_chunk_free))
247 
248 #define obstack_begin(h, size)						      \
249   _obstack_begin ((h), (size), 0,					      \
250                   _OBSTACK_CAST (void *(*) (size_t), obstack_chunk_alloc), \
251                   _OBSTACK_CAST (void (*) (void *), obstack_chunk_free))
252 
253 #define obstack_specify_allocation(h, size, alignment, chunkfun, freefun)     \
254   _obstack_begin ((h), (size), (alignment),				      \
255                   _OBSTACK_CAST (void *(*) (size_t), chunkfun),		      \
256                   _OBSTACK_CAST (void (*) (void *), freefun))
257 
258 #define obstack_specify_allocation_with_arg(h, size, alignment, chunkfun, freefun, arg) \
259   _obstack_begin_1 ((h), (size), (alignment),				      \
260                     _OBSTACK_CAST (void *(*) (void *, size_t), chunkfun),     \
261                     _OBSTACK_CAST (void (*) (void *, void *), freefun), arg)
262 
263 #define obstack_chunkfun(h, newchunkfun)				      \
264   ((void) ((h)->chunkfun.extra = (void *(*) (void *, size_t)) (newchunkfun)))
265 
266 #define obstack_freefun(h, newfreefun)					      \
267   ((void) ((h)->freefun.extra = (void *(*) (void *, void *)) (newfreefun)))
268 
269 #define obstack_1grow_fast(h, achar) ((void) (*((h)->next_free)++ = (achar)))
270 
271 #define obstack_blank_fast(h, n) ((void) ((h)->next_free += (n)))
272 
273 #define obstack_memory_used(h) _obstack_memory_used (h)
274 
275 #if defined __GNUC__
276 # if !defined __GNUC_MINOR__ || __GNUC__ * 1000 + __GNUC_MINOR__ < 2008
277 #  define __extension__
278 # endif
279 
280 /* For GNU C, if not -traditional,
281    we can define these macros to compute all args only once
282    without using a global variable.
283    Also, we can avoid using the 'temp' slot, to make faster code.  */
284 
285 # define obstack_object_size(OBSTACK)					      \
286   __extension__								      \
287     ({ struct obstack const *__o = (OBSTACK);				      \
288        (_OBSTACK_SIZE_T) (__o->next_free - __o->object_base); })
289 
290 /* The local variable is named __o1 to avoid a shadowed variable
291    warning when invoked from other obstack macros.  */
292 # define obstack_room(OBSTACK)						      \
293   __extension__								      \
294     ({ struct obstack const *__o1 = (OBSTACK);				      \
295        (_OBSTACK_SIZE_T) (__o1->chunk_limit - __o1->next_free); })
296 
297 # define obstack_make_room(OBSTACK, length)				      \
298   __extension__								      \
299     ({ struct obstack *__o = (OBSTACK);					      \
300        _OBSTACK_SIZE_T __len = (length);				      \
301        if (obstack_room (__o) < __len)					      \
302          _obstack_newchunk (__o, __len);				      \
303        (void) 0; })
304 
305 # define obstack_empty_p(OBSTACK)					      \
306   __extension__								      \
307     ({ struct obstack const *__o = (OBSTACK);				      \
308        (__o->chunk->prev == 0						      \
309         && __o->next_free == __PTR_ALIGN ((char *) __o->chunk,		      \
310                                           __o->chunk->contents,		      \
311                                           __o->alignment_mask)); })
312 
313 # define obstack_grow(OBSTACK, where, length)				      \
314   __extension__								      \
315     ({ struct obstack *__o = (OBSTACK);					      \
316        _OBSTACK_SIZE_T __len = (length);				      \
317        if (obstack_room (__o) < __len)					      \
318          _obstack_newchunk (__o, __len);				      \
319        memcpy (__o->next_free, where, __len);				      \
320        __o->next_free += __len;						      \
321        (void) 0; })
322 
323 # define obstack_grow0(OBSTACK, where, length)				      \
324   __extension__								      \
325     ({ struct obstack *__o = (OBSTACK);					      \
326        _OBSTACK_SIZE_T __len = (length);				      \
327        if (obstack_room (__o) < __len + 1)				      \
328          _obstack_newchunk (__o, __len + 1);				      \
329        memcpy (__o->next_free, where, __len);				      \
330        __o->next_free += __len;						      \
331        *(__o->next_free)++ = 0;						      \
332        (void) 0; })
333 
334 # define obstack_1grow(OBSTACK, datum)					      \
335   __extension__								      \
336     ({ struct obstack *__o = (OBSTACK);					      \
337        if (obstack_room (__o) < 1)					      \
338          _obstack_newchunk (__o, 1);					      \
339        obstack_1grow_fast (__o, datum); })
340 
341 /* These assume that the obstack alignment is good enough for pointers
342    or ints, and that the data added so far to the current object
343    shares that much alignment.  */
344 
345 # define obstack_ptr_grow(OBSTACK, datum)				      \
346   __extension__								      \
347     ({ struct obstack *__o = (OBSTACK);					      \
348        if (obstack_room (__o) < sizeof (void *))			      \
349          _obstack_newchunk (__o, sizeof (void *));			      \
350        obstack_ptr_grow_fast (__o, datum); })
351 
352 # define obstack_int_grow(OBSTACK, datum)				      \
353   __extension__								      \
354     ({ struct obstack *__o = (OBSTACK);					      \
355        if (obstack_room (__o) < sizeof (int))				      \
356          _obstack_newchunk (__o, sizeof (int));				      \
357        obstack_int_grow_fast (__o, datum); })
358 
359 # define obstack_ptr_grow_fast(OBSTACK, aptr)				      \
360   __extension__								      \
361     ({ struct obstack *__o1 = (OBSTACK);				      \
362        void *__p1 = __o1->next_free;					      \
363        *(const void **) __p1 = (aptr);					      \
364        __o1->next_free += sizeof (const void *);			      \
365        (void) 0; })
366 
367 # define obstack_int_grow_fast(OBSTACK, aint)				      \
368   __extension__								      \
369     ({ struct obstack *__o1 = (OBSTACK);				      \
370        void *__p1 = __o1->next_free;					      \
371        *(int *) __p1 = (aint);						      \
372        __o1->next_free += sizeof (int);					      \
373        (void) 0; })
374 
375 # define obstack_blank(OBSTACK, length)					      \
376   __extension__								      \
377     ({ struct obstack *__o = (OBSTACK);					      \
378        _OBSTACK_SIZE_T __len = (length);				      \
379        if (obstack_room (__o) < __len)					      \
380          _obstack_newchunk (__o, __len);				      \
381        obstack_blank_fast (__o, __len); })
382 
383 # define obstack_alloc(OBSTACK, length)					      \
384   __extension__								      \
385     ({ struct obstack *__h = (OBSTACK);					      \
386        obstack_blank (__h, (length));					      \
387        obstack_finish (__h); })
388 
389 # define obstack_copy(OBSTACK, where, length)				      \
390   __extension__								      \
391     ({ struct obstack *__h = (OBSTACK);					      \
392        obstack_grow (__h, (where), (length));				      \
393        obstack_finish (__h); })
394 
395 # define obstack_copy0(OBSTACK, where, length)				      \
396   __extension__								      \
397     ({ struct obstack *__h = (OBSTACK);					      \
398        obstack_grow0 (__h, (where), (length));				      \
399        obstack_finish (__h); })
400 
401 /* The local variable is named __o1 to avoid a shadowed variable
402    warning when invoked from other obstack macros, typically obstack_free.  */
403 # define obstack_finish(OBSTACK)					      \
404   __extension__								      \
405     ({ struct obstack *__o1 = (OBSTACK);				      \
406        void *__value = (void *) __o1->object_base;			      \
407        if (__o1->next_free == __value)					      \
408          __o1->maybe_empty_object = 1;					      \
409        __o1->next_free							      \
410          = __PTR_ALIGN (__o1->object_base, __o1->next_free,		      \
411                         __o1->alignment_mask);				      \
412        if ((size_t) (__o1->next_free - (char *) __o1->chunk)		      \
413            > (size_t) (__o1->chunk_limit - (char *) __o1->chunk))	      \
414          __o1->next_free = __o1->chunk_limit;				      \
415        __o1->object_base = __o1->next_free;				      \
416        __value; })
417 
418 # define obstack_free(OBSTACK, OBJ)					      \
419   __extension__								      \
420     ({ struct obstack *__o = (OBSTACK);					      \
421        void *__obj = (void *) (OBJ);					      \
422        if (__obj > (void *) __o->chunk && __obj < (void *) __o->chunk_limit)  \
423          __o->next_free = __o->object_base = (char *) __obj;		      \
424        else								      \
425          _obstack_free (__o, __obj); })
426 
427 #else /* not __GNUC__ */
428 
429 # define obstack_object_size(h)						      \
430   ((_OBSTACK_SIZE_T) ((h)->next_free - (h)->object_base))
431 
432 # define obstack_room(h)						      \
433   ((_OBSTACK_SIZE_T) ((h)->chunk_limit - (h)->next_free))
434 
435 # define obstack_empty_p(h)						      \
436   ((h)->chunk->prev == 0						      \
437    && (h)->next_free == __PTR_ALIGN ((char *) (h)->chunk,		      \
438                                      (h)->chunk->contents,		      \
439                                      (h)->alignment_mask))
440 
441 /* Note that the call to _obstack_newchunk is enclosed in (..., 0)
442    so that we can avoid having void expressions
443    in the arms of the conditional expression.
444    Casting the third operand to void was tried before,
445    but some compilers won't accept it.  */
446 
447 # define obstack_make_room(h, length)					      \
448   ((h)->temp.i = (length),						      \
449    ((obstack_room (h) < (h)->temp.i)					      \
450     ? (_obstack_newchunk (h, (h)->temp.i), 0) : 0),			      \
451    (void) 0)
452 
453 # define obstack_grow(h, where, length)					      \
454   ((h)->temp.i = (length),						      \
455    ((obstack_room (h) < (h)->temp.i)					      \
456    ? (_obstack_newchunk ((h), (h)->temp.i), 0) : 0),			      \
457    memcpy ((h)->next_free, where, (h)->temp.i),				      \
458    (h)->next_free += (h)->temp.i,					      \
459    (void) 0)
460 
461 # define obstack_grow0(h, where, length)				      \
462   ((h)->temp.i = (length),						      \
463    ((obstack_room (h) < (h)->temp.i + 1)				      \
464    ? (_obstack_newchunk ((h), (h)->temp.i + 1), 0) : 0),		      \
465    memcpy ((h)->next_free, where, (h)->temp.i),				      \
466    (h)->next_free += (h)->temp.i,					      \
467    *((h)->next_free)++ = 0,						      \
468    (void) 0)
469 
470 # define obstack_1grow(h, datum)					      \
471   (((obstack_room (h) < 1)						      \
472     ? (_obstack_newchunk ((h), 1), 0) : 0),				      \
473    obstack_1grow_fast (h, datum))
474 
475 # define obstack_ptr_grow(h, datum)					      \
476   (((obstack_room (h) < sizeof (char *))				      \
477     ? (_obstack_newchunk ((h), sizeof (char *)), 0) : 0),		      \
478    obstack_ptr_grow_fast (h, datum))
479 
480 # define obstack_int_grow(h, datum)					      \
481   (((obstack_room (h) < sizeof (int))					      \
482     ? (_obstack_newchunk ((h), sizeof (int)), 0) : 0),			      \
483    obstack_int_grow_fast (h, datum))
484 
485 # define obstack_ptr_grow_fast(h, aptr)					      \
486   (((const void **) ((h)->next_free += sizeof (void *)))[-1] = (aptr),	      \
487    (void) 0)
488 
489 # define obstack_int_grow_fast(h, aint)					      \
490   (((int *) ((h)->next_free += sizeof (int)))[-1] = (aint),		      \
491    (void) 0)
492 
493 # define obstack_blank(h, length)					      \
494   ((h)->temp.i = (length),						      \
495    ((obstack_room (h) < (h)->temp.i)					      \
496    ? (_obstack_newchunk ((h), (h)->temp.i), 0) : 0),			      \
497    obstack_blank_fast (h, (h)->temp.i))
498 
499 # define obstack_alloc(h, length)					      \
500   (obstack_blank ((h), (length)), obstack_finish ((h)))
501 
502 # define obstack_copy(h, where, length)					      \
503   (obstack_grow ((h), (where), (length)), obstack_finish ((h)))
504 
505 # define obstack_copy0(h, where, length)				      \
506   (obstack_grow0 ((h), (where), (length)), obstack_finish ((h)))
507 
508 # define obstack_finish(h)						      \
509   (((h)->next_free == (h)->object_base					      \
510     ? (((h)->maybe_empty_object = 1), 0)				      \
511     : 0),								      \
512    (h)->temp.p = (h)->object_base,					      \
513    (h)->next_free							      \
514      = __PTR_ALIGN ((h)->object_base, (h)->next_free,			      \
515                     (h)->alignment_mask),				      \
516    (((size_t) ((h)->next_free - (char *) (h)->chunk)			      \
517      > (size_t) ((h)->chunk_limit - (char *) (h)->chunk))		      \
518    ? ((h)->next_free = (h)->chunk_limit) : 0),				      \
519    (h)->object_base = (h)->next_free,					      \
520    (h)->temp.p)
521 
522 # define obstack_free(h, obj)						      \
523   ((h)->temp.p = (void *) (obj),					      \
524    (((h)->temp.p > (void *) (h)->chunk					      \
525      && (h)->temp.p < (void *) (h)->chunk_limit)			      \
526     ? (void) ((h)->next_free = (h)->object_base = (char *) (h)->temp.p)       \
527     : _obstack_free ((h), (h)->temp.p)))
528 
529 #endif /* not __GNUC__ */
530 
531 #ifdef __cplusplus
532 }       /* C++ */
533 #endif
534 
535 #endif /* _OBSTACK_H */
536