X-Git-Url: https://git.rrq.au/?a=blobdiff_plain;f=vector%2Fhashvector.h;h=d0f9e12f23114f0ec5aecac85c289e9641d49c85;hb=c1aae73b1fafd372c4f38a1a205e20a9f22a2fa0;hp=1994b66546024e2725ff418e8ba15473b1cb41a4;hpb=475928381654054e66270d48001c1a9b6e4258b6;p=rrq%2Frrqmisc.git

diff --git a/vector/hashvector.h b/vector/hashvector.h
index 1994b66..d0f9e12 100644
--- a/vector/hashvector.h
+++ b/vector/hashvector.h
@@ -1,7 +1,12 @@
 #ifndef hashvector_H
 #define hashvector_H
 
+#include <vector.h>
+#include <itemkeyfun.h>
+
 /**
+ * \file hashvector.h
+ *
  * A hashvector is a use of 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
@@ -15,81 +20,104 @@
  * 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 the
- * sum of items and holes exceeds 50% fill, and it shrinks to half
- * size when item numbers reduces below 50%.
+ * 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
+ * size, and the hashvector shrinks to half size when an item is
+ * deleted to make fill reduce below 25% of the size.
  */
 
-#include <vector.h>
-
-/*!
- * Type: hashvector
- * This combines a vector (for contents) with fill and hole counters
- * and the three functions.
+/**
+ * \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.
  */
-typedef struct _hashvector {
-    vector table;
-    unsigned long fill;                   // number of added elements
-    unsigned long holes;                  // number of deleted
-    unsigned long (*keyhashcode)(void *key); // The hashcode of a key
-    void *(*itemkey)(void *item);        // the key of ain item
-    int (*haskey)(void *item,void *key); // whether an item has a given
+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.
+     */
+    vector table;        // the table space for items
+    /**
+     * This is the fill count, i.e., how many key-distinct items there
+     * are in the backing vector.
+     */
+    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
+     * 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.
+     */
+    itemkeyfun *type;    // the key type for the items
 } hashvector;
 
-/*!
- * Macro: HV_HOLE
- * The representation of a deleted item.
+/**
+ * HV_HOLE is the representation of a deleted item. This supports the
+ * hashtable algoritm where hashcode collisions are resolved by
+ * placing later items compactly cyclically after their hashcode
+ * index. When an item is removed from the table, its slot is set as a
+ * HV_HOLE slot instead of being cleared.
+ *
+ * \related hashvector
  */
 #define HV_HOLE ((void*) 1)
 
-/*!
- * Function: int hashvector_find(hashvector *hv,void *key,void **x)
- *
+/**
  * 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.
+ *
+ * \related hashvector
  */
 int hashvector_find(hashvector *hv,void *key,void **x);
 
-/*!
- * Function: void hashvector_add(hashvector *hv,void *item)
- *
+/**
  * 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.
+ *
+ * \related hashvector
  */
 int hashvector_add(hashvector *hv,void *item);
 
-/*!
- * Function: void hashvector_delete(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.
+ *
+ * \related hashvector
  */
 int hashvector_delete(hashvector *hv,void *item);
 
-/*!
- * Function: int hashvector_contents(hashvector *hv,vector *pv)
- *
+/**
  * 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.
+ *
+ * \related hashvector
  */
 int hashvector_contents(hashvector *hv,vector *pv);
 
-/*!
- * Function unsigned long hashvector_hashcode(
- *              unsigned char *key,unsigned long n)
+/**
+ * This is a utility function to compute and return a hashcode for a
+ * block of bytes.
  *
- * Computes and returns a hashcode for a block of bytes.
+ * \related hashvector
  */
 unsigned long hashvector_hashcode(unsigned char *key,unsigned long n);