X-Git-Url: https://git.rrq.au/?a=blobdiff_plain;f=pvector%2Fhashvector.h;h=a5b426bd4daee2e2b04f068344145759a72c2ea0;hb=efd06144cd7b5ab1720ef2cda59bd7568f31d034;hp=b886660d900860433afc96f637cf3f0b565011a6;hpb=49912b2bb9fca7e0608e52ead72efdb14923b843;p=rrq%2Frrqmisc.git

diff --git a/pvector/hashvector.h b/pvector/hashvector.h
index b886660..a5b426b 100644
--- a/pvector/hashvector.h
+++ b/pvector/hashvector.h
@@ -1,43 +1,96 @@
 #ifndef hashvector_H
 #define hashvector_H
 
-#ifdef USE_PTHREAD
-#define __USE_GNU 1
-#include <pthread.h>
-#endif
+/**
+ * hashvector is a use of pvector 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
+ * uses those for locating and placing items into the vector; the
+ * 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 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%.
+ */
 
 #include "pvector.h"
 
+/*!
+ * Type: hashvector
+ * This combines a pvector (for contents) with fill and hole counters
+ * and the three functions.
+ */
 typedef struct _hashvector {
     pvector table;
-    unsigned int fill;    // number of added elements
-    unsigned int holes;   // number of deleted
-    int (*keyhashcode)(void *key);
-    void *(*itemkey)(void *item);
-    int (*haskey)(void *item,void *key);
-#ifdef USE_PTHREAD
-    pthread_mutex_t lock;
-#endif
+    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
 } hashvector;
 
+/*!
+ * Macro: HV_HOLE
+ * The representation of a deleted item.
+ */
 #define HV_HOLE ((void*) 1)
 
-// Find the keyed element, and assign the x pointer, or assign 0.
-// Returns 1 if element is found and 0 otherwise.
+/*!
+ * 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.
+ */
 int hashvector_find(hashvector *hv,void *key,void **x);
 
-// Add the given element.
-void hashvector_add(hashvector *hv,void *p);
+/*!
+ * 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.
+ */
+int hashvector_add(hashvector *hv,void *item);
 
-// Return the next element starting at i, or 0 if there are no more.
-// Also increment the index to be of the element + 1, or -1 if there
-// are no more elements.
-//unsigned char *htnext(htable *table,int *i);
+/*!
+ * 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.
+ */
+int hashvector_delete(hashvector *hv,void *item);
 
-// Delete the given element.
-void hashvector_delete(hashvector *hv,void *p);
+/*!
+ * Function: int hashvector_contents(hashvector *hv,pvector *pv)
+ *
+ * Copy content items into a pvector, which must be empty. The
+ * function returns -1 if the resizing of the pvector to the
+ * hashvector fill fails, otherwise 0 after having copied the
+ * hashvector items in their internal order of appearance into the
+ * pvector.
+ */
+int hashvector_contents(hashvector *hv,pvector *pv);
 
-// Copy content items into pvector, which must be empty.
-int hashvector_pack(hashvector *hv,pvector *pv);
+/*!
+ * Function unsigned long hashvector_hashcode(
+ *              unsigned char *key,unsigned long n)
+ *
+ * Computes and returns a hashcode for a block of bytes.
+ */
+unsigned long hashvector_hashcode(unsigned char *key,unsigned long n);
 
 #endif