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