pvector/hashvector.h

   1 #ifndef hashvector_H
   2 #define hashvector_H
   3
   4 /**
   5  * hashvector is a use of pvector as a hashtable. The hashvector
   6  * includes three functions to, respectively, obtain the hashcode of a
   7  * given key, to obtain the key of a given item, and to tell whether
   8  * or not a given item has a given key. The hashvector manipulations
   9  * uses those for locating and placing items into the vector; the
  10  * hascode is the primary place for an item, but then scanning upwards
  11  * with a rolling index in case of collisions.
  12  *
  13  * The vector holds 0 pointers for free slots, (void*)1 pointers (aka
  14  * HV_HOLE) to indicate slots of deleted items, and otherwise item
  15  * pointers. Thus, deleting an item results in av HV_HOLE et the
  16  * item's slot.
  17  *
  18  * The hashvector grows to double in size, with rehashing, when the
  19  * sum of items and holes exceeds 50% fill, and it shrinks to half
  20  * size when item numbers reduces below 50%.
  21  */
  22
  23 #include "pvector.h"
  24
  25 /*!
  26  * Type: hashvector
  27  * This combines a pvector (for contents) with fill and hole counters
  28  * and the three functions.
  29  */
  30 typedef struct _hashvector {
  31     pvector table;
  32     unsigned long fill;                   // number of added elements
  33     unsigned long holes;                  // number of deleted
  34     unsigned long (*keyhashcode)(void *key); // The hashcode of a key
  35     void *(*itemkey)(void *item);        // the key of ain item
  36     int (*haskey)(void *item,void *key); // whether an item has a given
  37 } hashvector;
  38
  39 /*!
  40  * Macro: HV_HOLE
  41  * The representation of a deleted item.
  42  */
  43 #define HV_HOLE ((void*) 1)
  44
  45 /*!
  46  * Function: int hashvector_find(hashvector *hv,void *key,void **x)
  47  *
  48  * Find the item, if any, with the given key and assign *x with its
  49  * address. Returns 1 on success and 0 on failure to find the keyed
  50  * item. Note that when the function returns 0, *x is unchanged.
  51  */
  52 int hashvector_find(hashvector *hv,void *key,void **x);
  53
  54 /*!
  55  * Function: void hashvector_add(hashvector *hv,void *item)
  56  *
  57  * Add the given item into the hashvector, growing the hashvector as
  58  * needed to ensure that its fill+holes is is no more than half the
  59  * size. Note that this function first locates any item of the same
  60  * key, and then doesn't add if there is already an item that has the
  61  * same key. Returns 1 when an item is added, 0 when the item key
  62  * is already present, and -1 upon OOM or ovefull hashvector.
  63  */
  64 int hashvector_add(hashvector *hv,void *item);
  65
  66 /*!
  67  * Function: void hashvector_delete(hashvector *hv,void *item)
  68  *
  69  * Delete the given item, and shrink the hashvector so that its size
  70  * is at most double its fill, though at least 256 slots. Returns 1
  71  * when the item gets deleted (by replacing its slot with a HV_HOLE
  72  * value, 0 if the hashvector has either no item or a different item
  73  * for the item key, and -1 in case of OOM or overfull hashvector.
  74  */
  75 int hashvector_delete(hashvector *hv,void *item);
  76
  77 /*!
  78  * Function: int hashvector_contents(hashvector *hv,pvector *pv)
  79  *
  80  * Copy content items into a pvector, which must be empty. The
  81  * function returns -1 if the resizing of the pvector to the
  82  * hashvector fill fails, otherwise 0 after having copied the
  83  * hashvector items in their internal order of appearance into the
  84  * pvector.
  85  */
  86 int hashvector_contents(hashvector *hv,pvector *pv);
  87
  88 /*!
  89  * Function unsigned long hashvector_hashcode(
  90  *              unsigned char *key,unsigned long n)
  91  *
  92  * Computes and returns a hashcode for a block of bytes.
  93  */
  94 unsigned long hashvector_hashcode(unsigned char *key,unsigned long n);
  95
  96 #endif