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. |
11 | extern char hash_removed; |
12 | |
13 | /// Type for hash number (hash calculation result). |
14 | typedef 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. |
38 | typedef 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. |
62 | typedef 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 | |