obstacks.texi

理解和实践操作系统的一本好书

@node Obstacks,Licenses,Functions,Top
@chapter Obstacks
@cindex obstacks

An @dfn{obstack} is a pool of memory containing a stack of objects.  You
can create any number of separate obstacks, and then allocate objects in
specified obstacks.  Within each obstack, the last object allocated must
always be the first one freed, but distinct obstacks are independent of
each other.

Aside from this one constraint of order of freeing, obstacks are totally
general: an obstack can contain any number of objects of any size.  They
are implemented with macros, so allocation is usually very fast as long as
the objects are usually small.  And the only space overhead per object is
the padding needed to start each object on a suitable boundary.

@menu
* Creating Obstacks::		How to declare an obstack in your program.
* Preparing for Obstacks::	Preparations needed before you can
				 use obstacks.
* Allocation in an Obstack::    Allocating objects in an obstack.
* Freeing Obstack Objects::     Freeing objects in an obstack.
* Obstack Functions::		The obstack functions are both
				 functions and macros.
* Growing Objects::             Making an object bigger by stages.
* Extra Fast Growing::		Extra-high-efficiency (though more
				 complicated) growing objects.
* Status of an Obstack::        Inquiries about the status of an obstack.
* Obstacks Data Alignment::     Controlling alignment of objects in obstacks.
* Obstack Chunks::              How obstacks obtain and release chunks;
				 efficiency considerations.
* Summary of Obstacks::
@end menu

@node Creating Obstacks
@section Creating Obstacks

The utilities for manipulating obstacks are declared in the header
file @file{obstack.h}.
@pindex obstack.h

@comment obstack.h
@comment GNU
@deftp {Data Type} {struct obstack}
An obstack is represented by a data structure of type @code{struct
obstack}.  This structure has a small fixed size; it records the status
of the obstack and how to find the space in which objects are allocated.
It does not contain any of the objects themselves.  You should not try
to access the contents of the structure directly; use only the functions
described in this chapter.
@end deftp

You can declare variables of type @code{struct obstack} and use them as
obstacks, or you can allocate obstacks dynamically like any other kind
of object.  Dynamic allocation of obstacks allows your program to have a
variable number of different stacks.  (You can even allocate an
obstack structure in another obstack, but this is rarely useful.)

All the functions that work with obstacks require you to specify which
obstack to use.  You do this with a pointer of type @code{struct obstack
*}.  In the following, we often say ``an obstack'' when strictly
speaking the object at hand is such a pointer.

The objects in the obstack are packed into large blocks called
@dfn{chunks}.  The @code{struct obstack} structure points to a chain of
the chunks currently in use.

The obstack library obtains a new chunk whenever you allocate an object
that won't fit in the previous chunk.  Since the obstack library manages
chunks automatically, you don't need to pay much attention to them, but
you do need to supply a function which the obstack library should use to
get a chunk.  Usually you supply a function which uses @code{malloc}
directly or indirectly.  You must also supply a function to free a chunk.
These matters are described in the following section.

@node Preparing for Obstacks
@section Preparing for Using Obstacks

Each source file in which you plan to use the obstack functions
must include the header file @file{obstack.h}, like this:

@smallexample
#include <obstack.h>
@end smallexample

@findex obstack_chunk_alloc
@findex obstack_chunk_free
Also, if the source file uses the macro @code{obstack_init}, it must
declare or define two functions or macros that will be called by the
obstack library.  One, @code{obstack_chunk_alloc}, is used to allocate
the chunks of memory into which objects are packed.  The other,
@code{obstack_chunk_free}, is used to return chunks when the objects in
them are freed.  These macros should appear before any use of obstacks
in the source file.

Usually these are defined to use @code{malloc} via the intermediary
@code{xmalloc} (@pxref{Unconstrained Allocation, , , libc, The GNU C Library Reference Manual}).  This is done with
the following pair of macro definitions:

@smallexample
#define obstack_chunk_alloc xmalloc
#define obstack_chunk_free free
@end smallexample

@noindent
Though the memory you get using obstacks really comes from @code{malloc},
using obstacks is faster because @code{malloc} is called less often, for
larger blocks of memory.  @xref{Obstack Chunks}, for full details.

At run time, before the program can use a @code{struct obstack} object
as an obstack, it must initialize the obstack by calling
@code{obstack_init}.

@comment obstack.h
@comment GNU
@deftypefun int obstack_init (struct obstack *@var{obstack-ptr})
Initialize obstack @var{obstack-ptr} for allocation of objects.  This
function calls the obstack's @code{obstack_chunk_alloc} function.  If
allocation of memory fails, the function pointed to by
@code{obstack_alloc_failed_handler} is called.  The @code{obstack_init}
function always returns 1 (Compatibility notice: Former versions of
obstack returned 0 if allocation failed).
@end deftypefun

Here are two examples of how to allocate the space for an obstack and
initialize it.  First, an obstack that is a static variable:

@smallexample
static struct obstack myobstack;
@dots{}
obstack_init (&myobstack);
@end smallexample

@noindent
Second, an obstack that is itself dynamically allocated:

@smallexample
struct obstack *myobstack_ptr
  = (struct obstack *) xmalloc (sizeof (struct obstack));

obstack_init (myobstack_ptr);
@end smallexample

@comment obstack.h
@comment GNU
@defvar obstack_alloc_failed_handler
The value of this variable is a pointer to a function that
@code{obstack} uses when @code{obstack_chunk_alloc} fails to allocate
memory.  The default action is to print a message and abort.
You should supply a function that either calls @code{exit}
(@pxref{Program Termination, , , libc, The GNU C Library Reference Manual}) or @code{longjmp} (@pxref{Non-Local
Exits, , , libc, The GNU C Library Reference Manual}) and doesn't return.

@smallexample
void my_obstack_alloc_failed (void)
@dots{}
obstack_alloc_failed_handler = &my_obstack_alloc_failed;
@end smallexample

@end defvar

@node Allocation in an Obstack
@section Allocation in an Obstack
@cindex allocation (obstacks)

The most direct way to allocate an object in an obstack is with
@code{obstack_alloc}, which is invoked almost like @code{malloc}.

@comment obstack.h
@comment GNU
@deftypefun {void *} obstack_alloc (struct obstack *@var{obstack-ptr}, int @var{size})
This allocates an uninitialized block of @var{size} bytes in an obstack
and returns its address.  Here @var{obstack-ptr} specifies which obstack
to allocate the block in; it is the address of the @code{struct obstack}
object which represents the obstack.  Each obstack function or macro
requires you to specify an @var{obstack-ptr} as the first argument.

This function calls the obstack's @code{obstack_chunk_alloc} function if
it needs to allocate a new chunk of memory; it calls
@code{obstack_alloc_failed_handler} if allocation of memory by
@code{obstack_chunk_alloc} failed.
@end deftypefun

For example, here is a function that allocates a copy of a string @var{str}
in a specific obstack, which is in the variable @code{string_obstack}:

@smallexample
struct obstack string_obstack;

char *
copystring (char *string)
@{
  size_t len = strlen (string) + 1;
  char *s = (char *) obstack_alloc (&string_obstack, len);
  memcpy (s, string, len);
  return s;
@}
@end smallexample

To allocate a block with specified contents, use the function
@code{obstack_copy}, declared like this:

@comment obstack.h
@comment GNU
@deftypefun {void *} obstack_copy (struct obstack *@var{obstack-ptr}, void *@var{address}, int @var{size})
This allocates a block and initializes it by copying @var{size}
bytes of data starting at @var{address}.  It calls
@code{obstack_alloc_failed_handler} if allocation of memory by
@code{obstack_chunk_alloc} failed.
@end deftypefun

@comment obstack.h
@comment GNU
@deftypefun {void *} obstack_copy0 (struct obstack *@var{obstack-ptr}, void *@var{address}, int @var{size})
Like @code{obstack_copy}, but appends an extra byte containing a null
character.  This extra byte is not counted in the argument @var{size}.
@end deftypefun

The @code{obstack_copy0} function is convenient for copying a sequence
of characters into an obstack as a null-terminated string.  Here is an
example of its use:

@smallexample
char *
obstack_savestring (char *addr, int size)
@{
  return obstack_copy0 (&myobstack, addr, size);
@}
@end smallexample

@noindent
Contrast this with the previous example of @code{savestring} using
@code{malloc} (@pxref{Basic Allocation, , , libc, The GNU C Library Reference Manual}).

@node Freeing Obstack Objects
@section Freeing Objects in an Obstack
@cindex freeing (obstacks)

To free an object allocated in an obstack, use the function
@code{obstack_free}.  Since the obstack is a stack of objects, freeing
one object automatically frees all other objects allocated more recently
in the same obstack.

@comment obstack.h
@comment GNU
@deftypefun void obstack_free (struct obstack *@var{obstack-ptr}, void *@var{object})
If @var{object} is a null pointer, everything allocated in the obstack
is freed.  Otherwise, @var{object} must be the address of an object
allocated in the obstack.  Then @var{object} is freed, along with
everything allocated in @var{obstack} since @var{object}.
@end deftypefun

Note that if @var{object} is a null pointer, the result is an
uninitialized obstack.  To free all memory in an obstack but leave it
valid for further allocation, call @code{obstack_free} with the address
of the first object allocated on the obstack:

@smallexample
obstack_free (obstack_ptr, first_object_allocated_ptr);
@end smallexample

Recall that the objects in an obstack are grouped into chunks.  When all
the objects in a chunk become free, the obstack library automatically
frees the chunk (@pxref{Preparing for Obstacks}).  Then other
obstacks, or non-obstack allocation, can reuse the space of the chunk.

@node Obstack Functions
@section Obstack Functions and Macros
@cindex macros

The interfaces for using obstacks may be defined either as functions or
as macros, depending on the compiler.  The obstack facility works with
all C compilers, including both @w{ISO C} and traditional C, but there are
precautions you must take if you plan to use compilers other than GNU C.

If you are using an old-fashioned @w{non-ISO C} compiler, all the obstack
``functions'' are actually defined only as macros.  You can call these
macros like functions, but you cannot use them in any other way (for
example, you cannot take their address).

Calling the macros requires a special precaution: namely, the first
operand (the obstack pointer) may not contain any side effects, because
it may be computed more than once.  For example, if you write this:

@smallexample
obstack_alloc (get_obstack (), 4);
@end smallexample

@noindent
you will find that @code{get_obstack} may be called several times.
If you use @code{*obstack_list_ptr++} as the obstack pointer argument,
you will get very strange results since the incrementation may occur
several times.

In @w{ISO C}, each function has both a macro definition and a function
definition.  The function definition is used if you take the address of the
function without calling it.  An ordinary call uses the macro definition by
default, but you can request the function definition instead by writing the
function name in parentheses, as shown here:

@smallexample
char *x;
void *(*funcp) ();
/* @r{Use the macro}.  */
x = (char *) obstack_alloc (obptr, size);
/* @r{Call the function}.  */
x = (char *) (obstack_alloc) (obptr, size);
/* @r{Take the address of the function}.  */
funcp = obstack_alloc;
@end smallexample

@noindent
This is the same situation that exists in @w{ISO C} for the standard library
functions.  @xref{Macro Definitions, , , libc, The GNU C Library Reference Manual}.

@strong{Warning:} When you do use the macros, you must observe the
precaution of avoiding side effects in the first operand, even in @w{ISO C}.

If you use the GNU C compiler, this precaution is not necessary, because
various language extensions in GNU C permit defining the macros so as to
compute each argument only once.

@node Growing Objects
@section Growing Objects
@cindex growing objects (in obstacks)
@cindex changing the size of a block (obstacks)

Because memory in obstack chunks is used sequentially, it is possible to
build up an object step by step, adding one or more bytes at a time to the
end of the object.  With this technique, you do not need to know how much
data you will put in the object until you come to the end of it.  We call
this the technique of @dfn{growing objects}.  The special functions
for adding data to the growing object are described in this section.

You don't need to do anything special when you start to grow an object.
Using one of the functions to add data to the object automatically
starts it.  However, it is necessary to say explicitly when the object is
finished.  This is done with the function @code{obstack_finish}.

The actual address of the object thus built up is not known until the
object is finished.  Until then, it always remains possible that you will
add so much data that the object must be copied into a new chunk.

While the obstack is in use for a growing object, you cannot use it for
ordinary allocation of another object.  If you try to do so, the space
already added to the growing object will become part of the other object.

@comment obstack.h
@comment GNU
@deftypefun void obstack_blank (struct obstack *@var{obstack-ptr}, int @var{size})
The most basic function for adding to a growing object is
@code{obstack_blank}, which adds space without initializing it.
@end deftypefun

@comment obstack.h
@comment GNU
@deftypefun void obstack_grow (struct obstack *@var{obstack-ptr}, void *@var{data}, int @var{size})
To add a block of initialized space, use @code{obstack_grow}, which is
the growing-object analogue of @code{obstack_copy}.  It adds @var{size}
bytes of data to the growing object, copying the contents from
@var{data}.
@end deftypefun

@comment obstack.h
@comment GNU
@deftypefun void obstack_grow0 (struct obstack *@var{obstack-ptr}, void *@var{data}, int @var{size})
This is the growing-object analogue of @code{obstack_copy0}.  It adds
@var{size} bytes copied from @var{data}, followed by an additional null
character.
@end deftypefun

@comment obstack.h
@comment GNU
@deftypefun void obstack_1grow (struct obstack *@var{obstack-ptr}, char @var{c})
To add one character at a time, use the function @code{obstack_1grow}.
It adds a single byte containing @var{c} to the growing object.
@end deftypefun

@comment obstack.h
@comment GNU