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>"
63 .B " size_t sz, len, off;"
64 .B " unsigned push, unshift;"
68 .B "#define DA_INIT ..."
70 .B "#define DAEXC_UFLOW EXC_ALLOCN(EXC_MLIB, ...)"
71 .B "#define DAEXC_OFLOW EXC_ALLOCN(EXC_MLIB, ...)"
73 .BI DA_DECL( type_v ", " type );
74 .BI "void DA_CREATE(" type_v " *" a );
75 .BI "void DA_DESTROY(" type_v " *" a );
77 .BI "void DA_ENSURE(" type_v " *" a ", size_t " n );
78 .BI "void DA_SHUNT(" type_v " *" a ", size_t " n );
79 .BI "void DA_TIDY(" type_v " *" a );
80 .BI "void DA_RESET(" type_v " *" a );
82 .IB type " *DA(" type_v " *" a );
83 .BI "size_t DA_LEN(" type_v " *" a );
84 .BI "size_t DA_SPARE(" type_v " *" a );
85 .BI "size_t DA_OFFSET(" type_v " *" a );
86 .BI "void DA_INCLUDE(" type_v " *" a ", size_t " i );
88 .BI "void DA_EXTEND(" type_v " *" a ", long " n );
89 .BI "void DA_SHRINK(" type_v " *" a ", long " n );
90 .BI "void DA_SLIDE(" type_v " *" a ", long " n );
91 .BI "void DA_UNSLIDE(" type_v " *" a ", long " n );
93 .BI "void DA_UNSAFE_EXTEND(" type_v " *" a ", long " n );
94 .BI "void DA_UNSAFE_SHRINK(" type_v " *" a ", long " n );
95 .BI "void DA_UNSAFE_SLIDE(" type_v " *" a ", long " n );
96 .BI "void DA_UNSAFE_UNSLIDE(" type_v " *" a ", long " n );
98 .IB type " DA_FIRST(" type_v " *" a );
99 .IB type " DA_LAST(" type_v " *" a );
100 .BI "void DA_PUSH(" type_v " *" a ", " type " " x );
101 .IB type " DA_POP(" type_v " *" a );
102 .BI "void DA_UNSHIFT(" type_v " *" a ", " type " " x );
103 .IB type " DA_SHIFT(" type_v " *" a );
105 .BI "void *da_ensure(da_base *" b ", void *" v ", size_t " sz ", size_t " n );
106 .BI "void *da_shunt(da_base *" b ", void *" v ", size_t " sz ", size_t " n );
107 .BI "void *da_tidy(da_base *" b ", void *" v ", size_t " sz );
112 header file declares a collection of types, macros and functions which
113 implement dynamically resizing arrays.
115 The macros described here may evaluate their arguments multiple times
116 unless otherwise specified.
117 .SS "Creation and destruction"
118 Each element type must have its own array
119 type declared using the
123 .BI DA_DECL( type_v ", " type );
125 Declares a new dynamic array type
127 whose elements have type
130 It is conventional to form the name of an array type by appending
132 to the base type name. If the base type is a standard type, or is
133 declared separately from the array, it's also conventional to declare a
134 macro with the same name as the array type only in uppercase which may
135 be used to prevent multiple declarations, e.g.,
144 is a valid static initializer for all types of dynamic arrays. For
145 cases where this isn't appropriate, a dynamic array may be initialized
148 passing it the address of the array.
150 Arrays may be disposed of using the
152 macro, which again takes the address of the array.
153 .SS "Storage allocation"
155 Space for new array elements may be reserved using the
159 macros, which reserve space at the end and beginning of the array
160 respectively. Both macros take two arguments: the address of an array
161 object and the number of spare elements required.
163 Neither of these macros actually extends the array; both merely allocate
164 memory for the array to extend itself into. Use the macros
168 to actually increase the bounds of the array.
170 Note that when space is reserved, all the array elements might move.
171 You should be careful not to depend on the addresses of array elements.
172 If sufficient storage cannot be allocated, the exception
179 takes one argument: the address of a dynamic array. It minimizes the
180 amount of memory used by the array. This is a useful function to call
181 when the array's size has finally settled down.
185 accepts the address of an array. It reduces the length of the array to
186 zero. No storage is deallocated. Resetting arrays might not be a good
187 idea if the objects in the array are dynamically allocated.
188 .SS "Accessing array elements"
191 is the address of a dynamic array object, then
193 is the base address of the actual array. The elements are stored
194 contiguously starting at this address. An element at index
196 may be referenced using the syntax
199 The number of elements in the array
203 An integer array index
212 There may be some spare slots at the end of the array. In particular,
214 .BI DA_ENSURE( a ", " n )
215 there will be at least
217 spare slots. The number of spare slots at the end of the array may be
219 .BI DA_SPARE( a )\fR.
221 Similarly, there may be spare slots before the start of the array. In
222 particular, after a call to
223 .BI DA_SHUNT( a ", " n )
224 there will be at least
226 spare slots. The number of spare slots before the start of the array
228 .BI DA_OFFSET( a )\fR.
231 .BI DA_INCLUDE( a ", " i )
232 ensures that the array's bounds include the index
234 by extending the array if necessary. The exception
236 is thrown if there isn't enough memory to do this.
238 The array's bounds may be extended by
241 .BI DA_EXTEND( a ", " n )\fR.
245 .BI DA_SPARE( a )\fR;
246 if this is not the case then the exception
251 may be negative to reduce the bounds of the array: in this case it must
258 does the same job, but performs no error checking.
261 .BI DA_SLIDE( a ", " n )
262 offsets the array elements by
266 is positive, the array elements are slid upwards, to higher-numbered
269 is negative, the elements are slid downwards. Precisely, what happens
270 is that elements which used to have index
281 .BI DA_OFFSET( a )\fR;
286 .BI \-DA_LEN( a )\fR.
289 does the same job, only without the error checking.
295 do the same things as
299 respectively, except that they interpret the sign of their second
300 arguments in the opposite way. This is useful if the argument is
301 unsigned (e.g., if it's based on
303 There are unsafe versions of both these macros too.
304 .SS "Stack operations"
305 Dynamic arrays support Perl-like stack operations. Given an array
308 and an object of the array's element type
310 the following operations are provided:
312 .BI DA_PUSH( a ", " x )
315 to the end of the array, increasing the array size by one.
317 .IB x " = DA_POP(" a )
318 Remove the final element of the array, assigning
320 its value and decreasing the array size by one.
322 .BI DA_UNSHIFT( a ", " x )
325 at the beginning of the array, shifting all the elements up one place
326 and increasing the array size by one.
328 .IB x " = DA_SHIFT(" a )
329 Remove the first element of the array, assigning
331 its value, shifting all the subsequent array items down one place and
332 decreasing the array size by one.
338 can fail due to lack of memory, in which case
340 is thrown. The operations
344 can fail because the array is empty, in which case
352 are lvalues referring to the first and last elements in the array
353 respectively. They are unsafe if the array is empty.
354 .SS "Low-level details"
355 This section describes low-level details of the dynamic array
356 implementation. You should try to avoid making use of this information
357 if you can, since the interface may change in later library versions.
358 In particular, more subtleties may be added which low-level access will
361 Dynamic arrays are structures with the format
363 .BI "typedef struct " type_v " {"
370 indicates the current base of the array. This will move in the
371 allocated space as a result of
381 structure contains the following elements:
384 The number of allocated slots from
389 The number of items considered to be in the array. The allocated space
390 is usually larger than this.
393 The number of allocated slots preceding
395 The total number of allocated items is therefore
401 The number of items pushed or ensured since the last array expansion.
403 .B "unsigned unshift"
404 The number of items unshifted or shunted since the last array expansion.
410 members are used by the expansion routines to decide how to allocate
411 free space before and after the array elements following a reallocation.
412 The other members should be fairly self-explanatory.
414 The reallocation routines
419 have a regular interface. They're a bit
420 strange, though, because they have to deal with lots of different types
421 of arrays. The arguments they take are:
426 member of the array block.
429 The array base pointer from the array block (i.e., the
434 The element size for the array.
441 only.) The number of spare slots required.
443 The functions may modify the base structure, and return a newly
444 allocated (or at least repositioned) array base pointer, or throw
446 if there's not enough memory.
448 The three functions behave as follows:
451 Ensure that there are at least
453 spare slots after the end of the array.
456 Ensure that there are at least
458 spare slots preceding the start of the array.
461 Reallocate the array to use the smallest amount of memory possible.
466 Mark Wooding, <mdw@distorted.org.uk>