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

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