#ifndef hashvector_H
#define hashvector_H
+#include <vector.h>
+#include <itemkeyfun.h>
+
/**
- * A hashvector is a use of vector as a hashtable. The hashvector
+ * \file hashvector.h
+ *
+ * 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
* 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 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 \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 _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 \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
+ /**
+ * 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 \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 \ref 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 \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 void *hashvector_next(hashvector *hv,vector_index *i,void *key);
+
+/**
+ * \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.
*
- * 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.
+ * \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
*/
-int hashvector_find(hashvector *hv,void *key,void **x);
+extern int hashvector_add(hashvector *hv,void *item);
-/*!
- * 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.
+/**
+ * \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
*/
-int hashvector_add(hashvector *hv,void *item);
+extern int hashvector_delete(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.
+/**
+ * \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
*/
-int hashvector_delete(hashvector *hv,void *item);
+extern vector *hashvector_contents(
+ hashvector *hv,enum vector_variant variant,vector *pv);
-/*!
- * 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.
+/**
+ * \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
*/
-int hashvector_contents(hashvector *hv,vector *pv);
+extern unsigned long hashvector_hashcode(unsigned char *key,unsigned long n);
-/*!
- * Function unsigned long hashvector_hashcode(
- * unsigned char *key,unsigned long n)
+/**
+ * \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.
*
- * Computes and returns a hashcode for a block of bytes.
+ * \related hashvector
*/
-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