Mercurial > hg > xemacs-beta

comparison src/array.c @ 5168:cf900a2f1fa3

Find changesets by keywords (author, files, the commit message), revision number or hash, or revset expression.
extract gap array from extents.c, use in range tables -------------------- ChangeLog entries follow: -------------------- src/ChangeLog addition: 2010-03-22 Ben Wing <ben@xemacs.org> * Makefile.in.in (objs): * array.c: * array.c (gap_array_adjust_markers): * array.c (gap_array_move_gap): * array.c (gap_array_make_gap): * array.c (gap_array_insert_els): * array.c (gap_array_delete_els): * array.c (gap_array_make_marker): * array.c (gap_array_delete_marker): * array.c (gap_array_delete_all_markers): * array.c (gap_array_clone): * array.h: * depend: * emacs.c (main_1): * extents.c: * extents.c (EXTENT_GAP_ARRAY_AT): * extents.c (extent_list_num_els): * extents.c (extent_list_locate): * extents.c (extent_list_at): * extents.c (extent_list_delete_all): * extents.c (allocate_extent_list): * extents.c (syms_of_extents): * extents.h: * extents.h (XEXTENT_LIST_MARKER): * lisp.h: * rangetab.c: * rangetab.c (mark_range_table): * rangetab.c (print_range_table): * rangetab.c (range_table_equal): * rangetab.c (range_table_hash): * rangetab.c (verify_range_table): * rangetab.c (get_range_table_pos): * rangetab.c (Fmake_range_table): * rangetab.c (Fcopy_range_table): * rangetab.c (Fget_range_table): * rangetab.c (put_range_table): * rangetab.c (Fclear_range_table): * rangetab.c (Fmap_range_table): * rangetab.c (unified_range_table_bytes_needed): * rangetab.c (unified_range_table_copy_data): * rangetab.c (unified_range_table_lookup): * rangetab.h: * rangetab.h (struct range_table_entry): * rangetab.h (struct Lisp_Range_Table): * rangetab.h (rangetab_gap_array_at): * symsinit.h: Rename dynarr.c to array.c. Move gap array from extents.c to array.c. Extract dynarr, gap array and stack-like malloc into new file array.h. Rename GAP_ARRAY_NUM_ELS -> gap_array_length(). Add gap_array_at(), gap_array_atp(). Rewrite range table code to use gap arrays. Make put_range_table() smarter so that its operation is O(log n) for adding a localized range. * gc.c (lispdesc_block_size_1): Don't ABORT() when two elements are located at the same place. This will happen with a size-0 gap array -- both parts of the array (before and after gap) are in the same place.
author Ben Wing <ben@xemacs.org>
date Mon, 22 Mar 2010 19:12:15 -0500
parents src/dynarr.c@1fae11d56ad2
children 6c6d78781d59
comparison
equal deleted inserted replaced
5167:e374ea766cc1 5168:cf900a2f1fa3
1 /* Support for dynarrs and other types of dynamic arrays.
2 Copyright (c) 1994, 1995 Free Software Foundation, Inc.
3 Copyright (c) 1993, 1995 Sun Microsystems, Inc.
4 Copyright (c) 1995, 1996, 2000, 2002, 2003, 2004, 2005, 2010 Ben Wing.
5
6 This file is part of XEmacs.
7
8 XEmacs is free software; you can redistribute it and/or modify it
9 under the terms of the GNU General Public License as published by the
10 Free Software Foundation; either version 2, or (at your option) any
11 later version.
12
13 XEmacs is distributed in the hope that it will be useful, but WITHOUT
14 ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
15 FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License
16 for more details.
17
18 You should have received a copy of the GNU General Public License
19 along with XEmacs; see the file COPYING. If not, write to
20 the Free Software Foundation, Inc., 59 Temple Place - Suite 330,
21 Boston, MA 02111-1307, USA. */
22
23 /* Synched up with: Not in FSF. */
24
25 /* Written by Ben Wing, December 1993. */
26
27 #include <config.h>
28 #include "lisp.h"
29
30 #include "insdel.h"
31
32
33 /*****************************************************************************/
34 /* "dynarr" a.k.a. dynamic array */
35 /*****************************************************************************/
36
37 /*
38 A "dynamic array" or "dynarr" is a contiguous array of fixed-size elements
39 where there is no upper limit (except available memory) on the number of
40 elements in the array. Because the elements are maintained contiguously,
41 space is used efficiently (no per-element pointers necessary) and random
42 access to a particular element is in constant time. At any one point, the
43 block of memory that holds the array has an upper limit; if this limit is
44 exceeded, the memory is realloc()ed into a new array that is twice as big.
45 Assuming that the time to grow the array is on the order of the new size of
46 the array block, this scheme has a provably constant amortized time
47 \(i.e. average time over all additions).
48
49 When you add elements or retrieve elements, pointers are used. Note that
50 the element itself (of whatever size it is), and not the pointer to it,
51 is stored in the array; thus you do not have to allocate any heap memory
52 on your own. Also, returned pointers are only guaranteed to be valid
53 until the next operation that changes the length of the array.
54
55 This is a container object. Declare a dynamic array of a specific type
56 as follows:
57
58 typedef struct
59 {
60 Dynarr_declare (mytype);
61 } mytype_dynarr;
62
63 Use the following functions/macros:
64
65
66 ************* Dynarr creation *************
67
68 void *Dynarr_new(type)
69 [MACRO] Create a new dynamic-array object, with each element of the
70 specified type. The return value is cast to (type##_dynarr).
71 This requires following the convention that types are declared in
72 such a way that this type concatenation works. In particular, TYPE
73 must be a symbol, not an arbitrary C type. To make dynarrs of
74 complex types, a typedef must be declared, e.g.
75
76 typedef unsigned char *unsigned_char_ptr;
77
78 and then you can say
79
80 unsigned_char_ptr_dynarr *dyn = Dynarr_new (unsigned_char_ptr);
81
82 void *Dynarr_new2(dynarr_type, type)
83 [MACRO] Create a new dynamic-array object, with each element of the
84 specified type. The array itself is of type DYNARR_TYPE. This makes
85 it possible to create dynarrs over complex types without the need
86 to create typedefs, as described above. Use is as follows:
87
88 ucharptr_dynarr *dyn = Dynarr_new2 (ucharptr_dynarr *, unsigned char *);
89
90 Dynarr_free(d)
91 Destroy a dynamic array and the memory allocated to it.
92
93 ************* Dynarr access *************
94
95 type Dynarr_at(d, i)
96 [MACRO] Return the element at the specified index. The index must be
97 between 0 and Dynarr_largest(d), inclusive. With error-checking
98 enabled, bounds checking on the index is in the form of asserts() --
99 an out-of-bounds index causes an abort. The element itself is
100 returned, not a pointer to it.
101
102 type *Dynarr_atp(d, i)
103 [MACRO] Return a pointer to the element at the specified index.
104 Restrictions and bounds checking on the index is as for Dynarr_at.
105 The pointer may not be valid after an element is added to or
106 (conceivably) removed from the array, because this may trigger a
107 realloc() performed on the underlying dynarr storage, which may
108 involve moving the entire underlying storage to a new location in
109 memory.
110
111 type *Dynarr_begin(d)
112 [MACRO] Return a pointer to the first element in the dynarr. See
113 Dynarr_atp() for warnings about when the pointer might become invalid.
114
115 type *Dynarr_lastp(d)
116 [MACRO] Return a pointer to the last element in the dynarr. See
117 Dynarr_atp() for warnings about when the pointer might become invalid.
118
119 type *Dynarr_past_lastp(d)
120 [MACRO] Return a pointer to the beginning of the element just past the
121 last one. WARNING: This may not point to valid memory; however, the
122 byte directly before will be pointer will be valid memory. This macro
123 might be useful for various reasons, e.g. as a stopping point in a loop
124 (although Dynarr_lastp() could be used just as well) or as a place to
125 start writing elements if Dynarr_length() < Dynarr_largest().
126
127 ************* Dynarr length/size retrieval and setting *************
128
129 int Dynarr_length(d)
130 [MACRO] Return the number of elements currently in a dynamic array.
131
132 int Dynarr_largest(d)
133 [MACRO] Return the maximum value that Dynarr_length(d) would
134 ever have returned. This is used esp. in the redisplay code,
135 which reuses dynarrs for performance reasons.
136
137 int Dynarr_max(d)
138 [MACRO] Return the maximum number of elements that can fit in the
139 dynarr before it needs to be resized.
140
141 Note that Dynarr_length(d) <= Dynarr_largest(d) <= Dynarr_max(d).
142
143 Bytecount Dynarr_sizeof(d)
144 [MACRO] Return the total size of the elements currently in dynarr
145 D. This
146
147 Dynarr_set_lengthr(d, len)
148 [MACRO] Set the length of D to LEN, which must be between 0 and
149 Dynarr_largest(d), inclusive. With error-checking enabled, an
150 assertion failure will result from trying to set the length
151 to less than zero or greater than Dynarr_largest(d). The
152 restriction to Dynarr_largest() is to ensure that
153
154 Dynarr_set_length(d, len)
155 [MACRO] Set the length of D to LEN, resizing the dynarr as
156 necessary to make sure enough space is available. there are no
157 restrictions on LEN other than available memory and that it must
158 be at least 0. Note that
159
160 Dynarr_set_length_and_zero(d, len)
161 [MACRO] Like Dynarr_set_length(d, len) but also, if increasing
162 the length, zero out the memory between the old and new lengths,
163 i.e. starting just past the previous last element and up through
164 the new last element.
165
166 Dynarr_incrementr(d)
167 [MACRO] Increments the length of D by 1. Equivalent to
168 Dynarr_set_lengthr(d, Dynarr_length(d) + 1).
169
170 Dynarr_increment(d)
171 [MACRO] Increments the length of D by 1. Equivalent to
172 Dynarr_set_length(d, Dynarr_length(d) + 1).
173
174 Dynarr_reset(d)
175 [MACRO] Reset the length of a dynamic array to 0.
176
177 Dynarr_resize(d, maxval)
178 Resize the internal dynarr storage to so that it can hold at least
179 MAXVAL elements. Resizing is done using a geometric series
180 (repeatedly multiply the old maximum by a constant, normally 1.5,
181 till a large enough size is reached), so this will be efficient
182 even if resizing larger by one element at a time. This is mostly
183 an internal function.
184
185
186
187 ************* Adding/deleting elements to/from a dynarr *************
188
189 Dynarr_add(d, el)
190 [MACRO] Add an element to the end of a dynamic array. EL is a pointer
191 to the element; the element itself is stored in the array, however.
192 No function call is performed unless the array needs to be resized.
193
194 Dynarr_add_many(d, base, len)
195 [MACRO] Add LEN elements to the end of the dynamic array. The elements
196 should be contiguous in memory, starting at BASE. If BASE if NULL,
197 just make space for the elements; don't actually add them.
198
199 Dynarr_prepend_many(d, base, len)
200 [MACRO] Prepend LEN elements to the beginning of the dynamic array.
201 The elements should be contiguous in memory, starting at BASE.
202 If BASE if NULL, just make space for the elements; don't actually
203 add them.
204
205 Dynarr_insert_many(d, base, len, pos)
206 Insert LEN elements to the dynamic array starting at position
207 POS. The elements should be contiguous in memory, starting at BASE.
208 If BASE if NULL, just make space for the elements; don't actually
209 add them.
210
211 type Dynarr_pop(d)
212 [MACRO] Pop the last element off the dynarr and return it.
213
214 Dynarr_delete(d, i)
215 [MACRO] Delete an element from the dynamic array at position I.
216
217 Dynarr_delete_many(d, pos, len)
218 Delete LEN elements from the dynamic array starting at position
219 POS.
220
221 Dynarr_zero_many(d, pos, len)
222 Zero out LEN elements in the dynarr D starting at position POS.
223
224 Dynarr_delete_by_pointer(d, p)
225 [MACRO] Delete an element from the dynamic array at pointer P,
226 which must point within the block of memory that stores the data.
227 P should be obtained using Dynarr_atp().
228
229 ************* Dynarr locking *************
230
231 Dynarr_lock(d)
232 Lock the dynarr against further locking or writing. With error-checking
233 enabled, any attempts to write into a locked dynarr or re-lock an
234 already locked one will cause an assertion failure and abort.
235
236 Dynarr_unlock(d)
237 Unlock a locked dynarr, allowing writing into it.
238
239 ************* Dynarr global variables *************
240
241 Dynarr_min_size
242 Minimum allowable size for a dynamic array when it is resized.
243
244 */
245
246 static const struct memory_description const_Ascbyte_ptr_description_1[] = {
247 { XD_ASCII_STRING, 0 },
248 { XD_END }
249 };
250
251 const struct sized_memory_description const_Ascbyte_ptr_description = {
252 sizeof (const Ascbyte *),
253 const_Ascbyte_ptr_description_1
254 };
255
256 static const struct memory_description const_Ascbyte_ptr_dynarr_description_1[] = {
257 XD_DYNARR_DESC (const_Ascbyte_ptr_dynarr, &const_Ascbyte_ptr_description),
258 { XD_END }
259 };
260
261 const struct sized_memory_description const_Ascbyte_ptr_dynarr_description = {
262 sizeof (const_Ascbyte_ptr_dynarr),
263 const_Ascbyte_ptr_dynarr_description_1
264 };
265
266
267 static Elemcount Dynarr_min_size = 8;
268
269 static void
270 Dynarr_realloc (Dynarr *dy, Elemcount new_size)
271 {
272 if (DUMPEDP (dy->base))
273 {
274 void *new_base = malloc (new_size * Dynarr_elsize (dy));
275 memcpy (new_base, dy->base,
276 (Dynarr_max (dy) < new_size ? Dynarr_max (dy) : new_size) *
277 Dynarr_elsize (dy));
278 dy->base = new_base;
279 }
280 else
281 dy->base = xrealloc (dy->base, new_size * Dynarr_elsize (dy));
282 }
283
284 void *
285 Dynarr_newf (Bytecount elsize)
286 {
287 Dynarr *d = xnew_and_zero (Dynarr);
288 d->elsize_ = elsize;
289
290 return d;
291 }
292
293 #ifdef NEW_GC
294 DEFINE_DUMPABLE_INTERNAL_LISP_OBJECT ("dynarr", dynarr,
295 0, 0,
296 Dynarr);
297
298 static void
299 Dynarr_lisp_realloc (Dynarr *dy, Elemcount new_size)
300 {
301 void *new_base =
302 XPNTR (alloc_sized_lrecord_array (Dynarr_elsize (dy), new_size,
303 dy->lisp_imp));
304 if (dy->base)
305 memcpy (new_base, dy->base,
306 (Dynarr_max (dy) < new_size ? Dynarr_max (dy) : new_size) *
307 Dynarr_elsize (dy));
308 dy->base = new_base;
309 }
310
311 void *
312 Dynarr_lisp_newf (Bytecount elsize,
313 const struct lrecord_implementation *dynarr_imp,
314 const struct lrecord_implementation *imp)
315 {
316 Dynarr *d = (Dynarr *) XPNTR (alloc_sized_lrecord (sizeof (Dynarr),
317 dynarr_imp));
318 d->elsize_ = elsize;
319 d->lisp_imp = imp;
320
321 return d;
322 }
323 #endif /* not NEW_GC */
324
325 void
326 Dynarr_resize (void *d, Elemcount size)
327 {
328 Elemcount newsize;
329 double multiplier;
330 Dynarr *dy = (Dynarr *) Dynarr_verify (d);
331
332 if (Dynarr_max (dy) <= 8)
333 multiplier = 2;
334 else
335 multiplier = 1.5;
336
337 for (newsize = Dynarr_max (dy); newsize < size;)
338 newsize = max (Dynarr_min_size, (Elemcount) (multiplier * newsize));
339
340 /* Don't do anything if the array is already big enough. */
341 if (newsize > Dynarr_max (dy))
342 {
343 #ifdef NEW_GC
344 if (dy->lisp_imp)
345 Dynarr_lisp_realloc (dy, newsize);
346 else
347 Dynarr_realloc (dy, newsize);
348 #else /* not NEW_GC */
349 Dynarr_realloc (dy, newsize);
350 #endif /* not NEW_GC */
351 dy->max_ = newsize;
352 }
353 }
354
355 /* Add a number of contiguous elements to the array starting at POS. */
356
357 void
358 Dynarr_insert_many (void *d, const void *base, Elemcount len, Elemcount pos)
359 {
360 Dynarr *dy = Dynarr_verify_mod (d);
361 Elemcount old_len = Dynarr_length (dy);
362
363 /* #### This could conceivably be wrong, if code wants to access stuff
364 between len and largest. */
365 dynarr_checking_assert (pos >= 0 && pos <= old_len);
366 dynarr_checking_assert (len >= 0);
367 Dynarr_increase_length (dy, old_len + len);
368
369 if (pos != old_len)
370 {
371 memmove ((Rawbyte *) dy->base + (pos + len)*Dynarr_elsize (dy),
372 (Rawbyte *) dy->base + pos*Dynarr_elsize (dy),
373 (old_len - pos)*Dynarr_elsize (dy));
374 }
375 /* Some functions call us with a value of 0 to mean "reserve space but
376 don't write into it" */
377 if (base)
378 memcpy ((Rawbyte *) dy->base + pos*Dynarr_elsize (dy), base,
379 len*Dynarr_elsize (dy));
380 }
381
382 void
383 Dynarr_delete_many (void *d, Elemcount pos, Elemcount len)
384 {
385 Dynarr *dy = Dynarr_verify_mod (d);
386
387 dynarr_checking_assert (pos >= 0 && len >= 0 &&
388 pos + len <= Dynarr_length (dy));
389
390 memmove ((Rawbyte *) dy->base + pos*Dynarr_elsize (dy),
391 (Rawbyte *) dy->base + (pos + len)*Dynarr_elsize (dy),
392 (Dynarr_length (dy) - pos - len)*Dynarr_elsize (dy));
393
394 Dynarr_set_length_1 (dy, Dynarr_length (dy) - len);
395 }
396
397 void
398 Dynarr_free (void *d)
399 {
400 Dynarr *dy = (Dynarr *) d;
401
402 #ifdef NEW_GC
403 if (dy->base && !DUMPEDP (dy->base))
404 {
405 if (!dy->lisp_imp)
406 xfree (dy->base);
407 }
408 if(!DUMPEDP (dy))
409 {
410 if (!dy->lisp_imp)
411 xfree (dy);
412 }
413 #else /* not NEW_GC */
414 if (dy->base && !DUMPEDP (dy->base))
415 xfree (dy->base);
416 if(!DUMPEDP (dy))
417 xfree (dy);
418 #endif /* not NEW_GC */
419 }
420
421 #ifdef MEMORY_USAGE_STATS
422
423 /* Return memory usage for dynarr D. The returned value is the total
424 amount of bytes actually being used for the dynarr, including all
425 overhead. The extra amount of space in the dynarr that is
426 allocated beyond what was requested is returned in DYNARR_OVERHEAD
427 in STATS. The extra amount of space that malloc() allocates beyond
428 what was requested of it is returned in MALLOC_OVERHEAD in STATS.
429 See the comment above the definition of this structure. */
430
431 Bytecount
432 Dynarr_memory_usage (void *d, struct usage_stats *stats)
433 {
434 Bytecount total = 0;
435 Dynarr *dy = (Dynarr *) d;
436
437 /* We have to be a bit tricky here because not all of the
438 memory that malloc() will claim as "requested" was actually
439 requested. */
440
441 if (dy->base)
442 {
443 Bytecount malloc_used =
444 malloced_storage_size (dy->base, Dynarr_elsize (dy) * Dynarr_max (dy),
445 0);
446 /* #### This may or may not be correct. Some dynarrs would
447 prefer that we use dy->len instead of dy->largest here. */
448 Bytecount was_requested = Dynarr_elsize (dy) * Dynarr_largest (dy);
449 Bytecount dynarr_overhead =
450 Dynarr_elsize (dy) * (Dynarr_max (dy) - Dynarr_largest (dy));
451
452 total += malloc_used;
453 stats->was_requested += was_requested;
454 stats->dynarr_overhead += dynarr_overhead;
455 /* And the remainder must be malloc overhead. */
456 stats->malloc_overhead +=
457 malloc_used - was_requested - dynarr_overhead;
458 }
459
460 total += malloced_storage_size (d, sizeof (*dy), stats);
461
462 return total;
463 }
464
465 #endif /* MEMORY_USAGE_STATS */
466
467
468 /*****************************************************************************/
469 /* stack-like allocation */
470 /*****************************************************************************/
471
472 /* Version of malloc() that will be extremely efficient when allocation
473 nearly always occurs in LIFO (stack) order.
474
475 #### Perhaps shouldn't be in this file, but where else? */
476
477 typedef struct
478 {
479 Dynarr_declare (char_dynarr *);
480 } char_dynarr_dynarr;
481
482 char_dynarr_dynarr *stack_like_free_list;
483 char_dynarr_dynarr *stack_like_in_use_list;
484
485 void *
486 stack_like_malloc (Bytecount size)
487 {
488 char_dynarr *this_one;
489 if (!stack_like_free_list)
490 {
491 stack_like_free_list = Dynarr_new2 (char_dynarr_dynarr,
492 char_dynarr *);
493 stack_like_in_use_list = Dynarr_new2 (char_dynarr_dynarr,
494 char_dynarr *);
495 }
496
497 if (Dynarr_length (stack_like_free_list) > 0)
498 this_one = Dynarr_pop (stack_like_free_list);
499 else
500 this_one = Dynarr_new (char);
501 Dynarr_add (stack_like_in_use_list, this_one);
502 Dynarr_reset (this_one);
503 Dynarr_add_many (this_one, 0, size);
504 return Dynarr_begin (this_one);
505 }
506
507 void
508 stack_like_free (void *val)
509 {
510 Elemcount len = Dynarr_length (stack_like_in_use_list);
511 assert (len > 0);
512 /* The vast majority of times, we will be called in a last-in first-out
513 order, and the item at the end of the list will be the one we're
514 looking for, so just check for this first and avoid any function
515 calls. */
516 if (Dynarr_begin (Dynarr_at (stack_like_in_use_list, len - 1)) == val)
517 {
518 char_dynarr *this_one = Dynarr_pop (stack_like_in_use_list);
519 Dynarr_add (stack_like_free_list, this_one);
520 }
521 else
522 {
523 /* Find the item and delete it. */
524 int i;
525 assert (len >= 2);
526 for (i = len - 2; i >= 0; i--)
527 if (Dynarr_begin (Dynarr_at (stack_like_in_use_list, i)) ==
528 val)
529 {
530 char_dynarr *this_one = Dynarr_at (stack_like_in_use_list, i);
531 Dynarr_add (stack_like_free_list, this_one);
532 Dynarr_delete (stack_like_in_use_list, i);
533 return;
534 }
535
536 ABORT ();
537 }
538 }
539
540
541 /*****************************************************************************/
542 /* Generalized gap array */
543 /*****************************************************************************/
544
545 /* A "gap array" is an array that has a "gap" somewhere in the middle of it,
546 so that insertions and deletions near the gap -- or in general, highly
547 localized insertions and deletions -- are very fast. Inserting or
548 deleting works by first moving the gap to the insertion or deletion
549 position and then shortening or lengthening the gap as necessary. The
550 idea comes from the gap used in storing text in a buffer.
551
552 The gap array interface differs in a number of ways from dynarrs (####
553 and should be changed so that it works the same as dynarrs):
554
555 (1) There aren't separate type-specific gap array types. As a result,
556 operations like gap_array_at() require that the type be specified as
557 one of the arguments. It is often more convenient to use a macro
558 wrapper around this operation.
559
560 (2) The gap array type is itself a stretchy array rather than using a
561 separate block of memory to store the array. This means that certain
562 operations (especially insertions) may relocate the the gap array,
563 and as a result return a pointer to the (possibly) moved gap array,
564 which must be stored back into the location where the gap array
565 pointer resides. This also means that the caller must worry about
566 cloning the gap array in the case where it has been dumped, or you
567 will get an ABORT() inside of xrealloc().
568
569 (3) Fewer operations are available than for dynarrs, and may have
570 different names and/or different calling conventions.
571
572 (4) The mechanism for creating "Lisp-object gap arrays" isn't completely
573 developed. Currently it's only possible to create a gap-array Lisp
574 object that wraps Lisp_Object pointers (not Lisp object structures
575 directly), and only under NEW_GC.
576
577 (5) Gap arrays have a concept of a "gap array marker" that properly
578 tracks insertions and deletions; no such thing exists in dynarrs.
579 It exists in gap arrays because it's necessary for their use in
580 implementing extent lists.
581 */
582
583 extern const struct sized_memory_description gap_array_marker_description;
584
585 static const struct memory_description gap_array_marker_description_1[] = {
586 #ifdef NEW_GC
587 { XD_LISP_OBJECT, offsetof (Gap_Array_Marker, next) },
588 #else /* not NEW_GC */
589 { XD_BLOCK_PTR, offsetof (Gap_Array_Marker, next), 1,
590 { &gap_array_marker_description } },
591 #endif /* not NEW_GC */
592 { XD_END }
593 };
594
595 #ifdef NEW_GC
596 DEFINE_NODUMP_INTERNAL_LISP_OBJECT ("gap-array-marker", gap_array_marker,
597 0, gap_array_marker_description_1,
598 struct gap_array_marker);
599 #else /* not NEW_GC */
600 const struct sized_memory_description gap_array_marker_description = {
601 sizeof (Gap_Array_Marker),
602 gap_array_marker_description_1
603 };
604 #endif /* not NEW_GC */
605
606 static const struct memory_description lispobj_gap_array_description_1[] = {
607 XD_GAP_ARRAY_DESC (&lisp_object_description),
608 { XD_END }
609 };
610
611 #ifdef NEW_GC
612
613 static Bytecount
614 size_gap_array (Lisp_Object obj)
615 {
616 Gap_Array *ga = XGAP_ARRAY (obj);
617 return gap_array_byte_size (ga);
618 }
619
620 DEFINE_DUMPABLE_SIZABLE_INTERNAL_LISP_OBJECT ("gap-array", gap_array,
621 0,
622 lispobj_gap_array_description_1,
623 size_gap_array,
624 struct gap_array);
625 #else /* not NEW_GC */
626 const struct sized_memory_description lispobj_gap_array_description = {
627 0, lispobj_gap_array_description_1
628 };
629 #endif /* (not) NEW_GC */
630
631 #ifndef NEW_GC
632 static Gap_Array_Marker *gap_array_marker_freelist;
633 #endif /* not NEW_GC */
634
635 /* This generalizes the "array with a gap" model used to store buffer
636 characters. This is based on the stuff in insdel.c and should
637 probably be merged with it. This is not extent-specific and should
638 perhaps be moved into a separate file. */
639
640 /* ------------------------------- */
641 /* internal functions */
642 /* ------------------------------- */
643
644 /* Adjust the gap array markers in the range (FROM, TO]. Parallel to
645 adjust_markers() in insdel.c. */
646
647 static void
648 gap_array_adjust_markers (Gap_Array *ga, Memxpos from,
649 Memxpos to, Elemcount amount)
650 {
651 Gap_Array_Marker *m;
652
653 for (m = ga->markers; m; m = m->next)
654 m->pos = do_marker_adjustment (m->pos, from, to, amount);
655 }
656
657 static void
658 gap_array_recompute_derived_values (Gap_Array *ga)
659 {
660 ga->offset_past_gap = ga->elsize * (ga->gap + ga->gapsize);
661 ga->els_past_gap = ga->numels - ga->gap;
662 }
663
664 /* Move the gap to array position POS. Parallel to move_gap() in
665 insdel.c but somewhat simplified. */
666
667 static void
668 gap_array_move_gap (Gap_Array *ga, Elemcount pos)
669 {
670 Elemcount gap = ga->gap;
671 Elemcount gapsize = ga->gapsize;
672
673 if (pos < gap)
674 {
675 memmove (GAP_ARRAY_MEMEL_ADDR (ga, pos + gapsize),
676 GAP_ARRAY_MEMEL_ADDR (ga, pos),
677 (gap - pos)*ga->elsize);
678 gap_array_adjust_markers (ga, (Memxpos) pos, (Memxpos) gap,
679 gapsize);
680 }
681 else if (pos > gap)
682 {
683 memmove (GAP_ARRAY_MEMEL_ADDR (ga, gap),
684 GAP_ARRAY_MEMEL_ADDR (ga, gap + gapsize),
685 (pos - gap)*ga->elsize);
686 gap_array_adjust_markers (ga, (Memxpos) (gap + gapsize),
687 (Memxpos) (pos + gapsize), - gapsize);
688 }
689 ga->gap = pos;
690
691 gap_array_recompute_derived_values (ga);
692 }
693
694 /* Make the gap INCREMENT characters longer. Parallel to make_gap() in
695 insdel.c. The gap array may be moved, so assign the return value back
696 to the array pointer. */
697
698 static Gap_Array *
699 gap_array_make_gap (Gap_Array *ga, Elemcount increment)
700 {
701 Elemcount real_gap_loc;
702 Elemcount old_gap_size;
703
704 /* If we have to get more space, get enough to last a while. We use
705 a geometric progression that saves on realloc space. */
706 increment += 100 + ga->numels / 8;
707
708 #ifdef NEW_GC
709 if (ga->is_lisp)
710 ga = (Gap_Array *) mc_realloc (ga,
711 offsetof (Gap_Array, array) +
712 (ga->numels + ga->gapsize + increment) *
713 ga->elsize);
714 else
715 #endif /* not NEW_GC */
716 ga = (Gap_Array *) xrealloc (ga,
717 offsetof (Gap_Array, array) +
718 (ga->numels + ga->gapsize + increment) *
719 ga->elsize);
720 if (ga == 0)
721 memory_full ();
722
723 real_gap_loc = ga->gap;
724 old_gap_size = ga->gapsize;
725
726 /* Call the newly allocated space a gap at the end of the whole space. */
727 ga->gap = ga->numels + ga->gapsize;
728 ga->gapsize = increment;
729
730 /* Move the new gap down to be consecutive with the end of the old one.
731 This adjusts the markers properly too. */
732 gap_array_move_gap (ga, real_gap_loc + old_gap_size);
733
734 /* Now combine the two into one large gap. */
735 ga->gapsize += old_gap_size;
736 ga->gap = real_gap_loc;
737
738 gap_array_recompute_derived_values (ga);
739
740 return ga;
741 }
742
743 /* ------------------------------- */
744 /* external functions */
745 /* ------------------------------- */
746
747 Bytecount
748 gap_array_byte_size (Gap_Array *ga)
749 {
750 return offsetof (Gap_Array, array) + (ga->numels + ga->gapsize) * ga->elsize;
751 }
752
753 /* Insert NUMELS elements (pointed to by ELPTR) into the specified
754 gap array at POS. The gap array may be moved, so assign the
755 return value back to the array pointer. */
756
757 Gap_Array *
758 gap_array_insert_els (Gap_Array *ga, Elemcount pos, void *elptr,
759 Elemcount numels)
760 {
761 assert (pos >= 0 && pos <= ga->numels);
762 if (ga->gapsize < numels)
763 ga = gap_array_make_gap (ga, numels - ga->gapsize);
764 if (pos != ga->gap)
765 gap_array_move_gap (ga, pos);
766
767 memcpy (GAP_ARRAY_MEMEL_ADDR (ga, ga->gap), (char *) elptr,
768 numels*ga->elsize);
769 ga->gapsize -= numels;
770 ga->gap += numels;
771 ga->numels += numels;
772 gap_array_recompute_derived_values (ga);
773 /* This is the equivalent of insert-before-markers.
774
775 #### Should only happen if marker is "moves forward at insert" type.
776 */
777
778 gap_array_adjust_markers (ga, pos - 1, pos, numels);
779 return ga;
780 }
781
782 /* Delete NUMELS elements from the specified gap array, starting at FROM. */
783
784 void
785 gap_array_delete_els (Gap_Array *ga, Elemcount from, Elemcount numdel)
786 {
787 Elemcount to = from + numdel;
788 Elemcount gapsize = ga->gapsize;
789
790 assert (from >= 0);
791 assert (numdel >= 0);
792 assert (to <= ga->numels);
793
794 /* Make sure the gap is somewhere in or next to what we are deleting. */
795 if (to < ga->gap)
796 gap_array_move_gap (ga, to);
797 if (from > ga->gap)
798 gap_array_move_gap (ga, from);
799
800 /* Relocate all markers pointing into the new, larger gap
801 to point at the end of the text before the gap. */
802 gap_array_adjust_markers (ga, to + gapsize, to + gapsize,
803 - numdel - gapsize);
804
805 ga->gapsize += numdel;
806 ga->numels -= numdel;
807 ga->gap = from;
808 gap_array_recompute_derived_values (ga);
809 }
810
811 Gap_Array_Marker *
812 gap_array_make_marker (Gap_Array *ga, Elemcount pos)
813 {
814 Gap_Array_Marker *m;
815
816 assert (pos >= 0 && pos <= ga->numels);
817 #ifdef NEW_GC
818 m = XGAP_ARRAY_MARKER (ALLOC_NORMAL_LISP_OBJECT (gap_array_marker));
819 #else /* not NEW_GC */
820 if (gap_array_marker_freelist)
821 {
822 m = gap_array_marker_freelist;
823 gap_array_marker_freelist = gap_array_marker_freelist->next;
824 }
825 else
826 m = xnew (Gap_Array_Marker);
827 #endif /* not NEW_GC */
828
829 m->pos = GAP_ARRAY_ARRAY_TO_MEMORY_POS (ga, pos);
830 m->next = ga->markers;
831 ga->markers = m;
832 return m;
833 }
834
835 void
836 gap_array_delete_marker (Gap_Array *ga, Gap_Array_Marker *m)
837 {
838 Gap_Array_Marker *p, *prev;
839
840 for (prev = 0, p = ga->markers; p && p != m; prev = p, p = p->next)
841 ;
842 assert (p);
843 if (prev)
844 prev->next = p->next;
845 else
846 ga->markers = p->next;
847 #ifndef NEW_GC
848 m->next = gap_array_marker_freelist;
849 m->pos = 0xDEADBEEF; /* -559038737 base 10 */
850 gap_array_marker_freelist = m;
851 #endif /* not NEW_GC */
852 }
853
854 #ifndef NEW_GC
855 void
856 gap_array_delete_all_markers (Gap_Array *ga)
857 {
858 Gap_Array_Marker *p, *next;
859
860 for (p = ga->markers; p; p = next)
861 {
862 next = p->next;
863 p->next = gap_array_marker_freelist;
864 p->pos = 0xDEADBEEF; /* -559038737 as an int */
865 gap_array_marker_freelist = p;
866 }
867 }
868 #endif /* not NEW_GC */
869
870 void
871 gap_array_move_marker (Gap_Array *ga, Gap_Array_Marker *m, Elemcount pos)
872 {
873 assert (pos >= 0 && pos <= ga->numels);
874 m->pos = GAP_ARRAY_ARRAY_TO_MEMORY_POS (ga, pos);
875 }
876
877 Gap_Array *
878 make_gap_array (Elemcount elsize, int USED_IF_NEW_GC (do_lisp))
879 {
880 Gap_Array *ga;
881 #ifdef NEW_GC
882 /* #### I don't quite understand why it's necessary to make all these
883 internal objects into Lisp objects under NEW_GC. It's a pain in the
884 ass to code around this. I'm proceeding on the assumption that it's
885 not really necessary to do it after all, and so we only make a Lisp-
886 object gap array when the object being held is a Lisp_Object, i.e. a
887 pointer to a Lisp object. In the case where instead we hold a `struct
888 range_table_entry', just blow it off. Otherwise we either need to do
889 a bunch of painful and/or boring rewriting. --ben */
890 if (do_lisp)
891 {
892 ga = XGAP_ARRAY (ALLOC_SIZED_LISP_OBJECT (sizeof (Gap_Array),
893 gap_array));
894 ga->is_lisp = 1;
895 }
896 else
897 #endif /* not NEW_GC */
898 ga = xnew_and_zero (Gap_Array);
899 ga->elsize = elsize;
900 return ga;
901 }
902
903 Gap_Array *
904 gap_array_clone (Gap_Array *ga)
905 {
906 Bytecount size = gap_array_byte_size (ga);
907 Gap_Array *ga2;
908 Gap_Array_Marker *m;
909
910 #ifdef NEW_GC
911 if (ga->is_lisp)
912 {
913 ga2 = XGAP_ARRAY (ALLOC_SIZED_LISP_OBJECT (size, gap_array));
914 copy_lisp_object (wrap_gap_array (ga2), wrap_gap_array (ga));
915 }
916 else
917 #endif
918 {
919 ga2 = (Gap_Array *) xmalloc (size);
920 memcpy (ga2, ga, size);
921 }
922 ga2->markers = NULL;
923 for (m = ga->markers; m; m = m->next)
924 gap_array_make_marker (ga2, m->pos);
925 return ga2;
926 }
927
928 #ifndef NEW_GC
929 void
930 free_gap_array (Gap_Array *ga)
931 {
932 gap_array_delete_all_markers (ga);
933 xfree (ga);
934 }
935 #endif /* not NEW_GC */
936
937
938 /*****************************************************************************/
939 /* Initialization */
940 /*****************************************************************************/
941
942 void
943 syms_of_array (void)
944 {
945 #ifdef NEW_GC
946 INIT_LISP_OBJECT (gap_array_marker);
947 INIT_LISP_OBJECT (gap_array);
948 #endif /* NEW_GC */
949 }
950