khash optimize

1 files changed, 24 insertions, 26 deletions

diff --git a/include/mruby/khash.h b/include/mruby/khash.h
index db8048f5a..7fec66c19 100644
--- a/include/mruby/khash.h
+++ b/include/mruby/khash.h
@@ -27,12 +27,14 @@ typedef khint_t khiter_t;
 //extern uint8_t __m[];
 
 /* mask for flags */
-static const uint8_t __m[8] = {0x01, 0x02, 0x04, 0x08, 0x10, 0x20, 0x40, 0x80};
+static const uint8_t __m_empty[8]  = {0x02, 0x08, 0x20, 0x80};
+static const uint8_t __m_del[8]    = {0x01, 0x04, 0x10, 0x40};
+static const uint8_t __m_either[8] = {0x03, 0x0c, 0x30, 0xc0};
 
 
-#define __ac_isempty(e_flag, d_flag, i) (e_flag[(i)/8]&__m[(i)%8])
-#define __ac_isdel(e_flag, d_flag, i) (d_flag[(i)/8]&__m[(i)%8])
-#define __ac_iseither(e_flag, d_flag, i) (__ac_isempty(e_flag,d_flag,i)||__ac_isdel(e_flag,d_flag,i))
+#define __ac_isempty(ed_flag, i) (ed_flag[(i)/4]&__m_empty[(i)%4])
+#define __ac_isdel(ed_flag, i) (ed_flag[(i)/4]&__m_del[(i)%4])
+#define __ac_iseither(ed_flag, i) (ed_flag[(i)/4]&__m_either[(i)%4])
 #define khash_power2(v) do { \
   v--;\
   v |= v >> 1;\
@@ -56,8 +58,7 @@ static const uint8_t __m[8] = {0x01, 0x02, 0x04, 0x08, 0x10, 0x20, 0x40, 0x80};
     khint_t size;                                                       \
     khint_t n_occupied;                                                 \
     khint_t upper_bound;                                                \
-    uint8_t *e_flags;                                                   \
-    uint8_t *d_flags;                                                   \
+    uint8_t *ed_flags;                                                  \
     khkey_t *keys;                                                      \
     khval_t *vals;                                                      \
     khint_t mask;                                                       \
@@ -98,10 +99,8 @@ kh_fill_flags(uint8_t *p, uint8_t c, size_t len)
     khint_t sz = h->n_buckets;                                          \
     h->size = h->n_occupied = 0;                                        \
     h->upper_bound = UPPER_BOUND(sz);                                   \
-    h->e_flags = (uint8_t *)mrb_malloc(h->mrb, sizeof(uint8_t)*sz/4);   \
-    h->d_flags = h->e_flags + sz/8;                                     \
-    kh_fill_flags(h->e_flags, 0xff, sz/8);                              \
-    kh_fill_flags(h->d_flags, 0x00, sz/8);                              \
+    h->ed_flags = (uint8_t *)mrb_malloc(h->mrb, sizeof(uint8_t)*sz/4);  \
+    kh_fill_flags(h->ed_flags, 0xaa, sz/4);                             \
     h->keys = (khkey_t *)mrb_malloc(h->mrb, sizeof(khkey_t)*sz);        \
     h->vals = (khval_t *)mrb_malloc(h->mrb, sizeof(khval_t)*sz);        \
     h->mask = sz-1;                                                     \
@@ -125,23 +124,22 @@ kh_fill_flags(uint8_t *p, uint8_t c, size_t len)
     if (h) {                                                            \
       mrb_free(h->mrb, h->keys);                                        \
       mrb_free(h->mrb, h->vals);                                        \
-      mrb_free(h->mrb, h->e_flags);                                     \
+      mrb_free(h->mrb, h->ed_flags);                                    \
       mrb_free(h->mrb, h);                                              \
     }                                                                   \
   }                                                                     \
   void kh_clear_##name(kh_##name##_t *h)                                \
   {                                                                     \
-    if (h && h->e_flags) {                                              \
-      kh_fill_flags(h->e_flags, 0xff, h->n_buckets/8);                  \
-      kh_fill_flags(h->d_flags, 0x00, h->n_buckets/8);                  \
+    if (h && h->ed_flags) {                                             \
+      kh_fill_flags(h->ed_flags, 0xaa, h->n_buckets/4);                 \
       h->size = h->n_occupied = 0;                                      \
     }                                                                   \
   }                                                                     \
   khint_t kh_get_##name(kh_##name##_t *h, khkey_t key)                  \
   {                                                                     \
     khint_t k = __hash_func(h->mrb,key) & (h->mask);                    \
-    while (!__ac_isempty(h->e_flags, h->d_flags, k)) {                  \
-      if (!__ac_isdel(h->e_flags, h->d_flags, k)) {                     \
+    while (!__ac_isempty(h->ed_flags, k)) {                             \
+      if (!__ac_isdel(h->ed_flags, k)) {                                \
         if (__hash_equal(h->mrb,h->keys[k], key)) return k;             \
       }                                                                 \
       k = (k+h->inc) & (h->mask);                                       \
@@ -154,7 +152,7 @@ kh_fill_flags(uint8_t *p, uint8_t c, size_t len)
       new_n_buckets = KHASH_MIN_SIZE;                                   \
     khash_power2(new_n_buckets);                                        \
     {                                                                   \
-      uint8_t *old_e_flags = h->e_flags;                                \
+      uint8_t *old_ed_flags = h->ed_flags;                              \
       khkey_t *old_keys = h->keys;                                      \
       khval_t *old_vals = h->vals;                                      \
       khint_t old_n_buckets = h->n_buckets;                             \
@@ -163,12 +161,12 @@ kh_fill_flags(uint8_t *p, uint8_t c, size_t len)
       kh_alloc_##name(h);                                               \
       /* relocate */                                                    \
       for (i=0 ; i<old_n_buckets ; i++) {                               \
-        if (!__ac_isempty(old_e_flags, old_d_flags, i)) {               \
+        if (!__ac_isempty(old_ed_flags, i)) {                           \
           khint_t k = kh_put_##name(h, old_keys[i]);                    \
           kh_value(h,k) = old_vals[i];                                  \
         }                                                               \
       }                                                                 \
-      mrb_free(h->mrb, old_e_flags);                                    \
+      mrb_free(h->mrb, old_ed_flags);                                   \
       mrb_free(h->mrb, old_keys);                                       \
       mrb_free(h->mrb, old_vals);                                       \
     }                                                                   \
@@ -180,27 +178,27 @@ kh_fill_flags(uint8_t *p, uint8_t c, size_t len)
       kh_resize_##name(h, h->n_buckets*2);                              \
     }                                                                   \
     k = __hash_func(h->mrb,key) & (h->mask);                            \
-    while (!__ac_iseither(h->e_flags, h->d_flags, k)) {                 \
+    while (!__ac_iseither(h->ed_flags, k)) {                            \
       if (__hash_equal(h->mrb,h->keys[k], key)) break;                  \
       k = (k+h->inc) & (h->mask);                                       \
     }                                                                   \
-    if (__ac_isempty(h->e_flags, h->d_flags, k)) {                      \
+    if (__ac_isempty(h->ed_flags, k)) {                                 \
       /* put at empty */                                                \
       h->keys[k] = key;                                                 \
-      h->e_flags[k/8] &= ~__m[k%8];                                     \
+      h->ed_flags[k/4] &= ~__m_empty[k%4];                              \
       h->size++;                                                        \
       h->n_occupied++;                                                  \
-    } else if (__ac_isdel(h->e_flags, h->d_flags, k)) {                 \
+    } else if (__ac_isdel(h->ed_flags, k)) {                            \
       /* put at del */                                                  \
       h->keys[k] = key;                                                 \
-      h->d_flags[k/8] &= ~__m[k%8];                                     \
+      h->ed_flags[k/4] &= ~__m_del[k%4];                                \
       h->size++;                                                        \
     }                                                                   \
     return k;                                                           \
   }                                                                     \
   void kh_del_##name(kh_##name##_t *h, khint_t x)                       \
   {                                                                     \
-    h->d_flags[x/8] |= __m[x%8];                                        \
+    h->ed_flags[x/4] |= __m_del[x%4];                                   \
     h->size--;                                                          \
   }                                                                     \
   kh_##name##_t *kh_copy_##name(mrb_state *mrb, kh_##name##_t *h)       \
@@ -231,7 +229,7 @@ kh_fill_flags(uint8_t *p, uint8_t c, size_t len)
 #define kh_del(name, h, k) kh_del_##name(h, k)
 #define kh_copy(name, mrb, h) kh_copy_##name(mrb, h)
 
-#define kh_exist(h, x) (!__ac_iseither((h)->e_flags, (h)->d_flags, (x)))
+#define kh_exist(h, x) (!__ac_iseither((h)->ed_flags, (x)))
 #define kh_key(h, x) ((h)->keys[x])
 #define kh_val(h, x) ((h)->vals[x])
 #define kh_value(h, x) ((h)->vals[x])