1#ifndef NVIM_HASHTAB_H
2#define NVIM_HASHTAB_H
3
4#include <stddef.h>
5
6#include "nvim/types.h"
7
8/// Magic number used for hashitem "hi_key" value indicating a deleted item
9///
10/// Only the address is used.
11extern char hash_removed;
12
13/// Type for hash number (hash calculation result).
14typedef size_t hash_T;
15
16/// The address of "hash_removed" is used as a magic number
17/// for hi_key to indicate a removed item.
18#define HI_KEY_REMOVED ((char_u *)&hash_removed)
19#define HASHITEM_EMPTY(hi) ((hi)->hi_key == NULL \
20 || (hi)->hi_key == (char_u *)&hash_removed)
21
22/// Hashtable item.
23///
24/// Each item has a NUL terminated string key.
25/// A key can appear only once in the table.
26///
27/// A hash number is computed from the key for quick lookup. When the hashes
28/// of two different keys point to the same entry an algorithm is used to
29/// iterate over other entries in the table until the right one is found.
30/// To make the iteration work removed keys are different from entries where a
31/// key was never present.
32///
33/// Note that this does not contain a pointer to the key and another pointer to
34/// the value. Instead, it is assumed that the key is contained within the
35/// value, so that you can get a pointer to the value subtracting an offset from
36/// the pointer to the key.
37/// This reduces the size of this item by 1/3.
38typedef struct hashitem_S {
39 /// Cached hash number for hi_key.
40 hash_T hi_hash;
41
42 /// Item key.
43 ///
44 /// Possible values mean the following:
45 /// NULL : Item was never used.
46 /// HI_KEY_REMOVED : Item was removed.
47 /// (Any other pointer value) : Item is currently being used.
48 char_u *hi_key;
49} hashitem_T;
50
51/// Initial size for a hashtable.
52/// Our items are relatively small and growing is expensive, thus start with 16.
53/// Must be a power of 2.
54#define HT_INIT_SIZE 16
55
56/// An array-based hashtable.
57///
58/// Keys are NUL terminated strings. They cannot be repeated within a table.
59/// Values are of any type.
60///
61/// The hashtable grows to accommodate more entries when needed.
62typedef struct hashtable_S {
63 hash_T ht_mask; /// mask used for hash value
64 /// (nr of items in array is "ht_mask" + 1)
65 size_t ht_used; /// number of items used
66 size_t ht_filled; /// number of items used or removed
67 int ht_locked; /// counter for hash_lock()
68 hashitem_T *ht_array; /// points to the array, allocated when it's
69 /// not "ht_smallarray"
70 hashitem_T ht_smallarray[HT_INIT_SIZE]; /// initial array
71} hashtab_T;
72
73/// Iterate over a hashtab
74///
75/// @param[in] ht Hashtab to iterate over.
76/// @param hi Name of the variable with current hashtab entry.
77/// @param code Cycle body.
78#define HASHTAB_ITER(ht, hi, code) \
79 do { \
80 hashtab_T *const hi##ht_ = (ht); \
81 size_t hi##todo_ = hi##ht_->ht_used; \
82 for (hashitem_T *hi = hi##ht_->ht_array; hi##todo_; hi++) { \
83 if (!HASHITEM_EMPTY(hi)) { \
84 { \
85 code \
86 } \
87 hi##todo_--; \
88 } \
89 } \
90 } while (0)
91
92#ifdef INCLUDE_GENERATED_DECLARATIONS
93# include "hashtab.h.generated.h"
94#endif
95
96#endif // NVIM_HASHTAB_H
97