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.
39 * This is the backing vector for the hashvector. Items are placed
40 * in the vector by means of their key hashcodes, at the first
41 * unused slot cyclically after the hashcode index.
43 vector table; // the table space for items
45 * This is the fill count, i.e., how many key-distinct items there
46 * are in the backing vector.
48 unsigned long fill; // current number of contained items
50 * This is a count of HV_HOLE markers in the backing vector, which
51 * hold the position of deleted items so as to not break the
52 * lookup sequence for items placed cyclically after their
53 * hashcode index due to hash collisions.
55 unsigned long holes; // current number of slots marking deleted items
57 * This is a pointer to the itemkeyfun record that provides the
58 * key-and-payload abstraction for items.
60 itemkeyfun *type; // the key type for the items
64 * HV_HOLE is the representation of a deleted item. This supports the
65 * hashtable algoritm where hashcode collisions are resolved by
66 * placing later items compactly cyclically after their hashcode
67 * index. When an item is removed from the table, its slot is set as a
68 * HV_HOLE slot instead of being cleared.
72 #define HV_HOLE ((void*) 1)
75 * \brief Find next keyed item at or after the given index.
76 * \param hv is the hasvector concerned
77 * \param index is a pointer to the index to advance
78 * \param key is the query key
79 * \returns the next matching item, or 0 if none, with the index updated.
83 extern void *hashvector_next(hashvector *hv,vector_index *i,void *key);
86 * Add the given item into the hashvector, growing the hashvector as
87 * needed to ensure that its fill+holes is is no more than half the
88 * size. Note that this function first locates any item of the same
89 * key, and then doesn't add if there is already an item that has the
90 * same key. Returns 1 when an item is added, 0 when the item key
91 * is already present, and -1 upon OOM or ovefull hashvector.
95 extern int hashvector_add(hashvector *hv,void *item);
98 * Delete the given item, and shrink the hashvector so that its size
99 * is at most double its fill, though at least 256 slots. Returns 1
100 * when the item gets deleted (by replacing its slot with a HV_HOLE
101 * value, 0 if the hashvector has either no item or a different item
102 * for the item key, and -1 in case of OOM or overfull hashvector.
104 * \related hashvector
106 extern int hashvector_delete(hashvector *hv,void *item);
109 * Copy content items into a vector, which must be empty. The
110 * function returns -1 if the resizing of the vector to the
111 * hashvector fill fails, otherwise 0 after having copied the
112 * hashvector items in their internal order of appearance into the
115 * \related hashvector
117 extern int hashvector_contents(hashvector *hv,vector *pv);
120 * This is a utility function to compute and return a hashcode for a
123 * \related hashvector
125 extern unsigned long hashvector_hashcode(unsigned char *key,unsigned long n);
128 * Create a hashvector for of given variant for given itemkeyfun*
130 extern hashvector *hashvector_create(
131 enum vector_variant variant,itemkeyfun *type);