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 19 In other words, you are welcome to use, share and improve this program. 20 You are forbidden to forbid anyone else to use, share and improve 21 what you give them. Help stamp out software-hoarding! */ 22 23 24 /* Summary: 25 26 All the apparent functions defined here are macros. The idea 27 is that you would use these pre-tested macros to solve a 28 very specific set of problems, and they would run fast. 29 Caution: no side-effects in arguments please!! They may be 30 evaluated MANY times!! 31 32 These macros operate a stack of objects. Each object starts life 33 small, and may grow to maturity. (Consider building a word syllable 34 by syllable.) An object can move while it is growing. Once it has 35 been "finished" it never changes address again. So the "top of the 36 stack" is typically an immature growing object, while the rest of the 37 stack is of mature, fixed size and fixed address objects. 38 39 These routines grab large chunks of memory, using a function you 40 supply, called `obstack_chunk_alloc'. On occasion, they free chunks, 41 by calling `obstack_chunk_free'. You must define them and declare 42 them before using any obstack macros. 43 44 Each independent stack is represented by a `struct obstack'. 45 Each of the obstack macros expects a pointer to such a structure 46 as the first argument. 47 48 One motivation for this package is the problem of growing char strings 49 in symbol tables. Unless you are "fascist pig with a read-only mind" 50 [Gosper's immortal quote from HAKMEM item 154, out of context] you 51 would not like to put any arbitrary upper limit on the length of your 52 symbols. 53 54 In practice this often means you will build many short symbols and a 55 few long symbols. At the time you are reading a symbol you don't know 56 how long it is. One traditional method is to read a symbol into a 57 buffer, realloc()ating the buffer every time you try to read a symbol 58 that is longer than the buffer. This is beaut, but you still will 59 want to copy the symbol from the buffer to a more permanent 60 symbol-table entry say about half the time. 61 62 With obstacks, you can work differently. Use one obstack for all symbol 63 names. As you read a symbol, grow the name in the obstack gradually. 64 When the name is complete, finalize it. Then, if the symbol exists already, 65 free the newly read name. 66 67 The way we do this is to take a large chunk, allocating memory from 68 low addresses. When you want to build a symbol in the chunk you just 69 add chars above the current "high water mark" in the chunk. When you 70 have finished adding chars, because you got to the end of the symbol, 71 you know how long the chars are, and you can create a new object. 72 Mostly the chars will not burst over the highest address of the chunk, 73 because you would typically expect a chunk to be (say) 100 times as 74 long as an average object. 75 76 In case that isn't clear, when we have enough chars to make up 77 the object, THEY ARE ALREADY CONTIGUOUS IN THE CHUNK (guaranteed) 78 so we just point to it where it lies. No moving of chars is 79 needed and this is the second win: potentially long strings need 80 never be explicitly shuffled. Once an object is formed, it does not 81 change its address during its lifetime. 82 83 When the chars burst over a chunk boundary, we allocate a larger 84 chunk, and then copy the partly formed object from the end of the old 85 chunk to the beginning of the new larger chunk. We then carry on 86 accreting characters to the end of the object as we normally would. 87 88 A special macro is provided to add a single char at a time to a 89 growing object. This allows the use of register variables, which 90 break the ordinary 'growth' macro. 91 92 Summary: 93 We allocate large chunks. 94 We carve out one object at a time from the current chunk. 95 Once carved, an object never moves. 96 We are free to append data of any size to the currently 97 growing object. 98 Exactly one object is growing in an obstack at any one time. 99 You can run one obstack per control block. 100 You may have as many control blocks as you dare. 101 Because of the way we do it, you can `unwind' a obstack 102 back to a previous state. (You may remove objects much 103 as you would with a stack.) 104 */ 105 106 107 /* Don't do the contents of this file more than once. */ 108 109 #ifndef __OBSTACKS__ 110 #define __OBSTACKS__ 111 112 /* We use subtraction of (char *)0 instead of casting to int 113 because on word-addressable machines a simple cast to int 114 may ignore the byte-within-word field of the pointer. */ 115 116 #ifndef __PTR_TO_INT 117 #define __PTR_TO_INT(P) ((P) - (char *)0) 118 #endif 119 120 #ifndef __INT_TO_PTR 121 #define __INT_TO_PTR(P) ((P) + (char *)0) 122 #endif 123 124 struct _obstack_chunk /* Lives at front of each chunk. */ 125 { 126 char *limit; /* 1 past end of this chunk */ 127 struct _obstack_chunk *prev; /* address of prior chunk or NULL */ 128 char contents[4]; /* objects begin here */ 129 }; 130 131 struct obstack /* control current object in current chunk */ 132 { 133 long chunk_size; /* preferred size to allocate chunks in */ 134 struct _obstack_chunk* chunk; /* address of current struct obstack_chunk */ 135 char *object_base; /* address of object we are building */ 136 char *next_free; /* where to add next char to current object */ 137 char *chunk_limit; /* address of char after current chunk */ 138 int temp; /* Temporary for some macros. */ 139 int alignment_mask; /* Mask of alignment for each object. */ 140 struct _obstack_chunk *(*chunkfun) (); /* User's fcn to allocate a chunk. */ 141 void (*freefun) (); /* User's function to free a chunk. */ 142 }; 143 144 #ifdef __STDC__ 145 146 /* Do the function-declarations after the structs 147 but before defining the macros. */ 148 149 void obstack_init (struct obstack *obstack); 150 151 void * obstack_alloc (struct obstack *obstack, int size); 152 153 void * obstack_copy (struct obstack *obstack, void *address, int size); 154 void * obstack_copy0 (struct obstack *obstack, void *address, int size); 155 156 void obstack_free (struct obstack *obstack, void *block); 157 158 void obstack_blank (struct obstack *obstack, int size); 159 160 void obstack_grow (struct obstack *obstack, void *data, int size); 161 void obstack_grow0 (struct obstack *obstack, void *data, int size); 162 163 void obstack_1grow (struct obstack *obstack, int data_char); 164 void obstack_ptr_grow (struct obstack *obstack, void *data); 165 void obstack_int_grow (struct obstack *obstack, int data); 166 167 void * obstack_finish (struct obstack *obstack); 168 169 int obstack_object_size (struct obstack *obstack); 170 171 int obstack_room (struct obstack *obstack); 172 void obstack_1grow_fast (struct obstack *obstack, int data_char); 173 void obstack_ptr_grow_fast (struct obstack *obstack, void *data); 174 void obstack_int_grow_fast (struct obstack *obstack, int data); 175 void obstack_blank_fast (struct obstack *obstack, int size); 176 177 void * obstack_base (struct obstack *obstack); 178 void * obstack_next_free (struct obstack *obstack); 179 int obstack_alignment_mask (struct obstack *obstack); 180 int obstack_chunk_size (struct obstack *obstack); 181 182 #endif /* __STDC__ */ 183 184 /* Non-ANSI C cannot really support alternative functions for these macros, 185 so we do not declare them. */ 186 187 /* Pointer to beginning of object being allocated or to be allocated next. 188 Note that this might not be the final address of the object 189 because a new chunk might be needed to hold the final size. */ 190 191 #define obstack_base(h) ((h)->object_base) 192 193 /* Size for allocating ordinary chunks. */ 194 195 #define obstack_chunk_size(h) ((h)->chunk_size) 196 197 /* Pointer to next byte not yet allocated in current chunk. */ 198 199 #define obstack_next_free(h) ((h)->next_free) 200 201 /* Mask specifying low bits that should be clear in address of an object. */ 202 203 #define obstack_alignment_mask(h) ((h)->alignment_mask) 204 205 #define obstack_init(h) \ 206 _obstack_begin ((h), 0, 0, obstack_chunk_alloc, obstack_chunk_free) 207 208 #define obstack_begin(h, size) \ 209 _obstack_begin ((h), (size), 0, obstack_chunk_alloc, obstack_chunk_free) 210 211 #define obstack_1grow_fast(h,achar) (*((h)->next_free)++ = achar) 212 213 #define obstack_blank_fast(h,n) ((h)->next_free += (n)) 214 215 #if defined (__GNUC__) && defined (__STDC__) 216 217 /* For GNU C, if not -traditional, 218 we can define these macros to compute all args only once 219 without using a global variable. 220 Also, we can avoid using the `temp' slot, to make faster code. */ 221 222 #define obstack_object_size(OBSTACK) \ 223 ({ struct obstack *__o = (OBSTACK); \ 224 (unsigned) (__o->next_free - __o->object_base); }) 225 226 #define obstack_room(OBSTACK) \ 227 ({ struct obstack *__o = (OBSTACK); \ 228 (unsigned) (__o->chunk_limit - __o->next_free); }) 229 230 #define obstack_grow(OBSTACK,where,length) \ 231 ({ struct obstack *__o = (OBSTACK); \ 232 int __len = (length); \ 233 ((__o->next_free + __len > __o->chunk_limit) \ 234 ? _obstack_newchunk (__o, __len) : 0); \ 235 bcopy (where, __o->next_free, __len); \ 236 __o->next_free += __len; \ 237 (void) 0; }) 238 239 #define obstack_grow0(OBSTACK,where,length) \ 240 ({ struct obstack *__o = (OBSTACK); \ 241 int __len = (length); \ 242 ((__o->next_free + __len + 1 > __o->chunk_limit) \ 243 ? _obstack_newchunk (__o, __len + 1) : 0), \ 244 bcopy (where, __o->next_free, __len), \ 245 __o->next_free += __len, \ 246 *(__o->next_free)++ = 0; \ 247 (void) 0; }) 248 249 #define obstack_1grow(OBSTACK,datum) \ 250 ({ struct obstack *__o = (OBSTACK); \ 251 ((__o->next_free + 1 > __o->chunk_limit) \ 252 ? _obstack_newchunk (__o, 1) : 0), \ 253 *(__o->next_free)++ = (datum); \ 254 (void) 0; }) 255 256 /* These assume that the obstack alignment is good enough for pointers or ints, 257 and that the data added so far to the current object 258 shares that much alignment. */ 259 260 #define obstack_ptr_grow(OBSTACK,datum) \ 261 ({ struct obstack *__o = (OBSTACK); \ 262 ((__o->next_free + sizeof (void *) > __o->chunk_limit) \ 263 ? _obstack_newchunk (__o, sizeof (void *)) : 0), \ 264 *((void **)__o->next_free)++ = ((void *)datum); \ 265 (void) 0; }) 266 267 #define obstack_int_grow(OBSTACK,datum) \ 268 ({ struct obstack *__o = (OBSTACK); \ 269 ((__o->next_free + sizeof (int) > __o->chunk_limit) \ 270 ? _obstack_newchunk (__o, sizeof (int)) : 0), \ 271 *((int *)__o->next_free)++ = ((int)datum); \ 272 (void) 0; }) 273 274 #define obstack_ptr_grow_fast(h,aptr) (*((void **)(h)->next_free)++ = (void *)aptr) 275 #define obstack_int_grow_fast(h,aint) (*((int *)(h)->next_free)++ = (int)aint) 276 277 #define obstack_blank(OBSTACK,length) \ 278 ({ struct obstack *__o = (OBSTACK); \ 279 int __len = (length); \ 280 ((__o->next_free + __len > __o->chunk_limit) \ 281 ? _obstack_newchunk (__o, __len) : 0); \ 282 __o->next_free += __len; \ 283 (void) 0; }) 284 285 #define obstack_alloc(OBSTACK,length) \ 286 ({ struct obstack *__h = (OBSTACK); \ 287 obstack_blank (__h, (length)); \ 288 obstack_finish (__h); }) 289 290 #define obstack_copy(OBSTACK,where,length) \ 291 ({ struct obstack *__h = (OBSTACK); \ 292 obstack_grow (__h, (where), (length)); \ 293 obstack_finish (__h); }) 294 295 #define obstack_copy0(OBSTACK,where,length) \ 296 ({ struct obstack *__h = (OBSTACK); \ 297 obstack_grow0 (__h, (where), (length)); \ 298 obstack_finish (__h); }) 299 300 #define obstack_finish(OBSTACK) \ 301 ({ struct obstack *__o = (OBSTACK); \ 302 void *value = (void *) __o->object_base; \ 303 __o->next_free \ 304 = __INT_TO_PTR ((__PTR_TO_INT (__o->next_free)+__o->alignment_mask)\ 305 & ~ (__o->alignment_mask)); \ 306 ((__o->next_free - (char *)__o->chunk \ 307 > __o->chunk_limit - (char *)__o->chunk) \ 308 ? (__o->next_free = __o->chunk_limit) : 0); \ 309 __o->object_base = __o->next_free; \ 310 value; }) 311 312 #define obstack_free(OBSTACK, OBJ) \ 313 ({ struct obstack *__o = (OBSTACK); \ 314 void *__obj = (OBJ); \ 315 if (__obj >= (void *)__o->chunk && __obj < (void *)__o->chunk_limit) \ 316 __o->next_free = __o->object_base = __obj; \ 317 else (obstack_free) (__o, __obj); }) 318 319 #else /* not __GNUC__ or not __STDC__ */ 320 321 /* The non-GNU macros copy the obstack-pointer into this global variable 322 to avoid multiple evaluation. */ 323 324 extern struct obstack *_obstack; 325 326 #define obstack_object_size(h) \ 327 (unsigned) (_obstack = (h), (h)->next_free - (h)->object_base) 328 329 #define obstack_room(h) \ 330 (unsigned) (_obstack = (h), (h)->chunk_limit - (h)->next_free) 331 332 #define obstack_grow(h,where,length) \ 333 ( (h)->temp = (length), \ 334 (((h)->next_free + (h)->temp > (h)->chunk_limit) \ 335 ? _obstack_newchunk ((h), (h)->temp) : 0), \ 336 bcopy (where, (h)->next_free, (h)->temp), \ 337 (h)->next_free += (h)->temp) 338 339 #define obstack_grow0(h,where,length) \ 340 ( (h)->temp = (length), \ 341 (((h)->next_free + (h)->temp + 1 > (h)->chunk_limit) \ 342 ? _obstack_newchunk ((h), (h)->temp + 1) : 0), \ 343 bcopy (where, (h)->next_free, (h)->temp), \ 344 (h)->next_free += (h)->temp, \ 345 *((h)->next_free)++ = 0) 346 347 #define obstack_1grow(h,datum) \ 348 ( (((h)->next_free + 1 > (h)->chunk_limit) \ 349 ? _obstack_newchunk ((h), 1) : 0), \ 350 *((h)->next_free)++ = (datum)) 351 352 #define obstack_ptr_grow(h,datum) \ 353 ( (((h)->next_free + sizeof (char *) > (h)->chunk_limit) \ 354 ? _obstack_newchunk ((h), sizeof (char *)) : 0), \ 355 *((char **)(h)->next_free)++ = ((char *)datum)) 356 357 #define obstack_int_grow(h,datum) \ 358 ( (((h)->next_free + sizeof (int) > (h)->chunk_limit) \ 359 ? _obstack_newchunk ((h), sizeof (int)) : 0), \ 360 *((int *)(h)->next_free)++ = ((int)datum)) 361 362 #define obstack_ptr_grow_fast(h,aptr) (*((char **)(h)->next_free)++ = (char *)aptr) 363 #define obstack_int_grow_fast(h,aint) (*((int *)(h)->next_free)++ = (int)aint) 364 365 #define obstack_blank(h,length) \ 366 ( (h)->temp = (length), \ 367 (((h)->next_free + (h)->temp > (h)->chunk_limit) \ 368 ? _obstack_newchunk ((h), (h)->temp) : 0), \ 369 (h)->next_free += (h)->temp) 370 371 #define obstack_alloc(h,length) \ 372 (obstack_blank ((h), (length)), obstack_finish ((h))) 373 374 #define obstack_copy(h,where,length) \ 375 (obstack_grow ((h), (where), (length)), obstack_finish ((h))) 376 377 #define obstack_copy0(h,where,length) \ 378 (obstack_grow0 ((h), (where), (length)), obstack_finish ((h))) 379 380 #define obstack_finish(h) \ 381 ( (h)->temp = __PTR_TO_INT ((h)->object_base), \ 382 (h)->next_free \ 383 = __INT_TO_PTR ((__PTR_TO_INT ((h)->next_free)+(h)->alignment_mask) \ 384 & ~ ((h)->alignment_mask)), \ 385 (((h)->next_free - (char *)(h)->chunk \ 386 > (h)->chunk_limit - (char *)(h)->chunk) \ 387 ? ((h)->next_free = (h)->chunk_limit) : 0), \ 388 (h)->object_base = (h)->next_free, \ 389 __INT_TO_PTR ((h)->temp)) 390 391 #ifdef __STDC__ 392 #define obstack_free(h,obj) \ 393 ( (h)->temp = (char *)(obj) - (char *) (h)->chunk, \ 394 (((h)->temp >= 0 && (h)->temp < (h)->chunk_limit - (char *) (h)->chunk)\ 395 ? (int) ((h)->next_free = (h)->object_base \ 396 = (h)->temp + (char *) (h)->chunk) \ 397 : ((obstack_free) ((h), (h)->temp + (char *) (h)->chunk), 0))) 398 #else 399 #define obstack_free(h,obj) \ 400 ( (h)->temp = (char *)(obj) - (char *) (h)->chunk, \ 401 (((h)->temp >= 0 && (h)->temp < (h)->chunk_limit - (char *) (h)->chunk)\ 402 ? (int) ((h)->next_free = (h)->object_base \ 403 = (h)->temp + (char *) (h)->chunk) \ 404 : (int) _obstack_free ((h), (h)->temp + (char *) (h)->chunk))) 405 #endif 406 407 #endif /* not __GNUC__ or not __STDC__ */ 408 409 #endif /* not __OBSTACKS__ */ 410 411