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 {
  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 Find the keyed item.
  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 for th next key-matching item at or after the
  90  * given index.
  91  *
  92  * \param hv is the \ref HashVector concerned.
  93  *
  94  * \param index is a pointer to the index to advance.
  95  * \
  96  * \param key is the query key
  97  *
  98  * \returns the next matching item, or \b 0 if none, with the index
  99  * updated.
 100  *
 101  * \related HashVector
 102  */
 103 extern void *HashVector_next(HashVector *hv,VectorIndex *i,void *key);
 104
 105 /**
 106  * \brief Add the given item into the \ref HashVector, growing it as
 107  * needed to ensure that its fill+holes is no more than half the size.
 108  *
 109  * \param hv is the \ref HashVector concerned.
 110  *
 111  * \param item is the item to add.
 112  *
 113  * \returns \b 1 when an item is added, \b 0 when the item key is
 114  * already present, and \b -1 upon OOM or ovefull \ref HashVector.
 115  *
 116  * Note that this function first locates any item of the same key, and
 117  * then doesn't add if there is already an item that has the same key.
 118  *
 119  * \related HashVector
 120  */
 121 extern int HashVector_add(HashVector *hv,void *item);
 122
 123 /**
 124  * \brief Delete the given item, and shrink the HashVector so that its
 125  * size is at most double its fill, though at minimum a single index
 126  * page corresponding to the \ref VectorVariant in use.
 127  *
 128  * \param hv is the \ref HashVector concerned.
 129  *
 130  * \param item is the item to delete.
 131  *
 132  * \returns \b 1 when the item gets deleted (by replacing its slot
 133  * with a \ref HV_HOLE value), \b 0 if the HashVector has either no
 134  * item or a different item for the item key, and \b -1 in case of OOM
 135  * or overfull HashVector.
 136  *
 137  * Note that the contained item that has the same key as the provided
 138  * item is deleted.
 139  *
 140  * \see ItemKeyFun
 141  *
 142  * \related HashVector
 143  */
 144 extern int HashVector_delete(HashVector *hv,void *item);
 145
 146 /**
 147  * \brief Copy content items into a given empty \ref Vector.
 148  *
 149  * \param hv is the \ref HashVector concerned.
 150  *
 151  * \param variant is the desired Vector variant.
 152  *
 153  * \param pv is the optional \ref Vector to copy the content into.
 154  *
 155  * \returns the \ref Vector with the \ref HashVector content
 156  *
 157  * If \pv is null, then a new Vector is allocated and handed out for
 158  * the caller to reclaim unless the HashVector is empty in which case
 159  * this function returns 0.
 160  *
 161  * If \b pv is not null, it is first cleared, and then populated with
 162  * the content from the HashVector. The populated Vector is returned.
 163  *
 164  * \related HashVector
 165  */
 166 extern Vector *HashVector_contents(
 167     HashVector *hv,enum VectorVariant variant,Vector *pv);
 168
 169 /**
 170  * \brief This is a utility function to compute and return a hashcode
 171  * for a block of bytes.
 172  *
 173  * \param key is the start of the block.
 174  *
 175  * \param n is the Byte size of the block.
 176  *
 177  * \related HashVector
 178  */
 179 extern unsigned long HashVector_hashcode(unsigned char *key,unsigned long n);
 180
 181 /**
 182  * \brief Create a \ref HashVector of given \ref VectorVariant
 183  * for given \ref ItemKeyFun.
 184  *
 185  * \param variant is the \ref VectorVariant to use.
 186  *
 187  * \param type is the \ref ItemKeyFun to use.
 188  *
 189  * \returns the initialised \ref HashVector.
 190  *
 191  * The HashVector will be initialized with a single \ref VectorPage.
 192  *
 193  * \note The \ref HashVector record is allocated with malloc and the
 194  * caller is responsible for free-ing the memory block when it's no
 195  * longer needed.
 196  *
 197  * \related HashVector
 198  */
 199 extern HashVector *HashVector_create(
 200     enum VectorVariant variant,ItemKeyFun *type);
 201
 202 #endif