Commit | Line | Data |
---|---|---|
d1836466 | 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 | |
fbf20b5b | 22 | .TH darray 3 "21 October 1999" "Straylight/Edgeware" "mLib utilities library" |
d1836466 | 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 | |
85bb21f7 | 32 | .\" @DA_RESET |
d1836466 | 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 | |
85bb21f7 | 42 | .\" @DA_SHRINK |
43 | .\" @DA_UNSAFE_SHRINK | |
44 | .\" @DA_UNSLIDE | |
45 | .\" @DA_UNSAFE_UNSLIDE | |
706bf01d | 46 | .\" @DA_FIRST |
47 | .\" @DA_LAST | |
d1836466 | 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 | ||
4729aa69 MW |
61 | .B "typedef struct {" |
62 | .B "\h'4n'size_t sz, len, off;" | |
63 | .B "\h'4n'unsigned push, unshift;" | |
64 | .B "\h'4n'arena *a;" | |
65 | .B "} da_base;" | |
66 | ||
67 | .B "#define DA_INIT ..." | |
68 | ||
69 | .B "#define DAEXC_UFLOW EXC_ALLOCN(EXC_MLIB, ...)" | |
70 | .B "#define DAEXC_OFLOW EXC_ALLOCN(EXC_MLIB, ...)" | |
71 | ||
bcb99985 | 72 | .BI DA_DECL( type_v ", " type ); |
bcb99985 | 73 | .BI "void DA_CREATE(" type_v " *" a ); |
74 | .BI "void DA_DESTROY(" type_v " *" a ); | |
d1836466 | 75 | |
bcb99985 | 76 | .BI "void DA_ENSURE(" type_v " *" a ", size_t " n ); |
77 | .BI "void DA_SHUNT(" type_v " *" a ", size_t " n ); | |
78 | .BI "void DA_TIDY(" type_v " *" a ); | |
79 | .BI "void DA_RESET(" type_v " *" a ); | |
d1836466 | 80 | |
bcb99985 | 81 | .IB type " *DA(" type_v " *" a ); |
82 | .BI "size_t DA_LEN(" type_v " *" a ); | |
83 | .BI "size_t DA_SPARE(" type_v " *" a ); | |
84 | .BI "size_t DA_OFFSET(" type_v " *" a ); | |
85 | .BI "void DA_INCLUDE(" type_v " *" a ", size_t " i ); | |
85bb21f7 | 86 | |
bcb99985 | 87 | .BI "void DA_EXTEND(" type_v " *" a ", long " n ); |
88 | .BI "void DA_SHRINK(" type_v " *" a ", long " n ); | |
89 | .BI "void DA_SLIDE(" type_v " *" a ", long " n ); | |
90 | .BI "void DA_UNSLIDE(" type_v " *" a ", long " n ); | |
85bb21f7 | 91 | |
bcb99985 | 92 | .BI "void DA_UNSAFE_EXTEND(" type_v " *" a ", long " n ); |
93 | .BI "void DA_UNSAFE_SHRINK(" type_v " *" a ", long " n ); | |
94 | .BI "void DA_UNSAFE_SLIDE(" type_v " *" a ", long " n ); | |
95 | .BI "void DA_UNSAFE_UNSLIDE(" type_v " *" a ", long " n ); | |
d1836466 | 96 | |
706bf01d | 97 | .IB type " DA_FIRST(" type_v " *" a ); |
98 | .IB type " DA_LAST(" type_v " *" a ); | |
bcb99985 | 99 | .BI "void DA_PUSH(" type_v " *" a ", " type " " x ); |
100 | .IB type " DA_POP(" type_v " *" a ); | |
101 | .BI "void DA_UNSHIFT(" type_v " *" a ", " type " " x ); | |
102 | .IB type " DA_SHIFT(" type_v " *" a ); | |
d1836466 | 103 | |
104 | .BI "void *da_ensure(da_base *" b ", void *" v ", size_t " sz ", size_t " n ); | |
105 | .BI "void *da_shunt(da_base *" b ", void *" v ", size_t " sz ", size_t " n ); | |
106 | .BI "void *da_tidy(da_base *" b ", void *" v ", size_t " sz ); | |
107 | .fi | |
108 | .SH "DESCRIPTION" | |
109 | The | |
110 | .B <mLib/darray.h> | |
d0053e2e | 111 | header file declares a collection of types, macros and functions which |
112 | implement dynamically resizing arrays. | |
d1836466 | 113 | .PP |
114 | The macros described here may evaluate their arguments multiple times | |
115 | unless otherwise specified. | |
116 | .SS "Creation and destruction" | |
117 | Each element type must have its own array | |
118 | type declared using the | |
119 | .B DA_DECL | |
120 | macro. Calling | |
121 | .VS | |
bcb99985 | 122 | .BI DA_DECL( type_v ", " type ); |
d1836466 | 123 | .VE |
124 | Declares a new dynamic array type | |
bcb99985 | 125 | .I type_v |
d1836466 | 126 | whose elements have type |
127 | .IR type . | |
128 | .PP | |
bcb99985 | 129 | It is conventional to form the name of an array type by appending |
130 | .RB ` _v ' | |
131 | to the base type name. If the base type is a standard type, or is | |
132 | declared separately from the array, it's also conventional to declare a | |
133 | macro with the same name as the array type only in uppercase which may | |
134 | be used to prevent multiple declarations, e.g., | |
135 | .VS | |
136 | #ifndef FOO_V | |
137 | # define FOO_V | |
cededfbe | 138 | DA_DECL(foo_v, foo); |
bcb99985 | 139 | #endif |
140 | .VE | |
d1836466 | 141 | The macro |
142 | .B DA_INIT | |
143 | is a valid static initializer for all types of dynamic arrays. For | |
144 | cases where this isn't appropriate, a dynamic array may be initialized | |
145 | using the macro | |
8f7d402a | 146 | .BR DA_CREATE , |
d1836466 | 147 | passing it the address of the array. |
148 | .PP | |
149 | Arrays may be disposed of using the | |
150 | .B DA_DESTROY | |
151 | macro, which again takes the address of the array. | |
152 | .SS "Storage allocation" | |
153 | .PP | |
154 | Space for new array elements may be reserved using the | |
155 | .B DA_ENSURE | |
156 | and | |
157 | .B DA_SHUNT | |
158 | macros, which reserve space at the end and beginning of the array | |
159 | respectively. Both macros take two arguments: the address of an array | |
160 | object and the number of spare elements required. | |
161 | .PP | |
162 | Neither of these macros actually extends the array; both merely allocate | |
163 | memory for the array to extend itself into. Use the macros | |
164 | .B DA_EXTEND | |
165 | and | |
166 | .B DA_SLIDE | |
167 | to actually increase the bounds of the array. | |
168 | .PP | |
169 | Note that when space is reserved, all the array elements might move. | |
170 | You should be careful not to depend on the addresses of array elements. | |
171 | If sufficient storage cannot be allocated, the exception | |
172 | .B EXC_NOMEM | |
173 | is thrown (see | |
174 | .BR exc (3)). | |
175 | .PP | |
176 | The macro | |
177 | .B DA_TIDY | |
178 | takes one argument: the address of a dynamic array. It minimizes the | |
179 | amount of memory used by the array. This is a useful function to call | |
180 | when the array's size has finally settled down. | |
85bb21f7 | 181 | .PP |
182 | The macro | |
183 | .B DA_RESET | |
184 | accepts the address of an array. It reduces the length of the array to | |
185 | zero. No storage is deallocated. Resetting arrays might not be a good | |
186 | idea if the objects in the array are dynamically allocated. | |
d1836466 | 187 | .SS "Accessing array elements" |
188 | If | |
189 | .I a | |
190 | is the address of a dynamic array object, then | |
191 | .BI DA( a ) | |
192 | is the base address of the actual array. The elements are stored | |
193 | contiguously starting at this address. An element at index | |
194 | .I i | |
195 | may be referenced using the syntax | |
8f7d402a | 196 | .BI DA( a )[ i ]\fR. |
d1836466 | 197 | .PP |
198 | The number of elements in the array | |
199 | .I a | |
200 | is given by | |
201 | .BI DA_LEN( a )\fR. | |
202 | An integer array index | |
203 | .I i | |
204 | is | |
205 | .I valid | |
206 | if 0 \(<= | |
207 | .I i | |
208 | < | |
209 | .BI DA_LEN( a )\fR. | |
210 | .PP | |
211 | There may be some spare slots at the end of the array. In particular, | |
212 | after a call to | |
213 | .BI DA_ENSURE( a ", " n ) | |
214 | there will be at least | |
215 | .I n | |
216 | spare slots. The number of spare slots at the end of the array may be | |
217 | obtained as | |
218 | .BI DA_SPARE( a )\fR. | |
219 | .PP | |
220 | Similarly, there may be spare slots before the start of the array. In | |
221 | particular, after a call to | |
222 | .BI DA_SHUNT( a ", " n ) | |
223 | there will be at least | |
224 | .I n | |
225 | spare slots. The number of spare slots before the start of the array | |
226 | may be obtained as | |
227 | .BI DA_OFFSET( a )\fR. | |
228 | .PP | |
229 | The call | |
230 | .BI DA_INCLUDE( a ", " i ) | |
231 | ensures that the array's bounds include the index | |
232 | .I i | |
233 | by extending the array if necessary. The exception | |
234 | .B EXC_NOMEM | |
235 | is thrown if there isn't enough memory to do this. | |
236 | .PP | |
237 | The array's bounds may be extended by | |
238 | .I n | |
239 | slots by calling | |
240 | .BI DA_EXTEND( a ", " n )\fR. | |
241 | The integer | |
242 | .I n | |
243 | must be less than | |
244 | .BI DA_SPARE( a )\fR; | |
245 | if this is not the case then the exception | |
246 | .B DAEXC_OFLOW | |
247 | is thrown. | |
248 | Note that | |
249 | .I n | |
250 | may be negative to reduce the bounds of the array: in this case it must | |
251 | be greater than | |
252 | .BI \-DA_LEN( a ) | |
253 | or the exception | |
254 | .B DAEXC_UFLOW | |
255 | is thrown. The macro | |
256 | .B DA_UNSAFE_EXTEND | |
257 | does the same job, but performs no error checking. | |
258 | .PP | |
259 | The macro | |
260 | .BI DA_SLIDE( a ", " n ) | |
261 | offsets the array elements by | |
262 | .IR n . | |
263 | If | |
264 | .I n | |
265 | is positive, the array elements are slid upwards, to higher-numbered | |
266 | indices; if | |
267 | .I n | |
268 | is negative, the elements are slid downwards. Precisely, what happens | |
269 | is that elements which used to have index | |
270 | .I i | |
271 | \- | |
272 | .I n | |
273 | now have index | |
274 | .IR i . | |
275 | The exception | |
276 | .B DAEXC_OFLOW | |
277 | is thrown if | |
278 | .I n | |
279 | > | |
280 | .BI DA_OFFSET( a )\fR; | |
281 | .B DAEXC_UFLOW | |
282 | is thrown if | |
283 | .I n | |
284 | < | |
285 | .BI \-DA_LEN( a )\fR. | |
286 | The macro | |
287 | .B DA_UNSAFE_SLIDE | |
288 | does the same job, only without the error checking. | |
85bb21f7 | 289 | .PP |
290 | The macros | |
291 | .B DA_SHRINK | |
292 | and | |
293 | .B DA_UNSLIDE | |
294 | do the same things as | |
295 | .B DA_EXTEND | |
296 | and | |
297 | .B DA_SLIDE | |
298 | respectively, except that they interpret the sign of their second | |
299 | arguments in the opposite way. This is useful if the argument is | |
300 | unsigned (e.g., if it's based on | |
cededfbe | 301 | .BR DA_LEN ). |
302 | There are unsafe versions of both these macros too. | |
d1836466 | 303 | .SS "Stack operations" |
304 | Dynamic arrays support Perl-like stack operations. Given an array | |
305 | (pointer) | |
306 | .I a | |
307 | and an object of the array's element type | |
308 | .I x | |
309 | the following operations are provided: | |
310 | .TP | |
311 | .BI DA_PUSH( a ", " x ) | |
312 | Add | |
313 | .I x | |
314 | to the end of the array, increasing the array size by one. | |
315 | .TP | |
316 | .IB x " = DA_POP(" a ) | |
317 | Remove the final element of the array, assigning | |
318 | .I x | |
319 | its value and decreasing the array size by one. | |
320 | .TP | |
321 | .BI DA_UNSHIFT( a ", " x ) | |
322 | Insert | |
323 | .I x | |
324 | at the beginning of the array, shifting all the elements up one place | |
325 | and increasing the array size by one. | |
326 | .TP | |
327 | .IB x " = DA_SHIFT(" a ) | |
328 | Remove the first element of the array, assigning | |
329 | .I x | |
330 | its value, shifting all the subsequent array items down one place and | |
331 | decreasing the array size by one. | |
332 | .PP | |
333 | The operations | |
334 | .B DA_PUSH | |
335 | and | |
336 | .B DA_UNSHIFT | |
337 | can fail due to lack of memory, in which case | |
338 | .B EXC_NOMEM | |
339 | is thrown. The operations | |
340 | .B DA_POP | |
341 | and | |
342 | .B DA_SHIFT | |
343 | can fail because the array is empty, in which case | |
344 | .B DAEXC_UFLOW | |
345 | is thrown. | |
706bf01d | 346 | .PP |
347 | The operations | |
348 | .B DA_FIRST | |
349 | and | |
350 | .B DA_LAST | |
351 | are lvalues referring to the first and last elements in the array | |
352 | respectively. They are unsafe if the array is empty. | |
d1836466 | 353 | .SS "Low-level details" |
354 | This section describes low-level details of the dynamic array | |
355 | implementation. You should try to avoid making use of this information | |
356 | if you can, since the interface may change in later library versions. | |
357 | In particular, more subtleties may be added which low-level access will | |
358 | miss. | |
359 | .PP | |
360 | Dynamic arrays are structures with the format | |
361 | .VS | |
bcb99985 | 362 | .BI "typedef struct " type_v " {" |
d1836466 | 363 | .B " da_base b;" |
364 | .BI " " type " *v;" | |
bcb99985 | 365 | .BI "} " type_v ";" |
d1836466 | 366 | .VE |
367 | The pointer | |
368 | .B v | |
369 | indicates the current base of the array. This will move in the | |
370 | allocated space as a result of | |
371 | .B DA_SHIFT | |
372 | and | |
373 | .B DA_UNSHIFT | |
374 | (and | |
375 | .BR DA_SLIDE ) | |
376 | operations. | |
377 | .PP | |
378 | The | |
379 | .B da_base | |
380 | structure contains the following elements: | |
381 | .TP | |
382 | .B "size_t sz" | |
383 | The number of allocated slots from | |
384 | .B v | |
385 | onwards. | |
386 | .TP | |
387 | .B "size_t len" | |
388 | The number of items considered to be in the array. The allocated space | |
389 | is usually larger than this. | |
390 | .TP | |
391 | .B "size_t off" | |
392 | The number of allocated slots preceding | |
393 | .BR v . | |
394 | The total number of allocated items is therefore | |
395 | .B sz | |
396 | + | |
397 | .BR off . | |
398 | .TP | |
399 | .B "unsigned push" | |
400 | The number of items pushed or ensured since the last array expansion. | |
401 | .TP | |
402 | .B "unsigned unshift" | |
403 | The number of items unshifted or shunted since the last array expansion. | |
404 | .PP | |
405 | The | |
406 | .B push | |
407 | and | |
408 | .B unshift | |
409 | members are used by the expansion routines to decide how to allocate | |
410 | free space before and after the array elements following a reallocation. | |
411 | The other members should be fairly self-explanatory. | |
412 | .PP | |
413 | The reallocation routines | |
414 | .BR da_ensure , | |
415 | .B da_shunt | |
416 | and | |
417 | .B da_tidy | |
418 | have a regular interface. They're a bit | |
419 | strange, though, because they have to deal with lots of different types | |
420 | of arrays. The arguments they take are: | |
421 | .TP | |
422 | .BI "da_base *" b | |
423 | Pointer to the | |
424 | .B da_base | |
425 | member of the array block. | |
426 | .TP | |
427 | .BI "void *" v | |
428 | The array base pointer from the array block (i.e., the | |
429 | .B v | |
430 | member). | |
431 | .TP | |
432 | .BI "size_t " sz | |
433 | The element size for the array. | |
434 | .TP | |
435 | .BI "size_t " n | |
436 | (For | |
437 | .B da_ensure | |
438 | and | |
439 | .B da_shunt | |
440 | only.) The number of spare slots required. | |
441 | .PP | |
442 | The functions may modify the base structure, and return a newly | |
443 | allocated (or at least repositioned) array base pointer, or throw | |
444 | .B EXC_NOMEM | |
445 | if there's not enough memory. | |
446 | .PP | |
447 | The three functions behave as follows: | |
448 | .TP | |
449 | .B da_ensure | |
450 | Ensure that there are at least | |
451 | .I n | |
452 | spare slots after the end of the array. | |
453 | .TP | |
454 | .B da_shunt | |
455 | Ensure that there are at least | |
456 | .I n | |
457 | spare slots preceding the start of the array. | |
458 | .TP | |
459 | .B da_tidy | |
460 | Reallocate the array to use the smallest amount of memory possible. | |
461 | .SH "SEE ALSO" | |
462 | .BR exc (3), | |
463 | .BR mLib (3). | |
464 | .SH "AUTHOR" | |
9b5ac6ff | 465 | Mark Wooding, <mdw@distorted.org.uk> |