1 /* obstack.h - object stack macros 2 Copyright (C) 1988 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 1, 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' a 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 struct _obstack_chunk /* Lives at front of each chunk. */ 119 { 120 char *limit; /* 1 past end of this chunk */ 121 struct _obstack_chunk *prev; /* address of prior chunk or NULL */ 122 char contents[4]; /* objects begin here */ 123 }; 124 125 struct obstack /* control current object in current chunk */ 126 { 127 long chunk_size; /* preferred size to allocate chunks in */ 128 struct _obstack_chunk* chunk; /* address of current struct obstack_chunk */ 129 char *object_base; /* address of object we are building */ 130 char *next_free; /* where to add next char to current object */ 131 char *chunk_limit; /* address of char after current chunk */ 132 int temp; /* Temporary for some macros. */ 133 int alignment_mask; /* Mask of alignment for each object. */ 134 struct _obstack_chunk *(*chunkfun) (); /* User's fcn to allocate a chunk. */ 135 void (*freefun) (); /* User's function to free a chunk. */ 136 }; 137 138 /* Declare the external functions we use; they are in obstack.c. */ 139 140 #ifdef __STDC__ 141 extern void _obstack_newchunk (struct obstack *, int); 142 extern void _obstack_free (struct obstack *, void *); 143 extern void _obstack_begin (struct obstack *, int, int, 144 void *(*) (), void (*) ()); 145 #else 146 extern void _obstack_newchunk (); 147 extern void _obstack_free (); 148 extern void _obstack_begin (); 149 #endif 150 151 #ifdef __STDC__ 152 153 /* Do the function-declarations after the structs 154 but before defining the macros. */ 155 156 void obstack_init (struct obstack *obstack); 157 158 void * obstack_alloc (struct obstack *obstack, int size); 159 160 void * obstack_copy (struct obstack *obstack, void *address, int size); 161 void * obstack_copy0 (struct obstack *obstack, void *address, int size); 162 163 void obstack_free (struct obstack *obstack, void *block); 164 165 void obstack_blank (struct obstack *obstack, int size); 166 167 void obstack_grow (struct obstack *obstack, void *data, int size); 168 void obstack_grow0 (struct obstack *obstack, void *data, int size); 169 170 void obstack_1grow (struct obstack *obstack, int data_char); 171 void obstack_ptr_grow (struct obstack *obstack, void *data); 172 void obstack_int_grow (struct obstack *obstack, int data); 173 174 void * obstack_finish (struct obstack *obstack); 175 176 int obstack_object_size (struct obstack *obstack); 177 178 int obstack_room (struct obstack *obstack); 179 void obstack_1grow_fast (struct obstack *obstack, int data_char); 180 void obstack_ptr_grow_fast (struct obstack *obstack, void *data); 181 void obstack_int_grow_fast (struct obstack *obstack, int data); 182 void obstack_blank_fast (struct obstack *obstack, int size); 183 184 void * obstack_base (struct obstack *obstack); 185 void * obstack_next_free (struct obstack *obstack); 186 int obstack_alignment_mask (struct obstack *obstack); 187 int obstack_chunk_size (struct obstack *obstack); 188 189 #endif /* __STDC__ */ 190 191 /* Non-ANSI C cannot really support alternative functions for these macros, 192 so we do not declare them. */ 193 194 /* Pointer to beginning of object being allocated or to be allocated next. 195 Note that this might not be the final address of the object 196 because a new chunk might be needed to hold the final size. */ 197 198 #define obstack_base(h) ((h)->object_base) 199 200 /* Size for allocating ordinary chunks. */ 201 202 #define obstack_chunk_size(h) ((h)->chunk_size) 203 204 /* Pointer to next byte not yet allocated in current chunk. */ 205 206 #define obstack_next_free(h) ((h)->next_free) 207 208 /* Mask specifying low bits that should be clear in address of an object. */ 209 210 #define obstack_alignment_mask(h) ((h)->alignment_mask) 211 212 #define obstack_init(h) \ 213 _obstack_begin ((h), 0, 0, \ 214 (void *(*) ()) obstack_chunk_alloc, obstack_chunk_free) 215 216 #define obstack_begin(h, size) \ 217 _obstack_begin ((h), (size), 0, \ 218 (void *(*) ()) obstack_chunk_alloc, obstack_chunk_free) 219 220 #define obstack_1grow_fast(h,achar) (*((h)->next_free)++ = achar) 221 222 #define obstack_blank_fast(h,n) ((h)->next_free += (n)) 223 224 #if defined (__GNUC__) && defined (__STDC__) 225 226 /* For GNU C, if not -traditional, 227 we can define these macros to compute all args only once 228 without using a global variable. 229 Also, we can avoid using the `temp' slot, to make faster code. */ 230 231 #define obstack_object_size(OBSTACK) \ 232 ({ struct obstack *__o = (OBSTACK); \ 233 (unsigned) (__o->next_free - __o->object_base); }) 234 235 #define obstack_room(OBSTACK) \ 236 ({ struct obstack *__o = (OBSTACK); \ 237 (unsigned) (__o->chunk_limit - __o->next_free); }) 238 239 /* Note that the call to _obstack_newchunk is enclosed in (..., 0) 240 so that we can avoid having void expressions 241 in the arms of the conditional expression. 242 Casting the third operand to void was tried before, 243 but some compilers won't accept it. */ 244 #define obstack_grow(OBSTACK,where,length) \ 245 ({ struct obstack *__o = (OBSTACK); \ 246 int __len = (length); \ 247 ((__o->next_free + __len > __o->chunk_limit) \ 248 ? (_obstack_newchunk (__o, __len), 0) : 0); \ 249 bcopy (where, __o->next_free, __len); \ 250 __o->next_free += __len; \ 251 (void) 0; }) 252 253 #define obstack_grow0(OBSTACK,where,length) \ 254 ({ struct obstack *__o = (OBSTACK); \ 255 int __len = (length); \ 256 ((__o->next_free + __len + 1 > __o->chunk_limit) \ 257 ? (_obstack_newchunk (__o, __len + 1), 0) : 0), \ 258 bcopy (where, __o->next_free, __len), \ 259 __o->next_free += __len, \ 260 *(__o->next_free)++ = 0; \ 261 (void) 0; }) 262 263 #define obstack_1grow(OBSTACK,datum) \ 264 ({ struct obstack *__o = (OBSTACK); \ 265 ((__o->next_free + 1 > __o->chunk_limit) \ 266 ? (_obstack_newchunk (__o, 1), 0) : 0), \ 267 *(__o->next_free)++ = (datum); \ 268 (void) 0; }) 269 270 /* These assume that the obstack alignment is good enough for pointers or ints, 271 and that the data added so far to the current object 272 shares that much alignment. */ 273 274 #define obstack_ptr_grow(OBSTACK,datum) \ 275 ({ struct obstack *__o = (OBSTACK); \ 276 ((__o->next_free + sizeof (void *) > __o->chunk_limit) \ 277 ? (_obstack_newchunk (__o, sizeof (void *)), 0) : 0), \ 278 *((void **)__o->next_free)++ = ((void *)datum); \ 279 (void) 0; }) 280 281 #define obstack_int_grow(OBSTACK,datum) \ 282 ({ struct obstack *__o = (OBSTACK); \ 283 ((__o->next_free + sizeof (int) > __o->chunk_limit) \ 284 ? (_obstack_newchunk (__o, sizeof (int)), 0) : 0), \ 285 *((int *)__o->next_free)++ = ((int)datum); \ 286 (void) 0; }) 287 288 #define obstack_ptr_grow_fast(h,aptr) (*((void **)(h)->next_free)++ = (void *)aptr) 289 #define obstack_int_grow_fast(h,aint) (*((int *)(h)->next_free)++ = (int)aint) 290 291 #define obstack_blank(OBSTACK,length) \ 292 ({ struct obstack *__o = (OBSTACK); \ 293 int __len = (length); \ 294 ((__o->chunk_limit - __o->next_free < __len) \ 295 ? (_obstack_newchunk (__o, __len), 0) : 0); \ 296 __o->next_free += __len; \ 297 (void) 0; }) 298 299 #define obstack_alloc(OBSTACK,length) \ 300 ({ struct obstack *__h = (OBSTACK); \ 301 obstack_blank (__h, (length)); \ 302 obstack_finish (__h); }) 303 304 #define obstack_copy(OBSTACK,where,length) \ 305 ({ struct obstack *__h = (OBSTACK); \ 306 obstack_grow (__h, (where), (length)); \ 307 obstack_finish (__h); }) 308 309 #define obstack_copy0(OBSTACK,where,length) \ 310 ({ struct obstack *__h = (OBSTACK); \ 311 obstack_grow0 (__h, (where), (length)); \ 312 obstack_finish (__h); }) 313 314 #define obstack_finish(OBSTACK) \ 315 ({ struct obstack *__o = (OBSTACK); \ 316 void *value = (void *) __o->object_base; \ 317 __o->next_free \ 318 = __INT_TO_PTR ((__PTR_TO_INT (__o->next_free)+__o->alignment_mask)\ 319 & ~ (__o->alignment_mask)); \ 320 ((__o->next_free - (char *)__o->chunk \ 321 > __o->chunk_limit - (char *)__o->chunk) \ 322 ? (__o->next_free = __o->chunk_limit) : 0); \ 323 __o->object_base = __o->next_free; \ 324 value; }) 325 326 #define obstack_free(OBSTACK, OBJ) \ 327 ({ struct obstack *__o = (OBSTACK); \ 328 void *__obj = (OBJ); \ 329 if (__obj > (void *)__o->chunk && __obj < (void *)__o->chunk_limit) \ 330 __o->next_free = __o->object_base = __obj; \ 331 else (obstack_free) (__o, __obj); }) 332 333 #else /* not __GNUC__ or not __STDC__ */ 334 335 #define obstack_object_size(h) \ 336 (unsigned) ((h)->next_free - (h)->object_base) 337 338 #define obstack_room(h) \ 339 (unsigned) ((h)->chunk_limit - (h)->next_free) 340 341 #define obstack_grow(h,where,length) \ 342 ( (h)->temp = (length), \ 343 (((h)->next_free + (h)->temp > (h)->chunk_limit) \ 344 ? (_obstack_newchunk ((h), (h)->temp), 0) : 0), \ 345 bcopy (where, (h)->next_free, (h)->temp), \ 346 (h)->next_free += (h)->temp) 347 348 #define obstack_grow0(h,where,length) \ 349 ( (h)->temp = (length), \ 350 (((h)->next_free + (h)->temp + 1 > (h)->chunk_limit) \ 351 ? (_obstack_newchunk ((h), (h)->temp + 1), 0) : 0), \ 352 bcopy (where, (h)->next_free, (h)->temp), \ 353 (h)->next_free += (h)->temp, \ 354 *((h)->next_free)++ = 0) 355 356 #define obstack_1grow(h,datum) \ 357 ( (((h)->next_free + 1 > (h)->chunk_limit) \ 358 ? (_obstack_newchunk ((h), 1), 0) : 0), \ 359 *((h)->next_free)++ = (datum)) 360 361 #define obstack_ptr_grow(h,datum) \ 362 ( (((h)->next_free + sizeof (char *) > (h)->chunk_limit) \ 363 ? (_obstack_newchunk ((h), sizeof (char *)), 0) : 0), \ 364 *((char **)(((h)->next_free+=sizeof(char *))-sizeof(char *))) = ((char *)datum)) 365 366 #define obstack_int_grow(h,datum) \ 367 ( (((h)->next_free + sizeof (int) > (h)->chunk_limit) \ 368 ? (_obstack_newchunk ((h), sizeof (int)), 0) : 0), \ 369 *((int *)(((h)->next_free+=sizeof(int))-sizeof(int))) = ((int)datum)) 370 371 #define obstack_ptr_grow_fast(h,aptr) (*((char **)(h)->next_free)++ = (char *)aptr) 372 #define obstack_int_grow_fast(h,aint) (*((int *)(h)->next_free)++ = (int)aint) 373 374 #define obstack_blank(h,length) \ 375 ( (h)->temp = (length), \ 376 (((h)->chunk_limit - (h)->next_free < (h)->temp) \ 377 ? (_obstack_newchunk ((h), (h)->temp), 0) : 0), \ 378 (h)->next_free += (h)->temp) 379 380 #define obstack_alloc(h,length) \ 381 (obstack_blank ((h), (length)), obstack_finish ((h))) 382 383 #define obstack_copy(h,where,length) \ 384 (obstack_grow ((h), (where), (length)), obstack_finish ((h))) 385 386 #define obstack_copy0(h,where,length) \ 387 (obstack_grow0 ((h), (where), (length)), obstack_finish ((h))) 388 389 #define obstack_finish(h) \ 390 ( (h)->temp = __PTR_TO_INT ((h)->object_base), \ 391 (h)->next_free \ 392 = __INT_TO_PTR ((__PTR_TO_INT ((h)->next_free)+(h)->alignment_mask) \ 393 & ~ ((h)->alignment_mask)), \ 394 (((h)->next_free - (char *)(h)->chunk \ 395 > (h)->chunk_limit - (char *)(h)->chunk) \ 396 ? ((h)->next_free = (h)->chunk_limit) : 0), \ 397 (h)->object_base = (h)->next_free, \ 398 __INT_TO_PTR ((h)->temp)) 399 400 #ifdef __STDC__ 401 #define obstack_free(h,obj) \ 402 ( (h)->temp = (char *)(obj) - (char *) (h)->chunk, \ 403 (((h)->temp >= 0 && (h)->temp < (h)->chunk_limit - (char *) (h)->chunk)\ 404 ? (int) ((h)->next_free = (h)->object_base \ 405 = (h)->temp + (char *) (h)->chunk) \ 406 : (((obstack_free) ((h), (h)->temp + (char *) (h)->chunk), 0), 0))) 407 #else 408 #define obstack_free(h,obj) \ 409 ( (h)->temp = (char *)(obj) - (char *) (h)->chunk, \ 410 (((h)->temp >= 0 && (h)->temp < (h)->chunk_limit - (char *) (h)->chunk)\ 411 ? (int) ((h)->next_free = (h)->object_base \ 412 = (h)->temp + (char *) (h)->chunk) \ 413 : (_obstack_free ((h), (h)->temp + (char *) (h)->chunk), 0))) 414 #endif 415 416 #endif /* not __GNUC__ or not __STDC__ */ 417 418 #endif /* not __OBSTACKS__ */ 419