3 * $Id: darray.c,v 1.7 2004/04/08 01:36:11 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 /*----- Header files ------------------------------------------------------*/
40 /*----- Magic numbers -----------------------------------------------------*/
42 #define DA_INITSZ 16 /* Default size for new array */
43 #define DA_SLOTS 8 /* Number of preshifted slots */
45 /*----- Main code ---------------------------------------------------------*/
47 /* --- @da_ensure@ --- *
49 * Arguments: @da_base *b@ = pointer to array base structure
50 * @void *v@ = pointer to array vector
51 * @size_t sz@ = size of individual array elements
52 * @size_t n@ = number of items required at the end
54 * Returns: Pointer to newly allocated or adjusted array vector.
56 * Use: Extends a dynamic array to accommodate a number of new items
57 * at its end. This function is a helper for the @DA_ENSURE@
58 * macro, which should be used by preference.
61 void *da_ensure(da_base *b, void *v, size_t sz, size_t n)
63 size_t rq = n + b->len;
68 /* --- Make sure there's something which needs doing --- *
70 * If there's enough space already then return immediately.
76 /* --- Compute a number of `unshift' slots --- *
78 * When returning from this function, the offset will be set to @slots@.
79 * If @unshift@ is zero, there's no point in reserving slots. Otherwise
80 * choose a power of two greater than @unshift@, with a minimum of
81 * @DA_SLOTS@. Then add the number of slots to the requirement.
88 while (slots < b->unshift)
93 /* --- Maybe just shunt data around a bit --- *
95 * If the vector is large enough, then theoretically we could cope by
96 * moving the objects about in their existing storage. It's not worth
97 * bothering if there's not actually double the amount of space I need.
100 if (rq * 2 < b->sz + b->off) {
101 q = p - (b->off - slots) * sz;
102 memmove(q, p, b->len * sz);
103 b->sz += b->off - slots;
105 b->unshift = b->push = 0;
109 /* --- Decide on a new size --- *
111 * There's a minimum possible size for the array which is used if it's
112 * currently completely empty. Otherwise I choose the smallest power of
113 * two which is big enough, starting at double the current size.
116 nsz = v ? b->sz + b->off : (DA_INITSZ >> 1);
117 do nsz <<= 1; while (nsz < rq);
119 /* --- Reallocate the block --- *
121 * If I'm not changing the base offset then it's worth using @realloc@;
122 * otherwise there'll probably be two calls to @memcpy@ to shunt the data
123 * around so it's not worth bothering.
126 if (p && slots == b->off) {
127 q = x_realloc(b->a, p - b->off * sz, nsz * sz, b->sz + b->off);
130 q = x_alloc(b->a, nsz * sz);
133 memcpy(q, p, b->len * sz);
134 x_free(b->a, p - b->off * sz);
138 /* --- Fill in the other parts of the base structure --- */
142 b->unshift = b->push = 0;
146 /* --- @da_shunt@ --- *
148 * Arguments: @da_base *b@ = pointer to array base structure
149 * @void *v@ = pointer to array vector
150 * @size_t sz@ = size of the array elements
151 * @size_t n@ = number of items required at the start
153 * Returns: Pointer to appropriately bodged vector.
155 * Use: Extends an array to accommodate items inserted at its front.
156 * This function is a helper for the @DA_SHUNT@ macro, which
157 * should be used by preference.
160 void *da_shunt(da_base *b, void *v, size_t sz, size_t n)
167 /* --- Make sure there's something which needs doing --- *
169 * If there's enough space already then return immediately.
175 /* --- Compute a number of `push' slots --- *
177 * When returning from this function, there will be @slots@ free spaces at
178 * the end of the array. If @push@ is zero, there's no point in reserving
179 * slots. Otherwise choose a power of two greater than @push@, with a
180 * minimum of @DA_SLOTS@. To simplify matters, add the number of items
181 * already in the array to @slots@, and then add the number of slots to the
189 while (slots < b->push)
195 /* --- Maybe just shunt data around a bit --- *
197 * If the vector is large enough, then theoretically we could cope by
198 * moving the objects about in their existing storage. Again, if there's
199 * not actually twice the space needed, reallocate the array.
202 if (rq * 2 < b->sz + b->off) {
203 q = p + (b->sz - slots) * sz;
204 memmove(q, p, b->len * sz);
205 b->off += b->sz - slots;
207 b->unshift = b->push = 0;
211 /* --- Reallocate the array --- *
213 * The neat @realloc@ code doesn't need to be here: the offset changes
214 * almost all the time -- that's the whole point of this routine!
217 /* --- Decide on a new size --- *
219 * There's a minimum possible size for the array which is used if it's
220 * currently completely empty. Otherwise I choose the smallest power of
221 * two which is big enough, starting at double the current size.
224 nsz = v ? b->sz + b->off : (DA_INITSZ >> 1);
225 do nsz <<= 1; while (nsz < rq);
227 /* --- Reallocate the block --- *
229 * The neat @realloc@ code doesn't need to be here: the offset changes
230 * almost all the time -- that's the whole point of this routine!
233 q = x_alloc(b->a, nsz * sz);
234 q += (nsz - slots) * sz;
236 memcpy(q, p, b->len * sz);
237 x_free(b->a, p - b->off * sz);
240 /* --- Fill in the other parts of the base structure --- */
242 b->off = nsz - slots;
244 b->unshift = b->push = 0;
248 /* --- @da_tidy@ --- *
250 * Arguments: @da_base *b@ = pointer to array base structure
251 * @void *v@ = pointer to vector
252 * @size_t sz@ = size of the array elements
254 * Returns: Newly allocated vector.
256 * Use: Minimizes the space occupied by an array. This function is a
257 * helper for the @DA_TIDY@ macro, which should be used by
261 void *da_tidy(da_base *b, void *v, size_t sz)
265 b->unshift = b->push = 0;
269 if (b->sz == b->len && b->off == 0)
273 xfree(p - b->off * sz);
277 q = x_alloc(b->a, b->len * sz);
278 memcpy(q, p, b->len * sz);
279 x_free(b->a, p - b->off * sz);
285 /* --- Note about testing --- *
287 * The test rig for this code is split into three parts. There's `da-gtest',
288 * which is a Perl script which generates a list of commands. The `da-ref'
289 * Perl script interprets these commands as operations on a Perl array. It's
290 * relatively conservatively written and believed to be reliable. The
291 * `da-test.c' file implements a command reader for the same syntax and
292 * performs the operations on an integer darray, producing output in the same
293 * format. To test darray, generate a command script with `da-gtest', pass
294 * it through both `da-ref' and `da-test' (the result of compiling
295 * da-test.c'), and compare the results. If they're not byte-for-byte
296 * identical, there's something wrong.
299 /*----- That's all, folks -------------------------------------------------*/