Mercurial > hg > xemacs-beta
annotate src/dynarr.c @ 5166:b50624d3ae55
open-database.message
| author | Aidan Kehoe <kehoea@parhasard.net> |
|---|---|
| date | Fri, 26 Mar 2010 15:06:28 +0000 |
| parents | 1fae11d56ad2 |
| children |
| rev | line source |
|---|---|
| 1318 | 1 /* Support for dynamic arrays. |
| 428 | 2 Copyright (C) 1993 Sun Microsystems, Inc. |
|
4952
19a72041c5ed
Mule-izing, various fixes related to char * arguments
Ben Wing <ben@xemacs.org>
parents:
4844
diff
changeset
|
3 Copyright (C) 2002, 2003, 2004, 2005, 2010 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 | |
| 5038 | 28 A "dynamic array" or "dynarr" is a contiguous array of fixed-size elements |
| 29 where there is no upper limit (except available memory) on the number of | |
| 30 elements in the array. Because the elements are maintained contiguously, | |
| 31 space is used efficiently (no per-element pointers necessary) and random | |
| 32 access to a particular element is in constant time. At any one point, the | |
| 33 block of memory that holds the array has an upper limit; if this limit is | |
| 34 exceeded, the memory is realloc()ed into a new array that is twice as big. | |
| 35 Assuming that the time to grow the array is on the order of the new size of | |
| 36 the array block, this scheme has a provably constant amortized time | |
| 37 \(i.e. average time over all additions). | |
| 428 | 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 | |
| 5038 | 55 |
| 56 ************* Dynarr creation ************* | |
| 57 | |
| 428 | 58 void *Dynarr_new(type) |
| 59 [MACRO] Create a new dynamic-array object, with each element of the | |
| 60 specified type. The return value is cast to (type##_dynarr). | |
| 61 This requires following the convention that types are declared in | |
| 62 such a way that this type concatenation works. In particular, TYPE | |
| 5038 | 63 must be a symbol, not an arbitrary C type. To make dynarrs of |
| 64 complex types, a typedef must be declared, e.g. | |
| 65 | |
| 66 typedef unsigned char *unsigned_char_ptr; | |
| 67 | |
| 68 and then you can say | |
| 69 | |
| 70 unsigned_char_ptr_dynarr *dyn = Dynarr_new (unsigned_char_ptr); | |
| 71 | |
| 72 void *Dynarr_new2(dynarr_type, type) | |
| 73 [MACRO] Create a new dynamic-array object, with each element of the | |
| 74 specified type. The array itself is of type DYNARR_TYPE. This makes | |
| 75 it possible to create dynarrs over complex types without the need | |
| 76 to create typedefs, as described above. Use is as follows: | |
| 77 | |
| 78 ucharptr_dynarr *dyn = Dynarr_new2 (ucharptr_dynarr *, unsigned char *); | |
| 79 | |
| 80 Dynarr_free(d) | |
| 81 Destroy a dynamic array and the memory allocated to it. | |
| 82 | |
| 83 ************* Dynarr access ************* | |
| 84 | |
| 85 type Dynarr_at(d, i) | |
| 86 [MACRO] Return the element at the specified index. The index must be | |
| 87 between 0 and Dynarr_largest(d), inclusive. With error-checking | |
| 88 enabled, bounds checking on the index is in the form of asserts() -- | |
| 89 an out-of-bounds index causes an abort. The element itself is | |
| 90 returned, not a pointer to it. | |
| 91 | |
| 92 type *Dynarr_atp(d, i) | |
| 93 [MACRO] Return a pointer to the element at the specified index. | |
| 94 Restrictions and bounds checking on the index is as for Dynarr_at. | |
| 95 The pointer may not be valid after an element is added to or | |
| 96 (conceivably) removed from the array, because this may trigger a | |
| 97 realloc() performed on the underlying dynarr storage, which may | |
| 98 involve moving the entire underlying storage to a new location in | |
| 99 memory. | |
| 100 | |
| 101 type *Dynarr_begin(d) | |
| 102 [MACRO] Return a pointer to the first element in the dynarr. See | |
| 103 Dynarr_atp() for warnings about when the pointer might become invalid. | |
| 104 | |
| 105 type *Dynarr_lastp(d) | |
| 106 [MACRO] Return a pointer to the last element in the dynarr. See | |
| 107 Dynarr_atp() for warnings about when the pointer might become invalid. | |
| 108 | |
| 109 type *Dynarr_past_lastp(d) | |
| 110 [MACRO] Return a pointer to the beginning of the element just past the | |
| 111 last one. WARNING: This may not point to valid memory; however, the | |
| 112 byte directly before will be pointer will be valid memory. This macro | |
| 113 might be useful for various reasons, e.g. as a stopping point in a loop | |
| 114 (although Dynarr_lastp() could be used just as well) or as a place to | |
| 115 start writing elements if Dynarr_length() < Dynarr_largest(). | |
| 116 | |
| 117 ************* Dynarr length/size retrieval and setting ************* | |
| 118 | |
| 119 int Dynarr_length(d) | |
| 120 [MACRO] Return the number of elements currently in a dynamic array. | |
| 121 | |
| 122 int Dynarr_largest(d) | |
| 123 [MACRO] Return the maximum value that Dynarr_length(d) would | |
| 124 ever have returned. This is used esp. in the redisplay code, | |
| 125 which reuses dynarrs for performance reasons. | |
| 126 | |
| 127 int Dynarr_max(d) | |
| 128 [MACRO] Return the maximum number of elements that can fit in the | |
| 129 dynarr before it needs to be resized. | |
| 130 | |
| 131 Note that Dynarr_length(d) <= Dynarr_largest(d) <= Dynarr_max(d). | |
| 132 | |
| 133 Bytecount Dynarr_sizeof(d) | |
| 134 [MACRO] Return the total size of the elements currently in dynarr | |
| 135 D. This | |
| 136 | |
| 137 Dynarr_set_lengthr(d, len) | |
| 138 [MACRO] Set the length of D to LEN, which must be between 0 and | |
| 139 Dynarr_largest(d), inclusive. With error-checking enabled, an | |
| 140 assertion failure will result from trying to set the length | |
| 141 to less than zero or greater than Dynarr_largest(d). The | |
| 142 restriction to Dynarr_largest() is to ensure that | |
| 143 | |
| 144 Dynarr_set_length(d, len) | |
| 145 [MACRO] Set the length of D to LEN, resizing the dynarr as | |
| 146 necessary to make sure enough space is available. there are no | |
| 147 restrictions on LEN other than available memory and that it must | |
| 148 be at least 0. Note that | |
| 149 | |
| 150 Dynarr_set_length_and_zero(d, len) | |
| 151 [MACRO] Like Dynarr_set_length(d, len) but also, if increasing | |
| 152 the length, zero out the memory between the old and new lengths, | |
| 153 i.e. starting just past the previous last element and up through | |
| 154 the new last element. | |
| 155 | |
| 156 Dynarr_incrementr(d) | |
| 157 [MACRO] Increments the length of D by 1. Equivalent to | |
| 158 Dynarr_set_lengthr(d, Dynarr_length(d) + 1). | |
| 159 | |
| 160 Dynarr_increment(d) | |
| 161 [MACRO] Increments the length of D by 1. Equivalent to | |
| 162 Dynarr_set_length(d, Dynarr_length(d) + 1). | |
| 163 | |
| 164 Dynarr_reset(d) | |
| 165 [MACRO] Reset the length of a dynamic array to 0. | |
| 166 | |
| 167 Dynarr_resize(d, maxval) | |
| 168 Resize the internal dynarr storage to so that it can hold at least | |
| 169 MAXVAL elements. Resizing is done using a geometric series | |
| 170 (repeatedly multiply the old maximum by a constant, normally 1.5, | |
| 171 till a large enough size is reached), so this will be efficient | |
| 172 even if resizing larger by one element at a time. This is mostly | |
| 173 an internal function. | |
| 174 | |
| 175 | |
| 176 | |
| 177 ************* Adding/deleting elements to/from a dynarr ************* | |
| 428 | 178 |
| 179 Dynarr_add(d, el) | |
| 180 [MACRO] Add an element to the end of a dynamic array. EL is a pointer | |
| 181 to the element; the element itself is stored in the array, however. | |
| 182 No function call is performed unless the array needs to be resized. | |
| 183 | |
| 184 Dynarr_add_many(d, base, len) | |
| 185 [MACRO] Add LEN elements to the end of the dynamic array. The elements | |
| 771 | 186 should be contiguous in memory, starting at BASE. If BASE if NULL, |
| 187 just make space for the elements; don't actually add them. | |
| 428 | 188 |
| 5038 | 189 Dynarr_prepend_many(d, base, len) |
| 190 [MACRO] Prepend LEN elements to the beginning of the dynamic array. | |
| 428 | 191 The elements should be contiguous in memory, starting at BASE. |
| 771 | 192 If BASE if NULL, just make space for the elements; don't actually |
| 193 add them. | |
| 428 | 194 |
| 5038 | 195 Dynarr_insert_many(d, base, len, pos) |
| 428 | 196 Insert LEN elements to the dynamic array starting at position |
| 5038 | 197 POS. The elements should be contiguous in memory, starting at BASE. |
| 771 | 198 If BASE if NULL, just make space for the elements; don't actually |
| 199 add them. | |
| 200 | |
| 5038 | 201 type Dynarr_pop(d) |
| 202 [MACRO] Pop the last element off the dynarr and return it. | |
| 203 | |
| 771 | 204 Dynarr_delete(d, i) |
| 205 [MACRO] Delete an element from the dynamic array at position I. | |
| 206 | |
| 5038 | 207 Dynarr_delete_many(d, pos, len) |
| 771 | 208 Delete LEN elements from the dynamic array starting at position |
| 5038 | 209 POS. |
| 210 | |
| 211 Dynarr_zero_many(d, pos, len) | |
| 212 Zero out LEN elements in the dynarr D starting at position POS. | |
| 771 | 213 |
| 214 Dynarr_delete_by_pointer(d, p) | |
| 215 [MACRO] Delete an element from the dynamic array at pointer P, | |
| 216 which must point within the block of memory that stores the data. | |
| 217 P should be obtained using Dynarr_atp(). | |
| 428 | 218 |
| 5038 | 219 ************* Dynarr locking ************* |
| 428 | 220 |
| 5038 | 221 Dynarr_lock(d) |
| 222 Lock the dynarr against further locking or writing. With error-checking | |
| 223 enabled, any attempts to write into a locked dynarr or re-lock an | |
| 224 already locked one will cause an assertion failure and abort. | |
| 428 | 225 |
| 5038 | 226 Dynarr_unlock(d) |
| 227 Unlock a locked dynarr, allowing writing into it. | |
| 428 | 228 |
| 5038 | 229 ************* Dynarr global variables ************* |
| 428 | 230 |
| 231 Dynarr_min_size | |
| 440 | 232 Minimum allowable size for a dynamic array when it is resized. |
| 428 | 233 |
| 234 */ | |
| 235 | |
| 236 #include <config.h> | |
| 237 #include "lisp.h" | |
| 238 | |
|
4952
19a72041c5ed
Mule-izing, various fixes related to char * arguments
Ben Wing <ben@xemacs.org>
parents:
4844
diff
changeset
|
239 static const struct memory_description const_Ascbyte_ptr_description_1[] = { |
|
19a72041c5ed
Mule-izing, various fixes related to char * arguments
Ben Wing <ben@xemacs.org>
parents:
4844
diff
changeset
|
240 { XD_ASCII_STRING, 0 }, |
|
19a72041c5ed
Mule-izing, various fixes related to char * arguments
Ben Wing <ben@xemacs.org>
parents:
4844
diff
changeset
|
241 { XD_END } |
|
19a72041c5ed
Mule-izing, various fixes related to char * arguments
Ben Wing <ben@xemacs.org>
parents:
4844
diff
changeset
|
242 }; |
|
19a72041c5ed
Mule-izing, various fixes related to char * arguments
Ben Wing <ben@xemacs.org>
parents:
4844
diff
changeset
|
243 |
|
19a72041c5ed
Mule-izing, various fixes related to char * arguments
Ben Wing <ben@xemacs.org>
parents:
4844
diff
changeset
|
244 const struct sized_memory_description const_Ascbyte_ptr_description = { |
|
19a72041c5ed
Mule-izing, various fixes related to char * arguments
Ben Wing <ben@xemacs.org>
parents:
4844
diff
changeset
|
245 sizeof (const Ascbyte *), |
|
19a72041c5ed
Mule-izing, various fixes related to char * arguments
Ben Wing <ben@xemacs.org>
parents:
4844
diff
changeset
|
246 const_Ascbyte_ptr_description_1 |
|
19a72041c5ed
Mule-izing, various fixes related to char * arguments
Ben Wing <ben@xemacs.org>
parents:
4844
diff
changeset
|
247 }; |
|
19a72041c5ed
Mule-izing, various fixes related to char * arguments
Ben Wing <ben@xemacs.org>
parents:
4844
diff
changeset
|
248 |
|
19a72041c5ed
Mule-izing, various fixes related to char * arguments
Ben Wing <ben@xemacs.org>
parents:
4844
diff
changeset
|
249 static const struct memory_description const_Ascbyte_ptr_dynarr_description_1[] = { |
|
19a72041c5ed
Mule-izing, various fixes related to char * arguments
Ben Wing <ben@xemacs.org>
parents:
4844
diff
changeset
|
250 XD_DYNARR_DESC (const_Ascbyte_ptr_dynarr, &const_Ascbyte_ptr_description), |
|
19a72041c5ed
Mule-izing, various fixes related to char * arguments
Ben Wing <ben@xemacs.org>
parents:
4844
diff
changeset
|
251 { XD_END } |
|
19a72041c5ed
Mule-izing, various fixes related to char * arguments
Ben Wing <ben@xemacs.org>
parents:
4844
diff
changeset
|
252 }; |
|
19a72041c5ed
Mule-izing, various fixes related to char * arguments
Ben Wing <ben@xemacs.org>
parents:
4844
diff
changeset
|
253 |
|
19a72041c5ed
Mule-izing, various fixes related to char * arguments
Ben Wing <ben@xemacs.org>
parents:
4844
diff
changeset
|
254 const struct sized_memory_description const_Ascbyte_ptr_dynarr_description = { |
|
19a72041c5ed
Mule-izing, various fixes related to char * arguments
Ben Wing <ben@xemacs.org>
parents:
4844
diff
changeset
|
255 sizeof (const_Ascbyte_ptr_dynarr), |
|
19a72041c5ed
Mule-izing, various fixes related to char * arguments
Ben Wing <ben@xemacs.org>
parents:
4844
diff
changeset
|
256 const_Ascbyte_ptr_dynarr_description_1 |
|
19a72041c5ed
Mule-izing, various fixes related to char * arguments
Ben Wing <ben@xemacs.org>
parents:
4844
diff
changeset
|
257 }; |
|
19a72041c5ed
Mule-izing, various fixes related to char * arguments
Ben Wing <ben@xemacs.org>
parents:
4844
diff
changeset
|
258 |
|
19a72041c5ed
Mule-izing, various fixes related to char * arguments
Ben Wing <ben@xemacs.org>
parents:
4844
diff
changeset
|
259 |
| 5038 | 260 static Elemcount Dynarr_min_size = 8; |
| 428 | 261 |
| 262 static void | |
| 5038 | 263 Dynarr_realloc (Dynarr *dy, Elemcount new_size) |
| 428 | 264 { |
| 265 if (DUMPEDP (dy->base)) | |
| 266 { | |
| 5038 | 267 void *new_base = malloc (new_size * Dynarr_elsize (dy)); |
| 3210 | 268 memcpy (new_base, dy->base, |
| 4967 | 269 (Dynarr_max (dy) < new_size ? Dynarr_max (dy) : new_size) * |
| 5038 | 270 Dynarr_elsize (dy)); |
| 428 | 271 dy->base = new_base; |
| 272 } | |
| 273 else | |
| 5038 | 274 dy->base = xrealloc (dy->base, new_size * Dynarr_elsize (dy)); |
| 428 | 275 } |
| 276 | |
| 277 void * | |
| 5038 | 278 Dynarr_newf (Bytecount elsize) |
| 428 | 279 { |
| 280 Dynarr *d = xnew_and_zero (Dynarr); | |
| 5038 | 281 d->elsize_ = elsize; |
| 428 | 282 |
| 283 return d; | |
| 284 } | |
| 285 | |
| 3092 | 286 #ifdef NEW_GC |
|
5118
e0db3c197671
merge up to latest default branch, doesn't compile yet
Ben Wing <ben@xemacs.org>
parents:
4117
diff
changeset
|
287 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
|
288 0, 0, |
|
e0db3c197671
merge up to latest default branch, doesn't compile yet
Ben Wing <ben@xemacs.org>
parents:
4117
diff
changeset
|
289 Dynarr); |
| 3092 | 290 |
| 291 static void | |
| 5038 | 292 Dynarr_lisp_realloc (Dynarr *dy, Elemcount new_size) |
| 3092 | 293 { |
|
5118
e0db3c197671
merge up to latest default branch, doesn't compile yet
Ben Wing <ben@xemacs.org>
parents:
4117
diff
changeset
|
294 void *new_base = |
| 5126 | 295 XPNTR (alloc_sized_lrecord_array (Dynarr_elsize (dy), new_size, |
| 296 dy->lisp_imp)); | |
| 3092 | 297 if (dy->base) |
| 298 memcpy (new_base, dy->base, | |
| 4967 | 299 (Dynarr_max (dy) < new_size ? Dynarr_max (dy) : new_size) * |
| 5038 | 300 Dynarr_elsize (dy)); |
| 3092 | 301 dy->base = new_base; |
| 302 } | |
| 303 | |
| 304 void * | |
| 5038 | 305 Dynarr_lisp_newf (Bytecount elsize, |
| 3092 | 306 const struct lrecord_implementation *dynarr_imp, |
| 307 const struct lrecord_implementation *imp) | |
| 308 { | |
|
5120
d1247f3cc363
latest work on lisp-object workspace;
Ben Wing <ben@xemacs.org>
parents:
5118
diff
changeset
|
309 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
|
310 dynarr_imp)); |
| 5038 | 311 d->elsize_ = elsize; |
| 3092 | 312 d->lisp_imp = imp; |
| 313 | |
| 314 return d; | |
| 315 } | |
| 316 #endif /* not NEW_GC */ | |
| 317 | |
| 428 | 318 void |
| 2367 | 319 Dynarr_resize (void *d, Elemcount size) |
| 428 | 320 { |
| 5038 | 321 Elemcount newsize; |
| 428 | 322 double multiplier; |
| 1318 | 323 Dynarr *dy = (Dynarr *) Dynarr_verify (d); |
| 428 | 324 |
| 4967 | 325 if (Dynarr_max (dy) <= 8) |
| 428 | 326 multiplier = 2; |
| 327 else | |
| 328 multiplier = 1.5; | |
| 329 | |
| 4967 | 330 for (newsize = Dynarr_max (dy); newsize < size;) |
| 5038 | 331 newsize = max (Dynarr_min_size, (Elemcount) (multiplier * newsize)); |
| 428 | 332 |
| 333 /* Don't do anything if the array is already big enough. */ | |
| 4967 | 334 if (newsize > Dynarr_max (dy)) |
| 428 | 335 { |
| 3092 | 336 #ifdef NEW_GC |
| 337 if (dy->lisp_imp) | |
| 338 Dynarr_lisp_realloc (dy, newsize); | |
| 339 else | |
| 3210 | 340 Dynarr_realloc (dy, newsize); |
| 3092 | 341 #else /* not NEW_GC */ |
| 3210 | 342 Dynarr_realloc (dy, newsize); |
| 3092 | 343 #endif /* not NEW_GC */ |
| 4967 | 344 dy->max_ = newsize; |
| 428 | 345 } |
| 346 } | |
| 347 | |
| 5038 | 348 /* Add a number of contiguous elements to the array starting at POS. */ |
| 349 | |
| 428 | 350 void |
| 5038 | 351 Dynarr_insert_many (void *d, const void *base, Elemcount len, Elemcount pos) |
| 428 | 352 { |
| 4967 | 353 Dynarr *dy = Dynarr_verify_mod (d); |
| 5038 | 354 Elemcount old_len = Dynarr_length (dy); |
| 4967 | 355 |
|
4844
91b3d00e717f
Various cleanups for Dynarr code, from Unicode-internal ws
Ben Wing <ben@xemacs.org>
parents:
4117
diff
changeset
|
356 /* #### 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
|
357 between len and largest. */ |
| 5038 | 358 dynarr_checking_assert (pos >= 0 && pos <= old_len); |
| 359 dynarr_checking_assert (len >= 0); | |
| 360 Dynarr_increase_length (dy, old_len + len); | |
| 428 | 361 |
| 5038 | 362 if (pos != old_len) |
| 428 | 363 { |
| 5038 | 364 memmove ((Rawbyte *) dy->base + (pos + len)*Dynarr_elsize (dy), |
| 365 (Rawbyte *) dy->base + pos*Dynarr_elsize (dy), | |
| 366 (old_len - pos)*Dynarr_elsize (dy)); | |
| 428 | 367 } |
| 4967 | 368 /* Some functions call us with a value of 0 to mean "reserve space but |
| 369 don't write into it" */ | |
| 5038 | 370 if (base) |
| 371 memcpy ((Rawbyte *) dy->base + pos*Dynarr_elsize (dy), base, | |
| 372 len*Dynarr_elsize (dy)); | |
| 428 | 373 } |
| 374 | |
| 375 void | |
| 5038 | 376 Dynarr_delete_many (void *d, Elemcount pos, Elemcount len) |
| 428 | 377 { |
| 4967 | 378 Dynarr *dy = Dynarr_verify_mod (d); |
| 428 | 379 |
| 5038 | 380 dynarr_checking_assert (pos >= 0 && len >= 0 && |
| 381 pos + len <= Dynarr_length (dy)); | |
| 4967 | 382 |
| 5038 | 383 memmove ((Rawbyte *) dy->base + pos*Dynarr_elsize (dy), |
| 384 (Rawbyte *) dy->base + (pos + len)*Dynarr_elsize (dy), | |
| 385 (Dynarr_length (dy) - pos - len)*Dynarr_elsize (dy)); | |
| 4967 | 386 |
| 387 Dynarr_set_length_1 (dy, Dynarr_length (dy) - len); | |
| 428 | 388 } |
| 389 | |
| 390 void | |
| 391 Dynarr_free (void *d) | |
| 392 { | |
| 393 Dynarr *dy = (Dynarr *) d; | |
| 394 | |
| 3092 | 395 #ifdef NEW_GC |
| 396 if (dy->base && !DUMPEDP (dy->base)) | |
| 397 { | |
| 4117 | 398 if (!dy->lisp_imp) |
|
4976
16112448d484
Rename xfree(FOO, TYPE) -> xfree(FOO)
Ben Wing <ben@xemacs.org>
parents:
4967
diff
changeset
|
399 xfree (dy->base); |
| 3092 | 400 } |
| 401 if(!DUMPEDP (dy)) | |
| 402 { | |
| 4117 | 403 if (!dy->lisp_imp) |
|
4976
16112448d484
Rename xfree(FOO, TYPE) -> xfree(FOO)
Ben Wing <ben@xemacs.org>
parents:
4967
diff
changeset
|
404 xfree (dy); |
| 3092 | 405 } |
| 406 #else /* not NEW_GC */ | |
| 428 | 407 if (dy->base && !DUMPEDP (dy->base)) |
|
4976
16112448d484
Rename xfree(FOO, TYPE) -> xfree(FOO)
Ben Wing <ben@xemacs.org>
parents:
4967
diff
changeset
|
408 xfree (dy->base); |
| 428 | 409 if(!DUMPEDP (dy)) |
|
4976
16112448d484
Rename xfree(FOO, TYPE) -> xfree(FOO)
Ben Wing <ben@xemacs.org>
parents:
4967
diff
changeset
|
410 xfree (dy); |
| 3092 | 411 #endif /* not NEW_GC */ |
| 428 | 412 } |
| 413 | |
| 414 #ifdef MEMORY_USAGE_STATS | |
| 415 | |
| 5038 | 416 /* Return memory usage for dynarr D. The returned value is the total |
| 417 amount of bytes actually being used for the dynarr, including all | |
| 418 overhead. The extra amount of space in the dynarr that is | |
| 428 | 419 allocated beyond what was requested is returned in DYNARR_OVERHEAD |
| 420 in STATS. The extra amount of space that malloc() allocates beyond | |
| 421 what was requested of it is returned in MALLOC_OVERHEAD in STATS. | |
| 422 See the comment above the definition of this structure. */ | |
| 423 | |
| 665 | 424 Bytecount |
|
5157
1fae11d56ad2
redo memory-usage mechanism, add way of dynamically initializing Lisp objects
Ben Wing <ben@xemacs.org>
parents:
5126
diff
changeset
|
425 Dynarr_memory_usage (void *d, struct usage_stats *stats) |
| 428 | 426 { |
| 665 | 427 Bytecount total = 0; |
| 428 | 428 Dynarr *dy = (Dynarr *) d; |
| 429 | |
| 430 /* We have to be a bit tricky here because not all of the | |
| 431 memory that malloc() will claim as "requested" was actually | |
| 432 requested. */ | |
| 433 | |
| 434 if (dy->base) | |
| 435 { | |
| 4967 | 436 Bytecount malloc_used = |
| 5038 | 437 malloced_storage_size (dy->base, Dynarr_elsize (dy) * Dynarr_max (dy), |
| 438 0); | |
| 439 /* #### 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
|
440 prefer that we use dy->len instead of dy->largest here. */ |
| 5038 | 441 Bytecount was_requested = Dynarr_elsize (dy) * Dynarr_largest (dy); |
| 4967 | 442 Bytecount dynarr_overhead = |
| 5038 | 443 Dynarr_elsize (dy) * (Dynarr_max (dy) - Dynarr_largest (dy)); |
| 428 | 444 |
| 445 total += malloc_used; | |
| 446 stats->was_requested += was_requested; | |
| 447 stats->dynarr_overhead += dynarr_overhead; | |
| 448 /* And the remainder must be malloc overhead. */ | |
| 449 stats->malloc_overhead += | |
| 450 malloc_used - was_requested - dynarr_overhead; | |
| 451 } | |
| 452 | |
| 453 total += malloced_storage_size (d, sizeof (*dy), stats); | |
| 454 | |
| 455 return total; | |
| 456 } | |
| 457 | |
| 458 #endif /* MEMORY_USAGE_STATS */ | |
| 2367 | 459 |
| 460 /* Version of malloc() that will be extremely efficient when allocation | |
| 461 nearly always occurs in LIFO (stack) order. | |
| 462 | |
| 463 #### Perhaps shouldn't be in this file, but where else? */ | |
| 464 | |
| 465 typedef struct | |
| 466 { | |
| 467 Dynarr_declare (char_dynarr *); | |
| 468 } char_dynarr_dynarr; | |
| 469 | |
| 470 char_dynarr_dynarr *stack_like_free_list; | |
| 471 char_dynarr_dynarr *stack_like_in_use_list; | |
| 472 | |
| 473 void * | |
| 474 stack_like_malloc (Bytecount size) | |
| 475 { | |
| 476 char_dynarr *this_one; | |
| 477 if (!stack_like_free_list) | |
| 478 { | |
| 479 stack_like_free_list = Dynarr_new2 (char_dynarr_dynarr, | |
| 480 char_dynarr *); | |
| 481 stack_like_in_use_list = Dynarr_new2 (char_dynarr_dynarr, | |
| 482 char_dynarr *); | |
| 483 } | |
| 484 | |
| 485 if (Dynarr_length (stack_like_free_list) > 0) | |
| 486 this_one = Dynarr_pop (stack_like_free_list); | |
| 487 else | |
| 488 this_one = Dynarr_new (char); | |
| 489 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
|
490 Dynarr_reset (this_one); |
|
91b3d00e717f
Various cleanups for Dynarr code, from Unicode-internal ws
Ben Wing <ben@xemacs.org>
parents:
4117
diff
changeset
|
491 Dynarr_add_many (this_one, 0, size); |
| 4967 | 492 return Dynarr_begin (this_one); |
| 2367 | 493 } |
| 494 | |
| 495 void | |
| 496 stack_like_free (void *val) | |
| 497 { | |
| 5038 | 498 Elemcount len = Dynarr_length (stack_like_in_use_list); |
| 2367 | 499 assert (len > 0); |
| 500 /* The vast majority of times, we will be called in a last-in first-out | |
| 501 order, and the item at the end of the list will be the one we're | |
| 502 looking for, so just check for this first and avoid any function | |
| 503 calls. */ | |
| 4967 | 504 if (Dynarr_begin (Dynarr_at (stack_like_in_use_list, len - 1)) == val) |
| 2367 | 505 { |
| 506 char_dynarr *this_one = Dynarr_pop (stack_like_in_use_list); | |
| 507 Dynarr_add (stack_like_free_list, this_one); | |
| 508 } | |
| 509 else | |
| 510 { | |
| 511 /* Find the item and delete it. */ | |
| 512 int i; | |
| 513 assert (len >= 2); | |
| 514 for (i = len - 2; i >= 0; i--) | |
| 4967 | 515 if (Dynarr_begin (Dynarr_at (stack_like_in_use_list, i)) == |
| 2367 | 516 val) |
| 517 { | |
| 518 char_dynarr *this_one = Dynarr_at (stack_like_in_use_list, i); | |
| 519 Dynarr_add (stack_like_free_list, this_one); | |
| 520 Dynarr_delete (stack_like_in_use_list, i); | |
| 521 return; | |
| 522 } | |
| 523 | |
| 2500 | 524 ABORT (); |
| 2367 | 525 } |
| 526 } |