5 #include <itemkeyfun.h>
10 * A hashvector is a use of \ref 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 (void*)0 pointers for free slots, (void*)1
19 * pointers (aka \ref HV_HOLE) to indicate slots of deleted items, and
20 * otherwise item pointers. Thus, deleting an item results in av
21 * HV_HOLE et the item's slot.
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 \ref vector (for contents) with fill and hole
33 * counters, and \ref itemkeyfun callback functions for abstracting
34 * items as being pairs of key and payload.
40 * This is the backing \ref vector for the hashvector. Items are
41 * placed in the vector by means of their key hashcodes, at the
42 * first unused slot cyclically after the hashcode index.
44 vector table; // the table space for items
46 * This is the fill count, i.e., how many key-distinct items there
47 * are in the backing vector.
49 unsigned long fill; // current number of contained items
51 * This is a count of \ref HV_HOLE markers in the backing vector,
52 * which hold the position of deleted items so as to not break the
53 * lookup sequence for items placed cyclically after their
54 * hashcode index due to hash collisions.
56 unsigned long holes; // current number of slots marking deleted items
58 * This is a pointer to the \ref itemkeyfun record that provides
59 * the key-and-payload abstraction for items.
61 itemkeyfun *type; // the key type for the items
65 * HV_HOLE is the representation of a deleted item. This supports the
66 * hashtable algoritm where hashcode collisions are resolved by
67 * placing later items compactly cyclically after their hashcode
68 * index. When an item is removed from the table, its slot is set as a
69 * HV_HOLE slot instead of being cleared.
73 #define HV_HOLE ((void*) 1)
76 * \brief Find next keyed item at or after the given index.
78 * \param hv is the \ref hashvector concerned.
80 * \param index is a pointer to the index to advance.
82 * \param key is the query key
84 * \returns the next matching item, or \b 0 if none, with the index
89 extern void *hashvector_next(hashvector *hv,vector_index *i,void *key);
92 * \brief Add the given item into the \ref hashvector, growing it as
93 * needed to ensure that its fill+holes is no more than half the size.
95 * \param hv is the \ref hashvector concerned.
97 * \param item is the item to add.
99 * \returns \b 1 when an item is added, \b 0 when the item key is
100 * already present, and \b -1 upon OOM or ovefull \ref hashvector.
102 * Note that this function first locates any item of the same key, and
103 * then doesn't add if there is already an item that has the same key.
105 * \related hashvector
107 extern int hashvector_add(hashvector *hv,void *item);
110 * \brief Delete the given item, and shrink the hashvector so that its
111 * size is at most double its fill, though at minimum a single index
112 * page corresponding to the \ref vector_variant in use.
114 * \param hv is the \ref hashvector concerned.
116 * \param item is the item to delete.
118 * \returns \b 1 when the item gets deleted (by replacing its slot
119 * with a \ref HV_HOLE value), \b 0 if the hashvector has either no
120 * item or a different item for the item key, and \b -1 in case of OOM
121 * or overfull hashvector.
123 * Note that the contained item that has the same key as the provided
128 * \related hashvector
130 extern int hashvector_delete(hashvector *hv,void *item);
133 * \brief Copy content items into a given empty \ref vector.
135 * \param hv is the \ref hashvector concerned.
137 * \param pv is the \ref vector to copy the content into.
139 * \returns \b -1 if the required resizing of the \ref vector to the
140 * \ref hashvector \b fill fails, otherwise \b 0 after having copied
141 * the hashvector items in their internal order of appearance into the
144 * \related hashvector
146 extern int hashvector_contents(hashvector *hv,vector *pv);
149 * \brief This is a utility function to compute and return a hashcode
150 * for a block of bytes.
152 * \param key is the start of the block.
154 * \param n is the byte size of the block.
156 * \related hashvector
158 extern unsigned long hashvector_hashcode(unsigned char *key,unsigned long n);
161 * \brief Create a \ref hashvector of given \ref vector_variant
162 * for given \ref itemkeyfun.
164 * \param variant is the \ref vector_variant to use.
166 * \param type is the \ref itemkeyfun to use.
168 * \returns the initialised \ref hashvector.
170 * The hashvector will be initialized with a single \ref vector_page.
172 * \note The \ref hashvector record is allocated with malloc and the
173 * caller is responsible for free-ing the memory block when it's no
176 extern hashvector *hashvector_create(
177 enum vector_variant variant,itemkeyfun *type);