sabme ua / mruby-mbed

mbed I/F binding for mruby

Dependents:   mruby_mbed_web mirb_mbed

mbed-mruby

How to use

Class

include/mruby/khash.h@0:158c61bb030f, 2015-03-25 (annotated)

Committer:
mzta
Date:
Wed Mar 25 17:36:16 2015 +0000
Revision:
0:158c61bb030f
mirb_mbed initial commit;

Who changed what in which revision?

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