X-Git-Url: https://git.rrq.au/?a=blobdiff_plain;f=vector%2Fvector.h;h=d3f99b699ac584214caf667210c2b780427efe18;hb=c1aae73b1fafd372c4f38a1a205e20a9f22a2fa0;hp=1227860e9978007a87dd4dda0a00992521be0f8b;hpb=c2fcc2eaad945b2bee685ca8b71c565158da0e18;p=rrq%2Frrqmisc.git

diff --git a/vector/vector.h b/vector/vector.h
index 1227860..d3f99b6 100644
--- a/vector/vector.h
+++ b/vector/vector.h
@@ -1,168 +1,334 @@
 #ifndef vector_H
 #define vector_H
 
-/**
+/** \file vector.h
+ *
  * A vector is a dynamic pointer array implemented as an access tree
- * of index pages. The indexing is done using "unsigned long" indexes.
- */
-
-/*!
- * Macro: VECTOR_LEVEL_BITS
- * This defines the number of bits in the indexing bit field.
+ * of index pages. The indexing is done using "unsigned long" indexes,
+ * and the level 0 index corresponds to actual items.
+ *
+ * Actual vectors are assigned a leveling variant which defines the
+ * index page size for the vector. This must not be changed for a
+ * vector with entries.
+ *
+ * \subsubsection variantlist Variants:
+ *
+ * - 0 is 8-bit indexing parts and index pages with 256 pointers
+ * - 1 is 4-bit indexing parts and index pages with 16 pointers
+ * - 2 is 2-bit indexing parts and index pages with 4 pointers
+ * - 3 is for a single page sized as the vector.
+ *
+ * Variants 0-2 are managed by adding/removing full pages of the
+ * indexing tree upon resize and access. Variant 3 is managed by using
+ * realloc upon resize. In all cases shrinking a vector may mean to
+ * reclaim "lost" items, if any, via a provided item reclaim callback
+ * function which also may veto the shrinking.
  */
-#define VECTOR_LEVEL_BITS 4
 
-/*!
- * Type: vector_index
+/**
  * This is the general indexing used for vector access.
  */
 typedef unsigned long vector_index;
 
-/*!
- * Macro: VECTOR_INDEX_BITS
- * This defines the number of bits of a vector index
- */
-#define VECTOR_INDEX_BITS sizeof( vector_index )
-
-/*!
- * Macro: VECTOR_INDEX_FIELDS
- * This defines the number of bit fields in an vector index
+/**
+ * A vector_page is an array of void* items. Its size depends on the
+ * applicable vector variant: 2^(8-variant)
  */
-#define VECTOR_INDEX_FIELDS \
-    ( ( VECTOR_INDEX_BITS - 1 ) / VECTOR_LEVEL_BITS + 1 )
+typedef void* vector_page[];
 
-/*!
- * Macro: VECTOR_SLOTS
- * This defines the number of slots spanned by an index level
+/**
+ * A vector is a compound of a size and a vector_page pointer, which
+ * when non-null points out the top-most page of the vector indexing
+ * tree. The number of levels is derived from its size with level 0
+ * being the leaf level of actual content. E.g., a vector larger than
+ * 256 items, has at least two levels, and generally N levels may span
+ * up to 256^N content entries.
  */
-#define VECTOR_SLOTS ( 1 << VECTOR_LEVEL_BITS )
+typedef struct {
+    /**
+     * The indexing variant. 0 = 8-bit, 1 = 4-bit, and 2 = 2-bit
+     * indexing parts. This gives 256, 16 or 4 slots per index page.
+     * Note that variant should not be changed after initialization.
+     */
+    int variant;
+    /**
+     * The size of the vector.
+     */
+    vector_index size;
+    /**
+     * The root page of the indexing tree.
+     */
+    vector_page *entries;
+} vector;
 
-/*!
- * Type: vector_page
+/**
+ * \brief Return the number of slots spanned by an index level for the
+ * given vector variant.
  *
- * A vector_page is an array of 16 void* items.
+ * - 0 indicates 8-bit index parts, and 256 page slots
+ * - 1 indicates 4-bit index parts, and 16 page slots
+ * - 2 indicates 2-bit index parts, and 4 page slots
+ * - 3 indicates 64-bit index parts, and 1 page level following the size
+ * 
+ * The type 3 vector is managed by using realloc.
  */
-typedef void* vector_page[ VECTOR_SLOTS ];
+extern unsigned long VECTOR_SLOTS(vector *pv);
 
-/*!
- * Type: vector_field
- * This is VECTOR_LEVEL_BITS size bit field
- */
-typedef struct { int bits:VECTOR_LEVEL_BITS; } vector_field;
-
-/*!
- * Type: vector_indexing
+/**
+ * \brief Find the nearest used (non-null) slot at given or higher
+ * index.
  *
- * A vector index is ether viewed in whole as an VECTOR_INDEX_BITS wide
- * unsigned, or in levels as a packed array of vector_field index
- * parts. This implementation assumes LE integer layout.
+ * \param pv is the vector concerned.
+ *
+ * \param index is the index to change.
+ *
+ * \returns a pointer to the first non-null vector slot from the given
+ * index, and *index set accordingly. If no non-null slot is found,
+ * the 0 is returned and *index is set to the vector size.
+ *
+ * \related vector
  */
-typedef union {
-    vector_index whole;                     // as a whole
-    vector_field level[ VECTOR_INDEX_FIELDS ];  // qua bits fields
-} vector_indexing;
+extern void **vector_next_used(vector *pv,vector_index *index);
 
-// The indexing part for level part p in index i
-#define VECTOR_INDEX_PART(i,p) (((vector_indexing*)(i))->level[ p ].bits)
-
-/*!
- * Type: vector
+/**
+ * \brief Find the nearest used (non-null) slot at given or lower
+ * index.
  *
- * A vector is a compound of a size and a vector_page pointer, which
- * when non-null points out the top-most page of the vector. The
- * number of levels is derived from its size with level 0 being the
- * leaf level of actual content. E.g., a vector larger than 16
- * items, has at least two levels, and generally N levels may span up
- * to 16^N content entries.
- */
-typedef struct _vector {
-    vector_index size;     //!< Limit for the logical entries[]
-    vector_page *entries; //!< Pointer to entries indexing
-} vector;
-
-/*!
- * Find the next used slot at given index or later. With a reclaim
- * function, it will be invoked for verifying that the item is
- * actually in use, in which case it returns 1. Otherwise it should
- * reclaim any memory for the item and return 0;
+ * \param pv is the vector concerned.
+ *
+ * \param index is the index to change.
+ *
+ * \returns a pointer to the first non-null vector slot from the given
+ * index, and *index set accordingly. If no non-null slot is found,
+ * the 0 is returned and *index is set to the vector size.
+ *
+ * \related vector
  */
-void **vector_next_used(
-    vector *pv,vector_index *index,
-    int (*reclaim)(vector *pv,vector_index index,void *item,void *data),
-    void *data );
+extern void **vector_prev_used(vector *pv,vector_index *index);
 
-/*!
- * Function: int vector_resize(
- *              vector *pv,vector_index new_size,
- *              int (*reclaim)(vector *,vector_index,void *item,void *data),
- *              void *data )
- * \param pv
- * \param new_size
- * \param reclaim
- * \param data
- *
- * Tries to resize the given vector to a new size. This may result in
- * the introduction or removal of indexing pages, so that the leveling
- * is consistent with the vector size. Thus, if it grows into a new
- * 16^N level, then one or more new upper level pages are inserted as
- * needed. If it shrinks below the current level, then top-level pages
- * are remove.
+/**
+ * \brief Resize a vector.
+ *
+ * \param pv is the vector concerned.
+ *
+ * \param new_size is the new size it should have,
+ *
+ * \param reclaim is used upon shrinking in size for handling any
+ * current items above the new size, or vetoing the attempted resize.
+ *
+ * \param data is passed on the the reclaim function to use as context
+ * as needed.
+ *
+ * \returns the index of a resizing veto any, or <0 otherwise, with -1
+ * indicating success and -2 indicating OOM.
+ *
+ * This function attempts to resize the given vector to a new size.
+ * This may result in the introduction or removal of indexing pages,
+ * so that the index tree leveling is consistent with the vector size.
+ * Thus, if it grows into a new level, then one or more new upper
+ * level pages are inserted as needed. If it shrinks below the current
+ * level, then top-level pages are removed.
  *
  * Also, if the new size is smaller than currently, then the now
  * excess tail of entries is scanned for any used slots and the given
  * reclaim function is invoked successively for these. The reclaim
  * function must, in addition to memory-managing the entry, return 0
- * upon success and non-zero to veto the attempted vector size
- * change. The data argument is passed on to the reclaim function.
+ * upon success, or non-zero to veto the attempted vector size change.
+ * The data argument is passed on to the reclaim function as given.
  *
- * The vector_resize function returns 0 on success, with the size
- * duly changed. Otherwise the function retains the current size and
- * returns -index-1 for the index of the veto-ed entry.
+ * \related vector
  */
-int vector_resize(
+extern int vector_resize(
     vector *pv, vector_index new_size,
     int (*reclaim)(vector *pv,vector_index index,void *item,void *data),
     void *data );
 
-/*!
- * Function: void **vector_entry(vector *pv,vector_index index)
- * \param pv - the vector record
- * \param index - the slot index
+/** 
+ * \brief Return pointer to the indexed page slot at the requested
+ * level, and adding intermediate index pages if so requested.
+ *
+ * \param pv is the vector concerned.
+ *
+ * \param index is the slot index.
+ *
+ * \param level is the indexing level to access. Level 0 is the leaf
+ * level that holds the slots for the items; level 1 is one level up,
+ * for vectors larger than 256 items; ans so on.
+ *
+ * \param add is a flag to indicate (with 1) that missing index pages
+ * should be added, or (with 0) that the function should simply return
+ * null if an index page to access at any level is missing.
+ *
+ * \returns a pointer to the slot for the indexed item (level 0), or
+ * (for higher levels) the slot for the index page on the access path
+ * to the indexed item. The function returns 0 if the access path is
+ * broken by a missing index page, or (with add==1) the allocation of
+ * a new index page fails.
+ *
+ * \note The index tree for the vector is populated on demand only
+ * where access has been requested.
+ *
+ * \related vector
+ */
+extern void **vector_access(vector *pv,vector_index index,int level,int add);
+
+/**
+ * \brief Return the slot value at the given index.
+ *
+ * \param pv is the vector concerned.
  *
- * [pgix,epix] = modulo( index, pv->page );
+ * \param index is the slot index.
  *
  * \returns a direct pointer to the slot of the given index in the
- * array, or 0 if the index is beyond the array limits (0-limit). Note
- * that slot pointers are only valid while the vector size is
- * unchanged.
+ * array, or 0 if the index is beyond the array limits (0-limit).
+ *
+ * \note Note that slot pointers are only valid while the vector size
+ * is unchanged.
+ *
+ * \related vector
  */
 extern void **vector_entry(vector *pv,vector_index index); 
 
-/*!
- * Function: vector_index vector_size(vector *pv)
- * \param pv - the vector record
+/**
+ * \param pv - the vector concerned
  * \returns the size of the vector.
+ * \related vector
  */
-inline vector_index vector_size(vector *pv) {
-    return pv->size;
-}
+#define vector_size(pv) ((vector_index) (pv)->size)
 
-void vector_set(vector *pv,vector_index index,void *value);
+/**
+ * \brief Set the vector value at the given index.
+ *
+ * \param pv is the vector concerned
+ * \param index is the index for the slot to assign
+ * \param value is the new slot value
+ *
+ * \note An assignment of 0 will be treated as an unused slot.
+ *
+ * \related vector
+ */
+extern void vector_set(vector *pv,vector_index index,void *value);
 
-void *vector_get(vector *pv,vector_index index);
+/**
+ * \brief Set the vector value at the given index and return the prior
+ * value.
+ *
+ * \param pv is the vector concerned
+ * \param index is the index for the slot to assign
+ * \param value is the new slot value
+ *
+ * \note An assignment of 0 will be treated as an unused slot.
+ *
+ * \related vector
+ */
+extern void *vector_get_set(vector *pv,vector_index index,void *value);
 
-void vector_append(vector *pv,void *value);
+/**
+ * \brief Get the vector value at the given index.
+ *
+ * \param pv is the vector concerned
+ * \param index is the index for the slot to assign
+ *
+ * \note This function will allocate all traversed indeex tree pages
+ * even for accessing an unassigned slot.
+ *
+ * \related vector
+ */
+extern void *vector_get(vector *pv,vector_index index);
 
-void vector_copy(vector *dst,vector_index di,
-		  vector *src,vector_index si,vector_index n);
+/**
+ * \brief Grow the vector by one and assign the added slot.
+ *
+ * \param pv is the vector concerned
+ * \param value is the new slot value
+ *
+ * \related vector
+ */
+extern void vector_append(vector *pv,void *value);
 
-void vector_dump(vector *pv,
-		  int (*itemdump)(const vector_index ,const void *));
+/**
+ * \brief Copy a consecutive region from one vector into another, or
+ * possibly the same vector.
+ *
+ * \param pv is the vector concerned
+ * \param value is the new slot value
+ *
+ * \note This transfers all slots from the source region to the
+ * destination region, including zero slots. The vectors must be large
+ * enough for the transfer, which is carried out from lowest to
+ * highest or highest to lowest index depending on wther the move is
+ * to higher index or to lower index respectively.
+ *
+ * \related vector
+ */
+extern void vector_copy(
+    vector *dst,vector_index di,
+    vector *src,vector_index si,
+    vector_index n);
+
+/**
+ * \brief Utility function that invokes the itemdump function for all
+ * used (non-null) slots.
+ *
+ * \related vector
+ * \seealso vector_iterate
+ */
+extern void vector_dump(
+    vector *pv,
+    void (*itemdump)(const vector_index ,const void *));
 
-void vector_qsort(vector *pv,int (*compar)(const void *,const void *));
+extern void vector_qsort(vector *pv,int (*compar)(const void *,const void *));
+
+/**
+ * Steps through the vector item by item invoking the given function
+ * for each. Continues stepping while the item function returns 0.
+ *
+ * \related vector
+ */
+extern void vector_iterate(
+    vector *pv, vector_index start,
+    int (*itemfn)(vector_index,void *item,void *data),
+    void *data);
+
+/**
+ * \brief Binary search in a sorted vector for an item of the given
+ * key, with a callback function providing the sorting order.
+ *
+ * \param pv is the vector concerned.
+ *
+ * \param index is a vector_index pointer for returning the index of
+ * the found item.
+ *
+ * \param key is the lookup key to find.
+ *
+ * \param compare is a callback function that should return the search
+ * direction given a key and an item. It should return 0 if the key is
+ * a match for the item, <0 if the sought item is expected at a higher
+ * index, and >0 if the sought item is expected at a lower index.
+ *
+ * \return a pointer to the found item and *index set to its index. If
+ * there is no matching item, then 0 is returned, and the index is set
+ * to the vector size.
+ *
+ * \related vector
+ */
+extern void *vector_bsearch(
+    vector *pv, vector_index *index, const void *key,
+    int (*compare)(const void *key, const void *item));
 
-void vector_iterate(vector *pv,
-		     int (*itemfn)(vector_index,void*,void*),
-		     void*);
+/**
+ * \brief Find the next used slot at or after the given index.
+ *
+ * \param pv the vector concerned.
+ * \param index pointer to the index to advance.
+ * \return the new index, or the vector size if no unused slot is
+ * found.
+ *
+ * Scans forward in the vector for the first unused (null) vector slot
+ * at or after the given index. Returns pv->size if full.
+ *
+ * \related vector
+ */
+extern vector_index vector_next_unused(vector *pv,vector_index index);
 
 #endif