1*38fd1498Szrj /* obstack.c - subroutines used implicitly by object stack macros
2*38fd1498Szrj Copyright (C) 1988-2018 Free Software Foundation, Inc.
3*38fd1498Szrj This file is part of the GNU C Library.
4*38fd1498Szrj
5*38fd1498Szrj The GNU C Library is free software; you can redistribute it and/or
6*38fd1498Szrj modify it under the terms of the GNU Lesser General Public
7*38fd1498Szrj License as published by the Free Software Foundation; either
8*38fd1498Szrj version 2.1 of the License, or (at your option) any later version.
9*38fd1498Szrj
10*38fd1498Szrj The GNU C Library is distributed in the hope that it will be useful,
11*38fd1498Szrj but WITHOUT ANY WARRANTY; without even the implied warranty of
12*38fd1498Szrj MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
13*38fd1498Szrj Lesser General Public License for more details.
14*38fd1498Szrj
15*38fd1498Szrj You should have received a copy of the GNU Lesser General Public
16*38fd1498Szrj License along with the GNU C Library; if not, see
17*38fd1498Szrj <http://www.gnu.org/licenses/>. */
18*38fd1498Szrj
19*38fd1498Szrj
20*38fd1498Szrj #ifdef _LIBC
21*38fd1498Szrj # include <obstack.h>
22*38fd1498Szrj #else
23*38fd1498Szrj # include <config.h>
24*38fd1498Szrj # include "obstack.h"
25*38fd1498Szrj #endif
26*38fd1498Szrj
27*38fd1498Szrj /* NOTE BEFORE MODIFYING THIS FILE: _OBSTACK_INTERFACE_VERSION in
28*38fd1498Szrj obstack.h must be incremented whenever callers compiled using an old
29*38fd1498Szrj obstack.h can no longer properly call the functions in this file. */
30*38fd1498Szrj
31*38fd1498Szrj /* Comment out all this code if we are using the GNU C Library, and are not
32*38fd1498Szrj actually compiling the library itself, and the installed library
33*38fd1498Szrj supports the same library interface we do. This code is part of the GNU
34*38fd1498Szrj C Library, but also included in many other GNU distributions. Compiling
35*38fd1498Szrj and linking in this code is a waste when using the GNU C library
36*38fd1498Szrj (especially if it is a shared library). Rather than having every GNU
37*38fd1498Szrj program understand 'configure --with-gnu-libc' and omit the object
38*38fd1498Szrj files, it is simpler to just do this in the source for each such file. */
39*38fd1498Szrj #if !defined _LIBC && defined __GNU_LIBRARY__ && __GNU_LIBRARY__ > 1
40*38fd1498Szrj # include <gnu-versions.h>
41*38fd1498Szrj # if (_GNU_OBSTACK_INTERFACE_VERSION == _OBSTACK_INTERFACE_VERSION \
42*38fd1498Szrj || (_GNU_OBSTACK_INTERFACE_VERSION == 1 \
43*38fd1498Szrj && _OBSTACK_INTERFACE_VERSION == 2 \
44*38fd1498Szrj && defined SIZEOF_INT && defined SIZEOF_SIZE_T \
45*38fd1498Szrj && SIZEOF_INT == SIZEOF_SIZE_T))
46*38fd1498Szrj # define _OBSTACK_ELIDE_CODE
47*38fd1498Szrj # endif
48*38fd1498Szrj #endif
49*38fd1498Szrj
50*38fd1498Szrj #ifndef _OBSTACK_ELIDE_CODE
51*38fd1498Szrj /* If GCC, or if an oddball (testing?) host that #defines __alignof__,
52*38fd1498Szrj use the already-supplied __alignof__. Otherwise, this must be Gnulib
53*38fd1498Szrj (as glibc assumes GCC); defer to Gnulib's alignof_type. */
54*38fd1498Szrj # if !defined __GNUC__ && !defined __IBM__ALIGNOF__ && !defined __alignof__
55*38fd1498Szrj # if defined __cplusplus
56*38fd1498Szrj template <class type> struct alignof_helper { char __slot1; type __slot2; };
57*38fd1498Szrj # define __alignof__(type) offsetof (alignof_helper<type>, __slot2)
58*38fd1498Szrj # else
59*38fd1498Szrj # define __alignof__(type) \
60*38fd1498Szrj offsetof (struct { char __slot1; type __slot2; }, __slot2)
61*38fd1498Szrj # endif
62*38fd1498Szrj # endif
63*38fd1498Szrj # include <stdlib.h>
64*38fd1498Szrj # include <stdint.h>
65*38fd1498Szrj
66*38fd1498Szrj # ifndef MAX
67*38fd1498Szrj # define MAX(a,b) ((a) > (b) ? (a) : (b))
68*38fd1498Szrj # endif
69*38fd1498Szrj
70*38fd1498Szrj /* Determine default alignment. */
71*38fd1498Szrj
72*38fd1498Szrj /* If malloc were really smart, it would round addresses to DEFAULT_ALIGNMENT.
73*38fd1498Szrj But in fact it might be less smart and round addresses to as much as
74*38fd1498Szrj DEFAULT_ROUNDING. So we prepare for it to do that.
75*38fd1498Szrj
76*38fd1498Szrj DEFAULT_ALIGNMENT cannot be an enum constant; see gnulib's alignof.h. */
77*38fd1498Szrj #define DEFAULT_ALIGNMENT MAX (__alignof__ (long double), \
78*38fd1498Szrj MAX (__alignof__ (uintmax_t), \
79*38fd1498Szrj __alignof__ (void *)))
80*38fd1498Szrj #define DEFAULT_ROUNDING MAX (sizeof (long double), \
81*38fd1498Szrj MAX (sizeof (uintmax_t), \
82*38fd1498Szrj sizeof (void *)))
83*38fd1498Szrj
84*38fd1498Szrj /* Call functions with either the traditional malloc/free calling
85*38fd1498Szrj interface, or the mmalloc/mfree interface (that adds an extra first
86*38fd1498Szrj argument), based on the value of use_extra_arg. */
87*38fd1498Szrj
88*38fd1498Szrj static void *
call_chunkfun(struct obstack * h,size_t size)89*38fd1498Szrj call_chunkfun (struct obstack *h, size_t size)
90*38fd1498Szrj {
91*38fd1498Szrj if (h->use_extra_arg)
92*38fd1498Szrj return h->chunkfun.extra (h->extra_arg, size);
93*38fd1498Szrj else
94*38fd1498Szrj return h->chunkfun.plain (size);
95*38fd1498Szrj }
96*38fd1498Szrj
97*38fd1498Szrj static void
call_freefun(struct obstack * h,void * old_chunk)98*38fd1498Szrj call_freefun (struct obstack *h, void *old_chunk)
99*38fd1498Szrj {
100*38fd1498Szrj if (h->use_extra_arg)
101*38fd1498Szrj h->freefun.extra (h->extra_arg, old_chunk);
102*38fd1498Szrj else
103*38fd1498Szrj h->freefun.plain (old_chunk);
104*38fd1498Szrj }
105*38fd1498Szrj
106*38fd1498Szrj
107*38fd1498Szrj /* Initialize an obstack H for use. Specify chunk size SIZE (0 means default).
108*38fd1498Szrj Objects start on multiples of ALIGNMENT (0 means use default).
109*38fd1498Szrj
110*38fd1498Szrj Return nonzero if successful, calls obstack_alloc_failed_handler if
111*38fd1498Szrj allocation fails. */
112*38fd1498Szrj
113*38fd1498Szrj static int
_obstack_begin_worker(struct obstack * h,_OBSTACK_SIZE_T size,_OBSTACK_SIZE_T alignment)114*38fd1498Szrj _obstack_begin_worker (struct obstack *h,
115*38fd1498Szrj _OBSTACK_SIZE_T size, _OBSTACK_SIZE_T alignment)
116*38fd1498Szrj {
117*38fd1498Szrj struct _obstack_chunk *chunk; /* points to new chunk */
118*38fd1498Szrj
119*38fd1498Szrj if (alignment == 0)
120*38fd1498Szrj alignment = DEFAULT_ALIGNMENT;
121*38fd1498Szrj if (size == 0)
122*38fd1498Szrj /* Default size is what GNU malloc can fit in a 4096-byte block. */
123*38fd1498Szrj {
124*38fd1498Szrj /* 12 is sizeof (mhead) and 4 is EXTRA from GNU malloc.
125*38fd1498Szrj Use the values for range checking, because if range checking is off,
126*38fd1498Szrj the extra bytes won't be missed terribly, but if range checking is on
127*38fd1498Szrj and we used a larger request, a whole extra 4096 bytes would be
128*38fd1498Szrj allocated.
129*38fd1498Szrj
130*38fd1498Szrj These number are irrelevant to the new GNU malloc. I suspect it is
131*38fd1498Szrj less sensitive to the size of the request. */
132*38fd1498Szrj int extra = ((((12 + DEFAULT_ROUNDING - 1) & ~(DEFAULT_ROUNDING - 1))
133*38fd1498Szrj + 4 + DEFAULT_ROUNDING - 1)
134*38fd1498Szrj & ~(DEFAULT_ROUNDING - 1));
135*38fd1498Szrj size = 4096 - extra;
136*38fd1498Szrj }
137*38fd1498Szrj
138*38fd1498Szrj h->chunk_size = size;
139*38fd1498Szrj h->alignment_mask = alignment - 1;
140*38fd1498Szrj
141*38fd1498Szrj chunk = (struct _obstack_chunk *) call_chunkfun (h, h->chunk_size);
142*38fd1498Szrj if (!chunk)
143*38fd1498Szrj (*obstack_alloc_failed_handler) ();
144*38fd1498Szrj h->chunk = chunk;
145*38fd1498Szrj h->next_free = h->object_base = __PTR_ALIGN ((char *) chunk, chunk->contents,
146*38fd1498Szrj alignment - 1);
147*38fd1498Szrj h->chunk_limit = chunk->limit = (char *) chunk + h->chunk_size;
148*38fd1498Szrj chunk->prev = 0;
149*38fd1498Szrj /* The initial chunk now contains no empty object. */
150*38fd1498Szrj h->maybe_empty_object = 0;
151*38fd1498Szrj h->alloc_failed = 0;
152*38fd1498Szrj return 1;
153*38fd1498Szrj }
154*38fd1498Szrj
155*38fd1498Szrj int
_obstack_begin(struct obstack * h,_OBSTACK_SIZE_T size,_OBSTACK_SIZE_T alignment,void * (* chunkfun)(size_t),void (* freefun)(void *))156*38fd1498Szrj _obstack_begin (struct obstack *h,
157*38fd1498Szrj _OBSTACK_SIZE_T size, _OBSTACK_SIZE_T alignment,
158*38fd1498Szrj void *(*chunkfun) (size_t),
159*38fd1498Szrj void (*freefun) (void *))
160*38fd1498Szrj {
161*38fd1498Szrj h->chunkfun.plain = chunkfun;
162*38fd1498Szrj h->freefun.plain = freefun;
163*38fd1498Szrj h->use_extra_arg = 0;
164*38fd1498Szrj return _obstack_begin_worker (h, size, alignment);
165*38fd1498Szrj }
166*38fd1498Szrj
167*38fd1498Szrj int
_obstack_begin_1(struct obstack * h,_OBSTACK_SIZE_T size,_OBSTACK_SIZE_T alignment,void * (* chunkfun)(void *,size_t),void (* freefun)(void *,void *),void * arg)168*38fd1498Szrj _obstack_begin_1 (struct obstack *h,
169*38fd1498Szrj _OBSTACK_SIZE_T size, _OBSTACK_SIZE_T alignment,
170*38fd1498Szrj void *(*chunkfun) (void *, size_t),
171*38fd1498Szrj void (*freefun) (void *, void *),
172*38fd1498Szrj void *arg)
173*38fd1498Szrj {
174*38fd1498Szrj h->chunkfun.extra = chunkfun;
175*38fd1498Szrj h->freefun.extra = freefun;
176*38fd1498Szrj h->extra_arg = arg;
177*38fd1498Szrj h->use_extra_arg = 1;
178*38fd1498Szrj return _obstack_begin_worker (h, size, alignment);
179*38fd1498Szrj }
180*38fd1498Szrj
181*38fd1498Szrj /* Allocate a new current chunk for the obstack *H
182*38fd1498Szrj on the assumption that LENGTH bytes need to be added
183*38fd1498Szrj to the current object, or a new object of length LENGTH allocated.
184*38fd1498Szrj Copies any partial object from the end of the old chunk
185*38fd1498Szrj to the beginning of the new one. */
186*38fd1498Szrj
187*38fd1498Szrj void
_obstack_newchunk(struct obstack * h,_OBSTACK_SIZE_T length)188*38fd1498Szrj _obstack_newchunk (struct obstack *h, _OBSTACK_SIZE_T length)
189*38fd1498Szrj {
190*38fd1498Szrj struct _obstack_chunk *old_chunk = h->chunk;
191*38fd1498Szrj struct _obstack_chunk *new_chunk = 0;
192*38fd1498Szrj size_t obj_size = h->next_free - h->object_base;
193*38fd1498Szrj char *object_base;
194*38fd1498Szrj
195*38fd1498Szrj /* Compute size for new chunk. */
196*38fd1498Szrj size_t sum1 = obj_size + length;
197*38fd1498Szrj size_t sum2 = sum1 + h->alignment_mask;
198*38fd1498Szrj size_t new_size = sum2 + (obj_size >> 3) + 100;
199*38fd1498Szrj if (new_size < sum2)
200*38fd1498Szrj new_size = sum2;
201*38fd1498Szrj if (new_size < h->chunk_size)
202*38fd1498Szrj new_size = h->chunk_size;
203*38fd1498Szrj
204*38fd1498Szrj /* Allocate and initialize the new chunk. */
205*38fd1498Szrj if (obj_size <= sum1 && sum1 <= sum2)
206*38fd1498Szrj new_chunk = (struct _obstack_chunk *) call_chunkfun (h, new_size);
207*38fd1498Szrj if (!new_chunk)
208*38fd1498Szrj (*obstack_alloc_failed_handler)();
209*38fd1498Szrj h->chunk = new_chunk;
210*38fd1498Szrj new_chunk->prev = old_chunk;
211*38fd1498Szrj new_chunk->limit = h->chunk_limit = (char *) new_chunk + new_size;
212*38fd1498Szrj
213*38fd1498Szrj /* Compute an aligned object_base in the new chunk */
214*38fd1498Szrj object_base =
215*38fd1498Szrj __PTR_ALIGN ((char *) new_chunk, new_chunk->contents, h->alignment_mask);
216*38fd1498Szrj
217*38fd1498Szrj /* Move the existing object to the new chunk. */
218*38fd1498Szrj memcpy (object_base, h->object_base, obj_size);
219*38fd1498Szrj
220*38fd1498Szrj /* If the object just copied was the only data in OLD_CHUNK,
221*38fd1498Szrj free that chunk and remove it from the chain.
222*38fd1498Szrj But not if that chunk might contain an empty object. */
223*38fd1498Szrj if (!h->maybe_empty_object
224*38fd1498Szrj && (h->object_base
225*38fd1498Szrj == __PTR_ALIGN ((char *) old_chunk, old_chunk->contents,
226*38fd1498Szrj h->alignment_mask)))
227*38fd1498Szrj {
228*38fd1498Szrj new_chunk->prev = old_chunk->prev;
229*38fd1498Szrj call_freefun (h, old_chunk);
230*38fd1498Szrj }
231*38fd1498Szrj
232*38fd1498Szrj h->object_base = object_base;
233*38fd1498Szrj h->next_free = h->object_base + obj_size;
234*38fd1498Szrj /* The new chunk certainly contains no empty object yet. */
235*38fd1498Szrj h->maybe_empty_object = 0;
236*38fd1498Szrj }
237*38fd1498Szrj
238*38fd1498Szrj /* Return nonzero if object OBJ has been allocated from obstack H.
239*38fd1498Szrj This is here for debugging.
240*38fd1498Szrj If you use it in a program, you are probably losing. */
241*38fd1498Szrj
242*38fd1498Szrj /* Suppress -Wmissing-prototypes warning. We don't want to declare this in
243*38fd1498Szrj obstack.h because it is just for debugging. */
244*38fd1498Szrj int _obstack_allocated_p (struct obstack *h, void *obj) __attribute_pure__;
245*38fd1498Szrj
246*38fd1498Szrj int
_obstack_allocated_p(struct obstack * h,void * obj)247*38fd1498Szrj _obstack_allocated_p (struct obstack *h, void *obj)
248*38fd1498Szrj {
249*38fd1498Szrj struct _obstack_chunk *lp; /* below addr of any objects in this chunk */
250*38fd1498Szrj struct _obstack_chunk *plp; /* point to previous chunk if any */
251*38fd1498Szrj
252*38fd1498Szrj lp = (h)->chunk;
253*38fd1498Szrj /* We use >= rather than > since the object cannot be exactly at
254*38fd1498Szrj the beginning of the chunk but might be an empty object exactly
255*38fd1498Szrj at the end of an adjacent chunk. */
256*38fd1498Szrj while (lp != 0 && ((void *) lp >= obj || (void *) (lp)->limit < obj))
257*38fd1498Szrj {
258*38fd1498Szrj plp = lp->prev;
259*38fd1498Szrj lp = plp;
260*38fd1498Szrj }
261*38fd1498Szrj return lp != 0;
262*38fd1498Szrj }
263*38fd1498Szrj
264*38fd1498Szrj /* Free objects in obstack H, including OBJ and everything allocate
265*38fd1498Szrj more recently than OBJ. If OBJ is zero, free everything in H. */
266*38fd1498Szrj
267*38fd1498Szrj void
_obstack_free(struct obstack * h,void * obj)268*38fd1498Szrj _obstack_free (struct obstack *h, void *obj)
269*38fd1498Szrj {
270*38fd1498Szrj struct _obstack_chunk *lp; /* below addr of any objects in this chunk */
271*38fd1498Szrj struct _obstack_chunk *plp; /* point to previous chunk if any */
272*38fd1498Szrj
273*38fd1498Szrj lp = h->chunk;
274*38fd1498Szrj /* We use >= because there cannot be an object at the beginning of a chunk.
275*38fd1498Szrj But there can be an empty object at that address
276*38fd1498Szrj at the end of another chunk. */
277*38fd1498Szrj while (lp != 0 && ((void *) lp >= obj || (void *) (lp)->limit < obj))
278*38fd1498Szrj {
279*38fd1498Szrj plp = lp->prev;
280*38fd1498Szrj call_freefun (h, lp);
281*38fd1498Szrj lp = plp;
282*38fd1498Szrj /* If we switch chunks, we can't tell whether the new current
283*38fd1498Szrj chunk contains an empty object, so assume that it may. */
284*38fd1498Szrj h->maybe_empty_object = 1;
285*38fd1498Szrj }
286*38fd1498Szrj if (lp)
287*38fd1498Szrj {
288*38fd1498Szrj h->object_base = h->next_free = (char *) (obj);
289*38fd1498Szrj h->chunk_limit = lp->limit;
290*38fd1498Szrj h->chunk = lp;
291*38fd1498Szrj }
292*38fd1498Szrj else if (obj != 0)
293*38fd1498Szrj /* obj is not in any of the chunks! */
294*38fd1498Szrj abort ();
295*38fd1498Szrj }
296*38fd1498Szrj
297*38fd1498Szrj _OBSTACK_SIZE_T
_obstack_memory_used(struct obstack * h)298*38fd1498Szrj _obstack_memory_used (struct obstack *h)
299*38fd1498Szrj {
300*38fd1498Szrj struct _obstack_chunk *lp;
301*38fd1498Szrj _OBSTACK_SIZE_T nbytes = 0;
302*38fd1498Szrj
303*38fd1498Szrj for (lp = h->chunk; lp != 0; lp = lp->prev)
304*38fd1498Szrj {
305*38fd1498Szrj nbytes += lp->limit - (char *) lp;
306*38fd1498Szrj }
307*38fd1498Szrj return nbytes;
308*38fd1498Szrj }
309*38fd1498Szrj
310*38fd1498Szrj # ifndef _OBSTACK_NO_ERROR_HANDLER
311*38fd1498Szrj /* Define the error handler. */
312*38fd1498Szrj # include <stdio.h>
313*38fd1498Szrj
314*38fd1498Szrj /* Exit value used when 'print_and_abort' is used. */
315*38fd1498Szrj # ifdef _LIBC
316*38fd1498Szrj int obstack_exit_failure = EXIT_FAILURE;
317*38fd1498Szrj # else
318*38fd1498Szrj # ifndef EXIT_FAILURE
319*38fd1498Szrj # define EXIT_FAILURE 1
320*38fd1498Szrj # endif
321*38fd1498Szrj # define obstack_exit_failure EXIT_FAILURE
322*38fd1498Szrj # endif
323*38fd1498Szrj
324*38fd1498Szrj # if defined _LIBC || (HAVE_LIBINTL_H && ENABLE_NLS)
325*38fd1498Szrj # include <libintl.h>
326*38fd1498Szrj # ifndef _
327*38fd1498Szrj # define _(msgid) gettext (msgid)
328*38fd1498Szrj # endif
329*38fd1498Szrj # else
330*38fd1498Szrj # ifndef _
331*38fd1498Szrj # define _(msgid) (msgid)
332*38fd1498Szrj # endif
333*38fd1498Szrj # endif
334*38fd1498Szrj
335*38fd1498Szrj # if !(defined _Noreturn \
336*38fd1498Szrj || (defined __STDC_VERSION__ && __STDC_VERSION__ >= 201112))
337*38fd1498Szrj # if ((defined __GNUC__ \
338*38fd1498Szrj && (__GNUC__ >= 3 || (__GNUC__ == 2 && __GNUC_MINOR__ >= 8))) \
339*38fd1498Szrj || (defined __SUNPRO_C && __SUNPRO_C >= 0x5110))
340*38fd1498Szrj # define _Noreturn __attribute__ ((__noreturn__))
341*38fd1498Szrj # elif defined _MSC_VER && _MSC_VER >= 1200
342*38fd1498Szrj # define _Noreturn __declspec (noreturn)
343*38fd1498Szrj # else
344*38fd1498Szrj # define _Noreturn
345*38fd1498Szrj # endif
346*38fd1498Szrj # endif
347*38fd1498Szrj
348*38fd1498Szrj # ifdef _LIBC
349*38fd1498Szrj # include <libio/iolibio.h>
350*38fd1498Szrj # endif
351*38fd1498Szrj
352*38fd1498Szrj static _Noreturn void
print_and_abort(void)353*38fd1498Szrj print_and_abort (void)
354*38fd1498Szrj {
355*38fd1498Szrj /* Don't change any of these strings. Yes, it would be possible to add
356*38fd1498Szrj the newline to the string and use fputs or so. But this must not
357*38fd1498Szrj happen because the "memory exhausted" message appears in other places
358*38fd1498Szrj like this and the translation should be reused instead of creating
359*38fd1498Szrj a very similar string which requires a separate translation. */
360*38fd1498Szrj # ifdef _LIBC
361*38fd1498Szrj (void) __fxprintf (NULL, "%s\n", _("memory exhausted"));
362*38fd1498Szrj # else
363*38fd1498Szrj fprintf (stderr, "%s\n", _("memory exhausted"));
364*38fd1498Szrj # endif
365*38fd1498Szrj exit (obstack_exit_failure);
366*38fd1498Szrj }
367*38fd1498Szrj
368*38fd1498Szrj /* The functions allocating more room by calling 'obstack_chunk_alloc'
369*38fd1498Szrj jump to the handler pointed to by 'obstack_alloc_failed_handler'.
370*38fd1498Szrj This can be set to a user defined function which should either
371*38fd1498Szrj abort gracefully or use longjump - but shouldn't return. This
372*38fd1498Szrj variable by default points to the internal function
373*38fd1498Szrj 'print_and_abort'. */
374*38fd1498Szrj void (*obstack_alloc_failed_handler) (void) = print_and_abort;
375*38fd1498Szrj # endif /* !_OBSTACK_NO_ERROR_HANDLER */
376*38fd1498Szrj #endif /* !_OBSTACK_ELIDE_CODE */
377