17 \h'-\w'\\$1\ 'u'\\$1\ \c
22 .TH darray 3 "21 October 1999" mLib
24 darray \- dense, dynamically resizing arrays
45 .\" @DA_UNSAFE_UNSLIDE
57 .B "#include <mLib/darray.h>"
59 .BI DA_DECL( type_v ", " type );
60 .IB type_v " " a " = DA_INIT;"
61 .BI "void DA_CREATE(" type_v " *" a );
62 .BI "void DA_DESTROY(" type_v " *" a );
64 .BI "void DA_ENSURE(" type_v " *" a ", size_t " n );
65 .BI "void DA_SHUNT(" type_v " *" a ", size_t " n );
66 .BI "void DA_TIDY(" type_v " *" a );
67 .BI "void DA_RESET(" type_v " *" a );
69 .IB type " *DA(" type_v " *" a );
70 .BI "size_t DA_LEN(" type_v " *" a );
71 .BI "size_t DA_SPARE(" type_v " *" a );
72 .BI "size_t DA_OFFSET(" type_v " *" a );
73 .BI "void DA_INCLUDE(" type_v " *" a ", size_t " i );
75 .BI "void DA_EXTEND(" type_v " *" a ", long " n );
76 .BI "void DA_SHRINK(" type_v " *" a ", long " n );
77 .BI "void DA_SLIDE(" type_v " *" a ", long " n );
78 .BI "void DA_UNSLIDE(" type_v " *" a ", long " n );
80 .BI "void DA_UNSAFE_EXTEND(" type_v " *" a ", long " n );
81 .BI "void DA_UNSAFE_SHRINK(" type_v " *" a ", long " n );
82 .BI "void DA_UNSAFE_SLIDE(" type_v " *" a ", long " n );
83 .BI "void DA_UNSAFE_UNSLIDE(" type_v " *" a ", long " n );
85 .BI "void DA_PUSH(" type_v " *" a ", " type " " x );
86 .IB type " DA_POP(" type_v " *" a );
87 .BI "void DA_UNSHIFT(" type_v " *" a ", " type " " x );
88 .IB type " DA_SHIFT(" type_v " *" a );
90 .BI "void *da_ensure(da_base *" b ", void *" v ", size_t " sz ", size_t " n );
91 .BI "void *da_shunt(da_base *" b ", void *" v ", size_t " sz ", size_t " n );
92 .BI "void *da_tidy(da_base *" b ", void *" v ", size_t " sz );
97 declares a collection of types, macros and functions which implement
98 dynamically resizing arrays.
100 The macros described here may evaluate their arguments multiple times
101 unless otherwise specified.
102 .SS "Creation and destruction"
103 Each element type must have its own array
104 type declared using the
108 .BI DA_DECL( type_v ", " type );
110 Declares a new dynamic array type
112 whose elements have type
115 It is conventional to form the name of an array type by appending
117 to the base type name. If the base type is a standard type, or is
118 declared separately from the array, it's also conventional to declare a
119 macro with the same name as the array type only in uppercase which may
120 be used to prevent multiple declarations, e.g.,
129 is a valid static initializer for all types of dynamic arrays. For
130 cases where this isn't appropriate, a dynamic array may be initialized
133 passing it the address of the array.
135 Arrays may be disposed of using the
137 macro, which again takes the address of the array.
138 .SS "Storage allocation"
140 Space for new array elements may be reserved using the
144 macros, which reserve space at the end and beginning of the array
145 respectively. Both macros take two arguments: the address of an array
146 object and the number of spare elements required.
148 Neither of these macros actually extends the array; both merely allocate
149 memory for the array to extend itself into. Use the macros
153 to actually increase the bounds of the array.
155 Note that when space is reserved, all the array elements might move.
156 You should be careful not to depend on the addresses of array elements.
157 If sufficient storage cannot be allocated, the exception
164 takes one argument: the address of a dynamic array. It minimizes the
165 amount of memory used by the array. This is a useful function to call
166 when the array's size has finally settled down.
170 accepts the address of an array. It reduces the length of the array to
171 zero. No storage is deallocated. Resetting arrays might not be a good
172 idea if the objects in the array are dynamically allocated.
173 .SS "Accessing array elements"
176 is the address of a dynamic array object, then
178 is the base address of the actual array. The elements are stored
179 contiguously starting at this address. An element at index
181 may be referenced using the syntax
184 The number of elements in the array
188 An integer array index
197 There may be some spare slots at the end of the array. In particular,
199 .BI DA_ENSURE( a ", " n )
200 there will be at least
202 spare slots. The number of spare slots at the end of the array may be
204 .BI DA_SPARE( a )\fR.
206 Similarly, there may be spare slots before the start of the array. In
207 particular, after a call to
208 .BI DA_SHUNT( a ", " n )
209 there will be at least
211 spare slots. The number of spare slots before the start of the array
213 .BI DA_OFFSET( a )\fR.
216 .BI DA_INCLUDE( a ", " i )
217 ensures that the array's bounds include the index
219 by extending the array if necessary. The exception
221 is thrown if there isn't enough memory to do this.
223 The array's bounds may be extended by
226 .BI DA_EXTEND( a ", " n )\fR.
230 .BI DA_SPARE( a )\fR;
231 if this is not the case then the exception
236 may be negative to reduce the bounds of the array: in this case it must
243 does the same job, but performs no error checking.
246 .BI DA_SLIDE( a ", " n )
247 offsets the array elements by
251 is positive, the array elements are slid upwards, to higher-numbered
254 is negative, the elements are slid downwards. Precisely, what happens
255 is that elements which used to have index
266 .BI DA_OFFSET( a )\fR;
271 .BI \-DA_LEN( a )\fR.
274 does the same job, only without the error checking.
280 do the same things as
284 respectively, except that they interpret the sign of their second
285 arguments in the opposite way. This is useful if the argument is
286 unsigned (e.g., if it's based on
288 There are unsafe versions of both these macros too.
289 .SS "Stack operations"
290 Dynamic arrays support Perl-like stack operations. Given an array
293 and an object of the array's element type
295 the following operations are provided:
297 .BI DA_PUSH( a ", " x )
300 to the end of the array, increasing the array size by one.
302 .IB x " = DA_POP(" a )
303 Remove the final element of the array, assigning
305 its value and decreasing the array size by one.
307 .BI DA_UNSHIFT( a ", " x )
310 at the beginning of the array, shifting all the elements up one place
311 and increasing the array size by one.
313 .IB x " = DA_SHIFT(" a )
314 Remove the first element of the array, assigning
316 its value, shifting all the subsequent array items down one place and
317 decreasing the array size by one.
323 can fail due to lack of memory, in which case
325 is thrown. The operations
329 can fail because the array is empty, in which case
332 .SS "Low-level details"
333 This section describes low-level details of the dynamic array
334 implementation. You should try to avoid making use of this information
335 if you can, since the interface may change in later library versions.
336 In particular, more subtleties may be added which low-level access will
339 Dynamic arrays are structures with the format
341 .BI "typedef struct " type_v " {"
348 indicates the current base of the array. This will move in the
349 allocated space as a result of
359 structure contains the following elements:
362 The number of allocated slots from
367 The number of items considered to be in the array. The allocated space
368 is usually larger than this.
371 The number of allocated slots preceding
373 The total number of allocated items is therefore
379 The number of items pushed or ensured since the last array expansion.
381 .B "unsigned unshift"
382 The number of items unshifted or shunted since the last array expansion.
388 members are used by the expansion routines to decide how to allocate
389 free space before and after the array elements following a reallocation.
390 The other members should be fairly self-explanatory.
392 The reallocation routines
397 have a regular interface. They're a bit
398 strange, though, because they have to deal with lots of different types
399 of arrays. The arguments they take are:
404 member of the array block.
407 The array base pointer from the array block (i.e., the
412 The element size for the array.
419 only.) The number of spare slots required.
421 The functions may modify the base structure, and return a newly
422 allocated (or at least repositioned) array base pointer, or throw
424 if there's not enough memory.
426 The three functions behave as follows:
429 Ensure that there are at least
431 spare slots after the end of the array.
434 Ensure that there are at least
436 spare slots preceding the start of the array.
439 Reallocate the array to use the smallest amount of memory possible.
444 Mark Wooding, <mdw@nsict.org>