3745e24b |
1 | /* -*-c-*- |
2 | * |
706bf01d |
3 | * $Id: darray.h,v 1.6 2001/03/03 12:20:23 mdw Exp $ |
3745e24b |
4 | * |
5 | * Dynamically growing dense arrays |
6 | * |
7 | * (c) 1999 Straylight/Edgeware |
8 | */ |
9 | |
10 | /*----- Licensing notice --------------------------------------------------* |
11 | * |
12 | * This file is part of the mLib utilities library. |
13 | * |
14 | * mLib is free software; you can redistribute it and/or modify |
15 | * it under the terms of the GNU Library General Public License as |
16 | * published by the Free Software Foundation; either version 2 of the |
17 | * License, or (at your option) any later version. |
18 | * |
19 | * mLib is distributed in the hope that it will be useful, |
20 | * but WITHOUT ANY WARRANTY; without even the implied warranty of |
21 | * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the |
22 | * GNU Library General Public License for more details. |
23 | * |
24 | * You should have received a copy of the GNU Library General Public |
25 | * License along with mLib; if not, write to the Free |
26 | * Software Foundation, Inc., 59 Temple Place - Suite 330, Boston, |
27 | * MA 02111-1307, USA. |
28 | */ |
29 | |
30 | /*----- Revision history --------------------------------------------------* |
31 | * |
32 | * $Log: darray.h,v $ |
706bf01d |
33 | * Revision 1.6 2001/03/03 12:20:23 mdw |
34 | * New macros @DA_FIRST@ and @DA_LAST@ for stack/queue peeking. |
35 | * |
20eb516f |
36 | * Revision 1.5 2000/06/17 10:37:39 mdw |
37 | * Add support for arena management. |
38 | * |
c6e0eaf0 |
39 | * Revision 1.4 1999/12/10 23:42:04 mdw |
40 | * Change header file guard names. |
41 | * |
d4e0e50d |
42 | * Revision 1.3 1999/11/05 14:32:43 mdw |
43 | * Minor change in argument naming. |
44 | * |
85bb21f7 |
45 | * Revision 1.2 1999/10/29 22:59:22 mdw |
46 | * New array adjustment macros for unsigned arguments. |
47 | * |
3745e24b |
48 | * Revision 1.1 1999/10/22 22:37:26 mdw |
49 | * New dynamic array implementation replaces `dynarray.h'. |
50 | * |
51 | */ |
52 | |
c6e0eaf0 |
53 | #ifndef MLIB_DARRAY_H |
54 | #define MLIB_DARRAY_H |
3745e24b |
55 | |
56 | #ifdef __cplusplus |
57 | extern "C" { |
58 | #endif |
59 | |
60 | /*----- Header files ------------------------------------------------------*/ |
61 | |
62 | #include <stdio.h> |
63 | #include <stdlib.h> |
64 | #include <string.h> |
65 | |
c6e0eaf0 |
66 | #ifndef MLIB_ALLOC_H |
3745e24b |
67 | # include "alloc.h" |
68 | #endif |
69 | |
c6e0eaf0 |
70 | #ifndef MLIB_EXC_H |
3745e24b |
71 | # include "exc.h" |
72 | #endif |
73 | |
74 | /*----- Various important constants ---------------------------------------*/ |
75 | |
76 | /* --- @DAEXC_UFLOW@, @DAEXC_OFLOW@ --- * |
77 | * |
78 | * Underflow and overflow exceptions raised by @DA_SHIFT@, and by @DA_POP@ |
79 | * and @DA_SHIFT@. |
80 | */ |
81 | |
82 | #define DAEXC_UFLOW EXC_ALLOCN(EXC_MLIB, 0) |
83 | #define DAEXC_OFLOW EXC_ALLOCN(EXC_MLIB, 1) |
84 | |
85 | /*----- Data structures ---------------------------------------------------*/ |
86 | |
87 | /* --- Base structure for dynamic arrays --- * |
88 | * |
89 | * An actual array has a `vector' @v@ in addition to this data (which is |
90 | * tucked away in the @b@ member). The vector contains the actual storage |
91 | * for the array elements. |
92 | * |
93 | * The vector pointer @v@ potentially points somewhere in the middle of the |
94 | * allocated storage. The @off@ member explains how far into the storage the |
95 | * vector points. The allocated storage is sufficient for @sz + off@ items |
96 | * to be stored. Valid array indices are integers between 0 (inclusive) and |
97 | * @len@ (exclusive). Thus, from @v@ onwards, there is space for @sz@ |
98 | * elements, and of these, @sz - len@ are currently not considered to be |
99 | * within the array's bounds. |
100 | * |
101 | * The @push@ and @unshift@ counts record how many times these operations |
102 | * have been performed since the last extension of the array. They are used |
103 | * by the extension algorithm to decide how to position the data offset. |
104 | * |
105 | * Try to use the access macros rather than the structure members. |
106 | */ |
107 | |
108 | typedef struct da_base { |
109 | size_t sz; /* Size of allocated vector */ |
110 | size_t len; /* Length of useful portion */ |
111 | size_t off; /* Offset of @v@ into space */ |
112 | unsigned push, unshift; /* Pushes/unshifts since growth */ |
20eb516f |
113 | arena *a; /* Pointer to allocation arena */ |
3745e24b |
114 | } da_base; |
115 | |
116 | /* --- @DA_DECL@ --- * |
117 | * |
118 | * Arguments: @atype@ = type name for the array |
119 | * @type@ = item type for the array |
120 | * |
121 | * Use: Declares a structure for decribing a dynamic array. |
122 | */ |
123 | |
d4e0e50d |
124 | #define DA_DECL(type_v, type) \ |
125 | typedef struct type_v { da_base b; type *v; } type_v |
3745e24b |
126 | |
127 | /*----- Initialization, creation and destruction --------------------------*/ |
128 | |
20eb516f |
129 | #define DA_INIT { { 0, 0, 0, 0, 0, &arena_stdlib }, 0 } |
3745e24b |
130 | |
131 | /* --- @DA_CREATE@ --- * |
132 | * |
133 | * Arguments: @a@ = pointer to an array block (multiply evaluated) |
134 | * |
135 | * Use: Initializes an array block. |
136 | */ |
137 | |
20eb516f |
138 | #define DA_CREATE(aa) do { \ |
139 | (aa)->b.sz = (aa)->b.len = 0; \ |
140 | (aa)->b.off = 0; \ |
141 | (aa)->b.push = (aa)->b.unshift = 0; \ |
142 | (aa)->b.a = &arena_stdlib; \ |
143 | (aa)->v = 0; \ |
3745e24b |
144 | } while (0) |
145 | |
146 | /* --- @DA_DESTROY@ --- * |
147 | * |
148 | * Arguments: @a@ = pointer to an array block (multiply evaluated) |
149 | * |
150 | * Use: Destroys an array. The array is left valid but empty. |
151 | */ |
152 | |
20eb516f |
153 | #define DA_DESTROY(aa) do { \ |
154 | if ((aa)->v) \ |
155 | x_free((aa)->b.a, (aa)->v - (aa)->b.off); \ |
156 | DA_CREATE(aa); \ |
3745e24b |
157 | } while (0) |
158 | |
159 | /*----- Storage reservation -----------------------------------------------*/ |
160 | |
161 | /* --- @DA_ENSURE@ --- * |
162 | * |
163 | * Arguments: @a@ = pointer to an array block (multiply evaluated) |
164 | * @n@ = required number of spare items in the array |
165 | * |
166 | * Use: Ensures that there are at least @n@ spare slots at the end of |
167 | * the array. |
168 | */ |
169 | |
170 | #define DA_ENSURE(a, n) do { \ |
171 | size_t _n = (n); \ |
172 | if (_n > (a)->b.sz - (a)->b.len) \ |
173 | (a)->v = da_ensure(&(a)->b, (a)->v, sizeof((a)->v[0]), _n); \ |
174 | else \ |
175 | (a)->b.push += _n; \ |
176 | } while (0) |
177 | |
178 | /* --- @DA_SHUNT@ --- * |
179 | * |
180 | * Arguments: @a@ = pointer to an array block (multiply evaluated) |
181 | * @n@ = required number of spare items in the array |
182 | * |
183 | * Use: Ensures that there are at least @n@ spare slots at the start |
184 | * of the array. |
185 | */ |
186 | |
187 | #define DA_SHUNT(a, n) do { \ |
188 | size_t _n = (n); \ |
189 | if (_n > (a)->b.off) \ |
190 | (a)->v = da_shunt(&(a)->b, (a)->v, sizeof((a)->v[0]), _n); \ |
191 | else \ |
192 | (a)->b.unshift += _n; \ |
193 | } while (0) |
194 | |
195 | /* --- @DA_TIDY@ --- * |
196 | * |
197 | * Arguments: @a@ = pointer to an array block (multiply evaluated) |
198 | * |
199 | * Use: Reduces the amount of storage required by an array to its |
200 | * minimum possible. |
201 | */ |
202 | |
203 | #define DA_TIDY(a) ((a)->v = da_tidy(&(a)->b, (a)->v, sizeof((a)->v[0]))) |
204 | |
85bb21f7 |
205 | /* --- @DA_RESET@ --- * |
206 | * |
207 | * Arguments: @a@ = pointer to array block |
208 | * |
209 | * Use: Removes all the items from the named array. This might not |
210 | * be a good idea. No storage is freed. |
211 | */ |
212 | |
213 | #define DA_RESET(a) ((a)->b.len = 0) |
214 | |
3745e24b |
215 | /*----- Access operations -------------------------------------------------*/ |
216 | |
217 | /* --- @DA@ --- * |
218 | * |
219 | * Arguments: @a@ = pointer to array block |
220 | * |
221 | * Use: Expands to a reference to the array proper. Given an array |
222 | * @a@, item @i@ may be located using the expression @DA(a)[i]@. |
223 | */ |
224 | |
225 | #define DA(a) ((a)->v + 0) |
226 | |
227 | /* --- @DA_LEN@ --- * |
228 | * |
229 | * Arguments: @a@ = pointer to array block |
230 | * |
231 | * Use: Expands to the number of elements in the array. Elements are |
232 | * assigned integer indices in the half-open interval |
233 | * [0, @DA_LEN(a)@). Don't change the length directly; use |
234 | * @DA_EXTEND@ instead. |
235 | */ |
236 | |
237 | #define DA_LEN(a) ((a)->b.len + 0) |
238 | |
239 | /* --- @DA_SPARE@ --- * |
240 | * |
241 | * Arguments: @a@ = pointer to array block (multiply evaluated) |
242 | * |
243 | * Use: Evaluates to the number of spare array elements above the |
244 | * end of the array. |
245 | */ |
246 | |
247 | #define DA_SPARE(a) ((a)->b.sz - (a)->b.len) |
248 | |
249 | /* --- @DA_INCLUDE@ --- * |
250 | * |
251 | * Arguments: @a@ = pointer to array block (multiply evaluated) |
252 | * @i@ = index into array |
253 | * |
254 | * Use: Extends the array (if necessary) so that it includes the |
255 | * index @i@. |
256 | */ |
257 | |
258 | #define DA_INCLUDE(a, i) do { \ |
259 | size_t _i = (i); \ |
260 | size_t _len = DA_LEN(a); \ |
261 | if (_i >= _len) { \ |
262 | size_t _nn = _i - _len + 1; \ |
263 | DA_ENSURE(a, _nn); \ |
264 | DA_UNSAFE_EXTEND(a, _nn); \ |
265 | } \ |
266 | } while (0) |
267 | |
268 | /* --- @DA_OFFSET@ --- * |
269 | * |
270 | * Arguments: @a@ = pointer to array block |
271 | * |
272 | * Use: Evaluates to the number of spare elements before the |
273 | * beginning of the array. Don't modify the offset directly; |
274 | * use @DA_SLIDE@ instead. |
275 | */ |
276 | |
277 | #define DA_OFFSET(a) ((a)->b.off + 0) |
278 | |
279 | /* --- @DA_EXTEND@ --- * |
280 | * |
281 | * Arguments: @a@ = pointer to array block (multiply evaluated) |
282 | * @n@ = number of slots to add (multiply evaluated) |
283 | * |
284 | * Use: Extends the end of the array by @n@ elements. The exception |
285 | * @DAEXC_OFLOW@ is thrown if there is not enough space for the |
286 | * new elements (i.e., @n > DA_SPARE(a)@) -- call @DA_ENSURE@ to |
287 | * prevent this from happening. The integer @n@ may be |
288 | * negative; @DAEXC_UFLOW@ is called if @n < DA_LEN(a)@. |
289 | */ |
290 | |
291 | #define DA_EXTEND(a, n) do { \ |
292 | if ((n) > 0 && (n) > DA_SPARE(a)) \ |
293 | THROW(DAEXC_OFLOW); \ |
294 | else if ((n) < 0 && -(n) > DA_LEN(a)) \ |
295 | THROW(DAEXC_UFLOW); \ |
296 | DA_UNSAFE_EXTEND(a, n); \ |
297 | } while (0) |
298 | |
85bb21f7 |
299 | /* --- @DA_UNSAFE_EXTEND@ --- * |
3745e24b |
300 | * |
301 | * Arguments: @a@ = pointer to array block (multiply evaluated) |
302 | * @n@ = number of slots to add (multiply evaluated) |
303 | * |
304 | * Use: As for @DA_EXTEND@, only it doesn't check for errors. |
305 | */ |
306 | |
307 | #define DA_UNSAFE_EXTEND(a, n) do { \ |
308 | (a)->b.len += (n); \ |
309 | } while (0) |
310 | |
311 | /* --- @DA_SLIDE@ --- * |
312 | * |
313 | * Arguments: @a@ = pointer to array block (multiply evaluated) |
314 | * @n@ = number of positions to slide the array (multiply |
315 | * evaluated) |
316 | * |
317 | * |
318 | * Use: Slides the array elements by @n@ positions. A positive @n@ |
319 | * slides upwards, introducing new elements at the bottom; a |
320 | * negative @n@ slides downwards, removing low-numbered |
321 | * elements. Formally, what was at index @i - n@ before the |
322 | * slide is moved to index @i@. It is an error to slide by more |
323 | * than @DA_OFFSET(a)@ or less than @-DA_LEN(a)@. The exception |
324 | * @DAEXC_OFLOW@ is raised in the former case, and @DAEXC_UFLOW@ |
325 | * in the latter. |
326 | */ |
327 | |
328 | #define DA_SLIDE(a, n) do { \ |
329 | if ((n) > 0 && (n) > DA_OFFSET(a)) \ |
330 | THROW(DAEXC_OFLOW); \ |
331 | else if ((n) < 0 && -(n) > DA_LEN(a)) \ |
332 | THROW(DAEXC_UFLOW); \ |
333 | DA_UNSAFE_SLIDE((a), (n)); \ |
334 | } while (0) |
335 | |
336 | /* --- @DA_UNSAFE_SLIDE@ --- * |
337 | * |
338 | * Arguments: @a@ = pointer to array block (multiply evaluated) |
339 | * @n@ = number of positions to slide the array (multiply |
340 | * evaluated) |
341 | * |
342 | * Use: As for @DA_SLIDE@, only it doesn't check for errors. |
343 | */ |
344 | |
345 | #define DA_UNSAFE_SLIDE(a, n) do { \ |
346 | (a)->v -= (n); \ |
347 | (a)->b.len += (n); \ |
348 | (a)->b.sz += (n); \ |
349 | (a)->b.off -= (n); \ |
350 | } while (0) |
351 | |
85bb21f7 |
352 | /* --- @DA_SHRINK@ --- * |
353 | * |
354 | * Arguments: @a@ = pointer to array block (multiply evaluated) |
355 | * @n@ = number of slots to remove (multiply evaluated) |
356 | * |
357 | * Use: As for @DA_EXTEND@, with the sense of the argument reversed. |
358 | */ |
359 | |
360 | #define DA_SHRINK(a, n) do { \ |
361 | if ((n) > 0 && (n) > DA_LEN(a)) \ |
362 | THROW(DAEXC_UFLOW); \ |
363 | else if ((n) < 0 && -(n) > DA_SPARE(a)) \ |
364 | THROW(DAEXC_OFLOW); \ |
365 | DA_UNSAFE_SHRINK(a, n); \ |
366 | } while (0) |
367 | |
368 | /* --- @DA_UNSAFE_SHRINK@ --- * |
369 | * |
370 | * Arguments: @a@ = pointer to array block (multiply evaluated) |
371 | * @n@ = number of slots to add (multiply evaluated) |
372 | * |
373 | * Use: As for @DA_SHRINK@, only it doesn't check for errors. |
374 | */ |
375 | |
376 | #define DA_UNSAFE_SHRINK(a, n) do { \ |
377 | (a)->b.len -= (n); \ |
378 | } while (0) |
379 | |
380 | /* --- @DA_UNSLIDE@ --- * |
381 | * |
382 | * Arguments: @a@ = pointer to array block (multiply evaluated) |
383 | * @n@ = number of positions to slide the array (multiply |
384 | * evaluated) |
385 | * |
386 | * |
387 | * Use: As for @DA_SLIDE@, only in the other direction. |
388 | */ |
389 | |
390 | #define DA_UNSLIDE(a, n) do { \ |
391 | if ((n) > 0 && (n) > DA_LEN(a)) \ |
392 | THROW(DAEXC_UFLOW); \ |
393 | else if ((n) < 0 && -(n) > DA_OFFSET(a)) \ |
394 | THROW(DAEXC_OFLOW); \ |
395 | DA_UNSAFE_UNSLIDE((a), (n)); \ |
396 | } while (0) |
397 | |
398 | /* --- @DA_UNSAFE_UNSLIDE@ --- * |
399 | * |
400 | * Arguments: @a@ = pointer to array block (multiply evaluated) |
401 | * @n@ = number of positions to slide the array (multiply |
402 | * evaluated) |
403 | * |
404 | * Use: As for @DA_UNSLIDE@, only it doesn't check for errors. |
405 | */ |
406 | |
407 | #define DA_UNSAFE_UNSLIDE(a, n) do { \ |
408 | (a)->v += (n); \ |
409 | (a)->b.len -= (n); \ |
410 | (a)->b.sz -= (n); \ |
411 | (a)->b.off += (n); \ |
412 | } while (0) |
413 | |
3745e24b |
414 | /*----- Stack-like operations ---------------------------------------------*/ |
415 | |
706bf01d |
416 | /* --- @DA_FIRST@ --- * |
417 | * |
418 | * Arguments: @a@ = pointer to an array block (multiply evaluated) |
419 | * |
420 | * Use: Evaluates to the initial element in array @a@. It is unsafe |
421 | * to do this if the array is empty. The array is not changed. |
422 | */ |
423 | |
424 | #define DA_FIRST(a) (DA(a)[0]) |
425 | |
426 | /* --- @DA_LAST@ --- * |
427 | * |
428 | * Arguments: @a@ = pointer to an array block (multiply evaluated) |
429 | * |
430 | * Use: Evaluates to the final element in array @a@. It is unsafe |
431 | * to do this if the array is empty. The array is not changed. |
432 | */ |
433 | |
434 | #define DA_LAST(a) (DA(a)[(a)->b.len - 1]) |
435 | |
3745e24b |
436 | /* --- @DA_PUSH@ --- * |
437 | * |
438 | * Arguments: @a@ = pointer to an array block (multiply evaluated) |
439 | * @x@ = item to append to the end |
440 | * |
441 | * Use: Appends @x@ as the final element in the array @a@. |
442 | */ |
443 | |
444 | #define DA_PUSH(a, x) do { \ |
445 | DA_ENSURE(a, 1); \ |
446 | DA(a)[(a)->b.len++] = x; \ |
447 | } while (0) |
448 | |
449 | /* --- @DA_POP@ --- * |
450 | * |
451 | * Arguments: @a@ = pointer to an array block (multiply evaluated) |
452 | * |
453 | * Use: Evaluates to the final element in array @a@. The element is |
454 | * removed. An exception @DAEXC_UFLOW@ is raised if there is |
455 | * no item available to pop. |
456 | */ |
457 | |
458 | #define DA_POP(a) \ |
459 | ((a)->b.len ? ((void)0) : THROW(DAEXC_UFLOW), \ |
460 | DA(a)[--(a)->b.len]) |
461 | |
462 | /* --- @DA_UNSHIFT@ --- * |
463 | * |
464 | * Arguments: @a@ = pointer to an array block (multiply evaluated) |
465 | * @x@ = the new element to insert |
466 | * |
467 | * Use: Inserts a new element at the beginning of an array. This |
468 | * might take a while. |
469 | */ |
470 | |
471 | #define DA_UNSHIFT(a, x) do { \ |
472 | DA_SHUNT(a, 1); \ |
473 | DA_UNSAFE_SLIDE(a, 1); \ |
474 | DA(a)[0] = x; \ |
475 | } while (0) |
476 | |
477 | /* --- @DA_SHIFT@ --- * |
478 | * |
479 | * Arguments: @a@ = pointer to an array block (multiply evaluated) |
480 | * |
481 | * Use: Evaluates to the initial element in array @a@. The element |
482 | * is removed, and all other elements are shifted down one |
483 | * place. The exception @DAEXC_UFLOW@ is raised if there is no |
484 | * element to return. |
485 | */ |
486 | |
487 | #define DA_SHIFT(a) \ |
706bf01d |
488 | ((a)->b.len ? ((void)0) : THROW(DAEXC_UFLOW), \ |
3745e24b |
489 | (a)->b.len--, \ |
490 | (a)->b.sz--, \ |
491 | (a)->b.off++, \ |
492 | *(a)->v++) |
493 | |
494 | /*----- Functions provided ------------------------------------------------*/ |
495 | |
496 | /* --- @da_ensure@ --- * |
497 | * |
498 | * Arguments: @da_base *b@ = pointer to array base structure |
499 | * @void *v@ = pointer to array vector |
500 | * @size_t sz@ = size of individual array elements |
501 | * @size_t n@ = number of items required at the end |
502 | * |
503 | * Returns: Pointer to newly allocated or adjusted array vector. |
504 | * |
505 | * Use: Extends a dynamic array to accommodate a number of new items |
506 | * at its end. This function is a helper for the @DA_ENSURE@ |
507 | * macro, which should be used by preference. |
508 | */ |
509 | |
510 | extern void *da_ensure(da_base */*b*/, void */*v*/, |
511 | size_t /*sz*/, size_t /*n*/); |
512 | |
513 | /* --- @da_shunt@ --- * |
514 | * |
515 | * Arguments: @da_base *b@ = pointer to array base structure |
516 | * @void *v@ = pointer to array vector |
517 | * @size_t sz@ = size of the array elements |
518 | * @size_t n@ = number of items required at the start |
519 | * |
520 | * Returns: Pointer to appropriately bodged vector. |
521 | * |
522 | * Use: Extends an array to accommodate items inserted at its front. |
523 | * This function is a helper for the @DA_SHUNT@ macro, which |
524 | * should be used by preference. |
525 | */ |
526 | |
527 | extern void *da_shunt(da_base */*b*/, void */*v*/, |
528 | size_t /*sz*/, size_t /*n*/); |
529 | |
530 | /* --- @da_tidy@ --- * |
531 | * |
532 | * Arguments: @da_base *b@ = pointer to array base structure |
533 | * @void *v@ = pointer to vector |
534 | * @size_t sz@ = size of the array elements |
535 | * |
536 | * Returns: Newly allocated vector. |
537 | * |
538 | * Use: Minimizes the space occupied by an array. This function is a |
539 | * helper for the @DA_TIDY@ macro, which should be used by |
540 | * preference. |
541 | */ |
542 | |
543 | extern void *da_tidy(da_base */*b*/, void */*v*/, size_t /*sz*/); |
544 | |
545 | /*----- That's all, folks -------------------------------------------------*/ |
546 | |
547 | #ifdef __cplusplus |
548 | } |
549 | #endif |
550 | |
551 | #endif |