|
|
1.1 root 1: /* obstack.h - object stack macros 1.1.1.2 ! root 2: Copyright (C) 1988, 1992 Free Software Foundation, Inc. 1.1 root 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" 1.1.1.2 ! root 44: --Gosper's immortal quote from HAKMEM item 154, out of context--you 1.1 root 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. 1.1.1.2 ! root 95: Because of the way we do it, you can `unwind' an obstack 1.1 root 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: 1.1.1.2 ! root 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: /* On Next machine, the system's stddef.h screws up if included ! 125: after we have defined just ptrdiff_t, so include all of gstddef.h. ! 126: Otherwise, define just ptrdiff_t, which is all we need. */ ! 127: #ifndef __NeXT__ ! 128: #define __need_ptrdiff_t ! 129: #endif ! 130: ! 131: /* While building GCC, the stddef.h that goes with GCC has this name. */ ! 132: #include "gstddef.h" ! 133: #else ! 134: #include <stddef.h> ! 135: #endif ! 136: #endif ! 137: ! 138: #ifdef __STDC__ ! 139: #define PTR_INT_TYPE ptrdiff_t ! 140: #else ! 141: #define PTR_INT_TYPE long ! 142: #endif ! 143: 1.1 root 144: struct _obstack_chunk /* Lives at front of each chunk. */ 145: { 146: char *limit; /* 1 past end of this chunk */ 147: struct _obstack_chunk *prev; /* address of prior chunk or NULL */ 148: char contents[4]; /* objects begin here */ 149: }; 150: 151: struct obstack /* control current object in current chunk */ 152: { 153: long chunk_size; /* preferred size to allocate chunks in */ 154: struct _obstack_chunk* chunk; /* address of current struct obstack_chunk */ 155: char *object_base; /* address of object we are building */ 156: char *next_free; /* where to add next char to current object */ 157: char *chunk_limit; /* address of char after current chunk */ 1.1.1.2 ! root 158: PTR_INT_TYPE temp; /* Temporary for some macros. */ 1.1 root 159: int alignment_mask; /* Mask of alignment for each object. */ 160: struct _obstack_chunk *(*chunkfun) (); /* User's fcn to allocate a chunk. */ 161: void (*freefun) (); /* User's function to free a chunk. */ 1.1.1.2 ! root 162: char *extra_arg; /* first arg for chunk alloc/dealloc funcs */ ! 163: unsigned use_extra_arg:1; /* chunk alloc/dealloc funcs take extra arg */ ! 164: unsigned maybe_empty_object:1;/* There is a possibility that the current ! 165: chunk contains a zero-length object. This ! 166: prevents freeing the chunk if we allocate ! 167: a bigger chunk to replace it. */ 1.1 root 168: }; 169: 170: /* Declare the external functions we use; they are in obstack.c. */ 171: 172: #ifdef __STDC__ 173: extern void _obstack_newchunk (struct obstack *, int); 174: extern void _obstack_free (struct obstack *, void *); 175: extern void _obstack_begin (struct obstack *, int, int, 176: void *(*) (), void (*) ()); 1.1.1.2 ! root 177: extern void _obstack_begin_1 (struct obstack *, int, int, ! 178: void *(*) (), void (*) (), void *); 1.1 root 179: #else 180: extern void _obstack_newchunk (); 181: extern void _obstack_free (); 182: extern void _obstack_begin (); 1.1.1.2 ! root 183: extern void _obstack_begin_1 (); 1.1 root 184: #endif 185: 186: #ifdef __STDC__ 187: 188: /* Do the function-declarations after the structs 189: but before defining the macros. */ 190: 191: void obstack_init (struct obstack *obstack); 192: 193: void * obstack_alloc (struct obstack *obstack, int size); 194: 195: void * obstack_copy (struct obstack *obstack, void *address, int size); 196: void * obstack_copy0 (struct obstack *obstack, void *address, int size); 197: 198: void obstack_free (struct obstack *obstack, void *block); 199: 200: void obstack_blank (struct obstack *obstack, int size); 201: 202: void obstack_grow (struct obstack *obstack, void *data, int size); 203: void obstack_grow0 (struct obstack *obstack, void *data, int size); 204: 205: void obstack_1grow (struct obstack *obstack, int data_char); 206: void obstack_ptr_grow (struct obstack *obstack, void *data); 207: void obstack_int_grow (struct obstack *obstack, int data); 208: 209: void * obstack_finish (struct obstack *obstack); 210: 211: int obstack_object_size (struct obstack *obstack); 212: 213: int obstack_room (struct obstack *obstack); 214: void obstack_1grow_fast (struct obstack *obstack, int data_char); 215: void obstack_ptr_grow_fast (struct obstack *obstack, void *data); 216: void obstack_int_grow_fast (struct obstack *obstack, int data); 217: void obstack_blank_fast (struct obstack *obstack, int size); 218: 219: void * obstack_base (struct obstack *obstack); 220: void * obstack_next_free (struct obstack *obstack); 221: int obstack_alignment_mask (struct obstack *obstack); 222: int obstack_chunk_size (struct obstack *obstack); 223: 224: #endif /* __STDC__ */ 225: 226: /* Non-ANSI C cannot really support alternative functions for these macros, 227: so we do not declare them. */ 228: 229: /* Pointer to beginning of object being allocated or to be allocated next. 230: Note that this might not be the final address of the object 231: because a new chunk might be needed to hold the final size. */ 232: 233: #define obstack_base(h) ((h)->object_base) 234: 235: /* Size for allocating ordinary chunks. */ 236: 237: #define obstack_chunk_size(h) ((h)->chunk_size) 238: 239: /* Pointer to next byte not yet allocated in current chunk. */ 240: 241: #define obstack_next_free(h) ((h)->next_free) 242: 243: /* Mask specifying low bits that should be clear in address of an object. */ 244: 245: #define obstack_alignment_mask(h) ((h)->alignment_mask) 246: 247: #define obstack_init(h) \ 248: _obstack_begin ((h), 0, 0, \ 1.1.1.2 ! root 249: (void *(*) ()) obstack_chunk_alloc, (void (*) ()) obstack_chunk_free) 1.1 root 250: 251: #define obstack_begin(h, size) \ 252: _obstack_begin ((h), (size), 0, \ 1.1.1.2 ! root 253: (void *(*) ()) obstack_chunk_alloc, (void (*) ()) obstack_chunk_free) ! 254: ! 255: #define obstack_specify_allocation(h, size, alignment, chunkfun, freefun) \ ! 256: _obstack_begin ((h), (size), (alignment), \ ! 257: (void *(*) ()) (chunkfun), (void (*) ()) (freefun)) ! 258: ! 259: #define obstack_specify_allocation_with_arg(h, size, alignment, chunkfun, freefun, arg) \ ! 260: _obstack_begin_1 ((h), (size), (alignment), \ ! 261: (void *(*) ()) (chunkfun), (void (*) ()) (freefun), (arg)) 1.1 root 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: bcopy (where, __o->next_free, __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: bcopy (where, __o->next_free, __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: bcopy (where, (h)->next_free, (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: bcopy (where, (h)->next_free, (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.