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 |
22 | .TH darray 3 "21 October 1999" mLib |
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 |
d1836466 |
46 | .\" @DA_PUSH |
47 | .\" @DA_POP |
48 | .\" @DA_UNSHIFT |
49 | .\" @DA_SHIFT |
50 | .\" @DAEXC_UFLOW |
51 | .\" @DAEXC_OFLOW |
52 | .\" @da_ensure |
53 | .\" @da_shunt |
54 | .\" @da_tidy |
55 | .SH "SYNOPSIS" |
56 | .nf |
57 | .B "#include <mLib/darray.h>" |
58 | |
bcb99985 |
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 ); |
d1836466 |
63 | |
bcb99985 |
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 ); |
d1836466 |
68 | |
bcb99985 |
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 ); |
85bb21f7 |
74 | |
bcb99985 |
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 ); |
85bb21f7 |
79 | |
bcb99985 |
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 ); |
d1836466 |
84 | |
bcb99985 |
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 ); |
d1836466 |
89 | |
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 ); |
93 | .fi |
94 | .SH "DESCRIPTION" |
95 | The |
96 | .B <mLib/darray.h> |
97 | declares a collection of types, macros and functions which implement |
98 | dynamically resizing arrays. |
99 | .PP |
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 |
105 | .B DA_DECL |
106 | macro. Calling |
107 | .VS |
bcb99985 |
108 | .BI DA_DECL( type_v ", " type ); |
d1836466 |
109 | .VE |
110 | Declares a new dynamic array type |
bcb99985 |
111 | .I type_v |
d1836466 |
112 | whose elements have type |
113 | .IR type . |
114 | .PP |
bcb99985 |
115 | It is conventional to form the name of an array type by appending |
116 | .RB ` _v ' |
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., |
121 | .VS |
122 | #ifndef FOO_V |
123 | # define FOO_V |
cededfbe |
124 | DA_DECL(foo_v, foo); |
bcb99985 |
125 | #endif |
126 | .VE |
d1836466 |
127 | The macro |
128 | .B DA_INIT |
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 |
131 | using the macro |
8f7d402a |
132 | .BR DA_CREATE , |
d1836466 |
133 | passing it the address of the array. |
134 | .PP |
135 | Arrays may be disposed of using the |
136 | .B DA_DESTROY |
137 | macro, which again takes the address of the array. |
138 | .SS "Storage allocation" |
139 | .PP |
140 | Space for new array elements may be reserved using the |
141 | .B DA_ENSURE |
142 | and |
143 | .B DA_SHUNT |
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. |
147 | .PP |
148 | Neither of these macros actually extends the array; both merely allocate |
149 | memory for the array to extend itself into. Use the macros |
150 | .B DA_EXTEND |
151 | and |
152 | .B DA_SLIDE |
153 | to actually increase the bounds of the array. |
154 | .PP |
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 |
158 | .B EXC_NOMEM |
159 | is thrown (see |
160 | .BR exc (3)). |
161 | .PP |
162 | The macro |
163 | .B DA_TIDY |
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. |
85bb21f7 |
167 | .PP |
168 | The macro |
169 | .B DA_RESET |
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. |
d1836466 |
173 | .SS "Accessing array elements" |
174 | If |
175 | .I a |
176 | is the address of a dynamic array object, then |
177 | .BI DA( a ) |
178 | is the base address of the actual array. The elements are stored |
179 | contiguously starting at this address. An element at index |
180 | .I i |
181 | may be referenced using the syntax |
8f7d402a |
182 | .BI DA( a )[ i ]\fR. |
d1836466 |
183 | .PP |
184 | The number of elements in the array |
185 | .I a |
186 | is given by |
187 | .BI DA_LEN( a )\fR. |
188 | An integer array index |
189 | .I i |
190 | is |
191 | .I valid |
192 | if 0 \(<= |
193 | .I i |
194 | < |
195 | .BI DA_LEN( a )\fR. |
196 | .PP |
197 | There may be some spare slots at the end of the array. In particular, |
198 | after a call to |
199 | .BI DA_ENSURE( a ", " n ) |
200 | there will be at least |
201 | .I n |
202 | spare slots. The number of spare slots at the end of the array may be |
203 | obtained as |
204 | .BI DA_SPARE( a )\fR. |
205 | .PP |
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 |
210 | .I n |
211 | spare slots. The number of spare slots before the start of the array |
212 | may be obtained as |
213 | .BI DA_OFFSET( a )\fR. |
214 | .PP |
215 | The call |
216 | .BI DA_INCLUDE( a ", " i ) |
217 | ensures that the array's bounds include the index |
218 | .I i |
219 | by extending the array if necessary. The exception |
220 | .B EXC_NOMEM |
221 | is thrown if there isn't enough memory to do this. |
222 | .PP |
223 | The array's bounds may be extended by |
224 | .I n |
225 | slots by calling |
226 | .BI DA_EXTEND( a ", " n )\fR. |
227 | The integer |
228 | .I n |
229 | must be less than |
230 | .BI DA_SPARE( a )\fR; |
231 | if this is not the case then the exception |
232 | .B DAEXC_OFLOW |
233 | is thrown. |
234 | Note that |
235 | .I n |
236 | may be negative to reduce the bounds of the array: in this case it must |
237 | be greater than |
238 | .BI \-DA_LEN( a ) |
239 | or the exception |
240 | .B DAEXC_UFLOW |
241 | is thrown. The macro |
242 | .B DA_UNSAFE_EXTEND |
243 | does the same job, but performs no error checking. |
244 | .PP |
245 | The macro |
246 | .BI DA_SLIDE( a ", " n ) |
247 | offsets the array elements by |
248 | .IR n . |
249 | If |
250 | .I n |
251 | is positive, the array elements are slid upwards, to higher-numbered |
252 | indices; if |
253 | .I n |
254 | is negative, the elements are slid downwards. Precisely, what happens |
255 | is that elements which used to have index |
256 | .I i |
257 | \- |
258 | .I n |
259 | now have index |
260 | .IR i . |
261 | The exception |
262 | .B DAEXC_OFLOW |
263 | is thrown if |
264 | .I n |
265 | > |
266 | .BI DA_OFFSET( a )\fR; |
267 | .B DAEXC_UFLOW |
268 | is thrown if |
269 | .I n |
270 | < |
271 | .BI \-DA_LEN( a )\fR. |
272 | The macro |
273 | .B DA_UNSAFE_SLIDE |
274 | does the same job, only without the error checking. |
85bb21f7 |
275 | .PP |
276 | The macros |
277 | .B DA_SHRINK |
278 | and |
279 | .B DA_UNSLIDE |
280 | do the same things as |
281 | .B DA_EXTEND |
282 | and |
283 | .B DA_SLIDE |
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 |
cededfbe |
287 | .BR DA_LEN ). |
288 | There are unsafe versions of both these macros too. |
d1836466 |
289 | .SS "Stack operations" |
290 | Dynamic arrays support Perl-like stack operations. Given an array |
291 | (pointer) |
292 | .I a |
293 | and an object of the array's element type |
294 | .I x |
295 | the following operations are provided: |
296 | .TP |
297 | .BI DA_PUSH( a ", " x ) |
298 | Add |
299 | .I x |
300 | to the end of the array, increasing the array size by one. |
301 | .TP |
302 | .IB x " = DA_POP(" a ) |
303 | Remove the final element of the array, assigning |
304 | .I x |
305 | its value and decreasing the array size by one. |
306 | .TP |
307 | .BI DA_UNSHIFT( a ", " x ) |
308 | Insert |
309 | .I x |
310 | at the beginning of the array, shifting all the elements up one place |
311 | and increasing the array size by one. |
312 | .TP |
313 | .IB x " = DA_SHIFT(" a ) |
314 | Remove the first element of the array, assigning |
315 | .I x |
316 | its value, shifting all the subsequent array items down one place and |
317 | decreasing the array size by one. |
318 | .PP |
319 | The operations |
320 | .B DA_PUSH |
321 | and |
322 | .B DA_UNSHIFT |
323 | can fail due to lack of memory, in which case |
324 | .B EXC_NOMEM |
325 | is thrown. The operations |
326 | .B DA_POP |
327 | and |
328 | .B DA_SHIFT |
329 | can fail because the array is empty, in which case |
330 | .B DAEXC_UFLOW |
331 | is thrown. |
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 |
337 | miss. |
338 | .PP |
339 | Dynamic arrays are structures with the format |
340 | .VS |
bcb99985 |
341 | .BI "typedef struct " type_v " {" |
d1836466 |
342 | .B " da_base b;" |
343 | .BI " " type " *v;" |
bcb99985 |
344 | .BI "} " type_v ";" |
d1836466 |
345 | .VE |
346 | The pointer |
347 | .B v |
348 | indicates the current base of the array. This will move in the |
349 | allocated space as a result of |
350 | .B DA_SHIFT |
351 | and |
352 | .B DA_UNSHIFT |
353 | (and |
354 | .BR DA_SLIDE ) |
355 | operations. |
356 | .PP |
357 | The |
358 | .B da_base |
359 | structure contains the following elements: |
360 | .TP |
361 | .B "size_t sz" |
362 | The number of allocated slots from |
363 | .B v |
364 | onwards. |
365 | .TP |
366 | .B "size_t len" |
367 | The number of items considered to be in the array. The allocated space |
368 | is usually larger than this. |
369 | .TP |
370 | .B "size_t off" |
371 | The number of allocated slots preceding |
372 | .BR v . |
373 | The total number of allocated items is therefore |
374 | .B sz |
375 | + |
376 | .BR off . |
377 | .TP |
378 | .B "unsigned push" |
379 | The number of items pushed or ensured since the last array expansion. |
380 | .TP |
381 | .B "unsigned unshift" |
382 | The number of items unshifted or shunted since the last array expansion. |
383 | .PP |
384 | The |
385 | .B push |
386 | and |
387 | .B unshift |
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. |
391 | .PP |
392 | The reallocation routines |
393 | .BR da_ensure , |
394 | .B da_shunt |
395 | and |
396 | .B da_tidy |
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: |
400 | .TP |
401 | .BI "da_base *" b |
402 | Pointer to the |
403 | .B da_base |
404 | member of the array block. |
405 | .TP |
406 | .BI "void *" v |
407 | The array base pointer from the array block (i.e., the |
408 | .B v |
409 | member). |
410 | .TP |
411 | .BI "size_t " sz |
412 | The element size for the array. |
413 | .TP |
414 | .BI "size_t " n |
415 | (For |
416 | .B da_ensure |
417 | and |
418 | .B da_shunt |
419 | only.) The number of spare slots required. |
420 | .PP |
421 | The functions may modify the base structure, and return a newly |
422 | allocated (or at least repositioned) array base pointer, or throw |
423 | .B EXC_NOMEM |
424 | if there's not enough memory. |
425 | .PP |
426 | The three functions behave as follows: |
427 | .TP |
428 | .B da_ensure |
429 | Ensure that there are at least |
430 | .I n |
431 | spare slots after the end of the array. |
432 | .TP |
433 | .B da_shunt |
434 | Ensure that there are at least |
435 | .I n |
436 | spare slots preceding the start of the array. |
437 | .TP |
438 | .B da_tidy |
439 | Reallocate the array to use the smallest amount of memory possible. |
440 | .SH "SEE ALSO" |
441 | .BR exc (3), |
442 | .BR mLib (3). |
443 | .SH "AUTHOR" |
444 | Mark Wooding, <mdw@nsict.org> |