obstacks.texi

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

@deftypefun void obstack_ptr_grow (struct obstack *@var{obstack-ptr}, void *@var{data})
Adding the value of a pointer one can use the function
@code{obstack_ptr_grow}.  It adds @code{sizeof (void *)} bytes
containing the value of @var{data}.
@end deftypefun

@comment obstack.h
@comment GNU
@deftypefun void obstack_int_grow (struct obstack *@var{obstack-ptr}, int @var{data})
A single value of type @code{int} can be added by using the
@code{obstack_int_grow} function.  It adds @code{sizeof (int)} bytes to
the growing object and initializes them with the value of @var{data}.
@end deftypefun

@comment obstack.h
@comment GNU
@deftypefun {void *} obstack_finish (struct obstack *@var{obstack-ptr})
When you are finished growing the object, use the function
@code{obstack_finish} to close it off and return its final address.

Once you have finished the object, the obstack is available for ordinary
allocation or for growing another object.

This function can return a null pointer under the same conditions as
@code{obstack_alloc} (@pxref{Allocation in an Obstack}).
@end deftypefun

When you build an object by growing it, you will probably need to know
afterward how long it became.  You need not keep track of this as you grow
the object, because you can find out the length from the obstack just
before finishing the object with the function @code{obstack_object_size},
declared as follows:

@comment obstack.h
@comment GNU
@deftypefun int obstack_object_size (struct obstack *@var{obstack-ptr})
This function returns the current size of the growing object, in bytes.
Remember to call this function @emph{before} finishing the object.
After it is finished, @code{obstack_object_size} will return zero.
@end deftypefun

If you have started growing an object and wish to cancel it, you should
finish it and then free it, like this:

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

@noindent
This has no effect if no object was growing.

@cindex shrinking objects
You can use @code{obstack_blank} with a negative size argument to make
the current object smaller.  Just don't try to shrink it beyond zero
length---there's no telling what will happen if you do that.

@node Extra Fast Growing
@section Extra Fast Growing Objects
@cindex efficiency and obstacks

The usual functions for growing objects incur overhead for checking
whether there is room for the new growth in the current chunk.  If you
are frequently constructing objects in small steps of growth, this
overhead can be significant.

You can reduce the overhead by using special ``fast growth''
functions that grow the object without checking.  In order to have a
robust program, you must do the checking yourself.  If you do this checking
in the simplest way each time you are about to add data to the object, you
have not saved anything, because that is what the ordinary growth
functions do.  But if you can arrange to check less often, or check
more efficiently, then you make the program faster.

The function @code{obstack_room} returns the amount of room available
in the current chunk.  It is declared as follows:

@comment obstack.h
@comment GNU
@deftypefun int obstack_room (struct obstack *@var{obstack-ptr})
This returns the number of bytes that can be added safely to the current
growing object (or to an object about to be started) in obstack
@var{obstack} using the fast growth functions.
@end deftypefun

While you know there is room, you can use these fast growth functions
for adding data to a growing object:

@comment obstack.h
@comment GNU
@deftypefun void obstack_1grow_fast (struct obstack *@var{obstack-ptr}, char @var{c})
The function @code{obstack_1grow_fast} adds one byte containing the
character @var{c} to the growing object in obstack @var{obstack-ptr}.
@end deftypefun

@comment obstack.h
@comment GNU
@deftypefun void obstack_ptr_grow_fast (struct obstack *@var{obstack-ptr}, void *@var{data})
The function @code{obstack_ptr_grow_fast} adds @code{sizeof (void *)}
bytes containing the value of @var{data} to the growing object in
obstack @var{obstack-ptr}.
@end deftypefun

@comment obstack.h
@comment GNU
@deftypefun void obstack_int_grow_fast (struct obstack *@var{obstack-ptr}, int @var{data})
The function @code{obstack_int_grow_fast} adds @code{sizeof (int)} bytes
containing the value of @var{data} to the growing object in obstack
@var{obstack-ptr}.
@end deftypefun

@comment obstack.h
@comment GNU
@deftypefun void obstack_blank_fast (struct obstack *@var{obstack-ptr}, int @var{size})
The function @code{obstack_blank_fast} adds @var{size} bytes to the
growing object in obstack @var{obstack-ptr} without initializing them.
@end deftypefun

When you check for space using @code{obstack_room} and there is not
enough room for what you want to add, the fast growth functions
are not safe.  In this case, simply use the corresponding ordinary
growth function instead.  Very soon this will copy the object to a
new chunk; then there will be lots of room available again.

So, each time you use an ordinary growth function, check afterward for
sufficient space using @code{obstack_room}.  Once the object is copied
to a new chunk, there will be plenty of space again, so the program will
start using the fast growth functions again.

Here is an example:

@smallexample
@group
void
add_string (struct obstack *obstack, const char *ptr, int len)
@{
  while (len > 0)
    @{
      int room = obstack_room (obstack);
      if (room == 0)
        @{
          /* @r{Not enough room. Add one character slowly,}
             @r{which may copy to a new chunk and make room.}  */
          obstack_1grow (obstack, *ptr++);
          len--;
        @}
      else
        @{
          if (room > len)
            room = len;
          /* @r{Add fast as much as we have room for.} */
          len -= room;
          while (room-- > 0)
            obstack_1grow_fast (obstack, *ptr++);
        @}
    @}
@}
@end group
@end smallexample

@node Status of an Obstack
@section Status of an Obstack
@cindex obstack status
@cindex status of obstack

Here are functions that provide information on the current status of
allocation in an obstack.  You can use them to learn about an object while
still growing it.

@comment obstack.h
@comment GNU
@deftypefun {void *} obstack_base (struct obstack *@var{obstack-ptr})
This function returns the tentative address of the beginning of the
currently growing object in @var{obstack-ptr}.  If you finish the object
immediately, it will have that address.  If you make it larger first, it
may outgrow the current chunk---then its address will change!

If no object is growing, this value says where the next object you
allocate will start (once again assuming it fits in the current
chunk).
@end deftypefun

@comment obstack.h
@comment GNU
@deftypefun {void *} obstack_next_free (struct obstack *@var{obstack-ptr})
This function returns the address of the first free byte in the current
chunk of obstack @var{obstack-ptr}.  This is the end of the currently
growing object.  If no object is growing, @code{obstack_next_free}
returns the same value as @code{obstack_base}.
@end deftypefun

@comment obstack.h
@comment GNU
@deftypefun int obstack_object_size (struct obstack *@var{obstack-ptr})
This function returns the size in bytes of the currently growing object.
This is equivalent to

@smallexample
obstack_next_free (@var{obstack-ptr}) - obstack_base (@var{obstack-ptr})
@end smallexample
@end deftypefun

@node Obstacks Data Alignment
@section Alignment of Data in Obstacks
@cindex alignment (in obstacks)

Each obstack has an @dfn{alignment boundary}; each object allocated in
the obstack automatically starts on an address that is a multiple of the
specified boundary.  By default, this boundary is 4 bytes.

To access an obstack's alignment boundary, use the macro
@code{obstack_alignment_mask}, whose function prototype looks like
this:

@comment obstack.h
@comment GNU
@deftypefn Macro int obstack_alignment_mask (struct obstack *@var{obstack-ptr})
The value is a bit mask; a bit that is 1 indicates that the corresponding
bit in the address of an object should be 0.  The mask value should be one
less than a power of 2; the effect is that all object addresses are
multiples of that power of 2.  The default value of the mask is 3, so that
addresses are multiples of 4.  A mask value of 0 means an object can start
on any multiple of 1 (that is, no alignment is required).

The expansion of the macro @code{obstack_alignment_mask} is an lvalue,
so you can alter the mask by assignment.  For example, this statement:

@smallexample
obstack_alignment_mask (obstack_ptr) = 0;
@end smallexample

@noindent
has the effect of turning off alignment processing in the specified obstack.
@end deftypefn

Note that a change in alignment mask does not take effect until
@emph{after} the next time an object is allocated or finished in the
obstack.  If you are not growing an object, you can make the new
alignment mask take effect immediately by calling @code{obstack_finish}.
This will finish a zero-length object and then do proper alignment for
the next object.

@node Obstack Chunks
@section Obstack Chunks
@cindex efficiency of chunks
@cindex chunks

Obstacks work by allocating space for themselves in large chunks, and
then parceling out space in the chunks to satisfy your requests.  Chunks
are normally 4096 bytes long unless you specify a different chunk size.
The chunk size includes 8 bytes of overhead that are not actually used
for storing objects.  Regardless of the specified size, longer chunks
will be allocated when necessary for long objects.

The obstack library allocates chunks by calling the function
@code{obstack_chunk_alloc}, which you must define.  When a chunk is no
longer needed because you have freed all the objects in it, the obstack
library frees the chunk by calling @code{obstack_chunk_free}, which you
must also define.

These two must be defined (as macros) or declared (as functions) in each
source file that uses @code{obstack_init} (@pxref{Creating Obstacks}).
Most often they are defined as macros like this:

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

Note that these are simple macros (no arguments).  Macro definitions with
arguments will not work!  It is necessary that @code{obstack_chunk_alloc}
or @code{obstack_chunk_free}, alone, expand into a function name if it is
not itself a function name.

If you allocate chunks with @code{malloc}, the chunk size should be a
power of 2.  The default chunk size, 4096, was chosen because it is long
enough to satisfy many typical requests on the obstack yet short enough
not to waste too much memory in the portion of the last chunk not yet used.

@comment obstack.h
@comment GNU
@deftypefn Macro int obstack_chunk_size (struct obstack *@var{obstack-ptr})
This returns the chunk size of the given obstack.
@end deftypefn

Since this macro expands to an lvalue, you can specify a new chunk size by
assigning it a new value.  Doing so does not affect the chunks already
allocated, but will change the size of chunks allocated for that particular
obstack in the future.  It is unlikely to be useful to make the chunk size
smaller, but making it larger might improve efficiency if you are
allocating many objects whose size is comparable to the chunk size.  Here
is how to do so cleanly:

@smallexample
if (obstack_chunk_size (obstack_ptr) < @var{new-chunk-size})
  obstack_chunk_size (obstack_ptr) = @var{new-chunk-size};
@end smallexample

@node Summary of Obstacks
@section Summary of Obstack Functions

Here is a summary of all the functions associated with obstacks.  Each
takes the address of an obstack (@code{struct obstack *}) as its first
argument.

@table @code
@item void obstack_init (struct obstack *@var{obstack-ptr})
Initialize use of an obstack.  @xref{Creating Obstacks}.

@item void *obstack_alloc (struct obstack *@var{obstack-ptr}, int @var{size})
Allocate an object of @var{size} uninitialized bytes.
@xref{Allocation in an Obstack}.

@item void *obstack_copy (struct obstack *@var{obstack-ptr}, void *@var{address}, int @var{size})
Allocate an object of @var{size} bytes, with contents copied from
@var{address}.  @xref{Allocation in an Obstack}.

@item void *obstack_copy0 (struct obstack *@var{obstack-ptr}, void *@var{address}, int @var{size})
Allocate an object of @var{size}+1 bytes, with @var{size} of them copied
from @var{address}, followed by a null character at the end.
@xref{Allocation in an Obstack}.

@item void obstack_free (struct obstack *@var{obstack-ptr}, void *@var{object})
Free @var{object} (and everything allocated in the specified obstack
more recently than @var{object}).  @xref{Freeing Obstack Objects}.

@item void obstack_blank (struct obstack *@var{obstack-ptr}, int @var{size})
Add @var{size} uninitialized bytes to a growing object.
@xref{Growing Objects}.

@item void obstack_grow (struct obstack *@var{obstack-ptr}, void *@var{address}, int @var{size})
Add @var{size} bytes, copied from @var{address}, to a growing object.
@xref{Growing Objects}.

@item void obstack_grow0 (struct obstack *@var{obstack-ptr}, void *@var{address}, int @var{size})
Add @var{size} bytes, copied from @var{address}, to a growing object,
and then add another byte containing a null character.  @xref{Growing
Objects}.

@item void obstack_1grow (struct obstack *@var{obstack-ptr}, char @var{data-char})
Add one byte containing @var{data-char} to a growing object.
@xref{Growing Objects}.

@item void *obstack_finish (struct obstack *@var{obstack-ptr})
Finalize the object that is growing and return its permanent address.
@xref{Growing Objects}.

@item int obstack_object_size (struct obstack *@var{obstack-ptr})
Get the current size of the currently growing object.  @xref{Growing
Objects}.

@item void obstack_blank_fast (struct obstack *@var{obstack-ptr}, int @var{size})
Add @var{size} uninitialized bytes to a growing object without checking
that there is enough room.  @xref{Extra Fast Growing}.

@item void obstack_1grow_fast (struct obstack *@var{obstack-ptr}, char @var{data-char})
Add one byte containing @var{data-char} to a growing object without
checking that there is enough room.  @xref{Extra Fast Growing}.

@item int obstack_room (struct obstack *@var{obstack-ptr})
Get the amount of room now available for growing the current object.
@xref{Extra Fast Growing}.

@item int obstack_alignment_mask (struct obstack *@var{obstack-ptr})
The mask used for aligning the beginning of an object.  This is an
lvalue.  @xref{Obstacks Data Alignment}.

@item int obstack_chunk_size (struct obstack *@var{obstack-ptr})
The size for allocating chunks.  This is an lvalue.  @xref{Obstack Chunks}.

@item void *obstack_base (struct obstack *@var{obstack-ptr})
Tentative starting address of the currently growing object.
@xref{Status of an Obstack}.

@item void *obstack_next_free (struct obstack *@var{obstack-ptr})
Address just after the end of the currently growing object.
@xref{Status of an Obstack}.
@end table