[libgit2.git] / src / khash.h

/* The MIT License

   Copyright (c) 2008, 2009, 2011 by Attractive Chaos <attractor@live.co.uk>

   Permission is hereby granted, free of charge, to any person obtaining
   a copy of this software and associated documentation files (the
   "Software"), to deal in the Software without restriction, including
   without limitation the rights to use, copy, modify, merge, publish,
   distribute, sublicense, and/or sell copies of the Software, and to
   permit persons to whom the Software is furnished to do so, subject to
   the following conditions:

   The above copyright notice and this permission notice shall be
   included in all copies or substantial portions of the Software.

   THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND,
   EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF
   MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND
   NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS
   BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN
   ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN
   CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE
   SOFTWARE.
*/

/*
  An example:

#include "khash.h"
KHASH_MAP_INIT_INT(32, char)
int main() {
	int ret, is_missing;
	khiter_t k;
	khash_t(32) *h = kh_init(32);
	k = kh_put(32, h, 5, &ret);
	kh_value(h, k) = 10;
	k = kh_get(32, h, 10);
	is_missing = (k == kh_end(h));
	k = kh_get(32, h, 5);
	kh_del(32, h, k);
	for (k = kh_begin(h); k != kh_end(h); ++k)
		if (kh_exist(h, k)) kh_value(h, k) = 1;
	kh_destroy(32, h);
	return 0;
}
*/

/*
  2011-12-29 (0.2.7):

    * Minor code clean up; no actual effect.

  2011-09-16 (0.2.6):

	* The capacity is a power of 2. This seems to dramatically improve the
	  speed for simple keys. Thank Zilong Tan for the suggestion. Reference:

	   - http://code.google.com/p/ulib/
	   - http://nothings.org/computer/judy/

	* Allow to optionally use linear probing which usually has better
	  performance for random input. Double hashing is still the default as it
	  is more robust to certain non-random input.

	* Added Wang's integer hash function (not used by default). This hash
	  function is more robust to certain non-random input.

  2011-02-14 (0.2.5):

    * Allow to declare global functions.

  2009-09-26 (0.2.4):

    * Improve portability

  2008-09-19 (0.2.3):

	* Corrected the example
	* Improved interfaces

  2008-09-11 (0.2.2):

	* Improved speed a little in kh_put()

  2008-09-10 (0.2.1):

	* Added kh_clear()
	* Fixed a compiling error

  2008-09-02 (0.2.0):

	* Changed to token concatenation which increases flexibility.

  2008-08-31 (0.1.2):

	* Fixed a bug in kh_get(), which has not been tested previously.

  2008-08-31 (0.1.1):

	* Added destructor
*/


#ifndef __AC_KHASH_H
#define __AC_KHASH_H

/*!
  @header

  Generic hash table library.
 */

#define AC_VERSION_KHASH_H "0.2.6"

#include <stdlib.h>
#include <string.h>
#include <limits.h>

/* compipler specific configuration */

#if UINT_MAX == 0xffffffffu
typedef unsigned int khint32_t;
#elif ULONG_MAX == 0xffffffffu
typedef unsigned long khint32_t;
#endif

#if ULONG_MAX == ULLONG_MAX
typedef unsigned long khint64_t;
#else
typedef unsigned long long khint64_t;
#endif

#ifdef _MSC_VER
#define kh_inline __inline
#else
#define kh_inline inline
#endif

typedef khint32_t khint_t;
typedef khint_t khiter_t;

#define __ac_isempty(flag, i) ((flag[i>>4]>>((i&0xfU)<<1))&2)
#define __ac_isdel(flag, i) ((flag[i>>4]>>((i&0xfU)<<1))&1)
#define __ac_iseither(flag, i) ((flag[i>>4]>>((i&0xfU)<<1))&3)
#define __ac_set_isdel_false(flag, i) (flag[i>>4]&=~(1ul<<((i&0xfU)<<1)))
#define __ac_set_isempty_false(flag, i) (flag[i>>4]&=~(2ul<<((i&0xfU)<<1)))
#define __ac_set_isboth_false(flag, i) (flag[i>>4]&=~(3ul<<((i&0xfU)<<1)))
#define __ac_set_isdel_true(flag, i) (flag[i>>4]|=1ul<<((i&0xfU)<<1))

#ifdef KHASH_LINEAR
#define __ac_inc(k, m) 1
#else
#define __ac_inc(k, m) (((k)>>3 ^ (k)<<3) | 1) & (m)
#endif

#define __ac_fsize(m) ((m) < 16? 1 : (m)>>4)

#ifndef kroundup32
#define kroundup32(x) (--(x), (x)|=(x)>>1, (x)|=(x)>>2, (x)|=(x)>>4, (x)|=(x)>>8, (x)|=(x)>>16, ++(x))
#endif

#ifndef kcalloc
#define kcalloc(N,Z) calloc(N,Z)
#endif
#ifndef kmalloc
#define kmalloc(Z) malloc(Z)
#endif
#ifndef krealloc
#define krealloc(P,Z) realloc(P,Z)
#endif
#ifndef kfree
#define kfree(P) free(P)
#endif

static const double __ac_HASH_UPPER = 0.77;

#define __KHASH_TYPE(name, khkey_t, khval_t) \
	typedef struct { \
		khint_t n_buckets, size, n_occupied, upper_bound; \
		khint32_t *flags; \
		khkey_t *keys; \
		khval_t *vals; \
	} kh_##name##_t;

#define __KHASH_PROTOTYPES(name, khkey_t, khval_t)	 					\
	extern kh_##name##_t *kh_init_##name(void);							\
	extern void kh_destroy_##name(kh_##name##_t *h);					\
	extern void kh_clear_##name(kh_##name##_t *h);						\
	extern khint_t kh_get_##name(const kh_##name##_t *h, khkey_t key); 	\
	extern int kh_resize_##name(kh_##name##_t *h, khint_t new_n_buckets); \
	extern khint_t kh_put_##name(kh_##name##_t *h, khkey_t key, int *ret); \
	extern void kh_del_##name(kh_##name##_t *h, khint_t x);

#define __KHASH_IMPL(name, SCOPE, khkey_t, khval_t, kh_is_map, __hash_func, __hash_equal) \
	SCOPE kh_##name##_t *kh_init_##name(void) {							\
		return (kh_##name##_t*)kcalloc(1, sizeof(kh_##name##_t));		\
	}																	\
	SCOPE void kh_destroy_##name(kh_##name##_t *h)						\
	{																	\
		if (h) {														\
			kfree((void *)h->keys); kfree(h->flags);					\
			kfree((void *)h->vals);										\
			kfree(h);													\
		}																\
	}																	\
	SCOPE void kh_clear_##name(kh_##name##_t *h)						\
	{																	\
		if (h && h->flags) {											\
			memset(h->flags, 0xaa, __ac_fsize(h->n_buckets) * sizeof(khint32_t)); \
			h->size = h->n_occupied = 0;								\
		}																\
	}																	\
	SCOPE khint_t kh_get_##name(const kh_##name##_t *h, khkey_t key) 	\
	{																	\
		if (h->n_buckets) {												\
			khint_t inc, k, i, last, mask;								\
			mask = h->n_buckets - 1;									\
			k = __hash_func(key); i = k & mask;							\
			inc = __ac_inc(k, mask); last = i; /* inc==1 for linear probing */ \
			while (!__ac_isempty(h->flags, i) && (__ac_isdel(h->flags, i) || !__hash_equal(h->keys[i], key))) { \
				i = (i + inc) & mask; 									\
				if (i == last) return h->n_buckets;						\
			}															\
			return __ac_iseither(h->flags, i)? h->n_buckets : i;		\
		} else return 0;												\
	}																	\
	SCOPE int kh_resize_##name(kh_##name##_t *h, khint_t new_n_buckets) \
	{ /* This function uses 0.25*n_bucktes bytes of working space instead of [sizeof(key_t+val_t)+.25]*n_buckets. */ \
		khint32_t *new_flags = 0;										\
		khint_t j = 1;													\
		{																\
			kroundup32(new_n_buckets); 									\
			if (new_n_buckets < 4) new_n_buckets = 4;					\
			if (h->size >= (khint_t)(new_n_buckets * __ac_HASH_UPPER + 0.5)) j = 0;	/* requested size is too small */ \
			else { /* hash table size to be changed (shrink or expand); rehash */ \
				new_flags = (khint32_t*)kmalloc(__ac_fsize(new_n_buckets) * sizeof(khint32_t));	\
				if (!new_flags) return -1;								\
				memset(new_flags, 0xaa, __ac_fsize(new_n_buckets) * sizeof(khint32_t)); \
				if (h->n_buckets < new_n_buckets) {	/* expand */		\
					khkey_t *new_keys = (khkey_t*)krealloc((void *)h->keys, new_n_buckets * sizeof(khkey_t)); \
					if (!new_keys) return -1;							\
					h->keys = new_keys;									\
					if (kh_is_map) {									\
						khval_t *new_vals = (khval_t*)krealloc((void *)h->vals, new_n_buckets * sizeof(khval_t)); \
						if (!new_vals) return -1;						\
						h->vals = new_vals;								\
					}													\
				} /* otherwise shrink */								\
			}															\
		}																\
		if (j) { /* rehashing is needed */								\
			for (j = 0; j != h->n_buckets; ++j) {						\
				if (__ac_iseither(h->flags, j) == 0) {					\
					khkey_t key = h->keys[j];							\
					khval_t val;										\
					khint_t new_mask;									\
					new_mask = new_n_buckets - 1; 						\
					if (kh_is_map) val = h->vals[j];					\
					__ac_set_isdel_true(h->flags, j);					\
					while (1) { /* kick-out process; sort of like in Cuckoo hashing */ \
						khint_t inc, k, i;								\
						k = __hash_func(key);							\
						i = k & new_mask;								\
						inc = __ac_inc(k, new_mask);					\
						while (!__ac_isempty(new_flags, i)) i = (i + inc) & new_mask; \
						__ac_set_isempty_false(new_flags, i);			\
						if (i < h->n_buckets && __ac_iseither(h->flags, i) == 0) { /* kick out the existing element */ \
							{ khkey_t tmp = h->keys[i]; h->keys[i] = key; key = tmp; } \
							if (kh_is_map) { khval_t tmp = h->vals[i]; h->vals[i] = val; val = tmp; } \
							__ac_set_isdel_true(h->flags, i); /* mark it as deleted in the old hash table */ \
						} else { /* write the element and jump out of the loop */ \
							h->keys[i] = key;							\
							if (kh_is_map) h->vals[i] = val;			\
							break;										\
						}												\
					}													\
				}														\
			}															\
			if (h->n_buckets > new_n_buckets) { /* shrink the hash table */ \
				h->keys = (khkey_t*)krealloc((void *)h->keys, new_n_buckets * sizeof(khkey_t)); \
				if (kh_is_map) h->vals = (khval_t*)krealloc((void *)h->vals, new_n_buckets * sizeof(khval_t)); \
			}															\
			kfree(h->flags); /* free the working space */				\
			h->flags = new_flags;										\
			h->n_buckets = new_n_buckets;								\
			h->n_occupied = h->size;									\
			h->upper_bound = (khint_t)(h->n_buckets * __ac_HASH_UPPER + 0.5); \
		}																\
		return 0;														\
	}																	\
	SCOPE khint_t kh_put_##name(kh_##name##_t *h, khkey_t key, int *ret) \
	{																	\
		khint_t x;														\
		if (h->n_occupied >= h->upper_bound) { /* update the hash table */ \
			if (h->n_buckets > (h->size<<1)) {							\
				if (kh_resize_##name(h, h->n_buckets - 1) < 0) { /* clear "deleted" elements */ \
					*ret = -1; return h->n_buckets;						\
				}														\
			} else if (kh_resize_##name(h, h->n_buckets + 1) < 0) { /* expand the hash table */ \
				*ret = -1; return h->n_buckets;							\
			}															\
		} /* TODO: to implement automatically shrinking; resize() already support shrinking */ \
		{																\
			khint_t inc, k, i, site, last, mask = h->n_buckets - 1;		\
			x = site = h->n_buckets; k = __hash_func(key); i = k & mask; \
			if (__ac_isempty(h->flags, i)) x = i; /* for speed up */	\
			else {														\
				inc = __ac_inc(k, mask); last = i;						\
				while (!__ac_isempty(h->flags, i) && (__ac_isdel(h->flags, i) || !__hash_equal(h->keys[i], key))) { \
					if (__ac_isdel(h->flags, i)) site = i;				\
					i = (i + inc) & mask; 								\
					if (i == last) { x = site; break; }					\
				}														\
				if (x == h->n_buckets) {								\
					if (__ac_isempty(h->flags, i) && site != h->n_buckets) x = site; \
					else x = i;											\
				}														\
			}															\
		}																\
		if (__ac_isempty(h->flags, x)) { /* not present at all */		\
			h->keys[x] = key;											\
			__ac_set_isboth_false(h->flags, x);							\
			++h->size; ++h->n_occupied;									\
			*ret = 1;													\
		} else if (__ac_isdel(h->flags, x)) { /* deleted */				\
			h->keys[x] = key;											\
			__ac_set_isboth_false(h->flags, x);							\
			++h->size;													\
			*ret = 2;													\
		} else *ret = 0; /* Don't touch h->keys[x] if present and not deleted */ \
		return x;														\
	}																	\
	SCOPE void kh_del_##name(kh_##name##_t *h, khint_t x)				\
	{																	\
		if (x != h->n_buckets && !__ac_iseither(h->flags, x)) {			\
			__ac_set_isdel_true(h->flags, x);							\
			--h->size;													\
		}																\
	}

#define KHASH_DECLARE(name, khkey_t, khval_t)		 					\
	__KHASH_TYPE(name, khkey_t, khval_t) 								\
	__KHASH_PROTOTYPES(name, khkey_t, khval_t)

#define KHASH_INIT2(name, SCOPE, khkey_t, khval_t, kh_is_map, __hash_func, __hash_equal) \
	__KHASH_TYPE(name, khkey_t, khval_t) 								\
	__KHASH_IMPL(name, SCOPE, khkey_t, khval_t, kh_is_map, __hash_func, __hash_equal)

#define KHASH_INIT(name, khkey_t, khval_t, kh_is_map, __hash_func, __hash_equal) \
	KHASH_INIT2(name, static kh_inline, khkey_t, khval_t, kh_is_map, __hash_func, __hash_equal)

/* --- BEGIN OF HASH FUNCTIONS --- */

/*! @function
  @abstract     Integer hash function
  @param  key   The integer [khint32_t]
  @return       The hash value [khint_t]
 */
#define kh_int_hash_func(key) (khint32_t)(key)
/*! @function
  @abstract     Integer comparison function
 */
#define kh_int_hash_equal(a, b) ((a) == (b))
/*! @function
  @abstract     64-bit integer hash function
  @param  key   The integer [khint64_t]
  @return       The hash value [khint_t]
 */
#define kh_int64_hash_func(key) (khint32_t)((key)>>33^(key)^(key)<<11)
/*! @function
  @abstract     64-bit integer comparison function
 */
#define kh_int64_hash_equal(a, b) ((a) == (b))
/*! @function
  @abstract     const char* hash function
  @param  s     Pointer to a null terminated string
  @return       The hash value
 */
static kh_inline khint_t __ac_X31_hash_string(const char *s)
{
	khint_t h = (khint_t)*s;
	if (h) for (++s ; *s; ++s) h = (h << 5) - h + (khint_t)*s;
	return h;
}
/*! @function
  @abstract     Another interface to const char* hash function
  @param  key   Pointer to a null terminated string [const char*]
  @return       The hash value [khint_t]
 */
#define kh_str_hash_func(key) __ac_X31_hash_string(key)
/*! @function
  @abstract     Const char* comparison function
 */
#define kh_str_hash_equal(a, b) (strcmp(a, b) == 0)

static kh_inline khint_t __ac_Wang_hash(khint_t key)
{
    key += ~(key << 15);
    key ^=  (key >> 10);
    key +=  (key << 3);
    key ^=  (key >> 6);
    key += ~(key << 11);
    key ^=  (key >> 16);
    return key;
}
#define kh_int_hash_func2(k) __ac_Wang_hash((khint_t)key)

/* --- END OF HASH FUNCTIONS --- */

/* Other convenient macros... */

/*!
  @abstract Type of the hash table.
  @param  name  Name of the hash table [symbol]
 */
#define khash_t(name) kh_##name##_t

/*! @function
  @abstract     Initiate a hash table.
  @param  name  Name of the hash table [symbol]
  @return       Pointer to the hash table [khash_t(name)*]
 */
#define kh_init(name) kh_init_##name()

/*! @function
  @abstract     Destroy a hash table.
  @param  name  Name of the hash table [symbol]
  @param  h     Pointer to the hash table [khash_t(name)*]
 */
#define kh_destroy(name, h) kh_destroy_##name(h)

/*! @function
  @abstract     Reset a hash table without deallocating memory.
  @param  name  Name of the hash table [symbol]
  @param  h     Pointer to the hash table [khash_t(name)*]
 */
#define kh_clear(name, h) kh_clear_##name(h)

/*! @function
  @abstract     Resize a hash table.
  @param  name  Name of the hash table [symbol]
  @param  h     Pointer to the hash table [khash_t(name)*]
  @param  s     New size [khint_t]
 */
#define kh_resize(name, h, s) kh_resize_##name(h, s)

/*! @function
  @abstract     Insert a key to the hash table.
  @param  name  Name of the hash table [symbol]
  @param  h     Pointer to the hash table [khash_t(name)*]
  @param  k     Key [type of keys]
  @param  r     Extra return code: 0 if the key is present in the hash table;
                1 if the bucket is empty (never used); 2 if the element in
				the bucket has been deleted [int*]
  @return       Iterator to the inserted element [khint_t]
 */
#define kh_put(name, h, k, r) kh_put_##name(h, k, r)

/*! @function
  @abstract     Retrieve a key from the hash table.
  @param  name  Name of the hash table [symbol]
  @param  h     Pointer to the hash table [khash_t(name)*]
  @param  k     Key [type of keys]
  @return       Iterator to the found element, or kh_end(h) is the element is absent [khint_t]
 */
#define kh_get(name, h, k) kh_get_##name(h, k)

/*! @function
  @abstract     Remove a key from the hash table.
  @param  name  Name of the hash table [symbol]
  @param  h     Pointer to the hash table [khash_t(name)*]
  @param  k     Iterator to the element to be deleted [khint_t]
 */
#define kh_del(name, h, k) kh_del_##name(h, k)

/*! @function
  @abstract     Test whether a bucket contains data.
  @param  h     Pointer to the hash table [khash_t(name)*]
  @param  x     Iterator to the bucket [khint_t]
  @return       1 if containing data; 0 otherwise [int]
 */
#define kh_exist(h, x) (!__ac_iseither((h)->flags, (x)))

/*! @function
  @abstract     Get key given an iterator
  @param  h     Pointer to the hash table [khash_t(name)*]
  @param  x     Iterator to the bucket [khint_t]
  @return       Key [type of keys]
 */
#define kh_key(h, x) ((h)->keys[x])

/*! @function
  @abstract     Get value given an iterator
  @param  h     Pointer to the hash table [khash_t(name)*]
  @param  x     Iterator to the bucket [khint_t]
  @return       Value [type of values]
  @discussion   For hash sets, calling this results in segfault.
 */
#define kh_val(h, x) ((h)->vals[x])

/*! @function
  @abstract     Alias of kh_val()
 */
#define kh_value(h, x) ((h)->vals[x])

/*! @function
  @abstract     Get the start iterator
  @param  h     Pointer to the hash table [khash_t(name)*]
  @return       The start iterator [khint_t]
 */
#define kh_begin(h) (khint_t)(0)

/*! @function
  @abstract     Get the end iterator
  @param  h     Pointer to the hash table [khash_t(name)*]
  @return       The end iterator [khint_t]
 */
#define kh_end(h) ((h)->n_buckets)

/*! @function
  @abstract     Get the number of elements in the hash table
  @param  h     Pointer to the hash table [khash_t(name)*]
  @return       Number of elements in the hash table [khint_t]
 */
#define kh_size(h) ((h)->size)

/*! @function
  @abstract     Get the number of buckets in the hash table
  @param  h     Pointer to the hash table [khash_t(name)*]
  @return       Number of buckets in the hash table [khint_t]
 */
#define kh_n_buckets(h) ((h)->n_buckets)

/*! @function
  @abstract     Iterate over the entries in the hash table
  @param  h     Pointer to the hash table [khash_t(name)*]
  @param  kvar  Variable to which key will be assigned
  @param  vvar  Variable to which value will be assigned
  @param  code  Block of code to execute
 */
#define kh_foreach(h, kvar, vvar, code) { khint_t __i;		\
	for (__i = kh_begin(h); __i != kh_end(h); ++__i) {		\
		if (!kh_exist(h,__i)) continue;						\
		(kvar) = kh_key(h,__i);								\
		(vvar) = kh_val(h,__i);								\
		code;												\
	} }

/*! @function
  @abstract     Iterate over the values in the hash table
  @param  h     Pointer to the hash table [khash_t(name)*]
  @param  vvar  Variable to which value will be assigned
  @param  code  Block of code to execute
 */
#define kh_foreach_value(h, vvar, code) { khint_t __i;		\
	for (__i = kh_begin(h); __i != kh_end(h); ++__i) {		\
		if (!kh_exist(h,__i)) continue;						\
		(vvar) = kh_val(h,__i);								\
		code;												\
	} }

/* More conenient interfaces */

/*! @function
  @abstract     Instantiate a hash set containing integer keys
  @param  name  Name of the hash table [symbol]
 */
#define KHASH_SET_INIT_INT(name)										\
	KHASH_INIT(name, khint32_t, char, 0, kh_int_hash_func, kh_int_hash_equal)

/*! @function
  @abstract     Instantiate a hash map containing integer keys
  @param  name  Name of the hash table [symbol]
  @param  khval_t  Type of values [type]
 */
#define KHASH_MAP_INIT_INT(name, khval_t)								\
	KHASH_INIT(name, khint32_t, khval_t, 1, kh_int_hash_func, kh_int_hash_equal)

/*! @function
  @abstract     Instantiate a hash map containing 64-bit integer keys
  @param  name  Name of the hash table [symbol]
 */
#define KHASH_SET_INIT_INT64(name)										\
	KHASH_INIT(name, khint64_t, char, 0, kh_int64_hash_func, kh_int64_hash_equal)

/*! @function
  @abstract     Instantiate a hash map containing 64-bit integer keys
  @param  name  Name of the hash table [symbol]
  @param  khval_t  Type of values [type]
 */
#define KHASH_MAP_INIT_INT64(name, khval_t)								\
	KHASH_INIT(name, khint64_t, khval_t, 1, kh_int64_hash_func, kh_int64_hash_equal)

typedef const char *kh_cstr_t;
/*! @function
  @abstract     Instantiate a hash map containing const char* keys
  @param  name  Name of the hash table [symbol]
 */
#define KHASH_SET_INIT_STR(name)										\
	KHASH_INIT(name, kh_cstr_t, char, 0, kh_str_hash_func, kh_str_hash_equal)

/*! @function
  @abstract     Instantiate a hash map containing const char* keys
  @param  name  Name of the hash table [symbol]
  @param  khval_t  Type of values [type]
 */
#define KHASH_MAP_INIT_STR(name, khval_t)								\
	KHASH_INIT(name, kh_cstr_t, khval_t, 1, kh_str_hash_func, kh_str_hash_equal)

#endif /* __AC_KHASH_H */
Commit	Line	Data
ada488bf RB	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	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
122	typedef unsigned int khint32_t;
123	#elif ULONG_MAX == 0xffffffffu
124	typedef unsigned long khint32_t;
125	#endif
126
127	#if ULONG_MAX == ULLONG_MAX
128	typedef unsigned long khint64_t;
129	#else
130	typedef unsigned long long khint64_t;
131	#endif
132
133	#ifdef _MSC_VER
72ee0787 RB	134	#define kh_inline __inline
	135	#else
	136	#define kh_inline inline
ada488bf RB	137	#endif
	138
	139	typedef khint32_t khint_t;
	140	typedef khint_t khiter_t;
	141
	142	#define __ac_isempty(flag, i) ((flag[i>>4]>>((i&0xfU)<<1))&2)
	143	#define __ac_isdel(flag, i) ((flag[i>>4]>>((i&0xfU)<<1))&1)
	144	#define __ac_iseither(flag, i) ((flag[i>>4]>>((i&0xfU)<<1))&3)
	145	#define __ac_set_isdel_false(flag, i) (flag[i>>4]&=~(1ul<<((i&0xfU)<<1)))
	146	#define __ac_set_isempty_false(flag, i) (flag[i>>4]&=~(2ul<<((i&0xfU)<<1)))
	147	#define __ac_set_isboth_false(flag, i) (flag[i>>4]&=~(3ul<<((i&0xfU)<<1)))
	148	#define __ac_set_isdel_true(flag, i) (flag[i>>4]\|=1ul<<((i&0xfU)<<1))
	149
	150	#ifdef KHASH_LINEAR
	151	#define __ac_inc(k, m) 1
	152	#else
	153	#define __ac_inc(k, m) (((k)>>3 ^ (k)<<3) \| 1) & (m)
	154	#endif
	155
	156	#define __ac_fsize(m) ((m) < 16? 1 : (m)>>4)
	157
	158	#ifndef kroundup32
	159	#define kroundup32(x) (--(x), (x)\|=(x)>>1, (x)\|=(x)>>2, (x)\|=(x)>>4, (x)\|=(x)>>8, (x)\|=(x)>>16, ++(x))
	160	#endif
	161
01fed0a8 RB	162	#ifndef kcalloc
	163	#define kcalloc(N,Z) calloc(N,Z)
	164	#endif
	165	#ifndef kmalloc
	166	#define kmalloc(Z) malloc(Z)
	167	#endif
	168	#ifndef krealloc
	169	#define krealloc(P,Z) realloc(P,Z)
	170	#endif
	171	#ifndef kfree
	172	#define kfree(P) free(P)
	173	#endif
	174
ada488bf RB	175	static const double __ac_HASH_UPPER = 0.77;
	176
	177	#define __KHASH_TYPE(name, khkey_t, khval_t) \
	178	typedef struct { \
	179	khint_t n_buckets, size, n_occupied, upper_bound; \
	180	khint32_t *flags; \
	181	khkey_t *keys; \
	182	khval_t *vals; \
	183	} kh_##name##_t;
	184
01fed0a8 RB	185	#define __KHASH_PROTOTYPES(name, khkey_t, khval_t) \
01fed0a8 RB	186	extern kh_##name##_t *kh_init_##name(void); \
ada488bf RB	187	extern void kh_destroy_##name(kh_##name##_t *h); \
	188	extern void kh_clear_##name(kh_##name##_t *h); \
	189	extern khint_t kh_get_##name(const kh_##name##_t *h, khkey_t key); \
01fed0a8	190	extern int kh_resize_##name(kh_##name##_t *h, khint_t new_n_buckets); \
ada488bf RB	191	extern khint_t kh_put_##name(kh_##name##_t h, khkey_t key, int ret); \
	192	extern void kh_del_##name(kh_##name##_t *h, khint_t x);
	193
01fed0a8 RB	194	#define __KHASH_IMPL(name, SCOPE, khkey_t, khval_t, kh_is_map, __hash_func, __hash_equal) \
	195	SCOPE kh_##name##_t *kh_init_##name(void) { \
	196	return (kh_##name##_t*)kcalloc(1, sizeof(kh_##name##_t)); \
ada488bf RB	197	} \
	198	SCOPE void kh_destroy_##name(kh_##name##_t *h) \
	199	{ \
	200	if (h) { \
821f6bc7 RB	201	kfree((void *)h->keys); kfree(h->flags); \
821f6bc7 RB	202	kfree((void *)h->vals); \
01fed0a8	203	kfree(h); \
ada488bf RB	204	} \
	205	} \
	206	SCOPE void kh_clear_##name(kh_##name##_t *h) \
	207	{ \
	208	if (h && h->flags) { \
	209	memset(h->flags, 0xaa, __ac_fsize(h->n_buckets) * sizeof(khint32_t)); \
	210	h->size = h->n_occupied = 0; \
	211	} \
	212	} \
	213	SCOPE khint_t kh_get_##name(const kh_##name##_t *h, khkey_t key) \
	214	{ \
	215	if (h->n_buckets) { \
	216	khint_t inc, k, i, last, mask; \
	217	mask = h->n_buckets - 1; \
	218	k = __hash_func(key); i = k & mask; \
	219	inc = __ac_inc(k, mask); last = i; /* inc==1 for linear probing */ \
	220	while (!__ac_isempty(h->flags, i) && (__ac_isdel(h->flags, i) \|\| !__hash_equal(h->keys[i], key))) { \
	221	i = (i + inc) & mask; \
	222	if (i == last) return h->n_buckets; \
	223	} \
	224	return __ac_iseither(h->flags, i)? h->n_buckets : i; \
	225	} else return 0; \
	226	} \
01fed0a8	227	SCOPE int kh_resize_##name(kh_##name##_t *h, khint_t new_n_buckets) \
ada488bf RB	228	{ /* This function uses 0.25n_bucktes bytes of working space instead of [sizeof(key_t+val_t)+.25]n_buckets. */ \
	229	khint32_t *new_flags = 0; \
	230	khint_t j = 1; \
	231	{ \
	232	kroundup32(new_n_buckets); \
	233	if (new_n_buckets < 4) new_n_buckets = 4; \
	234	if (h->size >= (khint_t)(new_n_buckets * __ac_HASH_UPPER + 0.5)) j = 0; /* requested size is too small */ \
	235	else { /* hash table size to be changed (shrink or expand); rehash */ \
01fed0a8 RB	236	new_flags = (khint32_t)kmalloc(__ac_fsize(new_n_buckets) sizeof(khint32_t)); \
01fed0a8 RB	237	if (!new_flags) return -1; \
ada488bf RB	238	memset(new_flags, 0xaa, __ac_fsize(new_n_buckets) * sizeof(khint32_t)); \
ada488bf RB	239	if (h->n_buckets < new_n_buckets) { /* expand */ \
821f6bc7	240	khkey_t new_keys = (khkey_t)krealloc((void )h->keys, new_n_buckets sizeof(khkey_t)); \
01fed0a8 RB	241	if (!new_keys) return -1; \
	242	h->keys = new_keys; \
	243	if (kh_is_map) { \
821f6bc7	244	khval_t new_vals = (khval_t)krealloc((void )h->vals, new_n_buckets sizeof(khval_t)); \
01fed0a8 RB	245	if (!new_vals) return -1; \
	246	h->vals = new_vals; \
	247	} \
ada488bf RB	248	} /* otherwise shrink */ \
	249	} \
	250	} \
	251	if (j) { /* rehashing is needed */ \
	252	for (j = 0; j != h->n_buckets; ++j) { \
	253	if (__ac_iseither(h->flags, j) == 0) { \
	254	khkey_t key = h->keys[j]; \
	255	khval_t val; \
	256	khint_t new_mask; \
	257	new_mask = new_n_buckets - 1; \
	258	if (kh_is_map) val = h->vals[j]; \
	259	__ac_set_isdel_true(h->flags, j); \
	260	while (1) { /* kick-out process; sort of like in Cuckoo hashing */ \
	261	khint_t inc, k, i; \
	262	k = __hash_func(key); \
	263	i = k & new_mask; \
	264	inc = __ac_inc(k, new_mask); \
	265	while (!__ac_isempty(new_flags, i)) i = (i + inc) & new_mask; \
	266	__ac_set_isempty_false(new_flags, i); \
	267	if (i < h->n_buckets && __ac_iseither(h->flags, i) == 0) { /* kick out the existing element */ \
	268	{ khkey_t tmp = h->keys[i]; h->keys[i] = key; key = tmp; } \
	269	if (kh_is_map) { khval_t tmp = h->vals[i]; h->vals[i] = val; val = tmp; } \
	270	__ac_set_isdel_true(h->flags, i); /* mark it as deleted in the old hash table */ \
	271	} else { /* write the element and jump out of the loop */ \
	272	h->keys[i] = key; \
	273	if (kh_is_map) h->vals[i] = val; \
	274	break; \
	275	} \
	276	} \
	277	} \
	278	} \
	279	if (h->n_buckets > new_n_buckets) { /* shrink the hash table */ \
821f6bc7 RB	280	h->keys = (khkey_t)krealloc((void )h->keys, new_n_buckets * sizeof(khkey_t)); \
821f6bc7 RB	281	if (kh_is_map) h->vals = (khval_t)krealloc((void )h->vals, new_n_buckets * sizeof(khval_t)); \
ada488bf	282	} \
01fed0a8	283	kfree(h->flags); /* free the working space */ \
ada488bf RB	284	h->flags = new_flags; \
	285	h->n_buckets = new_n_buckets; \
	286	h->n_occupied = h->size; \
	287	h->upper_bound = (khint_t)(h->n_buckets * __ac_HASH_UPPER + 0.5); \
	288	} \
01fed0a8	289	return 0; \
ada488bf RB	290	} \
	291	SCOPE khint_t kh_put_##name(kh_##name##_t h, khkey_t key, int ret) \
	292	{ \
	293	khint_t x; \
	294	if (h->n_occupied >= h->upper_bound) { /* update the hash table */ \
01fed0a8 RB	295	if (h->n_buckets > (h->size<<1)) { \
	296	if (kh_resize_##name(h, h->n_buckets - 1) < 0) { /* clear "deleted" elements */ \
	297	*ret = -1; return h->n_buckets; \
	298	} \
	299	} else if (kh_resize_##name(h, h->n_buckets + 1) < 0) { /* expand the hash table */ \
	300	*ret = -1; return h->n_buckets; \
	301	} \
ada488bf RB	302	} /* TODO: to implement automatically shrinking; resize() already support shrinking */ \
	303	{ \
	304	khint_t inc, k, i, site, last, mask = h->n_buckets - 1; \
	305	x = site = h->n_buckets; k = __hash_func(key); i = k & mask; \
	306	if (__ac_isempty(h->flags, i)) x = i; /* for speed up */ \
	307	else { \
	308	inc = __ac_inc(k, mask); last = i; \
	309	while (!__ac_isempty(h->flags, i) && (__ac_isdel(h->flags, i) \|\| !__hash_equal(h->keys[i], key))) { \
	310	if (__ac_isdel(h->flags, i)) site = i; \
	311	i = (i + inc) & mask; \
	312	if (i == last) { x = site; break; } \
	313	} \
	314	if (x == h->n_buckets) { \
	315	if (__ac_isempty(h->flags, i) && site != h->n_buckets) x = site; \
	316	else x = i; \
	317	} \
	318	} \
	319	} \
	320	if (__ac_isempty(h->flags, x)) { /* not present at all */ \
	321	h->keys[x] = key; \
	322	__ac_set_isboth_false(h->flags, x); \
	323	++h->size; ++h->n_occupied; \
	324	*ret = 1; \
	325	} else if (__ac_isdel(h->flags, x)) { /* deleted */ \
	326	h->keys[x] = key; \
	327	__ac_set_isboth_false(h->flags, x); \
	328	++h->size; \
	329	*ret = 2; \
	330	} else ret = 0; / Don't touch h->keys[x] if present and not deleted */ \
	331	return x; \
	332	} \
	333	SCOPE void kh_del_##name(kh_##name##_t *h, khint_t x) \
	334	{ \
	335	if (x != h->n_buckets && !__ac_iseither(h->flags, x)) { \
	336	__ac_set_isdel_true(h->flags, x); \
	337	--h->size; \
	338	} \
	339	}
	340
01fed0a8 RB	341	#define KHASH_DECLARE(name, khkey_t, khval_t) \
	342	__KHASH_TYPE(name, khkey_t, khval_t) \
	343	__KHASH_PROTOTYPES(name, khkey_t, khval_t)
	344
	345	#define KHASH_INIT2(name, SCOPE, khkey_t, khval_t, kh_is_map, __hash_func, __hash_equal) \
	346	__KHASH_TYPE(name, khkey_t, khval_t) \
	347	__KHASH_IMPL(name, SCOPE, khkey_t, khval_t, kh_is_map, __hash_func, __hash_equal)
	348
ada488bf	349	#define KHASH_INIT(name, khkey_t, khval_t, kh_is_map, __hash_func, __hash_equal) \
72ee0787	350	KHASH_INIT2(name, static kh_inline, khkey_t, khval_t, kh_is_map, __hash_func, __hash_equal)
ada488bf RB	351
	352	/* --- BEGIN OF HASH FUNCTIONS --- */
	353
	354	/*! @function
	355	@abstract Integer hash function
	356	@param key The integer [khint32_t]
	357	@return The hash value [khint_t]
	358	*/
	359	#define kh_int_hash_func(key) (khint32_t)(key)
	360	/*! @function
	361	@abstract Integer comparison function
	362	*/
	363	#define kh_int_hash_equal(a, b) ((a) == (b))
	364	/*! @function
	365	@abstract 64-bit integer hash function
	366	@param key The integer [khint64_t]
	367	@return The hash value [khint_t]
	368	*/
	369	#define kh_int64_hash_func(key) (khint32_t)((key)>>33^(key)^(key)<<11)
	370	/*! @function
	371	@abstract 64-bit integer comparison function
	372	*/
	373	#define kh_int64_hash_equal(a, b) ((a) == (b))
	374	/*! @function
	375	@abstract const char* hash function
	376	@param s Pointer to a null terminated string
	377	@return The hash value
	378	*/
72ee0787	379	static kh_inline khint_t __ac_X31_hash_string(const char *s)
ada488bf	380	{
821f6bc7 RB	381	khint_t h = (khint_t)*s;
821f6bc7 RB	382	if (h) for (++s ; s; ++s) h = (h << 5) - h + (khint_t)s;
ada488bf RB	383	return h;
	384	}
	385	/*! @function
	386	@abstract Another interface to const char* hash function
	387	@param key Pointer to a null terminated string [const char*]
	388	@return The hash value [khint_t]
	389	*/
	390	#define kh_str_hash_func(key) __ac_X31_hash_string(key)
	391	/*! @function
	392	@abstract Const char* comparison function
	393	*/
	394	#define kh_str_hash_equal(a, b) (strcmp(a, b) == 0)
	395
72ee0787	396	static kh_inline khint_t __ac_Wang_hash(khint_t key)
ada488bf RB	397	{
	398	key += ~(key << 15);
	399	key ^= (key >> 10);
	400	key += (key << 3);
	401	key ^= (key >> 6);
	402	key += ~(key << 11);
	403	key ^= (key >> 16);
	404	return key;
	405	}
	406	#define kh_int_hash_func2(k) __ac_Wang_hash((khint_t)key)
	407
	408	/* --- END OF HASH FUNCTIONS --- */
	409
	410	/* Other convenient macros... */
	411
	412	/*!
	413	@abstract Type of the hash table.
	414	@param name Name of the hash table [symbol]
	415	*/
	416	#define khash_t(name) kh_##name##_t
	417
	418	/*! @function
	419	@abstract Initiate a hash table.
	420	@param name Name of the hash table [symbol]
	421	@return Pointer to the hash table [khash_t(name)*]
	422	*/
	423	#define kh_init(name) kh_init_##name()
	424
	425	/*! @function
	426	@abstract Destroy a hash table.
	427	@param name Name of the hash table [symbol]
	428	@param h Pointer to the hash table [khash_t(name)*]
	429	*/
	430	#define kh_destroy(name, h) kh_destroy_##name(h)
	431
	432	/*! @function
	433	@abstract Reset a hash table without deallocating memory.
	434	@param name Name of the hash table [symbol]
	435	@param h Pointer to the hash table [khash_t(name)*]
	436	*/
	437	#define kh_clear(name, h) kh_clear_##name(h)
	438
	439	/*! @function
	440	@abstract Resize a hash table.
	441	@param name Name of the hash table [symbol]
	442	@param h Pointer to the hash table [khash_t(name)*]
	443	@param s New size [khint_t]
	444	*/
	445	#define kh_resize(name, h, s) kh_resize_##name(h, s)
	446
	447	/*! @function
	448	@abstract Insert a key to the hash table.
	449	@param name Name of the hash table [symbol]
	450	@param h Pointer to the hash table [khash_t(name)*]
	451	@param k Key [type of keys]
	452	@param r Extra return code: 0 if the key is present in the hash table;
	453	1 if the bucket is empty (never used); 2 if the element in
	454	the bucket has been deleted [int*]
	455	@return Iterator to the inserted element [khint_t]
	456	*/
	457	#define kh_put(name, h, k, r) kh_put_##name(h, k, r)
	458
	459	/*! @function
	460	@abstract Retrieve a key from the hash table.
461	@param name Name of the hash table [symbol]
462	@param h Pointer to the hash table [khash_t(name)*]
463	@param k Key [type of keys]
464	@return Iterator to the found element, or kh_end(h) is the element is absent [khint_t]
465	*/
466	#define kh_get(name, h, k) kh_get_##name(h, k)
467
468	/*! @function
469	@abstract Remove a key from the hash table.
470	@param name Name of the hash table [symbol]
471	@param h Pointer to the hash table [khash_t(name)*]
472	@param k Iterator to the element to be deleted [khint_t]
473	*/
474	#define kh_del(name, h, k) kh_del_##name(h, k)
475
476	/*! @function
477	@abstract Test whether a bucket contains data.
478	@param h Pointer to the hash table [khash_t(name)*]
479	@param x Iterator to the bucket [khint_t]
480	@return 1 if containing data; 0 otherwise [int]
481	*/
482	#define kh_exist(h, x) (!__ac_iseither((h)->flags, (x)))
483
484	/*! @function
485	@abstract Get key given an iterator
486	@param h Pointer to the hash table [khash_t(name)*]
487	@param x Iterator to the bucket [khint_t]
488	@return Key [type of keys]
489	*/
490	#define kh_key(h, x) ((h)->keys[x])
491
492	/*! @function
493	@abstract Get value given an iterator
494	@param h Pointer to the hash table [khash_t(name)*]
495	@param x Iterator to the bucket [khint_t]
496	@return Value [type of values]
497	@discussion For hash sets, calling this results in segfault.
498	*/
499	#define kh_val(h, x) ((h)->vals[x])
500
501	/*! @function
502	@abstract Alias of kh_val()
503	*/
504	#define kh_value(h, x) ((h)->vals[x])
505
506	/*! @function
507	@abstract Get the start iterator
508	@param h Pointer to the hash table [khash_t(name)*]
509	@return The start iterator [khint_t]
510	*/
511	#define kh_begin(h) (khint_t)(0)
512
513	/*! @function
514	@abstract Get the end iterator
515	@param h Pointer to the hash table [khash_t(name)*]
516	@return The end iterator [khint_t]
517	*/
518	#define kh_end(h) ((h)->n_buckets)
519
520	/*! @function
521	@abstract Get the number of elements in the hash table
522	@param h Pointer to the hash table [khash_t(name)*]
523	@return Number of elements in the hash table [khint_t]
524	*/
525	#define kh_size(h) ((h)->size)
526
527	/*! @function
528	@abstract Get the number of buckets in the hash table
529	@param h Pointer to the hash table [khash_t(name)*]
530	@return Number of buckets in the hash table [khint_t]
531	*/
532	#define kh_n_buckets(h) ((h)->n_buckets)
533
01fed0a8 RB	534	/*! @function
	535	@abstract Iterate over the entries in the hash table
	536	@param h Pointer to the hash table [khash_t(name)*]
	537	@param kvar Variable to which key will be assigned
	538	@param vvar Variable to which value will be assigned
	539	@param code Block of code to execute
	540	*/
	541	#define kh_foreach(h, kvar, vvar, code) { khint_t __i; \
	542	for (__i = kh_begin(h); __i != kh_end(h); ++__i) { \
	543	if (!kh_exist(h,__i)) continue; \
	544	(kvar) = kh_key(h,__i); \
	545	(vvar) = kh_val(h,__i); \
	546	code; \
	547	} }
	548
	549	/*! @function
	550	@abstract Iterate over the values in the hash table
	551	@param h Pointer to the hash table [khash_t(name)*]
	552	@param vvar Variable to which value will be assigned
	553	@param code Block of code to execute
	554	*/
	555	#define kh_foreach_value(h, vvar, code) { khint_t __i; \
	556	for (__i = kh_begin(h); __i != kh_end(h); ++__i) { \
	557	if (!kh_exist(h,__i)) continue; \
	558	(vvar) = kh_val(h,__i); \
	559	code; \
	560	} }
	561
ada488bf RB	562	/* More conenient interfaces */
	563
	564	/*! @function
	565	@abstract Instantiate a hash set containing integer keys
	566	@param name Name of the hash table [symbol]
	567	*/
	568	#define KHASH_SET_INIT_INT(name) \
	569	KHASH_INIT(name, khint32_t, char, 0, kh_int_hash_func, kh_int_hash_equal)
	570
	571	/*! @function
	572	@abstract Instantiate a hash map containing integer keys
	573	@param name Name of the hash table [symbol]
	574	@param khval_t Type of values [type]
	575	*/
	576	#define KHASH_MAP_INIT_INT(name, khval_t) \
	577	KHASH_INIT(name, khint32_t, khval_t, 1, kh_int_hash_func, kh_int_hash_equal)
	578
	579	/*! @function
	580	@abstract Instantiate a hash map containing 64-bit integer keys
	581	@param name Name of the hash table [symbol]
	582	*/
	583	#define KHASH_SET_INIT_INT64(name) \
	584	KHASH_INIT(name, khint64_t, char, 0, kh_int64_hash_func, kh_int64_hash_equal)
	585
	586	/*! @function
	587	@abstract Instantiate a hash map containing 64-bit integer keys
	588	@param name Name of the hash table [symbol]
	589	@param khval_t Type of values [type]
	590	*/
	591	#define KHASH_MAP_INIT_INT64(name, khval_t) \
	592	KHASH_INIT(name, khint64_t, khval_t, 1, kh_int64_hash_func, kh_int64_hash_equal)
	593
	594	typedef const char *kh_cstr_t;
	595	/*! @function
	596	@abstract Instantiate a hash map containing const char* keys
	597	@param name Name of the hash table [symbol]
	598	*/
	599	#define KHASH_SET_INIT_STR(name) \
	600	KHASH_INIT(name, kh_cstr_t, char, 0, kh_str_hash_func, kh_str_hash_equal)
	601
	602	/*! @function
	603	@abstract Instantiate a hash map containing const char* keys
	604	@param name Name of the hash table [symbol]
	605	@param khval_t Type of values [type]
	606	*/
	607	#define KHASH_MAP_INIT_STR(name, khval_t) \
	608	KHASH_INIT(name, kh_cstr_t, khval_t, 1, kh_str_hash_func, kh_str_hash_equal)
	609
	610	#endif /* __AC_KHASH_H */