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