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