The Obstack class
*****************

   The `Obstack' class is a simple rewrite of the C obstack macros and
functions provided in the GNU CC compiler source distribution.

   Obstacks provide a simple method of creating and maintaining a string
table, optimized for the very frequent task of building strings
character-by-character, and sometimes keeping them, and sometimes not.
They seem especially useful in any parsing application. One of the test
files demonstrates usage.

   A brief summary:
`grow'
     places something on the obstack without committing to wrap it up
     as a single entity yet.

`finish'
     wraps up a constructed object as a single entity, and returns the
     pointer to its start address.

`copy'
     places things on the obstack, and *does* wrap them up.  `copy' is
     always equivalent to first grow, then finish.

`free'
     deletes something, and anything else put on the obstack since its
     creation.

   The other functions are less commonly needed:
`blank'
     is like grow, except it just grows the space by size units without
     placing anything into this space

`alloc'
     is like `blank', but it wraps up the object and returns its
     starting address.

`chunk_size, base, next_free, alignment_mask, size, room'
     returns the appropriate class variables.

`grow_fast'
     places a character on the obstack without checking if there is
     enough room.

`blank_fast'
     like `blank', but without checking if there is enough room.

`shrink(int n)'
     shrink the current chunk by n bytes.

`contains(void* addr)'
     returns true if the Obstack holds the address addr.

   Here is a lightly edited version of the original C documentation:

   These functions operate a stack of objects.  Each object starts life
small, and may grow to maturity.  (Consider building a word syllable by
syllable.)  An object can move while it is growing.  Once it has been
"finished" it never changes address again.  So the "top of the stack"
is typically an immature growing object, while the rest of the stack is
of mature, fixed size and fixed address objects.

   These routines grab large chunks of memory, using the GNU C++ `new'
operator.  On occasion, they free chunks, via `delete'.

   Each independent stack is represented by a Obstack.

   One motivation for this package is the problem of growing char
strings in symbol tables.  Unless you are a "fascist pig with a
read-only mind" [Gosper's immortal quote from HAKMEM item 154, out of
context] you would not like to put any arbitrary upper limit on the
length of your symbols.

   In practice this often means you will build many short symbols and a
few long symbols.  At the time you are reading a symbol you don't know
how long it is.  One traditional method is to read a symbol into a
buffer, `realloc()'ating the buffer every time you try to read a symbol
that is longer than the buffer.  This is beaut, but you still will want
to copy the symbol from the buffer to a more permanent symbol-table
entry say about half the time.

   With obstacks, you can work differently.  Use one obstack for all
symbol names.  As you read a symbol, grow the name in the obstack
gradually.  When the name is complete, finalize it.  Then, if the
symbol exists already, free the newly read name.

   The way we do this is to take a large chunk, allocating memory from
low addresses.  When you want to build a symbol in the chunk you just
add chars above the current "high water mark" in the chunk.  When you
have finished adding chars, because you got to the end of the symbol,
you know how long the chars are, and you can create a new object.
Mostly the chars will not burst over the highest address of the chunk,
because you would typically expect a chunk to be (say) 100 times as
long as an average object.

   In case that isn't clear, when we have enough chars to make up the
object, *they are already contiguous in the chunk* (guaranteed) so we
just point to it where it lies.  No moving of chars is needed and this
is the second win: potentially long strings need never be explicitly
shuffled. Once an object is formed, it does not change its address
during its lifetime.

   When the chars burst over a chunk boundary, we allocate a larger
chunk, and then copy the partly formed object from the end of the old
chunk to the beginning of the new larger chunk.  We then carry on
accreting characters to the end of the object as we normally would.

   A special version of grow is provided to add a single char at a time
to a growing object.

   Summary:

   * We allocate large chunks.

   * We carve out one object at a time from the current chunk.

   * Once carved, an object never moves.

   * We are free to append data of any size to the currently growing
     object.

   * Exactly one object is growing in an obstack at any one time.

   * You can run one obstack per control block.

   * You may have as many control blocks as you dare.

   * Because of the way we do it, you can `unwind' a obstack back to a
     previous state. (You may remove objects much as you would with a
     stack.)

   The obstack data structure is used in many places in the GNU C++
compiler.

   Differences from the the GNU C version
  1. The obvious differences stemming from the use of classes and
     inline functions instead of structs and macros. The C `init' and
     `begin' macros are replaced by constructors.

  2. Overloaded function names are used for grow (and others), rather
     than the C `grow', `grow0', etc.

  3. All dynamic allocation uses the the built-in `new' operator.  This
     restricts flexibility by a little, but maintains compatibility
     with usual C++ conventions.

  4. There are now two versions of finish:

       1. finish() behaves like the C version.

       2. finish(char terminator) adds `terminator', and then calls
          `finish()'.  This enables the normal invocation of
          `finish(0)' to wrap up a string being grown
          character-by-character.

  5. There are special versions of grow(const char* s) and copy(const
     char* s) that add the null-terminated string `s' after computing
     its length.

  6. The shrink and contains functions are provided.