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