X-Git-Url: http://www.chiark.greenend.org.uk/ucgi/~mdw/git/mLib/blobdiff_plain/24017b42acbfca3af7a68f5edd286138fc9a09c9..d18364663d0d78b4ba0000372fd432e1f31c2aa9:/man/darray.3 diff --git a/man/darray.3 b/man/darray.3 new file mode 100644 index 0000000..76b0ced --- /dev/null +++ b/man/darray.3 @@ -0,0 +1,400 @@ +.\" -*-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" mLib +.SH "NAME" +darray \- dense, dynamically resizing arrays +.\" @DA_INIT +.\" @DA_DECL +.\" @DA_CREATE +.\" @DA_DESTROY +.\" @DA_ENSURE +.\" @DA_SHUNT +.\" @DA_TIDY +.\" @DA +.\" @DA_LEN +.\" @DA_SPARE +.\" @DA_OFFSET +.\" @DA_INCLUDE +.\" @DA_EXTEND +.\" @DA_UNSAFE_EXTEND +.\" @DA_SLIDE +.\" @DA_UNSAFE_SLIDE +.\" @DA_PUSH +.\" @DA_POP +.\" @DA_UNSHIFT +.\" @DA_SHIFT +.\" @DAEXC_UFLOW +.\" @DAEXC_OFLOW +.\" @da_ensure +.\" @da_shunt +.\" @da_tidy +.SH "SYNOPSIS" +.nf +.B "#include " + +.BI DA_DECL( atype ", " type ); +.IB atype " " a " = DA_INIT;" +.BI "void DA_CREATE(" atype " *" a ); +.BI "void DA_DESTROY(" atype " *" a ); + +.BI "void DA_ENSURE(" atype " *" a ", size_t " n ); +.BI "void DA_SHUNT(" atype " *" a ", size_t " n ); +.BI "void DA_TIDY(" atype " *" a ); + +.IB type " *DA(" atype " *" a ); +.BI "size_t DA_LEN(" atype " *" a ); +.BI "size_t DA_SPARE(" atype " *" a ); +.BI "size_t DA_OFFSET(" atype " *" a ); +.BI "void DA_INCLUDE(" atype " *" a ", size_t " i ); +.BI "void DA_EXTEND(" atype " *" a ", long " n ); +.BI "void DA_UNSAFE_EXTEND(" atype " *" a ", long " n ); +.BI "void DA_SLIDE(" atype " *" a ", long " n ); +.BI "void DA_UNSAFE_SLIDE(" atype " *" a ", long " n ); + +.BI "void DA_PUSH(" atype " *" a ", " type " " x ); +.IB type " DA_POP(" atype " *" a ); +.BI "void DA_UNSHIFT(" atype " *" a ", " type " " x ); +.IB type " DA_SHIFT(" atype " *" 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 +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( atype ", " type ); +.VE +Declares a new dynamic array type +.I atype +whose elements have type +.IR type . +.PP +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_INIT , +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. +.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. +.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. +.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 " atype " {" +.B " da_base b;" +.BI " " type " *v;" +.BI "} " atype ";" +.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,