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 * \brief Find next keyed item at or after the given index.
75 * \param hv is the hasvector concerned
76 * \param index is a pointer to the index to advance
77 * \param key is the query key
78 * \returns the next matching item, or 0 if none, with the index updated.
82 extern void *hashvector_next(hashvector *hv,vector_index *i,void *key);
85 * Add the given item into the hashvector, growing the hashvector as
86 * needed to ensure that its fill+holes is is no more than half the
87 * size. Note that this function first locates any item of the same
88 * key, and then doesn't add if there is already an item that has the
89 * same key. Returns 1 when an item is added, 0 when the item key
90 * is already present, and -1 upon OOM or ovefull hashvector.
94 extern int hashvector_add(hashvector *hv,void *item);
97 * Delete the given item, and shrink the hashvector so that its size
98 * is at most double its fill, though at least 256 slots. Returns 1
99 * when the item gets deleted (by replacing its slot with a HV_HOLE
100 * value, 0 if the hashvector has either no item or a different item
101 * for the item key, and -1 in case of OOM or overfull hashvector.
103 * \related hashvector
105 extern int hashvector_delete(hashvector *hv,void *item);
108 * Copy content items into a vector, which must be empty. The
109 * function returns -1 if the resizing of the vector to the
110 * hashvector fill fails, otherwise 0 after having copied the
111 * hashvector items in their internal order of appearance into the
114 * \related hashvector
116 extern int hashvector_contents(hashvector *hv,vector *pv);
119 * This is a utility function to compute and return a hashcode for a
122 * \related hashvector
124 extern unsigned long hashvector_hashcode(unsigned char *key,unsigned long n);
127 * Create a hashvector for of given variant for given itemkeyfun*
129 extern hashvector *hashvector_create(
130 enum vector_variant variant,itemkeyfun *type);