Use enum for variants; add "clone" and "find" and imporv doco

[rrq/rrqmisc.git] / vector / vector.h

diff --git a/vector/vector.h b/vector/vector.h
index b18603f5ebdb514128e13c17080413e849f39f9c..33cf96a46ce26919d927ca019891c83b5cae5bbb 100644 (file)
--- 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,23 +10,11 @@
  * 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.
  */
 
 /**
  * \brief This is the general indexing used for vector access.
+ *
  * \related vector
  */
 typedef unsigned long vector_index;
@@ -34,19 +22,48 @@ typedef unsigned long vector_index;
 /**
  * \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 struct is the "foot part" of an actual containing the
- * applicable implementation variant for this vector, the intended
- * slot size and a root pointer for the indexing structure, which
- * consist of indexing pages according to the variant.
- *
- * Variant 0, 1 and 2, involves indexing pages of 256, 16 and 4
- * pointers respectively. Variant 3 involves a single indexing page of
- * the size of the vector.
+ * \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 {
     /**
@@ -54,7 +71,7 @@ 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.
@@ -273,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.
@@ -329,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.
  *