khash.h File Reference

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

Go to the source code of this file.

Macros
#define	AC_VERSION_KHASH_H   "0.2.8"
#define	kh_inline   inline
#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))
#define	__ac_fsize(m)   ((m) < 16? 1 : (m)>>4)
#define	kroundup32(x)   (--(x), (x)|=(x)>>1, (x)|=(x)>>2, (x)|=(x)>>4, (x)|=(x)>>8, (x)|=(x)>>16, ++(x))
#define	kcalloc(N, Z)   calloc(N,Z)
#define	kmalloc(Z)   malloc(Z)
#define	krealloc(P, Z)   realloc(P,Z)
#define	kfree(P)   free(P)
#define	__KHASH_TYPE(name, khkey_t, khval_t)
#define	__KHASH_PROTOTYPES(name, khkey_t, khval_t)
#define	__KHASH_IMPL(name, SCOPE, khkey_t, khval_t, kh_is_map, __hash_func, __hash_equal)
#define	KHASH_DECLARE(name, khkey_t, khval_t)
#define	KHASH_INIT2(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)
#define	kh_int_hash_func(key)   (khint32_t)(key)
#define	kh_int_hash_equal(a, b)   ((a) == (b))
#define	kh_int64_hash_func(key)   (khint32_t)((key)>>33^(key)^(key)<<11)
#define	kh_int64_hash_equal(a, b)   ((a) == (b))
#define	kh_str_hash_func(key)   __ac_X31_hash_string(key)
#define	kh_str_hash_equal(a, b)   (strcmp(a, b) == 0)
#define	kh_int_hash_func2(k)   __ac_Wang_hash((khint_t)key)
#define	khash_t(name)   kh_##name##_t
#define	kh_init(name)   kh_init_##name()
#define	kh_destroy(name, h)   kh_destroy_##name(h)
#define	kh_clear(name, h)   kh_clear_##name(h)
#define	kh_resize(name, h, s)   kh_resize_##name(h, s)
#define	kh_put(name, h, k, r)   kh_put_##name(h, k, r)
#define	kh_get(name, h, k)   kh_get_##name(h, k)
#define	kh_del(name, h, k)   kh_del_##name(h, k)
#define	kh_exist(h, x)   (!__ac_iseither((h)->flags, (x)))
#define	kh_key(h, x)   ((h)->keys[x])
#define	kh_val(h, x)   ((h)->vals[x])
#define	kh_value(h, x)   ((h)->vals[x])
#define	kh_begin(h)   (khint_t)(0)
#define	kh_end(h)   ((h)->n_buckets)
#define	kh_size(h)   ((h)->size)
#define	kh_n_buckets(h)   ((h)->n_buckets)
#define	kh_foreach(h, kvar, vvar, code)
#define	kh_foreach_value(h, vvar, code)
#define	KHASH_SET_INIT_INT(name)   KHASH_INIT(name, khint32_t, char, 0, kh_int_hash_func, kh_int_hash_equal)
#define	KHASH_MAP_INIT_INT(name, khval_t)   KHASH_INIT(name, khint32_t, khval_t, 1, kh_int_hash_func, kh_int_hash_equal)
#define	KHASH_SET_INIT_INT64(name)   KHASH_INIT(name, khint64_t, char, 0, kh_int64_hash_func, kh_int64_hash_equal)
#define	KHASH_MAP_INIT_INT64(name, khval_t)   KHASH_INIT(name, khint64_t, khval_t, 1, kh_int64_hash_func, kh_int64_hash_equal)
#define	KHASH_SET_INIT_STR(name)   KHASH_INIT(name, kh_cstr_t, char, 0, kh_str_hash_func, kh_str_hash_equal)
#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)

Typedefs
typedef unsigned long	khint64_t
typedef khint32_t	khint_t
typedef khint_t	khiter_t
typedef const char *	kh_cstr_t

Macro Definition Documentation

#define __ac_fsize

(

m)

((m) < 16? 1 : (m)>>4)

Definition at line 163 of file khash.h.

#define __ac_isdel	(		flag,
			i
	)		((flag[i>>4]>>((i&0xfU)<<1))&1)

Definition at line 156 of file khash.h.

#define __ac_iseither	(		flag,
			i
	)		((flag[i>>4]>>((i&0xfU)<<1))&3)

Definition at line 157 of file khash.h.

#define __ac_isempty	(		flag,
			i
	)		((flag[i>>4]>>((i&0xfU)<<1))&2)

Definition at line 155 of file khash.h.

#define __ac_set_isboth_false	(		flag,
			i
	)		(flag[i>>4]&=~(3ul<<((i&0xfU)<<1)))

Definition at line 160 of file khash.h.

#define __ac_set_isdel_false	(		flag,
			i
	)		(flag[i>>4]&=~(1ul<<((i&0xfU)<<1)))

Definition at line 158 of file khash.h.

#define __ac_set_isdel_true	(		flag,
			i
	)		(flag[i>>4]|=1ul<<((i&0xfU)<<1))

Definition at line 161 of file khash.h.

#define __ac_set_isempty_false	(		flag,
			i
	)		(flag[i>>4]&=~(2ul<<((i&0xfU)<<1)))

Definition at line 159 of file khash.h.

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

Definition at line 201 of file khash.h.

#define __KHASH_PROTOTYPES	(		name,
			khkey_t,
			khval_t
	)

Value:

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);

Definition at line 192 of file khash.h.

#define __KHASH_TYPE	(		name,
			khkey_t,
			khval_t
	)

Value:

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

Definition at line 184 of file khash.h.

#define AC_VERSION_KHASH_H   "0.2.8"

Generic hash table library.

Definition at line 126 of file khash.h.

#define kcalloc	(		N,
			Z
	)		calloc(N,Z)

Definition at line 170 of file khash.h.

#define kfree

(

P)

free(P)

Definition at line 179 of file khash.h.

#define kh_begin

(

h)

(khint_t)(0)

Get the start iterator

Parameters

h	Pointer to the hash table [khash_t(name)*]

Returns

The start iterator [khint_t]

Definition at line 518 of file khash.h.

#define kh_clear	(		name,
			h
	)		kh_clear_##name(h)

Reset a hash table without deallocating memory.

Parameters

name	Name of the hash table [symbol]
h	Pointer to the hash table [khash_t(name)*]

Definition at line 443 of file khash.h.

#define kh_del	(		name,
			h,
			k
	)		kh_del_##name(h, k)

Remove a key from the hash table.

Parameters

name	Name of the hash table [symbol]
h	Pointer to the hash table [khash_t(name)*]
k	Iterator to the element to be deleted [khint_t]

Definition at line 481 of file khash.h.

#define kh_destroy	(		name,
			h
	)		kh_destroy_##name(h)

Destroy a hash table.

Parameters

name	Name of the hash table [symbol]
h	Pointer to the hash table [khash_t(name)*]

Definition at line 436 of file khash.h.

#define kh_end

(

h)

((h)->n_buckets)

Get the end iterator

Parameters

h	Pointer to the hash table [khash_t(name)*]

Returns

The end iterator [khint_t]

Definition at line 525 of file khash.h.

#define kh_exist	(		h,
			x
	)		(!__ac_iseither((h)->flags, (x)))

Test whether a bucket contains data.

Parameters

h	Pointer to the hash table [khash_t(name)*]
x	Iterator to the bucket [khint_t]

Returns

1 if containing data; 0 otherwise [int]

Definition at line 489 of file khash.h.

#define kh_foreach	(		h,
			kvar,
			vvar,
			code
	)

Value:

{ 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;                                                                                           \
        } }

Iterate over the entries in the hash table

Parameters

h	Pointer to the hash table [khash_t(name)*]
kvar	Variable to which key will be assigned
vvar	Variable to which value will be assigned
code	Block of code to execute

Definition at line 548 of file khash.h.

#define kh_foreach_value	(		h,
			vvar,
			code
	)

Value:

{ 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;                                                                                           \
        } }

Iterate over the values in the hash table

Parameters

h	Pointer to the hash table [khash_t(name)*]
vvar	Variable to which value will be assigned
code	Block of code to execute

Definition at line 562 of file khash.h.

#define kh_get	(		name,
			h,
			k
	)		kh_get_##name(h, k)

Retrieve a key from the hash table.

Parameters

name	Name of the hash table [symbol]
h	Pointer to the hash table [khash_t(name)*]
k	Key [type of keys]

Returns

Iterator to the found element, or kh_end(h) if the element is absent [khint_t]

Definition at line 473 of file khash.h.

#define kh_init

(

name)

kh_init_##name()

Initiate a hash table.

Parameters

name	Name of the hash table [symbol]

Returns

Pointer to the hash table [khash_t(name)*]

Definition at line 429 of file khash.h.

#define kh_inline   inline

Definition at line 149 of file khash.h.

#define kh_int64_hash_equal	(		a,
			b
	)		((a) == (b))

64-bit integer comparison function

Definition at line 379 of file khash.h.

#define kh_int64_hash_func

(

key)

(khint32_t)((key)>>33^(key)^(key)<<11)

64-bit integer hash function

Parameters

key	The integer [khint64_t]

Returns

The hash value [khint_t]

Definition at line 375 of file khash.h.

#define kh_int_hash_equal	(		a,
			b
	)		((a) == (b))

Integer comparison function

Definition at line 369 of file khash.h.

#define kh_int_hash_func

(

key)

(khint32_t)(key)

Integer hash function

Parameters

key	The integer [khint32_t]

Returns

The hash value [khint_t]

Definition at line 365 of file khash.h.

#define kh_int_hash_func2

(

k)

__ac_Wang_hash((khint_t)key)

Definition at line 412 of file khash.h.

#define kh_key	(		h,
			x
	)		((h)->keys[x])

Get key given an iterator

Parameters

h	Pointer to the hash table [khash_t(name)*]
x	Iterator to the bucket [khint_t]

Returns

Key [type of keys]

Definition at line 497 of file khash.h.

#define kh_n_buckets

(

h)

((h)->n_buckets)

Get the number of buckets in the hash table

Parameters

h	Pointer to the hash table [khash_t(name)*]

Returns

Number of buckets in the hash table [khint_t]

Definition at line 539 of file khash.h.

#define kh_put	(		name,
			h,
			k,
			r
	)		kh_put_##name(h, k, r)

Insert a key to the hash table.

Parameters

name	Name of the hash table [symbol]
h	Pointer to the hash table [khash_t(name)*]
k	Key [type of keys]
r	Extra return code: -1 if the operation failed; 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*]

Returns

Iterator to the inserted element [khint_t]

Definition at line 464 of file khash.h.

#define kh_resize	(		name,
			h,
			s
	)		kh_resize_##name(h, s)

Resize a hash table.

Parameters

name	Name of the hash table [symbol]
h	Pointer to the hash table [khash_t(name)*]
s	New size [khint_t]

Definition at line 451 of file khash.h.

#define kh_size

(

h)

((h)->size)

Get the number of elements in the hash table

Parameters

h	Pointer to the hash table [khash_t(name)*]

Returns

Number of elements in the hash table [khint_t]

Definition at line 532 of file khash.h.

#define kh_str_hash_equal	(		a,
			b
	)		(strcmp(a, b) == 0)

Const char* comparison function

Definition at line 400 of file khash.h.

#define kh_str_hash_func

(

key)

__ac_X31_hash_string(key)

Another interface to const char* hash function

Parameters

key	Pointer to a null terminated string [const char*]

Returns

The hash value [khint_t]

Definition at line 396 of file khash.h.

#define kh_val	(		h,
			x
	)		((h)->vals[x])

Get value given an iterator

Parameters

h	Pointer to the hash table [khash_t(name)*]
x	Iterator to the bucket [khint_t]

Returns

Value [type of values] For hash sets, calling this results in segfault.

Definition at line 506 of file khash.h.

#define kh_value	(		h,
			x
	)		((h)->vals[x])

Alias of kh_val()

Definition at line 511 of file khash.h.

#define KHASH_DECLARE	(		name,
			khkey_t,
			khval_t
	)

Value:

__KHASH_TYPE(name, khkey_t, khval_t)                                                            \
        __KHASH_PROTOTYPES(name, khkey_t, khval_t)

Definition at line 347 of file khash.h.

#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)

Definition at line 355 of file khash.h.

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

Value:

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

Definition at line 351 of file khash.h.

#define KHASH_MAP_INIT_INT	(		name,
			khval_t
	)		KHASH_INIT(name, khint32_t, khval_t, 1, kh_int_hash_func, kh_int_hash_equal)

Instantiate a hash map containing integer keys

Parameters

name	Name of the hash table [symbol]
khval_t	Type of values [type]

Definition at line 583 of file khash.h.

#define KHASH_MAP_INIT_INT64	(		name,
			khval_t
	)		KHASH_INIT(name, khint64_t, khval_t, 1, kh_int64_hash_func, kh_int64_hash_equal)

Instantiate a hash map containing 64-bit integer keys

Parameters

name	Name of the hash table [symbol]
khval_t	Type of values [type]

Definition at line 598 of file khash.h.

#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)

Instantiate a hash map containing const char* keys

Parameters

name	Name of the hash table [symbol]
khval_t	Type of values [type]

Definition at line 614 of file khash.h.

#define KHASH_SET_INIT_INT

(

name)

KHASH_INIT(name, khint32_t, char, 0, kh_int_hash_func, kh_int_hash_equal)

Instantiate a hash set containing integer keys

Parameters

name	Name of the hash table [symbol]

Definition at line 575 of file khash.h.

#define KHASH_SET_INIT_INT64

(

name)

KHASH_INIT(name, khint64_t, char, 0, kh_int64_hash_func, kh_int64_hash_equal)

Instantiate a hash map containing 64-bit integer keys

Parameters

name	Name of the hash table [symbol]

Definition at line 590 of file khash.h.

#define KHASH_SET_INIT_STR

(

name)

KHASH_INIT(name, kh_cstr_t, char, 0, kh_str_hash_func, kh_str_hash_equal)

Instantiate a hash map containing const char* keys

Parameters

name	Name of the hash table [symbol]

Definition at line 606 of file khash.h.

#define khash_t

(

name)

kh_##name##_t

Type of the hash table.

Parameters

name	Name of the hash table [symbol]

Definition at line 422 of file khash.h.

#define kmalloc

(

Z)

malloc(Z)

Definition at line 173 of file khash.h.

#define krealloc	(		P,
			Z
	)		realloc(P,Z)

Definition at line 176 of file khash.h.

#define kroundup32

(

x)

(--(x), (x)|=(x)>>1, (x)|=(x)>>2, (x)|=(x)>>4, (x)|=(x)>>8, (x)|=(x)>>16, ++(x))

Definition at line 166 of file khash.h.

Typedef Documentation

typedef const char* kh_cstr_t

Definition at line 601 of file khash.h.

typedef unsigned long khint64_t

Definition at line 141 of file khash.h.

typedef khint32_t khint_t

Definition at line 152 of file khash.h.

typedef khint_t khiter_t

Definition at line 153 of file khash.h.