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 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 0 pointers for free slots, (void*)1 pointers (aka
  19  * HV_HOLE) to indicate slots of deleted items, and otherwise item
  20  * pointers. Thus, deleting an item results in av HV_HOLE et the
  21  * 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 vector (for contents) with fill and hole
  33  * counters, and itemkeyfun callback functions for abstracting items
  34  * as being pairs of key and payload.
  35  * \extends vector
  36  */
  37 typedef struct {
  38     /**
  39      * This is the backing vector for the hashvector. Items are placed
  40      * in the vector by means of their key hashcodes, at the first
  41      * unused slot cyclically after the hashcode index.
  42      */
  43     vector table;        // the table space for items
  44     /**
  45      * This is the fill count, i.e., how many key-distinct items there
  46      * are in the backing vector.
  47      */
  48     unsigned long fill;  // current number of contained items
  49     /**
  50      * This is a count of HV_HOLE markers in the backing vector, which
  51      * hold the position of deleted items so as to not break the
  52      * lookup sequence for items placed cyclically after their
  53      * hashcode index due to hash collisions.
  54      */
  55     unsigned long holes; // current number of slots marking deleted items
  56     /**
  57      * This is a pointer to the itemkeyfun record that provides the
  58      * key-and-payload abstraction for items.
  59      */
  60     itemkeyfun *type;    // the key type for the items
  61 } hashvector;
  62
  63 /**
  64  * HV_HOLE is the representation of a deleted item. This supports the
  65  * hashtable algoritm where hashcode collisions are resolved by
  66  * placing later items compactly cyclically after their hashcode
  67  * index. When an item is removed from the table, its slot is set as a
  68  * HV_HOLE slot instead of being cleared.
  69  *
  70  * \related hashvector
  71  */
  72 #define HV_HOLE ((void*) 1)
  73
  74 /**
  75  * \brief Find next keyed item at or after the given index.
  76  * \param hv is the hasvector concerned
  77  * \param index is a pointer to the index to advance
  78  * \param key is the query key
  79  * \returns the next matching item, or 0 if none, with the index updated.
  80  *
  81  * \related hashvector
  82  */
  83 extern void *hashvector_next(hashvector *hv,vector_index *i,void *key);
  84
  85 /**
  86  * Add the given item into the hashvector, growing the hashvector as
  87  * needed to ensure that its fill+holes is is no more than half the
  88  * size. Note that this function first locates any item of the same
  89  * key, and then doesn't add if there is already an item that has the
  90  * same key. Returns 1 when an item is added, 0 when the item key
  91  * is already present, and -1 upon OOM or ovefull hashvector.
  92  *
  93  * \related hashvector
  94  */
  95 extern int hashvector_add(hashvector *hv,void *item);
  96
  97 /**
  98  * Delete the given item, and shrink the hashvector so that its size
  99  * is at most double its fill, though at least 256 slots. Returns 1
 100  * when the item gets deleted (by replacing its slot with a HV_HOLE
 101  * value, 0 if the hashvector has either no item or a different item
 102  * for the item key, and -1 in case of OOM or overfull hashvector.
 103  *
 104  * \related hashvector
 105  */
 106 extern int hashvector_delete(hashvector *hv,void *item);
 107
 108 /**
 109  * Copy content items into a vector, which must be empty. The
 110  * function returns -1 if the resizing of the vector to the
 111  * hashvector fill fails, otherwise 0 after having copied the
 112  * hashvector items in their internal order of appearance into the
 113  * vector.
 114  *
 115  * \related hashvector
 116  */
 117 extern int hashvector_contents(hashvector *hv,vector *pv);
 118
 119 /**
 120  * This is a utility function to compute and return a hashcode for a
 121  * block of bytes.
 122  *
 123  * \related hashvector
 124  */
 125 extern unsigned long hashvector_hashcode(unsigned char *key,unsigned long n);
 126
 127 /**
 128  * Create a hashvector for of given variant for given itemkeyfun*
 129  */
 130 extern hashvector *hashvector_create(
 131     enum vector_variant variant,itemkeyfun *type);
 132
 133 #endif