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