mruby  2.0.1
mruby is the lightweight implementation of the Ruby language
khash.h
Go to the documentation of this file.
1 
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 
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 */
khint_t
uint32_t khint_t
khash definitions used in mruby&#39;s hash table.
Definition: khash.h:20
string.h
String class
MRB_BEGIN_DECL
#define MRB_BEGIN_DECL
Start declarations in C mode.
Definition: common.h:26
MRB_END_DECL
#define MRB_END_DECL
End declarations in C mode.
Definition: common.h:28
common.h
mruby common platform definition"
Generated by   doxygen 1.8.13