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