--- /dev/null	Thu Jan 01 00:00:00 1970 +0000
+++ b/src/array.h	Mon Mar 22 19:12:15 2010 -0500
@@ -0,0 +1,767 @@
+/* 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_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);
+
+#endif /* INCLUDED_lrecordt_h_ */