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