third-party/mruby/include/mruby/khash.h

   1 /**
   2 ** @file mruby/khash.h - Hash for mruby
   3 **
   4 ** See Copyright Notice in mruby.h
   5 */
   6
   7 #ifndef MRUBY_KHASH_H
   8 #define MRUBY_KHASH_H
   9
  10 #include <string.h>
  11
  12 #include <mruby.h>
  13 #include "common.h"
  14
  15 /**
  16  * khash definitions used in mruby's hash table.
  17  */
  18 MRB_BEGIN_DECL
  19
  20 typedef uint32_t khint_t;
  21 typedef khint_t khiter_t;
  22
  23 #ifndef KHASH_DEFAULT_SIZE
  24 # define KHASH_DEFAULT_SIZE 32
  25 #endif
  26 #define KHASH_MIN_SIZE 8
  27
  28 #define UPPER_BOUND(x) ((x)>>2|(x)>>1)
  29
  30 /* extern uint8_t __m[]; */
  31
  32 /* mask for flags */
  33 static const uint8_t __m_empty[]  = {0x02, 0x08, 0x20, 0x80};
  34 static const uint8_t __m_del[]    = {0x01, 0x04, 0x10, 0x40};
  35 static const uint8_t __m_either[] = {0x03, 0x0c, 0x30, 0xc0};
  36
  37
  38 #define __ac_isempty(ed_flag, i) (ed_flag[(i)/4]&__m_empty[(i)%4])
  39 #define __ac_isdel(ed_flag, i) (ed_flag[(i)/4]&__m_del[(i)%4])
  40 #define __ac_iseither(ed_flag, i) (ed_flag[(i)/4]&__m_either[(i)%4])
  41 #define khash_power2(v) do { \
  42   v--;\
  43   v |= v >> 1;\
  44   v |= v >> 2;\
  45   v |= v >> 4;\
  46   v |= v >> 8;\
  47   v |= v >> 16;\
  48   v++;\
  49 } while (0)
  50 #define khash_mask(h) ((h)->n_buckets-1)
  51 #define khash_upper_bound(h) (UPPER_BOUND((h)->n_buckets))
  52
  53 /* declare struct kh_xxx and kh_xxx_funcs
  54
  55    name: hash name
  56    khkey_t: key data type
  57    khval_t: value data type
  58    kh_is_map: (0: hash set / 1: hash map)
  59 */
  60 #define KHASH_DECLARE(name, khkey_t, khval_t, kh_is_map)                \
  61   typedef struct kh_##name {                                            \
  62     khint_t n_buckets;                                                  \
  63     khint_t size;                                                       \
  64     khint_t n_occupied;                                                 \
  65     uint8_t *ed_flags;                                                  \
  66     khkey_t *keys;                                                      \
  67     khval_t *vals;                                                      \
  68   } kh_##name##_t;                                                      \
  69   void kh_alloc_##name(mrb_state *mrb, kh_##name##_t *h);               \
  70   kh_##name##_t *kh_init_##name##_size(mrb_state *mrb, khint_t size);   \
  71   kh_##name##_t *kh_init_##name(mrb_state *mrb);                        \
  72   void kh_destroy_##name(mrb_state *mrb, kh_##name##_t *h);             \
  73   void kh_clear_##name(mrb_state *mrb, kh_##name##_t *h);               \
  74   khint_t kh_get_##name(mrb_state *mrb, kh_##name##_t *h, khkey_t key);           \
  75   khint_t kh_put_##name(mrb_state *mrb, kh_##name##_t *h, khkey_t key, int *ret); \
  76   void kh_put_prepare_##name(mrb_state *mrb, kh_##name##_t *h);                   \
  77   void kh_resize_##name(mrb_state *mrb, kh_##name##_t *h, khint_t new_n_buckets); \
  78   void kh_del_##name(mrb_state *mrb, kh_##name##_t *h, khint_t x);                \
  79   kh_##name##_t *kh_copy_##name(mrb_state *mrb, kh_##name##_t *h);
  80
  81 static inline void
  82 kh_fill_flags(uint8_t *p, uint8_t c, size_t len)
  83 {
  84   while (len-- > 0) {
  85     *p++ = c;
  86   }
  87 }
  88
  89 /* define kh_xxx_funcs
  90
  91    name: hash name
  92    khkey_t: key data type
  93    khval_t: value data type
  94    kh_is_map: (0: hash set / 1: hash map)
  95    __hash_func: hash function
  96    __hash_equal: hash comparation function
  97 */
  98 #define KHASH_DEFINE(name, khkey_t, khval_t, kh_is_map, __hash_func, __hash_equal) \
  99   mrb_noreturn void mrb_raise_nomemory(mrb_state *mrb);                 \
 100   int kh_alloc_simple_##name(mrb_state *mrb, kh_##name##_t *h)          \
 101   {                                                                     \
 102     khint_t sz = h->n_buckets;                                          \
 103     size_t len = sizeof(khkey_t) + (kh_is_map ? sizeof(khval_t) : 0);   \
 104     uint8_t *p = (uint8_t*)mrb_malloc_simple(mrb, sizeof(uint8_t)*sz/4+len*sz); \
 105     if (!p) { return 1; }                                               \
 106     h->size = h->n_occupied = 0;                                        \
 107     h->keys = (khkey_t *)p;                                             \
 108     h->vals = kh_is_map ? (khval_t *)(p+sizeof(khkey_t)*sz) : NULL;     \
 109     h->ed_flags = p+len*sz;                                             \
 110     kh_fill_flags(h->ed_flags, 0xaa, sz/4);                             \
 111     return 0;                                                           \
 112   }                                                                     \
 113   void kh_alloc_##name(mrb_state *mrb, kh_##name##_t *h)                \
 114   {                                                                     \
 115     if (kh_alloc_simple_##name(mrb, h)) {                               \
 116       mrb_raise_nomemory(mrb);                                          \
 117     }                                                                   \
 118   }                                                                     \
 119   kh_##name##_t *kh_init_##name##_size(mrb_state *mrb, khint_t size) {  \
 120     kh_##name##_t *h = (kh_##name##_t*)mrb_calloc(mrb, 1, sizeof(kh_##name##_t)); \
 121     if (size < KHASH_MIN_SIZE)                                          \
 122       size = KHASH_MIN_SIZE;                                            \
 123     khash_power2(size);                                                 \
 124     h->n_buckets = size;                                                \
 125     if (kh_alloc_simple_##name(mrb, h)) {                               \
 126       mrb_free(mrb, h);                                                 \
 127       mrb_raise_nomemory(mrb);                                          \
 128     }                                                                   \
 129     return h;                                                           \
 130   }                                                                     \
 131   kh_##name##_t *kh_init_##name(mrb_state *mrb) {                       \
 132     return kh_init_##name##_size(mrb, KHASH_DEFAULT_SIZE);              \
 133   }                                                                     \
 134   void kh_destroy_##name(mrb_state *mrb, kh_##name##_t *h)              \
 135   {                                                                     \
 136     if (h) {                                                            \
 137       mrb_free(mrb, h->keys);                                           \
 138       mrb_free(mrb, h);                                                 \
 139     }                                                                   \
 140   }                                                                     \
 141   void kh_clear_##name(mrb_state *mrb, kh_##name##_t *h)                \
 142   {                                                                     \
 143     (void)mrb;                                                          \
 144     if (h && h->ed_flags) {                                             \
 145       kh_fill_flags(h->ed_flags, 0xaa, h->n_buckets/4);                 \
 146       h->size = h->n_occupied = 0;                                      \
 147     }                                                                   \
 148   }                                                                     \
 149   khint_t kh_get_##name(mrb_state *mrb, kh_##name##_t *h, khkey_t key)  \
 150   {                                                                     \
 151     khint_t k = __hash_func(mrb,key) & khash_mask(h), step = 0;         \
 152     (void)mrb;                                                          \
 153     while (!__ac_isempty(h->ed_flags, k)) {                             \
 154       if (!__ac_isdel(h->ed_flags, k)) {                                \
 155         if (__hash_equal(mrb,h->keys[k], key)) return k;                \
 156       }                                                                 \
 157       k = (k+(++step)) & khash_mask(h);                                 \
 158     }                                                                   \
 159     return kh_end(h);                                                   \
 160   }                                                                     \
 161   void kh_resize_##name(mrb_state *mrb, kh_##name##_t *h, khint_t new_n_buckets) \
 162   {                                                                     \
 163     if (new_n_buckets < KHASH_MIN_SIZE)                                 \
 164       new_n_buckets = KHASH_MIN_SIZE;                                   \
 165     khash_power2(new_n_buckets);                                        \
 166     {                                                                   \
 167       kh_##name##_t hh;                                                 \
 168       uint8_t *old_ed_flags = h->ed_flags;                              \
 169       khkey_t *old_keys = h->keys;                                      \
 170       khval_t *old_vals = h->vals;                                      \
 171       khint_t old_n_buckets = h->n_buckets;                             \
 172       khint_t i;                                                        \
 173       hh.n_buckets = new_n_buckets;                                     \
 174       kh_alloc_##name(mrb, &hh);                                        \
 175       /* relocate */                                                    \
 176       for (i=0 ; i<old_n_buckets ; i++) {                               \
 177         if (!__ac_iseither(old_ed_flags, i)) {                          \
 178           khint_t k = kh_put_##name(mrb, &hh, old_keys[i], NULL);       \
 179           if (kh_is_map) kh_value(&hh,k) = old_vals[i];                 \
 180         }                                                               \
 181       }                                                                 \
 182       /* copy hh to h */                                                \
 183       *h = hh;                                                          \
 184       mrb_free(mrb, old_keys);                                          \
 185     }                                                                   \
 186   }                                                                     \
 187   void kh_put_prepare_##name(mrb_state *mrb, kh_##name##_t *h)          \
 188   {                                                                     \
 189     if (h->n_occupied >= khash_upper_bound(h)) {                        \
 190       kh_resize_##name(mrb, h, h->n_buckets*2);                         \
 191     }                                                                   \
 192   }                                                                     \
 193   khint_t kh_put_##name(mrb_state *mrb, kh_##name##_t *h, khkey_t key, int *ret) \
 194   {                                                                     \
 195     khint_t k, del_k, step = 0;                                         \
 196     kh_put_prepare_##name(mrb, h);                                      \
 197     k = __hash_func(mrb,key) & khash_mask(h);                           \
 198     del_k = kh_end(h);                                                  \
 199     while (!__ac_isempty(h->ed_flags, k)) {                             \
 200       if (!__ac_isdel(h->ed_flags, k)) {                                \
 201         if (__hash_equal(mrb,h->keys[k], key)) {                        \
 202           if (ret) *ret = 0;                                            \
 203           return k;                                                     \
 204         }                                                               \
 205       }                                                                 \
 206       else if (del_k == kh_end(h)) {                                    \
 207         del_k = k;                                                      \
 208       }                                                                 \
 209       k = (k+(++step)) & khash_mask(h);                                 \
 210     }                                                                   \
 211     if (del_k != kh_end(h)) {                                           \
 212       /* put at del */                                                  \
 213       h->keys[del_k] = key;                                             \
 214       h->ed_flags[del_k/4] &= ~__m_del[del_k%4];                        \
 215       h->size++;                                                        \
 216       if (ret) *ret = 2;                                                \
 217       return del_k;                                                     \
 218     }                                                                   \
 219     else {                                                              \
 220       /* put at empty */                                                \
 221       h->keys[k] = key;                                                 \
 222       h->ed_flags[k/4] &= ~__m_empty[k%4];                              \
 223       h->size++;                                                        \
 224       h->n_occupied++;                                                  \
 225       if (ret) *ret = 1;                                                \
 226       return k;                                                         \
 227     }                                                                   \
 228   }                                                                     \
 229   void kh_del_##name(mrb_state *mrb, kh_##name##_t *h, khint_t x)       \
 230   {                                                                     \
 231     (void)mrb;                                                          \
 232     mrb_assert(x != h->n_buckets && !__ac_iseither(h->ed_flags, x));    \
 233     h->ed_flags[x/4] |= __m_del[x%4];                                   \
 234     h->size--;                                                          \
 235   }                                                                     \
 236   kh_##name##_t *kh_copy_##name(mrb_state *mrb, kh_##name##_t *h)       \
 237   {                                                                     \
 238     kh_##name##_t *h2;                                                  \
 239     khiter_t k, k2;                                                     \
 240                                                                         \
 241     h2 = kh_init_##name(mrb);                                           \
 242     for (k = kh_begin(h); k != kh_end(h); k++) {                        \
 243       if (kh_exist(h, k)) {                                             \
 244         k2 = kh_put_##name(mrb, h2, kh_key(h, k), NULL);                \
 245         if (kh_is_map) kh_value(h2, k2) = kh_value(h, k);               \
 246       }                                                                 \
 247     }                                                                   \
 248     return h2;                                                          \
 249   }
 250
 251
 252 #define khash_t(name) kh_##name##_t
 253
 254 #define kh_init_size(name,mrb,size) kh_init_##name##_size(mrb,size)
 255 #define kh_init(name,mrb) kh_init_##name(mrb)
 256 #define kh_destroy(name, mrb, h) kh_destroy_##name(mrb, h)
 257 #define kh_clear(name, mrb, h) kh_clear_##name(mrb, h)
 258 #define kh_resize(name, mrb, h, s) kh_resize_##name(mrb, h, s)
 259 #define kh_put_prepare(name, mrb, h) kh_put_prepare_##name(mrb, h)
 260 #define kh_put(name, mrb, h, k) kh_put_##name(mrb, h, k, NULL)
 261 #define kh_put2(name, mrb, h, k, r) kh_put_##name(mrb, h, k, r)
 262 #define kh_get(name, mrb, h, k) kh_get_##name(mrb, h, k)
 263 #define kh_del(name, mrb, h, k) kh_del_##name(mrb, h, k)
 264 #define kh_copy(name, mrb, h) kh_copy_##name(mrb, h)
 265
 266 #define kh_exist(h, x) (!__ac_iseither((h)->ed_flags, (x)))
 267 #define kh_key(h, x) ((h)->keys[x])
 268 #define kh_val(h, x) ((h)->vals[x])
 269 #define kh_value(h, x) ((h)->vals[x])
 270 #define kh_begin(h) (khint_t)(0)
 271 #define kh_end(h) ((h)->n_buckets)
 272 #define kh_size(h) ((h)->size)
 273 #define kh_n_buckets(h) ((h)->n_buckets)
 274
 275 #define kh_int_hash_func(mrb,key) (khint_t)((key)^((key)<<2)^((key)>>2))
 276 #define kh_int_hash_equal(mrb,a, b) (a == b)
 277 #define kh_int64_hash_func(mrb,key) (khint_t)((key)>>33^(key)^(key)<<11)
 278 #define kh_int64_hash_equal(mrb,a, b) (a == b)
 279 static inline khint_t __ac_X31_hash_string(const char *s)
 280 {
 281     khint_t h = *s;
 282     if (h) for (++s ; *s; ++s) h = (h << 5) - h + *s;
 283     return h;
 284 }
 285 #define kh_str_hash_func(mrb,key) __ac_X31_hash_string(key)
 286 #define kh_str_hash_equal(mrb,a, b) (strcmp(a, b) == 0)
 287
 288 typedef const char *kh_cstr_t;
 289
 290 MRB_END_DECL
 291
 292 #endif  /* MRUBY_KHASH_H */