#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
* 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)
+/**
+ * \brief Find next keyed item at or after the given index.
+ * \param hv is the hasvector concerned
+ * \param index is a pointer to the index to advance
+ * \param key is the query key
+ * \returns the next matching item, or 0 if none, with the index updated.
*
- * 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);
+extern void *hashvector_next(hashvector *hv,vector_index *i,void *key);
-/*!
- * 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);
+extern 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);
+extern 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);
+extern 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
+ */
+extern unsigned long hashvector_hashcode(unsigned char *key,unsigned long n);
+
+/**
+ * Create a hashvector for of given variant for given itemkeyfun*
*/
-unsigned long hashvector_hashcode(unsigned char *key,unsigned long n);
+extern hashvector *hashvector_create(
+ enum vector_variant variant,itemkeyfun *type);
#endif
projects / rrq / rrqmisc.git / blobdiff