5 #include <itemkeyfun.h>
10 * A hashvector is a use of vector as a hashtable. The hashvector
11 * includes three functions to, respectively, obtain the hashcode of a
12 * given key, to obtain the key of a given item, and to tell whether
13 * or not a given item has a given key. The hashvector manipulations
14 * uses those for locating and placing items into the vector; the
15 * hascode is the primary place for an item, but then scanning upwards
16 * with a rolling index in case of collisions.
18 * The vector holds 0 pointers for free slots, (void*)1 pointers (aka
19 * HV_HOLE) to indicate slots of deleted items, and otherwise item
20 * pointers. Thus, deleting an item results in av HV_HOLE et the
23 * The hashvector grows to double in size, with rehashing, when an
24 * item is added to make the sum of fill and holes exceed 50% of the
25 * size, and the hashvector shrinks to half size when an item is
26 * deleted to make fill reduce below 25% of the size.
32 * hashvector combines a vector (for contents) with fill and hole
33 * counters, and itemkeyfun callback functions for abstracting items
34 * as being pairs of key and payload.
38 * This is the backing vector for the hashvector. Items are placed
39 * in the vector by means of their key hashcodes, at the first
40 * unused slot cyclically after the hashcode index.
42 vector table; // the table space for items
44 * This is the fill count, i.e., how many key-distinct items there
45 * are in the backing vector.
47 unsigned long fill; // current number of contained items
49 * This is a count of HV_HOLE markers in the backing vector, which
50 * hold the position of deleted items so as to not break the
51 * lookup sequence for items placed cyclically after their
52 * hashcode index due to hash collisions.
54 unsigned long holes; // current number of slots marking deleted items
56 * This is a pointer to the itemkeyfun record that provides the
57 * key-and-payload abstraction for items.
59 itemkeyfun *type; // the key type for the items
63 * HV_HOLE is the representation of a deleted item. This supports the
64 * hashtable algoritm where hashcode collisions are resolved by
65 * placing later items compactly cyclically after their hashcode
66 * index. When an item is removed from the table, its slot is set as a
67 * HV_HOLE slot instead of being cleared.
71 #define HV_HOLE ((void*) 1)
74 * Find the item, if any, with the given key and assign *x with its
75 * address. Returns 1 on success and 0 on failure to find the keyed
76 * item. Note that when the function returns 0, *x is unchanged.
80 int hashvector_find(hashvector *hv,void *key,void **x);
83 * Add the given item into the hashvector, growing the hashvector as
84 * needed to ensure that its fill+holes is is no more than half the
85 * size. Note that this function first locates any item of the same
86 * key, and then doesn't add if there is already an item that has the
87 * same key. Returns 1 when an item is added, 0 when the item key
88 * is already present, and -1 upon OOM or ovefull hashvector.
92 int hashvector_add(hashvector *hv,void *item);
95 * Delete the given item, and shrink the hashvector so that its size
96 * is at most double its fill, though at least 256 slots. Returns 1
97 * when the item gets deleted (by replacing its slot with a HV_HOLE
98 * value, 0 if the hashvector has either no item or a different item
99 * for the item key, and -1 in case of OOM or overfull hashvector.
101 * \related hashvector
103 int hashvector_delete(hashvector *hv,void *item);
106 * Copy content items into a vector, which must be empty. The
107 * function returns -1 if the resizing of the vector to the
108 * hashvector fill fails, otherwise 0 after having copied the
109 * hashvector items in their internal order of appearance into the
112 * \related hashvector
114 int hashvector_contents(hashvector *hv,vector *pv);
117 * This is a utility function to compute and return a hashcode for a
120 * \related hashvector
122 unsigned long hashvector_hashcode(unsigned char *key,unsigned long n);