+++ /dev/null
-.\" -*-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>"
-
-.BI DA_DECL( type_v ", " type );
-.IB type_v " " a " = DA_INIT;"
-.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>
~mdw / mLib / blobdiff