|
1318
|
1 /* Support for dynamic arrays.
|
|
428
|
2 Copyright (C) 1993 Sun Microsystems, Inc.
|
|
2367
|
3 Copyright (C) 2002, 2003, 2004 Ben Wing.
|
|
428
|
4
|
|
|
5 This file is part of XEmacs.
|
|
|
6
|
|
|
7 XEmacs is free software; you can redistribute it and/or modify it
|
|
|
8 under the terms of the GNU General Public License as published by the
|
|
|
9 Free Software Foundation; either version 2, or (at your option) any
|
|
|
10 later version.
|
|
|
11
|
|
|
12 XEmacs is distributed in the hope that it will be useful, but WITHOUT
|
|
|
13 ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
|
|
|
14 FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License
|
|
|
15 for more details.
|
|
|
16
|
|
|
17 You should have received a copy of the GNU General Public License
|
|
|
18 along with XEmacs; see the file COPYING. If not, write to
|
|
|
19 the Free Software Foundation, Inc., 59 Temple Place - Suite 330,
|
|
|
20 Boston, MA 02111-1307, USA. */
|
|
|
21
|
|
|
22 /* Synched up with: Not in FSF. */
|
|
|
23
|
|
|
24 /* Written by Ben Wing, December 1993. */
|
|
|
25
|
|
|
26 /*
|
|
|
27
|
|
|
28 A "dynamic array" is a contiguous array of fixed-size elements where there
|
|
|
29 is no upper limit (except available memory) on the number of elements in the
|
|
|
30 array. Because the elements are maintained contiguously, space is used
|
|
|
31 efficiently (no per-element pointers necessary) and random access to a
|
|
|
32 particular element is in constant time. At any one point, the block of memory
|
|
|
33 that holds the array has an upper limit; if this limit is exceeded, the
|
|
|
34 memory is realloc()ed into a new array that is twice as big. Assuming that
|
|
|
35 the time to grow the array is on the order of the new size of the array
|
|
|
36 block, this scheme has a provably constant amortized time (i.e. average
|
|
|
37 time over all additions).
|
|
|
38
|
|
|
39 When you add elements or retrieve elements, pointers are used. Note that
|
|
|
40 the element itself (of whatever size it is), and not the pointer to it,
|
|
|
41 is stored in the array; thus you do not have to allocate any heap memory
|
|
|
42 on your own. Also, returned pointers are only guaranteed to be valid
|
|
|
43 until the next operation that changes the length of the array.
|
|
|
44
|
|
|
45 This is a container object. Declare a dynamic array of a specific type
|
|
|
46 as follows:
|
|
|
47
|
|
2367
|
48 typedef struct
|
|
|
49 {
|
|
|
50 Dynarr_declare (mytype);
|
|
|
51 } mytype_dynarr;
|
|
428
|
52
|
|
|
53 Use the following functions/macros:
|
|
|
54
|
|
|
55 void *Dynarr_new(type)
|
|
|
56 [MACRO] Create a new dynamic-array object, with each element of the
|
|
|
57 specified type. The return value is cast to (type##_dynarr).
|
|
|
58 This requires following the convention that types are declared in
|
|
|
59 such a way that this type concatenation works. In particular, TYPE
|
|
|
60 must be a symbol, not an arbitrary C type.
|
|
|
61
|
|
|
62 Dynarr_add(d, el)
|
|
|
63 [MACRO] Add an element to the end of a dynamic array. EL is a pointer
|
|
|
64 to the element; the element itself is stored in the array, however.
|
|
|
65 No function call is performed unless the array needs to be resized.
|
|
|
66
|
|
|
67 Dynarr_add_many(d, base, len)
|
|
|
68 [MACRO] Add LEN elements to the end of the dynamic array. The elements
|
|
771
|
69 should be contiguous in memory, starting at BASE. If BASE if NULL,
|
|
|
70 just make space for the elements; don't actually add them.
|
|
428
|
71
|
|
|
72 Dynarr_insert_many_at_start(d, base, len)
|
|
|
73 [MACRO] Append LEN elements to the beginning of the dynamic array.
|
|
|
74 The elements should be contiguous in memory, starting at BASE.
|
|
771
|
75 If BASE if NULL, just make space for the elements; don't actually
|
|
|
76 add them.
|
|
428
|
77
|
|
|
78 Dynarr_insert_many(d, base, len, start)
|
|
|
79 Insert LEN elements to the dynamic array starting at position
|
|
|
80 START. The elements should be contiguous in memory, starting at BASE.
|
|
771
|
81 If BASE if NULL, just make space for the elements; don't actually
|
|
|
82 add them.
|
|
|
83
|
|
|
84 Dynarr_delete(d, i)
|
|
|
85 [MACRO] Delete an element from the dynamic array at position I.
|
|
|
86
|
|
|
87 Dynarr_delete_many(d, start, len)
|
|
|
88 Delete LEN elements from the dynamic array starting at position
|
|
|
89 START.
|
|
|
90
|
|
|
91 Dynarr_delete_by_pointer(d, p)
|
|
|
92 [MACRO] Delete an element from the dynamic array at pointer P,
|
|
|
93 which must point within the block of memory that stores the data.
|
|
|
94 P should be obtained using Dynarr_atp().
|
|
428
|
95
|
|
|
96 int Dynarr_length(d)
|
|
|
97 [MACRO] Return the number of elements currently in a dynamic array.
|
|
|
98
|
|
|
99 int Dynarr_largest(d)
|
|
|
100 [MACRO] Return the maximum value that Dynarr_length(d) would
|
|
|
101 ever have returned.
|
|
|
102
|
|
|
103 type Dynarr_at(d, i)
|
|
|
104 [MACRO] Return the element at the specified index (no bounds checking
|
|
|
105 done on the index). The element itself is returned, not a pointer
|
|
|
106 to it.
|
|
|
107
|
|
|
108 type *Dynarr_atp(d, i)
|
|
|
109 [MACRO] Return a pointer to the element at the specified index (no
|
|
|
110 bounds checking done on the index). The pointer may not be valid
|
|
|
111 after an element is added to or removed from the array.
|
|
|
112
|
|
|
113 Dynarr_reset(d)
|
|
|
114 [MACRO] Reset the length of a dynamic array to 0.
|
|
|
115
|
|
|
116 Dynarr_free(d)
|
|
|
117 Destroy a dynamic array and the memory allocated to it.
|
|
|
118
|
|
|
119 Use the following global variable:
|
|
|
120
|
|
|
121 Dynarr_min_size
|
|
440
|
122 Minimum allowable size for a dynamic array when it is resized.
|
|
428
|
123
|
|
|
124 */
|
|
|
125
|
|
|
126 #include <config.h>
|
|
|
127 #include "lisp.h"
|
|
|
128
|
|
440
|
129 static int Dynarr_min_size = 8;
|
|
428
|
130
|
|
|
131 static void
|
|
3210
|
132 Dynarr_realloc (Dynarr *dy, int new_size)
|
|
428
|
133 {
|
|
|
134 if (DUMPEDP (dy->base))
|
|
|
135 {
|
|
3293
|
136 void *new_base = malloc (new_size * dy->elsize);
|
|
3210
|
137 memcpy (new_base, dy->base,
|
|
|
138 (dy->max < new_size ? dy->max : new_size) * dy->elsize);
|
|
428
|
139 dy->base = new_base;
|
|
|
140 }
|
|
|
141 else
|
|
3210
|
142 dy->base = xrealloc (dy->base, new_size * dy->elsize);
|
|
428
|
143 }
|
|
|
144
|
|
|
145 void *
|
|
|
146 Dynarr_newf (int elsize)
|
|
|
147 {
|
|
|
148 Dynarr *d = xnew_and_zero (Dynarr);
|
|
|
149 d->elsize = elsize;
|
|
|
150
|
|
|
151 return d;
|
|
|
152 }
|
|
|
153
|
|
3092
|
154 #ifdef NEW_GC
|
|
|
155 DEFINE_LRECORD_IMPLEMENTATION ("dynarr", dynarr,
|
|
|
156 1, /*dumpable-flag*/
|
|
|
157 0, 0, 0, 0, 0,
|
|
|
158 0,
|
|
|
159 Dynarr);
|
|
|
160
|
|
|
161 static void
|
|
3210
|
162 Dynarr_lisp_realloc (Dynarr *dy, int new_size)
|
|
3092
|
163 {
|
|
|
164 void *new_base = alloc_lrecord_array (dy->elsize, new_size, dy->lisp_imp);
|
|
|
165 void *old_base = dy->base;
|
|
|
166 if (dy->base)
|
|
|
167 memcpy (new_base, dy->base,
|
|
3210
|
168 (dy->max < new_size ? dy->max : new_size) * dy->elsize);
|
|
3092
|
169 dy->base = new_base;
|
|
|
170 if (old_base)
|
|
|
171 mc_free (old_base);
|
|
|
172 }
|
|
|
173
|
|
|
174 void *
|
|
|
175 Dynarr_lisp_newf (int elsize,
|
|
|
176 const struct lrecord_implementation *dynarr_imp,
|
|
|
177 const struct lrecord_implementation *imp)
|
|
|
178 {
|
|
|
179 Dynarr *d = (Dynarr *) alloc_lrecord (sizeof (Dynarr), dynarr_imp);
|
|
|
180 d->elsize = elsize;
|
|
|
181 d->lisp_imp = imp;
|
|
|
182
|
|
|
183 return d;
|
|
|
184 }
|
|
|
185 #endif /* not NEW_GC */
|
|
|
186
|
|
428
|
187 void
|
|
2367
|
188 Dynarr_resize (void *d, Elemcount size)
|
|
428
|
189 {
|
|
|
190 int newsize;
|
|
|
191 double multiplier;
|
|
1318
|
192 Dynarr *dy = (Dynarr *) Dynarr_verify (d);
|
|
428
|
193
|
|
|
194 if (dy->max <= 8)
|
|
|
195 multiplier = 2;
|
|
|
196 else
|
|
|
197 multiplier = 1.5;
|
|
|
198
|
|
|
199 for (newsize = dy->max; newsize < size;)
|
|
|
200 newsize = max (Dynarr_min_size, (int) (multiplier * newsize));
|
|
|
201
|
|
|
202 /* Don't do anything if the array is already big enough. */
|
|
|
203 if (newsize > dy->max)
|
|
|
204 {
|
|
3092
|
205 #ifdef NEW_GC
|
|
|
206 if (dy->lisp_imp)
|
|
|
207 Dynarr_lisp_realloc (dy, newsize);
|
|
|
208 else
|
|
3210
|
209 Dynarr_realloc (dy, newsize);
|
|
3092
|
210 #else /* not NEW_GC */
|
|
3210
|
211 Dynarr_realloc (dy, newsize);
|
|
3092
|
212 #endif /* not NEW_GC */
|
|
428
|
213 dy->max = newsize;
|
|
|
214 }
|
|
|
215 }
|
|
|
216
|
|
|
217 /* Add a number of contiguous elements to the array starting at START. */
|
|
|
218 void
|
|
442
|
219 Dynarr_insert_many (void *d, const void *el, int len, int start)
|
|
428
|
220 {
|
|
793
|
221 Dynarr *dy = (Dynarr *) Dynarr_verify (d);
|
|
|
222
|
|
428
|
223 Dynarr_resize (dy, dy->cur+len);
|
|
1318
|
224 #if 0
|
|
|
225 /* WTF? We should be catching these problems. */
|
|
428
|
226 /* Silently adjust start to be valid. */
|
|
|
227 if (start > dy->cur)
|
|
|
228 start = dy->cur;
|
|
|
229 else if (start < 0)
|
|
|
230 start = 0;
|
|
1318
|
231 #else
|
|
|
232 assert (start >= 0 && start <= dy->cur);
|
|
|
233 #endif
|
|
428
|
234
|
|
|
235 if (start != dy->cur)
|
|
|
236 {
|
|
|
237 memmove ((char *) dy->base + (start + len)*dy->elsize,
|
|
|
238 (char *) dy->base + start*dy->elsize,
|
|
|
239 (dy->cur - start)*dy->elsize);
|
|
|
240 }
|
|
771
|
241 if (el)
|
|
|
242 memcpy ((char *) dy->base + start*dy->elsize, el, len*dy->elsize);
|
|
428
|
243 dy->cur += len;
|
|
|
244
|
|
|
245 if (dy->cur > dy->largest)
|
|
|
246 dy->largest = dy->cur;
|
|
|
247 }
|
|
|
248
|
|
|
249 void
|
|
|
250 Dynarr_delete_many (void *d, int start, int len)
|
|
|
251 {
|
|
1318
|
252 Dynarr *dy = (Dynarr *) Dynarr_verify (d);
|
|
428
|
253
|
|
|
254 assert (start >= 0 && len >= 0 && start + len <= dy->cur);
|
|
|
255 memmove ((char *) dy->base + start*dy->elsize,
|
|
|
256 (char *) dy->base + (start + len)*dy->elsize,
|
|
|
257 (dy->cur - start - len)*dy->elsize);
|
|
|
258 dy->cur -= len;
|
|
|
259 }
|
|
|
260
|
|
|
261 void
|
|
|
262 Dynarr_free (void *d)
|
|
|
263 {
|
|
|
264 Dynarr *dy = (Dynarr *) d;
|
|
|
265
|
|
3092
|
266 #ifdef NEW_GC
|
|
|
267 if (dy->base && !DUMPEDP (dy->base))
|
|
|
268 {
|
|
|
269 if (dy->lisp_imp)
|
|
|
270 mc_free (dy->base);
|
|
|
271 else
|
|
|
272 xfree (dy->base, void *);
|
|
|
273 }
|
|
|
274 if(!DUMPEDP (dy))
|
|
|
275 {
|
|
|
276 if (dy->lisp_imp)
|
|
|
277 mc_free (dy);
|
|
|
278 else
|
|
|
279 xfree (dy, Dynarr *);
|
|
|
280 }
|
|
|
281 #else /* not NEW_GC */
|
|
428
|
282 if (dy->base && !DUMPEDP (dy->base))
|
|
1726
|
283 xfree (dy->base, void *);
|
|
428
|
284 if(!DUMPEDP (dy))
|
|
1726
|
285 xfree (dy, Dynarr *);
|
|
3092
|
286 #endif /* not NEW_GC */
|
|
428
|
287 }
|
|
|
288
|
|
|
289 #ifdef MEMORY_USAGE_STATS
|
|
|
290
|
|
|
291 /* Return memory usage for Dynarr D. The returned value is the total
|
|
|
292 amount of bytes actually being used for the Dynarr, including all
|
|
|
293 overhead. The extra amount of space in the Dynarr that is
|
|
|
294 allocated beyond what was requested is returned in DYNARR_OVERHEAD
|
|
|
295 in STATS. The extra amount of space that malloc() allocates beyond
|
|
|
296 what was requested of it is returned in MALLOC_OVERHEAD in STATS.
|
|
|
297 See the comment above the definition of this structure. */
|
|
|
298
|
|
665
|
299 Bytecount
|
|
428
|
300 Dynarr_memory_usage (void *d, struct overhead_stats *stats)
|
|
|
301 {
|
|
665
|
302 Bytecount total = 0;
|
|
428
|
303 Dynarr *dy = (Dynarr *) d;
|
|
|
304
|
|
|
305 /* We have to be a bit tricky here because not all of the
|
|
|
306 memory that malloc() will claim as "requested" was actually
|
|
|
307 requested. */
|
|
|
308
|
|
|
309 if (dy->base)
|
|
|
310 {
|
|
665
|
311 Bytecount malloc_used = malloced_storage_size (dy->base,
|
|
1318
|
312 dy->elsize * dy->max, 0);
|
|
428
|
313 /* #### This may or may not be correct. Some Dynarrs would
|
|
|
314 prefer that we use dy->cur instead of dy->largest here. */
|
|
1318
|
315 Bytecount was_requested = dy->elsize * dy->largest;
|
|
|
316 Bytecount dynarr_overhead = dy->elsize * (dy->max - dy->largest);
|
|
428
|
317
|
|
|
318 total += malloc_used;
|
|
|
319 stats->was_requested += was_requested;
|
|
|
320 stats->dynarr_overhead += dynarr_overhead;
|
|
|
321 /* And the remainder must be malloc overhead. */
|
|
|
322 stats->malloc_overhead +=
|
|
|
323 malloc_used - was_requested - dynarr_overhead;
|
|
|
324 }
|
|
|
325
|
|
|
326 total += malloced_storage_size (d, sizeof (*dy), stats);
|
|
|
327
|
|
|
328 return total;
|
|
|
329 }
|
|
|
330
|
|
|
331 #endif /* MEMORY_USAGE_STATS */
|
|
2367
|
332
|
|
|
333 /* Version of malloc() that will be extremely efficient when allocation
|
|
|
334 nearly always occurs in LIFO (stack) order.
|
|
|
335
|
|
|
336 #### Perhaps shouldn't be in this file, but where else? */
|
|
|
337
|
|
|
338 typedef struct
|
|
|
339 {
|
|
|
340 Dynarr_declare (char_dynarr *);
|
|
|
341 } char_dynarr_dynarr;
|
|
|
342
|
|
|
343 char_dynarr_dynarr *stack_like_free_list;
|
|
|
344 char_dynarr_dynarr *stack_like_in_use_list;
|
|
|
345
|
|
|
346 void *
|
|
|
347 stack_like_malloc (Bytecount size)
|
|
|
348 {
|
|
|
349 char_dynarr *this_one;
|
|
|
350 if (!stack_like_free_list)
|
|
|
351 {
|
|
|
352 stack_like_free_list = Dynarr_new2 (char_dynarr_dynarr,
|
|
|
353 char_dynarr *);
|
|
|
354 stack_like_in_use_list = Dynarr_new2 (char_dynarr_dynarr,
|
|
|
355 char_dynarr *);
|
|
|
356 }
|
|
|
357
|
|
|
358 if (Dynarr_length (stack_like_free_list) > 0)
|
|
|
359 this_one = Dynarr_pop (stack_like_free_list);
|
|
|
360 else
|
|
|
361 this_one = Dynarr_new (char);
|
|
|
362 Dynarr_add (stack_like_in_use_list, this_one);
|
|
|
363 Dynarr_resize (this_one, size);
|
|
|
364 return Dynarr_atp (this_one, 0);
|
|
|
365 }
|
|
|
366
|
|
|
367 void
|
|
|
368 stack_like_free (void *val)
|
|
|
369 {
|
|
|
370 int len = Dynarr_length (stack_like_in_use_list);
|
|
|
371 assert (len > 0);
|
|
|
372 /* The vast majority of times, we will be called in a last-in first-out
|
|
|
373 order, and the item at the end of the list will be the one we're
|
|
|
374 looking for, so just check for this first and avoid any function
|
|
|
375 calls. */
|
|
|
376 if (Dynarr_atp (Dynarr_at (stack_like_in_use_list, len - 1), 0) == val)
|
|
|
377 {
|
|
|
378 char_dynarr *this_one = Dynarr_pop (stack_like_in_use_list);
|
|
|
379 Dynarr_add (stack_like_free_list, this_one);
|
|
|
380 }
|
|
|
381 else
|
|
|
382 {
|
|
|
383 /* Find the item and delete it. */
|
|
|
384 int i;
|
|
|
385 assert (len >= 2);
|
|
|
386 for (i = len - 2; i >= 0; i--)
|
|
|
387 if (Dynarr_atp (Dynarr_at (stack_like_in_use_list, i), 0) ==
|
|
|
388 val)
|
|
|
389 {
|
|
|
390 char_dynarr *this_one = Dynarr_at (stack_like_in_use_list, i);
|
|
|
391 Dynarr_add (stack_like_free_list, this_one);
|
|
|
392 Dynarr_delete (stack_like_in_use_list, i);
|
|
|
393 return;
|
|
|
394 }
|
|
|
395
|
|
2500
|
396 ABORT ();
|
|
2367
|
397 }
|
|
|
398 }
|
