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