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

   1 /*
   2  * Copyright 2012 GRNET S.A. All rights reserved.
   3  *
   4  * Redistribution and use in source and binary forms, with or
   5  * without modification, are permitted provided that the following
   6  * conditions are met:
   7  *
   8  *   1. Redistributions of source code must retain the above
   9  *      copyright notice, this list of conditions and the following
  10  *      disclaimer.
  11  *   2. Redistributions in binary form must reproduce the above
  12  *      copyright notice, this list of conditions and the following
  13  *      disclaimer in the documentation and/or other materials
  14  *      provided with the distribution.
  15  *
  16  * THIS SOFTWARE IS PROVIDED BY GRNET S.A. ``AS IS'' AND ANY EXPRESS
  17  * OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED
  18  * WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR
  19  * PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL GRNET S.A OR
  20  * CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
  21  * SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT
  22  * LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF
  23  * USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED
  24  * AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
  25  * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN
  26  * ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE
  27  * POSSIBILITY OF SUCH DAMAGE.
  28  *
  29  * The views and conclusions contained in the software and
  30  * documentation are those of the authors and should not be
  31  * interpreted as representing official policies, either expressed
  32  * or implied, of GRNET S.A.
  33  */
  34
  35 #ifndef __PHASH_H__
  36 #define __PHASH_H__
  37
  38 #ifndef __KERNEL__
  39 #include <stdbool.h>
  40 #endif
  41
  42 #include <sys/util.h>
  43 #include <xtypes/domain.h>
  44 /* based on:
  45  *
  46  * python hash for C
  47  *  originally by gtsouk@cslab.ece.ntua.gr
  48  *  -- kkourt@cslab.ece.ntua.gr
  49  */
  50
  51 typedef uint64_t xhashidx;
  52 #define Noxhashidx ((xhashidx) -1)
  53
  54 #define XHASH_ERESIZE 1
  55 #define XHASH_EEXIST 2
  56 #define XHASH_ENOSPC 3
  57
  58 enum xhash_type {
  59         INTEGER = 0,    /* signed/unsigned integers, pointers, etc */
  60         STRING = 1      /* NULL terminated strings */
  61         //OBJECT = 2, to be used later with objects
  62 };
  63 #define NR_XHASH_TYPES 2
  64
  65 struct xhash {
  66     xhashidx size_shift;
  67     xhashidx minsize_shift;
  68     xhashidx used;
  69     xhashidx dummies;
  70     xhashidx defval;
  71     xhashidx limit;
  72     enum xhash_type type;
  73 #ifdef PHASH_STATS
  74     xhashidx inserts;
  75     xhashidx deletes;
  76     xhashidx lookups;
  77     xhashidx bounces;
  78 #endif
  79     XPTR_TYPE(xhashidx) kvs;
  80 };
  81 typedef struct xhash xhash_t;
  82
  83 static inline xhashidx
  84 xhash_elements(xhash_t *xhash)
  85 {
  86     return xhash->used;
  87 }
  88
  89 static inline xhashidx
  90 xhash_size(xhash_t *xhash)
  91 {
  92     return 1UL<<(xhash->size_shift);
  93 }
  94
  95 static inline xhashidx *
  96 xhash_kvs(xhash_t *xhash)
  97 {
  98     return XPTR(&xhash->kvs);
  99 }
 100
 101 static inline xhashidx *
 102 xhash_vals(xhash_t *xhash)
 103 {
 104     return XPTR(&xhash->kvs) + xhash_size(xhash);
 105 }
 106
 107 #ifdef PHASH_STATS
 108 #define ZEROSTAT(stat) (stat) = 0
 109 #define INCSTAT(stat) (stat) ++
 110 #define DECSTAT(stat) (stat) --
 111 #define REPSTAT(stat)  fprintf(stderr, "" # stat  " = %lu \n" , stat)
 112 #else
 113 #define ZEROSTAT(stat)
 114 #define INCSTAT(stat)
 115 #define DECSTAT(stat)
 116 #define REPSTAT(stat)  do { } while (0)
 117 #endif
 118
 119 #define REPSTATS(x) do {     \
 120     REPSTAT(x->inserts); \
 121     REPSTAT(x->deletes); \
 122     REPSTAT(x->lookups); \
 123     REPSTAT(x->bounces); \
 124 } while (0)
 125
 126
 127
 128 /**
 129  * hash functions (dict)
 130  */
 131
 132 xhashidx xhash_grow_size_shift(xhash_t *xhash);
 133 xhashidx xhash_shrink_size_shift(xhash_t *xhash);
 134 ssize_t xhash_get_alloc_size(xhashidx size_shift);
 135
 136 xhash_t *xhash_new(xhashidx minsize_shift, xhashidx limit, enum xhash_type type);
 137 void xhash_free(xhash_t *xhash); // pairs with _new()
 138 void xhash_init(struct xhash *xhash, xhashidx minsize_shift, xhashidx limit,
 139                 enum xhash_type type);
 140
 141 xhash_t * xhash_resize(xhash_t *xhash, xhashidx new_size_shift,
 142                 xhashidx newlimit, xhash_t *newxhash);
 143 int xhash_insert(xhash_t *xhash, xhashidx key, xhashidx val);
 144 int xhash_update(xhash_t *xhash, xhashidx key, xhashidx val);
 145 int xhash_freql_update(xhash_t *xhash, xhashidx key, xhashidx val);
 146 int xhash_delete(struct xhash *xhash, xhashidx key);
 147 int xhash_lookup(xhash_t *xhash, xhashidx key, xhashidx *val);
 148
 149 struct xhash_iter {
 150     xhashidx   loc;  /* location on the array */
 151     xhashidx   cnt;  /* returned items */
 152 };
 153 typedef struct xhash_iter xhash_iter_t;
 154
 155 /* The iterators are read-only */
 156 void xhash_iter_init(xhash_t *xhash, xhash_iter_t *pi);
 157 int  xhash_iterate(xhash_t *xhash, xhash_iter_t *pi, xhashidx *key, xhashidx *val);
 158
 159 void xhash_print(xhash_t *xhash);
 160
 161 /* no set functionality for now */
 162 #if 0
 163 /**
 164  * set funtions
 165  */
 166 struct pset {
 167     xhash_t ph_;
 168 };
 169 typedef struct pset pset_t;
 170
 171 static inline xhashidx
 172 pset_elements(pset_t *pset)
 173 {
 174     return pset->ph_.used;
 175 }
 176
 177 static inline xhashidx
 178 pset_size(pset_t *pset)
 179 {
 180     return 1UL<<(pset->ph_.size_shift);
 181 }
 182
 183 pset_t *pset_new(xhashidx minsize_shift); // returns an initialized pset
 184 void pset_free(pset_t *pset); // goes with _new()
 185
 186 void pset_init(pset_t *pset, xhashidx minsize_shift);
 187 void pset_tfree(pset_t *pset); // goes with _init()
 188
 189 void pset_insert(pset_t *pset, xhashidx key);
 190 int pset_delete(pset_t *pset, xhashidx key);
 191 bool pset_lookup(pset_t *pset, xhashidx key);
 192 int pset_iterate(pset_t *pset, xhash_iter_t *pi, xhashidx *key);
 193 void pset_print(pset_t *pset);
 194
 195 typedef xhash_iter_t pset_iter_t;
 196
 197 static inline void
 198 pset_iter_init(pset_t *pset, pset_iter_t *pi)
 199 {
 200     xhash_iter_init(&pset->ph_, pi);
 201 }
 202
 203 #endif /* if 0 */
 204
 205 #endif
 206
 207 // vim:expandtab:tabstop=8:shiftwidth=4:softtabstop=4