lib/obstack.c

   1 /* obstack.c - subroutines used implicitly by object stack macros
   2
   3    Copyright (C) 1988, 1989, 1990, 1991, 1992, 1993, 1994, 1996, 1997,
   4    1998, 1999, 2000, 2001, 2002, 2003, 2004, 2005, 2006 Free Software
   5    Foundation, Inc.
   6
   7    This program is free software; you can redistribute it and/or modify
   8    it under the terms of the GNU General Public License as published by
   9    the Free Software Foundation; either version 2, or (at your option)
  10    any later version.
  11
  12    This program is distributed in the hope that it will be useful,
  13    but WITHOUT ANY WARRANTY; without even the implied warranty of
  14    MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  15    GNU General Public License for more details.
  16
  17    You should have received a copy of the GNU General Public License along
  18    with this program; if not, write to the Free Software Foundation,
  19    Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301, USA.  */
  20
  21 #ifdef HAVE_CONFIG_H
  22 # include <config.h>
  23 #endif
  24
  25 #ifdef _LIBC
  26 # include <obstack.h>
  27 # include <shlib-compat.h>
  28 #else
  29 # include "obstack.h"
  30 #endif
  31
  32 /* NOTE BEFORE MODIFYING THIS FILE: This version number must be
  33    incremented whenever callers compiled using an old obstack.h can no
  34    longer properly call the functions in this obstack.c.  */
  35 #define OBSTACK_INTERFACE_VERSION 1
  36
  37 /* Comment out all this code if we are using the GNU C Library, and are not
  38    actually compiling the library itself, and the installed library
  39    supports the same library interface we do.  This code is part of the GNU
  40    C Library, but also included in many other GNU distributions.  Compiling
  41    and linking in this code is a waste when using the GNU C library
  42    (especially if it is a shared library).  Rather than having every GNU
  43    program understand `configure --with-gnu-libc' and omit the object
  44    files, it is simpler to just do this in the source for each such file.  */
  45
  46 #include <stdio.h>              /* Random thing to get __GNU_LIBRARY__.  */
  47 #if !defined _LIBC && defined __GNU_LIBRARY__ && __GNU_LIBRARY__ > 1
  48 # include <gnu-versions.h>
  49 # if _GNU_OBSTACK_INTERFACE_VERSION == OBSTACK_INTERFACE_VERSION
  50 #  define ELIDE_CODE
  51 # endif
  52 #endif
  53
  54 #include <stddef.h>
  55
  56 #ifndef ELIDE_CODE
  57
  58 # include <stdint.h>
  59
  60 /* Determine default alignment.  */
  61 union fooround
  62 {
  63   uintmax_t i;
  64   long double d;
  65   void *p;
  66 };
  67 struct fooalign
  68 {
  69   char c;
  70   union fooround u;
  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 enum
  76   {
  77     DEFAULT_ALIGNMENT = offsetof (struct fooalign, u),
  78     DEFAULT_ROUNDING = sizeof (union fooround)
  79   };
  80
  81 /* When we copy a long block of data, this is the unit to do it with.
  82    On some machines, copying successive ints does not work;
  83    in such a case, redefine COPYING_UNIT to `long' (if that works)
  84    or `char' as a last resort.  */
  85 # ifndef COPYING_UNIT
  86 #  define COPYING_UNIT int
  87 # endif
  88
  89
  90 /* The functions allocating more room by calling `obstack_chunk_alloc'
  91    jump to the handler pointed to by `obstack_alloc_failed_handler'.
  92    This can be set to a user defined function which should either
  93    abort gracefully or use longjump - but shouldn't return.  This
  94    variable by default points to the internal function
  95    `print_and_abort'.  */
  96 static void print_and_abort (void);
  97 void (*obstack_alloc_failed_handler) (void) = print_and_abort;
  98
  99 /* Exit value used when `print_and_abort' is used.  */
 100 # include <stdlib.h>
 101 # ifdef _LIBC
 102 int obstack_exit_failure = EXIT_FAILURE;
 103 # else
 104 #  include "exitfail.h"
 105 #  define obstack_exit_failure exit_failure
 106 # endif
 107
 108 # ifdef _LIBC
 109 #  if SHLIB_COMPAT (libc, GLIBC_2_0, GLIBC_2_3_4)
 110 /* A looong time ago (before 1994, anyway; we're not sure) this global variable
 111    was used by non-GNU-C macros to avoid multiple evaluation.  The GNU C
 112    library still exports it because somebody might use it.  */
 113 struct obstack *_obstack_compat;
 114 compat_symbol (libc, _obstack_compat, _obstack, GLIBC_2_0);
 115 #  endif
 116 # endif
 117
 118 /* Define a macro that either calls functions with the traditional malloc/free
 119    calling interface, or calls functions with the mmalloc/mfree interface
 120    (that adds an extra first argument), based on the state of use_extra_arg.
 121    For free, do not use ?:, since some compilers, like the MIPS compilers,
 122    do not allow (expr) ? void : void.  */
 123
 124 # define CALL_CHUNKFUN(h, size) \
 125   (((h) -> use_extra_arg) \
 126    ? (*(h)->chunkfun) ((h)->extra_arg, (size)) \
 127    : (*(struct _obstack_chunk *(*) (long)) (h)->chunkfun) ((size)))
 128
 129 # define CALL_FREEFUN(h, old_chunk) \
 130   do { \
 131     if ((h) -> use_extra_arg) \
 132       (*(h)->freefun) ((h)->extra_arg, (old_chunk)); \
 133     else \
 134       (*(void (*) (void *)) (h)->freefun) ((old_chunk)); \
 135   } while (0)
 136
 137 \f
 138 /* Initialize an obstack H for use.  Specify chunk size SIZE (0 means default).
 139    Objects start on multiples of ALIGNMENT (0 means use default).
 140    CHUNKFUN is the function to use to allocate chunks,
 141    and FREEFUN the function to free them.
 142
 143    Return nonzero if successful, calls obstack_alloc_failed_handler if
 144    allocation fails.  */
 145
 146 int
 147 _obstack_begin (struct obstack *h,
 148                 int size, int alignment,
 149                 void *(*chunkfun) (long),
 150                 void (*freefun) (void *))
 151 {
 152   register struct _obstack_chunk *chunk; /* points to new chunk */
 153
 154   if (alignment == 0)
 155     alignment = DEFAULT_ALIGNMENT;
 156   if (size == 0)
 157     /* Default size is what GNU malloc can fit in a 4096-byte block.  */
 158     {
 159       /* 12 is sizeof (mhead) and 4 is EXTRA from GNU malloc.
 160          Use the values for range checking, because if range checking is off,
 161          the extra bytes won't be missed terribly, but if range checking is on
 162          and we used a larger request, a whole extra 4096 bytes would be
 163          allocated.
 164
 165          These number are irrelevant to the new GNU malloc.  I suspect it is
 166          less sensitive to the size of the request.  */
 167       int extra = ((((12 + DEFAULT_ROUNDING - 1) & ~(DEFAULT_ROUNDING - 1))
 168                     + 4 + DEFAULT_ROUNDING - 1)
 169                    & ~(DEFAULT_ROUNDING - 1));
 170       size = 4096 - extra;
 171     }
 172
 173   h->chunkfun = (struct _obstack_chunk * (*)(void *, long)) chunkfun;
 174   h->freefun = (void (*) (void *, struct _obstack_chunk *)) freefun;
 175   h->chunk_size = size;
 176   h->alignment_mask = alignment - 1;
 177   h->use_extra_arg = 0;
 178
 179   chunk = h->chunk = CALL_CHUNKFUN (h, h -> chunk_size);
 180   if (!chunk)
 181     (*obstack_alloc_failed_handler) ();
 182   h->next_free = h->object_base = __PTR_ALIGN ((char *) chunk, chunk->contents,
 183                                                alignment - 1);
 184   h->chunk_limit = chunk->limit
 185     = (char *) chunk + h->chunk_size;
 186   chunk->prev = 0;
 187   /* The initial chunk now contains no empty object.  */
 188   h->maybe_empty_object = 0;
 189   h->alloc_failed = 0;
 190   return 1;
 191 }
 192
 193 int
 194 _obstack_begin_1 (struct obstack *h, int size, int alignment,
 195                   void *(*chunkfun) (void *, long),
 196                   void (*freefun) (void *, void *),
 197                   void *arg)
 198 {
 199   register struct _obstack_chunk *chunk; /* points to new chunk */
 200
 201   if (alignment == 0)
 202     alignment = DEFAULT_ALIGNMENT;
 203   if (size == 0)
 204     /* Default size is what GNU malloc can fit in a 4096-byte block.  */
 205     {
 206       /* 12 is sizeof (mhead) and 4 is EXTRA from GNU malloc.
 207          Use the values for range checking, because if range checking is off,
 208          the extra bytes won't be missed terribly, but if range checking is on
 209          and we used a larger request, a whole extra 4096 bytes would be
 210          allocated.
 211
 212          These number are irrelevant to the new GNU malloc.  I suspect it is
 213          less sensitive to the size of the request.  */
 214       int extra = ((((12 + DEFAULT_ROUNDING - 1) & ~(DEFAULT_ROUNDING - 1))
 215                     + 4 + DEFAULT_ROUNDING - 1)
 216                    & ~(DEFAULT_ROUNDING - 1));
 217       size = 4096 - extra;
 218     }
 219
 220   h->chunkfun = (struct _obstack_chunk * (*)(void *,long)) chunkfun;
 221   h->freefun = (void (*) (void *, struct _obstack_chunk *)) freefun;
 222   h->chunk_size = size;
 223   h->alignment_mask = alignment - 1;
 224   h->extra_arg = arg;
 225   h->use_extra_arg = 1;
 226
 227   chunk = h->chunk = CALL_CHUNKFUN (h, h -> chunk_size);
 228   if (!chunk)
 229     (*obstack_alloc_failed_handler) ();
 230   h->next_free = h->object_base = __PTR_ALIGN ((char *) chunk, chunk->contents,
 231                                                alignment - 1);
 232   h->chunk_limit = chunk->limit
 233     = (char *) chunk + h->chunk_size;
 234   chunk->prev = 0;
 235   /* The initial chunk now contains no empty object.  */
 236   h->maybe_empty_object = 0;
 237   h->alloc_failed = 0;
 238   return 1;
 239 }
 240
 241 /* Allocate a new current chunk for the obstack *H
 242    on the assumption that LENGTH bytes need to be added
 243    to the current object, or a new object of length LENGTH allocated.
 244    Copies any partial object from the end of the old chunk
 245    to the beginning of the new one.  */
 246
 247 void
 248 _obstack_newchunk (struct obstack *h, int length)
 249 {
 250   register struct _obstack_chunk *old_chunk = h->chunk;
 251   register struct _obstack_chunk *new_chunk;
 252   register long new_size;
 253   register long obj_size = h->next_free - h->object_base;
 254   register long i;
 255   long already;
 256   char *object_base;
 257
 258   /* Compute size for new chunk.  */
 259   new_size = (obj_size + length) + (obj_size >> 3) + h->alignment_mask + 100;
 260   if (new_size < h->chunk_size)
 261     new_size = h->chunk_size;
 262
 263   /* Allocate and initialize the new chunk.  */
 264   new_chunk = CALL_CHUNKFUN (h, new_size);
 265   if (!new_chunk)
 266     (*obstack_alloc_failed_handler) ();
 267   h->chunk = new_chunk;
 268   new_chunk->prev = old_chunk;
 269   new_chunk->limit = h->chunk_limit = (char *) new_chunk + new_size;
 270
 271   /* Compute an aligned object_base in the new chunk */
 272   object_base =
 273     __PTR_ALIGN ((char *) new_chunk, new_chunk->contents, h->alignment_mask);
 274
 275   /* Move the existing object to the new chunk.
 276      Word at a time is fast and is safe if the object
 277      is sufficiently aligned.  */
 278   if (h->alignment_mask + 1 >= DEFAULT_ALIGNMENT)
 279     {
 280       for (i = obj_size / sizeof (COPYING_UNIT) - 1;
 281            i >= 0; i--)
 282         ((COPYING_UNIT *)object_base)[i]
 283           = ((COPYING_UNIT *)h->object_base)[i];
 284       /* We used to copy the odd few remaining bytes as one extra COPYING_UNIT,
 285          but that can cross a page boundary on a machine
 286          which does not do strict alignment for COPYING_UNITS.  */
 287       already = obj_size / sizeof (COPYING_UNIT) * sizeof (COPYING_UNIT);
 288     }
 289   else
 290     already = 0;
 291   /* Copy remaining bytes one by one.  */
 292   for (i = already; i < obj_size; i++)
 293     object_base[i] = h->object_base[i];
 294
 295   /* If the object just copied was the only data in OLD_CHUNK,
 296      free that chunk and remove it from the chain.
 297      But not if that chunk might contain an empty object.  */
 298   if (! h->maybe_empty_object
 299       && (h->object_base
 300           == __PTR_ALIGN ((char *) old_chunk, old_chunk->contents,
 301                           h->alignment_mask)))
 302     {
 303       new_chunk->prev = old_chunk->prev;
 304       CALL_FREEFUN (h, old_chunk);
 305     }
 306
 307   h->object_base = object_base;
 308   h->next_free = h->object_base + obj_size;
 309   /* The new chunk certainly contains no empty object yet.  */
 310   h->maybe_empty_object = 0;
 311 }
 312 # ifdef _LIBC
 313 libc_hidden_def (_obstack_newchunk)
 314 # endif
 315
 316 /* Return nonzero if object OBJ has been allocated from obstack H.
 317    This is here for debugging.
 318    If you use it in a program, you are probably losing.  */
 319
 320 /* Suppress -Wmissing-prototypes warning.  We don't want to declare this in
 321    obstack.h because it is just for debugging.  */
 322 int _obstack_allocated_p (struct obstack *h, void *obj);
 323
 324 int
 325 _obstack_allocated_p (struct obstack *h, void *obj)
 326 {
 327   register struct _obstack_chunk *lp;   /* below addr of any objects in this chunk */
 328   register struct _obstack_chunk *plp;  /* point to previous chunk if any */
 329
 330   lp = (h)->chunk;
 331   /* We use >= rather than > since the object cannot be exactly at
 332      the beginning of the chunk but might be an empty object exactly
 333      at the end of an adjacent chunk.  */
 334   while (lp != 0 && ((void *) lp >= obj || (void *) (lp)->limit < obj))
 335     {
 336       plp = lp->prev;
 337       lp = plp;
 338     }
 339   return lp != 0;
 340 }
 341 \f
 342 /* Free objects in obstack H, including OBJ and everything allocate
 343    more recently than OBJ.  If OBJ is zero, free everything in H.  */
 344
 345 # undef obstack_free
 346
 347 void
 348 obstack_free (struct obstack *h, void *obj)
 349 {
 350   register struct _obstack_chunk *lp;   /* below addr of any objects in this chunk */
 351   register struct _obstack_chunk *plp;  /* point to previous chunk if any */
 352
 353   lp = h->chunk;
 354   /* We use >= because there cannot be an object at the beginning of a chunk.
 355      But there can be an empty object at that address
 356      at the end of another chunk.  */
 357   while (lp != 0 && ((void *) lp >= obj || (void *) (lp)->limit < obj))
 358     {
 359       plp = lp->prev;
 360       CALL_FREEFUN (h, lp);
 361       lp = plp;
 362       /* If we switch chunks, we can't tell whether the new current
 363          chunk contains an empty object, so assume that it may.  */
 364       h->maybe_empty_object = 1;
 365     }
 366   if (lp)
 367     {
 368       h->object_base = h->next_free = (char *) (obj);
 369       h->chunk_limit = lp->limit;
 370       h->chunk = lp;
 371     }
 372   else if (obj != 0)
 373     /* obj is not in any of the chunks! */
 374     abort ();
 375 }
 376
 377 # ifdef _LIBC
 378 /* Older versions of libc used a function _obstack_free intended to be
 379    called by non-GCC compilers.  */
 380 strong_alias (obstack_free, _obstack_free)
 381 # endif
 382 \f
 383 int
 384 _obstack_memory_used (struct obstack *h)
 385 {
 386   register struct _obstack_chunk* lp;
 387   register int nbytes = 0;
 388
 389   for (lp = h->chunk; lp != 0; lp = lp->prev)
 390     {
 391       nbytes += lp->limit - (char *) lp;
 392     }
 393   return nbytes;
 394 }
 395 \f
 396 /* Define the error handler.  */
 397 # ifdef _LIBC
 398 #  include <libintl.h>
 399 # else
 400 #  include "gettext.h"
 401 # endif
 402 # ifndef _
 403 #  define _(msgid) gettext (msgid)
 404 # endif
 405
 406 # ifdef _LIBC
 407 #  include <libio/iolibio.h>
 408 # endif
 409
 410 # ifndef __attribute__
 411 /* This feature is available in gcc versions 2.5 and later.  */
 412 #  if __GNUC__ < 2 || (__GNUC__ == 2 && __GNUC_MINOR__ < 5)
 413 #   define __attribute__(Spec) /* empty */
 414 #  endif
 415 # endif
 416
 417 static void
 418 __attribute__ ((noreturn))
 419 print_and_abort (void)
 420 {
 421   /* Don't change any of these strings.  Yes, it would be possible to add
 422      the newline to the string and use fputs or so.  But this must not
 423      happen because the "memory exhausted" message appears in other places
 424      like this and the translation should be reused instead of creating
 425      a very similar string which requires a separate translation.  */
 426 # ifdef _LIBC
 427   (void) __fxprintf (NULL, "%s\n", _("memory exhausted"));
 428 # else
 429   fprintf (stderr, "%s\n", _("memory exhausted"));
 430 # endif
 431   exit (obstack_exit_failure);
 432 }
 433
 434 #endif  /* !ELIDE_CODE */