malloc/obstack.c

   1 /* obstack.c - subroutines used implicitly by object stack macros
   2    Copyright (C) 1988-1994, 1996-2001, 2002 Free Software Foundation, Inc.
   3    This file is part of the GNU C Library.  Its master source is NOT part of
   4    the C library, however.  The master source lives in /gd/gnu/lib.
   5
   6    The GNU C Library is free software; you can redistribute it and/or
   7    modify it under the terms of the GNU Lesser General Public
   8    License as published by the Free Software Foundation; either
   9    version 2.1 of the License, or (at your option) any later version.
  10
  11    The GNU C Library 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 GNU
  14    Lesser General Public License for more details.
  15
  16    You should have received a copy of the GNU Lesser General Public
  17    License along with the GNU C Library; if not, write to the Free
  18    Software Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA
  19    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 # if defined __STDC__ && __STDC__
  61 #  define POINTER void *
  62 # else
  63 #  define POINTER char *
  64 # endif
  65
  66 /* Determine default alignment.  */
  67 struct fooalign {char x; double d;};
  68 # define DEFAULT_ALIGNMENT  \
  69   ((PTR_INT_TYPE) ((char *) &((struct fooalign *) 0)->d - (char *) 0))
  70 /* If malloc were really smart, it would round addresses to DEFAULT_ALIGNMENT.
  71    But in fact it might be less smart and round addresses to as much as
  72    DEFAULT_ROUNDING.  So we prepare for it to do that.  */
  73 union fooround {long x; double d;};
  74 # define DEFAULT_ROUNDING (sizeof (union fooround))
  75
  76 /* When we copy a long block of data, this is the unit to do it with.
  77    On some machines, copying successive ints does not work;
  78    in such a case, redefine COPYING_UNIT to `long' (if that works)
  79    or `char' as a last resort.  */
  80 # ifndef COPYING_UNIT
  81 #  define COPYING_UNIT int
  82 # endif
  83
  84
  85 /* The functions allocating more room by calling `obstack_chunk_alloc'
  86    jump to the handler pointed to by `obstack_alloc_failed_handler'.
  87    This can be set to a user defined function which should either
  88    abort gracefully or use longjump - but shouldn't return.  This
  89    variable by default points to the internal function
  90    `print_and_abort'.  */
  91 # if defined __STDC__ && __STDC__
  92 static void print_and_abort (void);
  93 void (*obstack_alloc_failed_handler) (void) = print_and_abort;
  94 # else
  95 static void print_and_abort ();
  96 void (*obstack_alloc_failed_handler) () = print_and_abort;
  97 # endif
  98
  99 /* Exit value used when `print_and_abort' is used.  */
 100 # if defined __GNU_LIBRARY__ || defined HAVE_STDLIB_H
 101 #  include <stdlib.h>
 102 # endif
 103 # ifndef EXIT_FAILURE
 104 #  define EXIT_FAILURE 1
 105 # endif
 106 int obstack_exit_failure = EXIT_FAILURE;
 107
 108 /* The non-GNU-C macros copy the obstack into this global variable
 109    to avoid multiple evaluation.  */
 110
 111 struct obstack *_obstack;
 112
 113 /* Define a macro that either calls functions with the traditional malloc/free
 114    calling interface, or calls functions with the mmalloc/mfree interface
 115    (that adds an extra first argument), based on the state of use_extra_arg.
 116    For free, do not use ?:, since some compilers, like the MIPS compilers,
 117    do not allow (expr) ? void : void.  */
 118
 119 # if defined __STDC__ && __STDC__
 120 #  define CALL_CHUNKFUN(h, size) \
 121   (((h) -> use_extra_arg) \
 122    ? (*(h)->chunkfun) ((h)->extra_arg, (size)) \
 123    : (*(struct _obstack_chunk *(*) (long)) (h)->chunkfun) ((size)))
 124
 125 #  define CALL_FREEFUN(h, old_chunk) \
 126   do { \
 127     if ((h) -> use_extra_arg) \
 128       (*(h)->freefun) ((h)->extra_arg, (old_chunk)); \
 129     else \
 130       (*(void (*) (void *)) (h)->freefun) ((old_chunk)); \
 131   } while (0)
 132 # else
 133 #  define CALL_CHUNKFUN(h, size) \
 134   (((h) -> use_extra_arg) \
 135    ? (*(h)->chunkfun) ((h)->extra_arg, (size)) \
 136    : (*(struct _obstack_chunk *(*) ()) (h)->chunkfun) ((size)))
 137
 138 #  define CALL_FREEFUN(h, old_chunk) \
 139   do { \
 140     if ((h) -> use_extra_arg) \
 141       (*(h)->freefun) ((h)->extra_arg, (old_chunk)); \
 142     else \
 143       (*(void (*) ()) (h)->freefun) ((old_chunk)); \
 144   } while (0)
 145 # endif
 146
 147 \f
 148 /* Initialize an obstack H for use.  Specify chunk size SIZE (0 means default).
 149    Objects start on multiples of ALIGNMENT (0 means use default).
 150    CHUNKFUN is the function to use to allocate chunks,
 151    and FREEFUN the function to free them.
 152
 153    Return nonzero if successful, calls obstack_alloc_failed_handler if
 154    allocation fails.  */
 155
 156 int
 157 _obstack_begin (h, size, alignment, chunkfun, freefun)
 158      struct obstack *h;
 159      int size;
 160      int alignment;
 161 # if defined __STDC__ && __STDC__
 162      POINTER (*chunkfun) (long);
 163      void (*freefun) (void *);
 164 # else
 165      POINTER (*chunkfun) ();
 166      void (*freefun) ();
 167 # endif
 168 {
 169   register struct _obstack_chunk *chunk; /* points to new chunk */
 170
 171   if (alignment == 0)
 172     alignment = (int) DEFAULT_ALIGNMENT;
 173   if (size == 0)
 174     /* Default size is what GNU malloc can fit in a 4096-byte block.  */
 175     {
 176       /* 12 is sizeof (mhead) and 4 is EXTRA from GNU malloc.
 177          Use the values for range checking, because if range checking is off,
 178          the extra bytes won't be missed terribly, but if range checking is on
 179          and we used a larger request, a whole extra 4096 bytes would be
 180          allocated.
 181
 182          These number are irrelevant to the new GNU malloc.  I suspect it is
 183          less sensitive to the size of the request.  */
 184       int extra = ((((12 + DEFAULT_ROUNDING - 1) & ~(DEFAULT_ROUNDING - 1))
 185                     + 4 + DEFAULT_ROUNDING - 1)
 186                    & ~(DEFAULT_ROUNDING - 1));
 187       size = 4096 - extra;
 188     }
 189
 190 # if defined __STDC__ && __STDC__
 191   h->chunkfun = (struct _obstack_chunk * (*)(void *, long)) chunkfun;
 192   h->freefun = (void (*) (void *, struct _obstack_chunk *)) freefun;
 193 # else
 194   h->chunkfun = (struct _obstack_chunk * (*)()) chunkfun;
 195   h->freefun = freefun;
 196 # endif
 197   h->chunk_size = size;
 198   h->alignment_mask = alignment - 1;
 199   h->use_extra_arg = 0;
 200
 201   chunk = h->chunk = CALL_CHUNKFUN (h, h -> chunk_size);
 202   if (!chunk)
 203     (*obstack_alloc_failed_handler) ();
 204   h->next_free = h->object_base = chunk->contents;
 205   h->chunk_limit = chunk->limit
 206     = (char *) chunk + h->chunk_size;
 207   chunk->prev = 0;
 208   /* The initial chunk now contains no empty object.  */
 209   h->maybe_empty_object = 0;
 210   h->alloc_failed = 0;
 211   return 1;
 212 }
 213
 214 int
 215 _obstack_begin_1 (h, size, alignment, chunkfun, freefun, arg)
 216      struct obstack *h;
 217      int size;
 218      int alignment;
 219 # if defined __STDC__ && __STDC__
 220      POINTER (*chunkfun) (POINTER, long);
 221      void (*freefun) (POINTER, POINTER);
 222 # else
 223      POINTER (*chunkfun) ();
 224      void (*freefun) ();
 225 # endif
 226      POINTER arg;
 227 {
 228   register struct _obstack_chunk *chunk; /* points to new chunk */
 229
 230   if (alignment == 0)
 231     alignment = (int) DEFAULT_ALIGNMENT;
 232   if (size == 0)
 233     /* Default size is what GNU malloc can fit in a 4096-byte block.  */
 234     {
 235       /* 12 is sizeof (mhead) and 4 is EXTRA from GNU malloc.
 236          Use the values for range checking, because if range checking is off,
 237          the extra bytes won't be missed terribly, but if range checking is on
 238          and we used a larger request, a whole extra 4096 bytes would be
 239          allocated.
 240
 241          These number are irrelevant to the new GNU malloc.  I suspect it is
 242          less sensitive to the size of the request.  */
 243       int extra = ((((12 + DEFAULT_ROUNDING - 1) & ~(DEFAULT_ROUNDING - 1))
 244                     + 4 + DEFAULT_ROUNDING - 1)
 245                    & ~(DEFAULT_ROUNDING - 1));
 246       size = 4096 - extra;
 247     }
 248
 249 # if defined __STDC__ && __STDC__
 250   h->chunkfun = (struct _obstack_chunk * (*)(void *,long)) chunkfun;
 251   h->freefun = (void (*) (void *, struct _obstack_chunk *)) freefun;
 252 # else
 253   h->chunkfun = (struct _obstack_chunk * (*)()) chunkfun;
 254   h->freefun = freefun;
 255 # endif
 256   h->chunk_size = size;
 257   h->alignment_mask = alignment - 1;
 258   h->extra_arg = arg;
 259   h->use_extra_arg = 1;
 260
 261   chunk = h->chunk = CALL_CHUNKFUN (h, h -> chunk_size);
 262   if (!chunk)
 263     (*obstack_alloc_failed_handler) ();
 264   h->next_free = h->object_base = chunk->contents;
 265   h->chunk_limit = chunk->limit
 266     = (char *) chunk + h->chunk_size;
 267   chunk->prev = 0;
 268   /* The initial chunk now contains no empty object.  */
 269   h->maybe_empty_object = 0;
 270   h->alloc_failed = 0;
 271   return 1;
 272 }
 273
 274 /* Allocate a new current chunk for the obstack *H
 275    on the assumption that LENGTH bytes need to be added
 276    to the current object, or a new object of length LENGTH allocated.
 277    Copies any partial object from the end of the old chunk
 278    to the beginning of the new one.  */
 279
 280 void
 281 _obstack_newchunk (h, length)
 282      struct obstack *h;
 283      int length;
 284 {
 285   register struct _obstack_chunk *old_chunk = h->chunk;
 286   register struct _obstack_chunk *new_chunk;
 287   register long new_size;
 288   register long obj_size = h->next_free - h->object_base;
 289   register long i;
 290   long already;
 291   char *object_base;
 292
 293   /* Compute size for new chunk.  */
 294   new_size = (obj_size + length) + (obj_size >> 3) + h->alignment_mask + 100;
 295   if (new_size < h->chunk_size)
 296     new_size = h->chunk_size;
 297
 298   /* Allocate and initialize the new chunk.  */
 299   new_chunk = CALL_CHUNKFUN (h, new_size);
 300   if (!new_chunk)
 301     (*obstack_alloc_failed_handler) ();
 302   h->chunk = new_chunk;
 303   new_chunk->prev = old_chunk;
 304   new_chunk->limit = h->chunk_limit = (char *) new_chunk + new_size;
 305
 306   /* Compute an aligned object_base in the new chunk */
 307   object_base =
 308     __INT_TO_PTR ((__PTR_TO_INT (new_chunk->contents) + h->alignment_mask)
 309                   & ~ (h->alignment_mask));
 310
 311   /* Move the existing object to the new chunk.
 312      Word at a time is fast and is safe if the object
 313      is sufficiently aligned.  */
 314   if (h->alignment_mask + 1 >= DEFAULT_ALIGNMENT)
 315     {
 316       for (i = obj_size / sizeof (COPYING_UNIT) - 1;
 317            i >= 0; i--)
 318         ((COPYING_UNIT *)object_base)[i]
 319           = ((COPYING_UNIT *)h->object_base)[i];
 320       /* We used to copy the odd few remaining bytes as one extra COPYING_UNIT,
 321          but that can cross a page boundary on a machine
 322          which does not do strict alignment for COPYING_UNITS.  */
 323       already = obj_size / sizeof (COPYING_UNIT) * sizeof (COPYING_UNIT);
 324     }
 325   else
 326     already = 0;
 327   /* Copy remaining bytes one by one.  */
 328   for (i = already; i < obj_size; i++)
 329     object_base[i] = h->object_base[i];
 330
 331   /* If the object just copied was the only data in OLD_CHUNK,
 332      free that chunk and remove it from the chain.
 333      But not if that chunk might contain an empty object.  */
 334   if (h->object_base == old_chunk->contents && ! h->maybe_empty_object)
 335     {
 336       new_chunk->prev = old_chunk->prev;
 337       CALL_FREEFUN (h, old_chunk);
 338     }
 339
 340   h->object_base = object_base;
 341   h->next_free = h->object_base + obj_size;
 342   /* The new chunk certainly contains no empty object yet.  */
 343   h->maybe_empty_object = 0;
 344 }
 345 #ifdef _LIBC
 346 libc_hidden_def (_obstack_newchunk)
 347 #endif
 348
 349 /* Return nonzero if object OBJ has been allocated from obstack H.
 350    This is here for debugging.
 351    If you use it in a program, you are probably losing.  */
 352
 353 # if defined __STDC__ && __STDC__
 354 /* Suppress -Wmissing-prototypes warning.  We don't want to declare this in
 355    obstack.h because it is just for debugging.  */
 356 int _obstack_allocated_p (struct obstack *h, POINTER obj);
 357 # endif
 358
 359 int
 360 _obstack_allocated_p (h, obj)
 361      struct obstack *h;
 362      POINTER obj;
 363 {
 364   register struct _obstack_chunk *lp;   /* below addr of any objects in this chunk */
 365   register struct _obstack_chunk *plp;  /* point to previous chunk if any */
 366
 367   lp = (h)->chunk;
 368   /* We use >= rather than > since the object cannot be exactly at
 369      the beginning of the chunk but might be an empty object exactly
 370      at the end of an adjacent chunk.  */
 371   while (lp != 0 && ((POINTER) lp >= obj || (POINTER) (lp)->limit < obj))
 372     {
 373       plp = lp->prev;
 374       lp = plp;
 375     }
 376   return lp != 0;
 377 }
 378 \f
 379 /* Free objects in obstack H, including OBJ and everything allocate
 380    more recently than OBJ.  If OBJ is zero, free everything in H.  */
 381
 382 # undef obstack_free
 383
 384 /* This function has two names with identical definitions.
 385    This is the first one, called from non-ANSI code.  */
 386
 387 void
 388 _obstack_free (h, obj)
 389      struct obstack *h;
 390      POINTER obj;
 391 {
 392   register struct _obstack_chunk *lp;   /* below addr of any objects in this chunk */
 393   register struct _obstack_chunk *plp;  /* point to previous chunk if any */
 394
 395   lp = h->chunk;
 396   /* We use >= because there cannot be an object at the beginning of a chunk.
 397      But there can be an empty object at that address
 398      at the end of another chunk.  */
 399   while (lp != 0 && ((POINTER) lp >= obj || (POINTER) (lp)->limit < obj))
 400     {
 401       plp = lp->prev;
 402       CALL_FREEFUN (h, lp);
 403       lp = plp;
 404       /* If we switch chunks, we can't tell whether the new current
 405          chunk contains an empty object, so assume that it may.  */
 406       h->maybe_empty_object = 1;
 407     }
 408   if (lp)
 409     {
 410       h->object_base = h->next_free = (char *) (obj);
 411       h->chunk_limit = lp->limit;
 412       h->chunk = lp;
 413     }
 414   else if (obj != 0)
 415     /* obj is not in any of the chunks! */
 416     abort ();
 417 }
 418
 419 /* This function is used from ANSI code.  */
 420
 421 #ifdef _LIBC
 422 strong_alias (_obstack_free, obstack_free)
 423 #else
 424
 425 void
 426 obstack_free (h, obj)
 427      struct obstack *h;
 428      POINTER obj;
 429 {
 430   register struct _obstack_chunk *lp;   /* below addr of any objects in this chunk */
 431   register struct _obstack_chunk *plp;  /* point to previous chunk if any */
 432
 433   lp = h->chunk;
 434   /* We use >= because there cannot be an object at the beginning of a chunk.
 435      But there can be an empty object at that address
 436      at the end of another chunk.  */
 437   while (lp != 0 && ((POINTER) lp >= obj || (POINTER) (lp)->limit < obj))
 438     {
 439       plp = lp->prev;
 440       CALL_FREEFUN (h, lp);
 441       lp = plp;
 442       /* If we switch chunks, we can't tell whether the new current
 443          chunk contains an empty object, so assume that it may.  */
 444       h->maybe_empty_object = 1;
 445     }
 446   if (lp)
 447     {
 448       h->object_base = h->next_free = (char *) (obj);
 449       h->chunk_limit = lp->limit;
 450       h->chunk = lp;
 451     }
 452   else if (obj != 0)
 453     /* obj is not in any of the chunks! */
 454     abort ();
 455 }
 456 #endif
 457 \f
 458 int
 459 _obstack_memory_used (h)
 460      struct obstack *h;
 461 {
 462   register struct _obstack_chunk* lp;
 463   register int nbytes = 0;
 464
 465   for (lp = h->chunk; lp != 0; lp = lp->prev)
 466     {
 467       nbytes += lp->limit - (char *) lp;
 468     }
 469   return nbytes;
 470 }
 471 \f
 472 /* Define the error handler.  */
 473 # ifndef _
 474 #  if (HAVE_LIBINTL_H && ENABLE_NLS) || defined _LIBC
 475 #   include <libintl.h>
 476 #   ifndef _
 477 #    define _(Str) gettext (Str)
 478 #   endif
 479 #  else
 480 #   define _(Str) (Str)
 481 #  endif
 482 # endif
 483 # ifdef _LIBC
 484 #  include <libio/iolibio.h>
 485 # endif
 486
 487 # ifndef __attribute__
 488 /* This feature is available in gcc versions 2.5 and later.  */
 489 #  if __GNUC__ < 2 || (__GNUC__ == 2 && __GNUC_MINOR__ < 5)
 490 #   define __attribute__(Spec) /* empty */
 491 #  endif
 492 # endif
 493
 494 static void
 495 __attribute__ ((noreturn))
 496 print_and_abort ()
 497 {
 498   /* Don't change any of these strings.  Yes, it would be possible to add
 499      the newline to the string and use fputs or so.  But this must not
 500      happen because the "memory exhausted" message appears in other places
 501      like this and the translation should be reused instead of creating
 502      a very similar string which requires a separate translation.  */
 503 # if defined _LIBC && defined USE_IN_LIBIO
 504   if (_IO_fwide (stderr, 0) > 0)
 505     __fwprintf (stderr, L"%s\n", _("memory exhausted"));
 506   else
 507 # endif
 508     fprintf (stderr, "%s\n", _("memory exhausted"));
 509   exit (obstack_exit_failure);
 510 }
 511 \f
 512 # if 0
 513 /* These are now turned off because the applications do not use it
 514    and it uses bcopy via obstack_grow, which causes trouble on sysV.  */
 515
 516 /* Now define the functional versions of the obstack macros.
 517    Define them to simply use the corresponding macros to do the job.  */
 518
 519 #  if defined __STDC__ && __STDC__
 520 /* These function definitions do not work with non-ANSI preprocessors;
 521    they won't pass through the macro names in parentheses.  */
 522
 523 /* The function names appear in parentheses in order to prevent
 524    the macro-definitions of the names from being expanded there.  */
 525
 526 POINTER (obstack_base) (obstack)
 527      struct obstack *obstack;
 528 {
 529   return obstack_base (obstack);
 530 }
 531
 532 POINTER (obstack_next_free) (obstack)
 533      struct obstack *obstack;
 534 {
 535   return obstack_next_free (obstack);
 536 }
 537
 538 int (obstack_object_size) (obstack)
 539      struct obstack *obstack;
 540 {
 541   return obstack_object_size (obstack);
 542 }
 543
 544 int (obstack_room) (obstack)
 545      struct obstack *obstack;
 546 {
 547   return obstack_room (obstack);
 548 }
 549
 550 int (obstack_make_room) (obstack, length)
 551      struct obstack *obstack;
 552      int length;
 553 {
 554   return obstack_make_room (obstack, length);
 555 }
 556
 557 void (obstack_grow) (obstack, data, length)
 558      struct obstack *obstack;
 559      const POINTER data;
 560      int length;
 561 {
 562   obstack_grow (obstack, data, length);
 563 }
 564
 565 void (obstack_grow0) (obstack, data, length)
 566      struct obstack *obstack;
 567      const POINTER data;
 568      int length;
 569 {
 570   obstack_grow0 (obstack, data, length);
 571 }
 572
 573 void (obstack_1grow) (obstack, character)
 574      struct obstack *obstack;
 575      int character;
 576 {
 577   obstack_1grow (obstack, character);
 578 }
 579
 580 void (obstack_blank) (obstack, length)
 581      struct obstack *obstack;
 582      int length;
 583 {
 584   obstack_blank (obstack, length);
 585 }
 586
 587 void (obstack_1grow_fast) (obstack, character)
 588      struct obstack *obstack;
 589      int character;
 590 {
 591   obstack_1grow_fast (obstack, character);
 592 }
 593
 594 void (obstack_blank_fast) (obstack, length)
 595      struct obstack *obstack;
 596      int length;
 597 {
 598   obstack_blank_fast (obstack, length);
 599 }
 600
 601 POINTER (obstack_finish) (obstack)
 602      struct obstack *obstack;
 603 {
 604   return obstack_finish (obstack);
 605 }
 606
 607 POINTER (obstack_alloc) (obstack, length)
 608      struct obstack *obstack;
 609      int length;
 610 {
 611   return obstack_alloc (obstack, length);
 612 }
 613
 614 POINTER (obstack_copy) (obstack, address, length)
 615      struct obstack *obstack;
 616      const POINTER address;
 617      int length;
 618 {
 619   return obstack_copy (obstack, address, length);
 620 }
 621
 622 POINTER (obstack_copy0) (obstack, address, length)
 623      struct obstack *obstack;
 624      const POINTER address;
 625      int length;
 626 {
 627   return obstack_copy0 (obstack, address, length);
 628 }
 629
 630 #  endif /* __STDC__ */
 631
 632 # endif /* 0 */
 633
 634 #endif  /* !ELIDE_CODE */