source: EcnlProtoTool/trunk/mruby-1.3.0/include/mruby/khash.h@ 331

Last change on this file since 331 was 331, checked in by coas-nagasima, 6 years ago

prototoolに関連するプロジェクトをnewlibからmuslを使うよう変更・更新
ntshellをnewlibの下位の実装から、muslのsyscallの実装に変更・更新
以下のOSSをアップデート
・mruby-1.3.0
・musl-1.1.18
・onigmo-6.1.3
・tcc-0.9.27
以下のOSSを追加
・openssl-1.1.0e
・curl-7.57.0
・zlib-1.2.11
以下のmrbgemsを追加
・iij/mruby-digest
・iij/mruby-env
・iij/mruby-errno
・iij/mruby-iijson
・iij/mruby-ipaddr
・iij/mruby-mock
・iij/mruby-require
・iij/mruby-tls-openssl
  • Property svn:eol-style set to native
  • Property svn:mime-type set to text/x-chdr;charset=UTF-8
File size: 14.3 KB
Line 
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 "common.h"
14
15/**
16 * khash definitions used in mruby's hash table.
17 */
18MRB_BEGIN_DECL
19
20typedef uint32_t khint_t;
21typedef 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 */
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};
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
80static inline void
81kh_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)
261static 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
270typedef const char *kh_cstr_t;
271
272MRB_END_DECL
273
274#endif /* MRUBY_KHASH_H */
Note: See TracBrowser for help on using the repository browser.