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.
38 typedef struct HashVector {
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 Lookup the first item with the given key.
78 * \param hv is the \ref HashVector concerned.
80 * \param key is the key to find.
82 * \returns the item if any or \b 0 if none.
86 void *HashVector_find(HashVector *hv,void *key);
89 * \brief Scan the table by index
91 * \param hv is the \ref HashVector concerned.
93 * \param index is a pointer to the index to advance.
95 * \returns the next matching item, or \b 0 if none, with the index
100 extern void *HashVector_next(HashVector *hv,VectorIndex *i);
103 * \brief Add the given item into the \ref HashVector, growing it as
104 * needed to ensure that its fill+holes is no more than half the size.
106 * \param hv is the \ref HashVector concerned.
108 * \param item is the item to add.
110 * \returns \b 1 when an item is added, \b 0 when the item key is
111 * already present, and \b -1 upon OOM or ovefull \ref HashVector.
113 * Note that this function first locates any item of the same key, and
114 * then doesn't add if there is already an item that has the same key.
116 * \related HashVector
118 extern int HashVector_add(HashVector *hv,void *item);
121 * \brief Delete the given item, and shrink the HashVector so that its
122 * size is at most double its fill, though at minimum a single index
123 * page corresponding to the \ref VectorVariant in use.
125 * \param hv is the \ref HashVector concerned.
127 * \param item is the item to delete.
129 * \returns \b 1 when the item gets deleted (by replacing its slot
130 * with a \ref HV_HOLE value), \b 0 if the HashVector has either no
131 * item or a different item for the item key, and \b -1 in case of OOM
132 * or overfull HashVector.
134 * Note that the contained item that has the same key as the provided
139 * \related HashVector
141 extern int HashVector_delete(HashVector *hv,void *item);
144 * \brief Copy content items into a given empty \ref Vector.
146 * \param hv is the \ref HashVector concerned.
148 * \param variant is the desired Vector variant.
150 * \param pv is the optional \ref Vector to copy the content into.
152 * \returns the \ref Vector with the \ref HashVector content
154 * If \pv is null, then a new Vector is allocated and handed out for
155 * the caller to reclaim unless the HashVector is empty in which case
156 * this function returns 0.
158 * If \b pv is not null, it is first cleared, and then populated with
159 * the content from the HashVector. The populated Vector is returned.
161 * \related HashVector
163 extern Vector *HashVector_contents(
164 HashVector *hv,enum VectorVariant variant,Vector *pv);
167 * \brief This is a utility function to compute and return a hashcode
168 * for a block of bytes.
170 * \param key is the start of the block.
172 * \param n is the Byte size of the block.
174 * \related HashVector
176 extern unsigned long HashVector_hashcode(unsigned char *key,unsigned long n);
179 * \brief Create a \ref HashVector of given \ref VectorVariant
180 * for given \ref ItemKeyFun.
182 * \param variant is the \ref VectorVariant to use.
184 * \param type is the \ref ItemKeyFun to use.
186 * \returns the initialised \ref HashVector.
188 * The HashVector will be initialized with a single \ref VectorPage.
190 * \note The \ref HashVector record is allocated with malloc and the
191 * caller is responsible for free-ing the memory block when it's no
194 * \related HashVector
196 extern HashVector *HashVector_create(
197 enum VectorVariant variant,ItemKeyFun *type);