chiark / gitweb /
Qualify name given to @bres_byname@.
[mLib] / darray.h
CommitLineData
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
108typedef 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
510extern 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
527extern 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
543extern 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