3 * $Id: darray.h,v 1.6 2001/03/03 12:20:23 mdw Exp $
5 * Dynamically growing dense arrays
7 * (c) 1999 Straylight/Edgeware
10 /*----- Licensing notice --------------------------------------------------*
12 * This file is part of the mLib utilities library.
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.
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.
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,
30 /*----- Revision history --------------------------------------------------*
33 * Revision 1.6 2001/03/03 12:20:23 mdw
34 * New macros @DA_FIRST@ and @DA_LAST@ for stack/queue peeking.
36 * Revision 1.5 2000/06/17 10:37:39 mdw
37 * Add support for arena management.
39 * Revision 1.4 1999/12/10 23:42:04 mdw
40 * Change header file guard names.
42 * Revision 1.3 1999/11/05 14:32:43 mdw
43 * Minor change in argument naming.
45 * Revision 1.2 1999/10/29 22:59:22 mdw
46 * New array adjustment macros for unsigned arguments.
48 * Revision 1.1 1999/10/22 22:37:26 mdw
49 * New dynamic array implementation replaces `dynarray.h'.
60 /*----- Header files ------------------------------------------------------*/
74 /*----- Various important constants ---------------------------------------*/
76 /* --- @DAEXC_UFLOW@, @DAEXC_OFLOW@ --- *
78 * Underflow and overflow exceptions raised by @DA_SHIFT@, and by @DA_POP@
82 #define DAEXC_UFLOW EXC_ALLOCN(EXC_MLIB, 0)
83 #define DAEXC_OFLOW EXC_ALLOCN(EXC_MLIB, 1)
85 /*----- Data structures ---------------------------------------------------*/
87 /* --- Base structure for dynamic arrays --- *
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.
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.
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.
105 * Try to use the access macros rather than the structure members.
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 */
113 arena *a; /* Pointer to allocation arena */
116 /* --- @DA_DECL@ --- *
118 * Arguments: @atype@ = type name for the array
119 * @type@ = item type for the array
121 * Use: Declares a structure for decribing a dynamic array.
124 #define DA_DECL(type_v, type) \
125 typedef struct type_v { da_base b; type *v; } type_v
127 /*----- Initialization, creation and destruction --------------------------*/
129 #define DA_INIT { { 0, 0, 0, 0, 0, &arena_stdlib }, 0 }
131 /* --- @DA_CREATE@ --- *
133 * Arguments: @a@ = pointer to an array block (multiply evaluated)
135 * Use: Initializes an array block.
138 #define DA_CREATE(aa) do { \
139 (aa)->b.sz = (aa)->b.len = 0; \
141 (aa)->b.push = (aa)->b.unshift = 0; \
142 (aa)->b.a = &arena_stdlib; \
146 /* --- @DA_DESTROY@ --- *
148 * Arguments: @a@ = pointer to an array block (multiply evaluated)
150 * Use: Destroys an array. The array is left valid but empty.
153 #define DA_DESTROY(aa) do { \
155 x_free((aa)->b.a, (aa)->v - (aa)->b.off); \
159 /*----- Storage reservation -----------------------------------------------*/
161 /* --- @DA_ENSURE@ --- *
163 * Arguments: @a@ = pointer to an array block (multiply evaluated)
164 * @n@ = required number of spare items in the array
166 * Use: Ensures that there are at least @n@ spare slots at the end of
170 #define DA_ENSURE(a, n) do { \
172 if (_n > (a)->b.sz - (a)->b.len) \
173 (a)->v = da_ensure(&(a)->b, (a)->v, sizeof((a)->v[0]), _n); \
178 /* --- @DA_SHUNT@ --- *
180 * Arguments: @a@ = pointer to an array block (multiply evaluated)
181 * @n@ = required number of spare items in the array
183 * Use: Ensures that there are at least @n@ spare slots at the start
187 #define DA_SHUNT(a, n) do { \
189 if (_n > (a)->b.off) \
190 (a)->v = da_shunt(&(a)->b, (a)->v, sizeof((a)->v[0]), _n); \
192 (a)->b.unshift += _n; \
195 /* --- @DA_TIDY@ --- *
197 * Arguments: @a@ = pointer to an array block (multiply evaluated)
199 * Use: Reduces the amount of storage required by an array to its
203 #define DA_TIDY(a) ((a)->v = da_tidy(&(a)->b, (a)->v, sizeof((a)->v[0])))
205 /* --- @DA_RESET@ --- *
207 * Arguments: @a@ = pointer to array block
209 * Use: Removes all the items from the named array. This might not
210 * be a good idea. No storage is freed.
213 #define DA_RESET(a) ((a)->b.len = 0)
215 /*----- Access operations -------------------------------------------------*/
219 * Arguments: @a@ = pointer to array block
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]@.
225 #define DA(a) ((a)->v + 0)
227 /* --- @DA_LEN@ --- *
229 * Arguments: @a@ = pointer to array block
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.
237 #define DA_LEN(a) ((a)->b.len + 0)
239 /* --- @DA_SPARE@ --- *
241 * Arguments: @a@ = pointer to array block (multiply evaluated)
243 * Use: Evaluates to the number of spare array elements above the
247 #define DA_SPARE(a) ((a)->b.sz - (a)->b.len)
249 /* --- @DA_INCLUDE@ --- *
251 * Arguments: @a@ = pointer to array block (multiply evaluated)
252 * @i@ = index into array
254 * Use: Extends the array (if necessary) so that it includes the
258 #define DA_INCLUDE(a, i) do { \
260 size_t _len = DA_LEN(a); \
262 size_t _nn = _i - _len + 1; \
264 DA_UNSAFE_EXTEND(a, _nn); \
268 /* --- @DA_OFFSET@ --- *
270 * Arguments: @a@ = pointer to array block
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.
277 #define DA_OFFSET(a) ((a)->b.off + 0)
279 /* --- @DA_EXTEND@ --- *
281 * Arguments: @a@ = pointer to array block (multiply evaluated)
282 * @n@ = number of slots to add (multiply evaluated)
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)@.
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); \
299 /* --- @DA_UNSAFE_EXTEND@ --- *
301 * Arguments: @a@ = pointer to array block (multiply evaluated)
302 * @n@ = number of slots to add (multiply evaluated)
304 * Use: As for @DA_EXTEND@, only it doesn't check for errors.
307 #define DA_UNSAFE_EXTEND(a, n) do { \
311 /* --- @DA_SLIDE@ --- *
313 * Arguments: @a@ = pointer to array block (multiply evaluated)
314 * @n@ = number of positions to slide the array (multiply
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@
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)); \
336 /* --- @DA_UNSAFE_SLIDE@ --- *
338 * Arguments: @a@ = pointer to array block (multiply evaluated)
339 * @n@ = number of positions to slide the array (multiply
342 * Use: As for @DA_SLIDE@, only it doesn't check for errors.
345 #define DA_UNSAFE_SLIDE(a, n) do { \
352 /* --- @DA_SHRINK@ --- *
354 * Arguments: @a@ = pointer to array block (multiply evaluated)
355 * @n@ = number of slots to remove (multiply evaluated)
357 * Use: As for @DA_EXTEND@, with the sense of the argument reversed.
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); \
368 /* --- @DA_UNSAFE_SHRINK@ --- *
370 * Arguments: @a@ = pointer to array block (multiply evaluated)
371 * @n@ = number of slots to add (multiply evaluated)
373 * Use: As for @DA_SHRINK@, only it doesn't check for errors.
376 #define DA_UNSAFE_SHRINK(a, n) do { \
380 /* --- @DA_UNSLIDE@ --- *
382 * Arguments: @a@ = pointer to array block (multiply evaluated)
383 * @n@ = number of positions to slide the array (multiply
387 * Use: As for @DA_SLIDE@, only in the other direction.
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)); \
398 /* --- @DA_UNSAFE_UNSLIDE@ --- *
400 * Arguments: @a@ = pointer to array block (multiply evaluated)
401 * @n@ = number of positions to slide the array (multiply
404 * Use: As for @DA_UNSLIDE@, only it doesn't check for errors.
407 #define DA_UNSAFE_UNSLIDE(a, n) do { \
414 /*----- Stack-like operations ---------------------------------------------*/
416 /* --- @DA_FIRST@ --- *
418 * Arguments: @a@ = pointer to an array block (multiply evaluated)
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.
424 #define DA_FIRST(a) (DA(a)[0])
426 /* --- @DA_LAST@ --- *
428 * Arguments: @a@ = pointer to an array block (multiply evaluated)
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.
434 #define DA_LAST(a) (DA(a)[(a)->b.len - 1])
436 /* --- @DA_PUSH@ --- *
438 * Arguments: @a@ = pointer to an array block (multiply evaluated)
439 * @x@ = item to append to the end
441 * Use: Appends @x@ as the final element in the array @a@.
444 #define DA_PUSH(a, x) do { \
446 DA(a)[(a)->b.len++] = x; \
449 /* --- @DA_POP@ --- *
451 * Arguments: @a@ = pointer to an array block (multiply evaluated)
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.
459 ((a)->b.len ? ((void)0) : THROW(DAEXC_UFLOW), \
462 /* --- @DA_UNSHIFT@ --- *
464 * Arguments: @a@ = pointer to an array block (multiply evaluated)
465 * @x@ = the new element to insert
467 * Use: Inserts a new element at the beginning of an array. This
468 * might take a while.
471 #define DA_UNSHIFT(a, x) do { \
473 DA_UNSAFE_SLIDE(a, 1); \
477 /* --- @DA_SHIFT@ --- *
479 * Arguments: @a@ = pointer to an array block (multiply evaluated)
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
487 #define DA_SHIFT(a) \
488 ((a)->b.len ? ((void)0) : THROW(DAEXC_UFLOW), \
494 /*----- Functions provided ------------------------------------------------*/
496 /* --- @da_ensure@ --- *
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
503 * Returns: Pointer to newly allocated or adjusted array vector.
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.
510 extern void *da_ensure(da_base */*b*/, void */*v*/,
511 size_t /*sz*/, size_t /*n*/);
513 /* --- @da_shunt@ --- *
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
520 * Returns: Pointer to appropriately bodged vector.
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.
527 extern void *da_shunt(da_base */*b*/, void */*v*/,
528 size_t /*sz*/, size_t /*n*/);
530 /* --- @da_tidy@ --- *
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
536 * Returns: Newly allocated vector.
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
543 extern void *da_tidy(da_base */*b*/, void */*v*/, size_t /*sz*/);
545 /*----- That's all, folks -------------------------------------------------*/