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 next keyed item at or after the given index.
  77  *
  78  * \param hv is the \ref hashvector concerned.
  79  *
  80  * \param index is a pointer to the index to advance.
  81  * \
  82  * \param key is the query key
  83  *
  84  * \returns the next matching item, or \b 0 if none, with the index
  85  * updated.
  86  *
  87  * \related hashvector
  88  */
  89 extern void *hashvector_next(hashvector *hv,vector_index *i,void *key);
  90
  91 /**
  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.
  94  *
  95  * \param hv is the \ref hashvector concerned.
  96  *
  97  * \param item is the item to add.
  98  *
  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.
 101  *
 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.
 104  *
 105  * \related hashvector
 106  */
 107 extern int hashvector_add(hashvector *hv,void *item);
 108
 109 /**
 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.
 113  *
 114  * \param hv is the \ref hashvector concerned.
 115  *
 116  * \param item is the item to delete.
 117  *
 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.
 122  *
 123  * Note that the contained item that has the same key as the provided
 124  * item is deleted.
 125  *
 126  * \see itemkeyfun
 127  *
 128  * \related hashvector
 129  */
 130 extern int hashvector_delete(hashvector *hv,void *item);
 131
 132 /**
 133  * \brief Copy content items into a given empty \ref vector.
 134  *
 135  * \param hv is the \ref hashvector concerned.
 136  *
 137  * \param pv is the \ref vector to copy the content into.
 138  *
 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
 142  * \ref vector.
 143  *
 144  * \related hashvector
 145  */
 146 extern int hashvector_contents(hashvector *hv,vector *pv);
 147
 148 /**
 149  * \brief This is a utility function to compute and return a hashcode
 150  * for a block of bytes.
 151  *
 152  * \param key is the start of the block.
 153  *
 154  * \param n is the byte size of the block.
 155  *
 156  * \related hashvector
 157  */
 158 extern unsigned long hashvector_hashcode(unsigned char *key,unsigned long n);
 159
 160 /**
 161  * \brief Create a \ref hashvector of given \ref vector_variant
 162  * for given \ref itemkeyfun.
 163  *
 164  * \param variant is the \ref vector_variant to use.
 165  *
 166  * \param type is the \ref itemkeyfun to use.
 167  *
 168  * \returns the initialised \ref hashvector.
 169  *
 170  * The hashvector will be initialized with a single \ref vector_page.
 171  *
 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
 174  * longer needed.
 175  */
 176 extern hashvector *hashvector_create(
 177     enum vector_variant variant,itemkeyfun *type);
 178
 179 #endif