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             if (new_n_buckets < __ac_prime_list[__ac_HASH_PRIME_SIZE - 1]) { \
 159                 while (__ac_prime_list[t] > new_n_buckets) {            \
 160                     --t;                                                \
 161                 }                                                       \
 162                 new_n_buckets = __ac_prime_list[t + 1];                 \
 163             }                                                           \
 164             if (h->size >= (khint_t)(new_n_buckets * __ac_HASH_UPPER + 0.5)) j = 0; \
 165             else {                                                      \
 166                 new_flags = (uint32_t*)real_malloc(((new_n_buckets>>4) + 1) * sizeof(uint32_t)); \
 167                 memset(new_flags, 0xaa, ((new_n_buckets>>4) + 1) * sizeof(uint32_t)); \
 168                 if (h->n_buckets < new_n_buckets) {                     \
 169                     h->keys = (khkey_t*)realloc(h->keys, new_n_buckets * sizeof(khkey_t)); \
 170                     if (kh_is_map)                                      \
 171                         h->vals = (khval_t*)realloc(h->vals, new_n_buckets * sizeof(khval_t)); \
 172                 }                                                       \
 173             }                                                           \
 174         }                                                               \
 175         if (j) {                                                        \
 176             for (j = 0; j != h->n_buckets; ++j) {                       \
 177                 if (__ac_iseither(h->flags, j) == 0) {                  \
 178                     khkey_t key = h->keys[j];                           \
 179                     khval_t val;                                        \
 180                     if (kh_is_map) val = h->vals[j];                    \
 181                     __ac_set_isdel_true(h->flags, j);                   \
 182                     while (1) {                                         \
 183                         khint_t inc, k, i;                              \
 184                         k = __hash_func(key);                           \
 185                         i = k % new_n_buckets;                          \
 186                         inc = 1 + k % (new_n_buckets - 1);              \
 187                         while (!__ac_isempty(new_flags, i)) {           \
 188                             if (i + inc >= new_n_buckets) i = i + inc - new_n_buckets; \
 189                             else i += inc;                              \
 190                         }                                               \
 191                         __ac_set_isempty_false(new_flags, i);           \
 192                         if (i < h->n_buckets && __ac_iseither(h->flags, i) == 0) { \
 193                             { khkey_t tmp = h->keys[i]; h->keys[i] = key; key = tmp; } \
 194                             if (kh_is_map) { khval_t tmp = h->vals[i]; h->vals[i] = val; val = tmp; } \
 195                             __ac_set_isdel_true(h->flags, i);           \
 196                         } else {                                        \
 197                             h->keys[i] = key;                           \
 198                             if (kh_is_map) h->vals[i] = val;            \
 199                             break;                                      \
 200                         }                                               \
 201                     }                                                   \
 202                 }                                                       \
 203             }                                                           \
 204             if (h->n_buckets > new_n_buckets) {                         \
 205                 h->keys = (khkey_t*)realloc(h->keys, new_n_buckets * sizeof(khkey_t)); \
 206                 if (kh_is_map)                                          \
 207                     h->vals = (khval_t*)realloc(h->vals, new_n_buckets * sizeof(khval_t)); \
 208             }                                                           \
 209             free(h->flags);                                             \
 210             h->flags = new_flags;                                       \
 211             h->n_buckets = new_n_buckets;                               \
 212             h->n_occupied = h->size;                                    \
 213             h->upper_bound = (khint_t)(h->n_buckets * __ac_HASH_UPPER + 0.5); \
 214         }                                                               \
 215     }                                                                   \
 216     static inline khint_t kh_put_##name(kh_##name##_t *h, khkey_t key, int *ret) \
 217     {                                                                   \
 218         khint_t x;                                                      \
 219         if (h->n_occupied >= h->upper_bound) {                          \
 220             if (h->n_buckets > (h->size<<1)) kh_resize_##name(h, h->n_buckets - 1); \
 221             else kh_resize_##name(h, h->n_buckets + 1);                 \
 222         }                                                               \
 223         {                                                               \
 224             khint_t inc, k, i, site, last;                              \
 225             x = site = h->n_buckets; k = __hash_func(key); i = k % h->n_buckets; \
 226             if (__ac_isempty(h->flags, i)) x = i;                       \
 227             else {                                                      \
 228                 inc = 1 + k % (h->n_buckets - 1); last = i;             \
 229                 while (!__ac_isempty(h->flags, i) && (__ac_isdel(h->flags, i) || !__hash_equal(h->keys[i], key))) { \
 230                     if (__ac_isdel(h->flags, i)) site = i;              \
 231                     if (i + inc >= h->n_buckets) i = i + inc - h->n_buckets; \
 232                     else i += inc;                                      \
 233                     if (i == last) { x = site; break; }                 \
 234                 }                                                       \
 235                 if (x == h->n_buckets) {                                \
 236                     if (__ac_isempty(h->flags, i) && site != h->n_buckets) x = site; \
 237                     else x = i;                                         \
 238                 }                                                       \
 239             }                                                           \
 240         }                                                               \
 241         if (__ac_isempty(h->flags, x)) {                                \
 242             h->keys[x] = key;                                           \
 243             __ac_set_isboth_false(h->flags, x);                         \
 244             ++h->size; ++h->n_occupied;                                 \
 245             *ret = 1;                                                   \
 246         } else if (__ac_isdel(h->flags, x)) {                           \
 247             h->keys[x] = key;                                           \
 248             __ac_set_isboth_false(h->flags, x);                         \
 249             ++h->size;                                                  \
 250             *ret = 2;                                                   \
 251         } else *ret = 0;                                                \
 252         return x;                                                       \
 253     }                                                                   \
 254     static inline void kh_del_##name(kh_##name##_t *h, khint_t x)       \
 255     {                                                                   \
 256         if (x != h->n_buckets && !__ac_iseither(h->flags, x)) {         \
 257             __ac_set_isdel_true(h->flags, x);                           \
 258             --h->size;                                                  \
 259         }                                                               \
 260     }
 261
 262 /* --- BEGIN OF HASH FUNCTIONS --- */
 263
 264 #define kh_int_hash_func(key) (uint32_t)(key)
 265 #define kh_int_hash_equal(a, b) (a == b)
 266 #define kh_int64_hash_func(key) (uint32_t)((key)>>33^(key)^(key)<<11)
 267 #define kh_int64_hash_equal(a, b) (a == b)
 268 static inline khint_t __ac_X31_hash_string(const char *s)
 269 {
 270     khint_t h = *s;
 271     if (h)
 272         {
 273                 for (++s ; *s; ++s)
 274                 {
 275                         h = (h << 5) - h + *s;
 276                 }
 277         }
 278     return h;
 279 }
 280 #define kh_str_hash_func(key) __ac_X31_hash_string(key)
 281 #define kh_str_hash_equal(a, b) (strcmp(a, b) == 0)
 282
 283 /* --- END OF HASH FUNCTIONS --- */
 284
 285 /* Other necessary macros... */
 286
 287 #define khash_t(name) kh_##name##_t
 288
 289 #define kh_init(name) kh_init_##name()
 290 #define kh_destroy(name, h) kh_destroy_##name(h)
 291 #define kh_clear(name, h) kh_clear_##name(h)
 292 #define kh_resize(name, h, s) kh_resize_##name(h, s)
 293 #define kh_put(name, h, k, r) kh_put_##name(h, k, r)
 294 #define kh_get(name, h, k) kh_get_##name(h, k)
 295 #define kh_del(name, h, k) kh_del_##name(h, k)
 296
 297 #define kh_exist(h, x) (!__ac_iseither((h)->flags, (x)))
 298 #define kh_key(h, x) ((h)->keys[x])
 299 #define kh_val(h, x) ((h)->vals[x])
 300 #define kh_value(h, x) ((h)->vals[x])
 301 #define kh_begin(h) (khint_t)(0)
 302 #define kh_end(h) ((h)->n_buckets)
 303 #define kh_size(h) ((h)->size)
 304 #define kh_n_buckets(h) ((h)->n_buckets)
 305
 306 /* More conenient interfaces */
 307
 308 #define KHASH_SET_INIT_INT(name)                                        \
 309     KHASH_INIT(name, uint32_t, char, 0, kh_int_hash_func, kh_int_hash_equal)
 310
 311 #define KHASH_MAP_INIT_INT(name, khval_t)                               \
 312     KHASH_INIT(name, uint32_t, khval_t, 1, kh_int_hash_func, kh_int_hash_equal)
 313
 314 #define KHASH_SET_INIT_INT64(name)                                      \
 315     KHASH_INIT(name, uint64_t, char, 0, kh_int64_hash_func, kh_int64_hash_equal)
 316
 317 #define KHASH_MAP_INIT_INT64(name, khval_t)                             \
 318     KHASH_INIT(name, uint64_t, khval_t, 1, kh_int64_hash_func, kh_int64_hash_equal)
 319
 320 typedef const char *kh_cstr_t;
 321 #define KHASH_SET_INIT_STR(name)                                        \
 322     KHASH_INIT(name, kh_cstr_t, char, 0, kh_str_hash_func, kh_str_hash_equal)
 323
 324 #define KHASH_MAP_INIT_STR(name, khval_t)                               \
 325     KHASH_INIT(name, kh_cstr_t, khval_t, 1, kh_str_hash_func, kh_str_hash_equal)
 326
 327 #endif /* __AC_KHASH_H */