chiark / gitweb /
Commit as 2.1.0.
[mLib] / darray.c
1 /* -*-c-*-
2  *
3  * $Id: darray.c,v 1.7 2004/04/08 01:36:11 mdw Exp $
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 /*----- Header files ------------------------------------------------------*/
31
32 #include <stdio.h>
33 #include <string.h>
34 #include <stdlib.h>
35
36 #include "alloc.h"
37 #include "arena.h"
38 #include "darray.h"
39
40 /*----- Magic numbers -----------------------------------------------------*/
41
42 #define DA_INITSZ 16                    /* Default size for new array */
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
61 void *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
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.
98    */
99
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;
104     b->off = slots;
105     b->unshift = b->push = 0;
106     return (q);
107   }
108
109   /* --- Decide on a new size --- *
110    *
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.
114    */
115
116   nsz = v ? b->sz + b->off : (DA_INITSZ >> 1);
117   do nsz <<= 1; while (nsz < rq);
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
126   if (p && slots == b->off) {
127     q = x_realloc(b->a, p - b->off * sz, nsz * sz, b->sz + b->off);
128     q += slots * sz;
129   } else {
130     q = x_alloc(b->a, nsz * sz);
131     q += slots * sz;
132     if (p) {
133       memcpy(q, p, b->len * sz);
134       x_free(b->a, p - b->off * sz);
135     }
136   }
137
138   /* --- Fill in the other parts of the base structure --- */
139
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
160 void *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
198    * moving the objects about in their existing storage.  Again, if there's
199    * not actually twice the space needed, reallocate the array.
200    */
201
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;
206     b->sz = slots;
207     b->unshift = b->push = 0;
208     return (q);
209   }
210
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    */
216
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
224   nsz = v ? b->sz + b->off : (DA_INITSZ >> 1);
225   do nsz <<= 1; while (nsz < rq);
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
233   q = x_alloc(b->a, nsz * sz);
234   q += (nsz - slots) * sz;
235   if (p) {
236     memcpy(q, p, b->len * sz);
237     x_free(b->a, p - b->off * sz);
238   }
239
240   /* --- Fill in the other parts of the base structure --- */
241
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
261 void *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) {
273     xfree(p - b->off * sz);
274     return (0);
275   }
276
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);
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 -------------------------------------------------*/