Mercurial > hg > xemacs-beta

comparison src/array.h @ 5495:1f0b15040456

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