3 * $Id: darray.h,v 1.5 2000/06/17 10:37:39 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.5 2000/06/17 10:37:39 mdw
34 * Add support for arena management.
36 * Revision 1.4 1999/12/10 23:42:04 mdw
37 * Change header file guard names.
39 * Revision 1.3 1999/11/05 14:32:43 mdw
40 * Minor change in argument naming.
42 * Revision 1.2 1999/10/29 22:59:22 mdw
43 * New array adjustment macros for unsigned arguments.
45 * Revision 1.1 1999/10/22 22:37:26 mdw
46 * New dynamic array implementation replaces `dynarray.h'.
57 /*----- Header files ------------------------------------------------------*/
71 /*----- Various important constants ---------------------------------------*/
73 /* --- @DAEXC_UFLOW@, @DAEXC_OFLOW@ --- *
75 * Underflow and overflow exceptions raised by @DA_SHIFT@, and by @DA_POP@
79 #define DAEXC_UFLOW EXC_ALLOCN(EXC_MLIB, 0)
80 #define DAEXC_OFLOW EXC_ALLOCN(EXC_MLIB, 1)
82 /*----- Data structures ---------------------------------------------------*/
84 /* --- Base structure for dynamic arrays --- *
86 * An actual array has a `vector' @v@ in addition to this data (which is
87 * tucked away in the @b@ member). The vector contains the actual storage
88 * for the array elements.
90 * The vector pointer @v@ potentially points somewhere in the middle of the
91 * allocated storage. The @off@ member explains how far into the storage the
92 * vector points. The allocated storage is sufficient for @sz + off@ items
93 * to be stored. Valid array indices are integers between 0 (inclusive) and
94 * @len@ (exclusive). Thus, from @v@ onwards, there is space for @sz@
95 * elements, and of these, @sz - len@ are currently not considered to be
96 * within the array's bounds.
98 * The @push@ and @unshift@ counts record how many times these operations
99 * have been performed since the last extension of the array. They are used
100 * by the extension algorithm to decide how to position the data offset.
102 * Try to use the access macros rather than the structure members.
105 typedef struct da_base {
106 size_t sz; /* Size of allocated vector */
107 size_t len; /* Length of useful portion */
108 size_t off; /* Offset of @v@ into space */
109 unsigned push, unshift; /* Pushes/unshifts since growth */
110 arena *a; /* Pointer to allocation arena */
113 /* --- @DA_DECL@ --- *
115 * Arguments: @atype@ = type name for the array
116 * @type@ = item type for the array
118 * Use: Declares a structure for decribing a dynamic array.
121 #define DA_DECL(type_v, type) \
122 typedef struct type_v { da_base b; type *v; } type_v
124 /*----- Initialization, creation and destruction --------------------------*/
126 #define DA_INIT { { 0, 0, 0, 0, 0, &arena_stdlib }, 0 }
128 /* --- @DA_CREATE@ --- *
130 * Arguments: @a@ = pointer to an array block (multiply evaluated)
132 * Use: Initializes an array block.
135 #define DA_CREATE(aa) do { \
136 (aa)->b.sz = (aa)->b.len = 0; \
138 (aa)->b.push = (aa)->b.unshift = 0; \
139 (aa)->b.a = &arena_stdlib; \
143 /* --- @DA_DESTROY@ --- *
145 * Arguments: @a@ = pointer to an array block (multiply evaluated)
147 * Use: Destroys an array. The array is left valid but empty.
150 #define DA_DESTROY(aa) do { \
152 x_free((aa)->b.a, (aa)->v - (aa)->b.off); \
156 /*----- Storage reservation -----------------------------------------------*/
158 /* --- @DA_ENSURE@ --- *
160 * Arguments: @a@ = pointer to an array block (multiply evaluated)
161 * @n@ = required number of spare items in the array
163 * Use: Ensures that there are at least @n@ spare slots at the end of
167 #define DA_ENSURE(a, n) do { \
169 if (_n > (a)->b.sz - (a)->b.len) \
170 (a)->v = da_ensure(&(a)->b, (a)->v, sizeof((a)->v[0]), _n); \
175 /* --- @DA_SHUNT@ --- *
177 * Arguments: @a@ = pointer to an array block (multiply evaluated)
178 * @n@ = required number of spare items in the array
180 * Use: Ensures that there are at least @n@ spare slots at the start
184 #define DA_SHUNT(a, n) do { \
186 if (_n > (a)->b.off) \
187 (a)->v = da_shunt(&(a)->b, (a)->v, sizeof((a)->v[0]), _n); \
189 (a)->b.unshift += _n; \
192 /* --- @DA_TIDY@ --- *
194 * Arguments: @a@ = pointer to an array block (multiply evaluated)
196 * Use: Reduces the amount of storage required by an array to its
200 #define DA_TIDY(a) ((a)->v = da_tidy(&(a)->b, (a)->v, sizeof((a)->v[0])))
202 /* --- @DA_RESET@ --- *
204 * Arguments: @a@ = pointer to array block
206 * Use: Removes all the items from the named array. This might not
207 * be a good idea. No storage is freed.
210 #define DA_RESET(a) ((a)->b.len = 0)
212 /*----- Access operations -------------------------------------------------*/
216 * Arguments: @a@ = pointer to array block
218 * Use: Expands to a reference to the array proper. Given an array
219 * @a@, item @i@ may be located using the expression @DA(a)[i]@.
222 #define DA(a) ((a)->v + 0)
224 /* --- @DA_LEN@ --- *
226 * Arguments: @a@ = pointer to array block
228 * Use: Expands to the number of elements in the array. Elements are
229 * assigned integer indices in the half-open interval
230 * [0, @DA_LEN(a)@). Don't change the length directly; use
231 * @DA_EXTEND@ instead.
234 #define DA_LEN(a) ((a)->b.len + 0)
236 /* --- @DA_SPARE@ --- *
238 * Arguments: @a@ = pointer to array block (multiply evaluated)
240 * Use: Evaluates to the number of spare array elements above the
244 #define DA_SPARE(a) ((a)->b.sz - (a)->b.len)
246 /* --- @DA_INCLUDE@ --- *
248 * Arguments: @a@ = pointer to array block (multiply evaluated)
249 * @i@ = index into array
251 * Use: Extends the array (if necessary) so that it includes the
255 #define DA_INCLUDE(a, i) do { \
257 size_t _len = DA_LEN(a); \
259 size_t _nn = _i - _len + 1; \
261 DA_UNSAFE_EXTEND(a, _nn); \
265 /* --- @DA_OFFSET@ --- *
267 * Arguments: @a@ = pointer to array block
269 * Use: Evaluates to the number of spare elements before the
270 * beginning of the array. Don't modify the offset directly;
271 * use @DA_SLIDE@ instead.
274 #define DA_OFFSET(a) ((a)->b.off + 0)
276 /* --- @DA_EXTEND@ --- *
278 * Arguments: @a@ = pointer to array block (multiply evaluated)
279 * @n@ = number of slots to add (multiply evaluated)
281 * Use: Extends the end of the array by @n@ elements. The exception
282 * @DAEXC_OFLOW@ is thrown if there is not enough space for the
283 * new elements (i.e., @n > DA_SPARE(a)@) -- call @DA_ENSURE@ to
284 * prevent this from happening. The integer @n@ may be
285 * negative; @DAEXC_UFLOW@ is called if @n < DA_LEN(a)@.
288 #define DA_EXTEND(a, n) do { \
289 if ((n) > 0 && (n) > DA_SPARE(a)) \
290 THROW(DAEXC_OFLOW); \
291 else if ((n) < 0 && -(n) > DA_LEN(a)) \
292 THROW(DAEXC_UFLOW); \
293 DA_UNSAFE_EXTEND(a, n); \
296 /* --- @DA_UNSAFE_EXTEND@ --- *
298 * Arguments: @a@ = pointer to array block (multiply evaluated)
299 * @n@ = number of slots to add (multiply evaluated)
301 * Use: As for @DA_EXTEND@, only it doesn't check for errors.
304 #define DA_UNSAFE_EXTEND(a, n) do { \
308 /* --- @DA_SLIDE@ --- *
310 * Arguments: @a@ = pointer to array block (multiply evaluated)
311 * @n@ = number of positions to slide the array (multiply
315 * Use: Slides the array elements by @n@ positions. A positive @n@
316 * slides upwards, introducing new elements at the bottom; a
317 * negative @n@ slides downwards, removing low-numbered
318 * elements. Formally, what was at index @i - n@ before the
319 * slide is moved to index @i@. It is an error to slide by more
320 * than @DA_OFFSET(a)@ or less than @-DA_LEN(a)@. The exception
321 * @DAEXC_OFLOW@ is raised in the former case, and @DAEXC_UFLOW@
325 #define DA_SLIDE(a, n) do { \
326 if ((n) > 0 && (n) > DA_OFFSET(a)) \
327 THROW(DAEXC_OFLOW); \
328 else if ((n) < 0 && -(n) > DA_LEN(a)) \
329 THROW(DAEXC_UFLOW); \
330 DA_UNSAFE_SLIDE((a), (n)); \
333 /* --- @DA_UNSAFE_SLIDE@ --- *
335 * Arguments: @a@ = pointer to array block (multiply evaluated)
336 * @n@ = number of positions to slide the array (multiply
339 * Use: As for @DA_SLIDE@, only it doesn't check for errors.
342 #define DA_UNSAFE_SLIDE(a, n) do { \
349 /* --- @DA_SHRINK@ --- *
351 * Arguments: @a@ = pointer to array block (multiply evaluated)
352 * @n@ = number of slots to remove (multiply evaluated)
354 * Use: As for @DA_EXTEND@, with the sense of the argument reversed.
357 #define DA_SHRINK(a, n) do { \
358 if ((n) > 0 && (n) > DA_LEN(a)) \
359 THROW(DAEXC_UFLOW); \
360 else if ((n) < 0 && -(n) > DA_SPARE(a)) \
361 THROW(DAEXC_OFLOW); \
362 DA_UNSAFE_SHRINK(a, n); \
365 /* --- @DA_UNSAFE_SHRINK@ --- *
367 * Arguments: @a@ = pointer to array block (multiply evaluated)
368 * @n@ = number of slots to add (multiply evaluated)
370 * Use: As for @DA_SHRINK@, only it doesn't check for errors.
373 #define DA_UNSAFE_SHRINK(a, n) do { \
377 /* --- @DA_UNSLIDE@ --- *
379 * Arguments: @a@ = pointer to array block (multiply evaluated)
380 * @n@ = number of positions to slide the array (multiply
384 * Use: As for @DA_SLIDE@, only in the other direction.
387 #define DA_UNSLIDE(a, n) do { \
388 if ((n) > 0 && (n) > DA_LEN(a)) \
389 THROW(DAEXC_UFLOW); \
390 else if ((n) < 0 && -(n) > DA_OFFSET(a)) \
391 THROW(DAEXC_OFLOW); \
392 DA_UNSAFE_UNSLIDE((a), (n)); \
395 /* --- @DA_UNSAFE_UNSLIDE@ --- *
397 * Arguments: @a@ = pointer to array block (multiply evaluated)
398 * @n@ = number of positions to slide the array (multiply
401 * Use: As for @DA_UNSLIDE@, only it doesn't check for errors.
404 #define DA_UNSAFE_UNSLIDE(a, n) do { \
411 /*----- Stack-like operations ---------------------------------------------*/
413 /* --- @DA_PUSH@ --- *
415 * Arguments: @a@ = pointer to an array block (multiply evaluated)
416 * @x@ = item to append to the end
418 * Use: Appends @x@ as the final element in the array @a@.
421 #define DA_PUSH(a, x) do { \
423 DA(a)[(a)->b.len++] = x; \
426 /* --- @DA_POP@ --- *
428 * Arguments: @a@ = pointer to an array block (multiply evaluated)
430 * Use: Evaluates to the final element in array @a@. The element is
431 * removed. An exception @DAEXC_UFLOW@ is raised if there is
432 * no item available to pop.
436 ((a)->b.len ? ((void)0) : THROW(DAEXC_UFLOW), \
439 /* --- @DA_UNSHIFT@ --- *
441 * Arguments: @a@ = pointer to an array block (multiply evaluated)
442 * @x@ = the new element to insert
444 * Use: Inserts a new element at the beginning of an array. This
445 * might take a while.
448 #define DA_UNSHIFT(a, x) do { \
450 DA_UNSAFE_SLIDE(a, 1); \
454 /* --- @DA_SHIFT@ --- *
456 * Arguments: @a@ = pointer to an array block (multiply evaluated)
458 * Use: Evaluates to the initial element in array @a@. The element
459 * is removed, and all other elements are shifted down one
460 * place. The exception @DAEXC_UFLOW@ is raised if there is no
464 #define DA_SHIFT(a) \
465 ((a)->b.len ? ((void)0) : THROW(DAEXC_UFLOW), \
471 /*----- Functions provided ------------------------------------------------*/
473 /* --- @da_ensure@ --- *
475 * Arguments: @da_base *b@ = pointer to array base structure
476 * @void *v@ = pointer to array vector
477 * @size_t sz@ = size of individual array elements
478 * @size_t n@ = number of items required at the end
480 * Returns: Pointer to newly allocated or adjusted array vector.
482 * Use: Extends a dynamic array to accommodate a number of new items
483 * at its end. This function is a helper for the @DA_ENSURE@
484 * macro, which should be used by preference.
487 extern void *da_ensure(da_base */*b*/, void */*v*/,
488 size_t /*sz*/, size_t /*n*/);
490 /* --- @da_shunt@ --- *
492 * Arguments: @da_base *b@ = pointer to array base structure
493 * @void *v@ = pointer to array vector
494 * @size_t sz@ = size of the array elements
495 * @size_t n@ = number of items required at the start
497 * Returns: Pointer to appropriately bodged vector.
499 * Use: Extends an array to accommodate items inserted at its front.
500 * This function is a helper for the @DA_SHUNT@ macro, which
501 * should be used by preference.
504 extern void *da_shunt(da_base */*b*/, void */*v*/,
505 size_t /*sz*/, size_t /*n*/);
507 /* --- @da_tidy@ --- *
509 * Arguments: @da_base *b@ = pointer to array base structure
510 * @void *v@ = pointer to vector
511 * @size_t sz@ = size of the array elements
513 * Returns: Newly allocated vector.
515 * Use: Minimizes the space occupied by an array. This function is a
516 * helper for the @DA_TIDY@ macro, which should be used by
520 extern void *da_tidy(da_base */*b*/, void */*v*/, size_t /*sz*/);
522 /*----- That's all, folks -------------------------------------------------*/