|
|
1.1 ! root 1: /* obstack.h - object stack macros ! 2: Copyright (C) 1988, 1992 Free Software Foundation, Inc. ! 3: ! 4: This program is free software; you can redistribute it and/or modify it ! 5: under the terms of the GNU General Public License as published by the ! 6: Free Software Foundation; either version 2, or (at your option) any ! 7: later version. ! 8: ! 9: This program is distributed in the hope that it will be useful, ! 10: but WITHOUT ANY WARRANTY; without even the implied warranty of ! 11: MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the ! 12: GNU General Public License for more details. ! 13: ! 14: You should have received a copy of the GNU General Public License ! 15: along with this program; if not, write to the Free Software ! 16: Foundation, 675 Mass Ave, Cambridge, MA 02139, USA. */ ! 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: ! 101: /* Don't do the contents of this file more than once. */ ! 102: ! 103: #ifndef __OBSTACKS__ ! 104: #define __OBSTACKS__ ! 105: ! 106: /* We use subtraction of (char *)0 instead of casting to int ! 107: because on word-addressable machines a simple cast to int ! 108: may ignore the byte-within-word field of the pointer. */ ! 109: ! 110: #ifndef __PTR_TO_INT ! 111: #define __PTR_TO_INT(P) ((P) - (char *)0) ! 112: #endif ! 113: ! 114: #ifndef __INT_TO_PTR ! 115: #define __INT_TO_PTR(P) ((P) + (char *)0) ! 116: #endif ! 117: ! 118: /* We need the type of the resulting object. In ANSI C it is ptrdiff_t ! 119: but in traditional C it is usually long. If we are in ANSI C and ! 120: don't already have ptrdiff_t get it. */ ! 121: ! 122: #if defined (__STDC__) && ! defined (offsetof) ! 123: #if defined (__GNUC__) && defined (IN_GCC) ! 124: /* While building GCC, the stddef.h that goes with GCC has this name. */ ! 125: #define __need_ptrdiff_t ! 126: #include "gstddef.h" ! 127: #else ! 128: #include <stddef.h> ! 129: #endif ! 130: #endif ! 131: ! 132: #ifdef __STDC__ ! 133: #define PTR_INT_TYPE ptrdiff_t ! 134: #else ! 135: #define PTR_INT_TYPE long ! 136: #endif ! 137: ! 138: struct _obstack_chunk /* Lives at front of each chunk. */ ! 139: { ! 140: char *limit; /* 1 past end of this chunk */ ! 141: struct _obstack_chunk *prev; /* address of prior chunk or NULL */ ! 142: char contents[4]; /* objects begin here */ ! 143: }; ! 144: ! 145: struct obstack /* control current object in current chunk */ ! 146: { ! 147: long chunk_size; /* preferred size to allocate chunks in */ ! 148: struct _obstack_chunk* chunk; /* address of current struct obstack_chunk */ ! 149: char *object_base; /* address of object we are building */ ! 150: char *next_free; /* where to add next char to current object */ ! 151: char *chunk_limit; /* address of char after current chunk */ ! 152: PTR_INT_TYPE temp; /* Temporary for some macros. */ ! 153: int alignment_mask; /* Mask of alignment for each object. */ ! 154: struct _obstack_chunk *(*chunkfun) (); /* User's fcn to allocate a chunk. */ ! 155: void (*freefun) (); /* User's function to free a chunk. */ ! 156: char *extra_arg; /* first arg for chunk alloc/dealloc funcs */ ! 157: unsigned use_extra_arg:1; /* chunk alloc/dealloc funcs take extra arg */ ! 158: unsigned maybe_empty_object:1;/* There is a possibility that the current ! 159: chunk contains a zero-length object. This ! 160: prevents freeing the chunk if we allocate ! 161: a bigger chunk to replace it. */ ! 162: }; ! 163: ! 164: /* Declare the external functions we use; they are in obstack.c. */ ! 165: ! 166: #ifdef __STDC__ ! 167: extern void _obstack_newchunk (struct obstack *, int); ! 168: extern void _obstack_free (struct obstack *, void *); ! 169: extern void _obstack_begin (struct obstack *, int, int, ! 170: void *(*) (), void (*) ()); ! 171: extern void _obstack_begin_1 (struct obstack *, int, int, ! 172: void *(*) (), void (*) (), void *); ! 173: #else ! 174: extern void _obstack_newchunk (); ! 175: extern void _obstack_free (); ! 176: extern void _obstack_begin (); ! 177: extern void _obstack_begin_1 (); ! 178: #endif ! 179: ! 180: #ifdef __STDC__ ! 181: ! 182: /* Do the function-declarations after the structs ! 183: but before defining the macros. */ ! 184: ! 185: void obstack_init (struct obstack *obstack); ! 186: ! 187: void * obstack_alloc (struct obstack *obstack, int size); ! 188: ! 189: void * obstack_copy (struct obstack *obstack, void *address, int size); ! 190: void * obstack_copy0 (struct obstack *obstack, void *address, int size); ! 191: ! 192: void obstack_free (struct obstack *obstack, void *block); ! 193: ! 194: void obstack_blank (struct obstack *obstack, int size); ! 195: ! 196: void obstack_grow (struct obstack *obstack, void *data, int size); ! 197: void obstack_grow0 (struct obstack *obstack, void *data, int size); ! 198: ! 199: void obstack_1grow (struct obstack *obstack, int data_char); ! 200: void obstack_ptr_grow (struct obstack *obstack, void *data); ! 201: void obstack_int_grow (struct obstack *obstack, int data); ! 202: ! 203: void * obstack_finish (struct obstack *obstack); ! 204: ! 205: int obstack_object_size (struct obstack *obstack); ! 206: ! 207: int obstack_room (struct obstack *obstack); ! 208: void obstack_1grow_fast (struct obstack *obstack, int data_char); ! 209: void obstack_ptr_grow_fast (struct obstack *obstack, void *data); ! 210: void obstack_int_grow_fast (struct obstack *obstack, int data); ! 211: void obstack_blank_fast (struct obstack *obstack, int size); ! 212: ! 213: void * obstack_base (struct obstack *obstack); ! 214: void * obstack_next_free (struct obstack *obstack); ! 215: int obstack_alignment_mask (struct obstack *obstack); ! 216: int obstack_chunk_size (struct obstack *obstack); ! 217: ! 218: #endif /* __STDC__ */ ! 219: ! 220: /* Non-ANSI C cannot really support alternative functions for these macros, ! 221: so we do not declare them. */ ! 222: ! 223: /* Pointer to beginning of object being allocated or to be allocated next. ! 224: Note that this might not be the final address of the object ! 225: because a new chunk might be needed to hold the final size. */ ! 226: ! 227: #define obstack_base(h) ((h)->object_base) ! 228: ! 229: /* Size for allocating ordinary chunks. */ ! 230: ! 231: #define obstack_chunk_size(h) ((h)->chunk_size) ! 232: ! 233: /* Pointer to next byte not yet allocated in current chunk. */ ! 234: ! 235: #define obstack_next_free(h) ((h)->next_free) ! 236: ! 237: /* Mask specifying low bits that should be clear in address of an object. */ ! 238: ! 239: #define obstack_alignment_mask(h) ((h)->alignment_mask) ! 240: ! 241: #define obstack_init(h) \ ! 242: _obstack_begin ((h), 0, 0, \ ! 243: (void *(*) ()) obstack_chunk_alloc, (void (*) ()) obstack_chunk_free) ! 244: ! 245: #define obstack_begin(h, size) \ ! 246: _obstack_begin ((h), (size), 0, \ ! 247: (void *(*) ()) obstack_chunk_alloc, (void (*) ()) obstack_chunk_free) ! 248: ! 249: #define obstack_specify_allocation(h, size, alignment, chunkfun, freefun) \ ! 250: _obstack_begin ((h), (size), (alignment), \ ! 251: (void *(*) ()) (chunkfun), (void (*) ()) (freefun)) ! 252: ! 253: #define obstack_specify_allocation_with_arg(h, size, alignment, chunkfun, freefun, arg) \ ! 254: _obstack_begin_1 ((h), (size), (alignment), \ ! 255: (void *(*) ()) (chunkfun), (void (*) ()) (freefun), (arg)) ! 256: ! 257: #define obstack_chunkfun(h, newchunkfun) \ ! 258: ((h) -> chunkfun = (struct _obstack_chunk *(*)()) (newchunkfun)) ! 259: ! 260: #define obstack_freefun(h, newfreefun) \ ! 261: ((h) -> freefun = (void (*)()) (newfreefun)) ! 262: ! 263: #define obstack_1grow_fast(h,achar) (*((h)->next_free)++ = achar) ! 264: ! 265: #define obstack_blank_fast(h,n) ((h)->next_free += (n)) ! 266: ! 267: #if defined (__GNUC__) && defined (__STDC__) ! 268: //#if __GNUC__ < 2 ! 269: #define __extension__ ! 270: //#endif ! 271: ! 272: /* For GNU C, if not -traditional, ! 273: we can define these macros to compute all args only once ! 274: without using a global variable. ! 275: Also, we can avoid using the `temp' slot, to make faster code. */ ! 276: ! 277: #define obstack_object_size(OBSTACK) \ ! 278: __extension__ \ ! 279: ({ struct obstack *__o = (OBSTACK); \ ! 280: (unsigned) (__o->next_free - __o->object_base); }) ! 281: ! 282: #define obstack_room(OBSTACK) \ ! 283: __extension__ \ ! 284: ({ struct obstack *__o = (OBSTACK); \ ! 285: (unsigned) (__o->chunk_limit - __o->next_free); }) ! 286: ! 287: /* Note that the call to _obstack_newchunk is enclosed in (..., 0) ! 288: so that we can avoid having void expressions ! 289: in the arms of the conditional expression. ! 290: Casting the third operand to void was tried before, ! 291: but some compilers won't accept it. */ ! 292: #define obstack_grow(OBSTACK,where,length) \ ! 293: __extension__ \ ! 294: ({ struct obstack *__o = (OBSTACK); \ ! 295: int __len = (length); \ ! 296: ((__o->next_free + __len > __o->chunk_limit) \ ! 297: ? (_obstack_newchunk (__o, __len), 0) : 0); \ ! 298: memcpy (__o->next_free, where, __len); \ ! 299: __o->next_free += __len; \ ! 300: (void) 0; }) ! 301: ! 302: #define obstack_grow0(OBSTACK,where,length) \ ! 303: __extension__ \ ! 304: ({ struct obstack *__o = (OBSTACK); \ ! 305: int __len = (length); \ ! 306: ((__o->next_free + __len + 1 > __o->chunk_limit) \ ! 307: ? (_obstack_newchunk (__o, __len + 1), 0) : 0), \ ! 308: memcpy (__o->next_free, where, __len), \ ! 309: __o->next_free += __len, \ ! 310: *(__o->next_free)++ = 0; \ ! 311: (void) 0; }) ! 312: ! 313: #define obstack_1grow(OBSTACK,datum) \ ! 314: __extension__ \ ! 315: ({ struct obstack *__o = (OBSTACK); \ ! 316: ((__o->next_free + 1 > __o->chunk_limit) \ ! 317: ? (_obstack_newchunk (__o, 1), 0) : 0), \ ! 318: *(__o->next_free)++ = (datum); \ ! 319: (void) 0; }) ! 320: ! 321: /* These assume that the obstack alignment is good enough for pointers or ints, ! 322: and that the data added so far to the current object ! 323: shares that much alignment. */ ! 324: ! 325: #define obstack_ptr_grow(OBSTACK,datum) \ ! 326: __extension__ \ ! 327: ({ struct obstack *__o = (OBSTACK); \ ! 328: ((__o->next_free + sizeof (void *) > __o->chunk_limit) \ ! 329: ? (_obstack_newchunk (__o, sizeof (void *)), 0) : 0), \ ! 330: *((void **)__o->next_free)++ = ((void *)datum); \ ! 331: (void) 0; }) ! 332: ! 333: #define obstack_int_grow(OBSTACK,datum) \ ! 334: __extension__ \ ! 335: ({ struct obstack *__o = (OBSTACK); \ ! 336: ((__o->next_free + sizeof (int) > __o->chunk_limit) \ ! 337: ? (_obstack_newchunk (__o, sizeof (int)), 0) : 0), \ ! 338: *((int *)__o->next_free)++ = ((int)datum); \ ! 339: (void) 0; }) ! 340: ! 341: #define obstack_ptr_grow_fast(h,aptr) (*((void **)(h)->next_free)++ = (void *)aptr) ! 342: #define obstack_int_grow_fast(h,aint) (*((int *)(h)->next_free)++ = (int)aint) ! 343: ! 344: #define obstack_blank(OBSTACK,length) \ ! 345: __extension__ \ ! 346: ({ struct obstack *__o = (OBSTACK); \ ! 347: int __len = (length); \ ! 348: ((__o->chunk_limit - __o->next_free < __len) \ ! 349: ? (_obstack_newchunk (__o, __len), 0) : 0); \ ! 350: __o->next_free += __len; \ ! 351: (void) 0; }) ! 352: ! 353: #define obstack_alloc(OBSTACK,length) \ ! 354: __extension__ \ ! 355: ({ struct obstack *__h = (OBSTACK); \ ! 356: obstack_blank (__h, (length)); \ ! 357: obstack_finish (__h); }) ! 358: ! 359: #define obstack_copy(OBSTACK,where,length) \ ! 360: __extension__ \ ! 361: ({ struct obstack *__h = (OBSTACK); \ ! 362: obstack_grow (__h, (where), (length)); \ ! 363: obstack_finish (__h); }) ! 364: ! 365: #define obstack_copy0(OBSTACK,where,length) \ ! 366: __extension__ \ ! 367: ({ struct obstack *__h = (OBSTACK); \ ! 368: obstack_grow0 (__h, (where), (length)); \ ! 369: obstack_finish (__h); }) ! 370: ! 371: /* The local variable is named __o1 to avoid a name conflict ! 372: when obstack_blank is called. */ ! 373: #define obstack_finish(OBSTACK) \ ! 374: __extension__ \ ! 375: ({ struct obstack *__o1 = (OBSTACK); \ ! 376: void *value = (void *) __o1->object_base; \ ! 377: if (__o1->next_free == value) \ ! 378: __o1->maybe_empty_object = 1; \ ! 379: __o1->next_free \ ! 380: = __INT_TO_PTR ((__PTR_TO_INT (__o1->next_free)+__o1->alignment_mask)\ ! 381: & ~ (__o1->alignment_mask)); \ ! 382: ((__o1->next_free - (char *)__o1->chunk \ ! 383: > __o1->chunk_limit - (char *)__o1->chunk) \ ! 384: ? (__o1->next_free = __o1->chunk_limit) : 0); \ ! 385: __o1->object_base = __o1->next_free; \ ! 386: value; }) ! 387: ! 388: #define obstack_free(OBSTACK, OBJ) \ ! 389: __extension__ \ ! 390: ({ struct obstack *__o = (OBSTACK); \ ! 391: void *__obj = (OBJ); \ ! 392: if (__obj > (void *)__o->chunk && __obj < (void *)__o->chunk_limit) \ ! 393: __o->next_free = __o->object_base = __obj; \ ! 394: else (obstack_free) (__o, __obj); }) ! 395: ! 396: #else /* not __GNUC__ or not __STDC__ */ ! 397: ! 398: #define obstack_object_size(h) \ ! 399: (unsigned) ((h)->next_free - (h)->object_base) ! 400: ! 401: #define obstack_room(h) \ ! 402: (unsigned) ((h)->chunk_limit - (h)->next_free) ! 403: ! 404: #define obstack_grow(h,where,length) \ ! 405: ( (h)->temp = (length), \ ! 406: (((h)->next_free + (h)->temp > (h)->chunk_limit) \ ! 407: ? (_obstack_newchunk ((h), (h)->temp), 0) : 0), \ ! 408: memcpy ((h)->next_free, where, (h)->temp), \ ! 409: (h)->next_free += (h)->temp) ! 410: ! 411: #define obstack_grow0(h,where,length) \ ! 412: ( (h)->temp = (length), \ ! 413: (((h)->next_free + (h)->temp + 1 > (h)->chunk_limit) \ ! 414: ? (_obstack_newchunk ((h), (h)->temp + 1), 0) : 0), \ ! 415: memcpy ((h)->next_free, where, (h)->temp), \ ! 416: (h)->next_free += (h)->temp, \ ! 417: *((h)->next_free)++ = 0) ! 418: ! 419: #define obstack_1grow(h,datum) \ ! 420: ( (((h)->next_free + 1 > (h)->chunk_limit) \ ! 421: ? (_obstack_newchunk ((h), 1), 0) : 0), \ ! 422: *((h)->next_free)++ = (datum)) ! 423: ! 424: #define obstack_ptr_grow(h,datum) \ ! 425: ( (((h)->next_free + sizeof (char *) > (h)->chunk_limit) \ ! 426: ? (_obstack_newchunk ((h), sizeof (char *)), 0) : 0), \ ! 427: *((char **)(((h)->next_free+=sizeof(char *))-sizeof(char *))) = ((char *)datum)) ! 428: ! 429: #define obstack_int_grow(h,datum) \ ! 430: ( (((h)->next_free + sizeof (int) > (h)->chunk_limit) \ ! 431: ? (_obstack_newchunk ((h), sizeof (int)), 0) : 0), \ ! 432: *((int *)(((h)->next_free+=sizeof(int))-sizeof(int))) = ((int)datum)) ! 433: ! 434: #define obstack_ptr_grow_fast(h,aptr) (*((char **)(h)->next_free)++ = (char *)aptr) ! 435: #define obstack_int_grow_fast(h,aint) (*((int *)(h)->next_free)++ = (int)aint) ! 436: ! 437: #define obstack_blank(h,length) \ ! 438: ( (h)->temp = (length), \ ! 439: (((h)->chunk_limit - (h)->next_free < (h)->temp) \ ! 440: ? (_obstack_newchunk ((h), (h)->temp), 0) : 0), \ ! 441: (h)->next_free += (h)->temp) ! 442: ! 443: #define obstack_alloc(h,length) \ ! 444: (obstack_blank ((h), (length)), obstack_finish ((h))) ! 445: ! 446: #define obstack_copy(h,where,length) \ ! 447: (obstack_grow ((h), (where), (length)), obstack_finish ((h))) ! 448: ! 449: #define obstack_copy0(h,where,length) \ ! 450: (obstack_grow0 ((h), (where), (length)), obstack_finish ((h))) ! 451: ! 452: #define obstack_finish(h) \ ! 453: ( ((h)->next_free == (h)->object_base \ ! 454: ? (((h)->maybe_empty_object = 1), 0) \ ! 455: : 0), \ ! 456: (h)->temp = __PTR_TO_INT ((h)->object_base), \ ! 457: (h)->next_free \ ! 458: = __INT_TO_PTR ((__PTR_TO_INT ((h)->next_free)+(h)->alignment_mask) \ ! 459: & ~ ((h)->alignment_mask)), \ ! 460: (((h)->next_free - (char *)(h)->chunk \ ! 461: > (h)->chunk_limit - (char *)(h)->chunk) \ ! 462: ? ((h)->next_free = (h)->chunk_limit) : 0), \ ! 463: (h)->object_base = (h)->next_free, \ ! 464: __INT_TO_PTR ((h)->temp)) ! 465: ! 466: #ifdef __STDC__ ! 467: #define obstack_free(h,obj) \ ! 468: ( (h)->temp = (char *)(obj) - (char *) (h)->chunk, \ ! 469: (((h)->temp > 0 && (h)->temp < (h)->chunk_limit - (char *) (h)->chunk)\ ! 470: ? (int) ((h)->next_free = (h)->object_base \ ! 471: = (h)->temp + (char *) (h)->chunk) \ ! 472: : (((obstack_free) ((h), (h)->temp + (char *) (h)->chunk), 0), 0))) ! 473: #else ! 474: #define obstack_free(h,obj) \ ! 475: ( (h)->temp = (char *)(obj) - (char *) (h)->chunk, \ ! 476: (((h)->temp > 0 && (h)->temp < (h)->chunk_limit - (char *) (h)->chunk)\ ! 477: ? (int) ((h)->next_free = (h)->object_base \ ! 478: = (h)->temp + (char *) (h)->chunk) \ ! 479: : (_obstack_free ((h), (h)->temp + (char *) (h)->chunk), 0))) ! 480: #endif ! 481: ! 482: #endif /* not __GNUC__ or not __STDC__ */ ! 483: ! 484: #endif /* not __OBSTACKS__ */
This archive runs on limited infrastructure. Preserving old code on modern bandwidth. Automated agents are requested to crawl responsibly.