5 * A hashvector is a use of vector as a hashtable. The hashvector
6 * includes three functions to, respectively, obtain the hashcode of a
7 * given key, to obtain the key of a given item, and to tell whether
8 * or not a given item has a given key. The hashvector manipulations
9 * uses those for locating and placing items into the vector; the
10 * hascode is the primary place for an item, but then scanning upwards
11 * with a rolling index in case of collisions.
13 * The vector holds 0 pointers for free slots, (void*)1 pointers (aka
14 * HV_HOLE) to indicate slots of deleted items, and otherwise item
15 * pointers. Thus, deleting an item results in av HV_HOLE et the
18 * The hashvector grows to double in size, with rehashing, when the
19 * sum of items and holes exceeds 50% fill, and it shrinks to half
20 * size when item numbers reduces below 50%.
27 * This combines a vector (for contents) with fill and hole counters
28 * and the three functions.
30 typedef struct _hashvector {
32 unsigned long fill; // number of added elements
33 unsigned long holes; // number of deleted
34 unsigned long (*keyhashcode)(void *key); // The hashcode of a key
35 void *(*itemkey)(void *item); // the key of ain item
36 int (*haskey)(void *item,void *key); // whether an item has a given
41 * The representation of a deleted item.
43 #define HV_HOLE ((void*) 1)
46 * Function: int hashvector_find(hashvector *hv,void *key,void **x)
48 * Find the item, if any, with the given key and assign *x with its
49 * address. Returns 1 on success and 0 on failure to find the keyed
50 * item. Note that when the function returns 0, *x is unchanged.
52 int hashvector_find(hashvector *hv,void *key,void **x);
55 * Function: void hashvector_add(hashvector *hv,void *item)
57 * Add the given item into the hashvector, growing the hashvector as
58 * needed to ensure that its fill+holes is is no more than half the
59 * size. Note that this function first locates any item of the same
60 * key, and then doesn't add if there is already an item that has the
61 * same key. Returns 1 when an item is added, 0 when the item key
62 * is already present, and -1 upon OOM or ovefull hashvector.
64 int hashvector_add(hashvector *hv,void *item);
67 * Function: void hashvector_delete(hashvector *hv,void *item)
69 * Delete the given item, and shrink the hashvector so that its size
70 * is at most double its fill, though at least 256 slots. Returns 1
71 * when the item gets deleted (by replacing its slot with a HV_HOLE
72 * value, 0 if the hashvector has either no item or a different item
73 * for the item key, and -1 in case of OOM or overfull hashvector.
75 int hashvector_delete(hashvector *hv,void *item);
78 * Function: int hashvector_contents(hashvector *hv,vector *pv)
80 * Copy content items into a vector, which must be empty. The
81 * function returns -1 if the resizing of the vector to the
82 * hashvector fill fails, otherwise 0 after having copied the
83 * hashvector items in their internal order of appearance into the
86 int hashvector_contents(hashvector *hv,vector *pv);
89 * Function unsigned long hashvector_hashcode(
90 * unsigned char *key,unsigned long n)
92 * Computes and returns a hashcode for a block of bytes.
94 unsigned long hashvector_hashcode(unsigned char *key,unsigned long n);