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 | |
bcb99985 |
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 ); |
d1836466 |
65 | |
bcb99985 |
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 ); |
d1836466 |
70 | |
bcb99985 |
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 ); |
85bb21f7 |
76 | |
bcb99985 |
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 ); |
85bb21f7 |
81 | |
bcb99985 |
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 ); |
d1836466 |
86 | |
706bf01d |
87 | .IB type " DA_FIRST(" type_v " *" a ); |
88 | .IB type " DA_LAST(" type_v " *" a ); |
bcb99985 |
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 ); |
d1836466 |
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> |
d0053e2e |
101 | header file declares a collection of types, macros and functions which |
102 | implement dynamically resizing arrays. |
d1836466 |
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 |
bcb99985 |
112 | .BI DA_DECL( type_v ", " type ); |
d1836466 |
113 | .VE |
114 | Declares a new dynamic array type |
bcb99985 |
115 | .I type_v |
d1836466 |
116 | whose elements have type |
117 | .IR type . |
118 | .PP |
bcb99985 |
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 |
cededfbe |
128 | DA_DECL(foo_v, foo); |
bcb99985 |
129 | #endif |
130 | .VE |
d1836466 |
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 |
8f7d402a |
136 | .BR DA_CREATE , |
d1836466 |
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. |
85bb21f7 |
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. |
d1836466 |
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 |
8f7d402a |
186 | .BI DA( a )[ i ]\fR. |
d1836466 |
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. |
85bb21f7 |
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 |
cededfbe |
291 | .BR DA_LEN ). |
292 | There are unsafe versions of both these macros too. |
d1836466 |
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. |
706bf01d |
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. |
d1836466 |
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 |
bcb99985 |
352 | .BI "typedef struct " type_v " {" |
d1836466 |
353 | .B " da_base b;" |
354 | .BI " " type " *v;" |
bcb99985 |
355 | .BI "} " type_v ";" |
d1836466 |
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@nsict.org> |