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 uint64_t xhashidx;
  18 #define Noxhashidx ((xhashidx) -1)
  19
  20 #define XHASH_ERESIZE 1
  21 #define XHASH_EEXIST 2
  22
  23 enum xhash_type {
  24         INTEGER = 0,    /* signed/unsigned integers, pointers, etc */
  25         STRING = 1      /* NULL terminated strings */
  26         //OBJECT = 2, to be used later with objects
  27 };
  28 #define NR_XHASH_TYPES 2
  29
  30 struct xhash {
  31     xhashidx size_shift;
  32     xhashidx minsize_shift;
  33     xhashidx used;
  34     xhashidx dummies;
  35     xhashidx defval;
  36     enum xhash_type type;
  37 #ifdef PHASH_STATS
  38     xhashidx inserts;
  39     xhashidx deletes;
  40     xhashidx lookups;
  41     xhashidx bounces;
  42 #endif
  43     XPTR_TYPE(xhashidx) kvs;
  44 };
  45 typedef struct xhash xhash_t;
  46
  47 static inline xhashidx
  48 xhash_elements(xhash_t *xhash)
  49 {
  50     return xhash->used;
  51 }
  52
  53 static inline xhashidx
  54 xhash_size(xhash_t *xhash)
  55 {
  56     return 1UL<<(xhash->size_shift);
  57 }
  58
  59 static inline xhashidx *
  60 xhash_kvs(xhash_t *xhash)
  61 {
  62     return XPTR(&xhash->kvs);
  63 }
  64
  65 static inline xhashidx *
  66 xhash_vals(xhash_t *xhash)
  67 {
  68     return XPTR(&xhash->kvs) + xhash_size(xhash);
  69 }
  70
  71 #ifdef PHASH_STATS
  72 #define ZEROSTAT(stat) (stat) = 0
  73 #define INCSTAT(stat) (stat) ++
  74 #define DECSTAT(stat) (stat) --
  75 #define REPSTAT(stat)  fprintf(stderr, "" # stat  " = %lu \n" , stat)
  76 #else
  77 #define ZEROSTAT(stat)
  78 #define INCSTAT(stat)
  79 #define DECSTAT(stat)
  80 #define REPSTAT(stat)  do { } while (0)
  81 #endif
  82
  83 #define REPSTATS(x) do {     \
  84     REPSTAT(x->inserts); \
  85     REPSTAT(x->deletes); \
  86     REPSTAT(x->lookups); \
  87     REPSTAT(x->bounces); \
  88 } while (0)
  89
  90
  91
  92 /**
  93  * hash functions (dict)
  94  */
  95
  96 xhashidx xhash_grow_size_shift(xhash_t *xhash);
  97 xhashidx xhash_shrink_size_shift(xhash_t *xhash);
  98 ssize_t xhash_get_alloc_size(xhashidx size_shift);
  99
 100 xhash_t *xhash_new(xhashidx minsize_shift, enum xhash_type type);
 101 void xhash_free(xhash_t *xhash); // pairs with _new()
 102 void xhash_init(struct xhash *xhash, xhashidx minsize_shift, enum xhash_type type);
 103
 104 xhash_t * xhash_resize(xhash_t *xhash, xhashidx new_size_shift, xhash_t *newxhash);
 105 int xhash_insert(xhash_t *xhash, xhashidx key, xhashidx val);
 106 int xhash_update(xhash_t *xhash, xhashidx key, xhashidx val);
 107 int xhash_freql_update(xhash_t *xhash, xhashidx key, xhashidx val);
 108 int xhash_delete(struct xhash *xhash, xhashidx key);
 109 int xhash_lookup(xhash_t *xhash, xhashidx key, xhashidx *val);
 110
 111 struct xhash_iter {
 112     xhashidx   loc;  /* location on the array */
 113     xhashidx   cnt;  /* returned items */
 114 };
 115 typedef struct xhash_iter xhash_iter_t;
 116
 117 /* The iterators are read-only */
 118 void xhash_iter_init(xhash_t *xhash, xhash_iter_t *pi);
 119 int  xhash_iterate(xhash_t *xhash, xhash_iter_t *pi, xhashidx *key, xhashidx *val);
 120
 121 void xhash_print(xhash_t *xhash);
 122
 123 /* no set functionality for now */
 124 #if 0
 125 /**
 126  * set funtions
 127  */
 128 struct pset {
 129     xhash_t ph_;
 130 };
 131 typedef struct pset pset_t;
 132
 133 static inline xhashidx
 134 pset_elements(pset_t *pset)
 135 {
 136     return pset->ph_.used;
 137 }
 138
 139 static inline xhashidx
 140 pset_size(pset_t *pset)
 141 {
 142     return 1UL<<(pset->ph_.size_shift);
 143 }
 144
 145 pset_t *pset_new(xhashidx minsize_shift); // returns an initialized pset
 146 void pset_free(pset_t *pset); // goes with _new()
 147
 148 void pset_init(pset_t *pset, xhashidx minsize_shift);
 149 void pset_tfree(pset_t *pset); // goes with _init()
 150
 151 void pset_insert(pset_t *pset, xhashidx key);
 152 int pset_delete(pset_t *pset, xhashidx key);
 153 bool pset_lookup(pset_t *pset, xhashidx key);
 154 int pset_iterate(pset_t *pset, xhash_iter_t *pi, xhashidx *key);
 155 void pset_print(pset_t *pset);
 156
 157 typedef xhash_iter_t pset_iter_t;
 158
 159 static inline void
 160 pset_iter_init(pset_t *pset, pset_iter_t *pi)
 161 {
 162     xhash_iter_init(&pset->ph_, pi);
 163 }
 164
 165 #endif /* if 0 */
 166
 167 #endif
 168
 169 // vim:expandtab:tabstop=8:shiftwidth=4:softtabstop=4