malloc/obstack.c

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