1 /* obstack.h - object stack macros
2 Copyright (C) 1988-1994,1996-1999,2003,2004,2005
3 Free Software Foundation, Inc.
4 This file is part of the GNU C Library.
6 The GNU C Library is free software; you can redistribute it and/or
7 modify it under the terms of the GNU Lesser General Public
8 License as published by the Free Software Foundation; either
9 version 2.1 of the License, or (at your option) any later version.
11 The GNU C Library is distributed in the hope that it will be useful,
12 but WITHOUT ANY WARRANTY; without even the implied warranty of
13 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
14 Lesser General Public License for more details.
16 You should have received a copy of the GNU Lesser General Public
17 License along with the GNU C Library; if not, write to the Free
18 Software Foundation, Inc., 51 Franklin Street, Fifth Floor,
19 Boston, MA 02110-1301, USA. */
21 /** @page obstack Obstack Memory Allocation
23 * Obstacks are the prefered way to handle memory allocation in libFirm.
24 * Compared to classical malloc they are faster but don't allow fine-grained
25 * freeing of allocated memory. But in a compile this is fine most of the time
26 * as memory is allocated for a phase or a graph and later the whole phase ends
27 * or the whole graph gets discarded.
29 * There's very good documentation about Object stacks in the glibc manual:
30 * http://www.gnu.org/s/libc/manual/html_node/Obstacks.html
35 All the apparent functions defined here are macros. The idea
36 is that you would use these pre-tested macros to solve a
37 very specific set of problems, and they would run fast.
38 Caution: no side-effects in arguments please!! They may be
39 evaluated MANY times!!
41 These macros operate a stack of objects. Each object starts life
42 small, and may grow to maturity. (Consider building a word syllable
43 by syllable.) An object can move while it is growing. Once it has
44 been "finished" it never changes address again. So the "top of the
45 stack" is typically an immature growing object, while the rest of the
46 stack is of mature, fixed size and fixed address objects.
48 These routines grab large chunks of memory, using a function you
49 supply, called `obstack_chunk_alloc'. On occasion, they free chunks,
50 by calling `obstack_chunk_free'. You must define them and declare
51 them before using any obstack macros.
53 Each independent stack is represented by a `struct obstack'.
54 Each of the obstack macros expects a pointer to such a structure
55 as the first argument.
57 One motivation for this package is the problem of growing char strings
58 in symbol tables. Unless you are "fascist pig with a read-only mind"
59 --Gosper's immortal quote from HAKMEM item 154, out of context--you
60 would not like to put any arbitrary upper limit on the length of your
63 In practice this often means you will build many short symbols and a
64 few long symbols. At the time you are reading a symbol you don't know
65 how long it is. One traditional method is to read a symbol into a
66 buffer, realloc()ating the buffer every time you try to read a symbol
67 that is longer than the buffer. This is beaut, but you still will
68 want to copy the symbol from the buffer to a more permanent
69 symbol-table entry say about half the time.
71 With obstacks, you can work differently. Use one obstack for all symbol
72 names. As you read a symbol, grow the name in the obstack gradually.
73 When the name is complete, finalize it. Then, if the symbol exists already,
74 free the newly read name.
76 The way we do this is to take a large chunk, allocating memory from
77 low addresses. When you want to build a symbol in the chunk you just
78 add chars above the current "high water mark" in the chunk. When you
79 have finished adding chars, because you got to the end of the symbol,
80 you know how long the chars are, and you can create a new object.
81 Mostly the chars will not burst over the highest address of the chunk,
82 because you would typically expect a chunk to be (say) 100 times as
83 long as an average object.
85 In case that isn't clear, when we have enough chars to make up
86 the object, THEY ARE ALREADY CONTIGUOUS IN THE CHUNK (guaranteed)
87 so we just point to it where it lies. No moving of chars is
88 needed and this is the second win: potentially long strings need
89 never be explicitly shuffled. Once an object is formed, it does not
90 change its address during its lifetime.
92 When the chars burst over a chunk boundary, we allocate a larger
93 chunk, and then copy the partly formed object from the end of the old
94 chunk to the beginning of the new larger chunk. We then carry on
95 accreting characters to the end of the object as we normally would.
97 A special macro is provided to add a single char at a time to a
98 growing object. This allows the use of register variables, which
99 break the ordinary 'growth' macro.
102 We allocate large chunks.
103 We carve out one object at a time from the current chunk.
104 Once carved, an object never moves.
105 We are free to append data of any size to the currently
107 Exactly one object is growing in an obstack at any one time.
108 You can run one obstack per control block.
109 You may have as many control blocks as you dare.
110 Because of the way we do it, you can `unwind' an obstack
111 back to a previous state. (You may remove objects much
112 as you would with a stack.)
116 /* Don't do the contents of this file more than once. */
121 #include "../begin.h"
123 /** @cond DISABLED */
125 /* We need the type of a pointer subtraction. If __PTRDIFF_TYPE__ is
126 defined, as with GNU C, use that; that way we don't pollute the
127 namespace with <stddef.h>'s symbols. Otherwise, include <stddef.h>
128 and use ptrdiff_t. */
130 #ifdef __PTRDIFF_TYPE__
131 # define PTR_INT_TYPE __PTRDIFF_TYPE__
134 # define PTR_INT_TYPE ptrdiff_t
137 /* If B is the base of an object addressed by P, return the result of
138 aligning P to the next multiple of A + 1. B and P must be of type
139 char *. A + 1 must be a power of 2. */
141 #define __BPTR_ALIGN(B, P, A) ((B) + (((P) - (B) + (A)) & ~(A)))
143 /* Similiar to _BPTR_ALIGN (B, P, A), except optimize the common case
144 where pointers can be converted to integers, aligned as integers,
145 and converted back again. If PTR_INT_TYPE is narrower than a
146 pointer (e.g., the AS/400), play it safe and compute the alignment
147 relative to B. Otherwise, use the faster strategy of computing the
148 alignment relative to 0. */
150 #define __PTR_ALIGN(B, P, A) \
151 __BPTR_ALIGN (sizeof (PTR_INT_TYPE) < sizeof (void *) ? (B) : (char *) 0, \
157 struct _obstack_chunk /* Lives at front of each chunk. */
159 char *limit; /* 1 past end of this chunk */
160 struct _obstack_chunk *prev; /* address of prior chunk or NULL */
161 char contents[4]; /* objects begin here */
164 struct obstack /* control current object in current chunk */
166 PTR_INT_TYPE chunk_size; /* preferred size to allocate chunks in */
167 struct _obstack_chunk *chunk; /* address of current struct obstack_chunk */
168 char *object_base; /* address of object we are building */
169 char *next_free; /* where to add next char to current object */
170 char *chunk_limit; /* address of char after current chunk */
173 PTR_INT_TYPE tempint;
175 } temp; /* Temporary for some macros. */
176 int alignment_mask; /* Mask of alignment for each object. */
177 /* These prototypes vary based on `use_extra_arg', and we use
178 casts to the prototypeless function type in all assignments,
179 but having prototypes here quiets -Wstrict-prototypes. */
180 struct _obstack_chunk *(*chunkfun) (void *, PTR_INT_TYPE);
181 void (*freefun) (void *, struct _obstack_chunk *);
182 void *extra_arg; /* first arg for chunk alloc/dealloc funcs */
183 unsigned use_extra_arg:1; /* chunk alloc/dealloc funcs take extra arg */
184 unsigned maybe_empty_object:1;/* There is a possibility that the current
185 chunk contains a zero-length object. This
186 prevents freeing the chunk if we allocate
187 a bigger chunk to replace it. */
188 unsigned alloc_failed:1; /* No longer used, as we now call the failed
189 handler on error, but retained for binary
193 /* Declare the external functions we use; they are in obstack.c. */
195 FIRM_API void _obstack_newchunk (struct obstack *, PTR_INT_TYPE);
196 FIRM_API int _obstack_begin (struct obstack *, int, int,
197 void *(*) (PTR_INT_TYPE), void (*) (void *));
198 FIRM_API int _obstack_begin_1 (struct obstack *, int, int,
199 void *(*) (void *, PTR_INT_TYPE),
200 void (*) (void *, void *), void *);
201 FIRM_API PTR_INT_TYPE _obstack_memory_used (struct obstack *);
203 FIRM_API void obstack_free (struct obstack *obstack, void *block);
206 /* Error handler called when `obstack_chunk_alloc' failed to allocate
207 more memory. This can be set to a user defined function which
208 should either abort gracefully or use longjump - but shouldn't
209 return. The default action is to print a message and abort. */
210 FIRM_API void (*obstack_alloc_failed_handler) (void);
212 /* Exit value used when `print_and_abort' is used. */
213 FIRM_API int obstack_exit_failure;
215 /* Pointer to beginning of object being allocated or to be allocated next.
216 Note that this might not be the final address of the object
217 because a new chunk might be needed to hold the final size. */
219 #define obstack_base(h) ((void *) (h)->object_base)
221 /* Size for allocating ordinary chunks. */
223 #define obstack_chunk_size(h) ((h)->chunk_size)
225 /* Pointer to next byte not yet allocated in current chunk. */
227 #define obstack_next_free(h) ((h)->next_free)
229 /* Mask specifying low bits that should be clear in address of an object. */
231 #define obstack_alignment_mask(h) ((h)->alignment_mask)
233 /* To prevent prototype warnings provide complete argument list. */
234 #define obstack_init(h) \
235 _obstack_begin ((h), 0, 0, \
236 (void *(*) (PTR_INT_TYPE)) obstack_chunk_alloc, \
237 (void (*) (void *)) obstack_chunk_free)
239 #define obstack_begin(h, size) \
240 _obstack_begin ((h), (size), 0, \
241 (void *(*) (PTR_INT_TYPE)) obstack_chunk_alloc, \
242 (void (*) (void *)) obstack_chunk_free)
244 #define obstack_specify_allocation(h, size, alignment, chunkfun, freefun) \
245 _obstack_begin ((h), (size), (alignment), \
246 (void *(*) (PTR_INT_TYPE)) (chunkfun), \
247 (void (*) (void *)) (freefun))
249 #define obstack_specify_allocation_with_arg(h, size, alignment, chunkfun, freefun, arg) \
250 _obstack_begin_1 ((h), (size), (alignment), \
251 (void *(*) (void *, PTR_INT_TYPE)) (chunkfun), \
252 (void (*) (void *, void *)) (freefun), (arg))
254 #define obstack_chunkfun(h, newchunkfun) \
255 ((h) -> chunkfun = (struct _obstack_chunk *(*)(void *, PTR_INT_TYPE)) (newchunkfun))
257 #define obstack_freefun(h, newfreefun) \
258 ((h) -> freefun = (void (*)(void *, struct _obstack_chunk *)) (newfreefun))
260 #define obstack_1grow_fast(h,achar) (*((h)->next_free)++ = (achar))
262 #define obstack_blank_fast(h,n) ((h)->next_free += (n))
264 #define obstack_memory_used(h) _obstack_memory_used (h)
266 #if defined __GNUC__ && defined __STDC__ && __STDC__
267 /* NextStep 2.0 cc is really gcc 1.93 but it defines __GNUC__ = 2 and
268 does not implement __extension__. But that compiler doesn't define
270 # if __GNUC__ < 2 || (__NeXT__ && !__GNUC_MINOR__)
271 # define __extension__
274 /* For GNU C, if not -traditional,
275 we can define these macros to compute all args only once
276 without using a global variable.
277 Also, we can avoid using the `temp' slot, to make faster code. */
279 # define obstack_object_size(OBSTACK) \
281 ({ struct obstack const *__o = (OBSTACK); \
282 (unsigned) (__o->next_free - __o->object_base); })
284 # define obstack_room(OBSTACK) \
286 ({ struct obstack const *__o = (OBSTACK); \
287 (unsigned) (__o->chunk_limit - __o->next_free); })
289 # define obstack_make_room(OBSTACK,length) \
291 ({ struct obstack *__o = (OBSTACK); \
292 int __len = (length); \
293 if (__o->chunk_limit - __o->next_free < __len) \
294 _obstack_newchunk (__o, __len); \
297 # define obstack_empty_p(OBSTACK) \
299 ({ struct obstack const *__o = (OBSTACK); \
300 (__o->chunk->prev == 0 \
301 && __o->next_free == __PTR_ALIGN ((char *) __o->chunk, \
302 __o->chunk->contents, \
303 __o->alignment_mask)); })
305 # define obstack_grow(OBSTACK,where,length) \
307 ({ struct obstack *__o = (OBSTACK); \
308 int __len = (length); \
309 if (__o->next_free + __len > __o->chunk_limit) \
310 _obstack_newchunk (__o, __len); \
311 memcpy (__o->next_free, where, __len); \
312 __o->next_free += __len; \
315 # define obstack_grow0(OBSTACK,where,length) \
317 ({ struct obstack *__o = (OBSTACK); \
318 int __len = (length); \
319 if (__o->next_free + __len + 1 > __o->chunk_limit) \
320 _obstack_newchunk (__o, __len + 1); \
321 memcpy (__o->next_free, where, __len); \
322 __o->next_free += __len; \
323 *(__o->next_free)++ = 0; \
326 # define obstack_1grow(OBSTACK,datum) \
328 ({ struct obstack *__o = (OBSTACK); \
329 if (__o->next_free + 1 > __o->chunk_limit) \
330 _obstack_newchunk (__o, 1); \
331 obstack_1grow_fast (__o, datum); \
334 /* These assume that the obstack alignment is good enough for pointers
335 or ints, and that the data added so far to the current object
336 shares that much alignment. */
338 # define obstack_ptr_grow(OBSTACK,datum) \
340 ({ struct obstack *__o = (OBSTACK); \
341 if (__o->next_free + sizeof (void *) > __o->chunk_limit) \
342 _obstack_newchunk (__o, sizeof (void *)); \
343 obstack_ptr_grow_fast (__o, datum); }) \
345 # define obstack_int_grow(OBSTACK,datum) \
347 ({ struct obstack *__o = (OBSTACK); \
348 if (__o->next_free + sizeof (int) > __o->chunk_limit) \
349 _obstack_newchunk (__o, sizeof (int)); \
350 obstack_int_grow_fast (__o, datum); })
352 # define obstack_ptr_grow_fast(OBSTACK,aptr) \
354 ({ struct obstack *__o1 = (OBSTACK); \
355 *(const void **) __o1->next_free = (aptr); \
356 __o1->next_free += sizeof (const void *); \
359 # define obstack_int_grow_fast(OBSTACK,aint) \
361 ({ struct obstack *__o1 = (OBSTACK); \
362 *(int *) __o1->next_free = (aint); \
363 __o1->next_free += sizeof (int); \
366 # define obstack_blank(OBSTACK,length) \
368 ({ struct obstack *__o = (OBSTACK); \
369 int __len = (length); \
370 if (__o->chunk_limit - __o->next_free < __len) \
371 _obstack_newchunk (__o, __len); \
372 obstack_blank_fast (__o, __len); \
375 # define obstack_alloc(OBSTACK,length) \
377 ({ struct obstack *__h = (OBSTACK); \
378 obstack_blank (__h, (length)); \
379 obstack_finish (__h); })
381 # define obstack_copy(OBSTACK,where,length) \
383 ({ struct obstack *__h = (OBSTACK); \
384 obstack_grow (__h, (where), (length)); \
385 obstack_finish (__h); })
387 # define obstack_copy0(OBSTACK,where,length) \
389 ({ struct obstack *__h = (OBSTACK); \
390 obstack_grow0 (__h, (where), (length)); \
391 obstack_finish (__h); })
393 /* The local variable is named __o1 to avoid a name conflict
394 when obstack_blank is called. */
395 # define obstack_finish(OBSTACK) \
397 ({ struct obstack *__o1 = (OBSTACK); \
398 void *__value = (void *) __o1->object_base; \
399 if (__o1->next_free == __value) \
400 __o1->maybe_empty_object = 1; \
402 = __PTR_ALIGN (__o1->object_base, __o1->next_free, \
403 __o1->alignment_mask); \
404 if (__o1->next_free - (char *)__o1->chunk \
405 > __o1->chunk_limit - (char *)__o1->chunk) \
406 __o1->next_free = __o1->chunk_limit; \
407 __o1->object_base = __o1->next_free; \
410 # define obstack_free(OBSTACK, OBJ) \
412 ({ struct obstack *__o = (OBSTACK); \
413 void *__obj = (OBJ); \
414 if (__obj > (void *)__o->chunk && __obj < (void *)__o->chunk_limit) \
415 __o->next_free = __o->object_base = (char *)__obj; \
416 else (obstack_free) (__o, __obj); })
418 #else /* not __GNUC__ or not __STDC__ */
420 # define obstack_object_size(h) \
421 (unsigned) ((h)->next_free - (h)->object_base)
423 # define obstack_room(h) \
424 (unsigned) ((h)->chunk_limit - (h)->next_free)
426 # define obstack_empty_p(h) \
427 ((h)->chunk->prev == 0 \
428 && (h)->next_free == __PTR_ALIGN ((char *) (h)->chunk, \
429 (h)->chunk->contents, \
430 (h)->alignment_mask))
432 /* Note that the call to _obstack_newchunk is enclosed in (..., 0)
433 so that we can avoid having void expressions
434 in the arms of the conditional expression.
435 Casting the third operand to void was tried before,
436 but some compilers won't accept it. */
438 # define obstack_make_room(h,length) \
439 ( (h)->temp.tempint = (length), \
440 (((h)->next_free + (h)->temp.tempint > (h)->chunk_limit) \
441 ? (_obstack_newchunk ((h), (h)->temp.tempint), 0) : 0))
443 # define obstack_grow(h,where,length) \
444 ( (h)->temp.tempint = (length), \
445 (((h)->next_free + (h)->temp.tempint > (h)->chunk_limit) \
446 ? (_obstack_newchunk ((h), (h)->temp.tempint), 0) : 0), \
447 memcpy ((h)->next_free, where, (h)->temp.tempint), \
448 (h)->next_free += (h)->temp.tempint)
450 # define obstack_grow0(h,where,length) \
451 ( (h)->temp.tempint = (length), \
452 (((h)->next_free + (h)->temp.tempint + 1 > (h)->chunk_limit) \
453 ? (_obstack_newchunk ((h), (h)->temp.tempint + 1), 0) : 0), \
454 memcpy ((h)->next_free, where, (h)->temp.tempint), \
455 (h)->next_free += (h)->temp.tempint, \
456 *((h)->next_free)++ = 0)
458 # define obstack_1grow(h,datum) \
459 ( (((h)->next_free + 1 > (h)->chunk_limit) \
460 ? (_obstack_newchunk ((h), 1), 0) : 0), \
461 obstack_1grow_fast (h, datum))
463 # define obstack_ptr_grow(h,datum) \
464 ( (((h)->next_free + sizeof (char *) > (h)->chunk_limit) \
465 ? (_obstack_newchunk ((h), sizeof (char *)), 0) : 0), \
466 obstack_ptr_grow_fast (h, datum))
468 # define obstack_int_grow(h,datum) \
469 ( (((h)->next_free + sizeof (int) > (h)->chunk_limit) \
470 ? (_obstack_newchunk ((h), sizeof (int)), 0) : 0), \
471 obstack_int_grow_fast (h, datum))
473 # define obstack_ptr_grow_fast(h,aptr) \
474 (((const void **) ((h)->next_free += sizeof (void *)))[-1] = (aptr))
476 # define obstack_int_grow_fast(h,aint) \
477 (((int *) ((h)->next_free += sizeof (int)))[-1] = (aint))
479 # define obstack_blank(h,length) \
480 ( (h)->temp.tempint = (length), \
481 (((h)->chunk_limit - (h)->next_free < (h)->temp.tempint) \
482 ? (_obstack_newchunk ((h), (h)->temp.tempint), 0) : 0), \
483 obstack_blank_fast (h, (h)->temp.tempint))
485 # define obstack_alloc(h,length) \
486 (obstack_blank ((h), (length)), obstack_finish ((h)))
488 # define obstack_copy(h,where,length) \
489 (obstack_grow ((h), (where), (length)), obstack_finish ((h)))
491 # define obstack_copy0(h,where,length) \
492 (obstack_grow0 ((h), (where), (length)), obstack_finish ((h)))
494 # define obstack_finish(h) \
495 ( ((h)->next_free == (h)->object_base \
496 ? (((h)->maybe_empty_object = 1), 0) \
498 (h)->temp.tempptr = (h)->object_base, \
500 = __PTR_ALIGN ((h)->object_base, (h)->next_free, \
501 (h)->alignment_mask), \
502 (((h)->next_free - (char *) (h)->chunk \
503 > (h)->chunk_limit - (char *) (h)->chunk) \
504 ? ((h)->next_free = (h)->chunk_limit) : 0), \
505 (h)->object_base = (h)->next_free, \
508 # define obstack_free(h,obj) \
509 ( (h)->temp.tempint = (char *) (obj) - (char *) (h)->chunk, \
510 ((((h)->temp.tempint > 0 \
511 && (h)->temp.tempint < (h)->chunk_limit - (char *) (h)->chunk)) \
512 ? (PTR_INT_TYPE) ((h)->next_free = (h)->object_base \
513 = (h)->temp.tempint + (char *) (h)->chunk) \
514 : (((obstack_free) ((h), (h)->temp.tempint + (char *) (h)->chunk), 0), 0)))
516 #endif /* not __GNUC__ or not __STDC__ */
518 /** @def FIRM_NOTHROW
519 * tells that a function does not throw C++ exceptions. Currently this is only
520 * necessary for obstack_printf to avoid nameclashes when linking with glibc
521 * which has an obstack library with NOTHROW builtin. */
523 # define FIRM_NOTHROW throw ()
525 # define FIRM_NOTHROW
530 * Attribute with marks a function to have a printf style format
531 * string and variadic argument.
533 #if defined(__GNUC__)
534 # define FIRM_PRINTF(a,b) __attribute__((__format__(__printf__, a, b)))
536 # define FIRM_PRINTF(a,b)
539 /** prints formated string (printf-style format) to an obstack.
540 * This is done by "growing" the obstack with the obstack_*grow*
541 * functions. Note: Does NOT append a null-byte. */
542 FIRM_API int obstack_printf(struct obstack *obst, const char *fmt, ...)
543 FIRM_NOTHROW FIRM_PRINTF(2, 3);
544 FIRM_API int obstack_vprintf(struct obstack *obst, const char *fmt, va_list ap)
545 FIRM_NOTHROW FIRM_PRINTF(2, 0);