chiark / gitweb /
Support for resource pools, based on the Apache model.
[mLib] / darray.c
CommitLineData
3745e24b 1/* -*-c-*-
2 *
20eb516f 3 * $Id: darray.c,v 1.5 2000/06/17 10:37:39 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.c,v $
20eb516f 33 * Revision 1.5 2000/06/17 10:37:39 mdw
34 * Add support for arena management.
35 *
c6e5bbae 36 * Revision 1.4 1999/11/06 12:40:45 mdw
37 * Minor changes to allocation strategy.
38 *
85bb21f7 39 * Revision 1.3 1999/10/29 22:59:22 mdw
40 * New array adjustment macros for unsigned arguments.
41 *
f8509853 42 * Revision 1.2 1999/10/28 22:05:28 mdw
43 * Modify and debug allocation routines.
44 *
3745e24b 45 * Revision 1.1 1999/10/22 22:37:26 mdw
46 * New dynamic array implementation replaces `dynarray.h'.
47 *
48 */
49
50/*----- Header files ------------------------------------------------------*/
51
52#include <stdio.h>
53#include <string.h>
54#include <stdlib.h>
55
56#include "alloc.h"
20eb516f 57#include "arena.h"
3745e24b 58#include "darray.h"
59
60/*----- Magic numbers -----------------------------------------------------*/
61
f8509853 62#define DA_INITSZ 16 /* Default size for new array */
3745e24b 63#define DA_SLOTS 8 /* Number of preshifted slots */
64
65/*----- Main code ---------------------------------------------------------*/
66
67/* --- @da_ensure@ --- *
68 *
69 * Arguments: @da_base *b@ = pointer to array base structure
70 * @void *v@ = pointer to array vector
71 * @size_t sz@ = size of individual array elements
72 * @size_t n@ = number of items required at the end
73 *
74 * Returns: Pointer to newly allocated or adjusted array vector.
75 *
76 * Use: Extends a dynamic array to accommodate a number of new items
77 * at its end. This function is a helper for the @DA_ENSURE@
78 * macro, which should be used by preference.
79 */
80
81void *da_ensure(da_base *b, void *v, size_t sz, size_t n)
82{
83 size_t rq = n + b->len;
84 char *p = v, *q;
85 size_t nsz;
86 size_t slots;
87
88 /* --- Make sure there's something which needs doing --- *
89 *
90 * If there's enough space already then return immediately.
91 */
92
93 if (rq < b->sz)
94 return (p);
95
96 /* --- Compute a number of `unshift' slots --- *
97 *
98 * When returning from this function, the offset will be set to @slots@.
99 * If @unshift@ is zero, there's no point in reserving slots. Otherwise
100 * choose a power of two greater than @unshift@, with a minimum of
101 * @DA_SLOTS@. Then add the number of slots to the requirement.
102 */
103
104 if (!b->unshift)
105 slots = 0;
106 else {
107 slots = DA_SLOTS;
108 while (slots < b->unshift)
109 slots <<= 1;
110 }
111 rq += slots;
112
113 /* --- Maybe just shunt data around a bit --- *
114 *
115 * If the vector is large enough, then theoretically we could cope by
c6e5bbae 116 * moving the objects about in their existing storage. It's not worth
117 * bothering if there's not actually double the amount of space I need.
3745e24b 118 */
119
c6e5bbae 120 if (rq * 2 < b->sz + b->off) {
3745e24b 121 q = p - (b->off - slots) * sz;
122 memmove(q, p, b->len * sz);
123 b->sz += b->off - slots;
124 b->off = slots;
125 b->unshift = b->push = 0;
126 return (q);
127 }
128
c6e5bbae 129 /* --- Decide on a new size --- *
85bb21f7 130 *
c6e5bbae 131 * There's a minimum possible size for the array which is used if it's
132 * currently completely empty. Otherwise I choose the smallest power of
133 * two which is big enough, starting at double the current size.
85bb21f7 134 */
3745e24b 135
f8509853 136 nsz = v ? b->sz + b->off : (DA_INITSZ >> 1);
3745e24b 137 do nsz <<= 1; while (nsz < rq);
c6e5bbae 138
139 /* --- Reallocate the block --- *
140 *
141 * If I'm not changing the base offset then it's worth using @realloc@;
142 * otherwise there'll probably be two calls to @memcpy@ to shunt the data
143 * around so it's not worth bothering.
144 */
145
85bb21f7 146 if (p && slots == b->off) {
20eb516f 147 q = x_realloc(b->a, p - b->off * sz, nsz * sz);
85bb21f7 148 q += slots * sz;
149 } else {
20eb516f 150 q = x_alloc(b->a, nsz * sz);
85bb21f7 151 q += slots * sz;
152 if (p) {
153 memcpy(q, p, b->len * sz);
20eb516f 154 x_free(b->a, p - b->off * sz);
85bb21f7 155 }
156 }
c6e5bbae 157
158 /* --- Fill in the other parts of the base structure --- */
159
3745e24b 160 b->off = slots;
161 b->sz = nsz - slots;
162 b->unshift = b->push = 0;
163 return (q);
164}
165
166/* --- @da_shunt@ --- *
167 *
168 * Arguments: @da_base *b@ = pointer to array base structure
169 * @void *v@ = pointer to array vector
170 * @size_t sz@ = size of the array elements
171 * @size_t n@ = number of items required at the start
172 *
173 * Returns: Pointer to appropriately bodged vector.
174 *
175 * Use: Extends an array to accommodate items inserted at its front.
176 * This function is a helper for the @DA_SHUNT@ macro, which
177 * should be used by preference.
178 */
179
180void *da_shunt(da_base *b, void *v, size_t sz, size_t n)
181{
182 size_t rq;
183 char *p = v, *q;
184 size_t nsz;
185 size_t slots;
186
187 /* --- Make sure there's something which needs doing --- *
188 *
189 * If there's enough space already then return immediately.
190 */
191
192 if (n < b->off)
193 return (p);
194
195 /* --- Compute a number of `push' slots --- *
196 *
197 * When returning from this function, there will be @slots@ free spaces at
198 * the end of the array. If @push@ is zero, there's no point in reserving
199 * slots. Otherwise choose a power of two greater than @push@, with a
200 * minimum of @DA_SLOTS@. To simplify matters, add the number of items
201 * already in the array to @slots@, and then add the number of slots to the
202 * requirement.
203 */
204
205 if (!b->push)
206 slots = 0;
207 else {
208 slots = DA_SLOTS;
209 while (slots < b->push)
210 slots <<= 1;
211 }
212 slots += b->len;
213 rq = n + slots;
214
215 /* --- Maybe just shunt data around a bit --- *
216 *
217 * If the vector is large enough, then theoretically we could cope by
c6e5bbae 218 * moving the objects about in their existing storage. Again, if there's
219 * not actually twice the space needed, reallocate the array.
3745e24b 220 */
221
c6e5bbae 222 if (rq * 2 < b->sz + b->off) {
3745e24b 223 q = p + (b->sz - slots) * sz;
224 memmove(q, p, b->len * sz);
225 b->off += b->sz - slots;
226 b->sz = slots;
227 b->unshift = b->push = 0;
228 return (q);
229 }
230
85bb21f7 231 /* --- Reallocate the array --- *
232 *
233 * The neat @realloc@ code doesn't need to be here: the offset changes
234 * almost all the time -- that's the whole point of this routine!
235 */
3745e24b 236
c6e5bbae 237 /* --- Decide on a new size --- *
238 *
239 * There's a minimum possible size for the array which is used if it's
240 * currently completely empty. Otherwise I choose the smallest power of
241 * two which is big enough, starting at double the current size.
242 */
243
f8509853 244 nsz = v ? b->sz + b->off : (DA_INITSZ >> 1);
3745e24b 245 do nsz <<= 1; while (nsz < rq);
c6e5bbae 246
247 /* --- Reallocate the block --- *
248 *
249 * The neat @realloc@ code doesn't need to be here: the offset changes
250 * almost all the time -- that's the whole point of this routine!
251 */
252
20eb516f 253 q = x_alloc(b->a, nsz * sz);
3745e24b 254 q += (nsz - slots) * sz;
85bb21f7 255 if (p) {
256 memcpy(q, p, b->len * sz);
20eb516f 257 x_free(b->a, p - b->off * sz);
85bb21f7 258 }
c6e5bbae 259
260 /* --- Fill in the other parts of the base structure --- */
261
3745e24b 262 b->off = nsz - slots;
263 b->sz = slots;
264 b->unshift = b->push = 0;
265 return (q);
266}
267
268/* --- @da_tidy@ --- *
269 *
270 * Arguments: @da_base *b@ = pointer to array base structure
271 * @void *v@ = pointer to vector
272 * @size_t sz@ = size of the array elements
273 *
274 * Returns: Newly allocated vector.
275 *
276 * Use: Minimizes the space occupied by an array. This function is a
277 * helper for the @DA_TIDY@ macro, which should be used by
278 * preference.
279 */
280
281void *da_tidy(da_base *b, void *v, size_t sz)
282{
283 char *p = v, *q;
284
285 b->unshift = b->push = 0;
286
287 if (!p)
288 return (0);
289 if (b->sz == b->len && b->off == 0)
290 return (p);
291
292 if (!b->len) {
20eb516f 293 xfree(p - b->off * sz);
3745e24b 294 return (0);
295 }
296
20eb516f 297 q = x_alloc(b->a, b->len * sz);
3745e24b 298 memcpy(q, p, b->len * sz);
20eb516f 299 x_free(b->a, p - b->off * sz);
3745e24b 300 b->sz = b->len;
301 b->off = 0;
302 return (q);
303}
304
305/* --- Note about testing --- *
306 *
307 * The test rig for this code is split into three parts. There's `da-gtest',
308 * which is a Perl script which generates a list of commands. The `da-ref'
309 * Perl script interprets these commands as operations on a Perl array. It's
310 * relatively conservatively written and believed to be reliable. The
311 * `da-test.c' file implements a command reader for the same syntax and
312 * performs the operations on an integer darray, producing output in the same
313 * format. To test darray, generate a command script with `da-gtest', pass
314 * it through both `da-ref' and `da-test' (the result of compiling
315 * da-test.c'), and compare the results. If they're not byte-for-byte
316 * identical, there's something wrong.
317 */
318
319/*----- That's all, folks -------------------------------------------------*/