include/khash.h

   1 /* The MIT License
   2
   3    Copyright (c) 2008, by Attractive Chaos <attractivechaos@aol.co.uk>
   4
   5    Permission is hereby granted, free of charge, to any person obtaining
   6    a copy of this software and associated documentation files (the
   7    "Software"), to deal in the Software without restriction, including
   8    without limitation the rights to use, copy, modify, merge, publish,
   9    distribute, sublicense, and/or sell copies of the Software, and to
  10    permit persons to whom the Software is furnished to do so, subject to
  11    the following conditions:
  12
  13    The above copyright notice and this permission notice shall be
  14    included in all copies or substantial portions of the Software.
  15
  16    THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND,
  17    EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF
  18    MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND
  19    NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS
  20    BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN
  21    ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN
  22    CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE
  23    SOFTWARE.
  24 */
  25
  26 /*
  27   An example:
  28
  29 #include "khash.h"
  30 KHASH_MAP_INIT_INT(32, char)
  31 int main() {
  32     int ret, is_missing;
  33     khiter_t k;
  34     khash_t(32) *h = kh_init(32);
  35     k = kh_put(32, h, 5, &ret);
  36     if (!ret) kh_del(32, h, k);
  37     kh_value(h, k) = 10;
  38     k = kh_get(32, h, 10);
  39     is_missing = (k == kh_end(h));
  40     k = kh_get(32, h, 5);
  41     kh_del(32, h, k);
  42     for (k = kh_begin(h); k != kh_end(h); ++k)
  43         if (kh_exist(h, k)) kh_value(h, k) = 1;
  44     kh_destroy(32, h);
  45     return 0;
  46 }
  47 */
  48
  49 /*
  50   2008-09-19 (0.2.3):
  51
  52     * Corrected the example
  53     * Improved interfaces
  54
  55   2008-09-11 (0.2.2):
  56
  57     * Improved speed a little in kh_put()
  58
  59   2008-09-10 (0.2.1):
  60
  61     * Added kh_clear()
  62     * Fixed a compiling error
  63
  64   2008-09-02 (0.2.0):
  65
  66     * Changed to token concatenation which increases flexibility.
  67
  68   2008-08-31 (0.1.2):
  69
  70     * Fixed a bug in kh_get(), which has not been tested previously.
  71
  72   2008-08-31 (0.1.1):
  73
  74     * Added destructor
  75 */
  76
  77
  78 #ifndef __AC_KHASH_H
  79 #define __AC_KHASH_H
  80
  81 #define AC_VERSION_KHASH_H "0.2.2"
  82
  83 #include <stdio.h>
  84 #include <stdint.h>
  85 #include <stdlib.h>
  86 #include <string.h>
  87
  88 typedef uint32_t khint_t;
  89 typedef khint_t khiter_t;
  90
  91 #define __ac_HASH_PRIME_SIZE 32
  92 static const uint32_t __ac_prime_list[__ac_HASH_PRIME_SIZE] =
  93 {
  94   0ul,          3ul,          11ul,         23ul,         53ul,
  95   97ul,         193ul,        389ul,        769ul,        1543ul,
  96   3079ul,       6151ul,       12289ul,      24593ul,      49157ul,
  97   98317ul,      196613ul,     393241ul,     786433ul,     1572869ul,
  98   3145739ul,    6291469ul,    12582917ul,   25165843ul,   50331653ul,
  99   100663319ul,  201326611ul,  402653189ul,  805306457ul,  1610612741ul,
 100   3221225473ul, 4294967291ul
 101 };
 102
 103 #define __ac_isempty(flag, i) ((flag[i>>4]>>((i&0xfU)<<1))&2)
 104 #define __ac_isdel(flag, i) ((flag[i>>4]>>((i&0xfU)<<1))&1)
 105 #define __ac_iseither(flag, i) ((flag[i>>4]>>((i&0xfU)<<1))&3)
 106 #define __ac_set_isdel_false(flag, i) (flag[i>>4]&=~(1ul<<((i&0xfU)<<1)))
 107 #define __ac_set_isempty_false(flag, i) (flag[i>>4]&=~(2ul<<((i&0xfU)<<1)))
 108 #define __ac_set_isboth_false(flag, i) (flag[i>>4]&=~(3ul<<((i&0xfU)<<1)))
 109 #define __ac_set_isdel_true(flag, i) (flag[i>>4]|=1ul<<((i&0xfU)<<1))
 110
 111 static const double __ac_HASH_UPPER = 0.77;
 112
 113 #define KHASH_INIT(name, khkey_t, khval_t, kh_is_map, __hash_func, __hash_equal) \
 114     typedef struct {                                                    \
 115         khint_t n_buckets, size, n_occupied, upper_bound;               \
 116         uint32_t *flags;                                                \
 117         khkey_t *keys;                                                  \
 118         khval_t *vals;                                                  \
 119     } kh_##name##_t;                                                    \
 120     static inline kh_##name##_t *kh_init_##name() {                     \
 121         return (kh_##name##_t*)calloc(1, sizeof(kh_##name##_t));        \
 122     }                                                                   \
 123     static inline void kh_destroy_##name(kh_##name##_t *h)              \
 124     {                                                                   \
 125         if (h) {                                                        \
 126             free(h->keys); free(h->flags);                              \
 127             free(h->vals);                                              \
 128             free(h);                                                    \
 129         }                                                               \
 130     }                                                                   \
 131     static inline void kh_clear_##name(kh_##name##_t *h)                \
 132     {                                                                   \
 133         if (h && h->flags) { \
 134             memset(h->flags, 0xaa, ((h->n_buckets>>4) + 1) * sizeof(uint32_t)); \
 135             h->size = h->n_occupied = 0;                                \
 136         }                                                               \
 137     }                                                                   \
 138     static inline khint_t kh_get_##name(kh_##name##_t *h, khkey_t key)  \
 139     {                                                                   \
 140         if (h->n_buckets) {                                             \
 141             khint_t inc, k, i, last;                                    \
 142             k = __hash_func(key); i = k % h->n_buckets;                 \
 143             inc = 1 + k % (h->n_buckets - 1); last = i;                 \
 144             while (!__ac_isempty(h->flags, i) && (__ac_isdel(h->flags, i) || !__hash_equal(h->keys[i], key))) { \
 145                 if (i + inc >= h->n_buckets) i = i + inc - h->n_buckets; \
 146                 else i += inc;                                          \
 147                 if (i == last) return h->n_buckets;                     \
 148             }                                                           \
 149             return __ac_iseither(h->flags, i)? h->n_buckets : i;            \
 150         } else return 0;                                                \
 151     }                                                                   \
 152     static inline void kh_resize_##name(kh_##name##_t *h, khint_t new_n_buckets) \
 153     {                                                                   \
 154         uint32_t *new_flags = 0;                                        \
 155         khint_t j = 1;                                                  \
 156         {                                                               \
 157             khint_t t = __ac_HASH_PRIME_SIZE - 1;                       \
 158             while (__ac_prime_list[t] > new_n_buckets) {                \
 159                 --t;                                                    \
 160             }                                                           \
 161             new_n_buckets = __ac_prime_list[t+1];                       \
 162             if (h->size >= (khint_t)(new_n_buckets * __ac_HASH_UPPER + 0.5)) j = 0; \
 163             else {                                                      \
 164                 new_flags = (uint32_t*)malloc(((new_n_buckets>>4) + 1) * sizeof(uint32_t)); \
 165                 memset(new_flags, 0xaa, ((new_n_buckets>>4) + 1) * sizeof(uint32_t)); \
 166                 if (h->n_buckets < new_n_buckets) {                     \
 167                     h->keys = (khkey_t*)realloc(h->keys, new_n_buckets * sizeof(khkey_t)); \
 168                     if (kh_is_map)                                      \
 169                         h->vals = (khval_t*)realloc(h->vals, new_n_buckets * sizeof(khval_t)); \
 170                 }                                                       \
 171             }                                                           \
 172         }                                                               \
 173         if (j) {                                                        \
 174             for (j = 0; j != h->n_buckets; ++j) {                       \
 175                 if (__ac_iseither(h->flags, j) == 0) {                  \
 176                     khkey_t key = h->keys[j];                           \
 177                     khval_t val;                                        \
 178                     if (kh_is_map) val = h->vals[j];                    \
 179                     __ac_set_isdel_true(h->flags, j);                   \
 180                     while (1) {                                         \
 181                         khint_t inc, k, i;                              \
 182                         k = __hash_func(key);                           \
 183                         i = k % new_n_buckets;                          \
 184                         inc = 1 + k % (new_n_buckets - 1);              \
 185                         while (!__ac_isempty(new_flags, i)) {           \
 186                             if (i + inc >= new_n_buckets) i = i + inc - new_n_buckets; \
 187                             else i += inc;                              \
 188                         }                                               \
 189                         __ac_set_isempty_false(new_flags, i);           \
 190                         if (i < h->n_buckets && __ac_iseither(h->flags, i) == 0) { \
 191                             { khkey_t tmp = h->keys[i]; h->keys[i] = key; key = tmp; } \
 192                             if (kh_is_map) { khval_t tmp = h->vals[i]; h->vals[i] = val; val = tmp; } \
 193                             __ac_set_isdel_true(h->flags, i);           \
 194                         } else {                                        \
 195                             h->keys[i] = key;                           \
 196                             if (kh_is_map) h->vals[i] = val;            \
 197                             break;                                      \
 198                         }                                               \
 199                     }                                                   \
 200                 }                                                       \
 201             }                                                           \
 202             if (h->n_buckets > new_n_buckets) {                         \
 203                 h->keys = (khkey_t*)realloc(h->keys, new_n_buckets * sizeof(khkey_t)); \
 204                 if (kh_is_map)                                          \
 205                     h->vals = (khval_t*)realloc(h->vals, new_n_buckets * sizeof(khval_t)); \
 206             }                                                           \
 207             free(h->flags);                                             \
 208             h->flags = new_flags;                                       \
 209             h->n_buckets = new_n_buckets;                               \
 210             h->n_occupied = h->size;                                    \
 211             h->upper_bound = (khint_t)(h->n_buckets * __ac_HASH_UPPER + 0.5); \
 212         }                                                               \
 213     }                                                                   \
 214     static inline khint_t kh_put_##name(kh_##name##_t *h, khkey_t key, int *ret) \
 215     {                                                                   \
 216         khint_t x;                                                      \
 217         if (h->n_occupied >= h->upper_bound) {                          \
 218             if (h->n_buckets > (h->size<<1)) kh_resize_##name(h, h->n_buckets - 1); \
 219             else kh_resize_##name(h, h->n_buckets + 1);                 \
 220         }                                                               \
 221         {                                                               \
 222             khint_t inc, k, i, site, last;                              \
 223             x = site = h->n_buckets; k = __hash_func(key); i = k % h->n_buckets; \
 224             if (__ac_isempty(h->flags, i)) x = i;                       \
 225             else {                                                      \
 226                 inc = 1 + k % (h->n_buckets - 1); last = i;             \
 227                 while (!__ac_isempty(h->flags, i) && (__ac_isdel(h->flags, i) || !__hash_equal(h->keys[i], key))) { \
 228                     if (__ac_isdel(h->flags, i)) site = i;              \
 229                     if (i + inc >= h->n_buckets) i = i + inc - h->n_buckets; \
 230                     else i += inc;                                      \
 231                     if (i == last) { x = site; break; }                 \
 232                 }                                                       \
 233                 if (x == h->n_buckets) {                                \
 234                     if (__ac_isempty(h->flags, i) && site != h->n_buckets) x = site; \
 235                     else x = i;                                         \
 236                 }                                                       \
 237             }                                                           \
 238         }                                                               \
 239         if (__ac_isempty(h->flags, x)) {                                \
 240             h->keys[x] = key;                                           \
 241             __ac_set_isboth_false(h->flags, x);                         \
 242             ++h->size; ++h->n_occupied;                                 \
 243             *ret = 1;                                                   \
 244         } else if (__ac_isdel(h->flags, x)) {                           \
 245             h->keys[x] = key;                                           \
 246             __ac_set_isboth_false(h->flags, x);                         \
 247             ++h->size;                                                  \
 248             *ret = 2;                                                   \
 249         } else *ret = 0;                                                \
 250         return x;                                                       \
 251     }                                                                   \
 252     static inline void kh_del_##name(kh_##name##_t *h, khint_t x)       \
 253     {                                                                   \
 254         if (x != h->n_buckets && !__ac_iseither(h->flags, x)) {         \
 255             __ac_set_isdel_true(h->flags, x);                           \
 256             --h->size;                                                  \
 257         }                                                               \
 258     }
 259
 260 /* --- BEGIN OF HASH FUNCTIONS --- */
 261
 262 #define kh_int_hash_func(key) (uint32_t)(key)
 263 #define kh_int_hash_equal(a, b) (a == b)
 264 #define kh_int64_hash_func(key) (uint32_t)((key)>>33^(key)^(key)<<11)
 265 #define kh_int64_hash_equal(a, b) (a == b)
 266 static inline khint_t __ac_X31_hash_string(const char *s)
 267 {
 268     khint_t h = *s;
 269     if (h)
 270         {
 271                 for (++s ; *s; ++s)
 272                 {
 273                         h = (h << 5) - h + *s;
 274                 }
 275         }
 276     return h;
 277 }
 278 #define kh_str_hash_func(key) __ac_X31_hash_string(key)
 279 #define kh_str_hash_equal(a, b) (strcmp(a, b) == 0)
 280
 281 /* --- END OF HASH FUNCTIONS --- */
 282
 283 /* Other necessary macros... */
 284
 285 #define khash_t(name) kh_##name##_t
 286
 287 #define kh_init(name) kh_init_##name()
 288 #define kh_destroy(name, h) kh_destroy_##name(h)
 289 #define kh_clear(name, h) kh_clear_##name(h)
 290 #define kh_resize(name, h, s) kh_resize_##name(h, s)
 291 #define kh_put(name, h, k, r) kh_put_##name(h, k, r)
 292 #define kh_get(name, h, k) kh_get_##name(h, k)
 293 #define kh_del(name, h, k) kh_del_##name(h, k)
 294
 295 #define kh_exist(h, x) (!__ac_iseither((h)->flags, (x)))
 296 #define kh_key(h, x) ((h)->keys[x])
 297 #define kh_val(h, x) ((h)->vals[x])
 298 #define kh_value(h, x) ((h)->vals[x])
 299 #define kh_begin(h) (khint_t)(0)
 300 #define kh_end(h) ((h)->n_buckets)
 301 #define kh_size(h) ((h)->size)
 302 #define kh_n_buckets(h) ((h)->n_buckets)
 303
 304 /* More conenient interfaces */
 305
 306 #define KHASH_SET_INIT_INT(name)                                        \
 307     KHASH_INIT(name, uint32_t, char, 0, kh_int_hash_func, kh_int_hash_equal)
 308
 309 #define KHASH_MAP_INIT_INT(name, khval_t)                               \
 310     KHASH_INIT(name, uint32_t, khval_t, 1, kh_int_hash_func, kh_int_hash_equal)
 311
 312 #define KHASH_SET_INIT_INT64(name)                                      \
 313     KHASH_INIT(name, uint64_t, char, 0, kh_int64_hash_func, kh_int64_hash_equal)
 314
 315 #define KHASH_MAP_INIT_INT64(name, khval_t)                             \
 316     KHASH_INIT(name, uint64_t, khval_t, 1, kh_int64_hash_func, kh_int64_hash_equal)
 317
 318 typedef const char *kh_cstr_t;
 319 #define KHASH_SET_INIT_STR(name)                                        \
 320     KHASH_INIT(name, kh_cstr_t, char, 0, kh_str_hash_func, kh_str_hash_equal)
 321
 322 #define KHASH_MAP_INIT_STR(name, khval_t)                               \
 323     KHASH_INIT(name, kh_cstr_t, khval_t, 1, kh_str_hash_func, kh_str_hash_equal)
 324
 325 #endif /* __AC_KHASH_H */