17 \h'-\w'\\$1\ 'u'\\$1\ \c
22 .TH darray 3 "21 October 1999" "Straylight/Edgeware" "mLib utilities library"
24 darray \- dense, dynamically resizing arrays
45 .\" @DA_UNSAFE_UNSLIDE
59 .B "#include <mLib/darray.h>"
61 .BI DA_DECL( type_v ", " type );
62 .IB type_v " " a " = DA_INIT;"
63 .BI "void DA_CREATE(" type_v " *" a );
64 .BI "void DA_DESTROY(" type_v " *" a );
66 .BI "void DA_ENSURE(" type_v " *" a ", size_t " n );
67 .BI "void DA_SHUNT(" type_v " *" a ", size_t " n );
68 .BI "void DA_TIDY(" type_v " *" a );
69 .BI "void DA_RESET(" type_v " *" a );
71 .IB type " *DA(" type_v " *" a );
72 .BI "size_t DA_LEN(" type_v " *" a );
73 .BI "size_t DA_SPARE(" type_v " *" a );
74 .BI "size_t DA_OFFSET(" type_v " *" a );
75 .BI "void DA_INCLUDE(" type_v " *" a ", size_t " i );
77 .BI "void DA_EXTEND(" type_v " *" a ", long " n );
78 .BI "void DA_SHRINK(" type_v " *" a ", long " n );
79 .BI "void DA_SLIDE(" type_v " *" a ", long " n );
80 .BI "void DA_UNSLIDE(" type_v " *" a ", long " n );
82 .BI "void DA_UNSAFE_EXTEND(" type_v " *" a ", long " n );
83 .BI "void DA_UNSAFE_SHRINK(" type_v " *" a ", long " n );
84 .BI "void DA_UNSAFE_SLIDE(" type_v " *" a ", long " n );
85 .BI "void DA_UNSAFE_UNSLIDE(" type_v " *" a ", long " n );
87 .IB type " DA_FIRST(" type_v " *" a );
88 .IB type " DA_LAST(" type_v " *" a );
89 .BI "void DA_PUSH(" type_v " *" a ", " type " " x );
90 .IB type " DA_POP(" type_v " *" a );
91 .BI "void DA_UNSHIFT(" type_v " *" a ", " type " " x );
92 .IB type " DA_SHIFT(" type_v " *" a );
94 .BI "void *da_ensure(da_base *" b ", void *" v ", size_t " sz ", size_t " n );
95 .BI "void *da_shunt(da_base *" b ", void *" v ", size_t " sz ", size_t " n );
96 .BI "void *da_tidy(da_base *" b ", void *" v ", size_t " sz );
101 header file declares a collection of types, macros and functions which
102 implement dynamically resizing arrays.
104 The macros described here may evaluate their arguments multiple times
105 unless otherwise specified.
106 .SS "Creation and destruction"
107 Each element type must have its own array
108 type declared using the
112 .BI DA_DECL( type_v ", " type );
114 Declares a new dynamic array type
116 whose elements have type
119 It is conventional to form the name of an array type by appending
121 to the base type name. If the base type is a standard type, or is
122 declared separately from the array, it's also conventional to declare a
123 macro with the same name as the array type only in uppercase which may
124 be used to prevent multiple declarations, e.g.,
133 is a valid static initializer for all types of dynamic arrays. For
134 cases where this isn't appropriate, a dynamic array may be initialized
137 passing it the address of the array.
139 Arrays may be disposed of using the
141 macro, which again takes the address of the array.
142 .SS "Storage allocation"
144 Space for new array elements may be reserved using the
148 macros, which reserve space at the end and beginning of the array
149 respectively. Both macros take two arguments: the address of an array
150 object and the number of spare elements required.
152 Neither of these macros actually extends the array; both merely allocate
153 memory for the array to extend itself into. Use the macros
157 to actually increase the bounds of the array.
159 Note that when space is reserved, all the array elements might move.
160 You should be careful not to depend on the addresses of array elements.
161 If sufficient storage cannot be allocated, the exception
168 takes one argument: the address of a dynamic array. It minimizes the
169 amount of memory used by the array. This is a useful function to call
170 when the array's size has finally settled down.
174 accepts the address of an array. It reduces the length of the array to
175 zero. No storage is deallocated. Resetting arrays might not be a good
176 idea if the objects in the array are dynamically allocated.
177 .SS "Accessing array elements"
180 is the address of a dynamic array object, then
182 is the base address of the actual array. The elements are stored
183 contiguously starting at this address. An element at index
185 may be referenced using the syntax
188 The number of elements in the array
192 An integer array index
201 There may be some spare slots at the end of the array. In particular,
203 .BI DA_ENSURE( a ", " n )
204 there will be at least
206 spare slots. The number of spare slots at the end of the array may be
208 .BI DA_SPARE( a )\fR.
210 Similarly, there may be spare slots before the start of the array. In
211 particular, after a call to
212 .BI DA_SHUNT( a ", " n )
213 there will be at least
215 spare slots. The number of spare slots before the start of the array
217 .BI DA_OFFSET( a )\fR.
220 .BI DA_INCLUDE( a ", " i )
221 ensures that the array's bounds include the index
223 by extending the array if necessary. The exception
225 is thrown if there isn't enough memory to do this.
227 The array's bounds may be extended by
230 .BI DA_EXTEND( a ", " n )\fR.
234 .BI DA_SPARE( a )\fR;
235 if this is not the case then the exception
240 may be negative to reduce the bounds of the array: in this case it must
247 does the same job, but performs no error checking.
250 .BI DA_SLIDE( a ", " n )
251 offsets the array elements by
255 is positive, the array elements are slid upwards, to higher-numbered
258 is negative, the elements are slid downwards. Precisely, what happens
259 is that elements which used to have index
270 .BI DA_OFFSET( a )\fR;
275 .BI \-DA_LEN( a )\fR.
278 does the same job, only without the error checking.
284 do the same things as
288 respectively, except that they interpret the sign of their second
289 arguments in the opposite way. This is useful if the argument is
290 unsigned (e.g., if it's based on
292 There are unsafe versions of both these macros too.
293 .SS "Stack operations"
294 Dynamic arrays support Perl-like stack operations. Given an array
297 and an object of the array's element type
299 the following operations are provided:
301 .BI DA_PUSH( a ", " x )
304 to the end of the array, increasing the array size by one.
306 .IB x " = DA_POP(" a )
307 Remove the final element of the array, assigning
309 its value and decreasing the array size by one.
311 .BI DA_UNSHIFT( a ", " x )
314 at the beginning of the array, shifting all the elements up one place
315 and increasing the array size by one.
317 .IB x " = DA_SHIFT(" a )
318 Remove the first element of the array, assigning
320 its value, shifting all the subsequent array items down one place and
321 decreasing the array size by one.
327 can fail due to lack of memory, in which case
329 is thrown. The operations
333 can fail because the array is empty, in which case
341 are lvalues referring to the first and last elements in the array
342 respectively. They are unsafe if the array is empty.
343 .SS "Low-level details"
344 This section describes low-level details of the dynamic array
345 implementation. You should try to avoid making use of this information
346 if you can, since the interface may change in later library versions.
347 In particular, more subtleties may be added which low-level access will
350 Dynamic arrays are structures with the format
352 .BI "typedef struct " type_v " {"
359 indicates the current base of the array. This will move in the
360 allocated space as a result of
370 structure contains the following elements:
373 The number of allocated slots from
378 The number of items considered to be in the array. The allocated space
379 is usually larger than this.
382 The number of allocated slots preceding
384 The total number of allocated items is therefore
390 The number of items pushed or ensured since the last array expansion.
392 .B "unsigned unshift"
393 The number of items unshifted or shunted since the last array expansion.
399 members are used by the expansion routines to decide how to allocate
400 free space before and after the array elements following a reallocation.
401 The other members should be fairly self-explanatory.
403 The reallocation routines
408 have a regular interface. They're a bit
409 strange, though, because they have to deal with lots of different types
410 of arrays. The arguments they take are:
415 member of the array block.
418 The array base pointer from the array block (i.e., the
423 The element size for the array.
430 only.) The number of spare slots required.
432 The functions may modify the base structure, and return a newly
433 allocated (or at least repositioned) array base pointer, or throw
435 if there's not enough memory.
437 The three functions behave as follows:
440 Ensure that there are at least
442 spare slots after the end of the array.
445 Ensure that there are at least
447 spare slots preceding the start of the array.
450 Reallocate the array to use the smallest amount of memory possible.
455 Mark Wooding, <mdw@distorted.org.uk>