Mercurial > hg > xemacs-beta
annotate src/dynarr.c @ 5120:d1247f3cc363 ben-lisp-object
latest work on lisp-object workspace;
more changes eliminating LCRECORD in place of LISP_OBJECT;
now compiles and runs.
| author | Ben Wing <ben@xemacs.org> |
|---|---|
| date | Mon, 28 Dec 2009 01:15:52 -0600 |
| parents | e0db3c197671 |
| children | b5df3737028a |
| rev | line source |
|---|---|
| 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 * | |
|
5118
e0db3c197671
merge up to latest default branch, doesn't compile yet
Ben Wing <ben@xemacs.org>
parents:
4117
diff
changeset
|
146 Dynarr_newf (Bytecount elsize) |
| 428 | 147 { |
| 148 Dynarr *d = xnew_and_zero (Dynarr); | |
| 149 d->elsize = elsize; | |
| 150 | |
| 151 return d; | |
| 152 } | |
| 153 | |
| 3092 | 154 #ifdef NEW_GC |
|
5118
e0db3c197671
merge up to latest default branch, doesn't compile yet
Ben Wing <ben@xemacs.org>
parents:
4117
diff
changeset
|
155 DEFINE_DUMPABLE_INTERNAL_LISP_OBJECT ("dynarr", dynarr, |
|
e0db3c197671
merge up to latest default branch, doesn't compile yet
Ben Wing <ben@xemacs.org>
parents:
4117
diff
changeset
|
156 0, 0, |
|
e0db3c197671
merge up to latest default branch, doesn't compile yet
Ben Wing <ben@xemacs.org>
parents:
4117
diff
changeset
|
157 Dynarr); |
| 3092 | 158 |
| 159 static void | |
|
5118
e0db3c197671
merge up to latest default branch, doesn't compile yet
Ben Wing <ben@xemacs.org>
parents:
4117
diff
changeset
|
160 Dynarr_lisp_realloc (Dynarr *dy, Elemcount new_size) |
| 3092 | 161 { |
|
5118
e0db3c197671
merge up to latest default branch, doesn't compile yet
Ben Wing <ben@xemacs.org>
parents:
4117
diff
changeset
|
162 void *new_base = |
|
e0db3c197671
merge up to latest default branch, doesn't compile yet
Ben Wing <ben@xemacs.org>
parents:
4117
diff
changeset
|
163 XPNTR (alloc_sized_lrecord_array (dy->elsize, new_size, dy->lisp_imp)); |
| 3092 | 164 if (dy->base) |
| 165 memcpy (new_base, dy->base, | |
| 3210 | 166 (dy->max < new_size ? dy->max : new_size) * dy->elsize); |
| 3092 | 167 dy->base = new_base; |
| 168 } | |
| 169 | |
| 170 void * | |
|
5118
e0db3c197671
merge up to latest default branch, doesn't compile yet
Ben Wing <ben@xemacs.org>
parents:
4117
diff
changeset
|
171 Dynarr_lisp_newf (Bytecount elsize, |
| 3092 | 172 const struct lrecord_implementation *dynarr_imp, |
| 173 const struct lrecord_implementation *imp) | |
| 174 { | |
|
5120
d1247f3cc363
latest work on lisp-object workspace;
Ben Wing <ben@xemacs.org>
parents:
5118
diff
changeset
|
175 Dynarr *d = (Dynarr *) XPNTR (alloc_sized_lrecord (sizeof (Dynarr), |
|
d1247f3cc363
latest work on lisp-object workspace;
Ben Wing <ben@xemacs.org>
parents:
5118
diff
changeset
|
176 dynarr_imp)); |
| 3092 | 177 d->elsize = elsize; |
| 178 d->lisp_imp = imp; | |
| 179 | |
| 180 return d; | |
| 181 } | |
| 182 #endif /* not NEW_GC */ | |
| 183 | |
| 428 | 184 void |
| 2367 | 185 Dynarr_resize (void *d, Elemcount size) |
| 428 | 186 { |
| 187 int newsize; | |
| 188 double multiplier; | |
| 1318 | 189 Dynarr *dy = (Dynarr *) Dynarr_verify (d); |
| 428 | 190 |
| 191 if (dy->max <= 8) | |
| 192 multiplier = 2; | |
| 193 else | |
| 194 multiplier = 1.5; | |
| 195 | |
| 196 for (newsize = dy->max; newsize < size;) | |
| 197 newsize = max (Dynarr_min_size, (int) (multiplier * newsize)); | |
| 198 | |
| 199 /* Don't do anything if the array is already big enough. */ | |
| 200 if (newsize > dy->max) | |
| 201 { | |
| 3092 | 202 #ifdef NEW_GC |
| 203 if (dy->lisp_imp) | |
| 204 Dynarr_lisp_realloc (dy, newsize); | |
| 205 else | |
| 3210 | 206 Dynarr_realloc (dy, newsize); |
| 3092 | 207 #else /* not NEW_GC */ |
| 3210 | 208 Dynarr_realloc (dy, newsize); |
| 3092 | 209 #endif /* not NEW_GC */ |
| 428 | 210 dy->max = newsize; |
| 211 } | |
| 212 } | |
| 213 | |
| 214 /* Add a number of contiguous elements to the array starting at START. */ | |
| 215 void | |
| 442 | 216 Dynarr_insert_many (void *d, const void *el, int len, int start) |
| 428 | 217 { |
| 793 | 218 Dynarr *dy = (Dynarr *) Dynarr_verify (d); |
| 219 | |
| 428 | 220 Dynarr_resize (dy, dy->cur+len); |
| 1318 | 221 #if 0 |
| 222 /* WTF? We should be catching these problems. */ | |
| 428 | 223 /* Silently adjust start to be valid. */ |
| 224 if (start > dy->cur) | |
| 225 start = dy->cur; | |
| 226 else if (start < 0) | |
| 227 start = 0; | |
| 1318 | 228 #else |
| 229 assert (start >= 0 && start <= dy->cur); | |
| 230 #endif | |
| 428 | 231 |
| 232 if (start != dy->cur) | |
| 233 { | |
| 234 memmove ((char *) dy->base + (start + len)*dy->elsize, | |
| 235 (char *) dy->base + start*dy->elsize, | |
| 236 (dy->cur - start)*dy->elsize); | |
| 237 } | |
| 771 | 238 if (el) |
| 239 memcpy ((char *) dy->base + start*dy->elsize, el, len*dy->elsize); | |
| 428 | 240 dy->cur += len; |
| 241 | |
| 242 if (dy->cur > dy->largest) | |
| 243 dy->largest = dy->cur; | |
| 244 } | |
| 245 | |
| 246 void | |
| 247 Dynarr_delete_many (void *d, int start, int len) | |
| 248 { | |
| 1318 | 249 Dynarr *dy = (Dynarr *) Dynarr_verify (d); |
| 428 | 250 |
| 251 assert (start >= 0 && len >= 0 && start + len <= dy->cur); | |
| 252 memmove ((char *) dy->base + start*dy->elsize, | |
| 253 (char *) dy->base + (start + len)*dy->elsize, | |
| 254 (dy->cur - start - len)*dy->elsize); | |
| 255 dy->cur -= len; | |
| 256 } | |
| 257 | |
| 258 void | |
| 259 Dynarr_free (void *d) | |
| 260 { | |
| 261 Dynarr *dy = (Dynarr *) d; | |
| 262 | |
| 3092 | 263 #ifdef NEW_GC |
| 264 if (dy->base && !DUMPEDP (dy->base)) | |
| 265 { | |
| 4117 | 266 if (!dy->lisp_imp) |
| 3092 | 267 xfree (dy->base, void *); |
| 268 } | |
| 269 if(!DUMPEDP (dy)) | |
| 270 { | |
| 4117 | 271 if (!dy->lisp_imp) |
| 3092 | 272 xfree (dy, Dynarr *); |
| 273 } | |
| 274 #else /* not NEW_GC */ | |
| 428 | 275 if (dy->base && !DUMPEDP (dy->base)) |
| 1726 | 276 xfree (dy->base, void *); |
| 428 | 277 if(!DUMPEDP (dy)) |
| 1726 | 278 xfree (dy, Dynarr *); |
| 3092 | 279 #endif /* not NEW_GC */ |
| 428 | 280 } |
| 281 | |
| 282 #ifdef MEMORY_USAGE_STATS | |
| 283 | |
| 284 /* Return memory usage for Dynarr D. The returned value is the total | |
| 285 amount of bytes actually being used for the Dynarr, including all | |
| 286 overhead. The extra amount of space in the Dynarr that is | |
| 287 allocated beyond what was requested is returned in DYNARR_OVERHEAD | |
| 288 in STATS. The extra amount of space that malloc() allocates beyond | |
| 289 what was requested of it is returned in MALLOC_OVERHEAD in STATS. | |
| 290 See the comment above the definition of this structure. */ | |
| 291 | |
| 665 | 292 Bytecount |
| 428 | 293 Dynarr_memory_usage (void *d, struct overhead_stats *stats) |
| 294 { | |
| 665 | 295 Bytecount total = 0; |
| 428 | 296 Dynarr *dy = (Dynarr *) d; |
| 297 | |
| 298 /* We have to be a bit tricky here because not all of the | |
| 299 memory that malloc() will claim as "requested" was actually | |
| 300 requested. */ | |
| 301 | |
| 302 if (dy->base) | |
| 303 { | |
| 665 | 304 Bytecount malloc_used = malloced_storage_size (dy->base, |
| 1318 | 305 dy->elsize * dy->max, 0); |
| 428 | 306 /* #### This may or may not be correct. Some Dynarrs would |
| 307 prefer that we use dy->cur instead of dy->largest here. */ | |
| 1318 | 308 Bytecount was_requested = dy->elsize * dy->largest; |
| 309 Bytecount dynarr_overhead = dy->elsize * (dy->max - dy->largest); | |
| 428 | 310 |
| 311 total += malloc_used; | |
| 312 stats->was_requested += was_requested; | |
| 313 stats->dynarr_overhead += dynarr_overhead; | |
| 314 /* And the remainder must be malloc overhead. */ | |
| 315 stats->malloc_overhead += | |
| 316 malloc_used - was_requested - dynarr_overhead; | |
| 317 } | |
| 318 | |
| 319 total += malloced_storage_size (d, sizeof (*dy), stats); | |
| 320 | |
| 321 return total; | |
| 322 } | |
| 323 | |
| 324 #endif /* MEMORY_USAGE_STATS */ | |
| 2367 | 325 |
| 326 /* Version of malloc() that will be extremely efficient when allocation | |
| 327 nearly always occurs in LIFO (stack) order. | |
| 328 | |
| 329 #### Perhaps shouldn't be in this file, but where else? */ | |
| 330 | |
| 331 typedef struct | |
| 332 { | |
| 333 Dynarr_declare (char_dynarr *); | |
| 334 } char_dynarr_dynarr; | |
| 335 | |
| 336 char_dynarr_dynarr *stack_like_free_list; | |
| 337 char_dynarr_dynarr *stack_like_in_use_list; | |
| 338 | |
| 339 void * | |
| 340 stack_like_malloc (Bytecount size) | |
| 341 { | |
| 342 char_dynarr *this_one; | |
| 343 if (!stack_like_free_list) | |
| 344 { | |
| 345 stack_like_free_list = Dynarr_new2 (char_dynarr_dynarr, | |
| 346 char_dynarr *); | |
| 347 stack_like_in_use_list = Dynarr_new2 (char_dynarr_dynarr, | |
| 348 char_dynarr *); | |
| 349 } | |
| 350 | |
| 351 if (Dynarr_length (stack_like_free_list) > 0) | |
| 352 this_one = Dynarr_pop (stack_like_free_list); | |
| 353 else | |
| 354 this_one = Dynarr_new (char); | |
| 355 Dynarr_add (stack_like_in_use_list, this_one); | |
| 356 Dynarr_resize (this_one, size); | |
| 357 return Dynarr_atp (this_one, 0); | |
| 358 } | |
| 359 | |
| 360 void | |
| 361 stack_like_free (void *val) | |
| 362 { | |
| 363 int len = Dynarr_length (stack_like_in_use_list); | |
| 364 assert (len > 0); | |
| 365 /* The vast majority of times, we will be called in a last-in first-out | |
| 366 order, and the item at the end of the list will be the one we're | |
| 367 looking for, so just check for this first and avoid any function | |
| 368 calls. */ | |
| 369 if (Dynarr_atp (Dynarr_at (stack_like_in_use_list, len - 1), 0) == val) | |
| 370 { | |
| 371 char_dynarr *this_one = Dynarr_pop (stack_like_in_use_list); | |
| 372 Dynarr_add (stack_like_free_list, this_one); | |
| 373 } | |
| 374 else | |
| 375 { | |
| 376 /* Find the item and delete it. */ | |
| 377 int i; | |
| 378 assert (len >= 2); | |
| 379 for (i = len - 2; i >= 0; i--) | |
| 380 if (Dynarr_atp (Dynarr_at (stack_like_in_use_list, i), 0) == | |
| 381 val) | |
| 382 { | |
| 383 char_dynarr *this_one = Dynarr_at (stack_like_in_use_list, i); | |
| 384 Dynarr_add (stack_like_free_list, this_one); | |
| 385 Dynarr_delete (stack_like_in_use_list, i); | |
| 386 return; | |
| 387 } | |
| 388 | |
| 2500 | 389 ABORT (); |
| 2367 | 390 } |
| 391 } |