]> git.ipfire.org Git - thirdparty/glibc.git/blob - malloc/obstack.h
Update copyright notices with scripts/update-copyrights
[thirdparty/glibc.git] / malloc / obstack.h
1 /* obstack.h - object stack macros
2 Copyright (C) 1988-2014 Free Software Foundation, Inc.
3 This file is part of the GNU C Library.
4
5 The GNU C Library is free software; you can redistribute it and/or
6 modify it under the terms of the GNU Lesser General Public
7 License as published by the Free Software Foundation; either
8 version 2.1 of the License, or (at your option) any later version.
9
10 The GNU C Library is distributed in the hope that it will be useful,
11 but WITHOUT ANY WARRANTY; without even the implied warranty of
12 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
13 Lesser General Public License for more details.
14
15 You should have received a copy of the GNU Lesser General Public
16 License along with the GNU C Library; if not, see
17 <http://www.gnu.org/licenses/>. */
18
19 /* Summary:
20
21 All the apparent functions defined here are macros. The idea
22 is that you would use these pre-tested macros to solve a
23 very specific set of problems, and they would run fast.
24 Caution: no side-effects in arguments please!! They may be
25 evaluated MANY times!!
26
27 These macros operate a stack of objects. Each object starts life
28 small, and may grow to maturity. (Consider building a word syllable
29 by syllable.) An object can move while it is growing. Once it has
30 been "finished" it never changes address again. So the "top of the
31 stack" is typically an immature growing object, while the rest of the
32 stack is of mature, fixed size and fixed address objects.
33
34 These routines grab large chunks of memory, using a function you
35 supply, called `obstack_chunk_alloc'. On occasion, they free chunks,
36 by calling `obstack_chunk_free'. You must define them and declare
37 them before using any obstack macros.
38
39 Each independent stack is represented by a `struct obstack'.
40 Each of the obstack macros expects a pointer to such a structure
41 as the first argument.
42
43 One motivation for this package is the problem of growing char strings
44 in symbol tables. Unless you are "fascist pig with a read-only mind"
45 --Gosper's immortal quote from HAKMEM item 154, out of context--you
46 would not like to put any arbitrary upper limit on the length of your
47 symbols.
48
49 In practice this often means you will build many short symbols and a
50 few long symbols. At the time you are reading a symbol you don't know
51 how long it is. One traditional method is to read a symbol into a
52 buffer, realloc()ating the buffer every time you try to read a symbol
53 that is longer than the buffer. This is beaut, but you still will
54 want to copy the symbol from the buffer to a more permanent
55 symbol-table entry say about half the time.
56
57 With obstacks, you can work differently. Use one obstack for all symbol
58 names. As you read a symbol, grow the name in the obstack gradually.
59 When the name is complete, finalize it. Then, if the symbol exists already,
60 free the newly read name.
61
62 The way we do this is to take a large chunk, allocating memory from
63 low addresses. When you want to build a symbol in the chunk you just
64 add chars above the current "high water mark" in the chunk. When you
65 have finished adding chars, because you got to the end of the symbol,
66 you know how long the chars are, and you can create a new object.
67 Mostly the chars will not burst over the highest address of the chunk,
68 because you would typically expect a chunk to be (say) 100 times as
69 long as an average object.
70
71 In case that isn't clear, when we have enough chars to make up
72 the object, THEY ARE ALREADY CONTIGUOUS IN THE CHUNK (guaranteed)
73 so we just point to it where it lies. No moving of chars is
74 needed and this is the second win: potentially long strings need
75 never be explicitly shuffled. Once an object is formed, it does not
76 change its address during its lifetime.
77
78 When the chars burst over a chunk boundary, we allocate a larger
79 chunk, and then copy the partly formed object from the end of the old
80 chunk to the beginning of the new larger chunk. We then carry on
81 accreting characters to the end of the object as we normally would.
82
83 A special macro is provided to add a single char at a time to a
84 growing object. This allows the use of register variables, which
85 break the ordinary 'growth' macro.
86
87 Summary:
88 We allocate large chunks.
89 We carve out one object at a time from the current chunk.
90 Once carved, an object never moves.
91 We are free to append data of any size to the currently
92 growing object.
93 Exactly one object is growing in an obstack at any one time.
94 You can run one obstack per control block.
95 You may have as many control blocks as you dare.
96 Because of the way we do it, you can `unwind' an obstack
97 back to a previous state. (You may remove objects much
98 as you would with a stack.)
99 */
100
101
102 /* Don't do the contents of this file more than once. */
103
104 #ifndef _OBSTACK_H
105 #define _OBSTACK_H 1
106
107 #ifdef __cplusplus
108 extern "C" {
109 #endif
110 \f
111 /* We need the type of a pointer subtraction. If __PTRDIFF_TYPE__ is
112 defined, as with GNU C, use that; that way we don't pollute the
113 namespace with <stddef.h>'s symbols. Otherwise, include <stddef.h>
114 and use ptrdiff_t. */
115
116 #ifdef __PTRDIFF_TYPE__
117 # define PTR_INT_TYPE __PTRDIFF_TYPE__
118 #else
119 # include <stddef.h>
120 # define PTR_INT_TYPE ptrdiff_t
121 #endif
122
123 /* If B is the base of an object addressed by P, return the result of
124 aligning P to the next multiple of A + 1. B and P must be of type
125 char *. A + 1 must be a power of 2. */
126
127 #define __BPTR_ALIGN(B, P, A) ((B) + (((P) - (B) + (A)) & ~(A)))
128
129 /* Similiar to _BPTR_ALIGN (B, P, A), except optimize the common case
130 where pointers can be converted to integers, aligned as integers,
131 and converted back again. If PTR_INT_TYPE is narrower than a
132 pointer (e.g., the AS/400), play it safe and compute the alignment
133 relative to B. Otherwise, use the faster strategy of computing the
134 alignment relative to 0. */
135
136 #define __PTR_ALIGN(B, P, A) \
137 __BPTR_ALIGN (sizeof (PTR_INT_TYPE) < sizeof (void *) ? (B) : (char *) 0, \
138 P, A)
139
140 #include <string.h>
141
142 struct _obstack_chunk /* Lives at front of each chunk. */
143 {
144 char *limit; /* 1 past end of this chunk */
145 struct _obstack_chunk *prev; /* address of prior chunk or NULL */
146 char contents[4]; /* objects begin here */
147 };
148
149 struct obstack /* control current object in current chunk */
150 {
151 long chunk_size; /* preferred size to allocate chunks in */
152 struct _obstack_chunk *chunk; /* address of current struct obstack_chunk */
153 char *object_base; /* address of object we are building */
154 char *next_free; /* where to add next char to current object */
155 char *chunk_limit; /* address of char after current chunk */
156 union
157 {
158 PTR_INT_TYPE tempint;
159 void *tempptr;
160 } temp; /* Temporary for some macros. */
161 int alignment_mask; /* Mask of alignment for each object. */
162 /* These prototypes vary based on `use_extra_arg', and we use
163 casts to the prototypeless function type in all assignments,
164 but having prototypes here quiets -Wstrict-prototypes. */
165 struct _obstack_chunk *(*chunkfun) (void *, long);
166 void (*freefun) (void *, struct _obstack_chunk *);
167 void *extra_arg; /* first arg for chunk alloc/dealloc funcs */
168 unsigned use_extra_arg:1; /* chunk alloc/dealloc funcs take extra arg */
169 unsigned maybe_empty_object:1;/* There is a possibility that the current
170 chunk contains a zero-length object. This
171 prevents freeing the chunk if we allocate
172 a bigger chunk to replace it. */
173 unsigned alloc_failed:1; /* No longer used, as we now call the failed
174 handler on error, but retained for binary
175 compatibility. */
176 };
177
178 /* Declare the external functions we use; they are in obstack.c. */
179
180 extern void _obstack_newchunk (struct obstack *, int);
181 extern int _obstack_begin (struct obstack *, int, int,
182 void *(*) (long), void (*) (void *));
183 extern int _obstack_begin_1 (struct obstack *, int, int,
184 void *(*) (void *, long),
185 void (*) (void *, void *), void *);
186 extern int _obstack_memory_used (struct obstack *);
187
188 void obstack_free (struct obstack *__obstack, void *__glibc_block);
189
190 \f
191 /* Error handler called when `obstack_chunk_alloc' failed to allocate
192 more memory. This can be set to a user defined function which
193 should either abort gracefully or use longjump - but shouldn't
194 return. The default action is to print a message and abort. */
195 extern void (*obstack_alloc_failed_handler) (void);
196
197 /* Exit value used when `print_and_abort' is used. */
198 extern int obstack_exit_failure;
199 \f
200 /* Pointer to beginning of object being allocated or to be allocated next.
201 Note that this might not be the final address of the object
202 because a new chunk might be needed to hold the final size. */
203
204 #define obstack_base(h) ((void *) (h)->object_base)
205
206 /* Size for allocating ordinary chunks. */
207
208 #define obstack_chunk_size(h) ((h)->chunk_size)
209
210 /* Pointer to next byte not yet allocated in current chunk. */
211
212 #define obstack_next_free(h) ((h)->next_free)
213
214 /* Mask specifying low bits that should be clear in address of an object. */
215
216 #define obstack_alignment_mask(h) ((h)->alignment_mask)
217
218 /* To prevent prototype warnings provide complete argument list. */
219 #define obstack_init(h) \
220 _obstack_begin ((h), 0, 0, \
221 (void *(*) (long)) obstack_chunk_alloc, \
222 (void (*) (void *)) obstack_chunk_free)
223
224 #define obstack_begin(h, size) \
225 _obstack_begin ((h), (size), 0, \
226 (void *(*) (long)) obstack_chunk_alloc, \
227 (void (*) (void *)) obstack_chunk_free)
228
229 #define obstack_specify_allocation(h, size, alignment, chunkfun, freefun) \
230 _obstack_begin ((h), (size), (alignment), \
231 (void *(*) (long)) (chunkfun), \
232 (void (*) (void *)) (freefun))
233
234 #define obstack_specify_allocation_with_arg(h, size, alignment, chunkfun, freefun, arg) \
235 _obstack_begin_1 ((h), (size), (alignment), \
236 (void *(*) (void *, long)) (chunkfun), \
237 (void (*) (void *, void *)) (freefun), (arg))
238
239 #define obstack_chunkfun(h, newchunkfun) \
240 ((h) -> chunkfun = (struct _obstack_chunk *(*)(void *, long)) (newchunkfun))
241
242 #define obstack_freefun(h, newfreefun) \
243 ((h) -> freefun = (void (*)(void *, struct _obstack_chunk *)) (newfreefun))
244
245 #define obstack_1grow_fast(h,achar) (*((h)->next_free)++ = (achar))
246
247 #define obstack_blank_fast(h,n) ((h)->next_free += (n))
248
249 #define obstack_memory_used(h) _obstack_memory_used (h)
250 \f
251 #if defined __GNUC__
252 /* NextStep 2.0 cc is really gcc 1.93 but it defines __GNUC__ = 2 and
253 does not implement __extension__. But that compiler doesn't define
254 __GNUC_MINOR__. */
255 # if __GNUC__ < 2 || (__NeXT__ && !__GNUC_MINOR__)
256 # define __extension__
257 # endif
258
259 /* For GNU C, if not -traditional,
260 we can define these macros to compute all args only once
261 without using a global variable.
262 Also, we can avoid using the `temp' slot, to make faster code. */
263
264 # define obstack_object_size(OBSTACK) \
265 __extension__ \
266 ({ struct obstack const *__o = (OBSTACK); \
267 (unsigned) (__o->next_free - __o->object_base); })
268
269 # define obstack_room(OBSTACK) \
270 __extension__ \
271 ({ struct obstack const *__o = (OBSTACK); \
272 (unsigned) (__o->chunk_limit - __o->next_free); })
273
274 # define obstack_make_room(OBSTACK,length) \
275 __extension__ \
276 ({ struct obstack *__o = (OBSTACK); \
277 int __len = (length); \
278 if (__o->chunk_limit - __o->next_free < __len) \
279 _obstack_newchunk (__o, __len); \
280 (void) 0; })
281
282 # define obstack_empty_p(OBSTACK) \
283 __extension__ \
284 ({ struct obstack const *__o = (OBSTACK); \
285 (__o->chunk->prev == 0 \
286 && __o->next_free == __PTR_ALIGN ((char *) __o->chunk, \
287 __o->chunk->contents, \
288 __o->alignment_mask)); })
289
290 # define obstack_grow(OBSTACK,where,length) \
291 __extension__ \
292 ({ struct obstack *__o = (OBSTACK); \
293 int __len = (length); \
294 if (__o->next_free + __len > __o->chunk_limit) \
295 _obstack_newchunk (__o, __len); \
296 memcpy (__o->next_free, where, __len); \
297 __o->next_free += __len; \
298 (void) 0; })
299
300 # define obstack_grow0(OBSTACK,where,length) \
301 __extension__ \
302 ({ struct obstack *__o = (OBSTACK); \
303 int __len = (length); \
304 if (__o->next_free + __len + 1 > __o->chunk_limit) \
305 _obstack_newchunk (__o, __len + 1); \
306 memcpy (__o->next_free, where, __len); \
307 __o->next_free += __len; \
308 *(__o->next_free)++ = 0; \
309 (void) 0; })
310
311 # define obstack_1grow(OBSTACK,datum) \
312 __extension__ \
313 ({ struct obstack *__o = (OBSTACK); \
314 if (__o->next_free + 1 > __o->chunk_limit) \
315 _obstack_newchunk (__o, 1); \
316 obstack_1grow_fast (__o, datum); \
317 (void) 0; })
318
319 /* These assume that the obstack alignment is good enough for pointers
320 or ints, and that the data added so far to the current object
321 shares that much alignment. */
322
323 # define obstack_ptr_grow(OBSTACK,datum) \
324 __extension__ \
325 ({ struct obstack *__o = (OBSTACK); \
326 if (__o->next_free + sizeof (void *) > __o->chunk_limit) \
327 _obstack_newchunk (__o, sizeof (void *)); \
328 obstack_ptr_grow_fast (__o, datum); }) \
329
330 # define obstack_int_grow(OBSTACK,datum) \
331 __extension__ \
332 ({ struct obstack *__o = (OBSTACK); \
333 if (__o->next_free + sizeof (int) > __o->chunk_limit) \
334 _obstack_newchunk (__o, sizeof (int)); \
335 obstack_int_grow_fast (__o, datum); })
336
337 # define obstack_ptr_grow_fast(OBSTACK,aptr) \
338 __extension__ \
339 ({ struct obstack *__o1 = (OBSTACK); \
340 *(const void **) __o1->next_free = (aptr); \
341 __o1->next_free += sizeof (const void *); \
342 (void) 0; })
343
344 # define obstack_int_grow_fast(OBSTACK,aint) \
345 __extension__ \
346 ({ struct obstack *__o1 = (OBSTACK); \
347 *(int *) __o1->next_free = (aint); \
348 __o1->next_free += sizeof (int); \
349 (void) 0; })
350
351 # define obstack_blank(OBSTACK,length) \
352 __extension__ \
353 ({ struct obstack *__o = (OBSTACK); \
354 int __len = (length); \
355 if (__o->chunk_limit - __o->next_free < __len) \
356 _obstack_newchunk (__o, __len); \
357 obstack_blank_fast (__o, __len); \
358 (void) 0; })
359
360 # define obstack_alloc(OBSTACK,length) \
361 __extension__ \
362 ({ struct obstack *__h = (OBSTACK); \
363 obstack_blank (__h, (length)); \
364 obstack_finish (__h); })
365
366 # define obstack_copy(OBSTACK,where,length) \
367 __extension__ \
368 ({ struct obstack *__h = (OBSTACK); \
369 obstack_grow (__h, (where), (length)); \
370 obstack_finish (__h); })
371
372 # define obstack_copy0(OBSTACK,where,length) \
373 __extension__ \
374 ({ struct obstack *__h = (OBSTACK); \
375 obstack_grow0 (__h, (where), (length)); \
376 obstack_finish (__h); })
377
378 /* The local variable is named __o1 to avoid a name conflict
379 when obstack_blank is called. */
380 # define obstack_finish(OBSTACK) \
381 __extension__ \
382 ({ struct obstack *__o1 = (OBSTACK); \
383 void *__value = (void *) __o1->object_base; \
384 if (__o1->next_free == __value) \
385 __o1->maybe_empty_object = 1; \
386 __o1->next_free \
387 = __PTR_ALIGN (__o1->object_base, __o1->next_free, \
388 __o1->alignment_mask); \
389 if (__o1->next_free - (char *)__o1->chunk \
390 > __o1->chunk_limit - (char *)__o1->chunk) \
391 __o1->next_free = __o1->chunk_limit; \
392 __o1->object_base = __o1->next_free; \
393 __value; })
394
395 # define obstack_free(OBSTACK, OBJ) \
396 __extension__ \
397 ({ struct obstack *__o = (OBSTACK); \
398 void *__obj = (OBJ); \
399 if (__obj > (void *)__o->chunk && __obj < (void *)__o->chunk_limit) \
400 __o->next_free = __o->object_base = (char *)__obj; \
401 else (obstack_free) (__o, __obj); })
402 \f
403 #else /* not __GNUC__ */
404
405 # define obstack_object_size(h) \
406 (unsigned) ((h)->next_free - (h)->object_base)
407
408 # define obstack_room(h) \
409 (unsigned) ((h)->chunk_limit - (h)->next_free)
410
411 # define obstack_empty_p(h) \
412 ((h)->chunk->prev == 0 \
413 && (h)->next_free == __PTR_ALIGN ((char *) (h)->chunk, \
414 (h)->chunk->contents, \
415 (h)->alignment_mask))
416
417 /* Note that the call to _obstack_newchunk is enclosed in (..., 0)
418 so that we can avoid having void expressions
419 in the arms of the conditional expression.
420 Casting the third operand to void was tried before,
421 but some compilers won't accept it. */
422
423 # define obstack_make_room(h,length) \
424 ( (h)->temp.tempint = (length), \
425 (((h)->next_free + (h)->temp.tempint > (h)->chunk_limit) \
426 ? (_obstack_newchunk ((h), (h)->temp.tempint), 0) : 0))
427
428 # define obstack_grow(h,where,length) \
429 ( (h)->temp.tempint = (length), \
430 (((h)->next_free + (h)->temp.tempint > (h)->chunk_limit) \
431 ? (_obstack_newchunk ((h), (h)->temp.tempint), 0) : 0), \
432 memcpy ((h)->next_free, where, (h)->temp.tempint), \
433 (h)->next_free += (h)->temp.tempint)
434
435 # define obstack_grow0(h,where,length) \
436 ( (h)->temp.tempint = (length), \
437 (((h)->next_free + (h)->temp.tempint + 1 > (h)->chunk_limit) \
438 ? (_obstack_newchunk ((h), (h)->temp.tempint + 1), 0) : 0), \
439 memcpy ((h)->next_free, where, (h)->temp.tempint), \
440 (h)->next_free += (h)->temp.tempint, \
441 *((h)->next_free)++ = 0)
442
443 # define obstack_1grow(h,datum) \
444 ( (((h)->next_free + 1 > (h)->chunk_limit) \
445 ? (_obstack_newchunk ((h), 1), 0) : 0), \
446 obstack_1grow_fast (h, datum))
447
448 # define obstack_ptr_grow(h,datum) \
449 ( (((h)->next_free + sizeof (char *) > (h)->chunk_limit) \
450 ? (_obstack_newchunk ((h), sizeof (char *)), 0) : 0), \
451 obstack_ptr_grow_fast (h, datum))
452
453 # define obstack_int_grow(h,datum) \
454 ( (((h)->next_free + sizeof (int) > (h)->chunk_limit) \
455 ? (_obstack_newchunk ((h), sizeof (int)), 0) : 0), \
456 obstack_int_grow_fast (h, datum))
457
458 # define obstack_ptr_grow_fast(h,aptr) \
459 (((const void **) ((h)->next_free += sizeof (void *)))[-1] = (aptr))
460
461 # define obstack_int_grow_fast(h,aint) \
462 (((int *) ((h)->next_free += sizeof (int)))[-1] = (aint))
463
464 # define obstack_blank(h,length) \
465 ( (h)->temp.tempint = (length), \
466 (((h)->chunk_limit - (h)->next_free < (h)->temp.tempint) \
467 ? (_obstack_newchunk ((h), (h)->temp.tempint), 0) : 0), \
468 obstack_blank_fast (h, (h)->temp.tempint))
469
470 # define obstack_alloc(h,length) \
471 (obstack_blank ((h), (length)), obstack_finish ((h)))
472
473 # define obstack_copy(h,where,length) \
474 (obstack_grow ((h), (where), (length)), obstack_finish ((h)))
475
476 # define obstack_copy0(h,where,length) \
477 (obstack_grow0 ((h), (where), (length)), obstack_finish ((h)))
478
479 # define obstack_finish(h) \
480 ( ((h)->next_free == (h)->object_base \
481 ? (((h)->maybe_empty_object = 1), 0) \
482 : 0), \
483 (h)->temp.tempptr = (h)->object_base, \
484 (h)->next_free \
485 = __PTR_ALIGN ((h)->object_base, (h)->next_free, \
486 (h)->alignment_mask), \
487 (((h)->next_free - (char *) (h)->chunk \
488 > (h)->chunk_limit - (char *) (h)->chunk) \
489 ? ((h)->next_free = (h)->chunk_limit) : 0), \
490 (h)->object_base = (h)->next_free, \
491 (h)->temp.tempptr)
492
493 # define obstack_free(h,obj) \
494 ( (h)->temp.tempint = (char *) (obj) - (char *) (h)->chunk, \
495 ((((h)->temp.tempint > 0 \
496 && (h)->temp.tempint < (h)->chunk_limit - (char *) (h)->chunk)) \
497 ? (((h)->next_free = (h)->object_base \
498 = (h)->temp.tempint + (char *) (h)->chunk), 0) \
499 : ((obstack_free) ((h), (h)->temp.tempint + (char *) (h)->chunk), 0)))
500
501 #endif /* not __GNUC__ */
502
503 #ifdef __cplusplus
504 } /* C++ */
505 #endif
506
507 #endif /* obstack.h */