vector/HashVector.h

   1 #ifndef HashVector_H
   2 #define HashVector_H
   3
   4 #include <Vector.h>
   5 #include <ItemKeyFun.h>
   6
   7 /**
   8  * \file HashVector.h
   9  *
  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.
  17  *
  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.
  22  *
  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.
  27  */
  28
  29 /**
  30  * \struct HashVector
  31  *
  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.
  35  *
  36  * \extends Vector
  37  */
  38 typedef struct HashVector {
  39     /**
  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.
  43      */
  44     Vector table;        // the table space for items
  45     /**
  46      * This is the fill count, i.e., how many key-distinct items there
  47      * are in the backing Vector.
  48      */
  49     unsigned long fill;  // current number of contained items
  50     /**
  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.
  55      */
  56     unsigned long holes; // current number of slots marking deleted items
  57     /**
  58      * This is a pointer to the \ref ItemKeyFun record that provides
  59      * the key-and-payload abstraction for items.
  60      */
  61     ItemKeyFun *type;    // the key type for the items
  62 } HashVector;
  63
  64 /**
  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.
  70  *
  71  * \related HashVector
  72  */
  73 #define HV_HOLE ((void*) 1)
  74
  75 /**
  76  * \brief Lookup the first item with the given key.
  77  *
  78  * \param hv is the \ref HashVector concerned.
  79  *
  80  * \param key is the key to find.
  81  *
  82  * \returns the item if any or \b 0 if none.
  83  *
  84  * \related HashVector
  85  */
  86 void *HashVector_find(HashVector *hv,void *key);
  87
  88 /**
  89  * \brief Scan the table by index
  90  *
  91  * \param hv is the \ref HashVector concerned.
  92  *
  93  * \param index is a pointer to the index to advance.
  94  *
  95  * \returns the next matching item, or \b 0 if none, with the index
  96  * updated.
  97  *
  98  * \related HashVector
  99  */
 100 extern void *HashVector_next(HashVector *hv,VectorIndex *i);
 101
 102 /**
 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.
 105  *
 106  * \param hv is the \ref HashVector concerned.
 107  *
 108  * \param item is the item to add.
 109  *
 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.
 112  *
 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.
 115  *
 116  * \related HashVector
 117  */
 118 extern int HashVector_add(HashVector *hv,void *item);
 119
 120 /**
 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.
 124  *
 125  * \param hv is the \ref HashVector concerned.
 126  *
 127  * \param item is the item to delete.
 128  *
 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.
 133  *
 134  * Note that the contained item that has the same key as the provided
 135  * item is deleted.
 136  *
 137  * \see ItemKeyFun
 138  *
 139  * \related HashVector
 140  */
 141 extern int HashVector_delete(HashVector *hv,void *item);
 142
 143 /**
 144  * \brief Copy content items into a given empty \ref Vector.
 145  *
 146  * \param hv is the \ref HashVector concerned.
 147  *
 148  * \param variant is the desired Vector variant.
 149  *
 150  * \param pv is the optional \ref Vector to copy the content into.
 151  *
 152  * \returns the \ref Vector with the \ref HashVector content
 153  *
 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.
 157  *
 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.
 160  *
 161  * \related HashVector
 162  */
 163 extern Vector *HashVector_contents(
 164     HashVector *hv,enum VectorVariant variant,Vector *pv);
 165
 166 /**
 167  * \brief This is a utility function to compute and return a hashcode
 168  * for a block of bytes.
 169  *
 170  * \param key is the start of the block.
 171  *
 172  * \param n is the Byte size of the block.
 173  *
 174  * \related HashVector
 175  */
 176 extern unsigned long HashVector_hashcode(unsigned char *key,unsigned long n);
 177
 178 /**
 179  * \brief Create a \ref HashVector of given \ref VectorVariant
 180  * for given \ref ItemKeyFun.
 181  *
 182  * \param variant is the \ref VectorVariant to use.
 183  *
 184  * \param type is the \ref ItemKeyFun to use.
 185  *
 186  * \returns the initialised \ref HashVector.
 187  *
 188  * The HashVector will be initialized with a single \ref VectorPage.
 189  *
 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
 192  * longer needed.
 193  *
 194  * \related HashVector
 195  */
 196 extern HashVector *HashVector_create(
 197     enum VectorVariant variant,ItemKeyFun *type);
 198
 199 #endif