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