X-Git-Url: https://git.rrq.au/?a=blobdiff_plain;f=vector%2Fhashvector.h;h=2754fb1fc737ed674821e11cd98b43193770434c;hb=1d1b4665da461c93dba11aca34656d6ff8858c2e;hp=71b62539ec5b3149753011005d38301d68a2c276;hpb=c2fcc2eaad945b2bee685ca8b71c565158da0e18;p=rrq%2Frrqmisc.git diff --git a/vector/hashvector.h b/vector/hashvector.h index 71b6253..2754fb1 100644 --- a/vector/hashvector.h +++ b/vector/hashvector.h @@ -1,8 +1,13 @@ #ifndef hashvector_H #define hashvector_H +#include +#include + /** - * 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 @@ -10,87 +15,167 @@ * 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 * - * 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. + * \returns the next matching item, or \b 0 if none, with the index + * updated. + * + * \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. +/** + * \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. + * + * \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_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. +/** + * \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 + */ +extern int hashvector_delete(hashvector *hv,void *item); + +/** + * \brief Copy content items into a given empty \ref vector. + * + * \param hv is the \ref hashvector concerned. + * + * \param pv is the \ref vector to copy the content into. + * + * \returns \b -1 if the required resizing of the \ref vector to the + * \ref hashvector \b fill fails, otherwise \b 0 after having copied + * the hashvector items in their internal order of appearance into the + * \ref vector. + * + * \related hashvector */ -int hashvector_delete(hashvector *hv,void *item); +extern int hashvector_contents(hashvector *hv,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