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