Mercurial > vim
annotate src/hashtab.c @ 34074:1629cc65d78d v9.1.0006
patch 9.1.0006: is*() and to*() function may be unsafe
Commit: https://github.com/vim/vim/commit/184f71cc6868a240dc872ed2852542bbc1d43e28
Author: Keith Thompson <Keith.S.Thompson@gmail.com>
Date: Thu Jan 4 21:19:04 2024 +0100
patch 9.1.0006: is*() and to*() function may be unsafe
Problem: is*() and to*() function may be unsafe
Solution: Add SAFE_* macros and start using those instead
(Keith Thompson)
Use SAFE_() macros for is*() and to*() functions
The standard is*() and to*() functions declared in <ctype.h> have
undefined behavior for negative arguments other than EOF. If plain char
is signed, passing an unchecked value from argv for from user input
to one of these functions has undefined behavior.
Solution: Add SAFE_*() macros that cast the argument to unsigned char.
Most implementations behave sanely for negative arguments, and most
character values in practice are non-negative, but it's still best
to avoid undefined behavior.
The change from #13347 has been omitted, as this has already been
separately fixed in commit ac709e2fc0db6d31abb7da96f743c40956b60c3a
(v9.0.2054)
fixes: #13332
closes: #13347
Signed-off-by: Keith Thompson <Keith.S.Thompson@gmail.com>
Signed-off-by: Christian Brabandt <cb@256bit.org>
| author | Christian Brabandt <cb@256bit.org> |
|---|---|
| date | Thu, 04 Jan 2024 21:30:04 +0100 |
| parents | 04d9dff67d99 |
| children |
| rev | line source |
|---|---|
|
10042
4aead6a9b7a9
commit https://github.com/vim/vim/commit/edf3f97ae2af024708ebb4ac614227327033ca47
Christian Brabandt <cb@256bit.org>
parents:
9513
diff
changeset
|
1 /* vi:set ts=8 sts=4 sw=4 noet: |
| 799 | 2 * |
| 3 * VIM - Vi IMproved by Bram Moolenaar | |
| 4 * | |
| 5 * Do ":help uganda" in Vim to read copying and usage conditions. | |
| 6 * Do ":help credits" in Vim to see a list of people who contributed. | |
| 7 * See README.txt for an overview of the Vim source code. | |
| 8 */ | |
| 9 | |
| 10 /* | |
| 11 * hashtab.c: Handling of a hashtable with Vim-specific properties. | |
| 12 * | |
| 13 * Each item in a hashtable has a NUL terminated string key. A key can appear | |
| 14 * only once in the table. | |
| 15 * | |
| 16 * A hash number is computed from the key for quick lookup. When the hashes | |
| 17 * of two different keys point to the same entry an algorithm is used to | |
| 18 * iterate over other entries in the table until the right one is found. | |
| 19 * To make the iteration work removed keys are different from entries where a | |
| 20 * key was never present. | |
| 21 * | |
| 22 * The mechanism has been partly based on how Python Dictionaries are | |
| 23 * implemented. The algorithm is from Knuth Vol. 3, Sec. 6.4. | |
| 24 * | |
| 25 * The hashtable grows to accommodate more entries when needed. At least 1/3 | |
| 26 * of the entries is empty to keep the lookup efficient (at the cost of extra | |
| 27 * memory). | |
| 28 */ | |
| 29 | |
| 30 #include "vim.h" | |
| 31 | |
| 32 #if 0 | |
|
18798
f0f9692d4487
patch 8.1.2387: using old C style comments
Bram Moolenaar <Bram@vim.org>
parents:
17508
diff
changeset
|
33 # define HT_DEBUG // extra checks for table consistency and statistics |
| 799 | 34 |
|
18798
f0f9692d4487
patch 8.1.2387: using old C style comments
Bram Moolenaar <Bram@vim.org>
parents:
17508
diff
changeset
|
35 static long hash_count_lookup = 0; // count number of hashtab lookups |
|
f0f9692d4487
patch 8.1.2387: using old C style comments
Bram Moolenaar <Bram@vim.org>
parents:
17508
diff
changeset
|
36 static long hash_count_perturb = 0; // count number of "misses" |
| 799 | 37 #endif |
| 38 | |
|
18798
f0f9692d4487
patch 8.1.2387: using old C style comments
Bram Moolenaar <Bram@vim.org>
parents:
17508
diff
changeset
|
39 // Magic value for algorithm that walks through the array. |
| 799 | 40 #define PERTURB_SHIFT 5 |
| 41 | |
|
7803
37c929c4a073
commit https://github.com/vim/vim/commit/92b8b2d307e34117f146319872010b0ccc9d2713
Christian Brabandt <cb@256bit.org>
parents:
3970
diff
changeset
|
42 static int hash_may_resize(hashtab_T *ht, int minitems); |
| 799 | 43 |
|
18798
f0f9692d4487
patch 8.1.2387: using old C style comments
Bram Moolenaar <Bram@vim.org>
parents:
17508
diff
changeset
|
44 #if 0 // currently not used |
| 799 | 45 /* |
| 46 * Create an empty hash table. | |
| 47 * Returns NULL when out of memory. | |
| 48 */ | |
| 49 hashtab_T * | |
|
7823
bcef391c101c
commit https://github.com/vim/vim/commit/68c2f638e65d914dc6e84eb7ce2624f08af525c0
Christian Brabandt <cb@256bit.org>
parents:
7803
diff
changeset
|
50 hash_create(void) |
| 799 | 51 { |
| 52 hashtab_T *ht; | |
| 53 | |
|
16825
ce04ebdf26b8
patch 8.1.1414: alloc() returning "char_u *" causes a lot of type casts
Bram Moolenaar <Bram@vim.org>
parents:
16764
diff
changeset
|
54 ht = ALLOC_ONE(hashtab_T); |
| 799 | 55 if (ht != NULL) |
| 56 hash_init(ht); | |
| 57 return ht; | |
| 58 } | |
| 59 #endif | |
| 60 | |
| 61 /* | |
| 62 * Initialize an empty hash table. | |
| 63 */ | |
| 64 void | |
|
7823
bcef391c101c
commit https://github.com/vim/vim/commit/68c2f638e65d914dc6e84eb7ce2624f08af525c0
Christian Brabandt <cb@256bit.org>
parents:
7803
diff
changeset
|
65 hash_init(hashtab_T *ht) |
| 799 | 66 { |
|
18798
f0f9692d4487
patch 8.1.2387: using old C style comments
Bram Moolenaar <Bram@vim.org>
parents:
17508
diff
changeset
|
67 // This zeroes all "ht_" entries and all the "hi_key" in "ht_smallarray". |
|
20007
aadd1cae2ff5
patch 8.2.0559: clearing a struct is verbose
Bram Moolenaar <Bram@vim.org>
parents:
18798
diff
changeset
|
68 CLEAR_POINTER(ht); |
| 799 | 69 ht->ht_array = ht->ht_smallarray; |
| 70 ht->ht_mask = HT_INIT_SIZE - 1; | |
| 71 } | |
| 72 | |
| 73 /* | |
|
31231
684e6dfa2fba
patch 9.0.0949: crash when unletting a variable while listing variables
Bram Moolenaar <Bram@vim.org>
parents:
27521
diff
changeset
|
74 * If "ht->ht_flags" has HTFLAGS_FROZEN then give an error message using |
|
684e6dfa2fba
patch 9.0.0949: crash when unletting a variable while listing variables
Bram Moolenaar <Bram@vim.org>
parents:
27521
diff
changeset
|
75 * "command" and return TRUE. |
|
684e6dfa2fba
patch 9.0.0949: crash when unletting a variable while listing variables
Bram Moolenaar <Bram@vim.org>
parents:
27521
diff
changeset
|
76 */ |
|
684e6dfa2fba
patch 9.0.0949: crash when unletting a variable while listing variables
Bram Moolenaar <Bram@vim.org>
parents:
27521
diff
changeset
|
77 int |
|
684e6dfa2fba
patch 9.0.0949: crash when unletting a variable while listing variables
Bram Moolenaar <Bram@vim.org>
parents:
27521
diff
changeset
|
78 check_hashtab_frozen(hashtab_T *ht, char *command) |
|
684e6dfa2fba
patch 9.0.0949: crash when unletting a variable while listing variables
Bram Moolenaar <Bram@vim.org>
parents:
27521
diff
changeset
|
79 { |
|
684e6dfa2fba
patch 9.0.0949: crash when unletting a variable while listing variables
Bram Moolenaar <Bram@vim.org>
parents:
27521
diff
changeset
|
80 if ((ht->ht_flags & HTFLAGS_FROZEN) == 0) |
|
684e6dfa2fba
patch 9.0.0949: crash when unletting a variable while listing variables
Bram Moolenaar <Bram@vim.org>
parents:
27521
diff
changeset
|
81 return FALSE; |
|
684e6dfa2fba
patch 9.0.0949: crash when unletting a variable while listing variables
Bram Moolenaar <Bram@vim.org>
parents:
27521
diff
changeset
|
82 |
|
684e6dfa2fba
patch 9.0.0949: crash when unletting a variable while listing variables
Bram Moolenaar <Bram@vim.org>
parents:
27521
diff
changeset
|
83 semsg(_(e_not_allowed_to_add_or_remove_entries_str), command); |
|
684e6dfa2fba
patch 9.0.0949: crash when unletting a variable while listing variables
Bram Moolenaar <Bram@vim.org>
parents:
27521
diff
changeset
|
84 return TRUE; |
|
684e6dfa2fba
patch 9.0.0949: crash when unletting a variable while listing variables
Bram Moolenaar <Bram@vim.org>
parents:
27521
diff
changeset
|
85 } |
|
684e6dfa2fba
patch 9.0.0949: crash when unletting a variable while listing variables
Bram Moolenaar <Bram@vim.org>
parents:
27521
diff
changeset
|
86 |
|
684e6dfa2fba
patch 9.0.0949: crash when unletting a variable while listing variables
Bram Moolenaar <Bram@vim.org>
parents:
27521
diff
changeset
|
87 /* |
| 799 | 88 * Free the array of a hash table. Does not free the items it contains! |
| 89 * If "ht" is not freed then you should call hash_init() next! | |
| 90 */ | |
| 91 void | |
|
7823
bcef391c101c
commit https://github.com/vim/vim/commit/68c2f638e65d914dc6e84eb7ce2624f08af525c0
Christian Brabandt <cb@256bit.org>
parents:
7803
diff
changeset
|
92 hash_clear(hashtab_T *ht) |
| 799 | 93 { |
| 94 if (ht->ht_array != ht->ht_smallarray) | |
| 95 vim_free(ht->ht_array); | |
| 96 } | |
| 97 | |
|
22226
4ed106deb772
patch 8.2.1662: :mksession does not restore shared terminal buffer properly
Bram Moolenaar <Bram@vim.org>
parents:
21317
diff
changeset
|
98 #if defined(FEAT_SPELL) || defined(FEAT_TERMINAL) || defined(PROTO) |
| 799 | 99 /* |
| 100 * Free the array of a hash table and all the keys it contains. The keys must | |
| 101 * have been allocated. "off" is the offset from the start of the allocate | |
| 102 * memory to the location of the key (it's always positive). | |
| 103 */ | |
| 104 void | |
|
7823
bcef391c101c
commit https://github.com/vim/vim/commit/68c2f638e65d914dc6e84eb7ce2624f08af525c0
Christian Brabandt <cb@256bit.org>
parents:
7803
diff
changeset
|
105 hash_clear_all(hashtab_T *ht, int off) |
| 799 | 106 { |
| 835 | 107 long todo; |
| 799 | 108 hashitem_T *hi; |
| 109 | |
| 835 | 110 todo = (long)ht->ht_used; |
|
32118
04d9dff67d99
patch 9.0.1390: FOR_ALL_ macros are defined in an unexpected file
Bram Moolenaar <Bram@vim.org>
parents:
31535
diff
changeset
|
111 FOR_ALL_HASHTAB_ITEMS(ht, hi, todo) |
| 799 | 112 { |
| 113 if (!HASHITEM_EMPTY(hi)) | |
| 114 { | |
| 115 vim_free(hi->hi_key - off); | |
| 116 --todo; | |
| 117 } | |
| 118 } | |
| 119 hash_clear(ht); | |
| 120 } | |
|
15555
d89c5b339c2a
patch 8.1.0785: depending on the configuration some functions are unused
Bram Moolenaar <Bram@vim.org>
parents:
15470
diff
changeset
|
121 #endif |
| 799 | 122 |
| 123 /* | |
| 124 * Find "key" in hashtable "ht". "key" must not be NULL. | |
| 125 * Always returns a pointer to a hashitem. If the item was not found then | |
| 126 * HASHITEM_EMPTY() is TRUE. The pointer is then the place where the key | |
| 127 * would be added. | |
| 128 * WARNING: The returned pointer becomes invalid when the hashtable is changed | |
| 129 * (adding, setting or removing an item)! | |
| 130 */ | |
| 131 hashitem_T * | |
|
7823
bcef391c101c
commit https://github.com/vim/vim/commit/68c2f638e65d914dc6e84eb7ce2624f08af525c0
Christian Brabandt <cb@256bit.org>
parents:
7803
diff
changeset
|
132 hash_find(hashtab_T *ht, char_u *key) |
| 799 | 133 { |
| 134 return hash_lookup(ht, key, hash_hash(key)); | |
| 135 } | |
| 136 | |
| 137 /* | |
| 138 * Like hash_find(), but caller computes "hash". | |
| 139 */ | |
| 140 hashitem_T * | |
|
7823
bcef391c101c
commit https://github.com/vim/vim/commit/68c2f638e65d914dc6e84eb7ce2624f08af525c0
Christian Brabandt <cb@256bit.org>
parents:
7803
diff
changeset
|
141 hash_lookup(hashtab_T *ht, char_u *key, hash_T hash) |
| 799 | 142 { |
| 143 hash_T perturb; | |
| 144 hashitem_T *freeitem; | |
| 145 hashitem_T *hi; | |
| 3970 | 146 unsigned idx; |
| 799 | 147 |
| 148 #ifdef HT_DEBUG | |
| 149 ++hash_count_lookup; | |
| 150 #endif | |
| 151 | |
| 152 /* | |
| 153 * Quickly handle the most common situations: | |
| 154 * - return if there is no item at all | |
| 155 * - skip over a removed item | |
| 156 * - return if the item matches | |
| 157 */ | |
| 3970 | 158 idx = (unsigned)(hash & ht->ht_mask); |
| 799 | 159 hi = &ht->ht_array[idx]; |
| 160 | |
| 161 if (hi->hi_key == NULL) | |
| 162 return hi; | |
| 163 if (hi->hi_key == HI_KEY_REMOVED) | |
| 164 freeitem = hi; | |
| 165 else if (hi->hi_hash == hash && STRCMP(hi->hi_key, key) == 0) | |
| 166 return hi; | |
| 167 else | |
| 168 freeitem = NULL; | |
| 169 | |
| 170 /* | |
| 171 * Need to search through the table to find the key. The algorithm | |
| 172 * to step through the table starts with large steps, gradually becoming | |
| 173 * smaller down to (1/4 table size + 1). This means it goes through all | |
| 174 * table entries in the end. | |
| 175 * When we run into a NULL key it's clear that the key isn't there. | |
| 176 * Return the first available slot found (can be a slot of a removed | |
| 177 * item). | |
| 178 */ | |
| 179 for (perturb = hash; ; perturb >>= PERTURB_SHIFT) | |
| 180 { | |
| 181 #ifdef HT_DEBUG | |
|
18798
f0f9692d4487
patch 8.1.2387: using old C style comments
Bram Moolenaar <Bram@vim.org>
parents:
17508
diff
changeset
|
182 ++hash_count_perturb; // count a "miss" for hashtab lookup |
| 799 | 183 #endif |
| 3970 | 184 idx = (unsigned)((idx << 2U) + idx + perturb + 1U); |
| 799 | 185 hi = &ht->ht_array[idx & ht->ht_mask]; |
| 186 if (hi->hi_key == NULL) | |
| 187 return freeitem == NULL ? hi : freeitem; | |
| 188 if (hi->hi_hash == hash | |
| 189 && hi->hi_key != HI_KEY_REMOVED | |
| 190 && STRCMP(hi->hi_key, key) == 0) | |
| 191 return hi; | |
| 192 if (hi->hi_key == HI_KEY_REMOVED && freeitem == NULL) | |
| 193 freeitem = hi; | |
| 194 } | |
| 195 } | |
| 196 | |
|
15555
d89c5b339c2a
patch 8.1.0785: depending on the configuration some functions are unused
Bram Moolenaar <Bram@vim.org>
parents:
15470
diff
changeset
|
197 #if defined(FEAT_EVAL) || defined(FEAT_SYN_HL) || defined(PROTO) |
| 799 | 198 /* |
| 199 * Print the efficiency of hashtable lookups. | |
| 200 * Useful when trying different hash algorithms. | |
| 201 * Called when exiting. | |
| 202 */ | |
| 203 void | |
|
7823
bcef391c101c
commit https://github.com/vim/vim/commit/68c2f638e65d914dc6e84eb7ce2624f08af525c0
Christian Brabandt <cb@256bit.org>
parents:
7803
diff
changeset
|
204 hash_debug_results(void) |
| 799 | 205 { |
|
27521
3ad379c0ab28
patch 8.2.4288: preprocessor indents are inconsistent
Bram Moolenaar <Bram@vim.org>
parents:
27018
diff
changeset
|
206 # ifdef HT_DEBUG |
| 799 | 207 fprintf(stderr, "\r\n\r\n\r\n\r\n"); |
| 208 fprintf(stderr, "Number of hashtable lookups: %ld\r\n", hash_count_lookup); | |
| 209 fprintf(stderr, "Number of perturb loops: %ld\r\n", hash_count_perturb); | |
| 210 fprintf(stderr, "Percentage of perturb loops: %ld%%\r\n", | |
| 211 hash_count_perturb * 100 / hash_count_lookup); | |
|
27521
3ad379c0ab28
patch 8.2.4288: preprocessor indents are inconsistent
Bram Moolenaar <Bram@vim.org>
parents:
27018
diff
changeset
|
212 # endif |
| 799 | 213 } |
|
15555
d89c5b339c2a
patch 8.1.0785: depending on the configuration some functions are unused
Bram Moolenaar <Bram@vim.org>
parents:
15470
diff
changeset
|
214 #endif |
| 799 | 215 |
| 216 /* | |
| 217 * Add item with key "key" to hashtable "ht". | |
|
31231
684e6dfa2fba
patch 9.0.0949: crash when unletting a variable while listing variables
Bram Moolenaar <Bram@vim.org>
parents:
27521
diff
changeset
|
218 * "command" is used for the error message when the hashtab if frozen. |
| 799 | 219 * Returns FAIL when out of memory or the key is already present. |
| 220 */ | |
| 221 int | |
|
31231
684e6dfa2fba
patch 9.0.0949: crash when unletting a variable while listing variables
Bram Moolenaar <Bram@vim.org>
parents:
27521
diff
changeset
|
222 hash_add(hashtab_T *ht, char_u *key, char *command) |
| 799 | 223 { |
| 224 hash_T hash = hash_hash(key); | |
| 225 hashitem_T *hi; | |
| 226 | |
|
31231
684e6dfa2fba
patch 9.0.0949: crash when unletting a variable while listing variables
Bram Moolenaar <Bram@vim.org>
parents:
27521
diff
changeset
|
227 if (check_hashtab_frozen(ht, command)) |
|
684e6dfa2fba
patch 9.0.0949: crash when unletting a variable while listing variables
Bram Moolenaar <Bram@vim.org>
parents:
27521
diff
changeset
|
228 return FAIL; |
| 799 | 229 hi = hash_lookup(ht, key, hash); |
| 230 if (!HASHITEM_EMPTY(hi)) | |
| 231 { | |
|
10359
66f1b5bf3fa6
commit https://github.com/vim/vim/commit/95f096030ed1a8afea028f2ea295d6f6a70f466f
Christian Brabandt <cb@256bit.org>
parents:
10042
diff
changeset
|
232 internal_error("hash_add()"); |
| 799 | 233 return FAIL; |
| 234 } | |
| 235 return hash_add_item(ht, hi, key, hash); | |
| 236 } | |
| 237 | |
| 238 /* | |
| 239 * Add item "hi" with "key" to hashtable "ht". "key" must not be NULL and | |
| 240 * "hi" must have been obtained with hash_lookup() and point to an empty item. | |
| 241 * "hi" is invalid after this! | |
| 242 * Returns OK or FAIL (out of memory). | |
| 243 */ | |
| 244 int | |
|
7823
bcef391c101c
commit https://github.com/vim/vim/commit/68c2f638e65d914dc6e84eb7ce2624f08af525c0
Christian Brabandt <cb@256bit.org>
parents:
7803
diff
changeset
|
245 hash_add_item( |
|
bcef391c101c
commit https://github.com/vim/vim/commit/68c2f638e65d914dc6e84eb7ce2624f08af525c0
Christian Brabandt <cb@256bit.org>
parents:
7803
diff
changeset
|
246 hashtab_T *ht, |
|
bcef391c101c
commit https://github.com/vim/vim/commit/68c2f638e65d914dc6e84eb7ce2624f08af525c0
Christian Brabandt <cb@256bit.org>
parents:
7803
diff
changeset
|
247 hashitem_T *hi, |
|
bcef391c101c
commit https://github.com/vim/vim/commit/68c2f638e65d914dc6e84eb7ce2624f08af525c0
Christian Brabandt <cb@256bit.org>
parents:
7803
diff
changeset
|
248 char_u *key, |
|
bcef391c101c
commit https://github.com/vim/vim/commit/68c2f638e65d914dc6e84eb7ce2624f08af525c0
Christian Brabandt <cb@256bit.org>
parents:
7803
diff
changeset
|
249 hash_T hash) |
| 799 | 250 { |
|
18798
f0f9692d4487
patch 8.1.2387: using old C style comments
Bram Moolenaar <Bram@vim.org>
parents:
17508
diff
changeset
|
251 // If resizing failed before and it fails again we can't add an item. |
|
31533
a5959e14771a
patch 9.0.1099: trying to resize a hashtab may cause a problem
Bram Moolenaar <Bram@vim.org>
parents:
31529
diff
changeset
|
252 if (ht->ht_flags & HTFLAGS_ERROR) |
| 799 | 253 return FAIL; |
| 254 | |
| 255 ++ht->ht_used; | |
|
21317
883aa425656a
patch 8.2.1209: Vim9: test failure
Bram Moolenaar <Bram@vim.org>
parents:
20007
diff
changeset
|
256 ++ht->ht_changed; |
| 799 | 257 if (hi->hi_key == NULL) |
| 258 ++ht->ht_filled; | |
| 259 hi->hi_key = key; | |
| 260 hi->hi_hash = hash; | |
| 261 | |
|
18798
f0f9692d4487
patch 8.1.2387: using old C style comments
Bram Moolenaar <Bram@vim.org>
parents:
17508
diff
changeset
|
262 // When the space gets low may resize the array. |
| 799 | 263 return hash_may_resize(ht, 0); |
| 264 } | |
| 265 | |
|
18798
f0f9692d4487
patch 8.1.2387: using old C style comments
Bram Moolenaar <Bram@vim.org>
parents:
17508
diff
changeset
|
266 #if 0 // not used |
| 799 | 267 /* |
| 268 * Overwrite hashtable item "hi" with "key". "hi" must point to the item that | |
| 269 * is to be overwritten. Thus the number of items in the hashtable doesn't | |
| 270 * change. | |
| 271 * Although the key must be identical, the pointer may be different, thus it's | |
| 272 * set anyway (the key is part of an item with that key). | |
| 273 * The caller must take care of freeing the old item. | |
| 274 * "hi" is invalid after this! | |
| 275 */ | |
| 276 void | |
|
7823
bcef391c101c
commit https://github.com/vim/vim/commit/68c2f638e65d914dc6e84eb7ce2624f08af525c0
Christian Brabandt <cb@256bit.org>
parents:
7803
diff
changeset
|
277 hash_set(hashitem_T *hi, char_u *key) |
| 799 | 278 { |
| 279 hi->hi_key = key; | |
| 280 } | |
| 281 #endif | |
| 282 | |
| 283 /* | |
| 284 * Remove item "hi" from hashtable "ht". "hi" must have been obtained with | |
| 285 * hash_lookup(). | |
|
31231
684e6dfa2fba
patch 9.0.0949: crash when unletting a variable while listing variables
Bram Moolenaar <Bram@vim.org>
parents:
27521
diff
changeset
|
286 * "command" is used for the error message when the hashtab if frozen. |
| 799 | 287 * The caller must take care of freeing the item itself. |
| 288 */ | |
|
31231
684e6dfa2fba
patch 9.0.0949: crash when unletting a variable while listing variables
Bram Moolenaar <Bram@vim.org>
parents:
27521
diff
changeset
|
289 int |
|
684e6dfa2fba
patch 9.0.0949: crash when unletting a variable while listing variables
Bram Moolenaar <Bram@vim.org>
parents:
27521
diff
changeset
|
290 hash_remove(hashtab_T *ht, hashitem_T *hi, char *command) |
| 799 | 291 { |
|
31231
684e6dfa2fba
patch 9.0.0949: crash when unletting a variable while listing variables
Bram Moolenaar <Bram@vim.org>
parents:
27521
diff
changeset
|
292 if (check_hashtab_frozen(ht, command)) |
|
684e6dfa2fba
patch 9.0.0949: crash when unletting a variable while listing variables
Bram Moolenaar <Bram@vim.org>
parents:
27521
diff
changeset
|
293 return FAIL; |
| 799 | 294 --ht->ht_used; |
|
21317
883aa425656a
patch 8.2.1209: Vim9: test failure
Bram Moolenaar <Bram@vim.org>
parents:
20007
diff
changeset
|
295 ++ht->ht_changed; |
| 799 | 296 hi->hi_key = HI_KEY_REMOVED; |
| 297 hash_may_resize(ht, 0); | |
|
31231
684e6dfa2fba
patch 9.0.0949: crash when unletting a variable while listing variables
Bram Moolenaar <Bram@vim.org>
parents:
27521
diff
changeset
|
298 return OK; |
| 799 | 299 } |
| 300 | |
| 301 /* | |
| 302 * Lock a hashtable: prevent that ht_array changes. | |
| 303 * Don't use this when items are to be added! | |
| 304 * Must call hash_unlock() later. | |
| 305 */ | |
| 306 void | |
|
7823
bcef391c101c
commit https://github.com/vim/vim/commit/68c2f638e65d914dc6e84eb7ce2624f08af525c0
Christian Brabandt <cb@256bit.org>
parents:
7803
diff
changeset
|
307 hash_lock(hashtab_T *ht) |
| 799 | 308 { |
| 309 ++ht->ht_locked; | |
| 310 } | |
| 311 | |
|
27018
268f6a3511df
patch 8.2.4038: various code not used when features are disabled
Bram Moolenaar <Bram@vim.org>
parents:
22226
diff
changeset
|
312 #if defined(FEAT_PROP_POPUP) || defined(PROTO) |
| 799 | 313 /* |
| 314 * Lock a hashtable at the specified number of entries. | |
| 315 * Caller must make sure no more than "size" entries will be added. | |
| 316 * Must call hash_unlock() later. | |
| 317 */ | |
| 318 void | |
|
7823
bcef391c101c
commit https://github.com/vim/vim/commit/68c2f638e65d914dc6e84eb7ce2624f08af525c0
Christian Brabandt <cb@256bit.org>
parents:
7803
diff
changeset
|
319 hash_lock_size(hashtab_T *ht, int size) |
| 799 | 320 { |
| 321 (void)hash_may_resize(ht, size); | |
| 322 ++ht->ht_locked; | |
| 323 } | |
|
27018
268f6a3511df
patch 8.2.4038: various code not used when features are disabled
Bram Moolenaar <Bram@vim.org>
parents:
22226
diff
changeset
|
324 #endif |
| 799 | 325 |
| 326 /* | |
| 327 * Unlock a hashtable: allow ht_array changes again. | |
| 328 * Table will be resized (shrink) when necessary. | |
| 329 * This must balance a call to hash_lock(). | |
| 330 */ | |
| 331 void | |
|
7823
bcef391c101c
commit https://github.com/vim/vim/commit/68c2f638e65d914dc6e84eb7ce2624f08af525c0
Christian Brabandt <cb@256bit.org>
parents:
7803
diff
changeset
|
332 hash_unlock(hashtab_T *ht) |
| 799 | 333 { |
| 334 --ht->ht_locked; | |
| 335 (void)hash_may_resize(ht, 0); | |
| 336 } | |
| 337 | |
| 338 /* | |
| 339 * Shrink a hashtable when there is too much empty space. | |
| 340 * Grow a hashtable when there is not enough empty space. | |
| 341 * Returns OK or FAIL (out of memory). | |
| 342 */ | |
| 343 static int | |
|
7823
bcef391c101c
commit https://github.com/vim/vim/commit/68c2f638e65d914dc6e84eb7ce2624f08af525c0
Christian Brabandt <cb@256bit.org>
parents:
7803
diff
changeset
|
344 hash_may_resize( |
|
bcef391c101c
commit https://github.com/vim/vim/commit/68c2f638e65d914dc6e84eb7ce2624f08af525c0
Christian Brabandt <cb@256bit.org>
parents:
7803
diff
changeset
|
345 hashtab_T *ht, |
|
18798
f0f9692d4487
patch 8.1.2387: using old C style comments
Bram Moolenaar <Bram@vim.org>
parents:
17508
diff
changeset
|
346 int minitems) // minimal number of items |
| 799 | 347 { |
| 348 hashitem_T temparray[HT_INIT_SIZE]; | |
| 349 hashitem_T *oldarray, *newarray; | |
| 350 hashitem_T *olditem, *newitem; | |
| 3970 | 351 unsigned newi; |
| 799 | 352 int todo; |
|
31535
8b9771b827c1
patch 9.0.1100: a hashtab with many removed items is not cleaned up
Bram Moolenaar <Bram@vim.org>
parents:
31533
diff
changeset
|
353 long_u newsize; |
| 799 | 354 long_u minsize; |
| 355 long_u newmask; | |
| 356 hash_T perturb; | |
| 357 | |
|
18798
f0f9692d4487
patch 8.1.2387: using old C style comments
Bram Moolenaar <Bram@vim.org>
parents:
17508
diff
changeset
|
358 // Don't resize a locked table. |
| 799 | 359 if (ht->ht_locked > 0) |
| 360 return OK; | |
| 361 | |
| 362 #ifdef HT_DEBUG | |
| 363 if (ht->ht_used > ht->ht_filled) | |
|
15470
55ccc2d353bd
patch 8.1.0743: giving error messages is not flexible
Bram Moolenaar <Bram@vim.org>
parents:
10605
diff
changeset
|
364 emsg("hash_may_resize(): more used than filled"); |
| 799 | 365 if (ht->ht_filled >= ht->ht_mask + 1) |
|
15470
55ccc2d353bd
patch 8.1.0743: giving error messages is not flexible
Bram Moolenaar <Bram@vim.org>
parents:
10605
diff
changeset
|
366 emsg("hash_may_resize(): table completely filled"); |
| 799 | 367 #endif |
| 368 | |
|
31535
8b9771b827c1
patch 9.0.1100: a hashtab with many removed items is not cleaned up
Bram Moolenaar <Bram@vim.org>
parents:
31533
diff
changeset
|
369 long_u oldsize = ht->ht_mask + 1; |
| 799 | 370 if (minitems == 0) |
| 371 { | |
|
18798
f0f9692d4487
patch 8.1.2387: using old C style comments
Bram Moolenaar <Bram@vim.org>
parents:
17508
diff
changeset
|
372 // Return quickly for small tables with at least two NULL items. NULL |
|
f0f9692d4487
patch 8.1.2387: using old C style comments
Bram Moolenaar <Bram@vim.org>
parents:
17508
diff
changeset
|
373 // items are required for the lookup to decide a key isn't there. |
| 799 | 374 if (ht->ht_filled < HT_INIT_SIZE - 1 |
| 375 && ht->ht_array == ht->ht_smallarray) | |
| 376 return OK; | |
| 377 | |
| 378 /* | |
| 379 * Grow or refill the array when it's more than 2/3 full (including | |
| 380 * removed items, so that they get cleaned up). | |
| 381 * Shrink the array when it's less than 1/5 full. When growing it is | |
| 382 * at least 1/4 full (avoids repeated grow-shrink operations) | |
| 383 */ | |
| 384 if (ht->ht_filled * 3 < oldsize * 2 && ht->ht_used > oldsize / 5) | |
| 385 return OK; | |
| 386 | |
| 387 if (ht->ht_used > 1000) | |
|
18798
f0f9692d4487
patch 8.1.2387: using old C style comments
Bram Moolenaar <Bram@vim.org>
parents:
17508
diff
changeset
|
388 minsize = ht->ht_used * 2; // it's big, don't make too much room |
| 799 | 389 else |
|
18798
f0f9692d4487
patch 8.1.2387: using old C style comments
Bram Moolenaar <Bram@vim.org>
parents:
17508
diff
changeset
|
390 minsize = ht->ht_used * 4; // make plenty of room |
| 799 | 391 } |
| 392 else | |
| 393 { | |
|
17508
34966be2e856
patch 8.1.1752: resizing hashtable is inefficient
Bram Moolenaar <Bram@vim.org>
parents:
16825
diff
changeset
|
394 // Use specified size. |
|
34966be2e856
patch 8.1.1752: resizing hashtable is inefficient
Bram Moolenaar <Bram@vim.org>
parents:
16825
diff
changeset
|
395 if ((long_u)minitems < ht->ht_used) // just in case... |
| 835 | 396 minitems = (int)ht->ht_used; |
|
17508
34966be2e856
patch 8.1.1752: resizing hashtable is inefficient
Bram Moolenaar <Bram@vim.org>
parents:
16825
diff
changeset
|
397 minsize = (minitems * 3 + 1) / 2; // array is up to 2/3 full |
| 799 | 398 } |
| 399 | |
| 400 newsize = HT_INIT_SIZE; | |
| 401 while (newsize < minsize) | |
| 402 { | |
|
18798
f0f9692d4487
patch 8.1.2387: using old C style comments
Bram Moolenaar <Bram@vim.org>
parents:
17508
diff
changeset
|
403 newsize <<= 1; // make sure it's always a power of 2 |
| 799 | 404 if (newsize == 0) |
|
18798
f0f9692d4487
patch 8.1.2387: using old C style comments
Bram Moolenaar <Bram@vim.org>
parents:
17508
diff
changeset
|
405 return FAIL; // overflow |
| 799 | 406 } |
| 407 | |
| 408 if (newsize == HT_INIT_SIZE) | |
| 409 { | |
|
18798
f0f9692d4487
patch 8.1.2387: using old C style comments
Bram Moolenaar <Bram@vim.org>
parents:
17508
diff
changeset
|
410 // Use the small array inside the hashdict structure. |
| 799 | 411 newarray = ht->ht_smallarray; |
| 412 if (ht->ht_array == newarray) | |
| 413 { | |
|
18798
f0f9692d4487
patch 8.1.2387: using old C style comments
Bram Moolenaar <Bram@vim.org>
parents:
17508
diff
changeset
|
414 // Moving from ht_smallarray to ht_smallarray! Happens when there |
|
f0f9692d4487
patch 8.1.2387: using old C style comments
Bram Moolenaar <Bram@vim.org>
parents:
17508
diff
changeset
|
415 // are many removed items. Copy the items to be able to clean up |
|
f0f9692d4487
patch 8.1.2387: using old C style comments
Bram Moolenaar <Bram@vim.org>
parents:
17508
diff
changeset
|
416 // removed items. |
| 799 | 417 mch_memmove(temparray, newarray, sizeof(temparray)); |
| 418 oldarray = temparray; | |
| 419 } | |
| 420 else | |
| 421 oldarray = ht->ht_array; | |
|
20007
aadd1cae2ff5
patch 8.2.0559: clearing a struct is verbose
Bram Moolenaar <Bram@vim.org>
parents:
18798
diff
changeset
|
422 CLEAR_FIELD(ht->ht_smallarray); |
| 799 | 423 } |
|
31529
52c9b288ce86
patch 9.0.1097: tests are failing
Bram Moolenaar <Bram@vim.org>
parents:
31527
diff
changeset
|
424 |
|
31535
8b9771b827c1
patch 9.0.1100: a hashtab with many removed items is not cleaned up
Bram Moolenaar <Bram@vim.org>
parents:
31533
diff
changeset
|
425 else if (newsize == oldsize && ht->ht_filled * 3 < oldsize * 2) |
|
31529
52c9b288ce86
patch 9.0.1097: tests are failing
Bram Moolenaar <Bram@vim.org>
parents:
31527
diff
changeset
|
426 { |
|
31535
8b9771b827c1
patch 9.0.1100: a hashtab with many removed items is not cleaned up
Bram Moolenaar <Bram@vim.org>
parents:
31533
diff
changeset
|
427 // The hashtab is already at the desired size, and there are not too |
|
8b9771b827c1
patch 9.0.1100: a hashtab with many removed items is not cleaned up
Bram Moolenaar <Bram@vim.org>
parents:
31533
diff
changeset
|
428 // many removed items, bail out. |
|
31529
52c9b288ce86
patch 9.0.1097: tests are failing
Bram Moolenaar <Bram@vim.org>
parents:
31527
diff
changeset
|
429 return OK; |
|
52c9b288ce86
patch 9.0.1097: tests are failing
Bram Moolenaar <Bram@vim.org>
parents:
31527
diff
changeset
|
430 } |
|
52c9b288ce86
patch 9.0.1097: tests are failing
Bram Moolenaar <Bram@vim.org>
parents:
31527
diff
changeset
|
431 |
| 799 | 432 else |
| 433 { | |
|
18798
f0f9692d4487
patch 8.1.2387: using old C style comments
Bram Moolenaar <Bram@vim.org>
parents:
17508
diff
changeset
|
434 // Allocate an array. |
|
20007
aadd1cae2ff5
patch 8.2.0559: clearing a struct is verbose
Bram Moolenaar <Bram@vim.org>
parents:
18798
diff
changeset
|
435 newarray = ALLOC_CLEAR_MULT(hashitem_T, newsize); |
| 799 | 436 if (newarray == NULL) |
| 437 { | |
|
18798
f0f9692d4487
patch 8.1.2387: using old C style comments
Bram Moolenaar <Bram@vim.org>
parents:
17508
diff
changeset
|
438 // Out of memory. When there are NULL items still return OK. |
|
31231
684e6dfa2fba
patch 9.0.0949: crash when unletting a variable while listing variables
Bram Moolenaar <Bram@vim.org>
parents:
27521
diff
changeset
|
439 // Otherwise set ht_flags to HTFLAGS_ERROR, because lookup may |
|
684e6dfa2fba
patch 9.0.0949: crash when unletting a variable while listing variables
Bram Moolenaar <Bram@vim.org>
parents:
27521
diff
changeset
|
440 // result in a hang if we add another item. |
| 799 | 441 if (ht->ht_filled < ht->ht_mask) |
| 442 return OK; | |
|
31231
684e6dfa2fba
patch 9.0.0949: crash when unletting a variable while listing variables
Bram Moolenaar <Bram@vim.org>
parents:
27521
diff
changeset
|
443 ht->ht_flags |= HTFLAGS_ERROR; |
| 799 | 444 return FAIL; |
| 445 } | |
| 446 oldarray = ht->ht_array; | |
| 447 } | |
| 448 | |
| 449 /* | |
| 450 * Move all the items from the old array to the new one, placing them in | |
| 451 * the right spot. The new array won't have any removed items, thus this | |
| 452 * is also a cleanup action. | |
| 453 */ | |
| 454 newmask = newsize - 1; | |
| 835 | 455 todo = (int)ht->ht_used; |
| 799 | 456 for (olditem = oldarray; todo > 0; ++olditem) |
| 457 if (!HASHITEM_EMPTY(olditem)) | |
| 458 { | |
| 459 /* | |
| 460 * The algorithm to find the spot to add the item is identical to | |
| 461 * the algorithm to find an item in hash_lookup(). But we only | |
| 462 * need to search for a NULL key, thus it's simpler. | |
| 463 */ | |
| 3970 | 464 newi = (unsigned)(olditem->hi_hash & newmask); |
| 799 | 465 newitem = &newarray[newi]; |
| 466 | |
| 467 if (newitem->hi_key != NULL) | |
| 468 for (perturb = olditem->hi_hash; ; perturb >>= PERTURB_SHIFT) | |
| 469 { | |
| 3970 | 470 newi = (unsigned)((newi << 2U) + newi + perturb + 1U); |
| 799 | 471 newitem = &newarray[newi & newmask]; |
| 472 if (newitem->hi_key == NULL) | |
| 473 break; | |
| 474 } | |
| 475 *newitem = *olditem; | |
| 476 --todo; | |
| 477 } | |
| 478 | |
| 479 if (ht->ht_array != ht->ht_smallarray) | |
| 480 vim_free(ht->ht_array); | |
| 481 ht->ht_array = newarray; | |
| 482 ht->ht_mask = newmask; | |
| 483 ht->ht_filled = ht->ht_used; | |
|
21317
883aa425656a
patch 8.2.1209: Vim9: test failure
Bram Moolenaar <Bram@vim.org>
parents:
20007
diff
changeset
|
484 ++ht->ht_changed; |
|
31231
684e6dfa2fba
patch 9.0.0949: crash when unletting a variable while listing variables
Bram Moolenaar <Bram@vim.org>
parents:
27521
diff
changeset
|
485 ht->ht_flags &= ~HTFLAGS_ERROR; |
| 799 | 486 |
| 487 return OK; | |
| 488 } | |
| 489 | |
| 490 /* | |
| 491 * Get the hash number for a key. | |
| 492 * If you think you know a better hash function: Compile with HT_DEBUG set and | |
| 493 * run a script that uses hashtables a lot. Vim will then print statistics | |
| 494 * when exiting. Try that with the current hash algorithm and yours. The | |
| 495 * lower the percentage the better. | |
| 496 */ | |
| 497 hash_T | |
|
7823
bcef391c101c
commit https://github.com/vim/vim/commit/68c2f638e65d914dc6e84eb7ce2624f08af525c0
Christian Brabandt <cb@256bit.org>
parents:
7803
diff
changeset
|
498 hash_hash(char_u *key) |
| 799 | 499 { |
| 500 hash_T hash; | |
| 501 char_u *p; | |
| 502 | |
| 503 if ((hash = *key) == 0) | |
|
8839
9fa567d13551
commit https://github.com/vim/vim/commit/0921ecff1c5a74541bad6c073e8ade32247403d8
Christian Brabandt <cb@256bit.org>
parents:
7823
diff
changeset
|
504 return (hash_T)0; |
| 799 | 505 p = key + 1; |
| 506 | |
|
18798
f0f9692d4487
patch 8.1.2387: using old C style comments
Bram Moolenaar <Bram@vim.org>
parents:
17508
diff
changeset
|
507 // A simplistic algorithm that appears to do very well. |
|
f0f9692d4487
patch 8.1.2387: using old C style comments
Bram Moolenaar <Bram@vim.org>
parents:
17508
diff
changeset
|
508 // Suggested by George Reilly. |
| 799 | 509 while (*p != NUL) |
| 510 hash = hash * 101 + *p++; | |
| 511 | |
| 512 return hash; | |
| 513 } |