[270] | 1 | /*
|
---|
| 2 | ** mruby/khash.c - 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 "mruby/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_resize_##name(mrb_state *mrb, kh_##name##_t *h, khint_t new_n_buckets); \
|
---|
| 77 | void kh_del_##name(mrb_state *mrb, kh_##name##_t *h, khint_t x); \
|
---|
| 78 | kh_##name##_t *kh_copy_##name(mrb_state *mrb, kh_##name##_t *h);
|
---|
| 79 |
|
---|
| 80 | static inline void
|
---|
| 81 | kh_fill_flags(uint8_t *p, uint8_t c, size_t len)
|
---|
| 82 | {
|
---|
| 83 | while (len-- > 0) {
|
---|
| 84 | *p++ = c;
|
---|
| 85 | }
|
---|
| 86 | }
|
---|
| 87 |
|
---|
| 88 | /* define kh_xxx_funcs
|
---|
| 89 |
|
---|
| 90 | name: hash name
|
---|
| 91 | khkey_t: key data type
|
---|
| 92 | khval_t: value data type
|
---|
| 93 | kh_is_map: (0: hash set / 1: hash map)
|
---|
| 94 | __hash_func: hash function
|
---|
| 95 | __hash_equal: hash comparation function
|
---|
| 96 | */
|
---|
| 97 | #define KHASH_DEFINE(name, khkey_t, khval_t, kh_is_map, __hash_func, __hash_equal) \
|
---|
| 98 | void kh_alloc_##name(mrb_state *mrb, kh_##name##_t *h) \
|
---|
| 99 | { \
|
---|
| 100 | khint_t sz = h->n_buckets; \
|
---|
| 101 | size_t len = sizeof(khkey_t) + (kh_is_map ? sizeof(khval_t) : 0); \
|
---|
| 102 | uint8_t *p = (uint8_t*)mrb_malloc(mrb, sizeof(uint8_t)*sz/4+len*sz); \
|
---|
| 103 | h->size = h->n_occupied = 0; \
|
---|
| 104 | h->keys = (khkey_t *)p; \
|
---|
| 105 | h->vals = kh_is_map ? (khval_t *)(p+sizeof(khkey_t)*sz) : NULL; \
|
---|
| 106 | h->ed_flags = p+len*sz; \
|
---|
| 107 | kh_fill_flags(h->ed_flags, 0xaa, sz/4); \
|
---|
| 108 | } \
|
---|
| 109 | kh_##name##_t *kh_init_##name##_size(mrb_state *mrb, khint_t size) { \
|
---|
| 110 | kh_##name##_t *h = (kh_##name##_t*)mrb_calloc(mrb, 1, sizeof(kh_##name##_t)); \
|
---|
| 111 | if (size < KHASH_MIN_SIZE) \
|
---|
| 112 | size = KHASH_MIN_SIZE; \
|
---|
| 113 | khash_power2(size); \
|
---|
| 114 | h->n_buckets = size; \
|
---|
| 115 | kh_alloc_##name(mrb, h); \
|
---|
| 116 | return h; \
|
---|
| 117 | } \
|
---|
| 118 | kh_##name##_t *kh_init_##name(mrb_state *mrb) { \
|
---|
| 119 | return kh_init_##name##_size(mrb, KHASH_DEFAULT_SIZE); \
|
---|
| 120 | } \
|
---|
| 121 | void kh_destroy_##name(mrb_state *mrb, kh_##name##_t *h) \
|
---|
| 122 | { \
|
---|
| 123 | if (h) { \
|
---|
| 124 | mrb_free(mrb, h->keys); \
|
---|
| 125 | mrb_free(mrb, h); \
|
---|
| 126 | } \
|
---|
| 127 | } \
|
---|
| 128 | void kh_clear_##name(mrb_state *mrb, kh_##name##_t *h) \
|
---|
| 129 | { \
|
---|
| 130 | (void)mrb; \
|
---|
| 131 | if (h && h->ed_flags) { \
|
---|
| 132 | kh_fill_flags(h->ed_flags, 0xaa, h->n_buckets/4); \
|
---|
| 133 | h->size = h->n_occupied = 0; \
|
---|
| 134 | } \
|
---|
| 135 | } \
|
---|
| 136 | khint_t kh_get_##name(mrb_state *mrb, kh_##name##_t *h, khkey_t key) \
|
---|
| 137 | { \
|
---|
| 138 | khint_t k = __hash_func(mrb,key) & khash_mask(h), step = 0; \
|
---|
| 139 | (void)mrb; \
|
---|
| 140 | while (!__ac_isempty(h->ed_flags, k)) { \
|
---|
| 141 | if (!__ac_isdel(h->ed_flags, k)) { \
|
---|
| 142 | if (__hash_equal(mrb,h->keys[k], key)) return k; \
|
---|
| 143 | } \
|
---|
| 144 | k = (k+(++step)) & khash_mask(h); \
|
---|
| 145 | } \
|
---|
| 146 | return kh_end(h); \
|
---|
| 147 | } \
|
---|
| 148 | void kh_resize_##name(mrb_state *mrb, kh_##name##_t *h, khint_t new_n_buckets) \
|
---|
| 149 | { \
|
---|
| 150 | if (new_n_buckets < KHASH_MIN_SIZE) \
|
---|
| 151 | new_n_buckets = KHASH_MIN_SIZE; \
|
---|
| 152 | khash_power2(new_n_buckets); \
|
---|
| 153 | { \
|
---|
| 154 | kh_##name##_t hh; \
|
---|
| 155 | uint8_t *old_ed_flags = h->ed_flags; \
|
---|
| 156 | khkey_t *old_keys = h->keys; \
|
---|
| 157 | khval_t *old_vals = h->vals; \
|
---|
| 158 | khint_t old_n_buckets = h->n_buckets; \
|
---|
| 159 | khint_t i; \
|
---|
| 160 | hh.n_buckets = new_n_buckets; \
|
---|
| 161 | kh_alloc_##name(mrb, &hh); \
|
---|
| 162 | /* relocate */ \
|
---|
| 163 | for (i=0 ; i<old_n_buckets ; i++) { \
|
---|
| 164 | if (!__ac_iseither(old_ed_flags, i)) { \
|
---|
| 165 | khint_t k = kh_put_##name(mrb, &hh, old_keys[i], NULL); \
|
---|
| 166 | if (kh_is_map) kh_value(&hh,k) = old_vals[i]; \
|
---|
| 167 | } \
|
---|
| 168 | } \
|
---|
| 169 | /* copy hh to h */ \
|
---|
| 170 | *h = hh; \
|
---|
| 171 | mrb_free(mrb, old_keys); \
|
---|
| 172 | } \
|
---|
| 173 | } \
|
---|
| 174 | khint_t kh_put_##name(mrb_state *mrb, kh_##name##_t *h, khkey_t key, int *ret) \
|
---|
| 175 | { \
|
---|
| 176 | khint_t k, del_k, step = 0; \
|
---|
| 177 | if (h->n_occupied >= khash_upper_bound(h)) { \
|
---|
| 178 | kh_resize_##name(mrb, h, h->n_buckets*2); \
|
---|
| 179 | } \
|
---|
| 180 | k = __hash_func(mrb,key) & khash_mask(h); \
|
---|
| 181 | del_k = kh_end(h); \
|
---|
| 182 | while (!__ac_isempty(h->ed_flags, k)) { \
|
---|
| 183 | if (!__ac_isdel(h->ed_flags, k)) { \
|
---|
| 184 | if (__hash_equal(mrb,h->keys[k], key)) { \
|
---|
| 185 | if (ret) *ret = 0; \
|
---|
| 186 | return k; \
|
---|
| 187 | } \
|
---|
| 188 | } \
|
---|
| 189 | else if (del_k == kh_end(h)) { \
|
---|
| 190 | del_k = k; \
|
---|
| 191 | } \
|
---|
| 192 | k = (k+(++step)) & khash_mask(h); \
|
---|
| 193 | } \
|
---|
| 194 | if (del_k != kh_end(h)) { \
|
---|
| 195 | /* put at del */ \
|
---|
| 196 | h->keys[del_k] = key; \
|
---|
| 197 | h->ed_flags[del_k/4] &= ~__m_del[del_k%4]; \
|
---|
| 198 | h->size++; \
|
---|
| 199 | if (ret) *ret = 2; \
|
---|
| 200 | return del_k; \
|
---|
| 201 | } \
|
---|
| 202 | else { \
|
---|
| 203 | /* put at empty */ \
|
---|
| 204 | h->keys[k] = key; \
|
---|
| 205 | h->ed_flags[k/4] &= ~__m_empty[k%4]; \
|
---|
| 206 | h->size++; \
|
---|
| 207 | h->n_occupied++; \
|
---|
| 208 | if (ret) *ret = 1; \
|
---|
| 209 | return k; \
|
---|
| 210 | } \
|
---|
| 211 | } \
|
---|
| 212 | void kh_del_##name(mrb_state *mrb, kh_##name##_t *h, khint_t x) \
|
---|
| 213 | { \
|
---|
| 214 | (void)mrb; \
|
---|
| 215 | mrb_assert(x != h->n_buckets && !__ac_iseither(h->ed_flags, x)); \
|
---|
| 216 | h->ed_flags[x/4] |= __m_del[x%4]; \
|
---|
| 217 | h->size--; \
|
---|
| 218 | } \
|
---|
| 219 | kh_##name##_t *kh_copy_##name(mrb_state *mrb, kh_##name##_t *h) \
|
---|
| 220 | { \
|
---|
| 221 | kh_##name##_t *h2; \
|
---|
| 222 | khiter_t k, k2; \
|
---|
| 223 | \
|
---|
| 224 | h2 = kh_init_##name(mrb); \
|
---|
| 225 | for (k = kh_begin(h); k != kh_end(h); k++) { \
|
---|
| 226 | if (kh_exist(h, k)) { \
|
---|
| 227 | k2 = kh_put_##name(mrb, h2, kh_key(h, k), NULL); \
|
---|
| 228 | if (kh_is_map) kh_value(h2, k2) = kh_value(h, k); \
|
---|
| 229 | } \
|
---|
| 230 | } \
|
---|
| 231 | return h2; \
|
---|
| 232 | }
|
---|
| 233 |
|
---|
| 234 |
|
---|
| 235 | #define khash_t(name) kh_##name##_t
|
---|
| 236 |
|
---|
| 237 | #define kh_init_size(name,mrb,size) kh_init_##name##_size(mrb,size)
|
---|
| 238 | #define kh_init(name,mrb) kh_init_##name(mrb)
|
---|
| 239 | #define kh_destroy(name, mrb, h) kh_destroy_##name(mrb, h)
|
---|
| 240 | #define kh_clear(name, mrb, h) kh_clear_##name(mrb, h)
|
---|
| 241 | #define kh_resize(name, mrb, h, s) kh_resize_##name(mrb, h, s)
|
---|
| 242 | #define kh_put(name, mrb, h, k) kh_put_##name(mrb, h, k, NULL)
|
---|
| 243 | #define kh_put2(name, mrb, h, k, r) kh_put_##name(mrb, h, k, r)
|
---|
| 244 | #define kh_get(name, mrb, h, k) kh_get_##name(mrb, h, k)
|
---|
| 245 | #define kh_del(name, mrb, h, k) kh_del_##name(mrb, h, k)
|
---|
| 246 | #define kh_copy(name, mrb, h) kh_copy_##name(mrb, h)
|
---|
| 247 |
|
---|
| 248 | #define kh_exist(h, x) (!__ac_iseither((h)->ed_flags, (x)))
|
---|
| 249 | #define kh_key(h, x) ((h)->keys[x])
|
---|
| 250 | #define kh_val(h, x) ((h)->vals[x])
|
---|
| 251 | #define kh_value(h, x) ((h)->vals[x])
|
---|
| 252 | #define kh_begin(h) (khint_t)(0)
|
---|
| 253 | #define kh_end(h) ((h)->n_buckets)
|
---|
| 254 | #define kh_size(h) ((h)->size)
|
---|
| 255 | #define kh_n_buckets(h) ((h)->n_buckets)
|
---|
| 256 |
|
---|
| 257 | #define kh_int_hash_func(mrb,key) (khint_t)((key)^((key)<<2)^((key)>>2))
|
---|
| 258 | #define kh_int_hash_equal(mrb,a, b) (a == b)
|
---|
| 259 | #define kh_int64_hash_func(mrb,key) (khint_t)((key)>>33^(key)^(key)<<11)
|
---|
| 260 | #define kh_int64_hash_equal(mrb,a, b) (a == b)
|
---|
| 261 | static inline khint_t __ac_X31_hash_string(const char *s)
|
---|
| 262 | {
|
---|
| 263 | khint_t h = *s;
|
---|
| 264 | if (h) for (++s ; *s; ++s) h = (h << 5) - h + *s;
|
---|
| 265 | return h;
|
---|
| 266 | }
|
---|
| 267 | #define kh_str_hash_func(mrb,key) __ac_X31_hash_string(key)
|
---|
| 268 | #define kh_str_hash_equal(mrb,a, b) (strcmp(a, b) == 0)
|
---|
| 269 |
|
---|
| 270 | typedef const char *kh_cstr_t;
|
---|
| 271 |
|
---|
| 272 | MRB_END_DECL
|
---|
| 273 |
|
---|
| 274 | #endif /* MRUBY_KHASH_H */
|
---|