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