@@@ man wip

[mLib] / struct / darray.3

.\" -*-nroff-*-
.de VS
.sp 1
.RS
.nf
.ft B
..
.de VE
.ft R
.fi
.RE
.sp 1
..
.de hP
.IP
.ft B
\h'-\w'\\$1\ 'u'\\$1\ \c
.ft P
..
.ie t .ds o \(bu
.el .ds o o
.TH darray 3 "21 October 1999" "Straylight/Edgeware" "mLib utilities library"
.SH "NAME"
darray \- dense, dynamically resizing arrays
.\" @DA_INIT
.\" @DA_DECL
.\" @DA_CREATE
.\" @DA_DESTROY
.\" @DA_ENSURE
.\" @DA_SHUNT
.\" @DA_TIDY
.\" @DA_RESET
.\" @DA
.\" @DA_LEN
.\" @DA_SPARE
.\" @DA_OFFSET
.\" @DA_INCLUDE
.\" @DA_EXTEND
.\" @DA_UNSAFE_EXTEND
.\" @DA_SLIDE
.\" @DA_UNSAFE_SLIDE
.\" @DA_SHRINK
.\" @DA_UNSAFE_SHRINK
.\" @DA_UNSLIDE
.\" @DA_UNSAFE_UNSLIDE
.\" @DA_FIRST
.\" @DA_LAST
.\" @DA_PUSH
.\" @DA_POP
.\" @DA_UNSHIFT
.\" @DA_SHIFT
.\" @DAEXC_UFLOW
.\" @DAEXC_OFLOW
.\" @da_ensure
.\" @da_shunt
.\" @da_tidy
.SH "SYNOPSIS"
.nf
.B "#include <mLib/darray.h>"

.ta 2n
.B "typedef struct {"
.B "	size_t sz, len, off;"
.B "	unsigned push, unshift;"
.B "	arena *a;"
.B "} da_base;"

.B "#define DA_INIT ..."

.B "#define DAEXC_UFLOW EXC_ALLOCN(EXC_MLIB, ...)"
.B "#define DAEXC_OFLOW EXC_ALLOCN(EXC_MLIB, ...)"

.BI DA_DECL( type_v ", " type );
.BI "void DA_CREATE(" type_v " *" a );
.BI "void DA_DESTROY(" type_v " *" a );

.BI "void DA_ENSURE(" type_v " *" a ", size_t " n );
.BI "void DA_SHUNT(" type_v " *" a ", size_t " n );
.BI "void DA_TIDY(" type_v " *" a );
.BI "void DA_RESET(" type_v " *" a );

.IB type " *DA(" type_v " *" a );
.BI "size_t DA_LEN(" type_v " *" a );
.BI "size_t DA_SPARE(" type_v " *" a );
.BI "size_t DA_OFFSET(" type_v " *" a );
.BI "void DA_INCLUDE(" type_v " *" a ", size_t " i );

.BI "void DA_EXTEND(" type_v " *" a ", long " n );
.BI "void DA_SHRINK(" type_v " *" a ", long " n );
.BI "void DA_SLIDE(" type_v " *" a ", long " n );
.BI "void DA_UNSLIDE(" type_v " *" a ", long " n );

.BI "void DA_UNSAFE_EXTEND(" type_v " *" a ", long " n );
.BI "void DA_UNSAFE_SHRINK(" type_v " *" a ", long " n );
.BI "void DA_UNSAFE_SLIDE(" type_v " *" a ", long " n );
.BI "void DA_UNSAFE_UNSLIDE(" type_v " *" a ", long " n );

.IB type " DA_FIRST(" type_v " *" a );
.IB type " DA_LAST(" type_v " *" a );
.BI "void DA_PUSH(" type_v " *" a ", " type " " x );
.IB type " DA_POP(" type_v " *" a );
.BI "void DA_UNSHIFT(" type_v " *" a ", " type " " x );
.IB type " DA_SHIFT(" type_v " *" a );

.BI "void *da_ensure(da_base *" b ", void *" v ", size_t " sz ", size_t " n );
.BI "void *da_shunt(da_base *" b ", void *" v ", size_t " sz ", size_t " n );
.BI "void *da_tidy(da_base *" b ", void *" v ", size_t " sz );
.fi
.SH "DESCRIPTION"
The
.B <mLib/darray.h>
header file declares a collection of types, macros and functions which
implement dynamically resizing arrays.
.PP
The macros described here may evaluate their arguments multiple times
unless otherwise specified.
.SS "Creation and destruction"
Each element type must have its own array
type declared using the
.B DA_DECL
macro.  Calling
.VS
.BI DA_DECL( type_v ", " type );
.VE
Declares a new dynamic array type
.I type_v
whose elements have type
.IR type .
.PP
It is conventional to form the name of an array type by appending
.RB ` _v '
to the base type name.  If the base type is a standard type, or is
declared separately from the array, it's also conventional to declare a
macro with the same name as the array type only in uppercase which may
be used to prevent multiple declarations, e.g.,
.VS
#ifndef FOO_V
#  define FOO_V
   DA_DECL(foo_v, foo);
#endif
.VE
The macro
.B DA_INIT
is a valid static initializer for all types of dynamic arrays.  For
cases where this isn't appropriate, a dynamic array may be initialized
using the macro
.BR DA_CREATE ,
passing it the address of the array.
.PP
Arrays may be disposed of using the
.B DA_DESTROY
macro, which again takes the address of the array.
.SS "Storage allocation"
.PP
Space for new array elements may be reserved using the
.B DA_ENSURE
and
.B DA_SHUNT
macros, which reserve space at the end and beginning of the array
respectively.  Both macros take two arguments: the address of an array
object and the number of spare elements required.
.PP
Neither of these macros actually extends the array; both merely allocate
memory for the array to extend itself into.  Use the macros
.B DA_EXTEND
and
.B DA_SLIDE
to actually increase the bounds of the array.
.PP
Note that when space is reserved, all the array elements might move.
You should be careful not to depend on the addresses of array elements.
If sufficient storage cannot be allocated, the exception
.B EXC_NOMEM
is thrown (see
.BR exc (3)).
.PP
The macro
.B DA_TIDY
takes one argument: the address of a dynamic array.  It minimizes the
amount of memory used by the array.  This is a useful function to call
when the array's size has finally settled down.
.PP
The macro
.B DA_RESET
accepts the address of an array.  It reduces the length of the array to
zero.  No storage is deallocated.  Resetting arrays might not be a good
idea if the objects in the array are dynamically allocated.
.SS "Accessing array elements"
If
.I a
is the address of a dynamic array object, then
.BI DA( a )
is the base address of the actual array.  The elements are stored
contiguously starting at this address.  An element at index
.I i
may be referenced using the syntax
.BI DA( a )[ i ]\fR.
.PP
The number of elements in the array
.I a
is given by
.BI DA_LEN( a )\fR.
An integer array index
.I i
is
.I valid
if 0 \(<=
.I i
<
.BI DA_LEN( a )\fR.
.PP
There may be some spare slots at the end of the array.  In particular,
after a call to
.BI DA_ENSURE( a ", " n )
there will be at least
.I n
spare slots.  The number of spare slots at the end of the array may be
obtained as
.BI DA_SPARE( a )\fR.
.PP
Similarly, there may be spare slots before the start of the array.  In
particular, after a call to
.BI DA_SHUNT( a ", " n )
there will be at least
.I n
spare slots.  The number of spare slots before the start of the array
may be obtained as
.BI DA_OFFSET( a )\fR.
.PP
The call
.BI DA_INCLUDE( a ", " i )
ensures that the array's bounds include the index
.I i
by extending the array if necessary.  The exception
.B EXC_NOMEM
is thrown if there isn't enough memory to do this.
.PP
The array's bounds may be extended by
.I n
slots by calling
.BI DA_EXTEND( a ", " n )\fR.
The integer
.I n
must be less than
.BI DA_SPARE( a )\fR;
if this is not the case then the exception
.B DAEXC_OFLOW
is thrown.
Note that
.I n
may be negative to reduce the bounds of the array: in this case it must
be greater than
.BI \-DA_LEN( a )
or the exception
.B DAEXC_UFLOW
is thrown.  The macro
.B DA_UNSAFE_EXTEND
does the same job, but performs no error checking.
.PP
The macro
.BI DA_SLIDE( a ", " n )
offsets the array elements by
.IR n .
If
.I n
is positive, the array elements are slid upwards, to higher-numbered
indices; if
.I n
is negative, the elements are slid downwards.  Precisely, what happens
is that elements which used to have index
.I i
\-
.I n
now have index
.IR i .
The exception
.B DAEXC_OFLOW
is thrown if
.I n
>
.BI DA_OFFSET( a )\fR;
.B DAEXC_UFLOW
is thrown if
.I n
<
.BI \-DA_LEN( a )\fR.
The macro
.B DA_UNSAFE_SLIDE
does the same job, only without the error checking.
.PP
The macros
.B DA_SHRINK
and
.B DA_UNSLIDE
do the same things as
.B DA_EXTEND
and
.B DA_SLIDE
respectively, except that they interpret the sign of their second
arguments in the opposite way.  This is useful if the argument is
unsigned (e.g., if it's based on
.BR DA_LEN ).
There are unsafe versions of both these macros too.
.SS "Stack operations"
Dynamic arrays support Perl-like stack operations.  Given an array
(pointer)
.I a
and an object of the array's element type
.I x
the following operations are provided:
.TP
.BI DA_PUSH( a ", " x )
Add
.I x
to the end of the array, increasing the array size by one.
.TP
.IB x " = DA_POP(" a )
Remove the final element of the array, assigning
.I x
its value and decreasing the array size by one.
.TP
.BI DA_UNSHIFT( a ", " x )
Insert
.I x
at the beginning of the array, shifting all the elements up one place
and increasing the array size by one.
.TP
.IB x " = DA_SHIFT(" a )
Remove the first element of the array, assigning
.I x
its value, shifting all the subsequent array items down one place and
decreasing the array size by one.
.PP
The operations
.B DA_PUSH
and
.B DA_UNSHIFT
can fail due to lack of memory, in which case
.B EXC_NOMEM
is thrown.  The operations
.B DA_POP
and
.B DA_SHIFT
can fail because the array is empty, in which case
.B DAEXC_UFLOW
is thrown.
.PP
The operations
.B DA_FIRST
and
.B DA_LAST
are lvalues referring to the first and last elements in the array
respectively.  They are unsafe if the array is empty.
.SS "Low-level details"
This section describes low-level details of the dynamic array
implementation.  You should try to avoid making use of this information
if you can, since the interface may change in later library versions.
In particular, more subtleties may be added which low-level access will
miss.
.PP
Dynamic arrays are structures with the format
.VS
.BI "typedef struct " type_v " {"
.B "  da_base b;"
.BI "  " type " *v;"
.BI "} " type_v ";"
.VE
The pointer
.B v
indicates the current base of the array.  This will move in the
allocated space as a result of
.B DA_SHIFT
and
.B DA_UNSHIFT
(and
.BR DA_SLIDE )
operations.
.PP
The
.B da_base
structure contains the following elements:
.TP
.B "size_t sz"
The number of allocated slots from
.B v
onwards.
.TP
.B "size_t len"
The number of items considered to be in the array.  The allocated space
is usually larger than this.
.TP
.B "size_t off"
The number of allocated slots preceding
.BR v .
The total number of allocated items is therefore
.B sz
+
.BR off .
.TP
.B "unsigned push"
The number of items pushed or ensured since the last array expansion.
.TP
.B "unsigned unshift"
The number of items unshifted or shunted since the last array expansion.
.PP
The
.B push
and
.B unshift
members are used by the expansion routines to decide how to allocate
free space before and after the array elements following a reallocation.
The other members should be fairly self-explanatory.
.PP
The reallocation routines
.BR da_ensure ,
.B da_shunt
and
.B da_tidy
have a regular interface.  They're a bit
strange, though, because they have to deal with lots of different types
of arrays.  The arguments they take are:
.TP
.BI "da_base *" b
Pointer to the
.B da_base
member of the array block.
.TP
.BI "void *" v
The array base pointer from the array block (i.e., the
.B v
member).
.TP
.BI "size_t " sz
The element size for the array.
.TP
.BI "size_t " n
(For
.B da_ensure
and
.B da_shunt
only.)  The number of spare slots required.
.PP
The functions may modify the base structure, and return a newly
allocated (or at least repositioned) array base pointer, or throw
.B EXC_NOMEM
if there's not enough memory.
.PP
The three functions behave as follows:
.TP
.B da_ensure
Ensure that there are at least
.I n
spare slots after the end of the array.
.TP
.B da_shunt
Ensure that there are at least
.I n
spare slots preceding the start of the array.
.TP
.B da_tidy
Reallocate the array to use the smallest amount of memory possible.
.SH "SEE ALSO"
.BR exc (3),
.BR mLib (3).
.SH "AUTHOR"
Mark Wooding, <mdw@distorted.org.uk>