3 * $Id: darray.c,v 1.6 2000/07/16 12:29:16 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.6 2000/07/16 12:29:16 mdw
34 * Change to arena `realloc' interface, to fix a design bug.
36 * Revision 1.5 2000/06/17 10:37:39 mdw
37 * Add support for arena management.
39 * Revision 1.4 1999/11/06 12:40:45 mdw
40 * Minor changes to allocation strategy.
42 * Revision 1.3 1999/10/29 22:59:22 mdw
43 * New array adjustment macros for unsigned arguments.
45 * Revision 1.2 1999/10/28 22:05:28 mdw
46 * Modify and debug allocation routines.
48 * Revision 1.1 1999/10/22 22:37:26 mdw
49 * New dynamic array implementation replaces `dynarray.h'.
53 /*----- Header files ------------------------------------------------------*/
63 /*----- Magic numbers -----------------------------------------------------*/
65 #define DA_INITSZ 16 /* Default size for new array */
66 #define DA_SLOTS 8 /* Number of preshifted slots */
68 /*----- Main code ---------------------------------------------------------*/
70 /* --- @da_ensure@ --- *
72 * Arguments: @da_base *b@ = pointer to array base structure
73 * @void *v@ = pointer to array vector
74 * @size_t sz@ = size of individual array elements
75 * @size_t n@ = number of items required at the end
77 * Returns: Pointer to newly allocated or adjusted array vector.
79 * Use: Extends a dynamic array to accommodate a number of new items
80 * at its end. This function is a helper for the @DA_ENSURE@
81 * macro, which should be used by preference.
84 void *da_ensure(da_base
*b
, void *v
, size_t sz
, size_t n
)
86 size_t rq
= n
+ b
->len
;
91 /* --- Make sure there's something which needs doing --- *
93 * If there's enough space already then return immediately.
99 /* --- Compute a number of `unshift' slots --- *
101 * When returning from this function, the offset will be set to @slots@.
102 * If @unshift@ is zero, there's no point in reserving slots. Otherwise
103 * choose a power of two greater than @unshift@, with a minimum of
104 * @DA_SLOTS@. Then add the number of slots to the requirement.
111 while (slots
< b
->unshift
)
116 /* --- Maybe just shunt data around a bit --- *
118 * If the vector is large enough, then theoretically we could cope by
119 * moving the objects about in their existing storage. It's not worth
120 * bothering if there's not actually double the amount of space I need.
123 if (rq
* 2 < b
->sz
+ b
->off
) {
124 q
= p
- (b
->off
- slots
) * sz
;
125 memmove(q
, p
, b
->len
* sz
);
126 b
->sz
+= b
->off
- slots
;
128 b
->unshift
= b
->push
= 0;
132 /* --- Decide on a new size --- *
134 * There's a minimum possible size for the array which is used if it's
135 * currently completely empty. Otherwise I choose the smallest power of
136 * two which is big enough, starting at double the current size.
139 nsz
= v ? b
->sz
+ b
->off
: (DA_INITSZ
>> 1);
140 do nsz
<<= 1; while (nsz
< rq
);
142 /* --- Reallocate the block --- *
144 * If I'm not changing the base offset then it's worth using @realloc@;
145 * otherwise there'll probably be two calls to @memcpy@ to shunt the data
146 * around so it's not worth bothering.
149 if (p
&& slots
== b
->off
) {
150 q
= x_realloc(b
->a
, p
- b
->off
* sz
, nsz
* sz
, b
->sz
+ b
->off
);
153 q
= x_alloc(b
->a
, nsz
* sz
);
156 memcpy(q
, p
, b
->len
* sz
);
157 x_free(b
->a
, p
- b
->off
* sz
);
161 /* --- Fill in the other parts of the base structure --- */
165 b
->unshift
= b
->push
= 0;
169 /* --- @da_shunt@ --- *
171 * Arguments: @da_base *b@ = pointer to array base structure
172 * @void *v@ = pointer to array vector
173 * @size_t sz@ = size of the array elements
174 * @size_t n@ = number of items required at the start
176 * Returns: Pointer to appropriately bodged vector.
178 * Use: Extends an array to accommodate items inserted at its front.
179 * This function is a helper for the @DA_SHUNT@ macro, which
180 * should be used by preference.
183 void *da_shunt(da_base
*b
, void *v
, size_t sz
, size_t n
)
190 /* --- Make sure there's something which needs doing --- *
192 * If there's enough space already then return immediately.
198 /* --- Compute a number of `push' slots --- *
200 * When returning from this function, there will be @slots@ free spaces at
201 * the end of the array. If @push@ is zero, there's no point in reserving
202 * slots. Otherwise choose a power of two greater than @push@, with a
203 * minimum of @DA_SLOTS@. To simplify matters, add the number of items
204 * already in the array to @slots@, and then add the number of slots to the
212 while (slots
< b
->push
)
218 /* --- Maybe just shunt data around a bit --- *
220 * If the vector is large enough, then theoretically we could cope by
221 * moving the objects about in their existing storage. Again, if there's
222 * not actually twice the space needed, reallocate the array.
225 if (rq
* 2 < b
->sz
+ b
->off
) {
226 q
= p
+ (b
->sz
- slots
) * sz
;
227 memmove(q
, p
, b
->len
* sz
);
228 b
->off
+= b
->sz
- slots
;
230 b
->unshift
= b
->push
= 0;
234 /* --- Reallocate the array --- *
236 * The neat @realloc@ code doesn't need to be here: the offset changes
237 * almost all the time -- that's the whole point of this routine!
240 /* --- Decide on a new size --- *
242 * There's a minimum possible size for the array which is used if it's
243 * currently completely empty. Otherwise I choose the smallest power of
244 * two which is big enough, starting at double the current size.
247 nsz
= v ? b
->sz
+ b
->off
: (DA_INITSZ
>> 1);
248 do nsz
<<= 1; while (nsz
< rq
);
250 /* --- Reallocate the block --- *
252 * The neat @realloc@ code doesn't need to be here: the offset changes
253 * almost all the time -- that's the whole point of this routine!
256 q
= x_alloc(b
->a
, nsz
* sz
);
257 q
+= (nsz
- slots
) * sz
;
259 memcpy(q
, p
, b
->len
* sz
);
260 x_free(b
->a
, p
- b
->off
* sz
);
263 /* --- Fill in the other parts of the base structure --- */
265 b
->off
= nsz
- slots
;
267 b
->unshift
= b
->push
= 0;
271 /* --- @da_tidy@ --- *
273 * Arguments: @da_base *b@ = pointer to array base structure
274 * @void *v@ = pointer to vector
275 * @size_t sz@ = size of the array elements
277 * Returns: Newly allocated vector.
279 * Use: Minimizes the space occupied by an array. This function is a
280 * helper for the @DA_TIDY@ macro, which should be used by
284 void *da_tidy(da_base
*b
, void *v
, size_t sz
)
288 b
->unshift
= b
->push
= 0;
292 if (b
->sz
== b
->len
&& b
->off
== 0)
296 xfree(p
- b
->off
* sz
);
300 q
= x_alloc(b
->a
, b
->len
* sz
);
301 memcpy(q
, p
, b
->len
* sz
);
302 x_free(b
->a
, p
- b
->off
* sz
);
308 /* --- Note about testing --- *
310 * The test rig for this code is split into three parts. There's `da-gtest',
311 * which is a Perl script which generates a list of commands. The `da-ref'
312 * Perl script interprets these commands as operations on a Perl array. It's
313 * relatively conservatively written and believed to be reliable. The
314 * `da-test.c' file implements a command reader for the same syntax and
315 * performs the operations on an integer darray, producing output in the same
316 * format. To test darray, generate a command script with `da-gtest', pass
317 * it through both `da-ref' and `da-test' (the result of compiling
318 * da-test.c'), and compare the results. If they're not byte-for-byte
319 * identical, there's something wrong.
322 /*----- That's all, folks -------------------------------------------------*/