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