khash.h

00001 /*
00002 ** mruby/khash.c - Hash for mruby
00003 **
00004 ** See Copyright Notice in mruby.h
00005 */
00006 
00007 #ifndef MRUBY_KHASH_H
00008 #define MRUBY_KHASH_H
00009 
00010 #if defined(__cplusplus)
00011 extern "C" {
00012 #endif
00013 
00014 #include "mruby.h"
00015 #include <string.h>
00016 
00017 typedef uint32_t khint_t;
00018 typedef khint_t khiter_t;
00019 
00020 #ifndef KHASH_DEFAULT_SIZE
00021 # define KHASH_DEFAULT_SIZE 32
00022 #endif
00023 #define KHASH_MIN_SIZE 8
00024 
00025 #define UPPER_BOUND(x) ((x)>>2|(x)>>1)
00026 
00027 /* extern uint8_t __m[]; */
00028 
00029 /* mask for flags */
00030 static const uint8_t __m_empty[]  = {0x02, 0x08, 0x20, 0x80};
00031 static const uint8_t __m_del[]    = {0x01, 0x04, 0x10, 0x40};
00032 static const uint8_t __m_either[] = {0x03, 0x0c, 0x30, 0xc0};
00033 
00034 
00035 #define __ac_isempty(ed_flag, i) (ed_flag[(i)/4]&__m_empty[(i)%4])
00036 #define __ac_isdel(ed_flag, i) (ed_flag[(i)/4]&__m_del[(i)%4])
00037 #define __ac_iseither(ed_flag, i) (ed_flag[(i)/4]&__m_either[(i)%4])
00038 #define khash_power2(v) do { \
00039   v--;\
00040   v |= v >> 1;\
00041   v |= v >> 2;\
00042   v |= v >> 4;\
00043   v |= v >> 8;\
00044   v |= v >> 16;\
00045   v++;\
00046 } while (0)
00047 #define khash_mask(h) ((h)->n_buckets-1)
00048 #define khash_upper_bound(h) (UPPER_BOUND((h)->n_buckets))
00049 
00050 /* declare struct kh_xxx and kh_xxx_funcs
00051 
00052    name: hash name
00053    khkey_t: key data type
00054    khval_t: value data type
00055    kh_is_map: (0: hash set / 1: hash map)
00056 */
00057 #define KHASH_DECLARE(name, khkey_t, khval_t, kh_is_map)                \
00058   typedef struct kh_##name {                                            \
00059     khint_t n_buckets;                                                  \
00060     khint_t size;                                                       \
00061     khint_t n_occupied;                                                 \
00062     uint8_t *ed_flags;                                                  \
00063     khkey_t *keys;                                                      \
00064     khval_t *vals;                                                      \
00065   } kh_##name##_t;                                                      \
00066   void kh_alloc_##name(mrb_state *mrb, kh_##name##_t *h);               \
00067   kh_##name##_t *kh_init_##name##_size(mrb_state *mrb, khint_t size);   \
00068   kh_##name##_t *kh_init_##name(mrb_state *mrb);                        \
00069   void kh_destroy_##name(mrb_state *mrb, kh_##name##_t *h);             \
00070   void kh_clear_##name(mrb_state *mrb, kh_##name##_t *h);               \
00071   khint_t kh_get_##name(mrb_state *mrb, kh_##name##_t *h, khkey_t key);           \
00072   khint_t kh_put_##name(mrb_state *mrb, kh_##name##_t *h, khkey_t key, int *ret); \
00073   void kh_resize_##name(mrb_state *mrb, kh_##name##_t *h, khint_t new_n_buckets); \
00074   void kh_del_##name(mrb_state *mrb, kh_##name##_t *h, khint_t x);                \
00075   kh_##name##_t *kh_copy_##name(mrb_state *mrb, kh_##name##_t *h);
00076 
00077 static inline void
00078 kh_fill_flags(uint8_t *p, uint8_t c, size_t len)
00079 {
00080   while (len-- > 0) {
00081     *p++ = c;
00082   }
00083 }
00084 
00085 /* define kh_xxx_funcs
00086 
00087    name: hash name
00088    khkey_t: key data type
00089    khval_t: value data type
00090    kh_is_map: (0: hash set / 1: hash map)
00091    __hash_func: hash function
00092    __hash_equal: hash comparation function
00093 */
00094 #define KHASH_DEFINE(name, khkey_t, khval_t, kh_is_map, __hash_func, __hash_equal) \
00095   void kh_alloc_##name(mrb_state *mrb, kh_##name##_t *h)                \
00096   {                                                                     \
00097     khint_t sz = h->n_buckets;                                          \
00098     size_t len = sizeof(khkey_t) + (kh_is_map ? sizeof(khval_t) : 0);   \
00099     uint8_t *p = (uint8_t*)mrb_malloc(mrb, sizeof(uint8_t)*sz/4+len*sz); \
00100     h->size = h->n_occupied = 0;                                        \
00101     h->keys = (khkey_t *)p;                                             \
00102     h->vals = kh_is_map ? (khval_t *)(p+sizeof(khkey_t)*sz) : NULL;     \
00103     h->ed_flags = p+len*sz;                                             \
00104     kh_fill_flags(h->ed_flags, 0xaa, sz/4);                             \
00105   }                                                                     \
00106   kh_##name##_t *kh_init_##name##_size(mrb_state *mrb, khint_t size) {  \
00107     kh_##name##_t *h = (kh_##name##_t*)mrb_calloc(mrb, 1, sizeof(kh_##name##_t)); \
00108     if (size < KHASH_MIN_SIZE)                                          \
00109       size = KHASH_MIN_SIZE;                                            \
00110     khash_power2(size);                                                 \
00111     h->n_buckets = size;                                                \
00112     kh_alloc_##name(mrb, h);                                            \
00113     return h;                                                           \
00114   }                                                                     \
00115   kh_##name##_t *kh_init_##name(mrb_state *mrb) {                       \
00116     return kh_init_##name##_size(mrb, KHASH_DEFAULT_SIZE);              \
00117   }                                                                     \
00118   void kh_destroy_##name(mrb_state *mrb, kh_##name##_t *h)              \
00119   {                                                                     \
00120     if (h) {                                                            \
00121       mrb_free(mrb, h->keys);                                           \
00122       mrb_free(mrb, h);                                                 \
00123     }                                                                   \
00124   }                                                                     \
00125   void kh_clear_##name(mrb_state *mrb, kh_##name##_t *h)                \
00126   {                                                                     \
00127     (void)mrb;                                                          \
00128     if (h && h->ed_flags) {                                             \
00129       kh_fill_flags(h->ed_flags, 0xaa, h->n_buckets/4);                 \
00130       h->size = h->n_occupied = 0;                                      \
00131     }                                                                   \
00132   }                                                                     \
00133   khint_t kh_get_##name(mrb_state *mrb, kh_##name##_t *h, khkey_t key)  \
00134   {                                                                     \
00135     khint_t k = __hash_func(mrb,key) & khash_mask(h), step = 0;         \
00136     (void)mrb;                                                          \
00137     while (!__ac_isempty(h->ed_flags, k)) {                             \
00138       if (!__ac_isdel(h->ed_flags, k)) {                                \
00139         if (__hash_equal(mrb,h->keys[k], key)) return k;                \
00140       }                                                                 \
00141       k = (k+(++step)) & khash_mask(h);                                 \
00142     }                                                                   \
00143     return kh_end(h);                                                   \
00144   }                                                                     \
00145   void kh_resize_##name(mrb_state *mrb, kh_##name##_t *h, khint_t new_n_buckets) \
00146   {                                                                     \
00147     if (new_n_buckets < KHASH_MIN_SIZE)                                 \
00148       new_n_buckets = KHASH_MIN_SIZE;                                   \
00149     khash_power2(new_n_buckets);                                        \
00150     {                                                                   \
00151       uint8_t *old_ed_flags = h->ed_flags;                              \
00152       khkey_t *old_keys = h->keys;                                      \
00153       khval_t *old_vals = h->vals;                                      \
00154       khint_t old_n_buckets = h->n_buckets;                             \
00155       khint_t i;                                                        \
00156       h->n_buckets = new_n_buckets;                                     \
00157       kh_alloc_##name(mrb, h);                                          \
00158       /* relocate */                                                    \
00159       for (i=0 ; i<old_n_buckets ; i++) {                               \
00160         if (!__ac_iseither(old_ed_flags, i)) {                          \
00161           khint_t k = kh_put_##name(mrb, h, old_keys[i], NULL);         \
00162           if (kh_is_map) kh_value(h,k) = old_vals[i];                   \
00163         }                                                               \
00164       }                                                                 \
00165       mrb_free(mrb, old_keys);                                          \
00166     }                                                                   \
00167   }                                                                     \
00168   khint_t kh_put_##name(mrb_state *mrb, kh_##name##_t *h, khkey_t key, int *ret) \
00169   {                                                                     \
00170     khint_t k, del_k, step = 0;                                         \
00171     if (h->n_occupied >= khash_upper_bound(h)) {                        \
00172       kh_resize_##name(mrb, h, h->n_buckets*2);                         \
00173     }                                                                   \
00174     k = __hash_func(mrb,key) & khash_mask(h);                           \
00175     del_k = kh_end(h);                                                  \
00176     while (!__ac_isempty(h->ed_flags, k)) {                             \
00177       if (!__ac_isdel(h->ed_flags, k)) {                                \
00178         if (__hash_equal(mrb,h->keys[k], key)) {                        \
00179           if (ret) *ret = 0;                                            \
00180           return k;                                                     \
00181         }                                                               \
00182       }                                                                 \
00183       else if (del_k == kh_end(h)) {                                    \
00184         del_k = k;                                                      \
00185       }                                                                 \
00186       k = (k+(++step)) & khash_mask(h);                                 \
00187     }                                                                   \
00188     if (del_k != kh_end(h)) {                                           \
00189       /* put at del */                                                  \
00190       h->keys[del_k] = key;                                             \
00191       h->ed_flags[del_k/4] &= ~__m_del[del_k%4];                        \
00192       h->size++;                                                        \
00193       if (ret) *ret = 2;                                                \
00194       return del_k;                                                     \
00195     }                                                                   \
00196     else {                                                              \
00197       /* put at empty */                                                \
00198       h->keys[k] = key;                                                 \
00199       h->ed_flags[k/4] &= ~__m_empty[k%4];                              \
00200       h->size++;                                                        \
00201       h->n_occupied++;                                                  \
00202       if (ret) *ret = 1;                                                \
00203       return k;                                                         \
00204     }                                                                   \
00205   }                                                                     \
00206   void kh_del_##name(mrb_state *mrb, kh_##name##_t *h, khint_t x)       \
00207   {                                                                     \
00208     (void)mrb;                                                          \
00209     mrb_assert(x != h->n_buckets && !__ac_iseither(h->ed_flags, x));    \
00210     h->ed_flags[x/4] |= __m_del[x%4];                                   \
00211     h->size--;                                                          \
00212   }                                                                     \
00213   kh_##name##_t *kh_copy_##name(mrb_state *mrb, kh_##name##_t *h)       \
00214   {                                                                     \
00215     kh_##name##_t *h2;                                                  \
00216     khiter_t k, k2;                                                     \
00217                                                                         \
00218     h2 = kh_init_##name(mrb);                                           \
00219     for (k = kh_begin(h); k != kh_end(h); k++) {                        \
00220       if (kh_exist(h, k)) {                                             \
00221         k2 = kh_put_##name(mrb, h2, kh_key(h, k), NULL);                \
00222         if (kh_is_map) kh_value(h2, k2) = kh_value(h, k);               \
00223       }                                                                 \
00224     }                                                                   \
00225     return h2;                                                          \
00226   }
00227 
00228 
00229 #define khash_t(name) kh_##name##_t
00230 
00231 #define kh_init_size(name,mrb,size) kh_init_##name##_size(mrb,size)
00232 #define kh_init(name,mrb) kh_init_##name(mrb)
00233 #define kh_destroy(name, mrb, h) kh_destroy_##name(mrb, h)
00234 #define kh_clear(name, mrb, h) kh_clear_##name(mrb, h)
00235 #define kh_resize(name, mrb, h, s) kh_resize_##name(mrb, h, s)
00236 #define kh_put(name, mrb, h, k) kh_put_##name(mrb, h, k, NULL)
00237 #define kh_put2(name, mrb, h, k, r) kh_put_##name(mrb, h, k, r)
00238 #define kh_get(name, mrb, h, k) kh_get_##name(mrb, h, k)
00239 #define kh_del(name, mrb, h, k) kh_del_##name(mrb, h, k)
00240 #define kh_copy(name, mrb, h) kh_copy_##name(mrb, h)
00241 
00242 #define kh_exist(h, x) (!__ac_iseither((h)->ed_flags, (x)))
00243 #define kh_key(h, x) ((h)->keys[x])
00244 #define kh_val(h, x) ((h)->vals[x])
00245 #define kh_value(h, x) ((h)->vals[x])
00246 #define kh_begin(h) (khint_t)(0)
00247 #define kh_end(h) ((h)->n_buckets)
00248 #define kh_size(h) ((h)->size)
00249 #define kh_n_buckets(h) ((h)->n_buckets)
00250 
00251 #define kh_int_hash_func(mrb,key) (khint_t)((key)^((key)<<2)^((key)>>2))
00252 #define kh_int_hash_equal(mrb,a, b) (a == b)
00253 #define kh_int64_hash_func(mrb,key) (khint_t)((key)>>33^(key)^(key)<<11)
00254 #define kh_int64_hash_equal(mrb,a, b) (a == b)
00255 static inline khint_t __ac_X31_hash_string(const char *s)
00256 {
00257     khint_t h = *s;
00258     if (h) for (++s ; *s; ++s) h = (h << 5) - h + *s;
00259     return h;
00260 }
00261 #define kh_str_hash_func(mrb,key) __ac_X31_hash_string(key)
00262 #define kh_str_hash_equal(mrb,a, b) (strcmp(a, b) == 0)
00263 
00264 typedef const char *kh_cstr_t;
00265 
00266 #if defined(__cplusplus)
00267 }  /* extern "C" { */
00268 #endif
00269 
00270 #endif  /* MRUBY_KHASH_H */
00271