Upgrade lib/vector.c & .h

This upgrade maintains the existing vector operations, but changes the
underlying mechanisms.  It then adds a number of new functions,
extending the operations on vectors.

The "struct vector" is redefined, which affects only some code in
lib/command.c -- which pokes around inside what should be treated as a
private data structure.  Pro tem this is supported by a macro.

The constant VECTOR_MIN_SIZE has been removed -- if there is a minimum
size that should be enforced by the vector code.

New functions include:

  vector_insert_item    -- insert item, moving existing items

  vector_move_item      -- move item from place to place in vector

  vector_delete_item    -- delete item and close up gap

  vector_reverse        -- reverse order of vector

  vector_push_item      -- simple push
  vector_pop_item       -- simple pop

  vector_insert         -- insert 1 or more NULL items, moving
                           existing items
  vector_delete         -- delete 1 or more items and close up gap

  vector_bsearch        -- perform binary search on vector
  vector_sort           -- qsort vector

  vector_copy_here      -- make copy of body of vector
  vector_move_here      -- move body of vector
  vector_copy_append    -- append copy of vector to end of another
  vector_move_append    -- move body of vector to the end of another

  vector_copy_extract   -- copy part of one vector to another
  vector_move_extract   -- move part of one vector to another
  vector_copy_splice    -- copy part of one vector to replace part of
                           another, taking a copy of the replaced part
  vector_move_splice    -- move part of one vector to replace part of
                           another, taking a copy of the replaced part
  vector_copy_replace   -- copy part of one vector to replace part of
                           another
  vector_move_replace   -- move part of one vector to replace part of
                           another

  vector_discard        -- discard body of vector
  vector_chop           -- discard any unused memory in body of vector
  vector_decant         -- decant vector to new body

Other files affected:

  command.c:

    -- removal of VECTOR_MIN_SIZE
    -- use of vector_sort()
    -- use of VECTOR_INDEX to poke around inside vector
       (removing this is TODO)

  memtypes.c & memory.c

    -- updating names and comments for vectors

  vty.c

    -- removal of VECTOR_MIN_SIZE

  memory.h

    -- added SIZE(t,n) macro -- (sizeof(t) * (n))

1 files changed, 1112 insertions, 80 deletions

diff --git a/lib/vector.c b/lib/vector.c
index 7c148628..8268c830 100644
--- a/lib/vector.c
+++ b/lib/vector.c
@@ -1,6 +1,9 @@
-/* Generic vector interface routine
+/* Generic vector interface routine -- functions
  * Copyright (C) 1997 Kunihiro Ishiguro
  *
+ * 24-Nov-2009  -- extended to add a number of new operations on vectors.
+ *                 Copyright (C) 2009 Chris Hall (GMCH), Highwayman
+ *
  * This file is part of GNU Zebra.
  *
  * GNU Zebra is free software; you can redistribute it and/or modify it
@@ -16,7 +19,7 @@
  * You should have received a copy of the GNU General Public License
  * along with GNU Zebra; see the file COPYING.  If not, write to the Free
  * Software Foundation, Inc., 59 Temple Place - Suite 330, Boston, MA
- * 02111-1307, USA.  
+ * 02111-1307, USA.
  */
 
 #include <zebra.h>
@@ -24,87 +27,757 @@
 #include "vector.h"
 #include "memory.h"
 
-/* Initialize vector : allocate memory and return vector. */
+/* Vectors are implemented as a structure which points to an array of pointers
+ * to vector items.  That array -- the body of the vector -- can change size,
+ * and therefore may move around in memory.
+ *
+ * The vector structure may be statically allocated, embedded in another
+ * structure, or allocated dynamically.  In any case the vector operations
+ * require the address of the vector structure -- see typedef for vector.
+ *
+ * Vector items are accessed by index, fetching and storing pointers to
+ * those items.  Can also push and pop items.
+ *
+ * A vector has a known (logical) end position.  Everything beyond the end is
+ * defined to be NULL.  When a vector is initialised it is set empty.
+ *
+ * At any given moment the vector body has a limit on the number of items it
+ * can accommodate (the physical end).
+ *
+ * A vector will grow to accommodate what is put into it.  Adding items beyond
+ * the (logical) end moves it.  Adding items beyond the (physical) limit causes
+ * the body to be extended to suit, and to leave some spare space for future
+ * expansion.
+ *
+ * While the vector is small (see VECTOR_LIMIT_DOUBLE_MAX) the body will grow by
+ * doubling in size.  When it is larger, it grows to be multiples of
+ * VECTOR_LIMIT_DOUBLE_MAX.
+ *
+ * Deleting items reduces the (logical) end position, but does NOT release
+ * memory -- the (physical) limit is not changed.
+ *
+ * To release memory: vector_chop will release everything beyond the current
+ * end; vector_decant will create a new body of exactly the current size,
+ * releasing the old body; vector_discard will release everything beyond a
+ * given position.
+ *
+ * NB: you can set a vector item to be NULL.  If you set a vector item beyond
+ *     the current end, NULL items are inserted in the vector.
+ *
+ * NB: when setting a vector item it is the caller's responsibility to
+ *     deallocate any pre-existing value of the item.
+ *
+ * NB: when deleting items it is also the caller's responsibility to deallocate
+ *     any values that require it.
+ *
+ * Implementation Notes
+ *
+ * Everything beyond the (logical) end is implicitly NULL.
+ *
+ * Actual memory between (logical) end and (physical) limit is UNDEFINED.  So
+ * when advancing the end some care has to be taken to ensure that any new
+ * items in the vector are either set to something or cleared to NULL.
+ *
+ * It would have been possible to ensure that everything between end and limit
+ * is cleared to NULL, but that is more work -- in particular it creates work
+ * when it is not always required.
+ */
+
+#define P_ITEMS_SIZE(n) SIZE(p_vector_item, n)
+/*==============================================================================
+ * Initialisation, allocation, reset etc.
+ */
+
+/* Initialise a brand new vector, setting it empty.
+ *
+ * Allocates vector structure if none given -- that is, if v == NULL.
+ *
+ * If size is given as zero, no body is allocated, otherwise body of exactly
+ * the required size is allocated.
+ *
+ * NB: discards any existing vector body -- so it is the caller's responsibility
+ *     to release any existing body, and any items in that body.
+ */
 vector
-vector_init (unsigned int size)
+vector_init_new(vector v, unsigned int size)
 {
-  vector v = XCALLOC (MTYPE_VECTOR, sizeof (struct _vector));
+  if (v == NULL)
+    v = XCALLOC(MTYPE_VECTOR, sizeof(struct vector)) ;
+  else
+    memset(v, 0, sizeof(struct vector)) ;
 
-  /* allocate at least one slot */
-  if (size == 0)
-    size = 1;
+  if (size != 0)
+    {
+      v->p_items = XMALLOC(MTYPE_VECTOR_BODY, P_ITEMS_SIZE(size)) ;
+      v->limit   = size ;
+    } ;
 
-  v->alloced = size;
-  v->active = 0;
-  v->index = XCALLOC (MTYPE_VECTOR_INDEX, sizeof (void *) * size);
-  return v;
-}
+  return v ;
+} ;
 
+/* Initialize vector : allocate memory and return vector.
+ *                     allocates body with at least 1 entry.
+ */
+vector
+vector_init (unsigned int size)
+{
+  return vector_init_new(NULL, size ? size : 1) ;	/* at least 1 entry */
+} ;
+
+/* Basic: free the given vector structure.  NB: Orphans any existing body !! */
 void
 vector_only_wrapper_free (vector v)
 {
   XFREE (MTYPE_VECTOR, v);
 }
 
+/* Basic: free the vector body.	*/
 void
-vector_only_index_free (void *index)
+vector_only_index_free (void *body)
 {
-  XFREE (MTYPE_VECTOR_INDEX, index);
+  XFREE (MTYPE_VECTOR_BODY, body);
 }
 
+/* Basic: free the vector body and the vector structure.	*/
 void
 vector_free (vector v)
 {
-  XFREE (MTYPE_VECTOR_INDEX, v->index);
+  XFREE (MTYPE_VECTOR_BODY, v->p_items);
   XFREE (MTYPE_VECTOR, v);
 }
 
+/* Re-Initialize vector (or create new one), setting it empty.
+ *
+ * Allocates vector structure if none given -- that is, if v == NULL.
+ *
+ * If size is given as zero, no body is allocated, but any existing body is
+ * retained.  (vector_reset() will discard body.)
+ *
+ * Otherwise ensures existing body is at least the required size, or a body
+ * of exactly the required size is allocated.
+ *
+ * NB: when re-initialising an existing vector it is the caller's
+ *     responsibility to release any vector item values *before* doing this.
+ * */
+vector
+vector_re_init(vector v, unsigned int size)
+{
+  if ((v == NULL) || (v->p_items == NULL))
+    return vector_init_new(v, size) ;
+
+  v->end = 0 ;
+
+  if (v->limit < size)
+    {
+      v->p_items = XREALLOC(MTYPE_VECTOR_BODY, v->p_items, P_ITEMS_SIZE(size)) ;
+      v->limit = size ;
+    } ;
+
+  return v ;
+} ;
+
+/* Free the vector body, and free the vector structure or reset it.
+ *
+ * Return NULL if releases vector, otherwise the address of the vector.
+ *
+ * NB: it is the caller's responsibility to release any vector item values
+ *     *before* doing this.
+ */
+vector
+vector_reset(vector v, int free_structure)
+{
+  if (v == NULL)
+    return NULL ;	/* allow for already freed vector	*/
+
+  if (v->p_items != NULL)
+    XFREE(MTYPE_VECTOR_BODY, v->p_items) ;
+
+  if (free_structure)
+    {
+      XFREE(MTYPE_VECTOR, v) ;
+      return NULL ;
+    }
+  else
+    return vector_init_new(v, 0) ;
+} ;
+
+/* Pop item from vector, stepping past any NULLs.
+ *
+ * If vector is empty, free the body and, if required, the vector structure.
+ *
+ * Useful for emptying out and discarding a vector:
+ *
+ *     while ((p_v = vector_ream_out(v, 1)))
+ *       ... do what's required to release the item p_v
+ *
+ * Returns NULL if vector was empty and has now been freed as required.
+ */
+p_vector_item
+vector_ream(vector v, int free_structure)
+{
+  p_vector_item p_v ;
+
+  if (v == NULL)
+    return NULL ;
+
+  while (v->end != 0)
+    {
+      p_v = v->p_items[--v->end] ;
+      if (p_v != NULL)
+        return p_v ;  /* return non-NULL item */
+    } ;
+
+  /* vector is empty: free the body, and (if required) the vector structure.  */
+  vector_reset(v, free_structure) ;
+
+  return NULL ;         /* signals end */
+} ;
+
+/*==============================================================================
+ * Inserting and deleting items.
+ */
+
+/* Insert item in vector, before item at given position
+ * Move items and extend vector as required.
+ */
+void
+vector_insert_item(vector v, vector_index i, void* p_v)
+{
+  if ((i == v->end) && (i < v->limit))
+    ++v->end ;
+  else
+    vector_insert(v, i, 1) ;
+
+  v->p_items[i] = (p_vector_item)p_v ;
+} ;
+
+/* Insert item in vector at given position with rider:
+ *
+ *   rider <  0 -- insert before the item at the given position
+ *   rider == 0 -- insert at the given position -- REPLACING any existing value
+ *   rider >  0 -- insert after the item at the given position
+ *
+ * NB: when an item is replaced, it is the caller's responsibility to release
+ *     any memory used by the item, if required.
+ *
+ * Move items and extend vector as required.
+ */
+void
+vector_insert_item_here(vector v, vector_index i, int rider,
+                                                          p_vector_item p_v)
+{
+  if (rider == 0)
+    return vector_set_item(v, i, p_v) ;
+
+  if (rider > 0)
+    ++i ;       /* insert before next item */
+  vector_insert_item(v, i, p_v) ;
+} ;
+
+/* Delete item from vector.
+ *
+ * Move items as required.  Reduces number of items in the vector (unless
+ * the item in question is beyond the end of the vector !)
+ *
+ * NB: it is the caller's responsibility to release memory used by any
+ *     current value of the item, if required.
+ *
+ * NB: does NOT change the size of the vector body.
+ */
+p_vector_item
+vector_delete_item(vector v, vector_index i)
+{
+  p_vector_item p_e ;
+  if (i < v->end)
+    {
+      p_e = v->p_items[i] ;     /* pick up the current value */
+      if (i != (v->end - 1))
+        vector_delete(v, i, 1) ;
+      else
+        v->end = i ;
+      return p_e ;
+    }
+  else
+    return NULL ;
+} ;
+
+/*==============================================================================
+ * Moving items within vector.
+ */
+
+/* Move item in vector from source position to destination position.
+ * Moves intervening items up or down as required.
+ * Extends vector to include the destination, if required.
+ * A source item beyond the end of the vector is implicitly NULL.
+ */
+void
+vector_move_item(vector v, vector_index i_dst, vector_index i_src)
+{
+  p_vector_item* pp_s ;
+  p_vector_item* pp_d ;
+  p_vector_item p_e ;
+
+  vector_index old_end = v->end ;
+
+  /* Worry about whether both source and destination exist.        */
+  if (i_dst >= old_end)
+    {
+      vector_insert(v, i_dst, 1) ; /* ensure destination exists    */
+      if (i_src >= old_end)
+        return ;                   /* both were beyond the end     */
+    }
+  else if (i_src >= old_end)
+    {
+      i_src = old_end ;            /* clamp to just beyond last    */
+      vector_insert(v, i_src, 1) ; /* create empty entry           */
+    } ;
+
+  if (i_dst == i_src)              /* avoid work and edge case     */
+    return ;
+
+  /* Both src and dst are within the vector and src != dst         */
+  pp_s = &v->p_items[i_src] ;     /* address of src entry          */
+  pp_d = &v->p_items[i_dst] ;     /* address of dst entry          */
+  p_e = *pp_s ;                   /* pick up item to move          */
+  if (i_src < i_dst)
+    memmove(pp_s, pp_s+1, P_ITEMS_SIZE(i_dst - i_src)) ;
+  else
+    memmove(pp_d+1, pp_d, P_ITEMS_SIZE(i_src - i_dst)) ;
+  *pp_d = p_e ;                   /* put down the item to move     */
+} ;
+
+/* Move item in vector to given position with rider:
+ *
+ *   rider <  0 -- move to before the item at the given position
+ *   rider == 0 -- move to replace item at the given position
+ *   rider >  0 -- insert after the item at the given position
+ *
+ * NB: it is the caller's responsibility to release the any existing value
+ *     that will be replaced.
+ *
+ * Move items and extend vector as required.
+ */
+void
+vector_move_item_here(vector v, vector_index i_dst, int rider,
+                                                             vector_index i_src)
+{
+  if (rider != 0)
+    {
+      if (rider > 0)
+	++i_dst ;
+      vector_move_item(v, i_dst, i_src) ;
+    }
+  else
+    {
+      /* to replace: copy and then delete.  */
+      vector_set_item(v, i_dst, vector_get_item(v, i_src)) ;
+      vector_delete_item(v, i_src) ;
+    } ;
+} ;
+
+/* Reverse vector: reverse the order of items in the vector.
+ */
+void
+vector_reverse(vector v)
+{
+  if (v != NULL)
+    vector_part_reverse(v, 0, v->end) ;
+} ;
+
+/* Reverse portion of vector.
+ */
+void
+vector_part_reverse(vector v, vector_index i, unsigned int n)
+{
+  vector_index j ;
+
+  if (v == NULL)
+    return ;
+
+  if ((i + n) > v->limit)
+    vector_extend(v, i + n) ;   /* ensure portion exists        */
+
+  if (n <= 1)
+    return ;
+
+  j = i + n - 1 ;               /* j > i, because n > 1         */
+  do
+    {
+      p_vector_item p_i = v->p_items[i] ;
+      v->p_items[i++]   = v->p_items[j] ;
+      v->p_items[j--]   = p_i ;
+    } while (j > i) ;
+} ;
+
+/*==============================================================================
+ * Copying, moving and appending entire vectors.
+ */
+
+static void vector_new_limit(vector v, vector_index new_end) ;
+
+/* Shallow vector copy -- copies pointers to item values, not the values.  */
+/* Creates a new vector.						   */
+/* NB: copies whole body, including stuff beyond (logical) end !           */
+/*     TODO: is this behaviour required ?                                  */
 vector
 vector_copy (vector v)
 {
-  unsigned int size;
-  vector new = XCALLOC (MTYPE_VECTOR, sizeof (struct _vector));
+  vector new = vector_init_new(NULL, v->limit) ;
 
-  new->active = v->active;
-  new->alloced = v->alloced;
+  new->end = v->end;
 
-  size = sizeof (void *) * (v->alloced);
-  new->index = XCALLOC (MTYPE_VECTOR_INDEX, size);
-  memcpy (new->index, v->index, size);
+  if (v->limit > 0)
+    memcpy(new->p_items, v->p_items, P_ITEMS_SIZE(v->limit)) ;
 
   return new;
 }
 
-/* Check assigned index, and if it runs short double index pointer */
-void
-vector_ensure (vector v, unsigned int num)
+/* Shallow vector copy -- copies pointers to item values, not the values.
+ * Creates a new vector or re-initialises an existing one.
+ *
+ * NB: creates new vector with same limit as existing one, but copies only
+ *     the known items (ie up to end, not up to limit).
+ *
+ * NB: if re-initialising existing vector, it is the caller's responsibility
+ *     to release any existing items if that is required.
+ *
+ * NB: if re-initialising existing vector, it is the caller's responsibility
+ *     to ensure the vector structure is currently valid.
+ *
+ * NB: do NOT try copying a vector to itself !!
+ */
+vector
+vector_copy_here(vector dst, vector src)
 {
-  if (v->alloced > num)
-    return;
+  assert((src != NULL) && (src != dst)) ;
+
+  dst = vector_re_init(dst, src->limit) ;
 
-  v->index = XREALLOC (MTYPE_VECTOR_INDEX, 
-		       v->index, sizeof (void *) * (v->alloced * 2));
-  memset (&v->index[v->alloced], 0, sizeof (void *) * v->alloced);
-  v->alloced *= 2;
-  
-  if (v->alloced <= num)
-    vector_ensure (v, num);
+  dst->end = src->end;
+
+  if (src->end > 0)
+    memcpy(dst->p_items, src->p_items, P_ITEMS_SIZE(src->end)) ;
+
+  return dst ;
+} ;
+
+/* Vector move -- moves body of vector.
+ * Creates a new vector or re-initialises an existing one.
+ * Leaves the source vector empty -- does not release the structure.
+ *
+ * NB: if re-initialising existing vector, it is the caller's responsibility
+ *     to release any existing items if that is required.
+ *
+ * NB: if re-initialising existing vector, it is the caller's responsibility
+ *     to ensure the vector structure is currently valid.
+ *
+ * NB: do NOT try moving a vector to itself !!
+ */
+vector
+vector_move_here(vector dst, vector src)
+{
+  assert((src != NULL) && (src != dst)) ;
+
+  if (dst != NULL)
+    dst = vector_reset(dst, 0) ;     /* Reset to deallocate any existing body */
+  else
+    dst = vector_init_new(dst, 0) ;  /* Create new structure sans body.       */
+
+  *dst = *src ;		             /* Copy the vector structure             */
+
+  vector_init_new(src, 0) ;	     /* Set empty, forgetting body            */
+
+  return dst ;
 }
 
-/* This function only returns next empty slot index.  It dose not mean
+/* Shallow vector copy append -- copies pointers to item values, not the values.
+ * Appends copied pointers to the destination vector.
+ * Creates a new destination vector if required.
+ *
+ * NB: Can append to self.
+ */
+vector
+vector_copy_append(vector dst, vector src)
+{
+  vector_index new_end ;
+
+  assert(src != NULL) ;
+
+  if (dst != NULL)
+    {
+      new_end = dst->end + src->end ;
+      if (new_end > dst->limit)
+        vector_new_limit(dst, new_end) ;
+    }
+  else
+    {
+      new_end = src->end ;
+      vector_init_new(dst, new_end) ;
+    } ;
+
+  if (src->end)
+    memcpy(&dst->p_items[dst->end], src->p_items, P_ITEMS_SIZE(src->end)) ;
+
+  dst->end = new_end ;          /* Done last, allows for append to self ! */
+  return dst ;
+} ;
+
+/* Vector move append -- moves pointers to item values.
+ * Appends moved pointers to the destination vector.
+ * Creates a new destination vector if required (dst == NULL).
+ * Leaves the source vector empty -- does not release the structure.
+ *
+ * NB: do NOT try moving a vector to itself !!
+ */
+vector
+vector_move_append(vector dst, vector src)
+{
+  assert((src != NULL) && (src != dst)) ;
+
+  if ((dst == NULL) || (dst->end == 0))
+    return vector_move_here(dst, src) ;  /* Easy way to do it if dst empty  */
+
+  vector_copy_append(dst, src) ;  /* Extend dst and copy src      */
+  vector_init_new(src, 0) ;	  /* Set empty, forgetting body   */
+
+  return dst ;
+} ;
+
+/*==============================================================================
+ * Portmanteau splice/extract/replace function.
+ *
+ * All take a portion of 'src' vector and:
+ *
+ * splice:
+ *
+ *   a) replace a portion of the 'dst' vector by a portion of the 'src' vector
+ *      copying the replaced portion of the 'dst' vector to the 'to' vector
+ *   b) either: leave 'src' unchanged               -- copy
+ *          or: remove the stuff copied from 'src'  -- move
+ *
+ *   Arguments:  to_copy  -- true
+ *               to       -- vector, or NULL => allocate new vector
+ *               dst      -- vector
+ *               i_dst    -- start of portion to replace
+ *               n_dst    -- length of portion to replace.  0 => insertion.
+ *               src      -- vector, or NULL => nothing to copy/move
+ *               i_src    -- start of portion to copy/move
+ *               n_src    -- length of portion to copy/move.  0 => nothing.
+ *               src_move -- true => move, otherwise copy.
+ *
+ *   Returns:    the (possibly new) 'to' vector
+ *
+ *   NB: 'to', 'dst' and 'src' must be distinct vectors.
+ *
+ * extract:
+ *
+ *   a) copy a portion of the 'src' vector to the 'to' vector
+ *   c) either: leave 'src' unchanged               -- copy
+ *          or: remove the stuff copied from 'src'  -- move
+ *
+ *   Arguments:  to_copy  -- true
+ *               to       -- vector, or NULL => allocate new vector
+ *               dst      -- NULL
+ *               i_dst    -- ignored
+ *               n_dst    -- ignored
+ *               src      -- vector, or NULL => nothing to copy/move
+ *               i_src    -- start of portion to copy/move
+ *               n_src    -- length of portion to copy/move.  0 => nothing.
+ *               src_move -- true => move, otherwise copy.
+ *
+ *   Returns:    the (possibly new) 'to' vector
+ *
+ *   NB: 'to' and 'src' must be distinct vectors.
+ *
+ * replace:
+ *
+ *   a) replace a portion of the 'dst' vector by a portion of the 'src' vector
+ *   b) either: leave 'src' unchanged               -- copy
+ *          or: remove the stuff copied from 'src'  -- move
+ *
+ *   Arguments:  to_copy  -- false
+ *               to       -- ignored
+ *               dst      -- vector
+ *               i_dst    -- start of portion to replace
+ *               n_dst    -- length of portion to replace.  0 => insertion.
+ *               src      -- vector, or NULL => nothing to copy/move
+ *               i_src    -- start of portion to copy/move
+ *               n_src    -- length of portion to copy/move.  0 => nothing.
+ *               src_move -- true => move, otherwise copy.
+ *
+ *   Returns:    original 'to' argument
+ *
+ *   NB: 'dst' and 'src' must be distinct vectors.
+ *
+ * All copies are shallow -- pointers to item values are copied, not the values.
+ *
+ * NB: any existing contents of the 'to' vector are discarded.
+ *
+ * NB: it is the caller's responsibility to release memory allocated to any
+ *     items which are discarded in these operations.
+ *
+ * NB: for splice and replace, the resulting destination vector will be at
+ *     least i_dst + n_src long.  (Even if is copying actual or implied NULLs
+ *     from the source.)
+ *
+ * NB: where new vectors are created, they will be of exactly the required size.
+ *
+ * NB: where an existing vector is reused, it is the caller's responsibility
+ *     to ensure the vector structure is currently valid (by vector_init_new()
+ *     or by ensuring it is zeroized).
+ */
+vector
+vector_sak(int to_copy, vector to,
+           vector dst, vector_index i_dst, unsigned int n_dst,
+           vector src, vector_index i_src, unsigned int n_src, int src_move)
+{
+  int dst_replace ;               /* true => replace portion of 'dst'   */
+
+  vector_index new_dst_end = 0 ;  /* new end of dst                     */
+
+  unsigned int n_dst_nulls ;      /* number of implicit NULLs to add    */
+  unsigned int n_dst_move ;       /* number of items to move up or down */
+  unsigned int n_src_real ;       /* number of items to really copy     */
+  unsigned int n_src_nulls ;      /* number of implicit NULLs to "copy" */
+
+  assert((to  == NULL) || (dst == NULL) || (to  != dst)) ;
+  assert((src == NULL) || (dst == NULL) || (src != dst)) ;
+
+  /* Worry about how much we really have in the source vector.          */
+
+  n_src_real  = n_src ;         /* assume all real              */
+  n_src_nulls = 0 ;             /* so no NULLs to "copy"        */
+
+  if (n_src != 0)
+    {
+      if ((src == NULL) || (i_src >= src->end))
+        n_src_real = 0 ;
+      else if ((i_src + n_src) > src->end)
+        n_src_real = src->end - i_src ;
+      n_src_nulls = n_src - n_src_real ;
+    } ;
+
+  /* If no 'dst' vector, then this is an extract.                       */
+
+  n_dst_move  = 0 ;             /* assume nothing to move       */
+  n_dst_nulls = 0 ;             /* assume no NULLs to add       */
+
+  if (dst == NULL)
+    /* For extract: set up dst, i_dst and n_dst so that can copy to the */
+    /*              'to' vector as if from 'dst'.                       */
+    {
+      dst_replace = 0 ;                 /* no replacement operation     */
+      dst   = src ;                     /* copy from here               */
+      i_dst = i_src ;
+      n_dst = n_src_real ;
+    }
+  else
+    /* Reduce n_dst to the number of actual items to be replaced.       */
+    /*                                                                  */
+    /* Calculate the new end of 'dst'.                                  */
+    {
+      dst_replace = 1 ;                 /* have replacement to do       */
+      if (i_dst >= dst->end)
+        /* If i_dst is beyond the end of 'dst', then there is nothing   */
+        /* to replace (so set n_dst == 0).  Will be adding n_src items  */
+        /* at i_dst -- so new end must be i_dst + n_src.                */
+        {
+          n_dst_nulls = i_dst - dst->end ;  /* fill from end to i_dst   */
+          n_dst       = 0 ;                 /* nothing to replace       */
+          new_dst_end = i_dst + n_src ;     /* all beyond current end   */
+        }
+      else
+        /* If i_dst + n_dst is beyond the end of 'dst', reduce n_dst to */
+        /* number of items up to the end.                               */
+        /* Will remove n_dst items and insert n_src, so end will move   */
+        /* by n_src - n_dst.                                            */
+        {
+          if ((i_dst + n_dst) > dst->end)
+            n_dst = dst->end - i_dst ;  /* what we actually replace     */
+          else if (n_dst != n_src)
+            n_dst_move = dst->end - (i_dst + n_dst) ;
+                                        /* what we move up or down      */
+
+          new_dst_end = dst->end + n_src - n_dst ;
+                                        /* end depends on amount added  */
+                                        /* & amount actually replaced   */
+        } ;
+    } ;
+
+  /* Copy portion of 'dst' (or of 'src') to 'to', if required.          */
+  /*                                                                    */
+  /* Have arranged: n_dst -- number of items to copy, all existent      */
+  /*                dst   -- vector to copy from -- if n_dst > 0        */
+  /*                i_dst -- first item to copy  -- if n_dst > 0        */
+
+  if (to_copy)
+    {
+      to = vector_re_init(to, n_dst) ;  /* reinitialise or create       */
+      to->end = n_dst ;
+      if (n_dst > 0)
+        memcpy(to->p_items, &dst->p_items[i_dst], P_ITEMS_SIZE(n_dst)) ;
+    } ;
+
+  /* Replace portion of 'dst' by portion of 'src', if required.         */
+  /*                                                                    */
+  /* Have arranged:                                                     */
+  /*                                                                    */
+  /*  new_dst_end  -- end of dst once dust settles                      */
+  /*  n_dst_nulls  -- number of NULLs to insert at dst->end to fill up  */
+  /*                  to i_dst (when i_dst is beyond old end.)          */
+  /*  n_dst_move   -- number of items in dst to move up or down to      */
+  /*                  leave n_src item hole at i_dst to fill in.        */
+  /*  n_src_real   -- number of real src items at i_src to copy to dst  */
+  /*                  at i_dst.                                         */
+  /*  n_src_nulls  -- number of nulls to add to fill to i_dst + n_src.  */
+
+  if (dst_replace)
+    {
+      if (new_dst_end > dst->limit)   /* extend body if required */
+        vector_new_limit(dst, new_dst_end) ;
+
+      if (n_dst_nulls > 0)
+        memset(&dst->p_items[dst->end], 0, P_ITEMS_SIZE(n_dst_nulls)) ;
+      if (n_dst_move > 0)
+        memmove(&dst->p_items[i_dst + n_dst], &dst->p_items[i_dst + n_src],
+                                                     P_ITEMS_SIZE(n_dst_move)) ;
+      if (n_src_real > 0)
+        memcpy(&dst->p_items[i_dst], &src->p_items[i_src],
+                                                     P_ITEMS_SIZE(n_src_real)) ;
+      if (n_src_nulls > 0)
+        memset(&dst->p_items[i_dst + n_src_real], 0,
+                                                    P_ITEMS_SIZE(n_src_nulls)) ;
+      dst->end = new_dst_end ;
+    } ;
+
+  /* Delete portion of 'src', if required (and have 'src' !)            */
+
+  if (src_move && (n_src_real != 0))
+    vector_delete(src, i_src, n_src_real) ;
+
+  /* Done -- return 'to' vector as promised.                            */
+
+  return to ;
+} ;
+
+/*==============================================================================
+ * Legacy Vector Operations
+ */
+
+/* This function only returns next empty slot index.  It does not mean
    the slot's index memory is assigned, please call vector_ensure()
-   after calling this function. */
+   after calling this function.
+
+   Index returned is <= current (logical) end.
+*/
 int
 vector_empty_slot (vector v)
 {
-  unsigned int i;
-
-  if (v->active == 0)
-    return 0;
+  vector_index i;
 
-  for (i = 0; i < v->active; i++)
-    if (v->index[i] == 0)
-      return i;
+  for (i = 0; i < v->end; i++)
+    if (v->p_items[i] == NULL)
+      break ;
 
   return i;
 }
@@ -113,77 +786,436 @@ vector_empty_slot (vector v)
 int
 vector_set (vector v, void *val)
 {
-  unsigned int i;
-
-  i = vector_empty_slot (v);
-  vector_ensure (v, i);
+  vector_index i;
+  i = vector_empty_slot(v) ;    /* NB: i <= v->end                */
+  if (i == v->end)
+    i = vector_extend_by_1(v) ;
 
-  v->index[i] = val;
-
-  if (v->active <= i)
-    v->active = i + 1;
+  v->p_items[i] = val;
 
   return i;
 }
 
 /* Set value to specified index slot. */
 int
-vector_set_index (vector v, unsigned int i, void *val)
+vector_set_index (vector v, vector_index i, void *val)
 {
   vector_ensure (v, i);
-
-  v->index[i] = val;
-
-  if (v->active <= i)
-    v->active = i + 1;
-
+  v->p_items[i] = val;
   return i;
 }
 
 /* Look up vector.  */
-void *
-vector_lookup (vector v, unsigned int i)
+p_vector_item
+vector_lookup (vector v, vector_index i)
 {
-  if (i >= v->active)
+  if (i >= v->end)
     return NULL;
-  return v->index[i];
+  return v->p_items[i];
 }
 
 /* Lookup vector, ensure it. */
-void *
-vector_lookup_ensure (vector v, unsigned int i)
+p_vector_item
+vector_lookup_ensure (vector v, vector_index i)
 {
   vector_ensure (v, i);
-  return v->index[i];
+  return v->p_items[i];
 }
 
 /* Unset value at specified index slot. */
 void
-vector_unset (vector v, unsigned int i)
+vector_unset (vector v, vector_index i)
 {
-  if (i >= v->alloced)
-    return;
+  vector_index j ;
+  if (i >= v->end)
+    return;		/* Everything beyond or at end is implicitly NULL */
 
-  v->index[i] = NULL;
+  v->p_items[i] = NULL;
 
-  if (i + 1 == v->active) 
-    {
-      v->active--;
-      while (i && v->index[--i] == NULL && v->active--) 
+  /* See if everything ahead of 'i' is also NULL.  */
+  j = i ;
+  while (++j < v->end)
+    if (v->p_items[j] != NULL)
+      return ;          /* Finished if anything ahead 'i' is not NULL	  */
+
+  /* Everything from 'i' onwards is NULL.
+   * Step backwards across any NULLs and then set the new end.
+   */
+#if 0
+      v->end--;
+      while (i && v->p_items[--i] == NULL && v->end--)
 	;				/* Is this ugly ? */
-    }
+#endif
+  while ((i != 0) && (v->p_items[i - 1] == NULL))
+    --i ;
+
+  v->end = i ;
 }
 
-/* Count the number of not emplty slot. */
-unsigned int
+/* Count the number of not empty slots. */
+vector_index
 vector_count (vector v)
 {
-  unsigned int i;
+  vector_index i;
   unsigned count = 0;
 
-  for (i = 0; i < v->active; i++) 
-    if (v->index[i] != NULL)
+  for (i = 0; i < v->end; i++)
+    if (v->p_items[i] != NULL)
       count++;
 
   return count;
 }
+
+/*==============================================================================
+ * Sorting and Searching vector.
+ */
+
+/* Sort the given vector.
+ *
+ * NB: the comparison function receives a pointer to the pointer to the
+ *     vector item's value.
+ *
+ * NB: if there are NULL items in the vector, the comparison function MUST
+ *     be ready for them.
+ */
+void
+vector_sort(vector v, vector_sort_cmp* cmp)
+{
+  if (v->end <= 1)
+    return ;		/* Stop dead if 0 or 1 items */
+
+  typedef int qsort_cmp(const void*, const void*) ;
+
+  qsort(v->p_items, v->end, sizeof(p_vector_item), (qsort_cmp*)cmp) ;
+} ;
+
+/* Perform binary search on the given vector.
+ *
+ * The vector MUST be sorted in the order implied by the comparison function
+ * given.  The vector need not contain unique values, but this search makes
+ * no effort to select any particular instance of a sequence of equals.
+ *
+ * Returns:
+ *
+ *   result ==  0: found an equal value.
+ *                 index returned is of first entry found which is equal to
+ *                 the value sought.  There may be other equal values, before
+ *                 and/or after this one in the vector.
+ *
+ *   result == +1: value not found and vector not empty.
+ *                 index returned is of the largest entry whose value is less
+ *                 than the value sought.
+ *                 (The value sought belongs after this point.)
+ *
+ *   result == -1: value is less than everything in the vector, or the
+ *                 vector is empty.
+ *                 index returned is 0
+ *
+ * NB: The comparison function takes arguments which are:
+ *
+ *       const void**  pointer to pointer to value being searched for.
+ *       const void**  pointer to pointer to vector item to compare with
+ *
+ *     The value being searched for need not be in the same form as a vector
+ *     item.  However, if it is then the same comparison function can be used
+ *     to sort and search.
+ *
+ * NB: if there are NULL items in the vector, the comparison function MUST
+ *     be ready for them.
+ */
+vector_index
+vector_bsearch(vector v, vector_bsearch_cmp* cmp, const void* p_val,
+								    int* result)
+{
+  vector_index il, iv, ih ;
+  int c ;
+
+  if (v->end <= 1)
+    {
+      *result = (v->end == 0) ? -1 : cmp(&p_val, (const void**)&v->p_items[0]) ;
+      return 0 ;		/* Stop dead if 0 or 1 items */
+    } ;
+
+  /* We have at least two items.    */
+  il = 0 ;
+  ih = v->end - 1 ;
+
+  /* Pick off the edge cases: >= last and <= first.  */
+  if ((c = cmp(&p_val, (const void**)&v->p_items[ih])) >= 0)
+    {
+      *result = c ;	/* 0 => found.  +1 => val > last	*/
+      return ih ;	/* return high index.                   */
+    } ;
+  if ((c = cmp(&p_val, (const void**)&v->p_items[il])) <= 0)
+    {
+      *result = c ;	/* 0 => found.  -1 => val < first      */
+      return il ;	/* return low index.                   */
+    }
+
+  /* Now binary chop.  We know that item[il] < val < item[ih]	*/
+  /*                   We also know that il < ih		*/
+  while (1)
+    {
+      iv = (il + ih) / 2 ;
+      if (iv == il)	/* true if (ih == il+1) 			*/
+	{
+	  *result = +1 ;
+	  return il ;	/* return il: item[il] < val < item[il+1]	*/
+	} ;
+      /* We now know that il < iv < ih	*/
+      c = cmp(&p_val, (const void**)&v->p_items[iv]) ;
+      if (c == 0)
+	{
+	  *result = 0 ;
+	  return iv ;	/* found !!				*/
+	}
+      if (c <  0)
+	ih = iv ;	/* step down	iv > il, so new ih > il	*/
+      else
+	il = iv ;	/* step up	iv < ih, so new il < ih	*/
+    } ;
+} ;
+
+/*==============================================================================
+ * Mechanics for adding/deleting items and managing the vector (logical) end
+ * and (physical) limit.
+ */
+
+/* Extract the LS bit of unsigned integer 'x'.  */
+#define lsbit(x) ((x) & ((~(x)) + 1))
+/* Round 'x' up to a multiple of 'm'            */
+#define multiple(x, m) ((((x) + (m) - 1) / (m)) * (m))
+
+/* Set new limit to suit new end for given vector.
+ *
+ * The new limit will be at least: VECTOR_LIMIT_MIN.
+ *
+ * While the vector is relatively small, the limit is doubled until there
+ * is at least 1/8 of the new vector free.
+ *
+ * Beyond VECTOR_LIMIT_DOUBLE_MAX, however, the limit is set to the
+ * smallest multiple of VECTOR_LIMIT_DOUBLE_MAX which gives at least
+ * VECTOR_LIMIT_SLACK_MIN free entries beyond the new end.
+ *
+ * This is an attempt to balance the cost of repeated reallocations of
+ * memory against the cost of possible wasted space at the end of the
+ * vector.
+ *
+ * NB: the new_limit depends entirely on the new end position.  (Current
+ *     end position is ignored.)
+ *
+ * NB: the new limit may be less than the current limit, in which case the
+ *     vector body is reduced in size.
+ *
+ * Except for any size set when the vector is initialised, the vector body
+ * size will be a power of 2 or a multiple of VECTOR_LIMIT_DOUBLE_MAX.
+ * (Vectors are regular in their habits, which may help the memory allocator).
+ *
+ * TODO: what to do if calculation of new_limit overflows, or calculation
+ *       of P_ITEMS_SIZE will ?
+ */
+static void
+vector_new_limit(vector v, vector_index new_end)
+{
+  vector_index old_limit = v->limit ;
+  vector_index new_limit ;
+
+  if (new_end > ((VECTOR_LIMIT_DOUBLE_MAX * 7) / 8))
+    {
+      new_limit = multiple(new_end + VECTOR_LIMIT_SLACK_MIN,
+                                                      VECTOR_LIMIT_DOUBLE_MAX) ;
+    }
+  else
+    {
+      /* Want the new_limit to be a power of 2.                           */
+      /* If the old_limit was a power of 2, start from there.             */
+      /* Otherwise start from a power of 2 less than new_end: either the  */
+      /* minimum value or a value mid way to VECTOR_LIMIT_DOUBLE_MAX.     */
+      if ( (old_limit != 0) && (old_limit == lsbit(old_limit))
+                            && (new_end >= old_limit) )
+        new_limit = old_limit ;
+      else
+        new_limit = (new_end < VECTOR_LIMIT_MID) ? VECTOR_LIMIT_MIN
+                                                 : VECTOR_LIMIT_MID ;
+      while (new_end > ((new_limit * 7) / 8))
+        new_limit *= 2 ;
+    } ;
+
+  v->p_items =
+             XREALLOC(MTYPE_VECTOR_BODY, v->p_items, P_ITEMS_SIZE(new_limit)) ;
+
+  v->limit = new_limit ;
+} ;
+
+/* Extend vector and set new (logical) end.
+ *
+ * Extends body if required.
+ * Ensures everything between old and new end is set NULL.
+ *
+ * NB: expects new end > old end, but copes with new end <= old end.
+ */
+void
+vector_extend(vector v, vector_index new_end)
+{
+  vector_index old_end = v->end ;
+
+  if (new_end > v->limit)
+    vector_new_limit(v, new_end) ;
+  v->end = new_end ;
+
+  if (new_end > old_end)
+    memset(&v->p_items[old_end], 0, P_ITEMS_SIZE(new_end - old_end)) ;
+} ;
+
+/* Insert entries into vector: insert 'n' NULL entries at location 'i'.
+ *
+ * Updates end (and limit) to be at least 'i' + 'n'.
+ * (So if 'i' < end then end becomes end + 'n', else end becomes 'i' + 'n'.)
+ */
+void
+vector_insert(vector v, vector_index i, unsigned int n)
+{
+  vector_index old_end, new_end ;
+  unsigned int n_above ;
+
+  /* If i < old end, then we are inserting n NULLs, and need
+   *                      to shuffle at least one item up.
+   *                 else we are setting new end to i + n and need to NULL
+   *                      fill from old end to the new end.
+   */
+  old_end = v->end ;
+  if (i < old_end)
+    {
+      if (n == 0)
+	return ;		/* give up now if not inserting anything  */
+      n_above = old_end - i ;	/* number of items to shuffle up.. >= 1   */
+      new_end = old_end + n ;
+    }
+  else
+    {
+      n_above = 0 ;		/* nothing to shuffle up.		  */
+      new_end = i + n ;
+      i = old_end ;             /* where to zeroize from                  */
+      n = new_end - old_end ;   /* how much to zeroize                    */
+    } ;
+
+  /* Now we extend the body if we need to.           	    */
+  if (new_end > v->limit)
+    vector_new_limit(v, new_end) ;
+  v->end = new_end ;
+
+  if (n_above > 0)
+    memmove(&v->p_items[i + n], &v->p_items[i], P_ITEMS_SIZE(n_above)) ;
+
+  memset(&v->p_items[i], 0, P_ITEMS_SIZE(n)) ;
+} ;
+
+/* Delete items from vector: delete 'n' items at location 'i'.
+ *
+ * Does nothing if 'i' is beyond current end of vector or if 'n' == 0.
+ *
+ * Deletes from 'i' to end if less than 'n' items to the end.
+ *
+ * NB: does NOT change the size of the body.
+ *
+ * NB: it is the caller's responsibility to have released any memory allocated
+ *     for the items that are being deleted.
+*/
+void
+vector_delete(vector v, vector_index i, unsigned int n)
+{
+  vector_index old_end, new_end ;
+
+  old_end = v->end ;
+
+  if ((i >= old_end) || (n == 0))
+    return ;
+
+  /* If i + n < old_end, we have 1 or more items to keep and move down */
+  if ((i + n) < old_end)
+    {
+      memmove(&v->p_items[i], &v->p_items[i + n],
+					      P_ITEMS_SIZE(old_end - (i + n))) ;
+      new_end = old_end - n ;
+    }
+  else
+    {
+      new_end = i ;             /* We are keeping nothing above 'i' */
+                                /* NB: new_end < old_end            */
+    } ;
+
+  v->end = new_end ;            /* account for stuff dropped        */
+} ;
+
+/* Discard entries from vector: discard entries from location 'i' onwards.
+ *
+ * Releases memory from 'i' onwards.
+ * Releases the body altogether if this sets the vector empty ('i' == 0).
+ * Sets new end of vector iff 'i' < current end.
+ *
+ * Does nothing if 'i' is beyond current limit (physical end) of vector.
+ *
+ * NB: it is the caller's responsibility to have released any memory allocated
+ *     for the items that are being discarded.
+*/
+void
+vector_discard(vector v, vector_index i)
+{
+  if (i >= v->limit)
+    return ;
+
+  if (i == 0)
+    vector_reset(v, 0) ;        /* reset, without releasing the structure */
+  else
+    {
+      v->limit = i ;
+      if (i < v->end)
+        v->end = i ;
+      v->p_items = XREALLOC(MTYPE_VECTOR_BODY, v->p_items, P_ITEMS_SIZE(i)) ;
+    } ;
+} ;
+
+/* Chop vector at the current (logical) end.
+ *
+ * Releases the body altogether if the vector is currently empty.
+*/
+void
+vector_chop(vector v)
+{
+  vector_index new_limit = v->end ;
+
+  if (new_limit == 0)
+    vector_reset(v, 0) ;        /* reset, without releasing the structure */
+  else if (new_limit != v->limit)
+    {
+      v->limit = new_limit ;
+      v->p_items = XREALLOC(MTYPE_VECTOR_BODY, v->p_items, P_ITEMS_SIZE(new_limit)) ;
+    } ;
+} ;
+
+/* Decant vector into a new body allocated to current logical size, and
+ * release the old body.
+ *
+ * Releases the body altogether if the vector is currently empty.
+*/
+void
+vector_decant(vector v)
+{
+  p_vector_item* p_old_body ;
+  vector_index new_limit = v->end ;
+
+  if (new_limit == 0)
+    vector_reset(v, 0) ;          /* reset, without releasing the structure */
+  else
+    {
+      p_old_body = v->p_items ;
+
+      vector_init_new(v, new_limit) ;   /* initialise with new body     */
+
+      memcpy(v->p_items, p_old_body, P_ITEMS_SIZE(new_limit)) ;
+                                        /* copy the old body across     */
+      v->end = new_limit ;
+
+      XFREE(MTYPE_VECTOR_BODY, p_old_body) ;
+    } ;
+} ;