code.grnet.gr Git - archipelago/blob - xseg/xtypes/xhash.h

   1 #ifndef __PHASH_H__
   2 #define __PHASH_H__
   3
   4 #ifndef __KERNEL__
   5 #include <stdbool.h>
   6 #endif
   7
   8 #include <sys/util.h>
   9 #include <xtypes/domain.h>
  10 /* based on:
  11  *
  12  * python hash for C
  13  *  originally by gtsouk@cslab.ece.ntua.gr
  14  *  -- kkourt@cslab.ece.ntua.gr
  15  */
  16
  17 typedef unsigned long ul_t;
  18
  19 #define XHASH_ERESIZE 1
  20 #define XHASH_EEXIST 2
  21
  22 struct xhash {
  23     ul_t size_shift;
  24     ul_t minsize_shift;
  25     ul_t used;
  26     ul_t dummies;
  27     ul_t defval;
  28 #ifdef PHASH_STATS
  29     ul_t inserts;
  30     ul_t deletes;
  31     ul_t lookups;
  32     ul_t bounces;
  33 #endif
  34     XPTR_TYPE(ul_t) kvs;
  35 };
  36 typedef struct xhash xhash_t;
  37
  38 static inline ul_t
  39 xhash_elements(xhash_t *xhash)
  40 {
  41     return xhash->used;
  42 }
  43
  44 static inline ul_t
  45 xhash_size(xhash_t *xhash)
  46 {
  47     return 1UL<<(xhash->size_shift);
  48 }
  49
  50 static inline ul_t *
  51 xhash_kvs(xhash_t *xhash)
  52 {
  53     return XPTR(&xhash->kvs);
  54 }
  55
  56 static inline ul_t *
  57 xhash_vals(xhash_t *xhash)
  58 {
  59     return XPTR(&xhash->kvs) + xhash_size(xhash);
  60 }
  61
  62 #ifdef PHASH_STATS
  63 #define ZEROSTAT(stat) (stat) = 0
  64 #define INCSTAT(stat) (stat) ++
  65 #define DECSTAT(stat) (stat) --
  66 #define REPSTAT(stat)  fprintf(stderr, "" # stat  " = %lu \n" , stat)
  67 #else
  68 #define ZEROSTAT(stat)
  69 #define INCSTAT(stat)
  70 #define DECSTAT(stat)
  71 #define REPSTAT(stat)  do { } while (0)
  72 #endif
  73
  74 #define REPSTATS(x) do {     \
  75     REPSTAT(x->inserts); \
  76     REPSTAT(x->deletes); \
  77     REPSTAT(x->lookups); \
  78     REPSTAT(x->bounces); \
  79 } while (0)
  80
  81
  82
  83 /**
  84  * hash functions (dict)
  85  */
  86
  87 ul_t grow_size_shift(xhash_t *xhash);
  88 ul_t shrink_size_shift(xhash_t *xhash);
  89 ssize_t xhash_get_alloc_size(ul_t size_shift);
  90
  91 xhash_t *xhash_new(ul_t minsize_shift);
  92 void xhash_free(xhash_t *xhash); // pairs with _new()
  93 void xhash_init(struct xhash *xhash, ul_t minsize_shift);
  94
  95 int xhash_resize(xhash_t *xhash, ul_t new_size_shift, xhash_t *newxhash);
  96 int xhash_insert(xhash_t *xhash, ul_t key, ul_t val);
  97 int xhash_update(xhash_t *xhash, ul_t key, ul_t val);
  98 int xhash_freql_update(xhash_t *xhash, ul_t key, ul_t val);
  99 int xhash_delete(struct xhash *xhash, ul_t key);
 100 int xhash_lookup(xhash_t *xhash, ul_t key, ul_t *val);
 101
 102 struct xhash_iter {
 103     ul_t   loc;  /* location on the array */
 104     ul_t   cnt;  /* returned items */
 105 };
 106 typedef struct xhash_iter xhash_iter_t;
 107
 108 /* The iterators are read-only */
 109 void xhash_iter_init(xhash_t *xhash, xhash_iter_t *pi);
 110 int  xhash_iterate(xhash_t *xhash, xhash_iter_t *pi, ul_t *key, ul_t *val);
 111
 112 void xhash_print(xhash_t *xhash);
 113
 114 /* no set functionality for now */
 115 #if 0
 116 /**
 117  * set funtions
 118  */
 119 struct pset {
 120     xhash_t ph_;
 121 };
 122 typedef struct pset pset_t;
 123
 124 static inline ul_t
 125 pset_elements(pset_t *pset)
 126 {
 127     return pset->ph_.used;
 128 }
 129
 130 static inline ul_t
 131 pset_size(pset_t *pset)
 132 {
 133     return 1UL<<(pset->ph_.size_shift);
 134 }
 135
 136 pset_t *pset_new(ul_t minsize_shift); // returns an initialized pset
 137 void pset_free(pset_t *pset); // goes with _new()
 138
 139 void pset_init(pset_t *pset, ul_t minsize_shift);
 140 void pset_tfree(pset_t *pset); // goes with _init()
 141
 142 void pset_insert(pset_t *pset, ul_t key);
 143 int pset_delete(pset_t *pset, ul_t key);
 144 bool pset_lookup(pset_t *pset, ul_t key);
 145 int pset_iterate(pset_t *pset, xhash_iter_t *pi, ul_t *key);
 146 void pset_print(pset_t *pset);
 147
 148 typedef xhash_iter_t pset_iter_t;
 149
 150 static inline void
 151 pset_iter_init(pset_t *pset, pset_iter_t *pi)
 152 {
 153     xhash_iter_init(&pset->ph_, pi);
 154 }
 155
 156 #endif /* if 0 */
 157
 158 #endif
 159
 160 // vim:expandtab:tabstop=8:shiftwidth=4:softtabstop=4