X-Git-Url: https://git.rrq.au/?a=blobdiff_plain;f=vector%2Fhashvector.h;h=b57aede5a0a5e9241993adb6aab4b324c87e4596;hb=1598c2a362fec3de547616cb8020a315631a4c15;hp=1c3f387443bda77cd212479d3dc56a74c50532d5;hpb=fff7d7c2ac83984bd2fc7ec3c72dc455c7c72807;p=rrq%2Frrqmisc.git

diff --git a/vector/hashvector.h b/vector/hashvector.h
index 1c3f387..b57aede 100644
--- a/vector/hashvector.h
+++ b/vector/hashvector.h
@@ -7,7 +7,7 @@
 /**
  * \file hashvector.h
  *
- * A hashvector is a use of vector as a hashtable. The hashvector
+ * A hashvector is a use of \ref vector as a hashtable. The hashvector
  * includes three functions to, respectively, obtain the hashcode of a
  * given key, to obtain the key of a given item, and to tell whether
  * or not a given item has a given key. The hashvector manipulations
@@ -15,10 +15,10 @@
  * hascode is the primary place for an item, but then scanning upwards
  * with a rolling index in case of collisions.
  *
- * The vector holds 0 pointers for free slots, (void*)1 pointers (aka
- * HV_HOLE) to indicate slots of deleted items, and otherwise item
- * pointers. Thus, deleting an item results in av HV_HOLE et the
- * item's slot.
+ * The vector holds (void*)0 pointers for free slots, (void*)1
+ * pointers (aka \ref HV_HOLE) to indicate slots of deleted items, and
+ * otherwise item pointers. Thus, deleting an item results in av
+ * HV_HOLE et the item's slot.
  *
  * The hashvector grows to double in size, with rehashing, when an
  * item is added to make the sum of fill and holes exceed 50% of the
@@ -29,15 +29,17 @@
 /**
  * \struct hashvector
  *
- * hashvector combines a vector (for contents) with fill and hole
- * counters, and itemkeyfun callback functions for abstracting items
- * as being pairs of key and payload.
+ * hashvector combines a \ref vector (for contents) with fill and hole
+ * counters, and \ref itemkeyfun callback functions for abstracting
+ * items as being pairs of key and payload.
+ *
+ * \extends vector
  */
 typedef struct {
     /**
-     * This is the backing vector for the hashvector. Items are placed
-     * in the vector by means of their key hashcodes, at the first
-     * unused slot cyclically after the hashcode index.
+     * This is the backing \ref vector for the hashvector. Items are
+     * placed in the vector by means of their key hashcodes, at the
+     * first unused slot cyclically after the hashcode index.
      */
     vector table;        // the table space for items
     /**
@@ -46,15 +48,15 @@ typedef struct {
      */
     unsigned long fill;  // current number of contained items
     /**
-     * This is a count of HV_HOLE markers in the backing vector, which
-     * hold the position of deleted items so as to not break the
+     * This is a count of \ref HV_HOLE markers in the backing vector,
+     * which hold the position of deleted items so as to not break the
      * lookup sequence for items placed cyclically after their
      * hashcode index due to hash collisions.
      */
     unsigned long holes; // current number of slots marking deleted items
     /**
-     * This is a pointer to the itemkeyfun record that provides the
-     * key-and-payload abstraction for items.
+     * This is a pointer to the \ref itemkeyfun record that provides
+     * the key-and-payload abstraction for items.
      */
     itemkeyfun *type;    // the key type for the items
 } hashvector;
@@ -71,59 +73,116 @@ typedef struct {
 #define HV_HOLE ((void*) 1)
 
 /**
- * Find the item, if any, with the given key and assign *x with its
- * address. Returns 1 on success and 0 on failure to find the keyed
- * item. Note that when the function returns 0, *x is unchanged.
+ * \brief Find next keyed item at or after the given index.
+ *
+ * \param hv is the \ref hashvector concerned.
+ *
+ * \param index is a pointer to the index to advance.
+ * \
+ * \param key is the query key
+ *
+ * \returns the next matching item, or \b 0 if none, with the index
+ * updated.
  *
  * \related hashvector
  */
-extern int hashvector_find(hashvector *hv,void *key,void **x);
+extern void *hashvector_next(hashvector *hv,vector_index *i,void *key);
 
 /**
- * Add the given item into the hashvector, growing the hashvector as
- * needed to ensure that its fill+holes is is no more than half the
- * size. Note that this function first locates any item of the same
- * key, and then doesn't add if there is already an item that has the
- * same key. Returns 1 when an item is added, 0 when the item key
- * is already present, and -1 upon OOM or ovefull hashvector.
+ * \brief Add the given item into the \ref hashvector, growing it as
+ * needed to ensure that its fill+holes is no more than half the size.
+ *
+ * \param hv is the \ref hashvector concerned.
+ *
+ * \param item is the item to add.
+ *
+ * \returns \b 1 when an item is added, \b 0 when the item key is
+ * already present, and \b -1 upon OOM or ovefull \ref hashvector.
+ *
+ * Note that this function first locates any item of the same key, and
+ * then doesn't add if there is already an item that has the same key.
  *
  * \related hashvector
  */
 extern int hashvector_add(hashvector *hv,void *item);
 
 /**
- * Delete the given item, and shrink the hashvector so that its size
- * is at most double its fill, though at least 256 slots. Returns 1
- * when the item gets deleted (by replacing its slot with a HV_HOLE
- * value, 0 if the hashvector has either no item or a different item
- * for the item key, and -1 in case of OOM or overfull hashvector.
+ * \brief Delete the given item, and shrink the hashvector so that its
+ * size is at most double its fill, though at minimum a single index
+ * page corresponding to the \ref vector_variant in use.
+ *
+ * \param hv is the \ref hashvector concerned.
+ *
+ * \param item is the item to delete.
+ *
+ * \returns \b 1 when the item gets deleted (by replacing its slot
+ * with a \ref HV_HOLE value), \b 0 if the hashvector has either no
+ * item or a different item for the item key, and \b -1 in case of OOM
+ * or overfull hashvector.
+ *
+ * Note that the contained item that has the same key as the provided
+ * item is deleted.
+ *
+ * \see itemkeyfun
  *
  * \related hashvector
  */
 extern int hashvector_delete(hashvector *hv,void *item);
 
 /**
- * Copy content items into a vector, which must be empty. The
- * function returns -1 if the resizing of the vector to the
- * hashvector fill fails, otherwise 0 after having copied the
- * hashvector items in their internal order of appearance into the
- * vector.
+ * \brief Copy content items into a given empty \ref vector.
+ * 
+ * \param hv is the \ref hashvector concerned.
+ *
+ * \param variant is the desired vector variant.
+ *
+ * \param pv is the optional \ref vector to copy the content into.
+ *
+ * \returns the \ref vector with the \ref hashvector content
+ *
+ * If \pv is null, then a new vector is allocated and handed out for
+ * the caller to reclaim unless the hashvector is empty in which case
+ * this function returns 0.
+ *
+ * If \b pv is not null, it is first cleared, and then populated with
+ * the content from the hashvector. The populated vector is returned.
  *
  * \related hashvector
  */
-extern int hashvector_contents(hashvector *hv,vector *pv);
+extern vector *hashvector_contents(
+    hashvector *hv,enum vector_variant variant,vector *pv);
 
 /**
- * This is a utility function to compute and return a hashcode for a
- * block of bytes.
+ * \brief This is a utility function to compute and return a hashcode
+ * for a block of bytes.
+ *
+ * \param key is the start of the block.
+ *
+ * \param n is the byte size of the block.
  *
  * \related hashvector
  */
 extern unsigned long hashvector_hashcode(unsigned char *key,unsigned long n);
 
 /**
- * Create a hashvector for of given variant for given itemkeyfun*
+ * \brief Create a \ref hashvector of given \ref vector_variant
+ * for given \ref itemkeyfun.
+ *
+ * \param variant is the \ref vector_variant to use.
+ *
+ * \param type is the \ref itemkeyfun to use.
+ *
+ * \returns the initialised \ref hashvector.
+ *
+ * The hashvector will be initialized with a single \ref vector_page.
+ *
+ * \note The \ref hashvector record is allocated with malloc and the
+ * caller is responsible for free-ing the memory block when it's no
+ * longer needed.
+ *
+ * \related hashvector
  */
-extern hashvector *hashvector_create(int variant,itemkeyfun *type);
+extern hashvector *hashvector_create(
+    enum vector_variant variant,itemkeyfun *type);
 
 #endif