Data Structures | Macros | Typedefs | Variables
hashtab.h File Reference
#include <stddef.h>
#include "nvim/types.h"

Go to the source code of this file.

Data Structures

struct  hashitem_S
struct  hashtable_S


#define HI_KEY_REMOVED   ((char_u *)&hash_removed)
#define HASHITEM_EMPTY(hi)
#define HT_INIT_SIZE   16
#define HASHTAB_ITER(ht, hi, code)


typedef size_t hash_T
 Type for hash number (hash calculation result). More...
typedef struct hashitem_S hashitem_T
typedef struct hashtable_S hashtab_T


char hash_removed

Macro Definition Documentation


#define HASHITEM_EMPTY (   hi)
((hi)->hi_key == NULL \
|| (hi)->hi_key == (char_u *)&hash_removed)


#define HASHTAB_ITER (   ht,
do { \
hashtab_T *const hi##ht_ = (ht); \
size_t hi##todo_ = hi##ht_->ht_used; \
for (hashitem_T *hi = hi##ht_->ht_array; hi##todo_; hi++) { \
if (!HASHITEM_EMPTY(hi)) { \
hi##todo_--; \
{ \
code \
} \
} \
} \
} while (0)

Iterate over a hashtab

[in]htHashtab to iterate over.
hiName of the variable with current hashtab entry.
codeCycle body.


#define HI_KEY_REMOVED   ((char_u *)&hash_removed)

The address of "hash_removed" is used as a magic number for hi_key to indicate a removed item.


#define HT_INIT_SIZE   16

Initial size for a hashtable. Our items are relatively small and growing is expensive, thus start with 16. Must be a power of 2. This allows for storing 10 items (2/3 of 16) before a resize is needed.

Typedef Documentation

◆ hash_T

typedef size_t hash_T

Type for hash number (hash calculation result).

◆ hashitem_T

typedef struct hashitem_S hashitem_T

Hashtable item.

Each item has a NUL terminated string key. A key can appear only once in the table.

A hash number is computed from the key for quick lookup. When the hashes of two different keys point to the same entry an algorithm is used to iterate over other entries in the table until the right one is found. To make the iteration work removed keys are different from entries where a key was never present.

Note that this does not contain a pointer to the key and another pointer to the value. Instead, it is assumed that the key is contained within the value, so that you can get a pointer to the value subtracting an offset from the pointer to the key. This reduces the size of this item by 1/3.

◆ hashtab_T

typedef struct hashtable_S hashtab_T

An array-based hashtable.

Keys are NUL terminated strings. They cannot be repeated within a table. Values are of any type.

The hashtable grows to accommodate more entries when needed.

Variable Documentation

◆ hash_removed

char hash_removed

Magic number used for hashitem "hi_key" value indicating a deleted item

Only the address is used.

hashtab_T * ht
Definition: eval.c:2001
char hash_removed
Definition: hashtab.c:42
unsigned char char_u
Definition: types.h:12
return NULL
Definition: eval.c:9968
Definition: hashtab.h:38
#define HASHITEM_EMPTY(hi)
Definition: hashtab.h:19