3 * Dynamically growing dense arrays
5 * (c) 1999 Straylight/Edgeware
8 /*----- Licensing notice --------------------------------------------------*
10 * This file is part of the mLib utilities library.
12 * mLib is free software; you can redistribute it and/or modify
13 * it under the terms of the GNU Library General Public License as
14 * published by the Free Software Foundation; either version 2 of the
15 * License, or (at your option) any later version.
17 * mLib is distributed in the hope that it will be useful,
18 * but WITHOUT ANY WARRANTY; without even the implied warranty of
19 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
20 * GNU Library General Public License for more details.
22 * You should have received a copy of the GNU Library General Public
23 * License along with mLib; if not, write to the Free
24 * Software Foundation, Inc., 59 Temple Place - Suite 330, Boston,
35 /*----- Header files ------------------------------------------------------*/
49 /*----- Various important constants ---------------------------------------*/
51 /* --- @DAEXC_UFLOW@, @DAEXC_OFLOW@ --- *
53 * Underflow and overflow exceptions raised by @DA_SHIFT@, and by @DA_POP@
57 #define DAEXC_UFLOW EXC_ALLOCN(EXC_MLIB, 0)
58 #define DAEXC_OFLOW EXC_ALLOCN(EXC_MLIB, 1)
60 /*----- Data structures ---------------------------------------------------*/
62 /* --- Base structure for dynamic arrays --- *
64 * An actual array has a `vector' @v@ in addition to this data (which is
65 * tucked away in the @b@ member). The vector contains the actual storage
66 * for the array elements.
68 * The vector pointer @v@ potentially points somewhere in the middle of the
69 * allocated storage. The @off@ member explains how far into the storage the
70 * vector points. The allocated storage is sufficient for @sz + off@ items
71 * to be stored. Valid array indices are integers between 0 (inclusive) and
72 * @len@ (exclusive). Thus, from @v@ onwards, there is space for @sz@
73 * elements, and of these, @sz - len@ are currently not considered to be
74 * within the array's bounds.
76 * The @push@ and @unshift@ counts record how many times these operations
77 * have been performed since the last extension of the array. They are used
78 * by the extension algorithm to decide how to position the data offset.
80 * Try to use the access macros rather than the structure members.
83 typedef struct da_base
{
84 size_t sz
; /* Size of allocated vector */
85 size_t len
; /* Length of useful portion */
86 size_t off
; /* Offset of @v@ into space */
87 unsigned push
, unshift
; /* Pushes/unshifts since growth */
88 arena
*a
; /* Pointer to allocation arena */
91 /* --- @DA_DECL@ --- *
93 * Arguments: @atype@ = type name for the array
94 * @type@ = item type for the array
96 * Use: Declares a structure for decribing a dynamic array.
99 #define DA_DECL(type_v, type) \
100 typedef struct type_v { da_base b; type *v; } type_v
102 /*----- Initialization, creation and destruction --------------------------*/
104 #define DA_INIT { { 0, 0, 0, 0, 0, &arena_stdlib }, 0 }
106 /* --- @DA_CREATE@ --- *
108 * Arguments: @a@ = pointer to an array block (multiply evaluated)
110 * Use: Initializes an array block.
113 #define DA_CREATE(aa) do { \
114 (aa)->b.sz = (aa)->b.len = 0; \
116 (aa)->b.push = (aa)->b.unshift = 0; \
117 (aa)->b.a = &arena_stdlib; \
121 /* --- @DA_DESTROY@ --- *
123 * Arguments: @a@ = pointer to an array block (multiply evaluated)
125 * Use: Destroys an array. The array is left valid but empty.
128 #define DA_DESTROY(aa) do { \
130 x_free((aa)->b.a, (aa)->v - (aa)->b.off); \
134 /*----- Storage reservation -----------------------------------------------*/
136 /* --- @DA_ENSURE@ --- *
138 * Arguments: @a@ = pointer to an array block (multiply evaluated)
139 * @n@ = required number of spare items in the array
141 * Use: Ensures that there are at least @n@ spare slots at the end of
145 #define DA_ENSURE(a, n) do { \
147 if (_n > (a)->b.sz - (a)->b.len) \
148 (a)->v = da_ensure(&(a)->b, (a)->v, sizeof((a)->v[0]), _n); \
153 /* --- @DA_SHUNT@ --- *
155 * Arguments: @a@ = pointer to an array block (multiply evaluated)
156 * @n@ = required number of spare items in the array
158 * Use: Ensures that there are at least @n@ spare slots at the start
162 #define DA_SHUNT(a, n) do { \
164 if (_n > (a)->b.off) \
165 (a)->v = da_shunt(&(a)->b, (a)->v, sizeof((a)->v[0]), _n); \
167 (a)->b.unshift += _n; \
170 /* --- @DA_TIDY@ --- *
172 * Arguments: @a@ = pointer to an array block (multiply evaluated)
174 * Use: Reduces the amount of storage required by an array to its
178 #define DA_TIDY(a) ((a)->v = da_tidy(&(a)->b, (a)->v, sizeof((a)->v[0])))
180 /* --- @DA_RESET@ --- *
182 * Arguments: @a@ = pointer to array block
184 * Use: Removes all the items from the named array. This might not
185 * be a good idea. No storage is freed.
188 #define DA_RESET(a) ((a)->b.len = 0)
190 /*----- Access operations -------------------------------------------------*/
194 * Arguments: @a@ = pointer to array block
196 * Use: Expands to a reference to the array proper. Given an array
197 * @a@, item @i@ may be located using the expression @DA(a)[i]@.
200 #define DA(a) ((a)->v + 0)
202 /* --- @DA_LEN@ --- *
204 * Arguments: @a@ = pointer to array block
206 * Use: Expands to the number of elements in the array. Elements are
207 * assigned integer indices in the half-open interval
208 * [0, @DA_LEN(a)@). Don't change the length directly; use
209 * @DA_EXTEND@ instead.
212 #define DA_LEN(a) ((a)->b.len + 0)
214 /* --- @DA_SPARE@ --- *
216 * Arguments: @a@ = pointer to array block (multiply evaluated)
218 * Use: Evaluates to the number of spare array elements above the
222 #define DA_SPARE(a) ((a)->b.sz - (a)->b.len)
224 /* --- @DA_INCLUDE@ --- *
226 * Arguments: @a@ = pointer to array block (multiply evaluated)
227 * @i@ = index into array
229 * Use: Extends the array (if necessary) so that it includes the
233 #define DA_INCLUDE(a, i) do { \
235 size_t _len = DA_LEN(a); \
237 size_t _nn = _i - _len + 1; \
239 DA_UNSAFE_EXTEND(a, _nn); \
243 /* --- @DA_OFFSET@ --- *
245 * Arguments: @a@ = pointer to array block
247 * Use: Evaluates to the number of spare elements before the
248 * beginning of the array. Don't modify the offset directly;
249 * use @DA_SLIDE@ instead.
252 #define DA_OFFSET(a) ((a)->b.off + 0)
254 /* --- @DA_EXTEND@ --- *
256 * Arguments: @a@ = pointer to array block (multiply evaluated)
257 * @n@ = number of slots to add (multiply evaluated)
259 * Use: Extends the end of the array by @n@ elements. The exception
260 * @DAEXC_OFLOW@ is thrown if there is not enough space for the
261 * new elements (i.e., @n > DA_SPARE(a)@) -- call @DA_ENSURE@ to
262 * prevent this from happening. The integer @n@ may be
263 * negative; @DAEXC_UFLOW@ is called if @n < DA_LEN(a)@.
266 #define DA_EXTEND(a, n) do { \
267 if ((n) > 0 && (n) > DA_SPARE(a)) \
268 THROW(DAEXC_OFLOW); \
269 else if ((n) < 0 && -(n) > DA_LEN(a)) \
270 THROW(DAEXC_UFLOW); \
271 DA_UNSAFE_EXTEND(a, n); \
274 /* --- @DA_UNSAFE_EXTEND@ --- *
276 * Arguments: @a@ = pointer to array block (multiply evaluated)
277 * @n@ = number of slots to add (multiply evaluated)
279 * Use: As for @DA_EXTEND@, only it doesn't check for errors.
282 #define DA_UNSAFE_EXTEND(a, n) do { \
286 /* --- @DA_SLIDE@ --- *
288 * Arguments: @a@ = pointer to array block (multiply evaluated)
289 * @n@ = number of positions to slide the array (multiply
293 * Use: Slides the array elements by @n@ positions. A positive @n@
294 * slides upwards, introducing new elements at the bottom; a
295 * negative @n@ slides downwards, removing low-numbered
296 * elements. Formally, what was at index @i - n@ before the
297 * slide is moved to index @i@. It is an error to slide by more
298 * than @DA_OFFSET(a)@ or less than @-DA_LEN(a)@. The exception
299 * @DAEXC_OFLOW@ is raised in the former case, and @DAEXC_UFLOW@
303 #define DA_SLIDE(a, n) do { \
304 if ((n) > 0 && (n) > DA_OFFSET(a)) \
305 THROW(DAEXC_OFLOW); \
306 else if ((n) < 0 && -(n) > DA_LEN(a)) \
307 THROW(DAEXC_UFLOW); \
308 DA_UNSAFE_SLIDE((a), (n)); \
311 /* --- @DA_UNSAFE_SLIDE@ --- *
313 * Arguments: @a@ = pointer to array block (multiply evaluated)
314 * @n@ = number of positions to slide the array (multiply
317 * Use: As for @DA_SLIDE@, only it doesn't check for errors.
320 #define DA_UNSAFE_SLIDE(a, n) do { \
327 /* --- @DA_SHRINK@ --- *
329 * Arguments: @a@ = pointer to array block (multiply evaluated)
330 * @n@ = number of slots to remove (multiply evaluated)
332 * Use: As for @DA_EXTEND@, with the sense of the argument reversed.
335 #define DA_SHRINK(a, n) do { \
336 if ((n) > 0 && (n) > DA_LEN(a)) \
337 THROW(DAEXC_UFLOW); \
338 else if ((n) < 0 && -(n) > DA_SPARE(a)) \
339 THROW(DAEXC_OFLOW); \
340 DA_UNSAFE_SHRINK(a, n); \
343 /* --- @DA_UNSAFE_SHRINK@ --- *
345 * Arguments: @a@ = pointer to array block (multiply evaluated)
346 * @n@ = number of slots to add (multiply evaluated)
348 * Use: As for @DA_SHRINK@, only it doesn't check for errors.
351 #define DA_UNSAFE_SHRINK(a, n) do { \
355 /* --- @DA_UNSLIDE@ --- *
357 * Arguments: @a@ = pointer to array block (multiply evaluated)
358 * @n@ = number of positions to slide the array (multiply
362 * Use: As for @DA_SLIDE@, only in the other direction.
365 #define DA_UNSLIDE(a, n) do { \
366 if ((n) > 0 && (n) > DA_LEN(a)) \
367 THROW(DAEXC_UFLOW); \
368 else if ((n) < 0 && -(n) > DA_OFFSET(a)) \
369 THROW(DAEXC_OFLOW); \
370 DA_UNSAFE_UNSLIDE((a), (n)); \
373 /* --- @DA_UNSAFE_UNSLIDE@ --- *
375 * Arguments: @a@ = pointer to array block (multiply evaluated)
376 * @n@ = number of positions to slide the array (multiply
379 * Use: As for @DA_UNSLIDE@, only it doesn't check for errors.
382 #define DA_UNSAFE_UNSLIDE(a, n) do { \
389 /*----- Stack-like operations ---------------------------------------------*/
391 /* --- @DA_FIRST@ --- *
393 * Arguments: @a@ = pointer to an array block (multiply evaluated)
395 * Use: Evaluates to the initial element in array @a@. It is unsafe
396 * to do this if the array is empty. The array is not changed.
399 #define DA_FIRST(a) (DA(a)[0])
401 /* --- @DA_LAST@ --- *
403 * Arguments: @a@ = pointer to an array block (multiply evaluated)
405 * Use: Evaluates to the final element in array @a@. It is unsafe
406 * to do this if the array is empty. The array is not changed.
409 #define DA_LAST(a) (DA(a)[(a)->b.len - 1])
411 /* --- @DA_PUSH@ --- *
413 * Arguments: @a@ = pointer to an array block (multiply evaluated)
414 * @x@ = item to append to the end
416 * Use: Appends @x@ as the final element in the array @a@.
419 #define DA_PUSH(a, x) do { \
421 DA(a)[(a)->b.len++] = x; \
424 /* --- @DA_POP@ --- *
426 * Arguments: @a@ = pointer to an array block (multiply evaluated)
428 * Use: Evaluates to the final element in array @a@. The element is
429 * removed. An exception @DAEXC_UFLOW@ is raised if there is
430 * no item available to pop.
434 ((a)->b.len ? ((void)0) : THROW(DAEXC_UFLOW), \
437 /* --- @DA_UNSHIFT@ --- *
439 * Arguments: @a@ = pointer to an array block (multiply evaluated)
440 * @x@ = the new element to insert
442 * Use: Inserts a new element at the beginning of an array. This
443 * might take a while.
446 #define DA_UNSHIFT(a, x) do { \
448 DA_UNSAFE_SLIDE(a, 1); \
452 /* --- @DA_SHIFT@ --- *
454 * Arguments: @a@ = pointer to an array block (multiply evaluated)
456 * Use: Evaluates to the initial element in array @a@. The element
457 * is removed, and all other elements are shifted down one
458 * place. The exception @DAEXC_UFLOW@ is raised if there is no
462 #define DA_SHIFT(a) \
463 ((a)->b.len ? ((void)0) : THROW(DAEXC_UFLOW), \
469 /*----- Functions provided ------------------------------------------------*/
471 /* --- @da_ensure@ --- *
473 * Arguments: @da_base *b@ = pointer to array base structure
474 * @void *v@ = pointer to array vector
475 * @size_t sz@ = size of individual array elements
476 * @size_t n@ = number of items required at the end
478 * Returns: Pointer to newly allocated or adjusted array vector.
480 * Use: Extends a dynamic array to accommodate a number of new items
481 * at its end. This function is a helper for the @DA_ENSURE@
482 * macro, which should be used by preference.
485 extern void *da_ensure(da_base */
*b*/
, void */
*v*/
,
486 size_t /*sz*/, size_t /*n*/);
488 /* --- @da_shunt@ --- *
490 * Arguments: @da_base *b@ = pointer to array base structure
491 * @void *v@ = pointer to array vector
492 * @size_t sz@ = size of the array elements
493 * @size_t n@ = number of items required at the start
495 * Returns: Pointer to appropriately bodged vector.
497 * Use: Extends an array to accommodate items inserted at its front.
498 * This function is a helper for the @DA_SHUNT@ macro, which
499 * should be used by preference.
502 extern void *da_shunt(da_base */
*b*/
, void */
*v*/
,
503 size_t /*sz*/, size_t /*n*/);
505 /* --- @da_tidy@ --- *
507 * Arguments: @da_base *b@ = pointer to array base structure
508 * @void *v@ = pointer to vector
509 * @size_t sz@ = size of the array elements
511 * Returns: Newly allocated vector.
513 * Use: Minimizes the space occupied by an array. This function is a
514 * helper for the @DA_TIDY@ macro, which should be used by
518 extern void *da_tidy(da_base */
*b*/
, void */
*v*/
, size_t /*sz*/);
520 /*----- That's all, folks -------------------------------------------------*/