#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
projects / rrq / rrqmisc.git / blobdiff