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 }
