1 /* ar.c - variable size arrays
2 *
3 ****************************************************************
4 * Copyright (C) 1998, 2000 Thomas Lord
5 *
6 * See the file "COPYING" for further information about
7 * the copyright and warranty status of this work.
8 */
9
10
11 #include "hackerlab/machine/alignment.h"
12 #include "hackerlab/mem/must-malloc.h"
13 #include "hackerlab/mem/mem.h"
14 #include "hackerlab/arrays/ar.h"
15
16 /************************************************************************
17 *(h1 "Variable Size Arrays"
18 * :include ("hackerlab/arrays/ar.h"))
19 *
20 * |array|
21 * |variable size array|
22 * |power of two size array|
23 * |aparse array|
24 *
25 * A "variable size array" is a dynamically allocated block of memory,
26 * similar to a block returned by `lim_malloc', except that a variable sized
27 * array is tagged with its size, measured in the number of array elements.
28 *
29 * A null pointer counts as an array of 0 elements. For example, if
30 * `ar_size', which returns the size of a variable sized arrary, is
31 * passed `0', it returns 0. That means there is no special function
32 * to allocate a new variable sized array -- instead, array pointers
33 * should be initialized to 0. This example creates an array with ten
34 * integers by using `ar_ref':
35 *
36 * {
37 * int * the_array;
38 * int * tenth_element;
39 *
40 * the_array = 0;
41 * tenth_element = (int *)ar_ref (&the_array,
42 * lim_use_must_malloc,
43 * 9,
44 * sizeof (int));
45 * }
46 *
47 * A variable size array can be used as a stack. (See `ar_push' and
48 * `ar_pop'.)
49 *
50 * Array functions use the `lim_malloc' family of functions to allcoate
51 * memory. (See xref:"Allocation With Limitations".)
52 */
53 /*(menu)
54 */
55
56 /************************************************************************
57 * (h2 "Variable Size Array Internals")
58 *
59 * A variable size array is represented by a malloced block of memory
60 * approximately one word larger than the memory containing the
61 * array's elements. The extra word contains the number of elements
62 * in the array:
63 *
64 *
65 *
66 * __________________________________________________
67 * | padding | n-elements | elt0 | elt1 | elt2 | ...
68 * --------------------------------------------------
69 * ^
70 * | `base'
71 *
72 * Pointers to the array point to element 0 (labeled `base'). The
73 * size of each element is determined by the `szof' parameter to
74 * functions like `ar_setsize' and `ar_ref'. It is not recorded as part
75 * of the array.
76 *
77 * Padding is added as necessary to ensure that the alignment of `elt0'
78 * is as would be returned from malloc.
79 *
80 * The amount of storage allocated to the array may be larger than is
81 * indicated by `n-elements'.
82 */
83
84 /************************************************************************
85 *(h2 "Basic Variable Size Array Functions")
86 *
87 *
88 *
89 */
90
91 #define SIZEOF_HEADER ((sizeof (int) > MACHINE_ALIGNMENT) ? sizeof (int) : MACHINE_ALIGNMENT)
92 #define AR_TO_HEADER(B) ((int *)((char *)(B) - SIZEOF_HEADER))
93 #define HEADER_TO_AR(H) ((void *)((char *)(H) + SIZEOF_HEADER))
94
95 /*(c ar_size)
96 * int ar_size (void * base,
97 * alloc_limits limits,
98 * size_t elt_size);
99 *
100 * Return the number of elements in the array. If `base == 0', return
101 * 0.
102 *
103 * `limits' is the allocation limits associated with this array.
104 */
105 int
ar_size(void * base,alloc_limits limits,size_t elt_size)106 ar_size (void * base, alloc_limits limits, size_t elt_size)
107 {
108 if (!base)
109 return 0;
110 else
111 return *AR_TO_HEADER(base);
112 }
113
114
115 /*(c ar_ref)
116 * void * ar_ref (void ** base,
117 * alloc_limits limits,
118 * int n,
119 * int szof);
120 *
121 * Return the address of element `n' of an array, expanding the array
122 * to `n+1' elements, if necessary.
123 *
124 * `base' is a pointer to a pointer to the array.
125 *
126 * `limits' is the allocation limits associated with this array.
127 *
128 * `szof' is the size, in bytes, of one element of the array.
129 *
130 * If this function adds new elements to an array, those elements are
131 * filled with 0 bytes.
132 *
133 * This function may resize and relocate the array. If it does,
134 * `*base' is updated to point to the new location of the array.
135 */
136 void *
ar_ref(void ** base,alloc_limits limits,int n,int szof)137 ar_ref (void ** base,
138 alloc_limits limits,
139 int n,
140 int szof)
141 {
142 int * size;
143 void * m;
144 char * b;
145
146 if (!*base)
147 {
148 m = lim_malloc (limits, SIZEOF_HEADER + szof * (n + 1));
149 if (!m)
150 return 0;
151 b = HEADER_TO_AR (m);
152 size = AR_TO_HEADER (b);
153 mem_set0 (b, szof * (n + 1));
154 *size = n + 1;
155 *base = b;
156 }
157 else
158 {
159 b = (char *)*base;
160 size = AR_TO_HEADER (b);
161 if (*size < (n + 1))
162 {
163 size_t old_size;
164 old_size = *size;
165 m = lim_realloc (limits, size, (SIZEOF_HEADER + szof * (n + 1)));
166 if (!m)
167 return 0;
168 b = HEADER_TO_AR (m);
169 size = AR_TO_HEADER (b);
170 mem_set0 (b + old_size * szof, (n + 1 - old_size) * szof);
171 *size = n + 1;
172 *base = b;
173 }
174 }
175 return b + szof * n;
176 }
177
178
179 /*(c ar_setsize)
180 * void ar_setsize (void ** base,
181 * alloc_limits limits,
182 * int n,
183 * size_t szof);
184 *
185 * Resize the array so that it contains exactly `n' elements.
186 *
187 * `base' is a pointer to a pointer to the array.
188 *
189 * `limits' is the allocation limits associated with this array.
190 *
191 * `szof' is the size, in bytes, of one element.
192 *
193 * If this function adds new elements to an array, those elements are
194 * filled with 0 bytes.
195 *
196 * This function can be used to make an array smaller, but doing so
197 * does not reclaim any storage. (See `ar_compact'.)
198 */
199 int
ar_setsize(void ** base,alloc_limits limits,int n,size_t szof)200 ar_setsize (void ** base,
201 alloc_limits limits,
202 int n,
203 size_t szof)
204 {
205 int answer;
206
207 answer = 0;
208
209 if (!n && !*base)
210 return 0;
211
212 if (n > 0)
213 {
214 if (!ar_ref (base, limits, n - 1, szof))
215 answer = -1;
216 }
217
218 if (!answer && *base)
219 {
220 *AR_TO_HEADER (*base) = n;
221 }
222
223 return answer;
224 }
225
226
227 /*(c ar_compact)
228 * void ar_compact (void ** base,
229 * alloc_limits limits,
230 * size_t szof);
231 *
232 * Resize an array so that it is only as large as it needs to be.
233 *
234 * `base' is a pointer to a pointer to the array.
235 *
236 * `limits' is the allocation limits associated with this array.
237 *
238 * `szof' is the size, in bytes, of one element.
239 *
240 * This function may resize and relocate the array. If it does,
241 * `*base' is updated to point to the new location of the array.
242 *
243 * Functions like `ar_setsize' can be used to make an array smaller, but
244 * doing so does not reclaim any storage used by the array and does
245 * not move the array in memory.
246 *
247 * This function does attempt to reclaim storage (by using
248 * `lim_realloc'). If the array occupies significantly more memory
249 * than needed, this function will move it to a smaller block.
250 * If `lim_realloc' returns 0, this function has no effect.
251 */
252 void
ar_compact(void ** base,alloc_limits limits,size_t szof)253 ar_compact (void ** base,
254 alloc_limits limits,
255 size_t szof)
256 {
257 size_t size;
258
259 size = ar_size (*base, limits, szof);
260
261 if (size == 0)
262 {
263 if (*base)
264 ar_free (base, limits);
265 *base = 0;
266 return;
267 }
268
269 *base = HEADER_TO_AR (lim_realloc (limits, (void *)AR_TO_HEADER (*base), SIZEOF_HEADER + size * szof));
270 }
271
272
273 /*(c ar_free)
274 * void ar_free (void ** base, alloc_limits limits);
275 *
276 * Release storage associated with the array pointed to by `*base'.
277 * Set `*base' to 0.
278 *
279 * `limits' is the allocation limits associated with this array.
280 */
281 void
ar_free(void ** base,alloc_limits limits)282 ar_free (void ** base, alloc_limits limits)
283 {
284 if (*base)
285 lim_free (limits, (void *)AR_TO_HEADER (*base));
286 *base = 0;
287 }
288
289
290
291 /************************************************************************
292 *(h2 "Variable Sized Arrays as Stacks")
293 *
294 *
295 *
296 */
297
298 /*(c ar_push)
299 * void * ar_push (void ** base,
300 * alloc_limits limits,
301 * size_t szof);
302 *
303 * Return the address of element `n' in an array previously containing
304 * only `n-1' elements.
305 *
306 * `base' is a pointer to a pointer to the array.
307 *
308 * `limits' is the allocation limits associated with this array.
309 *
310 * `szof' is the size, in bytes, of one element.
311 *
312 * The new array element is filled with 0 bytes.
313 *
314 * This function may resize and relocate the array. If it does,
315 * `*base' is updated to point to the new location of the array.
316 */
317 void *
ar_push(void ** base,alloc_limits limits,size_t szof)318 ar_push (void ** base,
319 alloc_limits limits,
320 size_t szof)
321 {
322 return ar_ref (base, limits, ar_size (*base, limits, szof), szof);
323 }
324
325
326 /*(c ar_pop)
327 * void * ar_pop (void ** base,
328 * alloc_limits limits,
329 * size_t szof);
330 *
331 * Return the address of the `n'th element in an array previously
332 * containing `n' elements. Resize the array so that it contains
333 * exactly `n-1' elements.
334 *
335 * `base' is a pointer to a pointer to the array.
336 *
337 * `limits' is the allocation limits associated with this array.
338 *
339 * `szof' is the size, in bytes, of one element.
340 *
341 * This function may resize and relocate the array. If it does,
342 * `*base' is updated to point to the new location of the array.
343 */
344 void *
ar_pop(void ** base,alloc_limits limits,size_t szof)345 ar_pop (void ** base,
346 alloc_limits limits,
347 size_t szof)
348 {
349 int size;
350
351 size = ar_size (*base, limits, szof);
352 ar_setsize (base, limits, size - 1, szof);
353 return (void *)((char *)*base + ((size - 1) * szof));
354 }
355
356
357 /*(c ar_copy)
358 * void * ar_copy (void * base,
359 * alloc_limits limits,
360 * size_t szof);
361 *
362 * Create a new array which is a copy of the array pointed to by
363 * `base'.
364 *
365 * `limits' is the allocation limits associated with this array.
366 */
367 void *
ar_copy(void * base,alloc_limits limits,size_t szof)368 ar_copy (void * base,
369 alloc_limits limits,
370 size_t szof)
371 {
372 void * answer;
373
374 answer = 0;
375 ar_setsize (&answer, limits, ar_size (base, limits, szof), szof);
376 mem_move (answer, base, szof * ar_size (base, limits, szof));
377 return answer;
378 }
379