1. xemacs
  2. xemacs-beta

Source

xemacs-beta / src / array.h

  1
  2
  3
  4
  5
  6
  7
  8
  9
 10
 11
 12
 13
 14
 15
 16
 17
 18
 19
 20
 21
 22
 23
 24
 25
 26
 27
 28
 29
 30
 31
 32
 33
 34
 35
 36
 37
 38
 39
 40
 41
 42
 43
 44
 45
 46
 47
 48
 49
 50
 51
 52
 53
 54
 55
 56
 57
 58
 59
 60
 61
 62
 63
 64
 65
 66
 67
 68
 69
 70
 71
 72
 73
 74
 75
 76
 77
 78
 79
 80
 81
 82
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
360
361
362
363
364
365
366
367
368
369
370
371
372
373
374
375
376
377
378
379
380
381
382
383
384
385
386
387
388
389
390
391
392
393
394
395
396
397
398
399
400
401
402
403
404
405
406
407
408
409
410
411
412
413
414
415
416
417
418
419
420
421
422
423
424
425
426
427
428
429
430
431
432
433
434
435
436
437
438
439
440
441
442
443
444
445
446
447
448
449
450
451
452
453
454
455
456
457
458
459
460
461
462
463
464
465
466
467
468
469
470
471
472
473
474
475
476
477
478
479
480
481
482
483
484
485
486
487
488
489
490
491
492
493
494
495
496
497
498
499
500
501
502
503
504
505
506
507
508
509
510
511
512
513
514
515
516
517
518
519
520
521
522
523
524
525
526
527
528
529
530
531
532
533
534
535
536
537
538
539
540
541
542
543
544
545
546
547
548
549
550
551
552
553
554
555
556
557
558
559
560
561
562
563
564
565
566
567
568
569
570
571
572
573
574
575
576
577
578
579
580
581
582
583
584
585
586
587
588
589
590
591
592
593
594
595
596
597
598
599
600
601
602
603
604
605
606
607
608
609
610
611
612
613
614
615
616
617
618
619
620
621
622
623
624
625
626
627
628
629
630
631
632
633
634
635
636
637
638
639
640
641
642
643
644
645
646
647
648
649
650
651
652
653
654
655
656
657
658
659
660
661
662
663
664
665
666
667
668
669
670
671
672
673
674
675
676
677
678
679
680
681
682
683
684
685
686
687
688
689
690
691
692
693
694
695
696
697
698
699
700
701
702
703
704
705
706
707
708
709
710
711
712
713
714
715
716
717
718
719
720
721
722
723
724
725
726
727
728
729
730
731
732
733
734
735
736
737
738
739
740
741
742
743
744
745
746
747
748
749
750
751
752
753
754
755
756
757
758
759
760
761
762
763
764
765
766
767
768
769
/* Header for arrays (dynarrs, gap arrays, etc.).
   Copyright (C) 1993, 1994, 1995 Free Software Foundation, Inc.
   Copyright (C) 1996, 2001, 2002, 2004, 2005, 2009, 2010 Ben Wing.

This file is part of XEmacs.

XEmacs is free software; you can redistribute it and/or modify it
under the terms of the GNU General Public License as published by the
Free Software Foundation; either version 2, or (at your option) any
later version.

XEmacs is distributed in the hope that it will be useful, but WITHOUT
ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
FITNESS FOR A PARTICULAR PURPOSE.  See the GNU General Public License
for more details.

You should have received a copy of the GNU General Public License
along with XEmacs; see the file COPYING.  If not, write to
the Free Software Foundation, Inc., 59 Temple Place - Suite 330,
Boston, MA 02111-1307, USA.  */

/* Synched up with: Not in FSF. */

/* This file has been Mule-ized, Ben Wing, 10-13-04. */

#ifndef INCLUDED_array_h_
#define INCLUDED_array_h_

/************************************************************************/
/**               Definition of dynamic arrays (dynarrs)               **/
/************************************************************************/

BEGIN_C_DECLS

/************* Dynarr declaration *************/

#ifdef NEW_GC
#define DECLARE_DYNARR_LISP_IMP()			\
  const struct lrecord_implementation *lisp_imp;
#else
#define DECLARE_DYNARR_LISP_IMP()
#endif

#ifdef ERROR_CHECK_DYNARR
#define DECLARE_DYNARR_LOCKED()				\
  int locked;
#else
#define DECLARE_DYNARR_LOCKED()
#endif

#define Dynarr_declare(type)			\
  struct lrecord_header header;			\
  type *base;					\
  DECLARE_DYNARR_LISP_IMP ()			\
  DECLARE_DYNARR_LOCKED ()			\
  int elsize_;					\
  int len_;					\
  int largest_;					\
  int max_

typedef struct dynarr
{
  Dynarr_declare (void);
} Dynarr;

#define XD_DYNARR_DESC(base_type, sub_desc)				\
  { XD_BLOCK_PTR, offsetof (base_type, base),				\
    XD_INDIRECT(1, 0), {sub_desc} },					\
  { XD_INT,        offsetof (base_type, len_) },			\
  { XD_INT_RESET,  offsetof (base_type, largest_), XD_INDIRECT(1, 0) },	\
  { XD_INT_RESET,  offsetof (base_type, max_), XD_INDIRECT(1, 0) }

#ifdef NEW_GC
#define XD_LISP_DYNARR_DESC(base_type, sub_desc)			\
  { XD_INLINE_LISP_OBJECT_BLOCK_PTR, offsetof (base_type, base),		\
    XD_INDIRECT(1, 0), {sub_desc} },					\
  { XD_INT,        offsetof (base_type, len_) },			\
  { XD_INT_RESET,  offsetof (base_type, largest_), XD_INDIRECT(1, 0) },	\
  { XD_INT_RESET,  offsetof (base_type, max_), XD_INDIRECT(1, 0) }
#endif /* NEW_GC */

/************* Dynarr verification *************/

/* Dynarr locking and verification.

   [I] VERIFICATION

   Verification routines simply return their basic argument, possibly
   casted, but in the process perform some verification on it, aborting if
   the verification fails.  The verification routines take FILE and LINE
   parameters, and use them to output the file and line of the caller
   when an abort occurs, rather than the file and line of the inline
   function, which is less than useful.

   There are three basic types of verification routines:

   (1) Verify the dynarr itself.  This verifies the basic invariant
   involving the length/size values:

   0 <= Dynarr_length(d) <= Dynarr_largest(d) <= Dynarr_max(d)

   (2) Verify the dynarr itself prior to modifying it.  This performs
   the same verification as previously, but also checks that the
   dynarr is not locked (see below).

   (3) Verify a dynarr position.  Unfortunately we have to have
   different verification routines depending on which kind of operation
   is being performed:

   (a) For Dynarr_at(), we check that the POS is bounded by Dynarr_largest(),
       i.e. 0 <= POS < Dynarr_largest().
   (b) For Dynarr_atp_allow_end(), we also have to allow
       POS == Dynarr_largest().
   (c) For Dynarr_atp(), we behave largely like Dynarr_at() but make a
       special exception when POS == 0 and Dynarr_largest() == 0 -- see
       comment below.
   (d) Some other routines contain the POS verification within their code,
       and make the check 0 <= POS < Dynarr_length() or
       0 <= POS <= Dynarr_length().

   #### It is not well worked-out whether and in what circumstances it's
   allowed to use a position that is between Dynarr_length() and
   Dynarr_largest().  The ideal solution is to never allow this, and require
   instead that code first change the length before accessing higher
   positions.  That would require looking through all the code that accesses
   dynarrs and fixing it appropriately (especially redisplay code, and
   especially redisplay code in the vicinity of a reference to
   Dynarr_largest(), since such code usually checks explicitly to see whether
   there is extra stuff between Dynarr_length() and Dynarr_largest().)

   [II] LOCKING

   The idea behind dynarr locking is simple: Locking a dynarr prevents
   any modification from occurring, or rather, leads to an abort upon
   any attempt to modify a dynarr.

   Dynarr locking was originally added to catch some sporadic and hard-to-
   debug crashes in the redisplay code where dynarrs appeared to be getting
   corrupted in an unexpected fashion.  The solution was to lock the
   dynarrs that were getting corrupted (in this case, the display-line
   dynarrs) around calls to routines that weren't supposed to be changing
   these dynarrs but might somehow be calling code that modified them.
   This eventually revealed that there was a reentrancy problem with
   redisplay that involved the QUIT mechanism and the processing done in
   order to determine whether C-g had been pressed -- this processing
   involves retrieving, processing and queueing pending events to see
   whether any of them result in a C-g keypress.  However, at least under
   MS Windows this can result in redisplay being called reentrantly.
   For more info:--
   
  (Info-goto-node "(internals)Critical Redisplay Sections")

*/

#ifdef ERROR_CHECK_DYNARR
DECLARE_INLINE_HEADER (
int
Dynarr_verify_pos_at (void *d, Elemcount pos, const Ascbyte *file, int line)
)
{
  Dynarr *dy = (Dynarr *) d;
  /* We use `largest', not `len', because the redisplay code often
     accesses stuff between len and largest. */
  assert_at_line (pos >= 0 && pos < dy->largest_, file, line);
  return pos;
}

DECLARE_INLINE_HEADER (
int
Dynarr_verify_pos_atp (void *d, Elemcount pos, const Ascbyte *file, int line)
)
{
  Dynarr *dy = (Dynarr *) d;
  /* We use `largest', not `len', because the redisplay code often
     accesses stuff between len and largest. */
  /* [[ Code will often do something like ...

     val = make_bit_vector_from_byte_vector (Dynarr_atp (dyn, 0),
	                                     Dynarr_length (dyn));

     which works fine when the Dynarr_length is non-zero, but when zero,
     the result of Dynarr_atp() not only points past the end of the
     allocated array, but the array may not have ever been allocated and
     hence the return value is NULL.  But the length of 0 causes the
     pointer to never get checked.  These can occur throughout the code
     so we put in a special check. --ben ]]

     Update: The common idiom `Dynarr_atp (dyn, 0)' has been changed to
     `Dynarr_begin (dyn)'.  Possibly this special check at POS 0 can be
     done only for Dynarr_begin() not for general Dynarr_atp(). --ben */
  if (pos == 0 && dy->len_ == 0)
    return pos;
  /* #### It's vaguely possible that some code could legitimately want to
     retrieve a pointer to the position just past the end of dynarr memory.
     This could happen with Dynarr_atp() but not Dynarr_at().  If so, it
     will trigger this assert().  In such cases, it should be obvious that
     the code wants to do this; rather than relaxing the assert, we should
     probably create a new macro Dynarr_atp_allow_end() which is like
     Dynarr_atp() but which allows for pointing at invalid addresses -- we
     really want to check for cases of accessing just past the end of
     memory, which is a likely off-by-one problem to occur and will usually
     not trigger a protection fault (instead, you'll just get random
     behavior, possibly overwriting other memory, which is bad). --ben */
  assert_at_line (pos >= 0 && pos < dy->largest_, file, line);
  return pos;
}

DECLARE_INLINE_HEADER (
int
Dynarr_verify_pos_atp_allow_end (void *d, Elemcount pos, const Ascbyte *file,
				 int line)
)
{
  Dynarr *dy = (Dynarr *) d;
  /* We use `largest', not `len', because the redisplay code often
     accesses stuff between len and largest.
     We also allow referencing the very end, past the end of allocated
     legitimately space.  See comments in Dynarr_verify_pos_atp.()*/
  assert_at_line (pos >= 0 && pos <= dy->largest_, file, line);
  return pos;
}

#else
#define Dynarr_verify_pos_at(d, pos, file, line) (pos)
#define Dynarr_verify_pos_atp(d, pos, file, line) (pos)
#define Dynarr_verify_pos_atp_allow_end(d, pos, file, line) (pos)
#endif /* ERROR_CHECK_DYNARR */

#ifdef ERROR_CHECK_DYNARR
DECLARE_INLINE_HEADER (
Dynarr *
Dynarr_verify_1 (void *d, const Ascbyte *file, int line)
)
{
  Dynarr *dy = (Dynarr *) d;
  assert_at_line (dy->len_ >= 0 && dy->len_ <= dy->largest_ &&
		  dy->largest_ <= dy->max_, file, line);
  return dy;
}

DECLARE_INLINE_HEADER (
Dynarr *
Dynarr_verify_mod_1 (void *d, const Ascbyte *file, int line)
)
{
  Dynarr *dy = (Dynarr *) d;
  assert_at_line (!dy->locked, file, line);
  return Dynarr_verify_1 (d, file, line);
}

#define Dynarr_verify(d) Dynarr_verify_1 (d, __FILE__, __LINE__)
#define Dynarr_verify_mod(d) Dynarr_verify_mod_1 (d, __FILE__, __LINE__)

DECLARE_INLINE_HEADER (
void
Dynarr_lock (void *d)
)
{
  Dynarr *dy = Dynarr_verify_mod (d);
  dy->locked = 1;
}

DECLARE_INLINE_HEADER (
void
Dynarr_unlock (void *d)
)
{
  Dynarr *dy = Dynarr_verify (d);
  assert (dy->locked);
  dy->locked = 0;
}

#else /* not ERROR_CHECK_DYNARR */

#define Dynarr_verify(d) ((Dynarr *) d)
#define Dynarr_verify_mod(d) ((Dynarr *) d)
#define Dynarr_lock(d) DO_NOTHING
#define Dynarr_unlock(d) DO_NOTHING

#endif /* ERROR_CHECK_DYNARR */

/************* Dynarr creation *************/

MODULE_API void *Dynarr_newf (Bytecount elsize);
MODULE_API void Dynarr_free (void *d);

#ifdef NEW_GC
MODULE_API void *Dynarr_lisp_newf (Bytecount elsize,
				   const struct lrecord_implementation 
				   *dynarr_imp,
				   const struct lrecord_implementation *imp);

#define Dynarr_lisp_new(type, dynarr_imp, imp)			\
  ((type##_dynarr *) Dynarr_lisp_newf (sizeof (type), dynarr_imp, imp))
#define Dynarr_lisp_new2(dynarr_type, type, dynarr_imp, imp)	\
  ((dynarr_type *) Dynarr_lisp_newf (sizeof (type)), dynarr_imp, imp)
#endif /* NEW_GC */
#define Dynarr_new(type) ((type##_dynarr *) Dynarr_newf (sizeof (type)))
#define Dynarr_new2(dynarr_type, type) \
  ((dynarr_type *) Dynarr_newf (sizeof (type)))

/************* Dynarr access *************/

#ifdef ERROR_CHECK_DYNARR
#define Dynarr_at(d, pos) \
  ((d)->base[Dynarr_verify_pos_at (d, pos, __FILE__, __LINE__)])
#define Dynarr_atp_allow_end(d, pos) \
  (&((d)->base[Dynarr_verify_pos_atp_allow_end (d, pos, __FILE__, __LINE__)]))
#define Dynarr_atp(d, pos) \
  (&((d)->base[Dynarr_verify_pos_atp (d, pos, __FILE__, __LINE__)]))
#else
#define Dynarr_at(d, pos) ((d)->base[pos])
#define Dynarr_atp(d, pos) (&Dynarr_at (d, pos))
#define Dynarr_atp_allow_end(d, pos) Dynarr_atp (d, pos)
#endif

/* Old #define Dynarr_atp(d, pos) (&Dynarr_at (d, pos)) */
#define Dynarr_begin(d) Dynarr_atp (d, 0)
#define Dynarr_lastp(d) Dynarr_atp (d, Dynarr_length (d) - 1)
#define Dynarr_past_lastp(d) Dynarr_atp_allow_end (d, Dynarr_length (d))


/************* Dynarr length/size retrieval and setting *************/

/* Retrieve the length of a dynarr.  The `+ 0' is to ensure that this cannot
   be used as an lvalue. */
#define Dynarr_length(d) (Dynarr_verify (d)->len_ + 0)
/* Retrieve the largest ever length seen of a dynarr.  The `+ 0' is to
   ensure that this cannot be used as an lvalue. */
#define Dynarr_largest(d) (Dynarr_verify (d)->largest_ + 0)
/* Retrieve the number of elements that fit in the currently allocated
   space.  The `+ 0' is to ensure that this cannot be used as an lvalue. */
#define Dynarr_max(d) (Dynarr_verify (d)->max_ + 0)
/* Return the size in bytes of an element in a dynarr. */
#define Dynarr_elsize(d) (Dynarr_verify (d)->elsize_ + 0)
/* Retrieve the advertised memory usage of a dynarr, i.e. the number of
   bytes occupied by the elements in the dynarr, not counting any overhead. */
#define Dynarr_sizeof(d) (Dynarr_length (d) * Dynarr_elsize (d))

/* Actually set the length of a dynarr.  This is a low-level routine that
   should not be directly used; use Dynarr_set_length() or
   Dynarr_set_lengthr() instead. */
DECLARE_INLINE_HEADER (
void
Dynarr_set_length_1 (void *d, Elemcount len)
)
{
  Dynarr *dy = Dynarr_verify_mod (d);
  dynarr_checking_assert (len >= 0 && len <= Dynarr_max (dy));
  /* Use the raw field references here otherwise we get a crash because
     we've set the length but not yet fixed up the largest value. */
  dy->len_ = len;
  if (dy->len_ > dy->largest_)
    dy->largest_ = dy->len_;
  (void) Dynarr_verify_mod (d);
}

/* "Restricted set-length": Set the length of dynarr D to LEN,
    which must be in the range [0, Dynarr_largest(d)]. */

DECLARE_INLINE_HEADER (
void
Dynarr_set_lengthr (void *d, Elemcount len)
)
{
  Dynarr *dy = Dynarr_verify_mod (d);
  dynarr_checking_assert (len >= 0 && len <= Dynarr_largest (dy));
  Dynarr_set_length_1 (dy, len);
}

/* "Restricted increment": Increment the length of dynarr D by 1; the resulting
    length must be in the range [0, Dynarr_largest(d)]. */

#define Dynarr_incrementr(d) Dynarr_set_lengthr (d, Dynarr_length (d) + 1)


MODULE_API void Dynarr_resize (void *d, Elemcount size);

DECLARE_INLINE_HEADER (
void
Dynarr_resize_to_fit (void *d, Elemcount size)
)
{
  Dynarr *dy = Dynarr_verify_mod (d);
  if (size > Dynarr_max (dy))
    Dynarr_resize (dy, size);
}

#define Dynarr_resize_to_add(d, numels)			\
  Dynarr_resize_to_fit (d, Dynarr_length (d) + numels)

/* This is an optimization.  This is like Dynarr_set_length() but the length
   is guaranteed to be at least as big as the existing length. */

DECLARE_INLINE_HEADER (
void
Dynarr_increase_length (void *d, Elemcount len)
)
{
  Dynarr *dy = Dynarr_verify_mod (d);
  dynarr_checking_assert (len >= Dynarr_length (dy));
  Dynarr_resize_to_fit (dy, len);
  Dynarr_set_length_1 (dy, len);
}

/* Set the length of dynarr D to LEN.  If the length increases, resize as
   necessary to fit. (NOTE: This will leave uninitialized memory.  If you
   aren't planning on immediately overwriting the memory, use
   Dynarr_set_length_and_zero() to zero out all the memory that would
   otherwise be uninitialized.) */

DECLARE_INLINE_HEADER (
void
Dynarr_set_length (void *d, Elemcount len)
)
{
  Dynarr *dy = Dynarr_verify_mod (d);
  Elemcount old_len = Dynarr_length (dy);
  if (old_len >= len)
    Dynarr_set_lengthr (dy, len);
  else
    Dynarr_increase_length (d, len);
}

#define Dynarr_increment(d) Dynarr_increase_length (d, Dynarr_length (d) + 1)

/* Zero LEN contiguous elements starting at POS. */

DECLARE_INLINE_HEADER (
void
Dynarr_zero_many (void *d, Elemcount pos, Elemcount len)
)
{
  Dynarr *dy = Dynarr_verify_mod (d);
  memset ((Rawbyte *) dy->base + pos*Dynarr_elsize (dy), 0,
	  len*Dynarr_elsize (dy));
}

/* This is an optimization.  This is like Dynarr_set_length_and_zero() but
   the length is guaranteed to be at least as big as the existing
   length. */

DECLARE_INLINE_HEADER (
void
Dynarr_increase_length_and_zero (void *d, Elemcount len)
)
{
  Dynarr *dy = Dynarr_verify_mod (d);
  Elemcount old_len = Dynarr_length (dy);
  Dynarr_increase_length (dy, len);
  Dynarr_zero_many (dy, old_len, len - old_len);
}

/* Set the length of dynarr D to LEN.  If the length increases, resize as
   necessary to fit and zero out all the elements between the old and new
   lengths. */

DECLARE_INLINE_HEADER (
void
Dynarr_set_length_and_zero (void *d, Elemcount len)
)
{
  Dynarr *dy = Dynarr_verify_mod (d);
  Elemcount old_len = Dynarr_length (dy);
  if (old_len >= len)
    Dynarr_set_lengthr (dy, len);
  else
    Dynarr_increase_length_and_zero (d, len);
}

/* Reset the dynarr's length to 0. */
#define Dynarr_reset(d) Dynarr_set_lengthr (d, 0)

#ifdef MEMORY_USAGE_STATS
struct usage_stats;
Bytecount Dynarr_memory_usage (void *d, struct usage_stats *stats);
#endif

/************* Adding/deleting elements to/from a dynarr *************/

/* Set the Lisp implementation of the element at POS in dynarr D.  Only
   does this if the dynarr holds Lisp objects of a particular type (the
   objects themselves, not pointers to them), and only under NEW_GC. */

#ifdef NEW_GC
#define DYNARR_SET_LISP_IMP(d, pos)					\
do {									\
  if ((d)->lisp_imp)							\
    set_lheader_implementation						\
      ((struct lrecord_header *)&(((d)->base)[pos]), (d)->lisp_imp);	\
} while (0)  
#else
#define DYNARR_SET_LISP_IMP(d, pos) DO_NOTHING
#endif /* (not) NEW_GC */

/* Add Element EL to the end of dynarr D. */

#define Dynarr_add(d, el)			\
do {						\
  Elemcount _da_pos = Dynarr_length (d);	\
  (void) Dynarr_verify_mod (d);			\
  Dynarr_increment (d);				\
  ((d)->base)[_da_pos] = (el);			\
  DYNARR_SET_LISP_IMP (d, _da_pos);		\
} while (0)

/* Set EL as the element at position POS in dynarr D.
   Expand the dynarr as necessary so that its length is enough to include
   position POS within it, and zero out any new elements created as a
   result of expansion, other than the one at POS. */

#define Dynarr_set(d, pos, el)				\
do {							\
  Elemcount _ds_pos = (pos);				\
  (void) Dynarr_verify_mod (d);				\
  if (Dynarr_length (d) < _ds_pos + 1)			\
    Dynarr_increase_length_and_zero (d, _ds_pos + 1);	\
  ((d)->base)[_ds_pos] = (el);				\
  DYNARR_SET_LISP_IMP (d, _ds_pos);			\
} while (0)

/* Add LEN contiguous elements, stored at BASE, to dynarr D.  If BASE is
   NULL, reserve space but don't store anything. */

DECLARE_INLINE_HEADER (
void
Dynarr_add_many (void *d, const void *base, Elemcount len)
)
{
  /* This duplicates Dynarr_insert_many to some extent; but since it is
     called so often, it seemed useful to remove the unnecessary stuff
     from that function and to make it inline */
  Dynarr *dy = Dynarr_verify_mod (d);
  Elemcount pos = Dynarr_length (dy);
  Dynarr_increase_length (dy, Dynarr_length (dy) + len);
  if (base)
    memcpy ((Rawbyte *) dy->base + pos*Dynarr_elsize (dy), base,
	    len*Dynarr_elsize (dy));
}

/* Insert LEN elements, currently pointed to by BASE, into dynarr D
   starting at position POS. */

MODULE_API void Dynarr_insert_many (void *d, const void *base, Elemcount len,
				    Elemcount pos);

/* Prepend LEN elements, currently pointed to by BASE, to the beginning. */

#define Dynarr_prepend_many(d, base, len) Dynarr_insert_many (d, base, len, 0)

/* Add literal string S to dynarr D, which should hold chars or unsigned
   chars.  The final zero byte is not stored. */

#define Dynarr_add_literal_string(d, s) Dynarr_add_many (d, s, sizeof (s) - 1)

/* Convert Lisp string S to an external encoding according to CODESYS and
   add to dynarr D, which should hold chars or unsigned chars.  No final
   zero byte is appended. */

/* #### This should be an inline function but LISP_STRING_TO_SIZED_EXTERNAL
   isn't declared yet. */

#define Dynarr_add_ext_lisp_string(d, s, codesys)		\
do {								\
  Lisp_Object dyna_ls_s = (s);					\
  Lisp_Object dyna_ls_cs = (codesys);				\
  Extbyte *dyna_ls_eb;						\
  Bytecount dyna_ls_bc;						\
								\
  LISP_STRING_TO_SIZED_EXTERNAL (dyna_ls_s, dyna_ls_eb,		\
				 dyna_ls_bc, dyna_ls_cs);	\
  Dynarr_add_many (d, dyna_ls_eb, dyna_ls_bc);			\
} while (0)

/* Delete LEN elements starting at position POS. */

MODULE_API void Dynarr_delete_many (void *d, Elemcount pos, Elemcount len);

/* Pop off (i.e. delete) the last element from the dynarr and return it */

#define Dynarr_pop(d)					\
  (dynarr_checking_assert (Dynarr_length (d) > 0),	\
   Dynarr_verify_mod (d)->len_--,			\
   Dynarr_at (d, Dynarr_length (d)))

/* Delete the item at POS */

#define Dynarr_delete(d, pos) Dynarr_delete_many (d, pos, 1)

/* Delete the item located at memory address P, which must be a `type *'
   pointer, where `type' is the type of the elements of the dynarr. */
#define Dynarr_delete_by_pointer(d, p) \
  Dynarr_delete_many (d, (p) - ((d)->base), 1)

/* Delete all elements that are numerically equal to EL. */

#define Dynarr_delete_object(d, el)		\
do						\
{						\
  REGISTER int i;				\
  for (i = Dynarr_length (d) - 1; i >= 0; i--)	\
    {						\
      if (el == Dynarr_at (d, i))		\
	Dynarr_delete_many (d, i, 1);		\
    }						\
} while (0)


/************************************************************************/
/**                       Stack-like malloc/free                       **/
/************************************************************************/

void *stack_like_malloc (Bytecount size);
void stack_like_free (void *val);



/************************************************************************/
/**                             Gap array                              **/
/************************************************************************/

/* Holds a marker that moves as elements in the array are inserted and
   deleted, similar to standard markers. */

typedef struct gap_array_marker
{
#ifdef NEW_GC
  NORMAL_LISP_OBJECT_HEADER header;
#endif /* NEW_GC */
  int pos;
  struct gap_array_marker *next;
} Gap_Array_Marker;


/* Holds a "gap array", which is an array of elements with a gap located
   in it.  Insertions and deletions with a high degree of locality
   are very fast, essentially in constant time.  Array positions as
   used and returned in the gap array functions are independent of
   the gap. */

/* Layout of gap array:

   <------ gap ------><---- gapsize ----><----- numels - gap ---->
   <---------------------- numels + gapsize --------------------->

   For marking purposes, we use two extra variables computed from
   the others -- the offset to the data past the gap, plus the number
   of elements in that data:

   offset_past_gap = elsize * (gap + gapsize)
   els_past_gap = numels - gap
*/


typedef struct gap_array
{
#ifdef NEW_GC
  NORMAL_LISP_OBJECT_HEADER header;
  int is_lisp;
#endif /* NEW_GC */
  Elemcount gap;
  Elemcount gapsize;
  Elemcount numels;
  Bytecount elsize;
  /* Redundant numbers computed from the others, for marking purposes */
  Bytecount offset_past_gap;
  Elemcount els_past_gap;
  Gap_Array_Marker *markers;
  /* this is a stretchy array */
  char array[1];
} Gap_Array;

#ifdef NEW_GC
struct gap_array_marker;

DECLARE_LISP_OBJECT (gap_array_marker, struct gap_array_marker);
#define XGAP_ARRAY_MARKER(x) \
  XRECORD (x, gap_array_marker, struct gap_array_marker)
#define wrap_gap_array_marker(p) wrap_record (p, gap_array_marker)
#define GAP_ARRAY_MARKERP(x) RECORDP (x, gap_array_marker)
#define CHECK_GAP_ARRAY_MARKER(x) CHECK_RECORD (x, gap_array_marker)
#define CONCHECK_GAP_ARRAY_MARKER(x) CONCHECK_RECORD (x, gap_array_marker)

struct gap_array;

DECLARE_LISP_OBJECT (gap_array, struct gap_array);
#define XGAP_ARRAY(x) XRECORD (x, gap_array, struct gap_array)
#define wrap_gap_array(p) wrap_record (p, gap_array)
#define GAP_ARRAYP(x) RECORDP (x, gap_array)
#define CHECK_GAP_ARRAY(x) CHECK_RECORD (x, gap_array)
#define CONCHECK_GAP_ARRAY(x) CONCHECK_RECORD (x, gap_array)
#endif /* NEW_GC */

#ifdef NEW_GC
#define XD_GAP_ARRAY_MARKER_DESC					\
  { XD_LISP_OBJECT, offsetof (Gap_Array, markers) }
#else /* not NEW_GC */
#define XD_GAP_ARRAY_MARKER_DESC					\
  { XD_BLOCK_PTR, offsetof (Gap_Array, markers), 1,			\
    { &gap_array_marker_description }, XD_FLAG_NO_KKCC }
#endif /* not NEW_GC */

#define XD_GAP_ARRAY_DESC(sub_desc)					\
  { XD_ELEMCOUNT, offsetof (Gap_Array, gap) },				\
  { XD_BYTECOUNT, offsetof (Gap_Array, offset_past_gap) },		\
  { XD_ELEMCOUNT, offsetof (Gap_Array, els_past_gap) },			\
  XD_GAP_ARRAY_MARKER_DESC,						\
  { XD_BLOCK_ARRAY, offsetof (Gap_Array, array), XD_INDIRECT (0, 0),	\
    { sub_desc } },							\
  { XD_BLOCK_ARRAY, XD_INDIRECT (1, offsetof (Gap_Array, array)),	\
    XD_INDIRECT (2, 0), { sub_desc } }

/* Convert a "memory position" (i.e. taking the gap into account) into
   the address of the element at (i.e. after) that position.  "Memory
   positions" are only used internally and are of type Memxpos.
   "Array positions" are used externally and are of type Elemcount. */
#define GAP_ARRAY_MEMEL_ADDR(ga, memel) ((ga)->array + (ga)->elsize*(memel))

/* Number of elements currently in a gap array */
#define gap_array_length(ga) ((ga)->numels)

#define gap_array_gappos(ga) ((ga)->gap)
#define gap_array_gapsize(ga) ((ga)->gapsize)

#define GAP_ARRAY_ARRAY_TO_MEMORY_POS_1(pos, gappos, gapsize) \
  ((pos) < gappos ? (pos) : (pos) + gapsize)

#define GAP_ARRAY_ARRAY_TO_MEMORY_POS(ga, pos) \
  GAP_ARRAY_ARRAY_TO_MEMORY_POS_1 (pos, (ga)->gap, (ga)->gapsize)

#define GAP_ARRAY_MEMORY_TO_ARRAY_POS(ga, pos) \
  ((pos) <= (ga)->gap ? (pos) : (pos) - (ga)->gapsize)

/* Return a pointer to the element at a given position. */
#define gap_array_atp(ga, pos, type) \
  ((type *) GAP_ARRAY_MEMEL_ADDR (ga, GAP_ARRAY_ARRAY_TO_MEMORY_POS (ga, pos)))

/* Return the element at a given position. */
#define gap_array_at(ga, pos, type) (*gap_array_atp (ga, pos, type))

/* Return a pointer to the beginning of memory storage for the gap array.
   Note this is NOT the same as gap_array_atp(ga, 0, type) because that
   will skip forward past the gap if the gap is at position 0. */
#define gap_array_begin(ga, type) ((type *) ((ga)->array))

#ifndef NEW_GC
extern const struct sized_memory_description lispobj_gap_array_description;
extern const struct sized_memory_description gap_array_marker_description;
#endif

Bytecount gap_array_byte_size (Gap_Array *ga);
Gap_Array *gap_array_insert_els (Gap_Array *ga, Elemcount pos, void *elptr,
				 Elemcount numels);
void gap_array_delete_els (Gap_Array *ga, Elemcount from, Elemcount numdel);
#define gap_array_delete_all_els(ga) \
  gap_array_delete_els (ga, 0, gap_array_length (ga))
Gap_Array_Marker *gap_array_make_marker (Gap_Array *ga, Elemcount pos);
void gap_array_delete_marker (Gap_Array *ga, Gap_Array_Marker *m);
void gap_array_delete_all_markers (Gap_Array *ga);
void gap_array_move_marker (Gap_Array *ga, Gap_Array_Marker *m, Elemcount pos);
#define gap_array_marker_pos(ga, m) \
  GAP_ARRAY_MEMORY_TO_ARRAY_POS (ga, (m)->pos)
Gap_Array *make_gap_array (Elemcount elsize, int USED_IF_NEW_GC (do_lisp));
Gap_Array *gap_array_clone (Gap_Array *ga);
void free_gap_array (Gap_Array *ga);
Bytecount gap_array_memory_usage (Gap_Array *ga, struct usage_stats *stats,
				  Bytecount *marker_ancillary);

#endif /* INCLUDED_array_h_ */