3 * Dynamically growing dense arrays
5 * (c) 1999 Straylight/Edgeware
8 /*----- Licensing notice --------------------------------------------------*
10 * This file is part of the mLib utilities library.
12 * mLib is free software; you can redistribute it and/or modify
13 * it under the terms of the GNU Library General Public License as
14 * published by the Free Software Foundation; either version 2 of the
15 * License, or (at your option) any later version.
17 * mLib is distributed in the hope that it will be useful,
18 * but WITHOUT ANY WARRANTY; without even the implied warranty of
19 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
20 * GNU Library General Public License for more details.
22 * You should have received a copy of the GNU Library General Public
23 * License along with mLib; if not, write to the Free
24 * Software Foundation, Inc., 59 Temple Place - Suite 330, Boston,
28 /*----- Header files ------------------------------------------------------*/
38 /*----- Magic numbers -----------------------------------------------------*/
40 #define DA_INITSZ 16 /* Default size for new array */
41 #define DA_SLOTS 8 /* Number of preshifted slots */
43 /*----- Main code ---------------------------------------------------------*/
45 /* --- @da_ensure@ --- *
47 * Arguments: @da_base *b@ = pointer to array base structure
48 * @void *v@ = pointer to array vector
49 * @size_t sz@ = size of individual array elements
50 * @size_t n@ = number of items required at the end
52 * Returns: Pointer to newly allocated or adjusted array vector.
54 * Use: Extends a dynamic array to accommodate a number of new items
55 * at its end. This function is a helper for the @DA_ENSURE@
56 * macro, which should be used by preference.
59 void *da_ensure(da_base
*b
, void *v
, size_t sz
, size_t n
)
61 size_t rq
= n
+ b
->len
;
66 /* --- Make sure there's something which needs doing --- *
68 * If there's enough space already then return immediately.
74 /* --- Compute a number of `unshift' slots --- *
76 * When returning from this function, the offset will be set to @slots@.
77 * If @unshift@ is zero, there's no point in reserving slots. Otherwise
78 * choose a power of two greater than @unshift@, with a minimum of
79 * @DA_SLOTS@. Then add the number of slots to the requirement.
86 while (slots
< b
->unshift
)
91 /* --- Maybe just shunt data around a bit --- *
93 * If the vector is large enough, then theoretically we could cope by
94 * moving the objects about in their existing storage. It's not worth
95 * bothering if there's not actually double the amount of space I need.
98 if (rq
* 2 < b
->sz
+ b
->off
) {
99 q
= p
- (b
->off
- slots
) * sz
;
100 memmove(q
, p
, b
->len
* sz
);
101 b
->sz
+= b
->off
- slots
;
103 b
->unshift
= b
->push
= 0;
107 /* --- Decide on a new size --- *
109 * There's a minimum possible size for the array which is used if it's
110 * currently completely empty. Otherwise I choose the smallest power of
111 * two which is big enough, starting at double the current size.
114 nsz
= v ? b
->sz
+ b
->off
: (DA_INITSZ
>> 1);
115 do nsz
<<= 1; while (nsz
< rq
);
117 /* --- Reallocate the block --- *
119 * If I'm not changing the base offset then it's worth using @realloc@;
120 * otherwise there'll probably be two calls to @memcpy@ to shunt the data
121 * around so it's not worth bothering.
124 if (p
&& slots
== b
->off
) {
125 q
= x_realloc(b
->a
, p
- b
->off
* sz
, nsz
* sz
, b
->sz
+ b
->off
);
128 q
= x_alloc(b
->a
, nsz
* sz
);
131 memcpy(q
, p
, b
->len
* sz
);
132 x_free(b
->a
, p
- b
->off
* sz
);
136 /* --- Fill in the other parts of the base structure --- */
140 b
->unshift
= b
->push
= 0;
144 /* --- @da_shunt@ --- *
146 * Arguments: @da_base *b@ = pointer to array base structure
147 * @void *v@ = pointer to array vector
148 * @size_t sz@ = size of the array elements
149 * @size_t n@ = number of items required at the start
151 * Returns: Pointer to appropriately bodged vector.
153 * Use: Extends an array to accommodate items inserted at its front.
154 * This function is a helper for the @DA_SHUNT@ macro, which
155 * should be used by preference.
158 void *da_shunt(da_base
*b
, void *v
, size_t sz
, size_t n
)
165 /* --- Make sure there's something which needs doing --- *
167 * If there's enough space already then return immediately.
173 /* --- Compute a number of `push' slots --- *
175 * When returning from this function, there will be @slots@ free spaces at
176 * the end of the array. If @push@ is zero, there's no point in reserving
177 * slots. Otherwise choose a power of two greater than @push@, with a
178 * minimum of @DA_SLOTS@. To simplify matters, add the number of items
179 * already in the array to @slots@, and then add the number of slots to the
187 while (slots
< b
->push
)
193 /* --- Maybe just shunt data around a bit --- *
195 * If the vector is large enough, then theoretically we could cope by
196 * moving the objects about in their existing storage. Again, if there's
197 * not actually twice the space needed, reallocate the array.
200 if (rq
* 2 < b
->sz
+ b
->off
) {
201 q
= p
+ (b
->sz
- slots
) * sz
;
202 memmove(q
, p
, b
->len
* sz
);
203 b
->off
+= b
->sz
- slots
;
205 b
->unshift
= b
->push
= 0;
209 /* --- Reallocate the array --- *
211 * The neat @realloc@ code doesn't need to be here: the offset changes
212 * almost all the time -- that's the whole point of this routine!
215 /* --- Decide on a new size --- *
217 * There's a minimum possible size for the array which is used if it's
218 * currently completely empty. Otherwise I choose the smallest power of
219 * two which is big enough, starting at double the current size.
222 nsz
= v ? b
->sz
+ b
->off
: (DA_INITSZ
>> 1);
223 do nsz
<<= 1; while (nsz
< rq
);
225 /* --- Reallocate the block --- *
227 * The neat @realloc@ code doesn't need to be here: the offset changes
228 * almost all the time -- that's the whole point of this routine!
231 q
= x_alloc(b
->a
, nsz
* sz
);
232 q
+= (nsz
- slots
) * sz
;
234 memcpy(q
, p
, b
->len
* sz
);
235 x_free(b
->a
, p
- b
->off
* sz
);
238 /* --- Fill in the other parts of the base structure --- */
240 b
->off
= nsz
- slots
;
242 b
->unshift
= b
->push
= 0;
246 /* --- @da_tidy@ --- *
248 * Arguments: @da_base *b@ = pointer to array base structure
249 * @void *v@ = pointer to vector
250 * @size_t sz@ = size of the array elements
252 * Returns: Newly allocated vector.
254 * Use: Minimizes the space occupied by an array. This function is a
255 * helper for the @DA_TIDY@ macro, which should be used by
259 void *da_tidy(da_base
*b
, void *v
, size_t sz
)
263 b
->unshift
= b
->push
= 0;
267 if (b
->sz
== b
->len
&& b
->off
== 0)
271 xfree(p
- b
->off
* sz
);
275 q
= x_alloc(b
->a
, b
->len
* sz
);
276 memcpy(q
, p
, b
->len
* sz
);
277 x_free(b
->a
, p
- b
->off
* sz
);
283 /* --- Note about testing --- *
285 * The test rig for this code is split into three parts. There's `da-gtest',
286 * which is a Perl script which generates a list of commands. The `da-ref'
287 * Perl script interprets these commands as operations on a Perl array. It's
288 * relatively conservatively written and believed to be reliable. The
289 * `da-test.c' file implements a command reader for the same syntax and
290 * performs the operations on an integer darray, producing output in the same
291 * format. To test darray, generate a command script with `da-gtest', pass
292 * it through both `da-ref' and `da-test' (the result of compiling
293 * da-test.c'), and compare the results. If they're not byte-for-byte
294 * identical, there's something wrong.
297 /*----- That's all, folks -------------------------------------------------*/