--- a/src/ChangeLog	Sun Mar 21 04:41:49 2010 -0500
+++ b/src/ChangeLog	Mon Mar 22 19:12:15 2010 -0500
@@ -1,3 +1,65 @@
+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.
+
 2010-03-21  Ben Wing  <ben@xemacs.org>
 
 	* alloc.c:

--- a/src/Makefile.in.in	Sun Mar 21 04:41:49 2010 -0500
+++ b/src/Makefile.in.in	Mon Mar 22 19:12:15 2010 -0500
@@ -274,13 +274,12 @@
 ## if they all come out null.
 
 objs=\
- abbrev.o alloc.o alloca.o \
+ abbrev.o alloc.o alloca.o array.o \
  $(balloon_help_objs) blocktype.o buffer.o bytecode.o \
  callint.o casefiddle.o casetab.o chartab.o \
  $(clash_detection_objs) cmdloop.o cmds.o $(coding_system_objs) console.o \
  console-stream.o\
  data.o $(database_objs) $(debug_objs) device.o dired.o doc.o doprnt.o\
- dynarr.o \
  editfns.o elhash.o emacs.o emodules.o eval.o events.o\
  event-stream.o $(event_unixoid_objs) $(extra_objs) extents.o\
  faces.o file-coding.o fileio.o $(LOCK_OBJ) filemode.o floatfns.o fns.o \

--- /dev/null	Thu Jan 01 00:00:00 1970 +0000
+++ b/src/array.c	Mon Mar 22 19:12:15 2010 -0500
@@ -0,0 +1,950 @@
+/* Support for dynarrs and other types of dynamic arrays.
+   Copyright (c) 1994, 1995 Free Software Foundation, Inc.
+   Copyright (c) 1993, 1995 Sun Microsystems, Inc.
+   Copyright (c) 1995, 1996, 2000, 2002, 2003, 2004, 2005, 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. */
+
+/* Written by Ben Wing, December 1993. */
+
+#include <config.h>
+#include "lisp.h"
+
+#include "insdel.h"
+
+
+/*****************************************************************************/
+/*                       "dynarr" a.k.a. dynamic array                       */
+/*****************************************************************************/
+
+/*
+A "dynamic array" or "dynarr" is a contiguous array of fixed-size elements
+where there is no upper limit (except available memory) on the number of
+elements in the array.  Because the elements are maintained contiguously,
+space is used efficiently (no per-element pointers necessary) and random
+access to a particular element is in constant time.  At any one point, the
+block of memory that holds the array has an upper limit; if this limit is
+exceeded, the memory is realloc()ed into a new array that is twice as big.
+Assuming that the time to grow the array is on the order of the new size of
+the array block, this scheme has a provably constant amortized time
+\(i.e. average time over all additions).
+
+When you add elements or retrieve elements, pointers are used.  Note that
+the element itself (of whatever size it is), and not the pointer to it,
+is stored in the array; thus you do not have to allocate any heap memory
+on your own.  Also, returned pointers are only guaranteed to be valid
+until the next operation that changes the length of the array.
+
+This is a container object.  Declare a dynamic array of a specific type
+as follows:
+
+  typedef struct
+  {
+    Dynarr_declare (mytype);
+  } mytype_dynarr;
+
+Use the following functions/macros:
+
+
+  ************* Dynarr creation *************
+
+   void *Dynarr_new(type)
+      [MACRO] Create a new dynamic-array object, with each element of the
+      specified type.  The return value is cast to (type##_dynarr).
+      This requires following the convention that types are declared in
+      such a way that this type concatenation works.  In particular, TYPE
+      must be a symbol, not an arbitrary C type.  To make dynarrs of
+      complex types, a typedef must be declared, e.g.
+
+      typedef unsigned char *unsigned_char_ptr;
+
+      and then you can say
+
+      unsigned_char_ptr_dynarr *dyn = Dynarr_new (unsigned_char_ptr);
+
+   void *Dynarr_new2(dynarr_type, type)
+      [MACRO] Create a new dynamic-array object, with each element of the
+      specified type.  The array itself is of type DYNARR_TYPE.  This makes
+      it possible to create dynarrs over complex types without the need
+      to create typedefs, as described above.  Use is as follows:
+
+      ucharptr_dynarr *dyn = Dynarr_new2 (ucharptr_dynarr *, unsigned char *);
+
+   Dynarr_free(d)
+      Destroy a dynamic array and the memory allocated to it.
+
+  ************* Dynarr access *************
+
+   type Dynarr_at(d, i)
+      [MACRO] Return the element at the specified index.  The index must be
+      between 0 and Dynarr_largest(d), inclusive.  With error-checking
+      enabled, bounds checking on the index is in the form of asserts() --
+      an out-of-bounds index causes an abort.  The element itself is
+      returned, not a pointer to it.
+
+   type *Dynarr_atp(d, i)
+      [MACRO] Return a pointer to the element at the specified index.
+      Restrictions and bounds checking on the index is as for Dynarr_at.
+      The pointer may not be valid after an element is added to or
+      (conceivably) removed from the array, because this may trigger a
+      realloc() performed on the underlying dynarr storage, which may
+      involve moving the entire underlying storage to a new location in
+      memory.
+
+   type *Dynarr_begin(d)
+      [MACRO] Return a pointer to the first element in the dynarr.  See
+      Dynarr_atp() for warnings about when the pointer might become invalid.
+
+   type *Dynarr_lastp(d)
+      [MACRO] Return a pointer to the last element in the dynarr.  See
+      Dynarr_atp() for warnings about when the pointer might become invalid.
+
+   type *Dynarr_past_lastp(d)
+      [MACRO] Return a pointer to the beginning of the element just past the
+      last one.  WARNING: This may not point to valid memory; however, the
+      byte directly before will be pointer will be valid memory.  This macro
+      might be useful for various reasons, e.g. as a stopping point in a loop
+      (although Dynarr_lastp() could be used just as well) or as a place to
+      start writing elements if Dynarr_length() < Dynarr_largest().
+
+  ************* Dynarr length/size retrieval and setting *************
+
+   int Dynarr_length(d)
+      [MACRO] Return the number of elements currently in a dynamic array.
+
+   int Dynarr_largest(d)
+      [MACRO] Return the maximum value that Dynarr_length(d) would
+      ever have returned.  This is used esp. in the redisplay code,
+      which reuses dynarrs for performance reasons.
+
+   int Dynarr_max(d)
+      [MACRO] Return the maximum number of elements that can fit in the
+      dynarr before it needs to be resized.
+
+      Note that Dynarr_length(d) <= Dynarr_largest(d) <= Dynarr_max(d).
+   
+   Bytecount Dynarr_sizeof(d)
+      [MACRO] Return the total size of the elements currently in dynarr
+      D.  This 
+
+   Dynarr_set_lengthr(d, len)
+      [MACRO] Set the length of D to LEN, which must be between 0 and
+      Dynarr_largest(d), inclusive.  With error-checking enabled, an
+      assertion failure will result from trying to set the length
+      to less than zero or greater than Dynarr_largest(d).  The
+      restriction to Dynarr_largest() is to ensure that
+
+   Dynarr_set_length(d, len)
+      [MACRO] Set the length of D to LEN, resizing the dynarr as
+      necessary to make sure enough space is available.  there are no
+      restrictions on LEN other than available memory and that it must
+      be at least 0.  Note that
+
+   Dynarr_set_length_and_zero(d, len)
+      [MACRO] Like Dynarr_set_length(d, len) but also, if increasing
+      the length, zero out the memory between the old and new lengths,
+      i.e. starting just past the previous last element and up through
+      the new last element.
+
+   Dynarr_incrementr(d)
+      [MACRO] Increments the length of D by 1.  Equivalent to
+      Dynarr_set_lengthr(d, Dynarr_length(d) + 1).
+
+   Dynarr_increment(d)
+      [MACRO] Increments the length of D by 1.  Equivalent to
+      Dynarr_set_length(d, Dynarr_length(d) + 1).
+
+   Dynarr_reset(d)
+      [MACRO] Reset the length of a dynamic array to 0.
+
+   Dynarr_resize(d, maxval)
+      Resize the internal dynarr storage to so that it can hold at least
+      MAXVAL elements.  Resizing is done using a geometric series
+      (repeatedly multiply the old maximum by a constant, normally 1.5,
+      till a large enough size is reached), so this will be efficient
+      even if resizing larger by one element at a time.  This is mostly
+      an internal function.
+
+
+
+  ************* Adding/deleting elements to/from a dynarr *************
+
+   Dynarr_add(d, el)
+      [MACRO] Add an element to the end of a dynamic array.  EL is a pointer
+      to the element; the element itself is stored in the array, however.
+      No function call is performed unless the array needs to be resized.
+
+   Dynarr_add_many(d, base, len)
+      [MACRO] Add LEN elements to the end of the dynamic array.  The elements
+      should be contiguous in memory, starting at BASE.  If BASE if NULL,
+      just make space for the elements; don't actually add them.
+
+   Dynarr_prepend_many(d, base, len)
+      [MACRO] Prepend LEN elements to the beginning of the dynamic array.
+      The elements should be contiguous in memory, starting at BASE.
+      If BASE if NULL, just make space for the elements; don't actually
+      add them.
+
+   Dynarr_insert_many(d, base, len, pos)
+      Insert LEN elements to the dynamic array starting at position
+      POS.  The elements should be contiguous in memory, starting at BASE.
+      If BASE if NULL, just make space for the elements; don't actually
+      add them.
+
+   type Dynarr_pop(d)
+      [MACRO] Pop the last element off the dynarr and return it.
+
+   Dynarr_delete(d, i)
+      [MACRO] Delete an element from the dynamic array at position I.
+
+   Dynarr_delete_many(d, pos, len)
+      Delete LEN elements from the dynamic array starting at position
+      POS.
+
+   Dynarr_zero_many(d, pos, len)
+      Zero out LEN elements in the dynarr D starting at position POS.
+
+   Dynarr_delete_by_pointer(d, p)
+      [MACRO] Delete an element from the dynamic array at pointer P,
+      which must point within the block of memory that stores the data.
+      P should be obtained using Dynarr_atp().
+
+  ************* Dynarr locking *************
+
+   Dynarr_lock(d)
+      Lock the dynarr against further locking or writing.  With error-checking
+      enabled, any attempts to write into a locked dynarr or re-lock an
+      already locked one will cause an assertion failure and abort.
+
+   Dynarr_unlock(d)
+      Unlock a locked dynarr, allowing writing into it.
+
+  ************* Dynarr global variables *************
+
+   Dynarr_min_size
+      Minimum allowable size for a dynamic array when it is resized.
+
+*/
+
+static const struct memory_description const_Ascbyte_ptr_description_1[] = {
+  { XD_ASCII_STRING, 0 },
+  { XD_END }
+};
+
+const struct sized_memory_description const_Ascbyte_ptr_description = {
+  sizeof (const Ascbyte *),
+  const_Ascbyte_ptr_description_1
+};
+
+static const struct memory_description const_Ascbyte_ptr_dynarr_description_1[] = {
+  XD_DYNARR_DESC (const_Ascbyte_ptr_dynarr, &const_Ascbyte_ptr_description),
+  { XD_END }
+};
+
+const struct sized_memory_description const_Ascbyte_ptr_dynarr_description = {
+  sizeof (const_Ascbyte_ptr_dynarr),
+  const_Ascbyte_ptr_dynarr_description_1
+};
+
+
+static Elemcount Dynarr_min_size = 8;
+
+static void
+Dynarr_realloc (Dynarr *dy, Elemcount new_size)
+{
+  if (DUMPEDP (dy->base))
+    {
+      void *new_base = malloc (new_size * Dynarr_elsize (dy));
+      memcpy (new_base, dy->base, 
+	      (Dynarr_max (dy) < new_size ? Dynarr_max (dy) : new_size) *
+	      Dynarr_elsize (dy));
+      dy->base = new_base;
+    }
+  else
+    dy->base = xrealloc (dy->base, new_size * Dynarr_elsize (dy));
+}
+
+void *
+Dynarr_newf (Bytecount elsize)
+{
+  Dynarr *d = xnew_and_zero (Dynarr);
+  d->elsize_ = elsize;
+
+  return d;
+}
+
+#ifdef NEW_GC
+DEFINE_DUMPABLE_INTERNAL_LISP_OBJECT ("dynarr", dynarr,
+				      0, 0,
+				      Dynarr);
+
+static void
+Dynarr_lisp_realloc (Dynarr *dy, Elemcount new_size)
+{
+  void *new_base =
+    XPNTR (alloc_sized_lrecord_array (Dynarr_elsize (dy), new_size,
+				      dy->lisp_imp));
+  if (dy->base)
+    memcpy (new_base, dy->base, 
+	    (Dynarr_max (dy) < new_size ? Dynarr_max (dy) : new_size) *
+	    Dynarr_elsize (dy));
+  dy->base = new_base;
+}
+
+void *
+Dynarr_lisp_newf (Bytecount elsize, 
+		  const struct lrecord_implementation *dynarr_imp, 
+		  const struct lrecord_implementation *imp)
+{
+  Dynarr *d = (Dynarr *) XPNTR (alloc_sized_lrecord (sizeof (Dynarr),
+                                                     dynarr_imp));
+  d->elsize_ = elsize;
+  d->lisp_imp = imp;
+
+  return d;
+}
+#endif /* not NEW_GC */
+
+void
+Dynarr_resize (void *d, Elemcount size)
+{
+  Elemcount newsize;
+  double multiplier;
+  Dynarr *dy = (Dynarr *) Dynarr_verify (d);
+
+  if (Dynarr_max (dy) <= 8)
+    multiplier = 2;
+  else
+    multiplier = 1.5;
+
+  for (newsize = Dynarr_max (dy); newsize < size;)
+    newsize = max (Dynarr_min_size, (Elemcount) (multiplier * newsize));
+
+  /* Don't do anything if the array is already big enough. */
+  if (newsize > Dynarr_max (dy))
+    {
+#ifdef NEW_GC
+      if (dy->lisp_imp)
+	Dynarr_lisp_realloc (dy, newsize);
+      else
+	Dynarr_realloc (dy, newsize);
+#else /* not NEW_GC */
+      Dynarr_realloc (dy, newsize);
+#endif /* not NEW_GC */
+      dy->max_ = newsize;
+    }
+}
+
+/* Add a number of contiguous elements to the array starting at POS. */
+
+void
+Dynarr_insert_many (void *d, const void *base, Elemcount len, Elemcount pos)
+{
+  Dynarr *dy = Dynarr_verify_mod (d);
+  Elemcount old_len = Dynarr_length (dy);
+
+  /* #### This could conceivably be wrong, if code wants to access stuff
+     between len and largest. */
+  dynarr_checking_assert (pos >= 0 && pos <= old_len);
+  dynarr_checking_assert (len >= 0);
+  Dynarr_increase_length (dy, old_len + len);
+
+  if (pos != old_len)
+    {
+      memmove ((Rawbyte *) dy->base + (pos + len)*Dynarr_elsize (dy),
+	       (Rawbyte *) dy->base + pos*Dynarr_elsize (dy),
+	       (old_len - pos)*Dynarr_elsize (dy));
+    }
+  /* Some functions call us with a value of 0 to mean "reserve space but
+     don't write into it" */
+  if (base)
+    memcpy ((Rawbyte *) dy->base + pos*Dynarr_elsize (dy), base,
+	    len*Dynarr_elsize (dy));
+}
+
+void
+Dynarr_delete_many (void *d, Elemcount pos, Elemcount len)
+{
+  Dynarr *dy = Dynarr_verify_mod (d);
+
+  dynarr_checking_assert (pos >= 0 && len >= 0 &&
+			  pos + len <= Dynarr_length (dy));
+
+  memmove ((Rawbyte *) dy->base + pos*Dynarr_elsize (dy),
+	   (Rawbyte *) dy->base + (pos + len)*Dynarr_elsize (dy),
+	   (Dynarr_length (dy) - pos - len)*Dynarr_elsize (dy));
+
+  Dynarr_set_length_1 (dy, Dynarr_length (dy) - len);
+}
+
+void
+Dynarr_free (void *d)
+{
+  Dynarr *dy = (Dynarr *) d;
+
+#ifdef NEW_GC
+  if (dy->base && !DUMPEDP (dy->base))
+    {
+      if (!dy->lisp_imp)
+	xfree (dy->base);
+    }
+  if(!DUMPEDP (dy))
+    {
+      if (!dy->lisp_imp)
+	xfree (dy);
+    }
+#else /* not NEW_GC */
+  if (dy->base && !DUMPEDP (dy->base))
+    xfree (dy->base);
+  if(!DUMPEDP (dy))
+    xfree (dy);
+#endif /* not NEW_GC */
+}
+
+#ifdef MEMORY_USAGE_STATS
+
+/* Return memory usage for dynarr D.  The returned value is the total
+   amount of bytes actually being used for the dynarr, including all
+   overhead.  The extra amount of space in the dynarr that is
+   allocated beyond what was requested is returned in DYNARR_OVERHEAD
+   in STATS.  The extra amount of space that malloc() allocates beyond
+   what was requested of it is returned in MALLOC_OVERHEAD in STATS.
+   See the comment above the definition of this structure. */
+
+Bytecount
+Dynarr_memory_usage (void *d, struct usage_stats *stats)
+{
+  Bytecount total = 0;
+  Dynarr *dy = (Dynarr *) d;
+
+  /* We have to be a bit tricky here because not all of the
+     memory that malloc() will claim as "requested" was actually
+     requested. */
+
+  if (dy->base)
+    {
+      Bytecount malloc_used =
+	malloced_storage_size (dy->base, Dynarr_elsize (dy) * Dynarr_max (dy),
+			       0);
+      /* #### This may or may not be correct.  Some dynarrs would
+	 prefer that we use dy->len instead of dy->largest here. */
+      Bytecount was_requested = Dynarr_elsize (dy) * Dynarr_largest (dy);
+      Bytecount dynarr_overhead =
+	Dynarr_elsize (dy) * (Dynarr_max (dy) - Dynarr_largest (dy));
+
+      total += malloc_used;
+      stats->was_requested += was_requested;
+      stats->dynarr_overhead += dynarr_overhead;
+      /* And the remainder must be malloc overhead. */
+      stats->malloc_overhead +=
+	malloc_used - was_requested - dynarr_overhead;
+    }
+
+  total += malloced_storage_size (d, sizeof (*dy), stats);
+
+  return total;
+}
+
+#endif /* MEMORY_USAGE_STATS */
+
+
+/*****************************************************************************/
+/*                           stack-like allocation                           */
+/*****************************************************************************/
+
+/* Version of malloc() that will be extremely efficient when allocation
+   nearly always occurs in LIFO (stack) order.
+
+   #### Perhaps shouldn't be in this file, but where else? */
+
+typedef struct
+{
+  Dynarr_declare (char_dynarr *);
+} char_dynarr_dynarr;
+
+char_dynarr_dynarr *stack_like_free_list;
+char_dynarr_dynarr *stack_like_in_use_list;
+
+void *
+stack_like_malloc (Bytecount size)
+{
+  char_dynarr *this_one;
+  if (!stack_like_free_list)
+    {
+      stack_like_free_list = Dynarr_new2 (char_dynarr_dynarr,
+					  char_dynarr *);
+      stack_like_in_use_list = Dynarr_new2 (char_dynarr_dynarr,
+					    char_dynarr *);
+    }
+
+  if (Dynarr_length (stack_like_free_list) > 0)
+    this_one = Dynarr_pop (stack_like_free_list);
+  else
+    this_one = Dynarr_new (char);
+  Dynarr_add (stack_like_in_use_list, this_one);
+  Dynarr_reset (this_one);
+  Dynarr_add_many (this_one, 0, size);
+  return Dynarr_begin (this_one);
+}
+
+void
+stack_like_free (void *val)
+{
+  Elemcount len = Dynarr_length (stack_like_in_use_list);
+  assert (len > 0);
+  /* The vast majority of times, we will be called in a last-in first-out
+     order, and the item at the end of the list will be the one we're
+     looking for, so just check for this first and avoid any function
+     calls. */
+  if (Dynarr_begin (Dynarr_at (stack_like_in_use_list, len - 1)) == val)
+    {
+      char_dynarr *this_one = Dynarr_pop (stack_like_in_use_list);
+      Dynarr_add (stack_like_free_list, this_one);
+    }
+  else
+    {
+      /* Find the item and delete it. */
+      int i;
+      assert (len >= 2);
+      for (i = len - 2; i >= 0; i--)
+	if (Dynarr_begin (Dynarr_at (stack_like_in_use_list, i)) ==
+	    val)
+	  {
+	    char_dynarr *this_one = Dynarr_at (stack_like_in_use_list, i);
+	    Dynarr_add (stack_like_free_list, this_one);
+	    Dynarr_delete (stack_like_in_use_list, i);
+	    return;
+	  }
+
+      ABORT ();
+    }
+}
+
+
+/*****************************************************************************/
+/*                           Generalized gap array                           */
+/*****************************************************************************/
+
+/* A "gap array" is an array that has a "gap" somewhere in the middle of it,
+   so that insertions and deletions near the gap -- or in general, highly
+   localized insertions and deletions -- are very fast.  Inserting or
+   deleting works by first moving the gap to the insertion or deletion
+   position and then shortening or lengthening the gap as necessary.  The
+   idea comes from the gap used in storing text in a buffer.
+
+   The gap array interface differs in a number of ways from dynarrs (####
+   and should be changed so that it works the same as dynarrs):
+
+   (1) There aren't separate type-specific gap array types.  As a result,
+       operations like gap_array_at() require that the type be specified as
+       one of the arguments.  It is often more convenient to use a macro
+       wrapper around this operation.
+
+   (2) The gap array type is itself a stretchy array rather than using a
+       separate block of memory to store the array.  This means that certain
+       operations (especially insertions) may relocate the the gap array,
+       and as a result return a pointer to the (possibly) moved gap array,
+       which must be stored back into the location where the gap array
+       pointer resides.  This also means that the caller must worry about
+       cloning the gap array in the case where it has been dumped, or you
+       will get an ABORT() inside of xrealloc().
+
+   (3) Fewer operations are available than for dynarrs, and may have
+       different names and/or different calling conventions.
+
+   (4) The mechanism for creating "Lisp-object gap arrays" isn't completely
+       developed.  Currently it's only possible to create a gap-array Lisp
+       object that wraps Lisp_Object pointers (not Lisp object structures
+       directly), and only under NEW_GC.
+
+   (5) Gap arrays have a concept of a "gap array marker" that properly
+       tracks insertions and deletions; no such thing exists in dynarrs.
+       It exists in gap arrays because it's necessary for their use in
+       implementing extent lists.
+ */
+
+extern const struct sized_memory_description gap_array_marker_description;
+
+static const struct memory_description gap_array_marker_description_1[] = { 
+#ifdef NEW_GC
+  { XD_LISP_OBJECT, offsetof (Gap_Array_Marker, next) },
+#else /* not NEW_GC */
+  { XD_BLOCK_PTR, offsetof (Gap_Array_Marker, next), 1,
+    { &gap_array_marker_description } },
+#endif /* not NEW_GC */
+  { XD_END }
+};
+
+#ifdef NEW_GC
+DEFINE_NODUMP_INTERNAL_LISP_OBJECT ("gap-array-marker", gap_array_marker,
+				    0, gap_array_marker_description_1,
+				    struct gap_array_marker);
+#else /* not NEW_GC */
+const struct sized_memory_description gap_array_marker_description = {
+  sizeof (Gap_Array_Marker),
+  gap_array_marker_description_1
+};
+#endif /* not NEW_GC */
+
+static const struct memory_description lispobj_gap_array_description_1[] = {
+  XD_GAP_ARRAY_DESC (&lisp_object_description),
+  { XD_END }
+};
+
+#ifdef NEW_GC
+
+static Bytecount
+size_gap_array (Lisp_Object obj)
+{
+  Gap_Array *ga = XGAP_ARRAY (obj);
+  return gap_array_byte_size (ga);
+}
+
+DEFINE_DUMPABLE_SIZABLE_INTERNAL_LISP_OBJECT ("gap-array", gap_array,
+					      0,
+					      lispobj_gap_array_description_1,
+					      size_gap_array,
+					      struct gap_array);
+#else /* not NEW_GC */
+const struct sized_memory_description lispobj_gap_array_description = {
+  0, lispobj_gap_array_description_1
+};
+#endif /* (not) NEW_GC */
+
+#ifndef NEW_GC
+static Gap_Array_Marker *gap_array_marker_freelist;
+#endif /* not NEW_GC */
+
+/* This generalizes the "array with a gap" model used to store buffer
+   characters.  This is based on the stuff in insdel.c and should
+   probably be merged with it.  This is not extent-specific and should
+   perhaps be moved into a separate file. */
+
+/* ------------------------------- */
+/*        internal functions       */
+/* ------------------------------- */
+
+/* Adjust the gap array markers in the range (FROM, TO].  Parallel to
+   adjust_markers() in insdel.c. */
+
+static void
+gap_array_adjust_markers (Gap_Array *ga, Memxpos from,
+			  Memxpos to, Elemcount amount)
+{
+  Gap_Array_Marker *m;
+
+  for (m = ga->markers; m; m = m->next)
+    m->pos = do_marker_adjustment (m->pos, from, to, amount);
+}
+
+static void
+gap_array_recompute_derived_values (Gap_Array *ga)
+{
+  ga->offset_past_gap = ga->elsize * (ga->gap + ga->gapsize);
+  ga->els_past_gap = ga->numels - ga->gap;
+}
+
+/* Move the gap to array position POS.  Parallel to move_gap() in
+   insdel.c but somewhat simplified. */
+
+static void
+gap_array_move_gap (Gap_Array *ga, Elemcount pos)
+{
+  Elemcount gap = ga->gap;
+  Elemcount gapsize = ga->gapsize;
+
+  if (pos < gap)
+    {
+      memmove (GAP_ARRAY_MEMEL_ADDR (ga, pos + gapsize),
+	       GAP_ARRAY_MEMEL_ADDR (ga, pos),
+	       (gap - pos)*ga->elsize);
+      gap_array_adjust_markers (ga, (Memxpos) pos, (Memxpos) gap,
+				gapsize);
+    }
+  else if (pos > gap)
+    {
+      memmove (GAP_ARRAY_MEMEL_ADDR (ga, gap),
+	       GAP_ARRAY_MEMEL_ADDR (ga, gap + gapsize),
+	       (pos - gap)*ga->elsize);
+      gap_array_adjust_markers (ga, (Memxpos) (gap + gapsize),
+				(Memxpos) (pos + gapsize), - gapsize);
+    }
+  ga->gap = pos;
+
+  gap_array_recompute_derived_values (ga);
+}
+
+/* Make the gap INCREMENT characters longer.  Parallel to make_gap() in
+   insdel.c.  The gap array may be moved, so assign the return value back
+   to the array pointer. */
+
+static Gap_Array *
+gap_array_make_gap (Gap_Array *ga, Elemcount increment)
+{
+  Elemcount real_gap_loc;
+  Elemcount old_gap_size;
+
+  /* If we have to get more space, get enough to last a while.  We use
+     a geometric progression that saves on realloc space. */
+  increment += 100 + ga->numels / 8;
+
+#ifdef NEW_GC
+  if (ga->is_lisp)
+    ga = (Gap_Array *) mc_realloc (ga,
+				   offsetof (Gap_Array, array) +
+				   (ga->numels + ga->gapsize + increment) *
+				   ga->elsize);
+  else
+#endif /* not NEW_GC */
+    ga = (Gap_Array *) xrealloc (ga,
+				 offsetof (Gap_Array, array) +
+				 (ga->numels + ga->gapsize + increment) *
+				 ga->elsize);
+  if (ga == 0)
+    memory_full ();
+
+  real_gap_loc = ga->gap;
+  old_gap_size = ga->gapsize;
+
+  /* Call the newly allocated space a gap at the end of the whole space.  */
+  ga->gap = ga->numels + ga->gapsize;
+  ga->gapsize = increment;
+
+  /* Move the new gap down to be consecutive with the end of the old one.
+     This adjusts the markers properly too.  */
+  gap_array_move_gap (ga, real_gap_loc + old_gap_size);
+
+  /* Now combine the two into one large gap.  */
+  ga->gapsize += old_gap_size;
+  ga->gap = real_gap_loc;
+
+  gap_array_recompute_derived_values (ga);
+
+  return ga;
+}
+
+/* ------------------------------- */
+/*        external functions       */
+/* ------------------------------- */
+
+Bytecount
+gap_array_byte_size (Gap_Array *ga)
+{
+  return offsetof (Gap_Array, array) + (ga->numels + ga->gapsize) * ga->elsize;
+}
+
+/* Insert NUMELS elements (pointed to by ELPTR) into the specified
+   gap array at POS.  The gap array may be moved, so assign the
+   return value back to the array pointer. */
+
+Gap_Array *
+gap_array_insert_els (Gap_Array *ga, Elemcount pos, void *elptr,
+		      Elemcount numels)
+{
+  assert (pos >= 0 && pos <= ga->numels);
+  if (ga->gapsize < numels)
+    ga = gap_array_make_gap (ga, numels - ga->gapsize);
+  if (pos != ga->gap)
+    gap_array_move_gap (ga, pos);
+
+  memcpy (GAP_ARRAY_MEMEL_ADDR (ga, ga->gap), (char *) elptr,
+	  numels*ga->elsize);
+  ga->gapsize -= numels;
+  ga->gap += numels;
+  ga->numels += numels;
+  gap_array_recompute_derived_values (ga);
+  /* This is the equivalent of insert-before-markers.
+
+     #### Should only happen if marker is "moves forward at insert" type.
+     */
+
+  gap_array_adjust_markers (ga, pos - 1, pos, numels);
+  return ga;
+}
+
+/* Delete NUMELS elements from the specified gap array, starting at FROM. */
+
+void
+gap_array_delete_els (Gap_Array *ga, Elemcount from, Elemcount numdel)
+{
+  Elemcount to = from + numdel;
+  Elemcount gapsize = ga->gapsize;
+
+  assert (from >= 0);
+  assert (numdel >= 0);
+  assert (to <= ga->numels);
+
+  /* Make sure the gap is somewhere in or next to what we are deleting.  */
+  if (to < ga->gap)
+    gap_array_move_gap (ga, to);
+  if (from > ga->gap)
+    gap_array_move_gap (ga, from);
+
+  /* Relocate all markers pointing into the new, larger gap
+     to point at the end of the text before the gap.  */
+  gap_array_adjust_markers (ga, to + gapsize, to + gapsize,
+			    - numdel - gapsize);
+
+  ga->gapsize += numdel;
+  ga->numels -= numdel;
+  ga->gap = from;
+  gap_array_recompute_derived_values (ga);
+}
+
+Gap_Array_Marker *
+gap_array_make_marker (Gap_Array *ga, Elemcount pos)
+{
+  Gap_Array_Marker *m;
+
+  assert (pos >= 0 && pos <= ga->numels);
+#ifdef NEW_GC
+    m = XGAP_ARRAY_MARKER (ALLOC_NORMAL_LISP_OBJECT (gap_array_marker));
+#else /* not NEW_GC */
+  if (gap_array_marker_freelist)
+    {
+      m = gap_array_marker_freelist;
+      gap_array_marker_freelist = gap_array_marker_freelist->next;
+    }
+  else
+    m = xnew (Gap_Array_Marker);
+#endif /* not NEW_GC */
+
+  m->pos = GAP_ARRAY_ARRAY_TO_MEMORY_POS (ga, pos);
+  m->next = ga->markers;
+  ga->markers = m;
+  return m;
+}
+
+void
+gap_array_delete_marker (Gap_Array *ga, Gap_Array_Marker *m)
+{
+  Gap_Array_Marker *p, *prev;
+
+  for (prev = 0, p = ga->markers; p && p != m; prev = p, p = p->next)
+    ;
+  assert (p);
+  if (prev)
+    prev->next = p->next;
+  else
+    ga->markers = p->next;
+#ifndef NEW_GC
+  m->next = gap_array_marker_freelist;
+  m->pos = 0xDEADBEEF; /* -559038737 base 10 */
+  gap_array_marker_freelist = m;
+#endif /* not NEW_GC */
+}
+
+#ifndef NEW_GC
+void
+gap_array_delete_all_markers (Gap_Array *ga)
+{
+  Gap_Array_Marker *p, *next;
+
+  for (p = ga->markers; p; p = next)
+    {
+      next = p->next;
+      p->next = gap_array_marker_freelist;
+      p->pos = 0xDEADBEEF; /* -559038737 as an int */
+      gap_array_marker_freelist = p;
+    }
+}
+#endif /* not NEW_GC */
+
+void
+gap_array_move_marker (Gap_Array *ga, Gap_Array_Marker *m, Elemcount pos)
+{
+  assert (pos >= 0 && pos <= ga->numels);
+  m->pos = GAP_ARRAY_ARRAY_TO_MEMORY_POS (ga, pos);
+}
+
+Gap_Array *
+make_gap_array (Elemcount elsize, int USED_IF_NEW_GC (do_lisp))
+{
+  Gap_Array *ga;
+#ifdef NEW_GC
+  /* #### I don't quite understand why it's necessary to make all these
+     internal objects into Lisp objects under NEW_GC.  It's a pain in the
+     ass to code around this.  I'm proceeding on the assumption that it's
+     not really necessary to do it after all, and so we only make a Lisp-
+     object gap array when the object being held is a Lisp_Object, i.e. a
+     pointer to a Lisp object.  In the case where instead we hold a `struct
+     range_table_entry', just blow it off.  Otherwise we either need to do
+     a bunch of painful and/or boring rewriting. --ben */
+  if (do_lisp)
+    {
+      ga = XGAP_ARRAY (ALLOC_SIZED_LISP_OBJECT (sizeof (Gap_Array),
+						gap_array));
+      ga->is_lisp = 1;
+    }
+  else
+#endif /* not NEW_GC */
+    ga = xnew_and_zero (Gap_Array);
+  ga->elsize = elsize;
+  return ga;
+}
+
+Gap_Array *
+gap_array_clone (Gap_Array *ga)
+{
+  Bytecount size = gap_array_byte_size (ga);
+  Gap_Array *ga2;
+  Gap_Array_Marker *m;
+
+#ifdef NEW_GC
+  if (ga->is_lisp)
+    {
+      ga2 = XGAP_ARRAY (ALLOC_SIZED_LISP_OBJECT (size, gap_array));
+      copy_lisp_object (wrap_gap_array (ga2), wrap_gap_array (ga));
+    }
+  else
+#endif
+    {
+      ga2 = (Gap_Array *) xmalloc (size);
+      memcpy (ga2, ga, size);
+    }
+  ga2->markers = NULL;
+  for (m = ga->markers; m; m = m->next)
+    gap_array_make_marker (ga2, m->pos);
+  return ga2;
+}
+
+#ifndef NEW_GC
+void
+free_gap_array (Gap_Array *ga)
+{
+  gap_array_delete_all_markers (ga);
+  xfree (ga);
+}
+#endif /* not NEW_GC */
+
+
+/*****************************************************************************/
+/*                              Initialization                               */
+/*****************************************************************************/
+
+void
+syms_of_array (void)
+{
+#ifdef NEW_GC
+  INIT_LISP_OBJECT (gap_array_marker);
+  INIT_LISP_OBJECT (gap_array);
+#endif /* NEW_GC */
+}
+

--- /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_ */

--- a/src/depend	Sun Mar 21 04:41:49 2010 -0500
+++ b/src/depend	Mon Mar 22 19:12:15 2010 -0500
@@ -11,7 +11,7 @@
 LISP_H=
 #else
 CONFIG_H=config.h
-LISP_H=lisp.h compiler.h config.h dumper.h gc.h general-slots.h lisp.h lrecord.h mc-alloc.h number-gmp.h number-mp.h number.h symeval.h symsinit.h text.h vdb.h $(LISP_UNION_H)
+LISP_H=lisp.h array.h compiler.h config.h dumper.h gc.h general-slots.h lisp.h lrecord.h mc-alloc.h number-gmp.h number-mp.h number.h symeval.h symsinit.h text.h vdb.h $(LISP_UNION_H)
 #endif
 
 #if defined(HAVE_MS_WINDOWS)
@@ -111,6 +111,7 @@
 alloc.o: $(CONFIG_H) $(LISP_H) backtrace.h buffer.h bufslots.h bytecode.h casetab.h charset.h chartab.h coding-system-slots.h conslots.h console-impl.h console-stream.h console.h device.h elhash.h events.h extents-impl.h extents.h file-coding.h frame-impl.h frame.h frameslots.h glyphs.h intl-auto-encap-win32.h keymap-buttons.h lstream.h opaque.h process.h profile.h redisplay.h scrollbar.h specifier.h sysdep.h sysfile.h systime.h syswindows.h window-impl.h window.h winslots.h
 alloca.o: $(CONFIG_H) $(LISP_H)
 alsaplay.o: $(CONFIG_H) $(LISP_H) buffer.h bufslots.h casetab.h charset.h chartab.h intl-auto-encap-win32.h sound.h sysfile.h syswindows.h
+array.o: $(CONFIG_H) $(LISP_H) insdel.h
 blocktype.o: $(CONFIG_H) $(LISP_H) blocktype.h
 buffer.o: $(CONFIG_H) $(LISP_H) buffer.h bufslots.h casetab.h charset.h chartab.h coding-system-slots.h commands.h conslots.h console-impl.h console.h device-impl.h device.h devslots.h elhash.h extents.h faces.h file-coding.h frame-impl.h frame.h frameslots.h insdel.h intl-auto-encap-win32.h lstream.h ndir.h process.h redisplay.h scrollbar.h select.h specifier.h syntax.h sysdir.h sysfile.h syswindows.h window.h
 bytecode.o: $(CONFIG_H) $(LISP_H) backtrace.h buffer.h bufslots.h bytecode-ops.h bytecode.h casetab.h charset.h chartab.h opaque.h redisplay.h scrollbar.h syntax.h window.h
@@ -133,7 +134,6 @@
 dragdrop.o: $(CONFIG_H) $(LISP_H) dragdrop.h
 dump-data.o: $(CONFIG_H) $(LISP_H) dump-data.h
 dumper.o: $(CONFIG_H) $(LISP_H) coding-system-slots.h console-stream.h console.h dump-data.h elhash.h file-coding.h intl-auto-encap-win32.h lstream.h specifier.h sysfile.h syswindows.h
-dynarr.o: $(CONFIG_H) $(LISP_H)
 ecrt0.o: $(CONFIG_H)
 editfns.o: $(CONFIG_H) $(LISP_H) buffer.h bufslots.h casetab.h charset.h chartab.h commands.h console.h device.h events.h frame.h insdel.h intl-auto-encap-win32.h keymap-buttons.h line-number.h ndir.h process.h redisplay.h scrollbar.h sysdep.h sysdir.h sysfile.h sysproc.h syspwd.h syssignal.h systime.h syswindows.h window.h
 elhash.o: $(CONFIG_H) $(LISP_H) bytecode.h elhash.h opaque.h
@@ -172,7 +172,7 @@
 hpplay.o: $(CONFIG_H) $(LISP_H) buffer.h bufslots.h casetab.h charset.h chartab.h sound.h
 imgproc.o: $(CONFIG_H) $(LISP_H) imgproc.h
 indent.o: $(CONFIG_H) $(LISP_H) buffer.h bufslots.h casetab.h charset.h chartab.h console.h device.h extents.h faces.h frame.h glyphs.h insdel.h redisplay.h scrollbar.h specifier.h window-impl.h window.h winslots.h
-inline.o: $(CONFIG_H) $(LISP_H) $(LWLIB_SRCDIR)/lwlib.h buffer.h bufslots.h bytecode.h casetab.h charset.h chartab.h coding-system-slots.h conslots.h console-gtk.h console-impl.h console-msw.h console.h database.h device-impl.h device.h devslots.h elhash.h events.h extents-impl.h extents.h faces.h file-coding.h font-mgr.h frame-impl.h frame.h frameslots.h glyphs-x.h glyphs.h gui.h intl-auto-encap-win32.h keymap-buttons.h keymap.h lstream.h objects-impl.h objects.h opaque.h process.h rangetab.h redisplay.h scrollbar.h specifier.h syntax.h sysdll.h sysfile.h sysgtk.h systime.h syswindows.h toolbar.h tooltalk.h ui-gtk.h window-impl.h window.h winslots.h xintrinsic.h
+inline.o: $(CONFIG_H) $(LISP_H) $(LWLIB_SRCDIR)/lwlib.h buffer.h bufslots.h bytecode.h casetab.h charset.h chartab.h coding-system-slots.h conslots.h console-gtk-impl.h console-gtk.h console-impl.h console-msw-impl.h console-msw.h console-stream-impl.h console-stream.h console-tty-impl.h console-tty.h console-x-impl.h console-x.h console.h database.h device-impl.h device.h devslots.h elhash.h events.h extents-impl.h extents.h faces.h file-coding.h font-mgr.h frame-impl.h frame.h frameslots.h glyphs.h gui.h intl-auto-encap-win32.h keymap-buttons.h keymap.h lstream.h objects-impl.h objects-tty-impl.h objects-tty.h objects.h opaque.h process.h rangetab.h redisplay.h scrollbar.h specifier.h syntax.h sysdll.h sysfile.h sysgtk.h systime.h systty.h syswindows.h toolbar.h tooltalk.h ui-gtk.h window-impl.h window.h winslots.h xintrinsic.h
 input-method-motif.o: $(CONFIG_H) $(LISP_H) $(LWLIB_SRCDIR)/lwlib.h EmacsFrame.h conslots.h console-impl.h console-x-impl.h console-x.h console.h device.h frame-impl.h frame.h frameslots.h redisplay.h specifier.h xintrinsic.h xmotif.h
 input-method-xlib.o: $(CONFIG_H) $(LISP_H) $(LWLIB_SRCDIR)/lwlib.h EmacsFrame.h buffer.h bufslots.h casetab.h charset.h chartab.h conslots.h console-impl.h console-x-impl.h console-x.h console.h device-impl.h device.h devslots.h events.h frame-impl.h frame.h frameslots.h keymap-buttons.h redisplay.h scrollbar.h specifier.h systime.h window-impl.h window.h winslots.h xintrinsic.h
 insdel.o: $(CONFIG_H) $(LISP_H) buffer.h bufslots.h casetab.h charset.h chartab.h console.h device.h extents.h frame.h insdel.h line-number.h lstream.h redisplay.h

--- a/src/dynarr.c	Sun Mar 21 04:41:49 2010 -0500
+++ /dev/null	Thu Jan 01 00:00:00 1970 +0000
@@ -1,526 +0,0 @@
-/* Support for dynamic arrays.
-   Copyright (C) 1993 Sun Microsystems, Inc.
-   Copyright (C) 2002, 2003, 2004, 2005, 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. */
-
-/* Written by Ben Wing, December 1993. */
-
-/*
-
-A "dynamic array" or "dynarr" is a contiguous array of fixed-size elements
-where there is no upper limit (except available memory) on the number of
-elements in the array.  Because the elements are maintained contiguously,
-space is used efficiently (no per-element pointers necessary) and random
-access to a particular element is in constant time.  At any one point, the
-block of memory that holds the array has an upper limit; if this limit is
-exceeded, the memory is realloc()ed into a new array that is twice as big.
-Assuming that the time to grow the array is on the order of the new size of
-the array block, this scheme has a provably constant amortized time
-\(i.e. average time over all additions).
-
-When you add elements or retrieve elements, pointers are used.  Note that
-the element itself (of whatever size it is), and not the pointer to it,
-is stored in the array; thus you do not have to allocate any heap memory
-on your own.  Also, returned pointers are only guaranteed to be valid
-until the next operation that changes the length of the array.
-
-This is a container object.  Declare a dynamic array of a specific type
-as follows:
-
-  typedef struct
-  {
-    Dynarr_declare (mytype);
-  } mytype_dynarr;
-
-Use the following functions/macros:
-
-
-  ************* Dynarr creation *************
-
-   void *Dynarr_new(type)
-      [MACRO] Create a new dynamic-array object, with each element of the
-      specified type.  The return value is cast to (type##_dynarr).
-      This requires following the convention that types are declared in
-      such a way that this type concatenation works.  In particular, TYPE
-      must be a symbol, not an arbitrary C type.  To make dynarrs of
-      complex types, a typedef must be declared, e.g.
-
-      typedef unsigned char *unsigned_char_ptr;
-
-      and then you can say
-
-      unsigned_char_ptr_dynarr *dyn = Dynarr_new (unsigned_char_ptr);
-
-   void *Dynarr_new2(dynarr_type, type)
-      [MACRO] Create a new dynamic-array object, with each element of the
-      specified type.  The array itself is of type DYNARR_TYPE.  This makes
-      it possible to create dynarrs over complex types without the need
-      to create typedefs, as described above.  Use is as follows:
-
-      ucharptr_dynarr *dyn = Dynarr_new2 (ucharptr_dynarr *, unsigned char *);
-
-   Dynarr_free(d)
-      Destroy a dynamic array and the memory allocated to it.
-
-  ************* Dynarr access *************
-
-   type Dynarr_at(d, i)
-      [MACRO] Return the element at the specified index.  The index must be
-      between 0 and Dynarr_largest(d), inclusive.  With error-checking
-      enabled, bounds checking on the index is in the form of asserts() --
-      an out-of-bounds index causes an abort.  The element itself is
-      returned, not a pointer to it.
-
-   type *Dynarr_atp(d, i)
-      [MACRO] Return a pointer to the element at the specified index.
-      Restrictions and bounds checking on the index is as for Dynarr_at.
-      The pointer may not be valid after an element is added to or
-      (conceivably) removed from the array, because this may trigger a
-      realloc() performed on the underlying dynarr storage, which may
-      involve moving the entire underlying storage to a new location in
-      memory.
-
-   type *Dynarr_begin(d)
-      [MACRO] Return a pointer to the first element in the dynarr.  See
-      Dynarr_atp() for warnings about when the pointer might become invalid.
-
-   type *Dynarr_lastp(d)
-      [MACRO] Return a pointer to the last element in the dynarr.  See
-      Dynarr_atp() for warnings about when the pointer might become invalid.
-
-   type *Dynarr_past_lastp(d)
-      [MACRO] Return a pointer to the beginning of the element just past the
-      last one.  WARNING: This may not point to valid memory; however, the
-      byte directly before will be pointer will be valid memory.  This macro
-      might be useful for various reasons, e.g. as a stopping point in a loop
-      (although Dynarr_lastp() could be used just as well) or as a place to
-      start writing elements if Dynarr_length() < Dynarr_largest().
-
-  ************* Dynarr length/size retrieval and setting *************
-
-   int Dynarr_length(d)
-      [MACRO] Return the number of elements currently in a dynamic array.
-
-   int Dynarr_largest(d)
-      [MACRO] Return the maximum value that Dynarr_length(d) would
-      ever have returned.  This is used esp. in the redisplay code,
-      which reuses dynarrs for performance reasons.
-
-   int Dynarr_max(d)
-      [MACRO] Return the maximum number of elements that can fit in the
-      dynarr before it needs to be resized.
-
-      Note that Dynarr_length(d) <= Dynarr_largest(d) <= Dynarr_max(d).
-   
-   Bytecount Dynarr_sizeof(d)
-      [MACRO] Return the total size of the elements currently in dynarr
-      D.  This 
-
-   Dynarr_set_lengthr(d, len)
-      [MACRO] Set the length of D to LEN, which must be between 0 and
-      Dynarr_largest(d), inclusive.  With error-checking enabled, an
-      assertion failure will result from trying to set the length
-      to less than zero or greater than Dynarr_largest(d).  The
-      restriction to Dynarr_largest() is to ensure that
-
-   Dynarr_set_length(d, len)
-      [MACRO] Set the length of D to LEN, resizing the dynarr as
-      necessary to make sure enough space is available.  there are no
-      restrictions on LEN other than available memory and that it must
-      be at least 0.  Note that
-
-   Dynarr_set_length_and_zero(d, len)
-      [MACRO] Like Dynarr_set_length(d, len) but also, if increasing
-      the length, zero out the memory between the old and new lengths,
-      i.e. starting just past the previous last element and up through
-      the new last element.
-
-   Dynarr_incrementr(d)
-      [MACRO] Increments the length of D by 1.  Equivalent to
-      Dynarr_set_lengthr(d, Dynarr_length(d) + 1).
-
-   Dynarr_increment(d)
-      [MACRO] Increments the length of D by 1.  Equivalent to
-      Dynarr_set_length(d, Dynarr_length(d) + 1).
-
-   Dynarr_reset(d)
-      [MACRO] Reset the length of a dynamic array to 0.
-
-   Dynarr_resize(d, maxval)
-      Resize the internal dynarr storage to so that it can hold at least
-      MAXVAL elements.  Resizing is done using a geometric series
-      (repeatedly multiply the old maximum by a constant, normally 1.5,
-      till a large enough size is reached), so this will be efficient
-      even if resizing larger by one element at a time.  This is mostly
-      an internal function.
-
-
-
-  ************* Adding/deleting elements to/from a dynarr *************
-
-   Dynarr_add(d, el)
-      [MACRO] Add an element to the end of a dynamic array.  EL is a pointer
-      to the element; the element itself is stored in the array, however.
-      No function call is performed unless the array needs to be resized.
-
-   Dynarr_add_many(d, base, len)
-      [MACRO] Add LEN elements to the end of the dynamic array.  The elements
-      should be contiguous in memory, starting at BASE.  If BASE if NULL,
-      just make space for the elements; don't actually add them.
-
-   Dynarr_prepend_many(d, base, len)
-      [MACRO] Prepend LEN elements to the beginning of the dynamic array.
-      The elements should be contiguous in memory, starting at BASE.
-      If BASE if NULL, just make space for the elements; don't actually
-      add them.
-
-   Dynarr_insert_many(d, base, len, pos)
-      Insert LEN elements to the dynamic array starting at position
-      POS.  The elements should be contiguous in memory, starting at BASE.
-      If BASE if NULL, just make space for the elements; don't actually
-      add them.
-
-   type Dynarr_pop(d)
-      [MACRO] Pop the last element off the dynarr and return it.
-
-   Dynarr_delete(d, i)
-      [MACRO] Delete an element from the dynamic array at position I.
-
-   Dynarr_delete_many(d, pos, len)
-      Delete LEN elements from the dynamic array starting at position
-      POS.
-
-   Dynarr_zero_many(d, pos, len)
-      Zero out LEN elements in the dynarr D starting at position POS.
-
-   Dynarr_delete_by_pointer(d, p)
-      [MACRO] Delete an element from the dynamic array at pointer P,
-      which must point within the block of memory that stores the data.
-      P should be obtained using Dynarr_atp().
-
-  ************* Dynarr locking *************
-
-   Dynarr_lock(d)
-      Lock the dynarr against further locking or writing.  With error-checking
-      enabled, any attempts to write into a locked dynarr or re-lock an
-      already locked one will cause an assertion failure and abort.
-
-   Dynarr_unlock(d)
-      Unlock a locked dynarr, allowing writing into it.
-
-  ************* Dynarr global variables *************
-
-   Dynarr_min_size
-      Minimum allowable size for a dynamic array when it is resized.
-
-*/
-
-#include <config.h>
-#include "lisp.h"
-
-static const struct memory_description const_Ascbyte_ptr_description_1[] = {
-  { XD_ASCII_STRING, 0 },
-  { XD_END }
-};
-
-const struct sized_memory_description const_Ascbyte_ptr_description = {
-  sizeof (const Ascbyte *),
-  const_Ascbyte_ptr_description_1
-};
-
-static const struct memory_description const_Ascbyte_ptr_dynarr_description_1[] = {
-  XD_DYNARR_DESC (const_Ascbyte_ptr_dynarr, &const_Ascbyte_ptr_description),
-  { XD_END }
-};
-
-const struct sized_memory_description const_Ascbyte_ptr_dynarr_description = {
-  sizeof (const_Ascbyte_ptr_dynarr),
-  const_Ascbyte_ptr_dynarr_description_1
-};
-
-
-static Elemcount Dynarr_min_size = 8;
-
-static void
-Dynarr_realloc (Dynarr *dy, Elemcount new_size)
-{
-  if (DUMPEDP (dy->base))
-    {
-      void *new_base = malloc (new_size * Dynarr_elsize (dy));
-      memcpy (new_base, dy->base, 
-	      (Dynarr_max (dy) < new_size ? Dynarr_max (dy) : new_size) *
-	      Dynarr_elsize (dy));
-      dy->base = new_base;
-    }
-  else
-    dy->base = xrealloc (dy->base, new_size * Dynarr_elsize (dy));
-}
-
-void *
-Dynarr_newf (Bytecount elsize)
-{
-  Dynarr *d = xnew_and_zero (Dynarr);
-  d->elsize_ = elsize;
-
-  return d;
-}
-
-#ifdef NEW_GC
-DEFINE_DUMPABLE_INTERNAL_LISP_OBJECT ("dynarr", dynarr,
-				      0, 0,
-				      Dynarr);
-
-static void
-Dynarr_lisp_realloc (Dynarr *dy, Elemcount new_size)
-{
-  void *new_base =
-    XPNTR (alloc_sized_lrecord_array (Dynarr_elsize (dy), new_size,
-				      dy->lisp_imp));
-  if (dy->base)
-    memcpy (new_base, dy->base, 
-	    (Dynarr_max (dy) < new_size ? Dynarr_max (dy) : new_size) *
-	    Dynarr_elsize (dy));
-  dy->base = new_base;
-}
-
-void *
-Dynarr_lisp_newf (Bytecount elsize, 
-		  const struct lrecord_implementation *dynarr_imp, 
-		  const struct lrecord_implementation *imp)
-{
-  Dynarr *d = (Dynarr *) XPNTR (alloc_sized_lrecord (sizeof (Dynarr),
-                                                     dynarr_imp));
-  d->elsize_ = elsize;
-  d->lisp_imp = imp;
-
-  return d;
-}
-#endif /* not NEW_GC */
-
-void
-Dynarr_resize (void *d, Elemcount size)
-{
-  Elemcount newsize;
-  double multiplier;
-  Dynarr *dy = (Dynarr *) Dynarr_verify (d);
-
-  if (Dynarr_max (dy) <= 8)
-    multiplier = 2;
-  else
-    multiplier = 1.5;
-
-  for (newsize = Dynarr_max (dy); newsize < size;)
-    newsize = max (Dynarr_min_size, (Elemcount) (multiplier * newsize));
-
-  /* Don't do anything if the array is already big enough. */
-  if (newsize > Dynarr_max (dy))
-    {
-#ifdef NEW_GC
-      if (dy->lisp_imp)
-	Dynarr_lisp_realloc (dy, newsize);
-      else
-	Dynarr_realloc (dy, newsize);
-#else /* not NEW_GC */
-      Dynarr_realloc (dy, newsize);
-#endif /* not NEW_GC */
-      dy->max_ = newsize;
-    }
-}
-
-/* Add a number of contiguous elements to the array starting at POS. */
-
-void
-Dynarr_insert_many (void *d, const void *base, Elemcount len, Elemcount pos)
-{
-  Dynarr *dy = Dynarr_verify_mod (d);
-  Elemcount old_len = Dynarr_length (dy);
-
-  /* #### This could conceivably be wrong, if code wants to access stuff
-     between len and largest. */
-  dynarr_checking_assert (pos >= 0 && pos <= old_len);
-  dynarr_checking_assert (len >= 0);
-  Dynarr_increase_length (dy, old_len + len);
-
-  if (pos != old_len)
-    {
-      memmove ((Rawbyte *) dy->base + (pos + len)*Dynarr_elsize (dy),
-	       (Rawbyte *) dy->base + pos*Dynarr_elsize (dy),
-	       (old_len - pos)*Dynarr_elsize (dy));
-    }
-  /* Some functions call us with a value of 0 to mean "reserve space but
-     don't write into it" */
-  if (base)
-    memcpy ((Rawbyte *) dy->base + pos*Dynarr_elsize (dy), base,
-	    len*Dynarr_elsize (dy));
-}
-
-void
-Dynarr_delete_many (void *d, Elemcount pos, Elemcount len)
-{
-  Dynarr *dy = Dynarr_verify_mod (d);
-
-  dynarr_checking_assert (pos >= 0 && len >= 0 &&
-			  pos + len <= Dynarr_length (dy));
-
-  memmove ((Rawbyte *) dy->base + pos*Dynarr_elsize (dy),
-	   (Rawbyte *) dy->base + (pos + len)*Dynarr_elsize (dy),
-	   (Dynarr_length (dy) - pos - len)*Dynarr_elsize (dy));
-
-  Dynarr_set_length_1 (dy, Dynarr_length (dy) - len);
-}
-
-void
-Dynarr_free (void *d)
-{
-  Dynarr *dy = (Dynarr *) d;
-
-#ifdef NEW_GC
-  if (dy->base && !DUMPEDP (dy->base))
-    {
-      if (!dy->lisp_imp)
-	xfree (dy->base);
-    }
-  if(!DUMPEDP (dy))
-    {
-      if (!dy->lisp_imp)
-	xfree (dy);
-    }
-#else /* not NEW_GC */
-  if (dy->base && !DUMPEDP (dy->base))
-    xfree (dy->base);
-  if(!DUMPEDP (dy))
-    xfree (dy);
-#endif /* not NEW_GC */
-}
-
-#ifdef MEMORY_USAGE_STATS
-
-/* Return memory usage for dynarr D.  The returned value is the total
-   amount of bytes actually being used for the dynarr, including all
-   overhead.  The extra amount of space in the dynarr that is
-   allocated beyond what was requested is returned in DYNARR_OVERHEAD
-   in STATS.  The extra amount of space that malloc() allocates beyond
-   what was requested of it is returned in MALLOC_OVERHEAD in STATS.
-   See the comment above the definition of this structure. */
-
-Bytecount
-Dynarr_memory_usage (void *d, struct usage_stats *stats)
-{
-  Bytecount total = 0;
-  Dynarr *dy = (Dynarr *) d;
-
-  /* We have to be a bit tricky here because not all of the
-     memory that malloc() will claim as "requested" was actually
-     requested. */
-
-  if (dy->base)
-    {
-      Bytecount malloc_used =
-	malloced_storage_size (dy->base, Dynarr_elsize (dy) * Dynarr_max (dy),
-			       0);
-      /* #### This may or may not be correct.  Some dynarrs would
-	 prefer that we use dy->len instead of dy->largest here. */
-      Bytecount was_requested = Dynarr_elsize (dy) * Dynarr_largest (dy);
-      Bytecount dynarr_overhead =
-	Dynarr_elsize (dy) * (Dynarr_max (dy) - Dynarr_largest (dy));
-
-      total += malloc_used;
-      stats->was_requested += was_requested;
-      stats->dynarr_overhead += dynarr_overhead;
-      /* And the remainder must be malloc overhead. */
-      stats->malloc_overhead +=
-	malloc_used - was_requested - dynarr_overhead;
-    }
-
-  total += malloced_storage_size (d, sizeof (*dy), stats);
-
-  return total;
-}
-
-#endif /* MEMORY_USAGE_STATS */
-
-/* Version of malloc() that will be extremely efficient when allocation
-   nearly always occurs in LIFO (stack) order.
-
-   #### Perhaps shouldn't be in this file, but where else? */
-
-typedef struct
-{
-  Dynarr_declare (char_dynarr *);
-} char_dynarr_dynarr;
-
-char_dynarr_dynarr *stack_like_free_list;
-char_dynarr_dynarr *stack_like_in_use_list;
-
-void *
-stack_like_malloc (Bytecount size)
-{
-  char_dynarr *this_one;
-  if (!stack_like_free_list)
-    {
-      stack_like_free_list = Dynarr_new2 (char_dynarr_dynarr,
-					  char_dynarr *);
-      stack_like_in_use_list = Dynarr_new2 (char_dynarr_dynarr,
-					    char_dynarr *);
-    }
-
-  if (Dynarr_length (stack_like_free_list) > 0)
-    this_one = Dynarr_pop (stack_like_free_list);
-  else
-    this_one = Dynarr_new (char);
-  Dynarr_add (stack_like_in_use_list, this_one);
-  Dynarr_reset (this_one);
-  Dynarr_add_many (this_one, 0, size);
-  return Dynarr_begin (this_one);
-}
-
-void
-stack_like_free (void *val)
-{
-  Elemcount len = Dynarr_length (stack_like_in_use_list);
-  assert (len > 0);
-  /* The vast majority of times, we will be called in a last-in first-out
-     order, and the item at the end of the list will be the one we're
-     looking for, so just check for this first and avoid any function
-     calls. */
-  if (Dynarr_begin (Dynarr_at (stack_like_in_use_list, len - 1)) == val)
-    {
-      char_dynarr *this_one = Dynarr_pop (stack_like_in_use_list);
-      Dynarr_add (stack_like_free_list, this_one);
-    }
-  else
-    {
-      /* Find the item and delete it. */
-      int i;
-      assert (len >= 2);
-      for (i = len - 2; i >= 0; i--)
-	if (Dynarr_begin (Dynarr_at (stack_like_in_use_list, i)) ==
-	    val)
-	  {
-	    char_dynarr *this_one = Dynarr_at (stack_like_in_use_list, i);
-	    Dynarr_add (stack_like_free_list, this_one);
-	    Dynarr_delete (stack_like_in_use_list, i);
-	    return;
-	  }
-
-      ABORT ();
-    }
-}

--- a/src/emacs.c	Sun Mar 21 04:41:49 2010 -0500
+++ b/src/emacs.c	Mon Mar 22 19:12:15 2010 -0500
@@ -1508,6 +1508,7 @@
 #ifdef NEW_GC
       syms_of_vdb ();
 #endif /* NEW_GC */
+      syms_of_array ();
       syms_of_buffer ();
       syms_of_bytecode ();
       syms_of_callint ();

--- a/src/extents.c	Sun Mar 21 04:41:49 2010 -0500
+++ b/src/extents.c	Mon Mar 22 19:12:15 2010 -0500
@@ -231,88 +231,6 @@
 #include "gutter.h"
 
 /* ------------------------------- */
-/*            gap array            */
-/* ------------------------------- */
-
-/* Note that this object is not extent-specific and should perhaps be
-   moved into another file. */
-
-/* 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;
-#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;
-
-#ifndef NEW_GC
-static Gap_Array_Marker *gap_array_marker_freelist;
-#endif /* not NEW_GC */
-
-/* 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 int. */
-#define GAP_ARRAY_MEMEL_ADDR(ga, memel) ((ga)->array + (ga)->elsize*(memel))
-
-/* Number of elements currently in a gap array */
-#define GAP_ARRAY_NUM_ELS(ga) ((ga)->numels)
-
-#define GAP_ARRAY_ARRAY_TO_MEMORY_POS(ga, pos) \
-  ((pos) <= (ga)->gap ? (pos) : (pos) + (ga)->gapsize)
-
-#define GAP_ARRAY_MEMORY_TO_ARRAY_POS(ga, pos) \
-  ((pos) <= (ga)->gap ? (pos) : (pos) - (ga)->gapsize)
-
-/* Convert an array position into the address of the element at
-   (i.e. after) that position. */
-#define GAP_ARRAY_EL_ADDR(ga, pos) ((pos) < (ga)->gap ? \
-  GAP_ARRAY_MEMEL_ADDR(ga, pos) : \
-  GAP_ARRAY_MEMEL_ADDR(ga, (pos) + (ga)->gapsize))
-
-/* ------------------------------- */
 /*          extent list            */
 /* ------------------------------- */
 
@@ -379,7 +297,7 @@
 #define EXTENT_E_LESS_EQUAL(e1,e2) \
   EXTENT_E_LESS_EQUAL_VALS (e1, extent_start (e2), extent_end (e2))
 
-#define EXTENT_GAP_ARRAY_AT(ga, pos) (* (EXTENT *) GAP_ARRAY_EL_ADDR(ga, pos))
+#define EXTENT_GAP_ARRAY_AT(ga, pos) gap_array_at (ga, pos, EXTENT)
 
 /* ------------------------------- */
 /*     buffer-extent primitives    */
@@ -510,271 +428,6 @@
 
 
 /************************************************************************/
-/*                       Generalized gap array                          */
-/************************************************************************/
-
-/* This generalizes the "array with a gap" model used to store buffer
-   characters.  This is based on the stuff in insdel.c and should
-   probably be merged with it.  This is not extent-specific and should
-   perhaps be moved into a separate file. */
-
-/* ------------------------------- */
-/*        internal functions       */
-/* ------------------------------- */
-
-/* Adjust the gap array markers in the range (FROM, TO].  Parallel to
-   adjust_markers() in insdel.c. */
-
-static void
-gap_array_adjust_markers (Gap_Array *ga, Memxpos from,
-			  Memxpos to, Elemcount amount)
-{
-  Gap_Array_Marker *m;
-
-  for (m = ga->markers; m; m = m->next)
-    m->pos = do_marker_adjustment (m->pos, from, to, amount);
-}
-
-static void
-gap_array_recompute_derived_values (Gap_Array *ga)
-{
-  ga->offset_past_gap = ga->elsize * (ga->gap + ga->gapsize);
-  ga->els_past_gap = ga->numels - ga->gap;
-}
-
-/* Move the gap to array position POS.  Parallel to move_gap() in
-   insdel.c but somewhat simplified. */
-
-static void
-gap_array_move_gap (Gap_Array *ga, Elemcount pos)
-{
-  Elemcount gap = ga->gap;
-  Elemcount gapsize = ga->gapsize;
-
-  if (pos < gap)
-    {
-      memmove (GAP_ARRAY_MEMEL_ADDR (ga, pos + gapsize),
-	       GAP_ARRAY_MEMEL_ADDR (ga, pos),
-	       (gap - pos)*ga->elsize);
-      gap_array_adjust_markers (ga, (Memxpos) pos, (Memxpos) gap,
-				gapsize);
-    }
-  else if (pos > gap)
-    {
-      memmove (GAP_ARRAY_MEMEL_ADDR (ga, gap),
-	       GAP_ARRAY_MEMEL_ADDR (ga, gap + gapsize),
-	       (pos - gap)*ga->elsize);
-      gap_array_adjust_markers (ga, (Memxpos) (gap + gapsize),
-				(Memxpos) (pos + gapsize), - gapsize);
-    }
-  ga->gap = pos;
-
-  gap_array_recompute_derived_values (ga);
-}
-
-/* Make the gap INCREMENT characters longer.  Parallel to make_gap() in
-   insdel.c.  The gap array may be moved, so assign the return value back
-   to the array pointer. */
-
-static Gap_Array *
-gap_array_make_gap (Gap_Array *ga, Elemcount increment)
-{
-  Elemcount real_gap_loc;
-  Elemcount old_gap_size;
-
-  /* If we have to get more space, get enough to last a while.  We use
-     a geometric progression that saves on realloc space. */
-  increment += 100 + ga->numels / 8;
-
-#ifdef NEW_GC
-  ga = (Gap_Array *) mc_realloc (ga,
-				 offsetof (Gap_Array, array) +
-				 (ga->numels + ga->gapsize + increment) *
-				 ga->elsize);
-#else /* not NEW_GC */
-  ga = (Gap_Array *) xrealloc (ga,
-			       offsetof (Gap_Array, array) +
-			       (ga->numels + ga->gapsize + increment) *
-			       ga->elsize);
-#endif /* not NEW_GC */
-  if (ga == 0)
-    memory_full ();
-
-  real_gap_loc = ga->gap;
-  old_gap_size = ga->gapsize;
-
-  /* Call the newly allocated space a gap at the end of the whole space.  */
-  ga->gap = ga->numels + ga->gapsize;
-  ga->gapsize = increment;
-
-  /* Move the new gap down to be consecutive with the end of the old one.
-     This adjusts the markers properly too.  */
-  gap_array_move_gap (ga, real_gap_loc + old_gap_size);
-
-  /* Now combine the two into one large gap.  */
-  ga->gapsize += old_gap_size;
-  ga->gap = real_gap_loc;
-
-  gap_array_recompute_derived_values (ga);
-
-  return ga;
-}
-
-/* ------------------------------- */
-/*        external functions       */
-/* ------------------------------- */
-
-/* Insert NUMELS elements (pointed to by ELPTR) into the specified
-   gap array at POS.  The gap array may be moved, so assign the
-   return value back to the array pointer. */
-
-static Gap_Array *
-gap_array_insert_els (Gap_Array *ga, Elemcount pos, void *elptr,
-		      Elemcount numels)
-{
-  assert (pos >= 0 && pos <= ga->numels);
-  if (ga->gapsize < numels)
-    ga = gap_array_make_gap (ga, numels - ga->gapsize);
-  if (pos != ga->gap)
-    gap_array_move_gap (ga, pos);
-
-  memcpy (GAP_ARRAY_MEMEL_ADDR (ga, ga->gap), (char *) elptr,
-	  numels*ga->elsize);
-  ga->gapsize -= numels;
-  ga->gap += numels;
-  ga->numels += numels;
-  gap_array_recompute_derived_values (ga);
-  /* This is the equivalent of insert-before-markers.
-
-     #### Should only happen if marker is "moves forward at insert" type.
-     */
-
-  gap_array_adjust_markers (ga, pos - 1, pos, numels);
-  return ga;
-}
-
-/* Delete NUMELS elements from the specified gap array, starting at FROM. */
-
-static void
-gap_array_delete_els (Gap_Array *ga, Elemcount from, Elemcount numdel)
-{
-  Elemcount to = from + numdel;
-  Elemcount gapsize = ga->gapsize;
-
-  assert (from >= 0);
-  assert (numdel >= 0);
-  assert (to <= ga->numels);
-
-  /* Make sure the gap is somewhere in or next to what we are deleting.  */
-  if (to < ga->gap)
-    gap_array_move_gap (ga, to);
-  if (from > ga->gap)
-    gap_array_move_gap (ga, from);
-
-  /* Relocate all markers pointing into the new, larger gap
-     to point at the end of the text before the gap.  */
-  gap_array_adjust_markers (ga, to + gapsize, to + gapsize,
-			    - numdel - gapsize);
-
-  ga->gapsize += numdel;
-  ga->numels -= numdel;
-  ga->gap = from;
-  gap_array_recompute_derived_values (ga);
-}
-
-static Gap_Array_Marker *
-gap_array_make_marker (Gap_Array *ga, Elemcount pos)
-{
-  Gap_Array_Marker *m;
-
-  assert (pos >= 0 && pos <= ga->numels);
-#ifdef NEW_GC
-    m = XGAP_ARRAY_MARKER (ALLOC_NORMAL_LISP_OBJECT (gap_array_marker));
-#else /* not NEW_GC */
-  if (gap_array_marker_freelist)
-    {
-      m = gap_array_marker_freelist;
-      gap_array_marker_freelist = gap_array_marker_freelist->next;
-    }
-  else
-    m = xnew (Gap_Array_Marker);
-#endif /* not NEW_GC */
-
-  m->pos = GAP_ARRAY_ARRAY_TO_MEMORY_POS (ga, pos);
-  m->next = ga->markers;
-  ga->markers = m;
-  return m;
-}
-
-static void
-gap_array_delete_marker (Gap_Array *ga, Gap_Array_Marker *m)
-{
-  Gap_Array_Marker *p, *prev;
-
-  for (prev = 0, p = ga->markers; p && p != m; prev = p, p = p->next)
-    ;
-  assert (p);
-  if (prev)
-    prev->next = p->next;
-  else
-    ga->markers = p->next;
-#ifndef NEW_GC
-  m->next = gap_array_marker_freelist;
-  m->pos = 0xDEADBEEF; /* -559038737 base 10 */
-  gap_array_marker_freelist = m;
-#endif /* not NEW_GC */
-}
-
-#ifndef NEW_GC
-static void
-gap_array_delete_all_markers (Gap_Array *ga)
-{
-  Gap_Array_Marker *p, *next;
-
-  for (p = ga->markers; p; p = next)
-    {
-      next = p->next;
-      p->next = gap_array_marker_freelist;
-      p->pos = 0xDEADBEEF; /* -559038737 as an int */
-      gap_array_marker_freelist = p;
-    }
-}
-#endif /* not NEW_GC */
-
-static void
-gap_array_move_marker (Gap_Array *ga, Gap_Array_Marker *m, Elemcount pos)
-{
-  assert (pos >= 0 && pos <= ga->numels);
-  m->pos = GAP_ARRAY_ARRAY_TO_MEMORY_POS (ga, pos);
-}
-
-#define gap_array_marker_pos(ga, m) \
-  GAP_ARRAY_MEMORY_TO_ARRAY_POS (ga, (m)->pos)
-
-static Gap_Array *
-make_gap_array (Elemcount elsize)
-{
-#ifdef NEW_GC
-  Gap_Array *ga = XGAP_ARRAY (ALLOC_SIZED_LISP_OBJECT (sizeof (Gap_Array),
-						       gap_array));
-#else /* not NEW_GC */
-  Gap_Array *ga = xnew_and_zero (Gap_Array);
-#endif /* not NEW_GC */
-  ga->elsize = elsize;
-  return ga;
-}
-
-#ifndef NEW_GC
-static void
-free_gap_array (Gap_Array *ga)
-{
-  gap_array_delete_all_markers (ga);
-  xfree (ga);
-}
-#endif /* not NEW_GC */
-
-
-/************************************************************************/
 /*                       Extent list primitives                         */
 /************************************************************************/
 
@@ -791,7 +444,7 @@
 */
 
 /* Number of elements in an extent list */
-#define extent_list_num_els(el) GAP_ARRAY_NUM_ELS (el->start)
+#define extent_list_num_els(el) gap_array_length (el->start)
 
 /* Return the position at which EXTENT is located in the specified extent
    list (in the display order if ENDP is 0, in the e-order otherwise).
@@ -805,7 +458,7 @@
 extent_list_locate (Extent_List *el, EXTENT extent, int endp, int *foundp)
 {
   Gap_Array *ga = endp ? el->end : el->start;
-  int left = 0, right = GAP_ARRAY_NUM_ELS (ga);
+  int left = 0, right = gap_array_length (ga);
   int oldfoundpos, foundpos;
   int found;
 
@@ -825,7 +478,7 @@
   /* Now we're at the beginning of all equal extents. */
   found = 0;
   oldfoundpos = foundpos = left;
-  while (foundpos < GAP_ARRAY_NUM_ELS (ga))
+  while (foundpos < gap_array_length (ga))
     {
       EXTENT e = EXTENT_GAP_ARRAY_AT (ga, foundpos);
       if (e == extent)
@@ -880,7 +533,7 @@
 {
   Gap_Array *ga = endp ? el->end : el->start;
 
-  assert (pos >= 0 && pos < GAP_ARRAY_NUM_ELS (ga));
+  assert (pos >= 0 && pos < gap_array_length (ga));
   return EXTENT_GAP_ARRAY_AT (ga, pos);
 }
 
@@ -917,8 +570,8 @@
 static void
 extent_list_delete_all (Extent_List *el)
 {
-  gap_array_delete_els (el->start, 0, GAP_ARRAY_NUM_ELS (el->start));
-  gap_array_delete_els (el->end, 0, GAP_ARRAY_NUM_ELS (el->end));
+  gap_array_delete_els (el->start, 0, gap_array_length (el->start));
+  gap_array_delete_els (el->end, 0, gap_array_length (el->end));
 }
 
 static Extent_List_Marker *
@@ -980,8 +633,8 @@
 #else /* not NEW_GC */
   Extent_List *el = xnew (Extent_List);
 #endif /* not NEW_GC */
-  el->start = make_gap_array (sizeof (EXTENT));
-  el->end = make_gap_array (sizeof (EXTENT));
+  el->start = make_gap_array (sizeof (EXTENT), 1);
+  el->end = make_gap_array (sizeof (EXTENT), 1);
   el->markers = 0;
   return el;
 }
@@ -1080,66 +733,7 @@
 #endif /* not NEW_GC */
 static void soe_invalidate (Lisp_Object obj);
 
-extern const struct sized_memory_description gap_array_marker_description;
-
-static const struct memory_description gap_array_marker_description_1[] = { 
-#ifdef NEW_GC
-  { XD_LISP_OBJECT, offsetof (Gap_Array_Marker, next) },
-#else /* not NEW_GC */
-  { XD_BLOCK_PTR, offsetof (Gap_Array_Marker, next), 1,
-    { &gap_array_marker_description } },
-#endif /* not NEW_GC */
-  { XD_END }
-};
-
-#ifdef NEW_GC
-DEFINE_NODUMP_INTERNAL_LISP_OBJECT ("gap-array-marker", gap_array_marker,
-				    0, gap_array_marker_description_1,
-				    struct gap_array_marker);
-#else /* not NEW_GC */
-const struct sized_memory_description gap_array_marker_description = {
-  sizeof (Gap_Array_Marker),
-  gap_array_marker_description_1
-};
-#endif /* not NEW_GC */
-
-static const struct memory_description lispobj_gap_array_description_1[] = { 
-  { XD_ELEMCOUNT, offsetof (Gap_Array, gap) },
-  { XD_BYTECOUNT, offsetof (Gap_Array, offset_past_gap) },
-  { XD_ELEMCOUNT, offsetof (Gap_Array, els_past_gap) },
-#ifdef NEW_GC
-  { XD_LISP_OBJECT, offsetof (Gap_Array, markers) },
-#else /* not NEW_GC */
-  { XD_BLOCK_PTR, offsetof (Gap_Array, markers), 1,
-    { &gap_array_marker_description }, XD_FLAG_NO_KKCC },
-#endif /* not NEW_GC */
-  { XD_BLOCK_ARRAY, offsetof (Gap_Array, array), XD_INDIRECT (0, 0),
-    { &lisp_object_description } },
-  { XD_BLOCK_ARRAY, XD_INDIRECT (1, offsetof (Gap_Array, array)),
-    XD_INDIRECT (2, 0), { &lisp_object_description } },
-  { XD_END }
-};
-
-#ifdef NEW_GC
-
-static Bytecount
-size_gap_array (Lisp_Object obj)
-{
-  Gap_Array *ga = XGAP_ARRAY (obj);
-  return offsetof (Gap_Array, array) + (ga->numels + ga->gapsize) * ga->elsize;
-}
-
-DEFINE_NODUMP_SIZABLE_INTERNAL_LISP_OBJECT ("gap-array", gap_array,
-					    0,
-					    lispobj_gap_array_description_1,
-					    size_gap_array,
-					    struct gap_array);
-#else /* not NEW_GC */
-static const struct sized_memory_description lispobj_gap_array_description = {
-  sizeof (Gap_Array),
-  lispobj_gap_array_description_1
-};
-
+#ifndef NEW_GC
 extern const struct sized_memory_description extent_list_marker_description;
 #endif /* not NEW_GC */
 
@@ -7445,8 +7039,6 @@
   INIT_LISP_OBJECT (extent_info);
   INIT_LISP_OBJECT (extent_auxiliary);
 #ifdef NEW_GC
-  INIT_LISP_OBJECT (gap_array_marker);
-  INIT_LISP_OBJECT (gap_array);
   INIT_LISP_OBJECT (extent_list_marker);
   INIT_LISP_OBJECT (extent_list);
   INIT_LISP_OBJECT (stack_of_extents);

--- a/src/extents.h	Sun Mar 21 04:41:49 2010 -0500
+++ b/src/extents.h	Mon Mar 22 19:12:15 2010 -0500
@@ -50,25 +50,6 @@
 #define CONCHECK_EXTENT_INFO(x) CONCHECK_RECORD (x, extent_info)
 
 #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)
-
 struct extent_list_marker;
 
 DECLARE_LISP_OBJECT (extent_list_marker, struct extent_list_marker);

--- a/src/gc.c	Sun Mar 21 04:41:49 2010 -0500
+++ b/src/gc.c	Mon Mar 22 19:12:15 2010 -0500
@@ -557,8 +557,13 @@
       EMACS_INT offset = lispdesc_indirect_count (desc[pos].offset, desc, obj);
       if (offset == max_offset)
 	{
+#if 0
+	  /* This can legitimately happen with gap arrays -- if there are
+	     no elements in the array, and the gap size is 0, then both
+	     parts of the array will be of size 0 and in the same place. */
 	  stderr_out ("Two relocatable elements at same offset?\n");
 	  ABORT ();
+#endif
 	}
       else if (offset > max_offset)
 	{

--- a/src/lisp.h	Sun Mar 21 04:41:49 2010 -0500
+++ b/src/lisp.h	Mon Mar 22 19:12:15 2010 -0500
@@ -1732,583 +1732,10 @@
 }
 
 /************************************************************************/
-/**    Definitions of dynamic arrays (dynarrs) and other allocators    **/
+/**            Definitions of dynarrs and other allocators             **/
 /************************************************************************/
 
-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)
+#include "array.h"
 
 /************* Dynarr typedefs *************/
 
@@ -2436,12 +1863,6 @@
 } Lisp_Object_ptr_dynarr;
 
 
-/************* Stack-like malloc/free: Another allocator *************/
-
-void *stack_like_malloc (Bytecount size);
-void stack_like_free (void *val);
-
-
 /************************************************************************/
 /**              Definitions of other basic Lisp objects               **/
 /************************************************************************/

--- a/src/rangetab.c	Sun Mar 21 04:41:49 2010 -0500
+++ b/src/rangetab.c	Mon Mar 22 19:12:15 2010 -0500
@@ -90,8 +90,8 @@
   Lisp_Range_Table *rt = XRANGE_TABLE (obj);
   int i;
 
-  for (i = 0; i < Dynarr_length (rt->entries); i++)
-    mark_object (Dynarr_at (rt->entries, i).val);
+  for (i = 0; i < gap_array_length (rt->entries); i++)
+    mark_object (rangetab_gap_array_at (rt->entries, i).val);
   
   return Qnil;
 }
@@ -108,9 +108,9 @@
 			   1, range_table_type_to_symbol (rt->type));
   else
     write_ascstring (printcharfun, "#<range-table ");
-  for (i = 0; i < Dynarr_length (rt->entries); i++)
+  for (i = 0; i < gap_array_length (rt->entries); i++)
     {
-      struct range_table_entry *rte = Dynarr_atp (rt->entries, i);
+      struct range_table_entry rte = rangetab_gap_array_at (rt->entries, i);
       int so, ec;
       if (i > 0)
 	write_ascstring (printcharfun, " ");
@@ -124,11 +124,11 @@
 	}
       write_fmt_string (printcharfun, "%c%ld %ld%c ",
 			print_readably ? '(' : so ? '(' : '[',
-			(long) (rte->first - so),
-			(long) (rte->last - ec),
+			(long) (rte.first - so),
+			(long) (rte.last - ec),
 			print_readably ? ')' : ec ? ']' : ')'
 			);
-      print_internal (rte->val, printcharfun, 1);
+      print_internal (rte.val, printcharfun, 1);
     }
   if (print_readably)
     write_ascstring (printcharfun, "))");
@@ -143,13 +143,15 @@
   Lisp_Range_Table *rt2 = XRANGE_TABLE (obj2);
   int i;
 
-  if (Dynarr_length (rt1->entries) != Dynarr_length (rt2->entries))
+  if (gap_array_length (rt1->entries) != gap_array_length (rt2->entries))
     return 0;
 
-  for (i = 0; i < Dynarr_length (rt1->entries); i++)
+  for (i = 0; i < gap_array_length (rt1->entries); i++)
     {
-      struct range_table_entry *rte1 = Dynarr_atp (rt1->entries, i);
-      struct range_table_entry *rte2 = Dynarr_atp (rt2->entries, i);
+      struct range_table_entry *rte1 =
+	rangetab_gap_array_atp (rt1->entries, i);
+      struct range_table_entry *rte2 =
+	rangetab_gap_array_atp (rt2->entries, i);
 
       if (rte1->first != rte2->first
 	  || rte1->last != rte2->last
@@ -171,7 +173,7 @@
 {
   Lisp_Range_Table *rt = XRANGE_TABLE (obj);
   int i;
-  int size = Dynarr_length (rt->entries);
+  int size = gap_array_length (rt->entries);
   Hashcode hash = size;
 
   /* approach based on internal_array_hash(). */
@@ -179,8 +181,8 @@
     {
       for (i = 0; i < size; i++)
 	hash = HASH2 (hash,
-		      range_table_entry_hash (Dynarr_atp (rt->entries, i),
-					      depth));
+		      range_table_entry_hash
+		      (rangetab_gap_array_atp (rt->entries, i), depth));
       return hash;
     }
 
@@ -188,9 +190,9 @@
      A slightly better approach would be to offset by some
      noise factor from the points chosen below. */
   for (i = 0; i < 5; i++)
-    hash = HASH2 (hash, range_table_entry_hash (Dynarr_atp (rt->entries,
-							    i*size/5),
-						depth));
+    hash = HASH2 (hash,
+		  range_table_entry_hash
+		  (rangetab_gap_array_atp (rt->entries, i*size/5), depth));
   return hash;
 }
 
@@ -204,19 +206,18 @@
   rte_description_1
 };
 
-static const struct memory_description rted_description_1[] = {
-  XD_DYNARR_DESC (range_table_entry_dynarr, &rte_description),
+static const struct memory_description rtega_description_1[] = {
+  XD_GAP_ARRAY_DESC (&rte_description),
   { XD_END }
 };
 
-static const struct sized_memory_description rted_description = {
-  sizeof (range_table_entry_dynarr),
-  rted_description_1
+static const struct sized_memory_description rtega_description = {
+  0, rtega_description_1
 };
 
 static const struct memory_description range_table_description[] = {
   { XD_BLOCK_PTR,  offsetof (Lisp_Range_Table, entries),  1,
-    { &rted_description } },
+    { &rtega_description } },
   { XD_END }
 };
 
@@ -237,12 +238,12 @@
 {
   int i;
 
-  for (i = 0; i < Dynarr_length (rt->entries); i++)
+  for (i = 0; i < gap_array_length (rt->entries); i++)
     {
-      struct range_table_entry *rte = Dynarr_atp (rt->entries, i);
+      struct range_table_entry *rte = rangetab_gap_array_atp (rt->entries, i);
       assert (rte->last >= rte->first);
       if (i > 0)
-	assert (Dynarr_at (rt->entries, i - 1).last <= rte->first);
+	assert (rangetab_gap_array_at (rt->entries, i - 1).last <= rte->first);
     }
 }
 
@@ -252,14 +253,18 @@
 
 #endif
 
-/* Look up in a range table without the Dynarr wrapper.
-   Used also by the unified range table format. */
+/* Locate the range table entry corresponding to the value POS, and return
+   it.  If found, FOUNDP is set to 1 and the return value specifies an entry
+   that encloses POS.  Otherwise, FOUNDP is set to 0 and the return value
+   specifies where an entry that encloses POS would be inserted. */
 
-static Lisp_Object
-get_range_table (EMACS_INT pos, int nentries, struct range_table_entry *tab,
-		 Lisp_Object default_)
+static Elemcount
+get_range_table_pos (Elemcount pos, Elemcount nentries,
+		     struct range_table_entry *tab,
+		     Elemcount gappos, Elemcount gapsize,
+		     int *foundp)
 {
-  int left = 0, right = nentries;
+  Elemcount left = 0, right = nentries;
 
   /* binary search for the entry.  Based on similar code in
      extent_list_locate(). */
@@ -267,14 +272,41 @@
     {
       /* RIGHT might not point to a valid entry (i.e. it's at the end
 	 of the list), so NEWPOS must round down. */
-      int newpos = (left + right) >> 1;
-      struct range_table_entry *entry = tab + newpos;
+      Elemcount newpos = (left + right) >> 1;
+      struct range_table_entry *entry =
+	tab + GAP_ARRAY_ARRAY_TO_MEMORY_POS_1 (newpos, gappos, gapsize);
       if (pos >= entry->last)
 	left = newpos + 1;
       else if (pos < entry->first)
 	right = newpos;
       else
-	return entry->val;
+	{
+	  *foundp = 1;
+	  return newpos;
+	}
+    }
+
+  *foundp = 0;
+  return left;
+}
+
+/* Look up in a range table without the gap array wrapper.
+   Used also by the unified range table format. */
+
+static Lisp_Object
+get_range_table (Elemcount pos, Elemcount nentries,
+		 struct range_table_entry *tab,
+		 Elemcount gappos, Elemcount gapsize,
+		 Lisp_Object default_)
+{
+  int foundp;
+  Elemcount entrypos = get_range_table_pos (pos, nentries, tab, gappos,
+					    gapsize, &foundp);
+  if (foundp)
+    {
+      struct range_table_entry *entry =
+	tab + GAP_ARRAY_ARRAY_TO_MEMORY_POS_1 (entrypos, gappos, gapsize);
+      return entry->val;
     }
 
   return default_;
@@ -333,7 +365,7 @@
 {
   Lisp_Object obj = ALLOC_NORMAL_LISP_OBJECT (range_table);
   Lisp_Range_Table *rt = XRANGE_TABLE (obj);
-  rt->entries = Dynarr_new (range_table_entry);
+  rt->entries = make_gap_array (sizeof (struct range_table_entry), 0);
   rt->type = range_table_symbol_to_type (type);
   return obj;
 }
@@ -347,17 +379,20 @@
 {
   Lisp_Range_Table *rt, *rtnew;
   Lisp_Object obj;
+  Elemcount i;
 
   CHECK_RANGE_TABLE (range_table);
   rt = XRANGE_TABLE (range_table);
 
   obj = ALLOC_NORMAL_LISP_OBJECT (range_table);
   rtnew = XRANGE_TABLE (obj);
-  rtnew->entries = Dynarr_new (range_table_entry);
+  rtnew->entries = make_gap_array (sizeof (struct range_table_entry), 0);
   rtnew->type = rt->type;
 
-  Dynarr_add_many (rtnew->entries, Dynarr_begin (rt->entries),
-		   Dynarr_length (rt->entries));
+  for (i = 0; i < gap_array_length (rt->entries); i++)
+    rtnew->entries =
+      gap_array_insert_els (rtnew->entries, i,
+			    rangetab_gap_array_atp (rt->entries, i), 1);
   return obj;
 }
 
@@ -374,8 +409,12 @@
 
   CHECK_INT_COERCE_CHAR (pos);
 
-  return get_range_table (XINT (pos), Dynarr_length (rt->entries),
-			  Dynarr_begin (rt->entries), default_);
+  return get_range_table (XINT (pos), gap_array_length (rt->entries),
+			  gap_array_begin (rt->entries,
+					   struct range_table_entry),
+			  gap_array_gappos (rt->entries),
+			  gap_array_gapsize (rt->entries),
+			  default_);
 }
 
 static void
@@ -415,6 +454,7 @@
   int i;
   int insert_me_here = -1;
   Lisp_Range_Table *rt = XRANGE_TABLE (table);
+  int foundp;
 
   external_to_internal_adjust_ends (rt->type, &first, &last);
   if (first == last)
@@ -424,15 +464,59 @@
        open. #### Should we signal an error? */
     return;
 
+  if (DUMPEDP (rt->entries))
+    rt->entries = gap_array_clone (rt->entries);
+  
+  i = get_range_table_pos (first, gap_array_length (rt->entries),
+			   gap_array_begin (rt->entries,
+					    struct range_table_entry),
+			   gap_array_gappos (rt->entries),
+			   gap_array_gapsize (rt->entries), &foundp);
+
+#ifdef ERROR_CHECK_TYPES
+  if (foundp)
+    {
+      if (i < gap_array_length (rt->entries))
+	{
+	  struct range_table_entry *entry =
+	    rangetab_gap_array_atp (rt->entries, i);
+	  assert (first >= entry->first && first < entry->last);
+	}
+    }
+  else
+    {
+      if (i < gap_array_length (rt->entries))
+	{
+	  struct range_table_entry *entry =
+	    rangetab_gap_array_atp (rt->entries, i);
+	  assert (first < entry->first);
+	}
+      if (i > 0)
+	{
+	  struct range_table_entry *entry =
+	    rangetab_gap_array_atp (rt->entries, i - 1);
+	  assert (first >= entry->last);
+	}
+    }
+#endif /* ERROR_CHECK_TYPES */
+
+  /* If the beginning of the new range isn't within any existing range,
+     it might still be just grazing the end of an end-open range (remember,
+     internally all ranges are start-close end-open); so back up one
+     so we consider this range. */
+  if (!foundp && i > 0)
+    i--;
+  
   /* Now insert in the proper place.  This gets tricky because
      we may be overlapping one or more existing ranges and need
      to fix them up. */
 
   /* First delete all sections of any existing ranges that overlap
      the new range. */
-  for (i = 0; i < Dynarr_length (rt->entries); i++)
+  for (; i < gap_array_length (rt->entries); i++)
     {
-      struct range_table_entry *entry = Dynarr_atp (rt->entries, i);
+      struct range_table_entry *entry =
+	rangetab_gap_array_atp (rt->entries, i);
       /* We insert before the first range that begins at or after the
 	 new range. */
       if (entry->first >= first && insert_me_here < 0)
@@ -476,7 +560,8 @@
 	  insert_me_too.last = entry->last;
 	  insert_me_too.val = entry->val;
 	  entry->last = first;
-	  Dynarr_insert_many (rt->entries, &insert_me_too, 1, i + 1);
+	  rt->entries =
+	    gap_array_insert_els (rt->entries, i + 1, &insert_me_too, 1);
 	}
       else if (entry->last >= last)
 	{
@@ -497,7 +582,7 @@
       else
 	{
 	  /* existing is entirely within new. */
-	  Dynarr_delete_many (rt->entries, i, 1);
+	  gap_array_delete_els (rt->entries, i, 1);
 	  i--; /* back up since everything shifted one to the left. */
 	}
     }
@@ -518,7 +603,8 @@
     insert_me.last = last;
     insert_me.val = val;
 
-    Dynarr_insert_many (rt->entries, &insert_me, 1, insert_me_here);
+    rt->entries =
+      gap_array_insert_els (rt->entries, insert_me_here, &insert_me, 1);
   }
 
   /* Now see if we can combine this entry with adjacent ones just
@@ -526,12 +612,12 @@
 
   if (insert_me_here > 0)
     {
-      struct range_table_entry *entry = Dynarr_atp (rt->entries,
-						    insert_me_here - 1);
+      struct range_table_entry *entry =
+	rangetab_gap_array_atp (rt->entries, insert_me_here - 1);
       if (EQ (val, entry->val) && entry->last == first)
 	{
 	  entry->last = last;
-	  Dynarr_delete_many (rt->entries, insert_me_here, 1);
+	  gap_array_delete_els (rt->entries, insert_me_here, 1);
 	  insert_me_here--;
 	  /* We have morphed into a larger range.  Update our records
 	     in case we also combine with the one after. */
@@ -539,14 +625,14 @@
 	}
     }
 
-  if (insert_me_here < Dynarr_length (rt->entries) - 1)
+  if (insert_me_here < gap_array_length (rt->entries) - 1)
     {
-      struct range_table_entry *entry = Dynarr_atp (rt->entries,
-						    insert_me_here + 1);
+      struct range_table_entry *entry =
+	rangetab_gap_array_atp (rt->entries, insert_me_here + 1);
       if (EQ (val, entry->val) && entry->first == last)
 	{
 	  entry->first = first;
-	  Dynarr_delete_many (rt->entries, insert_me_here, 1);
+	  gap_array_delete_els (rt->entries, insert_me_here, 1);
 	}
     }
 }
@@ -585,7 +671,7 @@
        (range_table))
 {
   CHECK_RANGE_TABLE (range_table);
-  Dynarr_reset (XRANGE_TABLE (range_table)->entries);
+  gap_array_delete_all_els (XRANGE_TABLE (range_table)->entries);
   return Qnil;
 }
 
@@ -611,17 +697,18 @@
 
   /* Do not "optimize" by pulling out the length computation below!
      FUNCTION may have changed the table. */
-  for (i = 0; i < Dynarr_length (rt->entries); i++)
+  for (i = 0; i < gap_array_length (rt->entries); i++)
     {
-      struct range_table_entry *entry = Dynarr_atp (rt->entries, i);
+      struct range_table_entry entry =
+	rangetab_gap_array_at (rt->entries, i);
       EMACS_INT first, last;
       Lisp_Object args[4];
       int oldlen;
 
     again:
-      first = entry->first;
-      last = entry->last;
-      oldlen = Dynarr_length (rt->entries);
+      first = entry.first;
+      last = entry.last;
+      oldlen = gap_array_length (rt->entries);
       args[0] = function;
       /* Fix up the numbers in accordance with the open/closedness of the
 	 table. */
@@ -631,12 +718,12 @@
 	args[1] = make_int (premier);
 	args[2] = make_int (dernier);
       }
-      args[3] = entry->val;
+      args[3] = entry.val;
       Ffuncall (countof (args), args);
       /* Has FUNCTION removed the entry? */
-      if (oldlen > Dynarr_length (rt->entries)
-	  && i < Dynarr_length (rt->entries)
-	  && (first != entry->first || last != entry->last))
+      if (oldlen > gap_array_length (rt->entries)
+	  && i < gap_array_length (rt->entries)
+	  && (first != entry.first || last != entry.last))
 	goto again;
       }
 
@@ -778,7 +865,7 @@
 unified_range_table_bytes_needed (Lisp_Object rangetab)
 {
   return (sizeof (struct range_table_entry) *
-	  (Dynarr_length (XRANGE_TABLE (rangetab)->entries) - 1) +
+	  (gap_array_length (XRANGE_TABLE (rangetab)->entries) - 1) +
 	  sizeof (struct unified_range_table) +
 	  /* ALIGNOF a struct may be too big. */
 	  /* We have four bytes for the size numbers, and an extra
@@ -798,9 +885,10 @@
      char * and adding sizeof(int), because that will lead to
      mis-aligned data on the Alpha machines. */
   struct unified_range_table *un;
-  range_table_entry_dynarr *rted = XRANGE_TABLE (rangetab)->entries;
+  Gap_Array *rtega = XRANGE_TABLE (rangetab)->entries;
   int total_needed = unified_range_table_bytes_needed (rangetab);
   void *new_dest = ALIGN_PTR ((char *) dest + 4, EMACS_INT);
+  Elemcount i;
 
   * (char *) dest = (char) ((char *) new_dest - (char *) dest);
   * ((unsigned char *) dest + 1) = total_needed & 0xFF;
@@ -809,10 +897,10 @@
   total_needed >>= 8;
   * ((unsigned char *) dest + 3) = total_needed & 0xFF;
   un = (struct unified_range_table *) new_dest;
-  un->nentries = Dynarr_length (rted);
+  un->nentries = gap_array_length (rtega);
   un->type = XRANGE_TABLE (rangetab)->type;
-  memcpy (&un->first, Dynarr_begin (rted),
-	  sizeof (struct range_table_entry) * Dynarr_length (rted));
+  for (i = 0; i < gap_array_length (rtega); i++)
+    (&un->first)[i] = rangetab_gap_array_at (rtega, i);
 }
 
 /* Return number of bytes actually used by a unified range table. */
@@ -855,7 +943,7 @@
   new_dest = (char *) unrangetab + * (char *) unrangetab;
   un = (struct unified_range_table *) new_dest;
 
-  return get_range_table (pos, un->nentries, &un->first, default_);
+  return get_range_table (pos, un->nentries, &un->first, 0, 0, default_);
 }
 
 /* Return number of entries in a unified range table. */