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