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
 

Macros

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

Typedefs

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
 

Variables

char hash_removed
 

Macro Definition Documentation

#define HASHITEM_EMPTY (   hi)
Value:
((hi)->hi_key == NULL \
|| (hi)->hi_key == (char_u *)&hash_removed)
return NULL
Definition: eval.c:23643
char hash_removed
Definition: hashtab.c:42
unsigned char char_u
Definition: types.h:11
#define HASHTAB_ITER (   ht,
  hi,
  code 
)
Value:
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)) { \
{ \
code \
} \
hi##todo_--; \
} \
} \
} while (0)
#define HASHITEM_EMPTY(hi)
Definition: hashtab.h:19
if(len)
Definition: encode.c:222
for(size_t i=1;i< ARRAY_SIZE(argv);i++)
Definition: typval.c:1215
size_t ht_used
Definition: hashtab.h:65
struct hashtable_S hashtab_T
hashtab_T * ht
Definition: eval.c:2141
Definition: hashtab.h:38

Iterate over a hashtab

Parameters
[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.

Typedef Documentation

typedef size_t hash_T

Type for hash number (hash calculation result).

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.

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

char hash_removed

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

Only the address is used.