chiark / gitweb /
Commit as 2.1.0.
[mLib] / darray.3
1 .\" -*-nroff-*-
2 .de VS
3 .sp 1
4 .RS
5 .nf
6 .ft B
7 ..
8 .de VE
9 .ft R
10 .fi
11 .RE
12 .sp 1
13 ..
14 .de hP
15 .IP
16 .ft B
17 \h'-\w'\\$1\ 'u'\\$1\ \c
18 .ft P
19 ..
20 .ie t .ds o \(bu
21 .el .ds o o
22 .TH darray 3 "21 October 1999" "Straylight/Edgeware" "mLib utilities library"
23 .SH "NAME"
24 darray \- dense, dynamically resizing arrays
25 .\" @DA_INIT
26 .\" @DA_DECL
27 .\" @DA_CREATE
28 .\" @DA_DESTROY
29 .\" @DA_ENSURE
30 .\" @DA_SHUNT
31 .\" @DA_TIDY
32 .\" @DA_RESET
33 .\" @DA
34 .\" @DA_LEN
35 .\" @DA_SPARE
36 .\" @DA_OFFSET
37 .\" @DA_INCLUDE
38 .\" @DA_EXTEND
39 .\" @DA_UNSAFE_EXTEND
40 .\" @DA_SLIDE
41 .\" @DA_UNSAFE_SLIDE
42 .\" @DA_SHRINK
43 .\" @DA_UNSAFE_SHRINK
44 .\" @DA_UNSLIDE
45 .\" @DA_UNSAFE_UNSLIDE
46 .\" @DA_FIRST
47 .\" @DA_LAST
48 .\" @DA_PUSH
49 .\" @DA_POP
50 .\" @DA_UNSHIFT
51 .\" @DA_SHIFT
52 .\" @DAEXC_UFLOW
53 .\" @DAEXC_OFLOW
54 .\" @da_ensure
55 .\" @da_shunt
56 .\" @da_tidy
57 .SH "SYNOPSIS"
58 .nf
59 .B "#include <mLib/darray.h>"
60
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 );
65
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 );
70
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 );
76
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 );
81
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 );
86
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 );
93
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 );
97 .fi
98 .SH "DESCRIPTION"
99 The
100 .B <mLib/darray.h>
101 header file declares a collection of types, macros and functions which
102 implement dynamically resizing arrays.
103 .PP
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
109 .B DA_DECL
110 macro.  Calling
111 .VS
112 .BI DA_DECL( type_v ", " type );
113 .VE
114 Declares a new dynamic array type
115 .I type_v
116 whose elements have type
117 .IR type .
118 .PP
119 It is conventional to form the name of an array type by appending
120 .RB ` _v '
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.,
125 .VS
126 #ifndef FOO_V
127 #  define FOO_V
128    DA_DECL(foo_v, foo);
129 #endif
130 .VE
131 The macro
132 .B DA_INIT
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
135 using the macro
136 .BR DA_CREATE ,
137 passing it the address of the array.
138 .PP
139 Arrays may be disposed of using the
140 .B DA_DESTROY
141 macro, which again takes the address of the array.
142 .SS "Storage allocation"
143 .PP
144 Space for new array elements may be reserved using the
145 .B DA_ENSURE
146 and
147 .B DA_SHUNT
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.
151 .PP
152 Neither of these macros actually extends the array; both merely allocate
153 memory for the array to extend itself into.  Use the macros
154 .B DA_EXTEND
155 and
156 .B DA_SLIDE
157 to actually increase the bounds of the array.
158 .PP
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
162 .B EXC_NOMEM
163 is thrown (see
164 .BR exc (3)).
165 .PP
166 The macro
167 .B DA_TIDY
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.
171 .PP
172 The macro
173 .B DA_RESET
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"
178 If
179 .I a
180 is the address of a dynamic array object, then
181 .BI DA( a )
182 is the base address of the actual array.  The elements are stored
183 contiguously starting at this address.  An element at index
184 .I i
185 may be referenced using the syntax
186 .BI DA( a )[ i ]\fR.
187 .PP
188 The number of elements in the array
189 .I a
190 is given by
191 .BI DA_LEN( a )\fR.
192 An integer array index
193 .I i
194 is
195 .I valid
196 if 0 \(<=
197 .I i
198 <
199 .BI DA_LEN( a )\fR.
200 .PP
201 There may be some spare slots at the end of the array.  In particular,
202 after a call to
203 .BI DA_ENSURE( a ", " n )
204 there will be at least
205 .I n
206 spare slots.  The number of spare slots at the end of the array may be
207 obtained as
208 .BI DA_SPARE( a )\fR.
209 .PP
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
214 .I n
215 spare slots.  The number of spare slots before the start of the array
216 may be obtained as
217 .BI DA_OFFSET( a )\fR.
218 .PP
219 The call
220 .BI DA_INCLUDE( a ", " i )
221 ensures that the array's bounds include the index
222 .I i
223 by extending the array if necessary.  The exception
224 .B EXC_NOMEM
225 is thrown if there isn't enough memory to do this.
226 .PP
227 The array's bounds may be extended by
228 .I n
229 slots by calling
230 .BI DA_EXTEND( a ", " n )\fR.
231 The integer
232 .I n
233 must be less than
234 .BI DA_SPARE( a )\fR;
235 if this is not the case then the exception
236 .B DAEXC_OFLOW
237 is thrown.
238 Note that
239 .I n
240 may be negative to reduce the bounds of the array: in this case it must
241 be greater than
242 .BI \-DA_LEN( a )
243 or the exception
244 .B DAEXC_UFLOW
245 is thrown.  The macro
246 .B DA_UNSAFE_EXTEND
247 does the same job, but performs no error checking.
248 .PP
249 The macro
250 .BI DA_SLIDE( a ", " n )
251 offsets the array elements by
252 .IR n .
253 If
254 .I n
255 is positive, the array elements are slid upwards, to higher-numbered
256 indices; if
257 .I n
258 is negative, the elements are slid downwards.  Precisely, what happens
259 is that elements which used to have index
260 .I i
261 \-
262 .I n
263 now have index
264 .IR i .
265 The exception
266 .B DAEXC_OFLOW
267 is thrown if
268 .I n
269 >
270 .BI DA_OFFSET( a )\fR;
271 .B DAEXC_UFLOW
272 is thrown if
273 .I n
274 <
275 .BI \-DA_LEN( a )\fR.
276 The macro
277 .B DA_UNSAFE_SLIDE
278 does the same job, only without the error checking.
279 .PP
280 The macros
281 .B DA_SHRINK
282 and
283 .B DA_UNSLIDE
284 do the same things as
285 .B DA_EXTEND
286 and
287 .B DA_SLIDE
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
291 .BR DA_LEN ).
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
295 (pointer)
296 .I a
297 and an object of the array's element type
298 .I x
299 the following operations are provided:
300 .TP
301 .BI DA_PUSH( a ", " x )
302 Add
303 .I x
304 to the end of the array, increasing the array size by one.
305 .TP
306 .IB x " = DA_POP(" a )
307 Remove the final element of the array, assigning
308 .I x
309 its value and decreasing the array size by one.
310 .TP
311 .BI DA_UNSHIFT( a ", " x )
312 Insert
313 .I x
314 at the beginning of the array, shifting all the elements up one place
315 and increasing the array size by one.
316 .TP
317 .IB x " = DA_SHIFT(" a )
318 Remove the first element of the array, assigning
319 .I x
320 its value, shifting all the subsequent array items down one place and
321 decreasing the array size by one.
322 .PP
323 The operations
324 .B DA_PUSH
325 and
326 .B DA_UNSHIFT
327 can fail due to lack of memory, in which case
328 .B EXC_NOMEM
329 is thrown.  The operations
330 .B DA_POP
331 and
332 .B DA_SHIFT
333 can fail because the array is empty, in which case
334 .B DAEXC_UFLOW
335 is thrown.
336 .PP
337 The operations
338 .B DA_FIRST
339 and
340 .B DA_LAST
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
348 miss.
349 .PP
350 Dynamic arrays are structures with the format
351 .VS
352 .BI "typedef struct " type_v " {"
353 .B "  da_base b;"
354 .BI "  " type " *v;"
355 .BI "} " type_v ";"
356 .VE
357 The pointer
358 .B v
359 indicates the current base of the array.  This will move in the
360 allocated space as a result of
361 .B DA_SHIFT
362 and
363 .B DA_UNSHIFT
364 (and
365 .BR DA_SLIDE )
366 operations.
367 .PP
368 The
369 .B da_base
370 structure contains the following elements:
371 .TP
372 .B "size_t sz"
373 The number of allocated slots from
374 .B v
375 onwards.
376 .TP
377 .B "size_t len"
378 The number of items considered to be in the array.  The allocated space
379 is usually larger than this.
380 .TP
381 .B "size_t off"
382 The number of allocated slots preceding
383 .BR v .
384 The total number of allocated items is therefore
385 .B sz
386 +
387 .BR off .
388 .TP
389 .B "unsigned push"
390 The number of items pushed or ensured since the last array expansion.
391 .TP
392 .B "unsigned unshift"
393 The number of items unshifted or shunted since the last array expansion.
394 .PP
395 The
396 .B push
397 and
398 .B unshift
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.
402 .PP
403 The reallocation routines
404 .BR da_ensure ,
405 .B da_shunt
406 and
407 .B da_tidy
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:
411 .TP
412 .BI "da_base *" b
413 Pointer to the
414 .B da_base
415 member of the array block.
416 .TP
417 .BI "void *" v
418 The array base pointer from the array block (i.e., the
419 .B v
420 member).
421 .TP
422 .BI "size_t " sz
423 The element size for the array.
424 .TP
425 .BI "size_t " n
426 (For
427 .B da_ensure
428 and
429 .B da_shunt
430 only.)  The number of spare slots required.
431 .PP
432 The functions may modify the base structure, and return a newly
433 allocated (or at least repositioned) array base pointer, or throw
434 .B EXC_NOMEM
435 if there's not enough memory.
436 .PP
437 The three functions behave as follows:
438 .TP
439 .B da_ensure
440 Ensure that there are at least
441 .I n
442 spare slots after the end of the array.
443 .TP
444 .B da_shunt
445 Ensure that there are at least
446 .I n
447 spare slots preceding the start of the array.
448 .TP
449 .B da_tidy
450 Reallocate the array to use the smallest amount of memory possible.
451 .SH "SEE ALSO"
452 .BR exc (3),
453 .BR mLib (3).
454 .SH "AUTHOR"
455 Mark Wooding, <mdw@distorted.org.uk>