Macros | Typedefs | Variables
khash.h File Reference
#include <limits.h>
#include <stdint.h>
#include <stdlib.h>
#include <string.h>
#include "nvim/func_attr.h"
#include "nvim/memory.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)
 
#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
 

Variables

const typedef char * kh_cstr_t
 

Macro Definition Documentation

◆ __ac_fsize

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

◆ __ac_HASH_UPPER

#define __ac_HASH_UPPER   0.77

◆ __ac_isdel

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

◆ __ac_iseither

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

◆ __ac_isempty

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

◆ __ac_set_isboth_false

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

◆ __ac_set_isdel_false

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

◆ __ac_set_isdel_true

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

◆ __ac_set_isempty_false

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

◆ __KHASH_IMPL

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

◆ __KHASH_PROTOTYPES

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

◆ __KHASH_TYPE

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

◆ AC_VERSION_KHASH_H

#define AC_VERSION_KHASH_H   "0.2.8"

@header

Generic hash table library.

◆ kcalloc

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

◆ kfree

#define kfree (   P)    XFREE_CLEAR(P)

◆ kh_begin

#define kh_begin (   h)    (khint_t)(0)

@function @abstract Get the start iterator

Parameters
hPointer to the hash table [khash_t(name)*]
Returns
The start iterator [khint_t]

◆ kh_clear

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

@function @abstract Reset a hash table without deallocating memory.

Parameters
nameName of the hash table [symbol]
hPointer to the hash table [khash_t(name)*]

◆ kh_dealloc

#define kh_dealloc (   name,
 
)    kh_dealloc_##name(h)

@function @abstract Free memory referenced directly inside a hash table.

Parameters
nameName of the hash table [symbol]
hPointer to the hash table [khash_t(name)*]

◆ kh_del

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

@function @abstract 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]

◆ kh_destroy

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

@function @abstract Destroy a hash table.

Parameters
nameName of the hash table [symbol]
hPointer to the hash table [khash_t(name)*]

◆ kh_end

#define kh_end (   h)    ((h)->n_buckets)

@function @abstract Get the end iterator

Parameters
hPointer to the hash table [khash_t(name)*]
Returns
The end iterator [khint_t]

◆ kh_exist

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

@function @abstract 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]

◆ 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
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

◆ kh_foreach_key

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

@function @abstract 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

◆ 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
hPointer to the hash table [khash_t(name)*]
vvarVariable to which value will be assigned
codeBlock of code to execute

◆ kh_get

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

@function @abstract 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]

◆ kh_init

#define kh_init (   name)    kh_init_##name()

@function @abstract Initiate a hash table.

Parameters
nameName of the hash table [symbol]
Returns
Pointer to the hash table [khash_t(name)*]

◆ kh_inline

#define kh_inline   inline

◆ kh_int64_hash_equal

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

@function @abstract 64-bit integer comparison function

◆ 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
keyThe integer [khint64_t]
Returns
The hash value [khint_t]

◆ kh_int_hash_equal

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

@function @abstract Integer comparison function

◆ kh_int_hash_func

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

@function @abstract Integer hash function

Parameters
keyThe integer [khint32_t]
Returns
The hash value [khint_t]

◆ kh_int_hash_func2

#define kh_int_hash_func2 (   k)    __ac_Wang_hash((khint_t)key)

◆ kh_key

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

@function @abstract 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]

◆ kh_n_buckets

#define kh_n_buckets (   h)    ((h)->n_buckets)

@function @abstract 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]

◆ 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
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]

◆ kh_resize

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

@function @abstract Resize a hash table.

Parameters
nameName of the hash table [symbol]
hPointer to the hash table [khash_t(name)*]
sNew size [khint_t]

◆ kh_size

#define kh_size (   h)    ((h)->size)

@function @abstract 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]

◆ kh_str_hash_equal

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

@function @abstract Const char* comparison function

◆ 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
keyPointer to a null terminated string [const char*]
Returns
The hash value [khint_t]

◆ kh_val

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

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

◆ kh_value

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

@function @abstract Alias of kh_val()

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

◆ KHASH_EMPTY_TABLE

#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, \
})

@function @abstract Return a literal for an empty hash table.

Parameters
nameName of the hash table [symbol]

◆ KHASH_INIT

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

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

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

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

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

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

◆ 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 map containing 64-bit integer keys

Parameters
nameName of the hash table [symbol]

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

◆ khash_t

#define khash_t (   name)    kh_##name##_t

@abstract Type of the hash table.

Parameters
nameName of the hash table [symbol]

◆ kmalloc

#define kmalloc (   Z)    xmalloc(Z)

◆ krealloc

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

◆ kroundup32

#define kroundup32 (   x)
Value:
(--(x), (x)|=(x)>>1, (x)|=(x)>>2, (x)|=(x)>>4, (x)|=(x)>>8, (x)|=(x)>>16, \
++(x))

Typedef Documentation

◆ khint64_t

typedef unsigned long khint64_t

◆ khint_t

typedef khint32_t khint_t

◆ khiter_t

typedef khint_t khiter_t

Variable Documentation

◆ kh_cstr_t

const typedef char* kh_cstr_t
kh_key
#define kh_key(h, x)
Definition: khash.h:579
size
size_t size
Definition: regexp_nfa.c:5109
__KHASH_TYPE
#define __KHASH_TYPE(name, khkey_t, khval_t)
Definition: khash.h:189
ret
const int ret
Definition: eval.c:722
kh_begin
#define kh_begin(h)
Definition: khash.h:600
khint_t
khint32_t khint_t
Definition: khash.h:156
kh_exist
#define kh_exist(h, x)
Definition: khash.h:571
kh_end
#define kh_end(h)
Definition: khash.h:607
kh_val
#define kh_val(h, x)
Definition: khash.h:588
name
char_u * name
Definition: userfunc.c:821
NULL
return NULL
Definition: eval.c:10355