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 |
#define HASHITEM_EMPTY | ( | hi | ) |
#define HASHTAB_ITER | ( | ht, | |
hi, | |||
code | |||
) |
Iterate over a hashtab
[in] | ht | Hashtab to iterate over. |
hi | Name of the variable with current hashtab entry. | |
code | Cycle 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 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.
char hash_removed |
Magic number used for hashitem "hi_key" value indicating a deleted item
Only the address is used.