Mercurial > hg > xemacs-beta

comparison src/array.h @ 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
children 6c6d78781d59
comparison
equal deleted inserted replaced
5167:e374ea766cc1 5168:cf900a2f1fa3
1 /* Header for arrays (dynarrs, gap arrays, etc.).
2 Copyright (C) 1993, 1994, 1995 Free Software Foundation, Inc.
3 Copyright (C) 1996, 2001, 2002, 2004, 2005, 2009, 2010 Ben Wing.
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 /* This file has been Mule-ized, Ben Wing, 10-13-04. */
25
26 #ifndef INCLUDED_array_h_
27 #define INCLUDED_array_h_
28
29 /************************************************************************/
30 /** Definition of dynamic arrays (dynarrs) **/
31 /************************************************************************/
32
33 BEGIN_C_DECLS
34
35 /************* Dynarr declaration *************/
36
37 #ifdef NEW_GC
38 #define DECLARE_DYNARR_LISP_IMP() \
39 const struct lrecord_implementation *lisp_imp;
40 #else
41 #define DECLARE_DYNARR_LISP_IMP()
42 #endif
43
44 #ifdef ERROR_CHECK_DYNARR
45 #define DECLARE_DYNARR_LOCKED() \
46 int locked;
47 #else
48 #define DECLARE_DYNARR_LOCKED()
49 #endif
50
51 #define Dynarr_declare(type) \
52 struct lrecord_header header; \
53 type *base; \
54 DECLARE_DYNARR_LISP_IMP () \
55 DECLARE_DYNARR_LOCKED () \
56 int elsize_; \
57 int len_; \
58 int largest_; \
59 int max_
60
61 typedef struct dynarr
62 {
63 Dynarr_declare (void);
64 } Dynarr;
65
66 #define XD_DYNARR_DESC(base_type, sub_desc) \
67 { XD_BLOCK_PTR, offsetof (base_type, base), \
68 XD_INDIRECT(1, 0), {sub_desc} }, \
69 { XD_INT, offsetof (base_type, len_) }, \
70 { XD_INT_RESET, offsetof (base_type, largest_), XD_INDIRECT(1, 0) }, \
71 { XD_INT_RESET, offsetof (base_type, max_), XD_INDIRECT(1, 0) }
72
73 #ifdef NEW_GC
74 #define XD_LISP_DYNARR_DESC(base_type, sub_desc) \
75 { XD_LISP_OBJECT_BLOCK_PTR, offsetof (base_type, base), \
76 XD_INDIRECT(1, 0), {sub_desc} }, \
77 { XD_INT, offsetof (base_type, len_) }, \
78 { XD_INT_RESET, offsetof (base_type, largest_), XD_INDIRECT(1, 0) }, \
79 { XD_INT_RESET, offsetof (base_type, max_), XD_INDIRECT(1, 0) }
80 #endif /* NEW_GC */
81
82 /************* Dynarr verification *************/
83
84 /* Dynarr locking and verification.
85
86 [I] VERIFICATION
87
88 Verification routines simply return their basic argument, possibly
89 casted, but in the process perform some verification on it, aborting if
90 the verification fails. The verification routines take FILE and LINE
91 parameters, and use them to output the file and line of the caller
92 when an abort occurs, rather than the file and line of the inline
93 function, which is less than useful.
94
95 There are three basic types of verification routines:
96
97 (1) Verify the dynarr itself. This verifies the basic invariant
98 involving the length/size values:
99
100 0 <= Dynarr_length(d) <= Dynarr_largest(d) <= Dynarr_max(d)
101
102 (2) Verify the dynarr itself prior to modifying it. This performs
103 the same verification as previously, but also checks that the
104 dynarr is not locked (see below).
105
106 (3) Verify a dynarr position. Unfortunately we have to have
107 different verification routines depending on which kind of operation
108 is being performed:
109
110 (a) For Dynarr_at(), we check that the POS is bounded by Dynarr_largest(),
111 i.e. 0 <= POS < Dynarr_largest().
112 (b) For Dynarr_atp_allow_end(), we also have to allow
113 POS == Dynarr_largest().
114 (c) For Dynarr_atp(), we behave largely like Dynarr_at() but make a
115 special exception when POS == 0 and Dynarr_largest() == 0 -- see
116 comment below.
117 (d) Some other routines contain the POS verification within their code,
118 and make the check 0 <= POS < Dynarr_length() or
119 0 <= POS <= Dynarr_length().
120
121 #### It is not well worked-out whether and in what circumstances it's
122 allowed to use a position that is between Dynarr_length() and
123 Dynarr_largest(). The ideal solution is to never allow this, and require
124 instead that code first change the length before accessing higher
125 positions. That would require looking through all the code that accesses
126 dynarrs and fixing it appropriately (especially redisplay code, and
127 especially redisplay code in the vicinity of a reference to
128 Dynarr_largest(), since such code usually checks explicitly to see whether
129 there is extra stuff between Dynarr_length() and Dynarr_largest().)
130
131 [II] LOCKING
132
133 The idea behind dynarr locking is simple: Locking a dynarr prevents
134 any modification from occurring, or rather, leads to an abort upon
135 any attempt to modify a dynarr.
136
137 Dynarr locking was originally added to catch some sporadic and hard-to-
138 debug crashes in the redisplay code where dynarrs appeared to be getting
139 corrupted in an unexpected fashion. The solution was to lock the
140 dynarrs that were getting corrupted (in this case, the display-line
141 dynarrs) around calls to routines that weren't supposed to be changing
142 these dynarrs but might somehow be calling code that modified them.
143 This eventually revealed that there was a reentrancy problem with
144 redisplay that involved the QUIT mechanism and the processing done in
145 order to determine whether C-g had been pressed -- this processing
146 involves retrieving, processing and queueing pending events to see
147 whether any of them result in a C-g keypress. However, at least under
148 MS Windows this can result in redisplay being called reentrantly.
149 For more info:--
150
151 (Info-goto-node "(internals)Critical Redisplay Sections")
152
153 */
154
155 #ifdef ERROR_CHECK_DYNARR
156 DECLARE_INLINE_HEADER (
157 int
158 Dynarr_verify_pos_at (void *d, Elemcount pos, const Ascbyte *file, int line)
159 )
160 {
161 Dynarr *dy = (Dynarr *) d;
162 /* We use `largest', not `len', because the redisplay code often
163 accesses stuff between len and largest. */
164 assert_at_line (pos >= 0 && pos < dy->largest_, file, line);
165 return pos;
166 }
167
168 DECLARE_INLINE_HEADER (
169 int
170 Dynarr_verify_pos_atp (void *d, Elemcount pos, const Ascbyte *file, int line)
171 )
172 {
173 Dynarr *dy = (Dynarr *) d;
174 /* We use `largest', not `len', because the redisplay code often
175 accesses stuff between len and largest. */
176 /* [[ Code will often do something like ...
177
178 val = make_bit_vector_from_byte_vector (Dynarr_atp (dyn, 0),
179 Dynarr_length (dyn));
180
181 which works fine when the Dynarr_length is non-zero, but when zero,
182 the result of Dynarr_atp() not only points past the end of the
183 allocated array, but the array may not have ever been allocated and
184 hence the return value is NULL. But the length of 0 causes the
185 pointer to never get checked. These can occur throughout the code
186 so we put in a special check. --ben ]]
187
188 Update: The common idiom `Dynarr_atp (dyn, 0)' has been changed to
189 `Dynarr_begin (dyn)'. Possibly this special check at POS 0 can be
190 done only for Dynarr_begin() not for general Dynarr_atp(). --ben */
191 if (pos == 0 && dy->len_ == 0)
192 return pos;
193 /* #### It's vaguely possible that some code could legitimately want to
194 retrieve a pointer to the position just past the end of dynarr memory.
195 This could happen with Dynarr_atp() but not Dynarr_at(). If so, it
196 will trigger this assert(). In such cases, it should be obvious that
197 the code wants to do this; rather than relaxing the assert, we should
198 probably create a new macro Dynarr_atp_allow_end() which is like
199 Dynarr_atp() but which allows for pointing at invalid addresses -- we
200 really want to check for cases of accessing just past the end of
201 memory, which is a likely off-by-one problem to occur and will usually
202 not trigger a protection fault (instead, you'll just get random
203 behavior, possibly overwriting other memory, which is bad). --ben */
204 assert_at_line (pos >= 0 && pos < dy->largest_, file, line);
205 return pos;
206 }
207
208 DECLARE_INLINE_HEADER (
209 int
210 Dynarr_verify_pos_atp_allow_end (void *d, Elemcount pos, const Ascbyte *file,
211 int line)
212 )
213 {
214 Dynarr *dy = (Dynarr *) d;
215 /* We use `largest', not `len', because the redisplay code often
216 accesses stuff between len and largest.
217 We also allow referencing the very end, past the end of allocated
218 legitimately space. See comments in Dynarr_verify_pos_atp.()*/
219 assert_at_line (pos >= 0 && pos <= dy->largest_, file, line);
220 return pos;
221 }
222
223 #else
224 #define Dynarr_verify_pos_at(d, pos, file, line) (pos)
225 #define Dynarr_verify_pos_atp(d, pos, file, line) (pos)
226 #define Dynarr_verify_pos_atp_allow_end(d, pos, file, line) (pos)
227 #endif /* ERROR_CHECK_DYNARR */
228
229 #ifdef ERROR_CHECK_DYNARR
230 DECLARE_INLINE_HEADER (
231 Dynarr *
232 Dynarr_verify_1 (void *d, const Ascbyte *file, int line)
233 )
234 {
235 Dynarr *dy = (Dynarr *) d;
236 assert_at_line (dy->len_ >= 0 && dy->len_ <= dy->largest_ &&
237 dy->largest_ <= dy->max_, file, line);
238 return dy;
239 }
240
241 DECLARE_INLINE_HEADER (
242 Dynarr *
243 Dynarr_verify_mod_1 (void *d, const Ascbyte *file, int line)
244 )
245 {
246 Dynarr *dy = (Dynarr *) d;
247 assert_at_line (!dy->locked, file, line);
248 return Dynarr_verify_1 (d, file, line);
249 }
250
251 #define Dynarr_verify(d) Dynarr_verify_1 (d, __FILE__, __LINE__)
252 #define Dynarr_verify_mod(d) Dynarr_verify_mod_1 (d, __FILE__, __LINE__)
253
254 DECLARE_INLINE_HEADER (
255 void
256 Dynarr_lock (void *d)
257 )
258 {
259 Dynarr *dy = Dynarr_verify_mod (d);
260 dy->locked = 1;
261 }
262
263 DECLARE_INLINE_HEADER (
264 void
265 Dynarr_unlock (void *d)
266 )
267 {
268 Dynarr *dy = Dynarr_verify (d);
269 assert (dy->locked);
270 dy->locked = 0;
271 }
272
273 #else /* not ERROR_CHECK_DYNARR */
274
275 #define Dynarr_verify(d) ((Dynarr *) d)
276 #define Dynarr_verify_mod(d) ((Dynarr *) d)
277 #define Dynarr_lock(d) DO_NOTHING
278 #define Dynarr_unlock(d) DO_NOTHING
279
280 #endif /* ERROR_CHECK_DYNARR */
281
282 /************* Dynarr creation *************/
283
284 MODULE_API void *Dynarr_newf (Bytecount elsize);
285 MODULE_API void Dynarr_free (void *d);
286
287 #ifdef NEW_GC
288 MODULE_API void *Dynarr_lisp_newf (Bytecount elsize,
289 const struct lrecord_implementation
290 *dynarr_imp,
291 const struct lrecord_implementation *imp);
292
293 #define Dynarr_lisp_new(type, dynarr_imp, imp) \
294 ((type##_dynarr *) Dynarr_lisp_newf (sizeof (type), dynarr_imp, imp))
295 #define Dynarr_lisp_new2(dynarr_type, type, dynarr_imp, imp) \
296 ((dynarr_type *) Dynarr_lisp_newf (sizeof (type)), dynarr_imp, imp)
297 #endif /* NEW_GC */
298 #define Dynarr_new(type) ((type##_dynarr *) Dynarr_newf (sizeof (type)))
299 #define Dynarr_new2(dynarr_type, type) \
300 ((dynarr_type *) Dynarr_newf (sizeof (type)))
301
302 /************* Dynarr access *************/
303
304 #ifdef ERROR_CHECK_DYNARR
305 #define Dynarr_at(d, pos) \
306 ((d)->base[Dynarr_verify_pos_at (d, pos, __FILE__, __LINE__)])
307 #define Dynarr_atp_allow_end(d, pos) \
308 (&((d)->base[Dynarr_verify_pos_atp_allow_end (d, pos, __FILE__, __LINE__)]))
309 #define Dynarr_atp(d, pos) \
310 (&((d)->base[Dynarr_verify_pos_atp (d, pos, __FILE__, __LINE__)]))
311 #else
312 #define Dynarr_at(d, pos) ((d)->base[pos])
313 #define Dynarr_atp(d, pos) (&Dynarr_at (d, pos))
314 #define Dynarr_atp_allow_end(d, pos) Dynarr_atp (d, pos)
315 #endif
316
317 /* Old #define Dynarr_atp(d, pos) (&Dynarr_at (d, pos)) */
318 #define Dynarr_begin(d) Dynarr_atp (d, 0)
319 #define Dynarr_lastp(d) Dynarr_atp (d, Dynarr_length (d) - 1)
320 #define Dynarr_past_lastp(d) Dynarr_atp_allow_end (d, Dynarr_length (d))
321
322
323 /************* Dynarr length/size retrieval and setting *************/
324
325 /* Retrieve the length of a dynarr. The `+ 0' is to ensure that this cannot
326 be used as an lvalue. */
327 #define Dynarr_length(d) (Dynarr_verify (d)->len_ + 0)
328 /* Retrieve the largest ever length seen of a dynarr. The `+ 0' is to
329 ensure that this cannot be used as an lvalue. */
330 #define Dynarr_largest(d) (Dynarr_verify (d)->largest_ + 0)
331 /* Retrieve the number of elements that fit in the currently allocated
332 space. The `+ 0' is to ensure that this cannot be used as an lvalue. */
333 #define Dynarr_max(d) (Dynarr_verify (d)->max_ + 0)
334 /* Return the size in bytes of an element in a dynarr. */
335 #define Dynarr_elsize(d) (Dynarr_verify (d)->elsize_ + 0)
336 /* Retrieve the advertised memory usage of a dynarr, i.e. the number of
337 bytes occupied by the elements in the dynarr, not counting any overhead. */
338 #define Dynarr_sizeof(d) (Dynarr_length (d) * Dynarr_elsize (d))
339
340 /* Actually set the length of a dynarr. This is a low-level routine that
341 should not be directly used; use Dynarr_set_length() or
342 Dynarr_set_lengthr() instead. */
343 DECLARE_INLINE_HEADER (
344 void
345 Dynarr_set_length_1 (void *d, Elemcount len)
346 )
347 {
348 Dynarr *dy = Dynarr_verify_mod (d);
349 dynarr_checking_assert (len >= 0 && len <= Dynarr_max (dy));
350 /* Use the raw field references here otherwise we get a crash because
351 we've set the length but not yet fixed up the largest value. */
352 dy->len_ = len;
353 if (dy->len_ > dy->largest_)
354 dy->largest_ = dy->len_;
355 (void) Dynarr_verify_mod (d);
356 }
357
358 /* "Restricted set-length": Set the length of dynarr D to LEN,
359 which must be in the range [0, Dynarr_largest(d)]. */
360
361 DECLARE_INLINE_HEADER (
362 void
363 Dynarr_set_lengthr (void *d, Elemcount len)
364 )
365 {
366 Dynarr *dy = Dynarr_verify_mod (d);
367 dynarr_checking_assert (len >= 0 && len <= Dynarr_largest (dy));
368 Dynarr_set_length_1 (dy, len);
369 }
370
371 /* "Restricted increment": Increment the length of dynarr D by 1; the resulting
372 length must be in the range [0, Dynarr_largest(d)]. */
373
374 #define Dynarr_incrementr(d) Dynarr_set_lengthr (d, Dynarr_length (d) + 1)
375
376
377 MODULE_API void Dynarr_resize (void *d, Elemcount size);
378
379 DECLARE_INLINE_HEADER (
380 void
381 Dynarr_resize_to_fit (void *d, Elemcount size)
382 )
383 {
384 Dynarr *dy = Dynarr_verify_mod (d);
385 if (size > Dynarr_max (dy))
386 Dynarr_resize (dy, size);
387 }
388
389 #define Dynarr_resize_to_add(d, numels) \
390 Dynarr_resize_to_fit (d, Dynarr_length (d) + numels)
391
392 /* This is an optimization. This is like Dynarr_set_length() but the length
393 is guaranteed to be at least as big as the existing length. */
394
395 DECLARE_INLINE_HEADER (
396 void
397 Dynarr_increase_length (void *d, Elemcount len)
398 )
399 {
400 Dynarr *dy = Dynarr_verify_mod (d);
401 dynarr_checking_assert (len >= Dynarr_length (dy));
402 Dynarr_resize_to_fit (dy, len);
403 Dynarr_set_length_1 (dy, len);
404 }
405
406 /* Set the length of dynarr D to LEN. If the length increases, resize as
407 necessary to fit. (NOTE: This will leave uninitialized memory. If you
408 aren't planning on immediately overwriting the memory, use
409 Dynarr_set_length_and_zero() to zero out all the memory that would
410 otherwise be uninitialized.) */
411
412 DECLARE_INLINE_HEADER (
413 void
414 Dynarr_set_length (void *d, Elemcount len)
415 )
416 {
417 Dynarr *dy = Dynarr_verify_mod (d);
418 Elemcount old_len = Dynarr_length (dy);
419 if (old_len >= len)
420 Dynarr_set_lengthr (dy, len);
421 else
422 Dynarr_increase_length (d, len);
423 }
424
425 #define Dynarr_increment(d) Dynarr_increase_length (d, Dynarr_length (d) + 1)
426
427 /* Zero LEN contiguous elements starting at POS. */
428
429 DECLARE_INLINE_HEADER (
430 void
431 Dynarr_zero_many (void *d, Elemcount pos, Elemcount len)
432 )
433 {
434 Dynarr *dy = Dynarr_verify_mod (d);
435 memset ((Rawbyte *) dy->base + pos*Dynarr_elsize (dy), 0,
436 len*Dynarr_elsize (dy));
437 }
438
439 /* This is an optimization. This is like Dynarr_set_length_and_zero() but
440 the length is guaranteed to be at least as big as the existing
441 length. */
442
443 DECLARE_INLINE_HEADER (
444 void
445 Dynarr_increase_length_and_zero (void *d, Elemcount len)
446 )
447 {
448 Dynarr *dy = Dynarr_verify_mod (d);
449 Elemcount old_len = Dynarr_length (dy);
450 Dynarr_increase_length (dy, len);
451 Dynarr_zero_many (dy, old_len, len - old_len);
452 }
453
454 /* Set the length of dynarr D to LEN. If the length increases, resize as
455 necessary to fit and zero out all the elements between the old and new
456 lengths. */
457
458 DECLARE_INLINE_HEADER (
459 void
460 Dynarr_set_length_and_zero (void *d, Elemcount len)
461 )
462 {
463 Dynarr *dy = Dynarr_verify_mod (d);
464 Elemcount old_len = Dynarr_length (dy);
465 if (old_len >= len)
466 Dynarr_set_lengthr (dy, len);
467 else
468 Dynarr_increase_length_and_zero (d, len);
469 }
470
471 /* Reset the dynarr's length to 0. */
472 #define Dynarr_reset(d) Dynarr_set_lengthr (d, 0)
473
474 #ifdef MEMORY_USAGE_STATS
475 struct usage_stats;
476 Bytecount Dynarr_memory_usage (void *d, struct usage_stats *stats);
477 #endif
478
479 /************* Adding/deleting elements to/from a dynarr *************/
480
481 /* Set the Lisp implementation of the element at POS in dynarr D. Only
482 does this if the dynarr holds Lisp objects of a particular type (the
483 objects themselves, not pointers to them), and only under NEW_GC. */
484
485 #ifdef NEW_GC
486 #define DYNARR_SET_LISP_IMP(d, pos) \
487 do { \
488 if ((d)->lisp_imp) \
489 set_lheader_implementation \
490 ((struct lrecord_header *)&(((d)->base)[pos]), (d)->lisp_imp); \
491 } while (0)
492 #else
493 #define DYNARR_SET_LISP_IMP(d, pos) DO_NOTHING
494 #endif /* (not) NEW_GC */
495
496 /* Add Element EL to the end of dynarr D. */
497
498 #define Dynarr_add(d, el) \
499 do { \
500 Elemcount _da_pos = Dynarr_length (d); \
501 (void) Dynarr_verify_mod (d); \
502 Dynarr_increment (d); \
503 ((d)->base)[_da_pos] = (el); \
504 DYNARR_SET_LISP_IMP (d, _da_pos); \
505 } while (0)
506
507 /* Set EL as the element at position POS in dynarr D.
508 Expand the dynarr as necessary so that its length is enough to include
509 position POS within it, and zero out any new elements created as a
510 result of expansion, other than the one at POS. */
511
512 #define Dynarr_set(d, pos, el) \
513 do { \
514 Elemcount _ds_pos = (pos); \
515 (void) Dynarr_verify_mod (d); \
516 if (Dynarr_length (d) < _ds_pos + 1) \
517 Dynarr_increase_length_and_zero (d, _ds_pos + 1); \
518 ((d)->base)[_ds_pos] = (el); \
519 DYNARR_SET_LISP_IMP (d, _ds_pos); \
520 } while (0)
521
522 /* Add LEN contiguous elements, stored at BASE, to dynarr D. If BASE is
523 NULL, reserve space but don't store anything. */
524
525 DECLARE_INLINE_HEADER (
526 void
527 Dynarr_add_many (void *d, const void *base, Elemcount len)
528 )
529 {
530 /* This duplicates Dynarr_insert_many to some extent; but since it is
531 called so often, it seemed useful to remove the unnecessary stuff
532 from that function and to make it inline */
533 Dynarr *dy = Dynarr_verify_mod (d);
534 Elemcount pos = Dynarr_length (dy);
535 Dynarr_increase_length (dy, Dynarr_length (dy) + len);
536 if (base)
537 memcpy ((Rawbyte *) dy->base + pos*Dynarr_elsize (dy), base,
538 len*Dynarr_elsize (dy));
539 }
540
541 /* Insert LEN elements, currently pointed to by BASE, into dynarr D
542 starting at position POS. */
543
544 MODULE_API void Dynarr_insert_many (void *d, const void *base, Elemcount len,
545 Elemcount pos);
546
547 /* Prepend LEN elements, currently pointed to by BASE, to the beginning. */
548
549 #define Dynarr_prepend_many(d, base, len) Dynarr_insert_many (d, base, len, 0)
550
551 /* Add literal string S to dynarr D, which should hold chars or unsigned
552 chars. The final zero byte is not stored. */
553
554 #define Dynarr_add_literal_string(d, s) Dynarr_add_many (d, s, sizeof (s) - 1)
555
556 /* Convert Lisp string S to an external encoding according to CODESYS and
557 add to dynarr D, which should hold chars or unsigned chars. No final
558 zero byte is appended. */
559
560 /* #### This should be an inline function but LISP_STRING_TO_SIZED_EXTERNAL
561 isn't declared yet. */
562
563 #define Dynarr_add_ext_lisp_string(d, s, codesys) \
564 do { \
565 Lisp_Object dyna_ls_s = (s); \
566 Lisp_Object dyna_ls_cs = (codesys); \
567 Extbyte *dyna_ls_eb; \
568 Bytecount dyna_ls_bc; \
569 \
570 LISP_STRING_TO_SIZED_EXTERNAL (dyna_ls_s, dyna_ls_eb, \
571 dyna_ls_bc, dyna_ls_cs); \
572 Dynarr_add_many (d, dyna_ls_eb, dyna_ls_bc); \
573 } while (0)
574
575 /* Delete LEN elements starting at position POS. */
576
577 MODULE_API void Dynarr_delete_many (void *d, Elemcount pos, Elemcount len);
578
579 /* Pop off (i.e. delete) the last element from the dynarr and return it */
580
581 #define Dynarr_pop(d) \
582 (dynarr_checking_assert (Dynarr_length (d) > 0), \
583 Dynarr_verify_mod (d)->len_--, \
584 Dynarr_at (d, Dynarr_length (d)))
585
586 /* Delete the item at POS */
587
588 #define Dynarr_delete(d, pos) Dynarr_delete_many (d, pos, 1)
589
590 /* Delete the item located at memory address P, which must be a `type *'
591 pointer, where `type' is the type of the elements of the dynarr. */
592 #define Dynarr_delete_by_pointer(d, p) \
593 Dynarr_delete_many (d, (p) - ((d)->base), 1)
594
595 /* Delete all elements that are numerically equal to EL. */
596
597 #define Dynarr_delete_object(d, el) \
598 do \
599 { \
600 REGISTER int i; \
601 for (i = Dynarr_length (d) - 1; i >= 0; i--) \
602 { \
603 if (el == Dynarr_at (d, i)) \
604 Dynarr_delete_many (d, i, 1); \
605 } \
606 } while (0)
607
608
609 /************************************************************************/
610 /** Stack-like malloc/free **/
611 /************************************************************************/
612
613 void *stack_like_malloc (Bytecount size);
614 void stack_like_free (void *val);
615
616
617
618 /************************************************************************/
619 /** Gap array **/
620 /************************************************************************/
621
622 /* Holds a marker that moves as elements in the array are inserted and
623 deleted, similar to standard markers. */
624
625 typedef struct gap_array_marker
626 {
627 #ifdef NEW_GC
628 NORMAL_LISP_OBJECT_HEADER header;
629 #endif /* NEW_GC */
630 int pos;
631 struct gap_array_marker *next;
632 } Gap_Array_Marker;
633
634
635 /* Holds a "gap array", which is an array of elements with a gap located
636 in it. Insertions and deletions with a high degree of locality
637 are very fast, essentially in constant time. Array positions as
638 used and returned in the gap array functions are independent of
639 the gap. */
640
641 /* Layout of gap array:
642
643 <------ gap ------><---- gapsize ----><----- numels - gap ---->
644 <---------------------- numels + gapsize --------------------->
645
646 For marking purposes, we use two extra variables computed from
647 the others -- the offset to the data past the gap, plus the number
648 of elements in that data:
649
650 offset_past_gap = elsize * (gap + gapsize)
651 els_past_gap = numels - gap
652 */
653
654
655 typedef struct gap_array
656 {
657 #ifdef NEW_GC
658 NORMAL_LISP_OBJECT_HEADER header;
659 int is_lisp;
660 #endif /* NEW_GC */
661 Elemcount gap;
662 Elemcount gapsize;
663 Elemcount numels;
664 Bytecount elsize;
665 /* Redundant numbers computed from the others, for marking purposes */
666 Bytecount offset_past_gap;
667 Elemcount els_past_gap;
668 Gap_Array_Marker *markers;
669 /* this is a stretchy array */
670 char array[1];
671 } Gap_Array;
672
673 #ifdef NEW_GC
674 struct gap_array_marker;
675
676 DECLARE_LISP_OBJECT (gap_array_marker, struct gap_array_marker);
677 #define XGAP_ARRAY_MARKER(x) \
678 XRECORD (x, gap_array_marker, struct gap_array_marker)
679 #define wrap_gap_array_marker(p) wrap_record (p, gap_array_marker)
680 #define GAP_ARRAY_MARKERP(x) RECORDP (x, gap_array_marker)
681 #define CHECK_GAP_ARRAY_MARKER(x) CHECK_RECORD (x, gap_array_marker)
682 #define CONCHECK_GAP_ARRAY_MARKER(x) CONCHECK_RECORD (x, gap_array_marker)
683
684 struct gap_array;
685
686 DECLARE_LISP_OBJECT (gap_array, struct gap_array);
687 #define XGAP_ARRAY(x) XRECORD (x, gap_array, struct gap_array)
688 #define wrap_gap_array(p) wrap_record (p, gap_array)
689 #define GAP_ARRAYP(x) RECORDP (x, gap_array)
690 #define CHECK_GAP_ARRAY(x) CHECK_RECORD (x, gap_array)
691 #define CONCHECK_GAP_ARRAY(x) CONCHECK_RECORD (x, gap_array)
692 #endif /* NEW_GC */
693
694 #ifdef NEW_GC
695 #define XD_GAP_ARRAY_MARKER_DESC \
696 { XD_LISP_OBJECT, offsetof (Gap_Array, markers) }
697 #else /* not NEW_GC */
698 #define XD_GAP_ARRAY_MARKER_DESC \
699 { XD_BLOCK_PTR, offsetof (Gap_Array, markers), 1, \
700 { &gap_array_marker_description }, XD_FLAG_NO_KKCC }
701 #endif /* not NEW_GC */
702
703 #define XD_GAP_ARRAY_DESC(sub_desc) \
704 { XD_ELEMCOUNT, offsetof (Gap_Array, gap) }, \
705 { XD_BYTECOUNT, offsetof (Gap_Array, offset_past_gap) }, \
706 { XD_ELEMCOUNT, offsetof (Gap_Array, els_past_gap) }, \
707 XD_GAP_ARRAY_MARKER_DESC, \
708 { XD_BLOCK_ARRAY, offsetof (Gap_Array, array), XD_INDIRECT (0, 0), \
709 { sub_desc } }, \
710 { XD_BLOCK_ARRAY, XD_INDIRECT (1, offsetof (Gap_Array, array)), \
711 XD_INDIRECT (2, 0), { sub_desc } }
712
713 /* Convert a "memory position" (i.e. taking the gap into account) into
714 the address of the element at (i.e. after) that position. "Memory
715 positions" are only used internally and are of type Memxpos.
716 "Array positions" are used externally and are of type Elemcount. */
717 #define GAP_ARRAY_MEMEL_ADDR(ga, memel) ((ga)->array + (ga)->elsize*(memel))
718
719 /* Number of elements currently in a gap array */
720 #define gap_array_length(ga) ((ga)->numels)
721
722 #define gap_array_gappos(ga) ((ga)->gap)
723 #define gap_array_gapsize(ga) ((ga)->gapsize)
724
725 #define GAP_ARRAY_ARRAY_TO_MEMORY_POS_1(pos, gappos, gapsize) \
726 ((pos) < gappos ? (pos) : (pos) + gapsize)
727
728 #define GAP_ARRAY_ARRAY_TO_MEMORY_POS(ga, pos) \
729 GAP_ARRAY_ARRAY_TO_MEMORY_POS_1 (pos, (ga)->gap, (ga)->gapsize)
730
731 #define GAP_ARRAY_MEMORY_TO_ARRAY_POS(ga, pos) \
732 ((pos) <= (ga)->gap ? (pos) : (pos) - (ga)->gapsize)
733
734 /* Return a pointer to the element at a given position. */
735 #define gap_array_atp(ga, pos, type) \
736 ((type *) GAP_ARRAY_MEMEL_ADDR (ga, GAP_ARRAY_ARRAY_TO_MEMORY_POS (ga, pos)))
737
738 /* Return the element at a given position. */
739 #define gap_array_at(ga, pos, type) (*gap_array_atp (ga, pos, type))
740
741 /* Return a pointer to the beginning of memory storage for the gap array.
742 Note this is NOT the same as gap_array_atp(ga, 0, type) because that
743 will skip forward past the gap if the gap is at position 0. */
744 #define gap_array_begin(ga, type) ((type *) ((ga)->array))
745
746 #ifndef NEW_GC
747 extern const struct sized_memory_description lispobj_gap_array_description;
748 extern const struct sized_memory_description gap_array_marker_description;
749 #endif
750
751 Bytecount gap_array_byte_size (Gap_Array *ga);
752 Gap_Array *gap_array_insert_els (Gap_Array *ga, Elemcount pos, void *elptr,
753 Elemcount numels);
754 void gap_array_delete_els (Gap_Array *ga, Elemcount from, Elemcount numdel);
755 #define gap_array_delete_all_els(ga) \
756 gap_array_delete_els (ga, 0, gap_array_length (ga))
757 Gap_Array_Marker *gap_array_make_marker (Gap_Array *ga, Elemcount pos);
758 void gap_array_delete_marker (Gap_Array *ga, Gap_Array_Marker *m);
759 void gap_array_delete_all_markers (Gap_Array *ga);
760 void gap_array_move_marker (Gap_Array *ga, Gap_Array_Marker *m, Elemcount pos);
761 #define gap_array_marker_pos(ga, m) \
762 GAP_ARRAY_MEMORY_TO_ARRAY_POS (ga, (m)->pos)
763 Gap_Array *make_gap_array (Elemcount elsize, int USED_IF_NEW_GC (do_lisp));
764 Gap_Array *gap_array_clone (Gap_Array *ga);
765 void free_gap_array (Gap_Array *ga);
766
767 #endif /* INCLUDED_lrecordt_h_ */