chiark / gitweb /
Expunge revision histories in files.
[mLib] / darray.c
CommitLineData
3745e24b 1/* -*-c-*-
2 *
8656dc50 3 * $Id: darray.c,v 1.7 2004/04/08 01:36:11 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
3745e24b 30/*----- Header files ------------------------------------------------------*/
31
32#include <stdio.h>
33#include <string.h>
34#include <stdlib.h>
35
36#include "alloc.h"
20eb516f 37#include "arena.h"
3745e24b 38#include "darray.h"
39
40/*----- Magic numbers -----------------------------------------------------*/
41
f8509853 42#define DA_INITSZ 16 /* Default size for new array */
3745e24b 43#define DA_SLOTS 8 /* Number of preshifted slots */
44
45/*----- Main code ---------------------------------------------------------*/
46
47/* --- @da_ensure@ --- *
48 *
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
53 *
54 * Returns: Pointer to newly allocated or adjusted array vector.
55 *
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.
59 */
60
61void *da_ensure(da_base *b, void *v, size_t sz, size_t n)
62{
63 size_t rq = n + b->len;
64 char *p = v, *q;
65 size_t nsz;
66 size_t slots;
67
68 /* --- Make sure there's something which needs doing --- *
69 *
70 * If there's enough space already then return immediately.
71 */
72
73 if (rq < b->sz)
74 return (p);
75
76 /* --- Compute a number of `unshift' slots --- *
77 *
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.
82 */
83
84 if (!b->unshift)
85 slots = 0;
86 else {
87 slots = DA_SLOTS;
88 while (slots < b->unshift)
89 slots <<= 1;
90 }
91 rq += slots;
92
93 /* --- Maybe just shunt data around a bit --- *
94 *
95 * If the vector is large enough, then theoretically we could cope by
c6e5bbae 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.
3745e24b 98 */
99
c6e5bbae 100 if (rq * 2 < b->sz + b->off) {
3745e24b 101 q = p - (b->off - slots) * sz;
102 memmove(q, p, b->len * sz);
103 b->sz += b->off - slots;
104 b->off = slots;
105 b->unshift = b->push = 0;
106 return (q);
107 }
108
c6e5bbae 109 /* --- Decide on a new size --- *
85bb21f7 110 *
c6e5bbae 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.
85bb21f7 114 */
3745e24b 115
f8509853 116 nsz = v ? b->sz + b->off : (DA_INITSZ >> 1);
3745e24b 117 do nsz <<= 1; while (nsz < rq);
c6e5bbae 118
119 /* --- Reallocate the block --- *
120 *
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.
124 */
125
85bb21f7 126 if (p && slots == b->off) {
b5ea4de3 127 q = x_realloc(b->a, p - b->off * sz, nsz * sz, b->sz + b->off);
85bb21f7 128 q += slots * sz;
129 } else {
20eb516f 130 q = x_alloc(b->a, nsz * sz);
85bb21f7 131 q += slots * sz;
132 if (p) {
133 memcpy(q, p, b->len * sz);
20eb516f 134 x_free(b->a, p - b->off * sz);
85bb21f7 135 }
136 }
c6e5bbae 137
138 /* --- Fill in the other parts of the base structure --- */
139
3745e24b 140 b->off = slots;
141 b->sz = nsz - slots;
142 b->unshift = b->push = 0;
143 return (q);
144}
145
146/* --- @da_shunt@ --- *
147 *
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
152 *
153 * Returns: Pointer to appropriately bodged vector.
154 *
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.
158 */
159
160void *da_shunt(da_base *b, void *v, size_t sz, size_t n)
161{
162 size_t rq;
163 char *p = v, *q;
164 size_t nsz;
165 size_t slots;
166
167 /* --- Make sure there's something which needs doing --- *
168 *
169 * If there's enough space already then return immediately.
170 */
171
172 if (n < b->off)
173 return (p);
174
175 /* --- Compute a number of `push' slots --- *
176 *
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
182 * requirement.
183 */
184
185 if (!b->push)
186 slots = 0;
187 else {
188 slots = DA_SLOTS;
189 while (slots < b->push)
190 slots <<= 1;
191 }
192 slots += b->len;
193 rq = n + slots;
194
195 /* --- Maybe just shunt data around a bit --- *
196 *
197 * If the vector is large enough, then theoretically we could cope by
c6e5bbae 198 * moving the objects about in their existing storage. Again, if there's
199 * not actually twice the space needed, reallocate the array.
3745e24b 200 */
201
c6e5bbae 202 if (rq * 2 < b->sz + b->off) {
3745e24b 203 q = p + (b->sz - slots) * sz;
204 memmove(q, p, b->len * sz);
205 b->off += b->sz - slots;
206 b->sz = slots;
207 b->unshift = b->push = 0;
208 return (q);
209 }
210
85bb21f7 211 /* --- Reallocate the array --- *
212 *
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!
215 */
3745e24b 216
c6e5bbae 217 /* --- Decide on a new size --- *
218 *
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.
222 */
223
f8509853 224 nsz = v ? b->sz + b->off : (DA_INITSZ >> 1);
3745e24b 225 do nsz <<= 1; while (nsz < rq);
c6e5bbae 226
227 /* --- Reallocate the block --- *
228 *
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!
231 */
232
20eb516f 233 q = x_alloc(b->a, nsz * sz);
3745e24b 234 q += (nsz - slots) * sz;
85bb21f7 235 if (p) {
236 memcpy(q, p, b->len * sz);
20eb516f 237 x_free(b->a, p - b->off * sz);
85bb21f7 238 }
c6e5bbae 239
240 /* --- Fill in the other parts of the base structure --- */
241
3745e24b 242 b->off = nsz - slots;
243 b->sz = slots;
244 b->unshift = b->push = 0;
245 return (q);
246}
247
248/* --- @da_tidy@ --- *
249 *
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
253 *
254 * Returns: Newly allocated vector.
255 *
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
258 * preference.
259 */
260
261void *da_tidy(da_base *b, void *v, size_t sz)
262{
263 char *p = v, *q;
264
265 b->unshift = b->push = 0;
266
267 if (!p)
268 return (0);
269 if (b->sz == b->len && b->off == 0)
270 return (p);
271
272 if (!b->len) {
20eb516f 273 xfree(p - b->off * sz);
3745e24b 274 return (0);
275 }
276
20eb516f 277 q = x_alloc(b->a, b->len * sz);
3745e24b 278 memcpy(q, p, b->len * sz);
20eb516f 279 x_free(b->a, p - b->off * sz);
3745e24b 280 b->sz = b->len;
281 b->off = 0;
282 return (q);
283}
284
285/* --- Note about testing --- *
286 *
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.
297 */
298
299/*----- That's all, folks -------------------------------------------------*/