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