Macros | Typedefs
khash.h File Reference
#include <stdlib.h>
#include <string.h>
#include <limits.h>
#include <stdint.h>
#include "nvim/memory.h"
#include "nvim/func_attr.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]&=~(khint_t)(1ul<<((i&0xfU)<<1)))
 
#define __ac_set_isempty_false(flag, i)   (flag[i>>4]&=~(khint_t)(2ul<<((i&0xfU)<<1)))
 
#define __ac_set_isboth_false(flag, i)   (flag[i>>4]&=~(khint_t)(3ul<<((i&0xfU)<<1)))
 
#define __ac_set_isdel_true(flag, i)   (flag[i>>4]|=(khint_t)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)   xcalloc(N,Z)
 
#define kmalloc(Z)   xmalloc(Z)
 
#define krealloc(P, Z)   xrealloc(P,Z)
 
#define kfree(P)   XFREE_CLEAR(P)
 
#define __ac_HASH_UPPER   0.77
 
#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_dealloc(name, h)   kh_dealloc_##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 kh_foreach_key(h, kvar, 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)
 
#define KHASH_EMPTY_TABLE(name)
 

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)
#define __ac_HASH_UPPER   0.77
#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_isempty (   flag,
  i 
)    ((flag[i>>4]>>((i&0xfU)<<1))&2)
#define __ac_set_isboth_false (   flag,
  i 
)    (flag[i>>4]&=~(khint_t)(3ul<<((i&0xfU)<<1)))
#define __ac_set_isdel_false (   flag,
  i 
)    (flag[i>>4]&=~(khint_t)(1ul<<((i&0xfU)<<1)))
#define __ac_set_isdel_true (   flag,
  i 
)    (flag[i>>4]|=(khint_t)1ul<<((i&0xfU)<<1))
#define __ac_set_isempty_false (   flag,
  i 
)    (flag[i>>4]&=~(khint_t)(2ul<<((i&0xfU)<<1)))
#define __KHASH_IMPL (   name,
  SCOPE,
  khkey_t,
  khval_t,
  kh_is_map,
  __hash_func,
  __hash_equal 
)
#define __KHASH_PROTOTYPES (   name,
  khkey_t,
  khval_t 
)
Value:
extern kh_##name##_t *kh_init_##name(void); \
extern void kh_dealloc_##name(kh_##name##_t *h); \
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 void 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);
const int ret
Definition: eval.c:994
khint32_t khint_t
Definition: khash.h:157
char * name
Definition: eval.c:1955
#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;
khint32_t khint_t
Definition: khash.h:157
char * name
Definition: eval.c:1955
#define AC_VERSION_KHASH_H   "0.2.8"

Generic hash table library.

#define kcalloc (   N,
 
)    xcalloc(N,Z)
#define kfree (   P)    XFREE_CLEAR(P)
#define kh_begin (   h)    (khint_t)(0)

Get the start iterator

Parameters
hPointer to the hash table [khash_t(name)*]
Returns
The start iterator [khint_t]
#define kh_clear (   name,
 
)    kh_clear_##name(h)

Reset a hash table without deallocating memory.

Parameters
nameName of the hash table [symbol]
hPointer to the hash table [khash_t(name)*]
#define kh_dealloc (   name,
 
)    kh_dealloc_##name(h)

Free memory referenced directly inside a hash table.

Parameters
nameName of the hash table [symbol]
hPointer to the hash table [khash_t(name)*]
#define kh_del (   name,
  h,
  k 
)    kh_del_##name(h, k)

Remove a key from the hash table.

Parameters
nameName of the hash table [symbol]
hPointer to the hash table [khash_t(name)*]
kIterator to the element to be deleted [khint_t]
#define kh_destroy (   name,
 
)    kh_destroy_##name(h)

Destroy a hash table.

Parameters
nameName of the hash table [symbol]
hPointer to the hash table [khash_t(name)*]
#define kh_end (   h)    ((h)->n_buckets)

Get the end iterator

Parameters
hPointer to the hash table [khash_t(name)*]
Returns
The end iterator [khint_t]
#define kh_exist (   h,
 
)    (!__ac_iseither((h)->flags, (x)))

Test whether a bucket contains data.

Parameters
hPointer to the hash table [khash_t(name)*]
xIterator to the bucket [khint_t]
Returns
1 if containing data; 0 otherwise [int]
#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; \
} }
#define kh_val(h, x)
Definition: khash.h:587
if(len)
Definition: encode.c:222
#define kh_exist(h, x)
Definition: khash.h:570
khint32_t khint_t
Definition: khash.h:157
#define kh_end(h)
Definition: khash.h:606
for(size_t i=1;i< ARRAY_SIZE(argv);i++)
Definition: typval.c:1215
#define kh_begin(h)
Definition: khash.h:599
#define kh_key(h, x)
Definition: khash.h:578

Iterate over the entries in the hash table

Parameters
hPointer to the hash table [khash_t(name)*]
kvarVariable to which key will be assigned
vvarVariable to which value will be assigned
codeBlock of code to execute
#define kh_foreach_key (   h,
  kvar,
  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); \
code; \
} \
}
if(len)
Definition: encode.c:222
#define kh_exist(h, x)
Definition: khash.h:570
khint32_t khint_t
Definition: khash.h:157
#define kh_end(h)
Definition: khash.h:606
for(size_t i=1;i< ARRAY_SIZE(argv);i++)
Definition: typval.c:1215
#define kh_begin(h)
Definition: khash.h:599
#define kh_key(h, x)
Definition: khash.h:578

Iterate over the keys in the hash table

Parameters
hPointer to the hash table [khash_t(name)*]
kvarVariable to which value will be assigned
codeBlock of code to execute
#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; \
} }
#define kh_val(h, x)
Definition: khash.h:587
if(len)
Definition: encode.c:222
#define kh_exist(h, x)
Definition: khash.h:570
khint32_t khint_t
Definition: khash.h:157
#define kh_end(h)
Definition: khash.h:606
for(size_t i=1;i< ARRAY_SIZE(argv);i++)
Definition: typval.c:1215
#define kh_begin(h)
Definition: khash.h:599

Iterate over the values in the hash table

Parameters
hPointer to the hash table [khash_t(name)*]
vvarVariable to which value will be assigned
codeBlock of code to execute
#define kh_get (   name,
  h,
  k 
)    kh_get_##name(h, k)

Retrieve a key from the hash table.

Parameters
nameName of the hash table [symbol]
hPointer to the hash table [khash_t(name)*]
kKey [type of keys]
Returns
Iterator to the found element, or kh_end(h) if the element is absent [khint_t]
#define kh_init (   name)    kh_init_##name()

Initiate a hash table.

Parameters
nameName of the hash table [symbol]
Returns
Pointer to the hash table [khash_t(name)*]
#define kh_inline   inline
#define kh_int64_hash_equal (   a,
 
)    ((a) == (b))

64-bit integer comparison function

#define kh_int64_hash_func (   key)    (khint32_t)((key)>>33^(key)^(key)<<11)

64-bit integer hash function

Parameters
keyThe integer [khint64_t]
Returns
The hash value [khint_t]
#define kh_int_hash_equal (   a,
 
)    ((a) == (b))

Integer comparison function

#define kh_int_hash_func (   key)    (khint32_t)(key)

Integer hash function

Parameters
keyThe integer [khint32_t]
Returns
The hash value [khint_t]
#define kh_int_hash_func2 (   k)    __ac_Wang_hash((khint_t)key)
#define kh_key (   h,
 
)    ((h)->keys[x])

Get key given an iterator

Parameters
hPointer to the hash table [khash_t(name)*]
xIterator to the bucket [khint_t]
Returns
Key [type of keys]
#define kh_n_buckets (   h)    ((h)->n_buckets)

Get the number of buckets in the hash table

Parameters
hPointer to the hash table [khash_t(name)*]
Returns
Number of buckets in the hash table [khint_t]
#define kh_put (   name,
  h,
  k,
  r 
)    kh_put_##name(h, k, r)

Insert a key to the hash table.

Parameters
nameName of the hash table [symbol]
hPointer to the hash table [khash_t(name)*]
kKey [type of keys]
rExtra 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]
#define kh_resize (   name,
  h,
  s 
)    kh_resize_##name(h, s)

Resize a hash table.

Parameters
nameName of the hash table [symbol]
hPointer to the hash table [khash_t(name)*]
sNew size [khint_t]
#define kh_size (   h)    ((h)->size)

Get the number of elements in the hash table

Parameters
hPointer to the hash table [khash_t(name)*]
Returns
Number of elements in the hash table [khint_t]
#define kh_str_hash_equal (   a,
 
)    (strcmp(a, b) == 0)

Const char* comparison function

#define kh_str_hash_func (   key)    __ac_X31_hash_string(key)

Another interface to const char* hash function

Parameters
keyPointer to a null terminated string [const char*]
Returns
The hash value [khint_t]
#define kh_val (   h,
 
)    ((h)->vals[x])

Get value given an iterator

Parameters
hPointer to the hash table [khash_t(name)*]
xIterator to the bucket [khint_t]
Returns
Value [type of values] For hash sets, calling this results in segfault.
#define kh_value (   h,
 
)    ((h)->vals[x])

Alias of kh_val()

#define KHASH_DECLARE (   name,
  khkey_t,
  khval_t 
)
Value:
__KHASH_TYPE(name, khkey_t, khval_t) \
__KHASH_PROTOTYPES(name, khkey_t, khval_t)
#define __KHASH_TYPE(name, khkey_t, khval_t)
Definition: khash.h:189
#define __KHASH_PROTOTYPES(name, khkey_t, khval_t)
Definition: khash.h:197
char * name
Definition: eval.c:1955
#define KHASH_EMPTY_TABLE (   name)
Value:
((kh_##name##_t) { \
.n_buckets = 0, \
.size = 0, \
.n_occupied = 0, \
.upper_bound = 0, \
.flags = NULL, \
.keys = NULL, \
.vals = NULL, \
})
return NULL
Definition: eval.c:23556
char * name
Definition: eval.c:1955

Return a literal for an empty hash table.

Parameters
nameName of the hash table [symbol]
#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 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)
#define __KHASH_TYPE(name, khkey_t, khval_t)
Definition: khash.h:189
#define __KHASH_IMPL(name, SCOPE, khkey_t, khval_t, kh_is_map, __hash_func, __hash_equal)
Definition: khash.h:207
char * name
Definition: eval.c:1955
#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
nameName of the hash table [symbol]
khval_tType 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)

Instantiate a hash map containing 64-bit integer keys

Parameters
nameName of the hash table [symbol]
khval_tType 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)

Instantiate a hash map containing const char* keys

Parameters
nameName of the hash table [symbol]
khval_tType of values [type]
#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
nameName 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)

Instantiate a hash map containing 64-bit integer keys

Parameters
nameName 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)

Instantiate a hash map containing const char* keys

Parameters
nameName of the hash table [symbol]
#define khash_t (   name)    kh_##name##_t

Type of the hash table.

Parameters
nameName of the hash table [symbol]
#define kmalloc (   Z)    xmalloc(Z)
#define krealloc (   P,
 
)    xrealloc(P,Z)
#define kroundup32 (   x)    (--(x), (x)|=(x)>>1, (x)|=(x)>>2, (x)|=(x)>>4, (x)|=(x)>>8, (x)|=(x)>>16, ++(x))

Typedef Documentation

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