23#ifndef KHASH_DEFAULT_SIZE
24# define KHASH_DEFAULT_SIZE 32
26#define KHASH_MIN_SIZE 8
28#define UPPER_BOUND(x) ((x)>>2|(x)>>1)
33static const uint8_t __m_empty[] = {0x02, 0x08, 0x20, 0x80};
34static const uint8_t __m_del[] = {0x01, 0x04, 0x10, 0x40};
35static const uint8_t __m_either[] = {0x03, 0x0c, 0x30, 0xc0};
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 { \
50#define khash_mask(h) ((h)->n_buckets-1)
51#define khash_upper_bound(h) (UPPER_BOUND((h)->n_buckets))
60#define KHASH_DECLARE(name, khkey_t, khval_t, kh_is_map) \
61 typedef struct kh_##name { \
68 void kh_alloc_##name(mrb_state *mrb, kh_##name##_t *h); \
69 kh_##name##_t *kh_init_##name##_size(mrb_state *mrb, khint_t size); \
70 kh_##name##_t *kh_init_##name(mrb_state *mrb); \
71 void kh_destroy_##name(mrb_state *mrb, kh_##name##_t *h); \
72 void kh_clear_##name(mrb_state *mrb, kh_##name##_t *h); \
73 khint_t kh_get_##name(mrb_state *mrb, kh_##name##_t *h, khkey_t key); \
74 khint_t kh_put_##name(mrb_state *mrb, kh_##name##_t *h, khkey_t key, int *ret); \
75 void kh_resize_##name(mrb_state *mrb, kh_##name##_t *h, khint_t new_n_buckets); \
76 void kh_del_##name(mrb_state *mrb, kh_##name##_t *h, khint_t x); \
77 kh_##name##_t *kh_copy_##name(mrb_state *mrb, kh_##name##_t *h);
80kh_fill_flags(uint8_t *p, uint8_t c,
size_t len)
96#define KHASH_DEFINE(name, khkey_t, khval_t, kh_is_map, __hash_func, __hash_equal) \
97 mrb_noreturn void mrb_raise_nomemory(mrb_state *mrb); \
98 int kh_alloc_simple_##name(mrb_state *mrb, kh_##name##_t *h) \
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_simple(mrb, sizeof(uint8_t)*sz/4+len*sz); \
103 if (!p) { return 1; } \
105 h->keys = (khkey_t*)p; \
106 h->vals = kh_is_map ? (khval_t*)(p+sizeof(khkey_t)*sz) : NULL; \
107 h->ed_flags = p+len*sz; \
108 kh_fill_flags(h->ed_flags, 0xaa, sz/4); \
111 void kh_alloc_##name(mrb_state *mrb, kh_##name##_t *h) \
113 if (kh_alloc_simple_##name(mrb, h)) { \
114 mrb_raise_nomemory(mrb); \
117 kh_##name##_t *kh_init_##name##_size(mrb_state *mrb, khint_t size) { \
118 kh_##name##_t *h = (kh_##name##_t*)mrb_calloc(mrb, 1, sizeof(kh_##name##_t)); \
119 if (size < KHASH_MIN_SIZE) \
120 size = KHASH_MIN_SIZE; \
121 khash_power2(size); \
122 h->n_buckets = size; \
123 if (kh_alloc_simple_##name(mrb, h)) { \
125 mrb_raise_nomemory(mrb); \
129 kh_##name##_t *kh_init_##name(mrb_state *mrb) { \
130 return kh_init_##name##_size(mrb, KHASH_DEFAULT_SIZE); \
132 void kh_destroy_##name(mrb_state *mrb, kh_##name##_t *h) \
135 mrb_free(mrb, h->keys); \
139 void kh_clear_##name(mrb_state *mrb, kh_##name##_t *h) \
142 if (h && h->ed_flags) { \
143 kh_fill_flags(h->ed_flags, 0xaa, h->n_buckets/4); \
147 khint_t kh_get_##name(mrb_state *mrb, kh_##name##_t *h, khkey_t key) \
149 khint_t k = __hash_func(mrb,key) & khash_mask(h), step = 0; \
151 while (!__ac_isempty(h->ed_flags, k)) { \
152 if (!__ac_isdel(h->ed_flags, k)) { \
153 if (__hash_equal(mrb,h->keys[k], key)) return k; \
155 k = (k+(++step)) & khash_mask(h); \
159 void kh_resize_##name(mrb_state *mrb, kh_##name##_t *h, khint_t new_n_buckets) \
161 if (new_n_buckets < KHASH_MIN_SIZE) \
162 new_n_buckets = KHASH_MIN_SIZE; \
163 khash_power2(new_n_buckets); \
166 uint8_t *old_ed_flags = h->ed_flags; \
167 khkey_t *old_keys = h->keys; \
168 khval_t *old_vals = h->vals; \
169 khint_t old_n_buckets = h->n_buckets; \
171 hh.n_buckets = new_n_buckets; \
172 kh_alloc_##name(mrb, &hh); \
174 for (i=0; i<old_n_buckets; i++) { \
175 if (!__ac_iseither(old_ed_flags, i)) { \
176 khint_t k = kh_put_##name(mrb, &hh, old_keys[i], NULL); \
177 if (kh_is_map) kh_value(&hh,k) = old_vals[i]; \
182 mrb_free(mrb, old_keys); \
185 khint_t kh_put_##name(mrb_state *mrb, kh_##name##_t *h, khkey_t key, int *ret) \
187 khint_t k, del_k, step = 0; \
188 if (h->size >= khash_upper_bound(h)) { \
189 kh_resize_##name(mrb, h, h->n_buckets*2); \
191 k = __hash_func(mrb,key) & khash_mask(h); \
193 while (!__ac_isempty(h->ed_flags, k)) { \
194 if (!__ac_isdel(h->ed_flags, k)) { \
195 if (__hash_equal(mrb,h->keys[k], key)) { \
200 else if (del_k == kh_end(h)) { \
203 k = (k+(++step)) & khash_mask(h); \
205 if (del_k != kh_end(h)) { \
207 h->keys[del_k] = key; \
208 h->ed_flags[del_k/4] &= ~__m_del[del_k%4]; \
216 h->ed_flags[k/4] &= ~__m_empty[k%4]; \
222 void kh_del_##name(mrb_state *mrb, kh_##name##_t *h, khint_t x) \
225 mrb_assert(x != h->n_buckets && !__ac_iseither(h->ed_flags, x)); \
226 h->ed_flags[x/4] |= __m_del[x%4]; \
229 kh_##name##_t *kh_copy_##name(mrb_state *mrb, kh_##name##_t *h) \
234 h2 = kh_init_##name(mrb); \
235 for (k = kh_begin(h); k != kh_end(h); k++) { \
236 if (kh_exist(h, k)) { \
237 k2 = kh_put_##name(mrb, h2, kh_key(h, k), NULL); \
238 if (kh_is_map) kh_value(h2, k2) = kh_value(h, k); \
245#define khash_t(name) kh_##name##_t
247#define kh_init_size(name,mrb,size) kh_init_##name##_size(mrb,size)
248#define kh_init(name,mrb) kh_init_##name(mrb)
249#define kh_destroy(name, mrb, h) kh_destroy_##name(mrb, h)
250#define kh_clear(name, mrb, h) kh_clear_##name(mrb, h)
251#define kh_resize(name, mrb, h, s) kh_resize_##name(mrb, h, s)
252#define kh_put(name, mrb, h, k) kh_put_##name(mrb, h, k, NULL)
253#define kh_put2(name, mrb, h, k, r) kh_put_##name(mrb, h, k, r)
254#define kh_get(name, mrb, h, k) kh_get_##name(mrb, h, k)
255#define kh_del(name, mrb, h, k) kh_del_##name(mrb, h, k)
256#define kh_copy(name, mrb, h) kh_copy_##name(mrb, h)
258#define kh_exist(h, x) (!__ac_iseither((h)->ed_flags, (x)))
259#define kh_key(h, x) ((h)->keys[x])
260#define kh_val(h, x) ((h)->vals[x])
261#define kh_value(h, x) ((h)->vals[x])
262#define kh_begin(h) (khint_t)(0)
263#define kh_end(h) ((h)->n_buckets)
264#define kh_size(h) ((h)->size)
265#define kh_n_buckets(h) ((h)->n_buckets)
267#define kh_int_hash_func(mrb,key) (khint_t)((key)^((key)<<2)^((key)>>2))
268#define kh_int_hash_equal(mrb,a, b) (a == b)
269#define kh_int64_hash_func(mrb,key) (khint_t)((key)>>33^(key)^(key)<<11)
270#define kh_int64_hash_equal(mrb,a, b) (a == b)
271static inline khint_t __ac_X31_hash_string(
const char *s)
274 if (h)
for (++s; *s; ++s) h = (h << 5) - h + *s;
277#define kh_str_hash_func(mrb,key) __ac_X31_hash_string(key)
278#define kh_str_hash_equal(mrb,a, b) (strcmp(a, b) == 0)
280typedef const char *kh_cstr_t;
mruby common platform definition"
#define MRB_END_DECL
End declarations in C mode.
Definition common.h:28
#define MRB_BEGIN_DECL
Start declarations in C mode.
Definition common.h:26
uint32_t khint_t
khash definitions used in mruby's hash table.
Definition khash.h:20