# Uploaded samtools version 0.1.14-1.
[samtools.git] / khash.h
1 /* The MIT License
2
3    Copyright (c) 2008, 2009, 2011 by Attractive Chaos <attractor@live.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   2011-02-14 (0.2.5):
51
52     * Allow to declare global functions.
53
54   2009-09-26 (0.2.4):
55
56     * Improve portability
57
58   2008-09-19 (0.2.3):
59
60         * Corrected the example
61         * Improved interfaces
62
63   2008-09-11 (0.2.2):
64
65         * Improved speed a little in kh_put()
66
67   2008-09-10 (0.2.1):
68
69         * Added kh_clear()
70         * Fixed a compiling error
71
72   2008-09-02 (0.2.0):
73
74         * Changed to token concatenation which increases flexibility.
75
76   2008-08-31 (0.1.2):
77
78         * Fixed a bug in kh_get(), which has not been tested previously.
79
80   2008-08-31 (0.1.1):
81
82         * Added destructor
83 */
84
85
86 #ifndef __AC_KHASH_H
87 #define __AC_KHASH_H
88
89 /*!
90   @header
91
92   Generic hash table library.
93
94   @copyright Heng Li
95  */
96
97 #define AC_VERSION_KHASH_H "0.2.5"
98
99 #include <stdlib.h>
100 #include <string.h>
101 #include <limits.h>
102
103 /* compipler specific configuration */
104
105 #if UINT_MAX == 0xffffffffu
106 typedef unsigned int khint32_t;
107 #elif ULONG_MAX == 0xffffffffu
108 typedef unsigned long khint32_t;
109 #endif
110
111 #if ULONG_MAX == ULLONG_MAX
112 typedef unsigned long khint64_t;
113 #else
114 typedef unsigned long long khint64_t;
115 #endif
116
117 #ifdef _MSC_VER
118 #define inline __inline
119 #endif
120
121 typedef khint32_t khint_t;
122 typedef khint_t khiter_t;
123
124 #define __ac_HASH_PRIME_SIZE 32
125 static const khint32_t __ac_prime_list[__ac_HASH_PRIME_SIZE] =
126 {
127   0ul,          3ul,          11ul,         23ul,         53ul,
128   97ul,         193ul,        389ul,        769ul,        1543ul,
129   3079ul,       6151ul,       12289ul,      24593ul,      49157ul,
130   98317ul,      196613ul,     393241ul,     786433ul,     1572869ul,
131   3145739ul,    6291469ul,    12582917ul,   25165843ul,   50331653ul,
132   100663319ul,  201326611ul,  402653189ul,  805306457ul,  1610612741ul,
133   3221225473ul, 4294967291ul
134 };
135
136 #define __ac_isempty(flag, i) ((flag[i>>4]>>((i&0xfU)<<1))&2)
137 #define __ac_isdel(flag, i) ((flag[i>>4]>>((i&0xfU)<<1))&1)
138 #define __ac_iseither(flag, i) ((flag[i>>4]>>((i&0xfU)<<1))&3)
139 #define __ac_set_isdel_false(flag, i) (flag[i>>4]&=~(1ul<<((i&0xfU)<<1)))
140 #define __ac_set_isempty_false(flag, i) (flag[i>>4]&=~(2ul<<((i&0xfU)<<1)))
141 #define __ac_set_isboth_false(flag, i) (flag[i>>4]&=~(3ul<<((i&0xfU)<<1)))
142 #define __ac_set_isdel_true(flag, i) (flag[i>>4]|=1ul<<((i&0xfU)<<1))
143
144 static const double __ac_HASH_UPPER = 0.77;
145
146 #define KHASH_DECLARE(name, khkey_t, khval_t)                                                   \
147         typedef struct {                                                                                                        \
148                 khint_t n_buckets, size, n_occupied, upper_bound;                               \
149                 khint32_t *flags;                                                                                               \
150                 khkey_t *keys;                                                                                                  \
151                 khval_t *vals;                                                                                                  \
152         } kh_##name##_t;                                                                                                        \
153         extern kh_##name##_t *kh_init_##name();                                                         \
154         extern void kh_destroy_##name(kh_##name##_t *h);                                        \
155         extern void kh_clear_##name(kh_##name##_t *h);                                          \
156         extern khint_t kh_get_##name(const kh_##name##_t *h, khkey_t key);      \
157         extern void kh_resize_##name(kh_##name##_t *h, khint_t new_n_buckets); \
158         extern khint_t kh_put_##name(kh_##name##_t *h, khkey_t key, int *ret); \
159         extern void kh_del_##name(kh_##name##_t *h, khint_t x);
160
161 #define KHASH_INIT2(name, SCOPE, khkey_t, khval_t, kh_is_map, __hash_func, __hash_equal) \
162         typedef struct {                                                                                                        \
163                 khint_t n_buckets, size, n_occupied, upper_bound;                               \
164                 khint32_t *flags;                                                                                               \
165                 khkey_t *keys;                                                                                                  \
166                 khval_t *vals;                                                                                                  \
167         } kh_##name##_t;                                                                                                        \
168         SCOPE kh_##name##_t *kh_init_##name() {                                                         \
169                 return (kh_##name##_t*)calloc(1, sizeof(kh_##name##_t));                \
170         }                                                                                                                                       \
171         SCOPE void kh_destroy_##name(kh_##name##_t *h)                                          \
172         {                                                                                                                                       \
173                 if (h) {                                                                                                                \
174                         free(h->keys); free(h->flags);                                                          \
175                         free(h->vals);                                                                                          \
176                         free(h);                                                                                                        \
177                 }                                                                                                                               \
178         }                                                                                                                                       \
179         SCOPE void kh_clear_##name(kh_##name##_t *h)                                            \
180         {                                                                                                                                       \
181                 if (h && h->flags) {                                                                                    \
182                         memset(h->flags, 0xaa, ((h->n_buckets>>4) + 1) * sizeof(khint32_t)); \
183                         h->size = h->n_occupied = 0;                                                            \
184                 }                                                                                                                               \
185         }                                                                                                                                       \
186         SCOPE khint_t kh_get_##name(const kh_##name##_t *h, khkey_t key)        \
187         {                                                                                                                                       \
188                 if (h->n_buckets) {                                                                                             \
189                         khint_t inc, k, i, last;                                                                        \
190                         k = __hash_func(key); i = k % h->n_buckets;                                     \
191                         inc = 1 + k % (h->n_buckets - 1); last = i;                                     \
192                         while (!__ac_isempty(h->flags, i) && (__ac_isdel(h->flags, i) || !__hash_equal(h->keys[i], key))) { \
193                                 if (i + inc >= h->n_buckets) i = i + inc - h->n_buckets; \
194                                 else i += inc;                                                                                  \
195                                 if (i == last) return h->n_buckets;                                             \
196                         }                                                                                                                       \
197                         return __ac_iseither(h->flags, i)? h->n_buckets : i;            \
198                 } else return 0;                                                                                                \
199         }                                                                                                                                       \
200         SCOPE void kh_resize_##name(kh_##name##_t *h, khint_t new_n_buckets) \
201         {                                                                                                                                       \
202                 khint32_t *new_flags = 0;                                                                               \
203                 khint_t j = 1;                                                                                                  \
204                 {                                                                                                                               \
205                         khint_t t = __ac_HASH_PRIME_SIZE - 1;                                           \
206                         while (__ac_prime_list[t] > new_n_buckets) --t;                         \
207                         new_n_buckets = __ac_prime_list[t+1];                                           \
208                         if (h->size >= (khint_t)(new_n_buckets * __ac_HASH_UPPER + 0.5)) j = 0; \
209                         else {                                                                                                          \
210                                 new_flags = (khint32_t*)malloc(((new_n_buckets>>4) + 1) * sizeof(khint32_t));   \
211                                 memset(new_flags, 0xaa, ((new_n_buckets>>4) + 1) * sizeof(khint32_t)); \
212                                 if (h->n_buckets < new_n_buckets) {                                             \
213                                         h->keys = (khkey_t*)realloc(h->keys, new_n_buckets * sizeof(khkey_t)); \
214                                         if (kh_is_map)                                                                          \
215                                                 h->vals = (khval_t*)realloc(h->vals, new_n_buckets * sizeof(khval_t)); \
216                                 }                                                                                                               \
217                         }                                                                                                                       \
218                 }                                                                                                                               \
219                 if (j) {                                                                                                                \
220                         for (j = 0; j != h->n_buckets; ++j) {                                           \
221                                 if (__ac_iseither(h->flags, j) == 0) {                                  \
222                                         khkey_t key = h->keys[j];                                                       \
223                                         khval_t val;                                                                            \
224                                         if (kh_is_map) val = h->vals[j];                                        \
225                                         __ac_set_isdel_true(h->flags, j);                                       \
226                                         while (1) {                                                                                     \
227                                                 khint_t inc, k, i;                                                              \
228                                                 k = __hash_func(key);                                                   \
229                                                 i = k % new_n_buckets;                                                  \
230                                                 inc = 1 + k % (new_n_buckets - 1);                              \
231                                                 while (!__ac_isempty(new_flags, i)) {                   \
232                                                         if (i + inc >= new_n_buckets) i = i + inc - new_n_buckets; \
233                                                         else i += inc;                                                          \
234                                                 }                                                                                               \
235                                                 __ac_set_isempty_false(new_flags, i);                   \
236                                                 if (i < h->n_buckets && __ac_iseither(h->flags, i) == 0) { \
237                                                         { khkey_t tmp = h->keys[i]; h->keys[i] = key; key = tmp; } \
238                                                         if (kh_is_map) { khval_t tmp = h->vals[i]; h->vals[i] = val; val = tmp; } \
239                                                         __ac_set_isdel_true(h->flags, i);                       \
240                                                 } else {                                                                                \
241                                                         h->keys[i] = key;                                                       \
242                                                         if (kh_is_map) h->vals[i] = val;                        \
243                                                         break;                                                                          \
244                                                 }                                                                                               \
245                                         }                                                                                                       \
246                                 }                                                                                                               \
247                         }                                                                                                                       \
248                         if (h->n_buckets > new_n_buckets) {                                                     \
249                                 h->keys = (khkey_t*)realloc(h->keys, new_n_buckets * sizeof(khkey_t)); \
250                                 if (kh_is_map)                                                                                  \
251                                         h->vals = (khval_t*)realloc(h->vals, new_n_buckets * sizeof(khval_t)); \
252                         }                                                                                                                       \
253                         free(h->flags);                                                                                         \
254                         h->flags = new_flags;                                                                           \
255                         h->n_buckets = new_n_buckets;                                                           \
256                         h->n_occupied = h->size;                                                                        \
257                         h->upper_bound = (khint_t)(h->n_buckets * __ac_HASH_UPPER + 0.5); \
258                 }                                                                                                                               \
259         }                                                                                                                                       \
260         SCOPE khint_t kh_put_##name(kh_##name##_t *h, khkey_t key, int *ret) \
261         {                                                                                                                                       \
262                 khint_t x;                                                                                                              \
263                 if (h->n_occupied >= h->upper_bound) {                                                  \
264                         if (h->n_buckets > (h->size<<1)) kh_resize_##name(h, h->n_buckets - 1); \
265                         else kh_resize_##name(h, h->n_buckets + 1);                                     \
266                 }                                                                                                                               \
267                 {                                                                                                                               \
268                         khint_t inc, k, i, site, last;                                                          \
269                         x = site = h->n_buckets; k = __hash_func(key); i = k % h->n_buckets; \
270                         if (__ac_isempty(h->flags, i)) x = i;                                           \
271                         else {                                                                                                          \
272                                 inc = 1 + k % (h->n_buckets - 1); last = i;                             \
273                                 while (!__ac_isempty(h->flags, i) && (__ac_isdel(h->flags, i) || !__hash_equal(h->keys[i], key))) { \
274                                         if (__ac_isdel(h->flags, i)) site = i;                          \
275                                         if (i + inc >= h->n_buckets) i = i + inc - h->n_buckets; \
276                                         else i += inc;                                                                          \
277                                         if (i == last) { x = site; break; }                                     \
278                                 }                                                                                                               \
279                                 if (x == h->n_buckets) {                                                                \
280                                         if (__ac_isempty(h->flags, i) && site != h->n_buckets) x = site; \
281                                         else x = i;                                                                                     \
282                                 }                                                                                                               \
283                         }                                                                                                                       \
284                 }                                                                                                                               \
285                 if (__ac_isempty(h->flags, x)) {                                                                \
286                         h->keys[x] = key;                                                                                       \
287                         __ac_set_isboth_false(h->flags, x);                                                     \
288                         ++h->size; ++h->n_occupied;                                                                     \
289                         *ret = 1;                                                                                                       \
290                 } else if (__ac_isdel(h->flags, x)) {                                                   \
291                         h->keys[x] = key;                                                                                       \
292                         __ac_set_isboth_false(h->flags, x);                                                     \
293                         ++h->size;                                                                                                      \
294                         *ret = 2;                                                                                                       \
295                 } else *ret = 0;                                                                                                \
296                 return x;                                                                                                               \
297         }                                                                                                                                       \
298         SCOPE void kh_del_##name(kh_##name##_t *h, khint_t x)                           \
299         {                                                                                                                                       \
300                 if (x != h->n_buckets && !__ac_iseither(h->flags, x)) {                 \
301                         __ac_set_isdel_true(h->flags, x);                                                       \
302                         --h->size;                                                                                                      \
303                 }                                                                                                                               \
304         }
305
306 #define KHASH_INIT(name, khkey_t, khval_t, kh_is_map, __hash_func, __hash_equal) \
307         KHASH_INIT2(name, static inline, khkey_t, khval_t, kh_is_map, __hash_func, __hash_equal)
308
309 /* --- BEGIN OF HASH FUNCTIONS --- */
310
311 /*! @function
312   @abstract     Integer hash function
313   @param  key   The integer [khint32_t]
314   @return       The hash value [khint_t]
315  */
316 #define kh_int_hash_func(key) (khint32_t)(key)
317 /*! @function
318   @abstract     Integer comparison function
319  */
320 #define kh_int_hash_equal(a, b) ((a) == (b))
321 /*! @function
322   @abstract     64-bit integer hash function
323   @param  key   The integer [khint64_t]
324   @return       The hash value [khint_t]
325  */
326 #define kh_int64_hash_func(key) (khint32_t)((key)>>33^(key)^(key)<<11)
327 /*! @function
328   @abstract     64-bit integer comparison function
329  */
330 #define kh_int64_hash_equal(a, b) ((a) == (b))
331 /*! @function
332   @abstract     const char* hash function
333   @param  s     Pointer to a null terminated string
334   @return       The hash value
335  */
336 static inline khint_t __ac_X31_hash_string(const char *s)
337 {
338         khint_t h = *s;
339         if (h) for (++s ; *s; ++s) h = (h << 5) - h + *s;
340         return h;
341 }
342 /*! @function
343   @abstract     Another interface to const char* hash function
344   @param  key   Pointer to a null terminated string [const char*]
345   @return       The hash value [khint_t]
346  */
347 #define kh_str_hash_func(key) __ac_X31_hash_string(key)
348 /*! @function
349   @abstract     Const char* comparison function
350  */
351 #define kh_str_hash_equal(a, b) (strcmp(a, b) == 0)
352
353 /* --- END OF HASH FUNCTIONS --- */
354
355 /* Other necessary macros... */
356
357 /*!
358   @abstract Type of the hash table.
359   @param  name  Name of the hash table [symbol]
360  */
361 #define khash_t(name) kh_##name##_t
362
363 /*! @function
364   @abstract     Initiate a hash table.
365   @param  name  Name of the hash table [symbol]
366   @return       Pointer to the hash table [khash_t(name)*]
367  */
368 #define kh_init(name) kh_init_##name()
369
370 /*! @function
371   @abstract     Destroy a hash table.
372   @param  name  Name of the hash table [symbol]
373   @param  h     Pointer to the hash table [khash_t(name)*]
374  */
375 #define kh_destroy(name, h) kh_destroy_##name(h)
376
377 /*! @function
378   @abstract     Reset a hash table without deallocating memory.
379   @param  name  Name of the hash table [symbol]
380   @param  h     Pointer to the hash table [khash_t(name)*]
381  */
382 #define kh_clear(name, h) kh_clear_##name(h)
383
384 /*! @function
385   @abstract     Resize a hash table.
386   @param  name  Name of the hash table [symbol]
387   @param  h     Pointer to the hash table [khash_t(name)*]
388   @param  s     New size [khint_t]
389  */
390 #define kh_resize(name, h, s) kh_resize_##name(h, s)
391
392 /*! @function
393   @abstract     Insert a key to the hash table.
394   @param  name  Name of the hash table [symbol]
395   @param  h     Pointer to the hash table [khash_t(name)*]
396   @param  k     Key [type of keys]
397   @param  r     Extra return code: 0 if the key is present in the hash table;
398                 1 if the bucket is empty (never used); 2 if the element in
399                                 the bucket has been deleted [int*]
400   @return       Iterator to the inserted element [khint_t]
401  */
402 #define kh_put(name, h, k, r) kh_put_##name(h, k, r)
403
404 /*! @function
405   @abstract     Retrieve a key from the hash table.
406   @param  name  Name of the hash table [symbol]
407   @param  h     Pointer to the hash table [khash_t(name)*]
408   @param  k     Key [type of keys]
409   @return       Iterator to the found element, or kh_end(h) is the element is absent [khint_t]
410  */
411 #define kh_get(name, h, k) kh_get_##name(h, k)
412
413 /*! @function
414   @abstract     Remove a key from the hash table.
415   @param  name  Name of the hash table [symbol]
416   @param  h     Pointer to the hash table [khash_t(name)*]
417   @param  k     Iterator to the element to be deleted [khint_t]
418  */
419 #define kh_del(name, h, k) kh_del_##name(h, k)
420
421
422 /*! @function
423   @abstract     Test whether a bucket contains data.
424   @param  h     Pointer to the hash table [khash_t(name)*]
425   @param  x     Iterator to the bucket [khint_t]
426   @return       1 if containing data; 0 otherwise [int]
427  */
428 #define kh_exist(h, x) (!__ac_iseither((h)->flags, (x)))
429
430 /*! @function
431   @abstract     Get key given an iterator
432   @param  h     Pointer to the hash table [khash_t(name)*]
433   @param  x     Iterator to the bucket [khint_t]
434   @return       Key [type of keys]
435  */
436 #define kh_key(h, x) ((h)->keys[x])
437
438 /*! @function
439   @abstract     Get value given an iterator
440   @param  h     Pointer to the hash table [khash_t(name)*]
441   @param  x     Iterator to the bucket [khint_t]
442   @return       Value [type of values]
443   @discussion   For hash sets, calling this results in segfault.
444  */
445 #define kh_val(h, x) ((h)->vals[x])
446
447 /*! @function
448   @abstract     Alias of kh_val()
449  */
450 #define kh_value(h, x) ((h)->vals[x])
451
452 /*! @function
453   @abstract     Get the start iterator
454   @param  h     Pointer to the hash table [khash_t(name)*]
455   @return       The start iterator [khint_t]
456  */
457 #define kh_begin(h) (khint_t)(0)
458
459 /*! @function
460   @abstract     Get the end iterator
461   @param  h     Pointer to the hash table [khash_t(name)*]
462   @return       The end iterator [khint_t]
463  */
464 #define kh_end(h) ((h)->n_buckets)
465
466 /*! @function
467   @abstract     Get the number of elements in the hash table
468   @param  h     Pointer to the hash table [khash_t(name)*]
469   @return       Number of elements in the hash table [khint_t]
470  */
471 #define kh_size(h) ((h)->size)
472
473 /*! @function
474   @abstract     Get the number of buckets in the hash table
475   @param  h     Pointer to the hash table [khash_t(name)*]
476   @return       Number of buckets in the hash table [khint_t]
477  */
478 #define kh_n_buckets(h) ((h)->n_buckets)
479
480 /* More conenient interfaces */
481
482 /*! @function
483   @abstract     Instantiate a hash set containing integer keys
484   @param  name  Name of the hash table [symbol]
485  */
486 #define KHASH_SET_INIT_INT(name)                                                                                \
487         KHASH_INIT(name, khint32_t, char, 0, kh_int_hash_func, kh_int_hash_equal)
488
489 /*! @function
490   @abstract     Instantiate a hash map containing integer keys
491   @param  name  Name of the hash table [symbol]
492   @param  khval_t  Type of values [type]
493  */
494 #define KHASH_MAP_INIT_INT(name, khval_t)                                                               \
495         KHASH_INIT(name, khint32_t, khval_t, 1, kh_int_hash_func, kh_int_hash_equal)
496
497 /*! @function
498   @abstract     Instantiate a hash map containing 64-bit integer keys
499   @param  name  Name of the hash table [symbol]
500  */
501 #define KHASH_SET_INIT_INT64(name)                                                                              \
502         KHASH_INIT(name, khint64_t, char, 0, kh_int64_hash_func, kh_int64_hash_equal)
503
504 /*! @function
505   @abstract     Instantiate a hash map containing 64-bit integer keys
506   @param  name  Name of the hash table [symbol]
507   @param  khval_t  Type of values [type]
508  */
509 #define KHASH_MAP_INIT_INT64(name, khval_t)                                                             \
510         KHASH_INIT(name, khint64_t, khval_t, 1, kh_int64_hash_func, kh_int64_hash_equal)
511
512 typedef const char *kh_cstr_t;
513 /*! @function
514   @abstract     Instantiate a hash map containing const char* keys
515   @param  name  Name of the hash table [symbol]
516  */
517 #define KHASH_SET_INIT_STR(name)                                                                                \
518         KHASH_INIT(name, kh_cstr_t, char, 0, kh_str_hash_func, kh_str_hash_equal)
519
520 /*! @function
521   @abstract     Instantiate a hash map containing const char* keys
522   @param  name  Name of the hash table [symbol]
523   @param  khval_t  Type of values [type]
524  */
525 #define KHASH_MAP_INIT_STR(name, khval_t)                                                               \
526         KHASH_INIT(name, kh_cstr_t, khval_t, 1, kh_str_hash_func, kh_str_hash_equal)
527
528 #endif /* __AC_KHASH_H */