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