Source code

Download source archive ↓

upstream-dependencies/seqtk/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"
30KHASH_MAP_INIT_INT(32, char)
31int 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	kh_value(h, k) = 10;
37	k = kh_get(32, h, 10);
38	is_missing = (k == kh_end(h));
39	k = kh_get(32, h, 5);
40	kh_del(32, h, k);
41	for (k = kh_begin(h); k != kh_end(h); ++k)
42		if (kh_exist(h, k)) kh_value(h, k) = 1;
43	kh_destroy(32, h);
44	return 0;
45}
46*/
47
48/*
49  2011-12-29 (0.2.7):
50
51    * Minor code clean up; no actual effect.
52
53  2011-09-16 (0.2.6):
54
55	* The capacity is a power of 2. This seems to dramatically improve the
56	  speed for simple keys. Thank Zilong Tan for the suggestion. Reference:
57
58	   - http://code.google.com/p/ulib/
59	   - http://nothings.org/computer/judy/
60
61	* Allow to optionally use linear probing which usually has better
62	  performance for random input. Double hashing is still the default as it
63	  is more robust to certain non-random input.
64
65	* Added Wang's integer hash function (not used by default). This hash
66	  function is more robust to certain non-random input.
67
68  2011-02-14 (0.2.5):
69
70    * Allow to declare global functions.
71
72  2009-09-26 (0.2.4):
73
74    * Improve portability
75
76  2008-09-19 (0.2.3):
77
78	* Corrected the example
79	* Improved interfaces
80
81  2008-09-11 (0.2.2):
82
83	* Improved speed a little in kh_put()
84
85  2008-09-10 (0.2.1):
86
87	* Added kh_clear()
88	* Fixed a compiling error
89
90  2008-09-02 (0.2.0):
91
92	* Changed to token concatenation which increases flexibility.
93
94  2008-08-31 (0.1.2):
95
96	* Fixed a bug in kh_get(), which has not been tested previously.
97
98  2008-08-31 (0.1.1):
99
100	* Added destructor
101*/
102
103
104#ifndef __AC_KHASH_H
105#define __AC_KHASH_H
106
107/*!
108  @header
109
110  Generic hash table library.
111 */
112
113#define AC_VERSION_KHASH_H "0.2.6"
114
115#include <stdlib.h>
116#include <string.h>
117#include <limits.h>
118
119/* compipler specific configuration */
120
121#if UINT_MAX == 0xffffffffu
122typedef unsigned int khint32_t;
123#elif ULONG_MAX == 0xffffffffu
124typedef unsigned long khint32_t;
125#endif
126
127#if ULONG_MAX == ULLONG_MAX
128typedef unsigned long khint64_t;
129#else
130typedef unsigned long long khint64_t;
131#endif
132
133#ifdef _MSC_VER
134#define inline __inline
135#endif
136
137typedef khint32_t khint_t;
138typedef khint_t khiter_t;
139
140#define __ac_isempty(flag, i) ((flag[i>>4]>>((i&0xfU)<<1))&2)
141#define __ac_isdel(flag, i) ((flag[i>>4]>>((i&0xfU)<<1))&1)
142#define __ac_iseither(flag, i) ((flag[i>>4]>>((i&0xfU)<<1))&3)
143#define __ac_set_isdel_false(flag, i) (flag[i>>4]&=~(1ul<<((i&0xfU)<<1)))
144#define __ac_set_isempty_false(flag, i) (flag[i>>4]&=~(2ul<<((i&0xfU)<<1)))
145#define __ac_set_isboth_false(flag, i) (flag[i>>4]&=~(3ul<<((i&0xfU)<<1)))
146#define __ac_set_isdel_true(flag, i) (flag[i>>4]|=1ul<<((i&0xfU)<<1))
147
148#ifdef KHASH_LINEAR
149#define __ac_inc(k, m) 1
150#else
151#define __ac_inc(k, m) (((k)>>3 ^ (k)<<3) | 1) & (m)
152#endif
153
154#define __ac_fsize(m) ((m) < 16? 1 : (m)>>4)
155
156#ifndef kroundup32
157#define kroundup32(x) (--(x), (x)|=(x)>>1, (x)|=(x)>>2, (x)|=(x)>>4, (x)|=(x)>>8, (x)|=(x)>>16, ++(x))
158#endif
159
160static const double __ac_HASH_UPPER = 0.77;
161
162#define __KHASH_TYPE(name, khkey_t, khval_t) \
163	typedef struct { \
164		khint_t n_buckets, size, n_occupied, upper_bound; \
165		khint32_t *flags; \
166		khkey_t *keys; \
167		khval_t *vals; \
168	} kh_##name##_t;
169
170#define KHASH_DECLARE(name, khkey_t, khval_t)		 					\
171	__KHASH_TYPE(name, khkey_t, khval_t) 								\
172	extern kh_##name##_t *kh_init_##name();								\
173	extern void kh_destroy_##name(kh_##name##_t *h);					\
174	extern void kh_clear_##name(kh_##name##_t *h);						\
175	extern khint_t kh_get_##name(const kh_##name##_t *h, khkey_t key); 	\
176	extern void kh_resize_##name(kh_##name##_t *h, khint_t new_n_buckets); \
177	extern khint_t kh_put_##name(kh_##name##_t *h, khkey_t key, int *ret); \
178	extern void kh_del_##name(kh_##name##_t *h, khint_t x);
179
180#define KHASH_INIT2(name, SCOPE, khkey_t, khval_t, kh_is_map, __hash_func, __hash_equal) \
181	__KHASH_TYPE(name, khkey_t, khval_t) 								\
182	SCOPE kh_##name##_t *kh_init_##name() {								\
183		return (kh_##name##_t*)calloc(1, sizeof(kh_##name##_t));		\
184	}																	\
185	SCOPE void kh_destroy_##name(kh_##name##_t *h)						\
186	{																	\
187		if (h) {														\
188			free(h->keys); free(h->flags);								\
189			free(h->vals);												\
190			free(h);													\
191		}																\
192	}																	\
193	SCOPE void kh_clear_##name(kh_##name##_t *h)						\
194	{																	\
195		if (h && h->flags) {											\
196			memset(h->flags, 0xaa, __ac_fsize(h->n_buckets) * sizeof(khint32_t)); \
197			h->size = h->n_occupied = 0;								\
198		}																\
199	}																	\
200	SCOPE khint_t kh_get_##name(const kh_##name##_t *h, khkey_t key) 	\
201	{																	\
202		if (h->n_buckets) {												\
203			khint_t inc, k, i, last, mask;								\
204			mask = h->n_buckets - 1;									\
205			k = __hash_func(key); i = k & mask;							\
206			inc = __ac_inc(k, mask); last = i; /* inc==1 for linear probing */ \
207			while (!__ac_isempty(h->flags, i) && (__ac_isdel(h->flags, i) || !__hash_equal(h->keys[i], key))) { \
208				i = (i + inc) & mask; 									\
209				if (i == last) return h->n_buckets;						\
210			}															\
211			return __ac_iseither(h->flags, i)? h->n_buckets : i;		\
212		} else return 0;												\
213	}																	\
214	SCOPE void kh_resize_##name(kh_##name##_t *h, khint_t new_n_buckets) \
215	{ /* This function uses 0.25*n_bucktes bytes of working space instead of [sizeof(key_t+val_t)+.25]*n_buckets. */ \
216		khint32_t *new_flags = 0;										\
217		khint_t j = 1;													\
218		{																\
219			kroundup32(new_n_buckets); 									\
220			if (new_n_buckets < 4) new_n_buckets = 4;					\
221			if (h->size >= (khint_t)(new_n_buckets * __ac_HASH_UPPER + 0.5)) j = 0;	/* requested size is too small */ \
222			else { /* hash table size to be changed (shrink or expand); rehash */ \
223				new_flags = (khint32_t*)malloc(__ac_fsize(new_n_buckets) * sizeof(khint32_t));	\
224				memset(new_flags, 0xaa, __ac_fsize(new_n_buckets) * sizeof(khint32_t)); \
225				if (h->n_buckets < new_n_buckets) {	/* expand */		\
226					h->keys = (khkey_t*)realloc(h->keys, new_n_buckets * sizeof(khkey_t)); \
227					if (kh_is_map) h->vals = (khval_t*)realloc(h->vals, new_n_buckets * sizeof(khval_t)); \
228				} /* otherwise shrink */								\
229			}															\
230		}																\
231		if (j) { /* rehashing is needed */								\
232			for (j = 0; j != h->n_buckets; ++j) {						\
233				if (__ac_iseither(h->flags, j) == 0) {					\
234					khkey_t key = h->keys[j];							\
235					khval_t val;										\
236					khint_t new_mask;									\
237					new_mask = new_n_buckets - 1; 						\
238					if (kh_is_map) val = h->vals[j];					\
239					__ac_set_isdel_true(h->flags, j);					\
240					while (1) { /* kick-out process; sort of like in Cuckoo hashing */ \
241						khint_t inc, k, i;								\
242						k = __hash_func(key);							\
243						i = k & new_mask;								\
244						inc = __ac_inc(k, new_mask);					\
245						while (!__ac_isempty(new_flags, i)) i = (i + inc) & new_mask; \
246						__ac_set_isempty_false(new_flags, i);			\
247						if (i < h->n_buckets && __ac_iseither(h->flags, i) == 0) { /* kick out the existing element */ \
248							{ khkey_t tmp = h->keys[i]; h->keys[i] = key; key = tmp; } \
249							if (kh_is_map) { khval_t tmp = h->vals[i]; h->vals[i] = val; val = tmp; } \
250							__ac_set_isdel_true(h->flags, i); /* mark it as deleted in the old hash table */ \
251						} else { /* write the element and jump out of the loop */ \
252							h->keys[i] = key;							\
253							if (kh_is_map) h->vals[i] = val;			\
254							break;										\
255						}												\
256					}													\
257				}														\
258			}															\
259			if (h->n_buckets > new_n_buckets) { /* shrink the hash table */ \
260				h->keys = (khkey_t*)realloc(h->keys, new_n_buckets * sizeof(khkey_t)); \
261				if (kh_is_map) h->vals = (khval_t*)realloc(h->vals, new_n_buckets * sizeof(khval_t)); \
262			}															\
263			free(h->flags); /* free the working space */				\
264			h->flags = new_flags;										\
265			h->n_buckets = new_n_buckets;								\
266			h->n_occupied = h->size;									\
267			h->upper_bound = (khint_t)(h->n_buckets * __ac_HASH_UPPER + 0.5); \
268		}																\
269	}																	\
270	SCOPE khint_t kh_put_##name(kh_##name##_t *h, khkey_t key, int *ret) \
271	{																	\
272		khint_t x;														\
273		if (h->n_occupied >= h->upper_bound) { /* update the hash table */ \
274			if (h->n_buckets > (h->size<<1)) kh_resize_##name(h, h->n_buckets - 1); /* clear "deleted" elements */ \
275			else kh_resize_##name(h, h->n_buckets + 1); /* expand the hash table */ \
276		} /* TODO: to implement automatically shrinking; resize() already support shrinking */ \
277		{																\
278			khint_t inc, k, i, site, last, mask = h->n_buckets - 1;		\
279			x = site = h->n_buckets; k = __hash_func(key); i = k & mask; \
280			if (__ac_isempty(h->flags, i)) x = i; /* for speed up */	\
281			else {														\
282				inc = __ac_inc(k, mask); last = i;						\
283				while (!__ac_isempty(h->flags, i) && (__ac_isdel(h->flags, i) || !__hash_equal(h->keys[i], key))) { \
284					if (__ac_isdel(h->flags, i)) site = i;				\
285					i = (i + inc) & mask; 								\
286					if (i == last) { x = site; break; }					\
287				}														\
288				if (x == h->n_buckets) {								\
289					if (__ac_isempty(h->flags, i) && site != h->n_buckets) x = site; \
290					else x = i;											\
291				}														\
292			}															\
293		}																\
294		if (__ac_isempty(h->flags, x)) { /* not present at all */		\
295			h->keys[x] = key;											\
296			__ac_set_isboth_false(h->flags, x);							\
297			++h->size; ++h->n_occupied;									\
298			*ret = 1;													\
299		} else if (__ac_isdel(h->flags, x)) { /* deleted */				\
300			h->keys[x] = key;											\
301			__ac_set_isboth_false(h->flags, x);							\
302			++h->size;													\
303			*ret = 2;													\
304		} else *ret = 0; /* Don't touch h->keys[x] if present and not deleted */ \
305		return x;														\
306	}																	\
307	SCOPE void kh_del_##name(kh_##name##_t *h, khint_t x)				\
308	{																	\
309		if (x != h->n_buckets && !__ac_iseither(h->flags, x)) {			\
310			__ac_set_isdel_true(h->flags, x);							\
311			--h->size;													\
312		}																\
313	}
314
315#define KHASH_INIT(name, khkey_t, khval_t, kh_is_map, __hash_func, __hash_equal) \
316	KHASH_INIT2(name, static inline, khkey_t, khval_t, kh_is_map, __hash_func, __hash_equal)
317
318/* --- BEGIN OF HASH FUNCTIONS --- */
319
320/*! @function
321  @abstract     Integer hash function
322  @param  key   The integer [khint32_t]
323  @return       The hash value [khint_t]
324 */
325#define kh_int_hash_func(key) (khint32_t)(key)
326/*! @function
327  @abstract     Integer comparison function
328 */
329#define kh_int_hash_equal(a, b) ((a) == (b))
330/*! @function
331  @abstract     64-bit integer hash function
332  @param  key   The integer [khint64_t]
333  @return       The hash value [khint_t]
334 */
335#define kh_int64_hash_func(key) (khint32_t)((key)>>33^(key)^(key)<<11)
336/*! @function
337  @abstract     64-bit integer comparison function
338 */
339#define kh_int64_hash_equal(a, b) ((a) == (b))
340/*! @function
341  @abstract     const char* hash function
342  @param  s     Pointer to a null terminated string
343  @return       The hash value
344 */
345static inline khint_t __ac_X31_hash_string(const char *s)
346{
347	khint_t h = *s;
348	if (h) for (++s ; *s; ++s) h = (h << 5) - h + *s;
349	return h;
350}
351/*! @function
352  @abstract     Another interface to const char* hash function
353  @param  key   Pointer to a null terminated string [const char*]
354  @return       The hash value [khint_t]
355 */
356#define kh_str_hash_func(key) __ac_X31_hash_string(key)
357/*! @function
358  @abstract     Const char* comparison function
359 */
360#define kh_str_hash_equal(a, b) (strcmp(a, b) == 0)
361
362static inline khint_t __ac_Wang_hash(khint_t key)
363{
364    key += ~(key << 15);
365    key ^=  (key >> 10);
366    key +=  (key << 3);
367    key ^=  (key >> 6);
368    key += ~(key << 11);
369    key ^=  (key >> 16);
370    return key;
371}
372#define kh_int_hash_func2(k) __ac_Wang_hash((khint_t)key)
373
374/* --- END OF HASH FUNCTIONS --- */
375
376/* Other convenient macros... */
377
378/*!
379  @abstract Type of the hash table.
380  @param  name  Name of the hash table [symbol]
381 */
382#define khash_t(name) kh_##name##_t
383
384/*! @function
385  @abstract     Initiate a hash table.
386  @param  name  Name of the hash table [symbol]
387  @return       Pointer to the hash table [khash_t(name)*]
388 */
389#define kh_init(name) kh_init_##name()
390
391/*! @function
392  @abstract     Destroy a hash table.
393  @param  name  Name of the hash table [symbol]
394  @param  h     Pointer to the hash table [khash_t(name)*]
395 */
396#define kh_destroy(name, h) kh_destroy_##name(h)
397
398/*! @function
399  @abstract     Reset a hash table without deallocating memory.
400  @param  name  Name of the hash table [symbol]
401  @param  h     Pointer to the hash table [khash_t(name)*]
402 */
403#define kh_clear(name, h) kh_clear_##name(h)
404
405/*! @function
406  @abstract     Resize a hash table.
407  @param  name  Name of the hash table [symbol]
408  @param  h     Pointer to the hash table [khash_t(name)*]
409  @param  s     New size [khint_t]
410 */
411#define kh_resize(name, h, s) kh_resize_##name(h, s)
412
413/*! @function
414  @abstract     Insert a key to 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     Key [type of keys]
418  @param  r     Extra return code: 0 if the key is present in the hash table;
419                1 if the bucket is empty (never used); 2 if the element in
420				the bucket has been deleted [int*]
421  @return       Iterator to the inserted element [khint_t]
422 */
423#define kh_put(name, h, k, r) kh_put_##name(h, k, r)
424
425/*! @function
426  @abstract     Retrieve a key from the hash table.
427  @param  name  Name of the hash table [symbol]
428  @param  h     Pointer to the hash table [khash_t(name)*]
429  @param  k     Key [type of keys]
430  @return       Iterator to the found element, or kh_end(h) is the element is absent [khint_t]
431 */
432#define kh_get(name, h, k) kh_get_##name(h, k)
433
434/*! @function
435  @abstract     Remove a key from the hash table.
436  @param  name  Name of the hash table [symbol]
437  @param  h     Pointer to the hash table [khash_t(name)*]
438  @param  k     Iterator to the element to be deleted [khint_t]
439 */
440#define kh_del(name, h, k) kh_del_##name(h, k)
441
442/*! @function
443  @abstract     Test whether a bucket contains data.
444  @param  h     Pointer to the hash table [khash_t(name)*]
445  @param  x     Iterator to the bucket [khint_t]
446  @return       1 if containing data; 0 otherwise [int]
447 */
448#define kh_exist(h, x) (!__ac_iseither((h)->flags, (x)))
449
450/*! @function
451  @abstract     Get key given an iterator
452  @param  h     Pointer to the hash table [khash_t(name)*]
453  @param  x     Iterator to the bucket [khint_t]
454  @return       Key [type of keys]
455 */
456#define kh_key(h, x) ((h)->keys[x])
457
458/*! @function
459  @abstract     Get value given an iterator
460  @param  h     Pointer to the hash table [khash_t(name)*]
461  @param  x     Iterator to the bucket [khint_t]
462  @return       Value [type of values]
463  @discussion   For hash sets, calling this results in segfault.
464 */
465#define kh_val(h, x) ((h)->vals[x])
466
467/*! @function
468  @abstract     Alias of kh_val()
469 */
470#define kh_value(h, x) ((h)->vals[x])
471
472/*! @function
473  @abstract     Get the start iterator
474  @param  h     Pointer to the hash table [khash_t(name)*]
475  @return       The start iterator [khint_t]
476 */
477#define kh_begin(h) (khint_t)(0)
478
479/*! @function
480  @abstract     Get the end iterator
481  @param  h     Pointer to the hash table [khash_t(name)*]
482  @return       The end iterator [khint_t]
483 */
484#define kh_end(h) ((h)->n_buckets)
485
486/*! @function
487  @abstract     Get the number of elements in the hash table
488  @param  h     Pointer to the hash table [khash_t(name)*]
489  @return       Number of elements in the hash table [khint_t]
490 */
491#define kh_size(h) ((h)->size)
492
493/*! @function
494  @abstract     Get the number of buckets in the hash table
495  @param  h     Pointer to the hash table [khash_t(name)*]
496  @return       Number of buckets in the hash table [khint_t]
497 */
498#define kh_n_buckets(h) ((h)->n_buckets)
499
500/* More conenient interfaces */
501
502/*! @function
503  @abstract     Instantiate a hash set containing integer keys
504  @param  name  Name of the hash table [symbol]
505 */
506#define KHASH_SET_INIT_INT(name)										\
507	KHASH_INIT(name, khint32_t, char, 0, kh_int_hash_func, kh_int_hash_equal)
508
509/*! @function
510  @abstract     Instantiate a hash map containing integer keys
511  @param  name  Name of the hash table [symbol]
512  @param  khval_t  Type of values [type]
513 */
514#define KHASH_MAP_INIT_INT(name, khval_t)								\
515	KHASH_INIT(name, khint32_t, khval_t, 1, kh_int_hash_func, kh_int_hash_equal)
516
517/*! @function
518  @abstract     Instantiate a hash map containing 64-bit integer keys
519  @param  name  Name of the hash table [symbol]
520 */
521#define KHASH_SET_INIT_INT64(name)										\
522	KHASH_INIT(name, khint64_t, char, 0, kh_int64_hash_func, kh_int64_hash_equal)
523
524/*! @function
525  @abstract     Instantiate a hash map containing 64-bit integer keys
526  @param  name  Name of the hash table [symbol]
527  @param  khval_t  Type of values [type]
528 */
529#define KHASH_MAP_INIT_INT64(name, khval_t)								\
530	KHASH_INIT(name, khint64_t, khval_t, 1, kh_int64_hash_func, kh_int64_hash_equal)
531
532typedef const char *kh_cstr_t;
533/*! @function
534  @abstract     Instantiate a hash map containing const char* keys
535  @param  name  Name of the hash table [symbol]
536 */
537#define KHASH_SET_INIT_STR(name)										\
538	KHASH_INIT(name, kh_cstr_t, char, 0, kh_str_hash_func, kh_str_hash_equal)
539
540/*! @function
541  @abstract     Instantiate a hash map containing const char* keys
542  @param  name  Name of the hash table [symbol]
543  @param  khval_t  Type of values [type]
544 */
545#define KHASH_MAP_INIT_STR(name, khval_t)								\
546	KHASH_INIT(name, kh_cstr_t, khval_t, 1, kh_str_hash_func, kh_str_hash_equal)
547
548#endif /* __AC_KHASH_H */