Mercurial > hg > xemacs-beta
annotate src/dynarr.c @ 4844:91b3d00e717f
Various cleanups for Dynarr code, from Unicode-internal ws
dynarr.c: Add comment explaining Dynarr_largest() use.
dynarr.c: In Dynarr_insert_many(), don't call Dynarr_resize() unless we
actually need to resize, and note that an assert() that we are
inserting at or below the current end could be wrong if code
wants to access stuff between `len' and `largest'.
dynarr.c: Don't just Dynarr_resize() to the right size; instead use
Dynarr_reset() then Dynarr_add_many(), so that the 'len' and
'largest' and such get set properly.
dynarr.c, faces.c, gutter.c, lisp.h, lread.c, lrecord.h, redisplay-output.c, redisplay.c: Rename Dynarr member 'cur' to 'len' since it's the length of
the dynarr, not really a pointer to a "current insertion point".
Use type_checking_assert() instead of just assert() in some places.
Add additional assertions (Dynarr_verify*()) to check that we're
being given positions within range. Use them in Dynarr_at,
Dynarr_atp, etc. New Dynarr_atp_allow_end() for retrieving a
pointer to a position that might be the element past the last one.
New Dynarr_past_lastp() to retrieve a pointer to the position
past the last one, using Dynarr_atp_allow_end(). Change code
appropriately to use it.
Rename Dynarr_end() to Dynarr_lastp() (pointer to the last
element) for clarity, and change code appropriately to use it.
Change code appropriately to use Dynarr_begin().
Rewrite Dynarr_add_many(). New version can accept a NULL pointer
to mean "reserve space but don't put anything in it". Used by
stack_like_malloc().
author | Ben Wing <ben@xemacs.org> |
---|---|
date | Wed, 13 Jan 2010 04:07:42 -0600 |
parents | 229bd619740a |
children | 19a72041c5ed |
rev | line source |
---|---|
1318 | 1 /* Support for dynamic arrays. |
428 | 2 Copyright (C) 1993 Sun Microsystems, Inc. |
4844
91b3d00e717f
Various cleanups for Dynarr code, from Unicode-internal ws
Ben Wing <ben@xemacs.org>
parents:
4117
diff
changeset
|
3 Copyright (C) 2002, 2003, 2004, 2005 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 | |
4844
91b3d00e717f
Various cleanups for Dynarr code, from Unicode-internal ws
Ben Wing <ben@xemacs.org>
parents:
4117
diff
changeset
|
101 ever have returned. This is used esp. in the redisplay code, |
91b3d00e717f
Various cleanups for Dynarr code, from Unicode-internal ws
Ben Wing <ben@xemacs.org>
parents:
4117
diff
changeset
|
102 which reuses dynarrs for performance reasons. |
428 | 103 |
104 type Dynarr_at(d, i) | |
105 [MACRO] Return the element at the specified index (no bounds checking | |
106 done on the index). The element itself is returned, not a pointer | |
107 to it. | |
108 | |
109 type *Dynarr_atp(d, i) | |
110 [MACRO] Return a pointer to the element at the specified index (no | |
111 bounds checking done on the index). The pointer may not be valid | |
112 after an element is added to or removed from the array. | |
113 | |
114 Dynarr_reset(d) | |
115 [MACRO] Reset the length of a dynamic array to 0. | |
116 | |
117 Dynarr_free(d) | |
118 Destroy a dynamic array and the memory allocated to it. | |
119 | |
120 Use the following global variable: | |
121 | |
122 Dynarr_min_size | |
440 | 123 Minimum allowable size for a dynamic array when it is resized. |
428 | 124 |
125 */ | |
126 | |
127 #include <config.h> | |
128 #include "lisp.h" | |
129 | |
440 | 130 static int Dynarr_min_size = 8; |
428 | 131 |
132 static void | |
3210 | 133 Dynarr_realloc (Dynarr *dy, int new_size) |
428 | 134 { |
135 if (DUMPEDP (dy->base)) | |
136 { | |
3293 | 137 void *new_base = malloc (new_size * dy->elsize); |
3210 | 138 memcpy (new_base, dy->base, |
139 (dy->max < new_size ? dy->max : new_size) * dy->elsize); | |
428 | 140 dy->base = new_base; |
141 } | |
142 else | |
3210 | 143 dy->base = xrealloc (dy->base, new_size * dy->elsize); |
428 | 144 } |
145 | |
146 void * | |
147 Dynarr_newf (int elsize) | |
148 { | |
149 Dynarr *d = xnew_and_zero (Dynarr); | |
150 d->elsize = elsize; | |
151 | |
152 return d; | |
153 } | |
154 | |
3092 | 155 #ifdef NEW_GC |
156 DEFINE_LRECORD_IMPLEMENTATION ("dynarr", dynarr, | |
157 1, /*dumpable-flag*/ | |
158 0, 0, 0, 0, 0, | |
159 0, | |
160 Dynarr); | |
161 | |
162 static void | |
3210 | 163 Dynarr_lisp_realloc (Dynarr *dy, int new_size) |
3092 | 164 { |
165 void *new_base = alloc_lrecord_array (dy->elsize, new_size, dy->lisp_imp); | |
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 } | |
171 | |
172 void * | |
173 Dynarr_lisp_newf (int elsize, | |
174 const struct lrecord_implementation *dynarr_imp, | |
175 const struct lrecord_implementation *imp) | |
176 { | |
177 Dynarr *d = (Dynarr *) alloc_lrecord (sizeof (Dynarr), dynarr_imp); | |
178 d->elsize = elsize; | |
179 d->lisp_imp = imp; | |
180 | |
181 return d; | |
182 } | |
183 #endif /* not NEW_GC */ | |
184 | |
428 | 185 void |
2367 | 186 Dynarr_resize (void *d, Elemcount size) |
428 | 187 { |
188 int newsize; | |
189 double multiplier; | |
1318 | 190 Dynarr *dy = (Dynarr *) Dynarr_verify (d); |
428 | 191 |
192 if (dy->max <= 8) | |
193 multiplier = 2; | |
194 else | |
195 multiplier = 1.5; | |
196 | |
197 for (newsize = dy->max; newsize < size;) | |
198 newsize = max (Dynarr_min_size, (int) (multiplier * newsize)); | |
199 | |
200 /* Don't do anything if the array is already big enough. */ | |
201 if (newsize > dy->max) | |
202 { | |
3092 | 203 #ifdef NEW_GC |
204 if (dy->lisp_imp) | |
205 Dynarr_lisp_realloc (dy, newsize); | |
206 else | |
3210 | 207 Dynarr_realloc (dy, newsize); |
3092 | 208 #else /* not NEW_GC */ |
3210 | 209 Dynarr_realloc (dy, newsize); |
3092 | 210 #endif /* not NEW_GC */ |
428 | 211 dy->max = newsize; |
212 } | |
213 } | |
214 | |
215 /* Add a number of contiguous elements to the array starting at START. */ | |
216 void | |
442 | 217 Dynarr_insert_many (void *d, const void *el, int len, int start) |
428 | 218 { |
793 | 219 Dynarr *dy = (Dynarr *) Dynarr_verify (d); |
220 | |
4844
91b3d00e717f
Various cleanups for Dynarr code, from Unicode-internal ws
Ben Wing <ben@xemacs.org>
parents:
4117
diff
changeset
|
221 if (dy->len + len > dy->max) |
91b3d00e717f
Various cleanups for Dynarr code, from Unicode-internal ws
Ben Wing <ben@xemacs.org>
parents:
4117
diff
changeset
|
222 Dynarr_resize (dy, dy->len + len); |
1318 | 223 #if 0 |
224 /* WTF? We should be catching these problems. */ | |
428 | 225 /* Silently adjust start to be valid. */ |
4844
91b3d00e717f
Various cleanups for Dynarr code, from Unicode-internal ws
Ben Wing <ben@xemacs.org>
parents:
4117
diff
changeset
|
226 if (start > dy->len) |
91b3d00e717f
Various cleanups for Dynarr code, from Unicode-internal ws
Ben Wing <ben@xemacs.org>
parents:
4117
diff
changeset
|
227 start = dy->len; |
428 | 228 else if (start < 0) |
229 start = 0; | |
1318 | 230 #else |
4844
91b3d00e717f
Various cleanups for Dynarr code, from Unicode-internal ws
Ben Wing <ben@xemacs.org>
parents:
4117
diff
changeset
|
231 /* #### This could conceivably be wrong, if code wants to access stuff |
91b3d00e717f
Various cleanups for Dynarr code, from Unicode-internal ws
Ben Wing <ben@xemacs.org>
parents:
4117
diff
changeset
|
232 between len and largest. */ |
91b3d00e717f
Various cleanups for Dynarr code, from Unicode-internal ws
Ben Wing <ben@xemacs.org>
parents:
4117
diff
changeset
|
233 type_checking_assert (start >= 0 && start <= dy->len); |
1318 | 234 #endif |
428 | 235 |
4844
91b3d00e717f
Various cleanups for Dynarr code, from Unicode-internal ws
Ben Wing <ben@xemacs.org>
parents:
4117
diff
changeset
|
236 if (start != dy->len) |
428 | 237 { |
238 memmove ((char *) dy->base + (start + len)*dy->elsize, | |
239 (char *) dy->base + start*dy->elsize, | |
4844
91b3d00e717f
Various cleanups for Dynarr code, from Unicode-internal ws
Ben Wing <ben@xemacs.org>
parents:
4117
diff
changeset
|
240 (dy->len - start)*dy->elsize); |
428 | 241 } |
771 | 242 if (el) |
243 memcpy ((char *) dy->base + start*dy->elsize, el, len*dy->elsize); | |
4844
91b3d00e717f
Various cleanups for Dynarr code, from Unicode-internal ws
Ben Wing <ben@xemacs.org>
parents:
4117
diff
changeset
|
244 dy->len += len; |
428 | 245 |
4844
91b3d00e717f
Various cleanups for Dynarr code, from Unicode-internal ws
Ben Wing <ben@xemacs.org>
parents:
4117
diff
changeset
|
246 if (dy->len > dy->largest) |
91b3d00e717f
Various cleanups for Dynarr code, from Unicode-internal ws
Ben Wing <ben@xemacs.org>
parents:
4117
diff
changeset
|
247 dy->largest = dy->len; |
428 | 248 } |
249 | |
250 void | |
251 Dynarr_delete_many (void *d, int start, int len) | |
252 { | |
1318 | 253 Dynarr *dy = (Dynarr *) Dynarr_verify (d); |
428 | 254 |
4844
91b3d00e717f
Various cleanups for Dynarr code, from Unicode-internal ws
Ben Wing <ben@xemacs.org>
parents:
4117
diff
changeset
|
255 type_checking_assert (start >= 0 && len >= 0 && start + len <= dy->len); |
428 | 256 memmove ((char *) dy->base + start*dy->elsize, |
257 (char *) dy->base + (start + len)*dy->elsize, | |
4844
91b3d00e717f
Various cleanups for Dynarr code, from Unicode-internal ws
Ben Wing <ben@xemacs.org>
parents:
4117
diff
changeset
|
258 (dy->len - start - len)*dy->elsize); |
91b3d00e717f
Various cleanups for Dynarr code, from Unicode-internal ws
Ben Wing <ben@xemacs.org>
parents:
4117
diff
changeset
|
259 dy->len -= len; |
428 | 260 } |
261 | |
262 void | |
263 Dynarr_free (void *d) | |
264 { | |
265 Dynarr *dy = (Dynarr *) d; | |
266 | |
3092 | 267 #ifdef NEW_GC |
268 if (dy->base && !DUMPEDP (dy->base)) | |
269 { | |
4117 | 270 if (!dy->lisp_imp) |
3092 | 271 xfree (dy->base, void *); |
272 } | |
273 if(!DUMPEDP (dy)) | |
274 { | |
4117 | 275 if (!dy->lisp_imp) |
3092 | 276 xfree (dy, Dynarr *); |
277 } | |
278 #else /* not NEW_GC */ | |
428 | 279 if (dy->base && !DUMPEDP (dy->base)) |
1726 | 280 xfree (dy->base, void *); |
428 | 281 if(!DUMPEDP (dy)) |
1726 | 282 xfree (dy, Dynarr *); |
3092 | 283 #endif /* not NEW_GC */ |
428 | 284 } |
285 | |
286 #ifdef MEMORY_USAGE_STATS | |
287 | |
288 /* Return memory usage for Dynarr D. The returned value is the total | |
289 amount of bytes actually being used for the Dynarr, including all | |
290 overhead. The extra amount of space in the Dynarr that is | |
291 allocated beyond what was requested is returned in DYNARR_OVERHEAD | |
292 in STATS. The extra amount of space that malloc() allocates beyond | |
293 what was requested of it is returned in MALLOC_OVERHEAD in STATS. | |
294 See the comment above the definition of this structure. */ | |
295 | |
665 | 296 Bytecount |
428 | 297 Dynarr_memory_usage (void *d, struct overhead_stats *stats) |
298 { | |
665 | 299 Bytecount total = 0; |
428 | 300 Dynarr *dy = (Dynarr *) d; |
301 | |
302 /* We have to be a bit tricky here because not all of the | |
303 memory that malloc() will claim as "requested" was actually | |
304 requested. */ | |
305 | |
306 if (dy->base) | |
307 { | |
665 | 308 Bytecount malloc_used = malloced_storage_size (dy->base, |
1318 | 309 dy->elsize * dy->max, 0); |
428 | 310 /* #### This may or may not be correct. Some Dynarrs would |
4844
91b3d00e717f
Various cleanups for Dynarr code, from Unicode-internal ws
Ben Wing <ben@xemacs.org>
parents:
4117
diff
changeset
|
311 prefer that we use dy->len instead of dy->largest here. */ |
1318 | 312 Bytecount was_requested = dy->elsize * dy->largest; |
313 Bytecount dynarr_overhead = dy->elsize * (dy->max - dy->largest); | |
428 | 314 |
315 total += malloc_used; | |
316 stats->was_requested += was_requested; | |
317 stats->dynarr_overhead += dynarr_overhead; | |
318 /* And the remainder must be malloc overhead. */ | |
319 stats->malloc_overhead += | |
320 malloc_used - was_requested - dynarr_overhead; | |
321 } | |
322 | |
323 total += malloced_storage_size (d, sizeof (*dy), stats); | |
324 | |
325 return total; | |
326 } | |
327 | |
328 #endif /* MEMORY_USAGE_STATS */ | |
2367 | 329 |
330 /* Version of malloc() that will be extremely efficient when allocation | |
331 nearly always occurs in LIFO (stack) order. | |
332 | |
333 #### Perhaps shouldn't be in this file, but where else? */ | |
334 | |
335 typedef struct | |
336 { | |
337 Dynarr_declare (char_dynarr *); | |
338 } char_dynarr_dynarr; | |
339 | |
340 char_dynarr_dynarr *stack_like_free_list; | |
341 char_dynarr_dynarr *stack_like_in_use_list; | |
342 | |
343 void * | |
344 stack_like_malloc (Bytecount size) | |
345 { | |
346 char_dynarr *this_one; | |
347 if (!stack_like_free_list) | |
348 { | |
349 stack_like_free_list = Dynarr_new2 (char_dynarr_dynarr, | |
350 char_dynarr *); | |
351 stack_like_in_use_list = Dynarr_new2 (char_dynarr_dynarr, | |
352 char_dynarr *); | |
353 } | |
354 | |
355 if (Dynarr_length (stack_like_free_list) > 0) | |
356 this_one = Dynarr_pop (stack_like_free_list); | |
357 else | |
358 this_one = Dynarr_new (char); | |
359 Dynarr_add (stack_like_in_use_list, this_one); | |
4844
91b3d00e717f
Various cleanups for Dynarr code, from Unicode-internal ws
Ben Wing <ben@xemacs.org>
parents:
4117
diff
changeset
|
360 Dynarr_reset (this_one); |
91b3d00e717f
Various cleanups for Dynarr code, from Unicode-internal ws
Ben Wing <ben@xemacs.org>
parents:
4117
diff
changeset
|
361 Dynarr_add_many (this_one, 0, size); |
2367 | 362 return Dynarr_atp (this_one, 0); |
363 } | |
364 | |
365 void | |
366 stack_like_free (void *val) | |
367 { | |
368 int len = Dynarr_length (stack_like_in_use_list); | |
369 assert (len > 0); | |
370 /* The vast majority of times, we will be called in a last-in first-out | |
371 order, and the item at the end of the list will be the one we're | |
372 looking for, so just check for this first and avoid any function | |
373 calls. */ | |
374 if (Dynarr_atp (Dynarr_at (stack_like_in_use_list, len - 1), 0) == val) | |
375 { | |
376 char_dynarr *this_one = Dynarr_pop (stack_like_in_use_list); | |
377 Dynarr_add (stack_like_free_list, this_one); | |
378 } | |
379 else | |
380 { | |
381 /* Find the item and delete it. */ | |
382 int i; | |
383 assert (len >= 2); | |
384 for (i = len - 2; i >= 0; i--) | |
385 if (Dynarr_atp (Dynarr_at (stack_like_in_use_list, i), 0) == | |
386 val) | |
387 { | |
388 char_dynarr *this_one = Dynarr_at (stack_like_in_use_list, i); | |
389 Dynarr_add (stack_like_free_list, this_one); | |
390 Dynarr_delete (stack_like_in_use_list, i); | |
391 return; | |
392 } | |
393 | |
2500 | 394 ABORT (); |
2367 | 395 } |
396 } |