khash.h File Reference

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

Include dependency graph for khash.h:

This graph shows which files directly or indirectly include this file:

Go to the source code of this file.

Macros
#define	AC_VERSION_KHASH_H   "0.2.8"
#define	kh_inline   inline
#define	klib_unused
#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 klib_unused, 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(key)   __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 uint32_t	khint32_t
typedef uint64_t	khint64_t
typedef khint32_t	khint_t
typedef khint_t	khiter_t
typedef const char *	kh_cstr_t

Functions
static khint_t	__ac_X31_hash_string (const char *s)
static khint_t	__ac_Wang_hash (khint_t key)

Variables
static const double	__ac_HASH_UPPER = 0.77

Macro Definition Documentation

__ac_fsize

#define __ac_fsize

(

m

)

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

Definition at line 164 of file khash.h.

__ac_isdel

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

Definition at line 157 of file khash.h.

__ac_iseither

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

Definition at line 158 of file khash.h.

__ac_isempty

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

Definition at line 156 of file khash.h.

__ac_set_isboth_false

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

Definition at line 161 of file khash.h.

__ac_set_isdel_false

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

Definition at line 159 of file khash.h.

__ac_set_isdel_true

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

Definition at line 162 of file khash.h.

__ac_set_isempty_false

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

Definition at line 160 of file khash.h.

__KHASH_IMPL

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

Definition at line 202 of file khash.h.

__KHASH_PROTOTYPES

#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 193 of file khash.h.

__KHASH_TYPE

#define __KHASH_TYPE	(		name,
			khkey_t,
			khval_t
	)

Value:

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

Definition at line 185 of file khash.h.

AC_VERSION_KHASH_H

#define AC_VERSION_KHASH_H   "0.2.8"

@header

Generic hash table library.

Definition at line 128 of file khash.h.

kcalloc

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

Definition at line 171 of file khash.h.

kfree

#define kfree

(

P

)

free(P)

Definition at line 180 of file khash.h.

kh_begin

#define kh_begin

(

h

)

(khint_t)(0)

@function @abstract Get the start iterator

Parameters

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

Returns

The start iterator [khint_t]

Definition at line 519 of file khash.h.

kh_clear

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

@function @abstract 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 444 of file khash.h.

kh_del

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

@function @abstract 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 482 of file khash.h.

kh_destroy

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

@function @abstract Destroy a hash table.

Parameters

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

Definition at line 437 of file khash.h.

kh_end

#define kh_end

(

h

)

((h)->n_buckets)

@function @abstract Get the end iterator

Parameters

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

Returns

The end iterator [khint_t]

Definition at line 526 of file khash.h.

kh_exist

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

@function @abstract 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 490 of file khash.h.

kh_foreach

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

@function @abstract 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 549 of file khash.h.

kh_foreach_value

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

@function @abstract 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 563 of file khash.h.

kh_get

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

@function @abstract 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 474 of file khash.h.

kh_init

#define kh_init

(

name

)

kh_init_##name()

@function @abstract Initiate a hash table.

Parameters

name	Name of the hash table [symbol]

Returns

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

Definition at line 430 of file khash.h.

kh_inline

#define kh_inline   inline

Definition at line 141 of file khash.h.

kh_int64_hash_equal

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

@function @abstract 64-bit integer comparison function

Definition at line 380 of file khash.h.

kh_int64_hash_func

#define kh_int64_hash_func

(

key

)

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

@function @abstract 64-bit integer hash function

Parameters

key	The integer [khint64_t]

Returns

The hash value [khint_t]

Definition at line 376 of file khash.h.

kh_int_hash_equal

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

@function @abstract Integer comparison function

Definition at line 370 of file khash.h.

kh_int_hash_func

#define kh_int_hash_func

(

key

)

(khint32_t)(key)

@function @abstract Integer hash function

Parameters

key	The integer [khint32_t]

Returns

The hash value [khint_t]

Definition at line 366 of file khash.h.

kh_int_hash_func2

#define kh_int_hash_func2

(

key

)

__ac_Wang_hash((khint_t)key)

Definition at line 413 of file khash.h.

kh_key

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

@function @abstract 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 498 of file khash.h.

kh_n_buckets

#define kh_n_buckets

(

h

)

((h)->n_buckets)

@function @abstract 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 540 of file khash.h.

kh_put

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

@function @abstract 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 465 of file khash.h.

kh_resize

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

@function @abstract 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 452 of file khash.h.

kh_size

#define kh_size

(

h

)

((h)->size)

@function @abstract 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 533 of file khash.h.

kh_str_hash_equal

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

@function @abstract Const char* comparison function

Definition at line 401 of file khash.h.

kh_str_hash_func

#define kh_str_hash_func

(

key

)

__ac_X31_hash_string(key)

@function @abstract 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 397 of file khash.h.

kh_val

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

@function @abstract 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] @discussion For hash sets, calling this results in segfault.

Definition at line 507 of file khash.h.

kh_value

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

@function @abstract Alias of kh_val()

Definition at line 512 of file khash.h.

KHASH_DECLARE

#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 348 of file khash.h.

KHASH_INIT

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

Definition at line 356 of file khash.h.

KHASH_INIT2

#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 352 of file khash.h.

KHASH_MAP_INIT_INT

#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 integer keys

Parameters

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

Definition at line 584 of file khash.h.

KHASH_MAP_INIT_INT64

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

@function @abstract 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 599 of file khash.h.

KHASH_MAP_INIT_STR

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

@function @abstract 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 615 of file khash.h.

KHASH_SET_INIT_INT

#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 set containing integer keys

Parameters

name	Name of the hash table [symbol]

Definition at line 576 of file khash.h.

KHASH_SET_INIT_INT64

#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 set containing 64-bit integer keys

Parameters

name	Name of the hash table [symbol]

Definition at line 591 of file khash.h.

KHASH_SET_INIT_STR

#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

Parameters

name	Name of the hash table [symbol]

Definition at line 607 of file khash.h.

khash_t

#define khash_t

(

name

)

kh_##name##_t

@abstract Type of the hash table.

Parameters

name	Name of the hash table [symbol]

Definition at line 423 of file khash.h.

klib_unused

#define klib_unused

Definition at line 149 of file khash.h.

kmalloc

#define kmalloc

(

Z

)

malloc(Z)

Definition at line 174 of file khash.h.

krealloc

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

Definition at line 177 of file khash.h.

kroundup32

#define kroundup32

(

x

)

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

Definition at line 167 of file khash.h.

Typedef Documentation

kh_cstr_t

typedef const char* kh_cstr_t

Definition at line 602 of file khash.h.

khint32_t

typedef uint32_t khint32_t

Definition at line 134 of file khash.h.

khint64_t

typedef uint64_t khint64_t

Definition at line 135 of file khash.h.

khint_t

typedef khint32_t khint_t

Definition at line 153 of file khash.h.

khiter_t

typedef khint_t khiter_t

Definition at line 154 of file khash.h.

Function Documentation

__ac_Wang_hash()

static khint_t __ac_Wang_hash ( khint_t  key )

inlinestatic

Definition at line 403 of file khash.h.

__ac_X31_hash_string()

static khint_t __ac_X31_hash_string ( const char *  s )

inlinestatic

@function @abstract const char* hash function

Parameters

s	Pointer to a null terminated string

Returns

The hash value

Definition at line 386 of file khash.h.

References h, and s.

Variable Documentation

__ac_HASH_UPPER

const double __ac_HASH_UPPER = 0.77

static

Definition at line 183 of file khash.h.