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

diff --git a/vector/vector.h b/vector/vector.h
index d3f99b6..33cf96a 100644
--- a/vector/vector.h
+++ b/vector/vector.h
@@ -1,7 +1,7 @@
 #ifndef vector_H
 #define vector_H
 
-/** \file vector.h
+/** \file
  *
  * A vector is a dynamic pointer array implemented as an access tree
  * of index pages. The indexing is done using "unsigned long" indexes,
@@ -10,39 +10,60 @@
  * 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.
  */
 
 /**
- * This is the general indexing used for vector access.
+ * \brief This is the general indexing used for vector access.
+ *
+ * \related vector
  */
 typedef unsigned long vector_index;
 
 /**
- * A vector_page is an array of void* items. Its size depends on the
- * applicable vector variant: 2^(8-variant)
+ * \brief A vector_page is an array of void* items. Its size depends
+ * on the applicable vector variant.
+ *
+ * \related vector
  */
 typedef void* vector_page[];
 
 /**
- * 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.
+ * \brief The implementation variants.
+ *
+ * - byte_index_levels (0) has 8-bit indexing parts and index pages
+ *   with 256 pointers,
+ *
+ * - nibble_index_levels (1) has 4-bit indexing parts and index pages
+ *   with 16 pointers,
+ *
+ * - bitpair_index_levels (2) has 2-bit indexing parts and index pages
+ *   with 4 pointers,
+ *
+ * - single_index_level (3) has a single page that is sized as the
+ *   vector.
+ *
+ * The first three variants are managed by adding/removing full pages
+ * of the indexing tree upon resize and access. The single_index_level
+ * variant is managed by using realloc upon resize. In all cases
+ * shrinking a vector might mean to reclaim items about to be "lost",
+ * if any, via a provided item reclaim callback function. The callback
+ * function may then also veto the shrinking.
+ *
+ * \related vector
+ */
+enum vector_variant {
+    byte_index_levels = 0,
+    nibble_index_levels = 1,
+    bitpair_index_levels = 2,
+    single_index_level = 3
+};
+
+/**
+ * A vector struct is the "foot part" of a representation that
+ * constitutes the implementation variant for a vector abstraction. It
+ * holds the variant indicator, the intended slot size and a root
+ * pointer for the indexing structure, which consist of indexing pages
+ * according to the variant.
  */
 typedef struct {
     /**
@@ -50,11 +71,13 @@ typedef struct {
      * indexing parts. This gives 256, 16 or 4 slots per index page.
      * Note that variant should not be changed after initialization.
      */
-    int variant;
+    enum vector_variant variant;
+
     /**
      * The size of the vector.
      */
     vector_index size;
+
     /**
      * The root page of the indexing tree.
      */
@@ -71,6 +94,7 @@ typedef struct {
  * - 3 indicates 64-bit index parts, and 1 page level following the size
  * 
  * The type 3 vector is managed by using realloc.
+ * \related vector
  */
 extern unsigned long VECTOR_SLOTS(vector *pv);
 
@@ -266,6 +290,11 @@ extern void vector_copy(
     vector *src,vector_index si,
     vector_index n);
 
+/**
+ * \brief Allocate a copy of a vector into one in the given variant.
+ */
+extern vector *vector_clone(enum vector_variant variant,vector *src);
+
 /**
  * \brief Utility function that invokes the itemdump function for all
  * used (non-null) slots.
@@ -277,6 +306,12 @@ extern void vector_dump(
     vector *pv,
     void (*itemdump)(const vector_index ,const void *));
 
+/**
+ * \brief Sort a vector with quicksort using the provided ordering
+ * collback function.
+ *
+ * \related vector
+ */
 extern void vector_qsort(vector *pv,int (*compar)(const void *,const void *));
 
 /**
@@ -316,6 +351,19 @@ extern void *vector_bsearch(
     vector *pv, vector_index *index, const void *key,
     int (*compare)(const void *key, const void *item));
 
+/**
+ * \brief Find the index for a given value
+ *
+ * \param pv is the vector concerned
+ * \param is the value to find
+ *
+ * This function scans the vector for the first, if any, occurrence of
+ * the value, or returns pv->size if not found.
+ *
+ * \related vector
+ */
+extern vector_index vector_find(vector *pv,void *value);
+
 /**
  * \brief Find the next used slot at or after the given index.
  *