annotate src/hashtab.c @ 33821:6c92d6f3a255 v9.0.2126

patch 9.0.2126: unused assignments when checking 'listchars' Commit: https://github.com/vim/vim/commit/00624a2fa08d04bdded240d474e9cfdc193dbe10 Author: zeertzjq <zeertzjq@outlook.com> Date: Thu Nov 23 20:47:16 2023 +0100 patch 9.0.2126: unused assignments when checking 'listchars' Problem: Unused assignments when checking the value of 'listchars'. Solution: Loop only once when just checking the value. Add a test to check that this change doesn't cause double-free. closes: #13559 Signed-off-by: zeertzjq <zeertzjq@outlook.com> Signed-off-by: Christian Brabandt <cb@256bit.org>
author Christian Brabandt <cb@256bit.org>
date Thu, 23 Nov 2023 21:00:04 +0100
parents 04d9dff67d99
children
Ignore whitespace changes - Everywhere: Within whitespace: At end of lines:
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
6beb2c667935 updated for version 7.0b
vimboss
parents:
diff changeset
2 *
6beb2c667935 updated for version 7.0b
vimboss
parents:
diff changeset
3 * VIM - Vi IMproved by Bram Moolenaar
6beb2c667935 updated for version 7.0b
vimboss
parents:
diff changeset
4 *
6beb2c667935 updated for version 7.0b
vimboss
parents:
diff changeset
5 * Do ":help uganda" in Vim to read copying and usage conditions.
6beb2c667935 updated for version 7.0b
vimboss
parents:
diff changeset
6 * Do ":help credits" in Vim to see a list of people who contributed.
6beb2c667935 updated for version 7.0b
vimboss
parents:
diff changeset
7 * See README.txt for an overview of the Vim source code.
6beb2c667935 updated for version 7.0b
vimboss
parents:
diff changeset
8 */
6beb2c667935 updated for version 7.0b
vimboss
parents:
diff changeset
9
6beb2c667935 updated for version 7.0b
vimboss
parents:
diff changeset
10 /*
6beb2c667935 updated for version 7.0b
vimboss
parents:
diff changeset
11 * hashtab.c: Handling of a hashtable with Vim-specific properties.
6beb2c667935 updated for version 7.0b
vimboss
parents:
diff changeset
12 *
6beb2c667935 updated for version 7.0b
vimboss
parents:
diff changeset
13 * Each item in a hashtable has a NUL terminated string key. A key can appear
6beb2c667935 updated for version 7.0b
vimboss
parents:
diff changeset
14 * only once in the table.
6beb2c667935 updated for version 7.0b
vimboss
parents:
diff changeset
15 *
6beb2c667935 updated for version 7.0b
vimboss
parents:
diff changeset
16 * A hash number is computed from the key for quick lookup. When the hashes
6beb2c667935 updated for version 7.0b
vimboss
parents:
diff changeset
17 * of two different keys point to the same entry an algorithm is used to
6beb2c667935 updated for version 7.0b
vimboss
parents:
diff changeset
18 * iterate over other entries in the table until the right one is found.
6beb2c667935 updated for version 7.0b
vimboss
parents:
diff changeset
19 * To make the iteration work removed keys are different from entries where a
6beb2c667935 updated for version 7.0b
vimboss
parents:
diff changeset
20 * key was never present.
6beb2c667935 updated for version 7.0b
vimboss
parents:
diff changeset
21 *
6beb2c667935 updated for version 7.0b
vimboss
parents:
diff changeset
22 * The mechanism has been partly based on how Python Dictionaries are
6beb2c667935 updated for version 7.0b
vimboss
parents:
diff changeset
23 * implemented. The algorithm is from Knuth Vol. 3, Sec. 6.4.
6beb2c667935 updated for version 7.0b
vimboss
parents:
diff changeset
24 *
6beb2c667935 updated for version 7.0b
vimboss
parents:
diff changeset
25 * The hashtable grows to accommodate more entries when needed. At least 1/3
6beb2c667935 updated for version 7.0b
vimboss
parents:
diff changeset
26 * of the entries is empty to keep the lookup efficient (at the cost of extra
6beb2c667935 updated for version 7.0b
vimboss
parents:
diff changeset
27 * memory).
6beb2c667935 updated for version 7.0b
vimboss
parents:
diff changeset
28 */
6beb2c667935 updated for version 7.0b
vimboss
parents:
diff changeset
29
6beb2c667935 updated for version 7.0b
vimboss
parents:
diff changeset
30 #include "vim.h"
6beb2c667935 updated for version 7.0b
vimboss
parents:
diff changeset
31
6beb2c667935 updated for version 7.0b
vimboss
parents:
diff changeset
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
6beb2c667935 updated for version 7.0b
vimboss
parents:
diff changeset
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
6beb2c667935 updated for version 7.0b
vimboss
parents:
diff changeset
37 #endif
6beb2c667935 updated for version 7.0b
vimboss
parents:
diff changeset
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
6beb2c667935 updated for version 7.0b
vimboss
parents:
diff changeset
40 #define PERTURB_SHIFT 5
6beb2c667935 updated for version 7.0b
vimboss
parents:
diff changeset
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
6beb2c667935 updated for version 7.0b
vimboss
parents:
diff changeset
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
6beb2c667935 updated for version 7.0b
vimboss
parents:
diff changeset
45 /*
6beb2c667935 updated for version 7.0b
vimboss
parents:
diff changeset
46 * Create an empty hash table.
6beb2c667935 updated for version 7.0b
vimboss
parents:
diff changeset
47 * Returns NULL when out of memory.
6beb2c667935 updated for version 7.0b
vimboss
parents:
diff changeset
48 */
6beb2c667935 updated for version 7.0b
vimboss
parents:
diff changeset
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
6beb2c667935 updated for version 7.0b
vimboss
parents:
diff changeset
51 {
6beb2c667935 updated for version 7.0b
vimboss
parents:
diff changeset
52 hashtab_T *ht;
6beb2c667935 updated for version 7.0b
vimboss
parents:
diff changeset
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
6beb2c667935 updated for version 7.0b
vimboss
parents:
diff changeset
55 if (ht != NULL)
6beb2c667935 updated for version 7.0b
vimboss
parents:
diff changeset
56 hash_init(ht);
6beb2c667935 updated for version 7.0b
vimboss
parents:
diff changeset
57 return ht;
6beb2c667935 updated for version 7.0b
vimboss
parents:
diff changeset
58 }
6beb2c667935 updated for version 7.0b
vimboss
parents:
diff changeset
59 #endif
6beb2c667935 updated for version 7.0b
vimboss
parents:
diff changeset
60
6beb2c667935 updated for version 7.0b
vimboss
parents:
diff changeset
61 /*
6beb2c667935 updated for version 7.0b
vimboss
parents:
diff changeset
62 * Initialize an empty hash table.
6beb2c667935 updated for version 7.0b
vimboss
parents:
diff changeset
63 */
6beb2c667935 updated for version 7.0b
vimboss
parents:
diff changeset
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
6beb2c667935 updated for version 7.0b
vimboss
parents:
diff changeset
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
6beb2c667935 updated for version 7.0b
vimboss
parents:
diff changeset
69 ht->ht_array = ht->ht_smallarray;
6beb2c667935 updated for version 7.0b
vimboss
parents:
diff changeset
70 ht->ht_mask = HT_INIT_SIZE - 1;
6beb2c667935 updated for version 7.0b
vimboss
parents:
diff changeset
71 }
6beb2c667935 updated for version 7.0b
vimboss
parents:
diff changeset
72
6beb2c667935 updated for version 7.0b
vimboss
parents:
diff changeset
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
6beb2c667935 updated for version 7.0b
vimboss
parents:
diff changeset
88 * Free the array of a hash table. Does not free the items it contains!
6beb2c667935 updated for version 7.0b
vimboss
parents:
diff changeset
89 * If "ht" is not freed then you should call hash_init() next!
6beb2c667935 updated for version 7.0b
vimboss
parents:
diff changeset
90 */
6beb2c667935 updated for version 7.0b
vimboss
parents:
diff changeset
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
6beb2c667935 updated for version 7.0b
vimboss
parents:
diff changeset
93 {
6beb2c667935 updated for version 7.0b
vimboss
parents:
diff changeset
94 if (ht->ht_array != ht->ht_smallarray)
6beb2c667935 updated for version 7.0b
vimboss
parents:
diff changeset
95 vim_free(ht->ht_array);
6beb2c667935 updated for version 7.0b
vimboss
parents:
diff changeset
96 }
6beb2c667935 updated for version 7.0b
vimboss
parents:
diff changeset
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
6beb2c667935 updated for version 7.0b
vimboss
parents:
diff changeset
99 /*
6beb2c667935 updated for version 7.0b
vimboss
parents:
diff changeset
100 * Free the array of a hash table and all the keys it contains. The keys must
6beb2c667935 updated for version 7.0b
vimboss
parents:
diff changeset
101 * have been allocated. "off" is the offset from the start of the allocate
6beb2c667935 updated for version 7.0b
vimboss
parents:
diff changeset
102 * memory to the location of the key (it's always positive).
6beb2c667935 updated for version 7.0b
vimboss
parents:
diff changeset
103 */
6beb2c667935 updated for version 7.0b
vimboss
parents:
diff changeset
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
6beb2c667935 updated for version 7.0b
vimboss
parents:
diff changeset
106 {
835
8bebcabccc2c updated for version 7.0e01
vimboss
parents: 799
diff changeset
107 long todo;
799
6beb2c667935 updated for version 7.0b
vimboss
parents:
diff changeset
108 hashitem_T *hi;
6beb2c667935 updated for version 7.0b
vimboss
parents:
diff changeset
109
835
8bebcabccc2c updated for version 7.0e01
vimboss
parents: 799
diff changeset
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
6beb2c667935 updated for version 7.0b
vimboss
parents:
diff changeset
112 {
6beb2c667935 updated for version 7.0b
vimboss
parents:
diff changeset
113 if (!HASHITEM_EMPTY(hi))
6beb2c667935 updated for version 7.0b
vimboss
parents:
diff changeset
114 {
6beb2c667935 updated for version 7.0b
vimboss
parents:
diff changeset
115 vim_free(hi->hi_key - off);
6beb2c667935 updated for version 7.0b
vimboss
parents:
diff changeset
116 --todo;
6beb2c667935 updated for version 7.0b
vimboss
parents:
diff changeset
117 }
6beb2c667935 updated for version 7.0b
vimboss
parents:
diff changeset
118 }
6beb2c667935 updated for version 7.0b
vimboss
parents:
diff changeset
119 hash_clear(ht);
6beb2c667935 updated for version 7.0b
vimboss
parents:
diff changeset
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
6beb2c667935 updated for version 7.0b
vimboss
parents:
diff changeset
122
6beb2c667935 updated for version 7.0b
vimboss
parents:
diff changeset
123 /*
6beb2c667935 updated for version 7.0b
vimboss
parents:
diff changeset
124 * Find "key" in hashtable "ht". "key" must not be NULL.
6beb2c667935 updated for version 7.0b
vimboss
parents:
diff changeset
125 * Always returns a pointer to a hashitem. If the item was not found then
6beb2c667935 updated for version 7.0b
vimboss
parents:
diff changeset
126 * HASHITEM_EMPTY() is TRUE. The pointer is then the place where the key
6beb2c667935 updated for version 7.0b
vimboss
parents:
diff changeset
127 * would be added.
6beb2c667935 updated for version 7.0b
vimboss
parents:
diff changeset
128 * WARNING: The returned pointer becomes invalid when the hashtable is changed
6beb2c667935 updated for version 7.0b
vimboss
parents:
diff changeset
129 * (adding, setting or removing an item)!
6beb2c667935 updated for version 7.0b
vimboss
parents:
diff changeset
130 */
6beb2c667935 updated for version 7.0b
vimboss
parents:
diff changeset
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
6beb2c667935 updated for version 7.0b
vimboss
parents:
diff changeset
133 {
6beb2c667935 updated for version 7.0b
vimboss
parents:
diff changeset
134 return hash_lookup(ht, key, hash_hash(key));
6beb2c667935 updated for version 7.0b
vimboss
parents:
diff changeset
135 }
6beb2c667935 updated for version 7.0b
vimboss
parents:
diff changeset
136
6beb2c667935 updated for version 7.0b
vimboss
parents:
diff changeset
137 /*
6beb2c667935 updated for version 7.0b
vimboss
parents:
diff changeset
138 * Like hash_find(), but caller computes "hash".
6beb2c667935 updated for version 7.0b
vimboss
parents:
diff changeset
139 */
6beb2c667935 updated for version 7.0b
vimboss
parents:
diff changeset
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
6beb2c667935 updated for version 7.0b
vimboss
parents:
diff changeset
142 {
6beb2c667935 updated for version 7.0b
vimboss
parents:
diff changeset
143 hash_T perturb;
6beb2c667935 updated for version 7.0b
vimboss
parents:
diff changeset
144 hashitem_T *freeitem;
6beb2c667935 updated for version 7.0b
vimboss
parents:
diff changeset
145 hashitem_T *hi;
3970
2c12cd5c1381 updated for version 7.3.740
Bram Moolenaar <bram@vim.org>
parents: 2520
diff changeset
146 unsigned idx;
799
6beb2c667935 updated for version 7.0b
vimboss
parents:
diff changeset
147
6beb2c667935 updated for version 7.0b
vimboss
parents:
diff changeset
148 #ifdef HT_DEBUG
6beb2c667935 updated for version 7.0b
vimboss
parents:
diff changeset
149 ++hash_count_lookup;
6beb2c667935 updated for version 7.0b
vimboss
parents:
diff changeset
150 #endif
6beb2c667935 updated for version 7.0b
vimboss
parents:
diff changeset
151
6beb2c667935 updated for version 7.0b
vimboss
parents:
diff changeset
152 /*
6beb2c667935 updated for version 7.0b
vimboss
parents:
diff changeset
153 * Quickly handle the most common situations:
6beb2c667935 updated for version 7.0b
vimboss
parents:
diff changeset
154 * - return if there is no item at all
6beb2c667935 updated for version 7.0b
vimboss
parents:
diff changeset
155 * - skip over a removed item
6beb2c667935 updated for version 7.0b
vimboss
parents:
diff changeset
156 * - return if the item matches
6beb2c667935 updated for version 7.0b
vimboss
parents:
diff changeset
157 */
3970
2c12cd5c1381 updated for version 7.3.740
Bram Moolenaar <bram@vim.org>
parents: 2520
diff changeset
158 idx = (unsigned)(hash & ht->ht_mask);
799
6beb2c667935 updated for version 7.0b
vimboss
parents:
diff changeset
159 hi = &ht->ht_array[idx];
6beb2c667935 updated for version 7.0b
vimboss
parents:
diff changeset
160
6beb2c667935 updated for version 7.0b
vimboss
parents:
diff changeset
161 if (hi->hi_key == NULL)
6beb2c667935 updated for version 7.0b
vimboss
parents:
diff changeset
162 return hi;
6beb2c667935 updated for version 7.0b
vimboss
parents:
diff changeset
163 if (hi->hi_key == HI_KEY_REMOVED)
6beb2c667935 updated for version 7.0b
vimboss
parents:
diff changeset
164 freeitem = hi;
6beb2c667935 updated for version 7.0b
vimboss
parents:
diff changeset
165 else if (hi->hi_hash == hash && STRCMP(hi->hi_key, key) == 0)
6beb2c667935 updated for version 7.0b
vimboss
parents:
diff changeset
166 return hi;
6beb2c667935 updated for version 7.0b
vimboss
parents:
diff changeset
167 else
6beb2c667935 updated for version 7.0b
vimboss
parents:
diff changeset
168 freeitem = NULL;
6beb2c667935 updated for version 7.0b
vimboss
parents:
diff changeset
169
6beb2c667935 updated for version 7.0b
vimboss
parents:
diff changeset
170 /*
6beb2c667935 updated for version 7.0b
vimboss
parents:
diff changeset
171 * Need to search through the table to find the key. The algorithm
6beb2c667935 updated for version 7.0b
vimboss
parents:
diff changeset
172 * to step through the table starts with large steps, gradually becoming
6beb2c667935 updated for version 7.0b
vimboss
parents:
diff changeset
173 * smaller down to (1/4 table size + 1). This means it goes through all
6beb2c667935 updated for version 7.0b
vimboss
parents:
diff changeset
174 * table entries in the end.
6beb2c667935 updated for version 7.0b
vimboss
parents:
diff changeset
175 * When we run into a NULL key it's clear that the key isn't there.
6beb2c667935 updated for version 7.0b
vimboss
parents:
diff changeset
176 * Return the first available slot found (can be a slot of a removed
6beb2c667935 updated for version 7.0b
vimboss
parents:
diff changeset
177 * item).
6beb2c667935 updated for version 7.0b
vimboss
parents:
diff changeset
178 */
6beb2c667935 updated for version 7.0b
vimboss
parents:
diff changeset
179 for (perturb = hash; ; perturb >>= PERTURB_SHIFT)
6beb2c667935 updated for version 7.0b
vimboss
parents:
diff changeset
180 {
6beb2c667935 updated for version 7.0b
vimboss
parents:
diff changeset
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
6beb2c667935 updated for version 7.0b
vimboss
parents:
diff changeset
183 #endif
3970
2c12cd5c1381 updated for version 7.3.740
Bram Moolenaar <bram@vim.org>
parents: 2520
diff changeset
184 idx = (unsigned)((idx << 2U) + idx + perturb + 1U);
799
6beb2c667935 updated for version 7.0b
vimboss
parents:
diff changeset
185 hi = &ht->ht_array[idx & ht->ht_mask];
6beb2c667935 updated for version 7.0b
vimboss
parents:
diff changeset
186 if (hi->hi_key == NULL)
6beb2c667935 updated for version 7.0b
vimboss
parents:
diff changeset
187 return freeitem == NULL ? hi : freeitem;
6beb2c667935 updated for version 7.0b
vimboss
parents:
diff changeset
188 if (hi->hi_hash == hash
6beb2c667935 updated for version 7.0b
vimboss
parents:
diff changeset
189 && hi->hi_key != HI_KEY_REMOVED
6beb2c667935 updated for version 7.0b
vimboss
parents:
diff changeset
190 && STRCMP(hi->hi_key, key) == 0)
6beb2c667935 updated for version 7.0b
vimboss
parents:
diff changeset
191 return hi;
6beb2c667935 updated for version 7.0b
vimboss
parents:
diff changeset
192 if (hi->hi_key == HI_KEY_REMOVED && freeitem == NULL)
6beb2c667935 updated for version 7.0b
vimboss
parents:
diff changeset
193 freeitem = hi;
6beb2c667935 updated for version 7.0b
vimboss
parents:
diff changeset
194 }
6beb2c667935 updated for version 7.0b
vimboss
parents:
diff changeset
195 }
6beb2c667935 updated for version 7.0b
vimboss
parents:
diff changeset
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
6beb2c667935 updated for version 7.0b
vimboss
parents:
diff changeset
198 /*
6beb2c667935 updated for version 7.0b
vimboss
parents:
diff changeset
199 * Print the efficiency of hashtable lookups.
6beb2c667935 updated for version 7.0b
vimboss
parents:
diff changeset
200 * Useful when trying different hash algorithms.
6beb2c667935 updated for version 7.0b
vimboss
parents:
diff changeset
201 * Called when exiting.
6beb2c667935 updated for version 7.0b
vimboss
parents:
diff changeset
202 */
6beb2c667935 updated for version 7.0b
vimboss
parents:
diff changeset
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
6beb2c667935 updated for version 7.0b
vimboss
parents:
diff changeset
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
6beb2c667935 updated for version 7.0b
vimboss
parents:
diff changeset
207 fprintf(stderr, "\r\n\r\n\r\n\r\n");
6beb2c667935 updated for version 7.0b
vimboss
parents:
diff changeset
208 fprintf(stderr, "Number of hashtable lookups: %ld\r\n", hash_count_lookup);
6beb2c667935 updated for version 7.0b
vimboss
parents:
diff changeset
209 fprintf(stderr, "Number of perturb loops: %ld\r\n", hash_count_perturb);
6beb2c667935 updated for version 7.0b
vimboss
parents:
diff changeset
210 fprintf(stderr, "Percentage of perturb loops: %ld%%\r\n",
6beb2c667935 updated for version 7.0b
vimboss
parents:
diff changeset
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
6beb2c667935 updated for version 7.0b
vimboss
parents:
diff changeset
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
6beb2c667935 updated for version 7.0b
vimboss
parents:
diff changeset
215
6beb2c667935 updated for version 7.0b
vimboss
parents:
diff changeset
216 /*
6beb2c667935 updated for version 7.0b
vimboss
parents:
diff changeset
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
6beb2c667935 updated for version 7.0b
vimboss
parents:
diff changeset
219 * Returns FAIL when out of memory or the key is already present.
6beb2c667935 updated for version 7.0b
vimboss
parents:
diff changeset
220 */
6beb2c667935 updated for version 7.0b
vimboss
parents:
diff changeset
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
6beb2c667935 updated for version 7.0b
vimboss
parents:
diff changeset
223 {
6beb2c667935 updated for version 7.0b
vimboss
parents:
diff changeset
224 hash_T hash = hash_hash(key);
6beb2c667935 updated for version 7.0b
vimboss
parents:
diff changeset
225 hashitem_T *hi;
6beb2c667935 updated for version 7.0b
vimboss
parents:
diff changeset
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
6beb2c667935 updated for version 7.0b
vimboss
parents:
diff changeset
229 hi = hash_lookup(ht, key, hash);
6beb2c667935 updated for version 7.0b
vimboss
parents:
diff changeset
230 if (!HASHITEM_EMPTY(hi))
6beb2c667935 updated for version 7.0b
vimboss
parents:
diff changeset
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
6beb2c667935 updated for version 7.0b
vimboss
parents:
diff changeset
233 return FAIL;
6beb2c667935 updated for version 7.0b
vimboss
parents:
diff changeset
234 }
6beb2c667935 updated for version 7.0b
vimboss
parents:
diff changeset
235 return hash_add_item(ht, hi, key, hash);
6beb2c667935 updated for version 7.0b
vimboss
parents:
diff changeset
236 }
6beb2c667935 updated for version 7.0b
vimboss
parents:
diff changeset
237
6beb2c667935 updated for version 7.0b
vimboss
parents:
diff changeset
238 /*
6beb2c667935 updated for version 7.0b
vimboss
parents:
diff changeset
239 * Add item "hi" with "key" to hashtable "ht". "key" must not be NULL and
6beb2c667935 updated for version 7.0b
vimboss
parents:
diff changeset
240 * "hi" must have been obtained with hash_lookup() and point to an empty item.
6beb2c667935 updated for version 7.0b
vimboss
parents:
diff changeset
241 * "hi" is invalid after this!
6beb2c667935 updated for version 7.0b
vimboss
parents:
diff changeset
242 * Returns OK or FAIL (out of memory).
6beb2c667935 updated for version 7.0b
vimboss
parents:
diff changeset
243 */
6beb2c667935 updated for version 7.0b
vimboss
parents:
diff changeset
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
6beb2c667935 updated for version 7.0b
vimboss
parents:
diff changeset
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
6beb2c667935 updated for version 7.0b
vimboss
parents:
diff changeset
253 return FAIL;
6beb2c667935 updated for version 7.0b
vimboss
parents:
diff changeset
254
6beb2c667935 updated for version 7.0b
vimboss
parents:
diff changeset
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
6beb2c667935 updated for version 7.0b
vimboss
parents:
diff changeset
257 if (hi->hi_key == NULL)
6beb2c667935 updated for version 7.0b
vimboss
parents:
diff changeset
258 ++ht->ht_filled;
6beb2c667935 updated for version 7.0b
vimboss
parents:
diff changeset
259 hi->hi_key = key;
6beb2c667935 updated for version 7.0b
vimboss
parents:
diff changeset
260 hi->hi_hash = hash;
6beb2c667935 updated for version 7.0b
vimboss
parents:
diff changeset
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
6beb2c667935 updated for version 7.0b
vimboss
parents:
diff changeset
263 return hash_may_resize(ht, 0);
6beb2c667935 updated for version 7.0b
vimboss
parents:
diff changeset
264 }
6beb2c667935 updated for version 7.0b
vimboss
parents:
diff changeset
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
6beb2c667935 updated for version 7.0b
vimboss
parents:
diff changeset
267 /*
6beb2c667935 updated for version 7.0b
vimboss
parents:
diff changeset
268 * Overwrite hashtable item "hi" with "key". "hi" must point to the item that
6beb2c667935 updated for version 7.0b
vimboss
parents:
diff changeset
269 * is to be overwritten. Thus the number of items in the hashtable doesn't
6beb2c667935 updated for version 7.0b
vimboss
parents:
diff changeset
270 * change.
6beb2c667935 updated for version 7.0b
vimboss
parents:
diff changeset
271 * Although the key must be identical, the pointer may be different, thus it's
6beb2c667935 updated for version 7.0b
vimboss
parents:
diff changeset
272 * set anyway (the key is part of an item with that key).
6beb2c667935 updated for version 7.0b
vimboss
parents:
diff changeset
273 * The caller must take care of freeing the old item.
6beb2c667935 updated for version 7.0b
vimboss
parents:
diff changeset
274 * "hi" is invalid after this!
6beb2c667935 updated for version 7.0b
vimboss
parents:
diff changeset
275 */
6beb2c667935 updated for version 7.0b
vimboss
parents:
diff changeset
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
6beb2c667935 updated for version 7.0b
vimboss
parents:
diff changeset
278 {
6beb2c667935 updated for version 7.0b
vimboss
parents:
diff changeset
279 hi->hi_key = key;
6beb2c667935 updated for version 7.0b
vimboss
parents:
diff changeset
280 }
6beb2c667935 updated for version 7.0b
vimboss
parents:
diff changeset
281 #endif
6beb2c667935 updated for version 7.0b
vimboss
parents:
diff changeset
282
6beb2c667935 updated for version 7.0b
vimboss
parents:
diff changeset
283 /*
6beb2c667935 updated for version 7.0b
vimboss
parents:
diff changeset
284 * Remove item "hi" from hashtable "ht". "hi" must have been obtained with
6beb2c667935 updated for version 7.0b
vimboss
parents:
diff changeset
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
6beb2c667935 updated for version 7.0b
vimboss
parents:
diff changeset
287 * The caller must take care of freeing the item itself.
6beb2c667935 updated for version 7.0b
vimboss
parents:
diff changeset
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
6beb2c667935 updated for version 7.0b
vimboss
parents:
diff changeset
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
6beb2c667935 updated for version 7.0b
vimboss
parents:
diff changeset
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
6beb2c667935 updated for version 7.0b
vimboss
parents:
diff changeset
296 hi->hi_key = HI_KEY_REMOVED;
6beb2c667935 updated for version 7.0b
vimboss
parents:
diff changeset
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
6beb2c667935 updated for version 7.0b
vimboss
parents:
diff changeset
299 }
6beb2c667935 updated for version 7.0b
vimboss
parents:
diff changeset
300
6beb2c667935 updated for version 7.0b
vimboss
parents:
diff changeset
301 /*
6beb2c667935 updated for version 7.0b
vimboss
parents:
diff changeset
302 * Lock a hashtable: prevent that ht_array changes.
6beb2c667935 updated for version 7.0b
vimboss
parents:
diff changeset
303 * Don't use this when items are to be added!
6beb2c667935 updated for version 7.0b
vimboss
parents:
diff changeset
304 * Must call hash_unlock() later.
6beb2c667935 updated for version 7.0b
vimboss
parents:
diff changeset
305 */
6beb2c667935 updated for version 7.0b
vimboss
parents:
diff changeset
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
6beb2c667935 updated for version 7.0b
vimboss
parents:
diff changeset
308 {
6beb2c667935 updated for version 7.0b
vimboss
parents:
diff changeset
309 ++ht->ht_locked;
6beb2c667935 updated for version 7.0b
vimboss
parents:
diff changeset
310 }
6beb2c667935 updated for version 7.0b
vimboss
parents:
diff changeset
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
6beb2c667935 updated for version 7.0b
vimboss
parents:
diff changeset
313 /*
6beb2c667935 updated for version 7.0b
vimboss
parents:
diff changeset
314 * Lock a hashtable at the specified number of entries.
6beb2c667935 updated for version 7.0b
vimboss
parents:
diff changeset
315 * Caller must make sure no more than "size" entries will be added.
6beb2c667935 updated for version 7.0b
vimboss
parents:
diff changeset
316 * Must call hash_unlock() later.
6beb2c667935 updated for version 7.0b
vimboss
parents:
diff changeset
317 */
6beb2c667935 updated for version 7.0b
vimboss
parents:
diff changeset
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
6beb2c667935 updated for version 7.0b
vimboss
parents:
diff changeset
320 {
6beb2c667935 updated for version 7.0b
vimboss
parents:
diff changeset
321 (void)hash_may_resize(ht, size);
6beb2c667935 updated for version 7.0b
vimboss
parents:
diff changeset
322 ++ht->ht_locked;
6beb2c667935 updated for version 7.0b
vimboss
parents:
diff changeset
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
6beb2c667935 updated for version 7.0b
vimboss
parents:
diff changeset
325
6beb2c667935 updated for version 7.0b
vimboss
parents:
diff changeset
326 /*
6beb2c667935 updated for version 7.0b
vimboss
parents:
diff changeset
327 * Unlock a hashtable: allow ht_array changes again.
6beb2c667935 updated for version 7.0b
vimboss
parents:
diff changeset
328 * Table will be resized (shrink) when necessary.
6beb2c667935 updated for version 7.0b
vimboss
parents:
diff changeset
329 * This must balance a call to hash_lock().
6beb2c667935 updated for version 7.0b
vimboss
parents:
diff changeset
330 */
6beb2c667935 updated for version 7.0b
vimboss
parents:
diff changeset
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
6beb2c667935 updated for version 7.0b
vimboss
parents:
diff changeset
333 {
6beb2c667935 updated for version 7.0b
vimboss
parents:
diff changeset
334 --ht->ht_locked;
6beb2c667935 updated for version 7.0b
vimboss
parents:
diff changeset
335 (void)hash_may_resize(ht, 0);
6beb2c667935 updated for version 7.0b
vimboss
parents:
diff changeset
336 }
6beb2c667935 updated for version 7.0b
vimboss
parents:
diff changeset
337
6beb2c667935 updated for version 7.0b
vimboss
parents:
diff changeset
338 /*
6beb2c667935 updated for version 7.0b
vimboss
parents:
diff changeset
339 * Shrink a hashtable when there is too much empty space.
6beb2c667935 updated for version 7.0b
vimboss
parents:
diff changeset
340 * Grow a hashtable when there is not enough empty space.
6beb2c667935 updated for version 7.0b
vimboss
parents:
diff changeset
341 * Returns OK or FAIL (out of memory).
6beb2c667935 updated for version 7.0b
vimboss
parents:
diff changeset
342 */
6beb2c667935 updated for version 7.0b
vimboss
parents:
diff changeset
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
6beb2c667935 updated for version 7.0b
vimboss
parents:
diff changeset
347 {
6beb2c667935 updated for version 7.0b
vimboss
parents:
diff changeset
348 hashitem_T temparray[HT_INIT_SIZE];
6beb2c667935 updated for version 7.0b
vimboss
parents:
diff changeset
349 hashitem_T *oldarray, *newarray;
6beb2c667935 updated for version 7.0b
vimboss
parents:
diff changeset
350 hashitem_T *olditem, *newitem;
3970
2c12cd5c1381 updated for version 7.3.740
Bram Moolenaar <bram@vim.org>
parents: 2520
diff changeset
351 unsigned newi;
799
6beb2c667935 updated for version 7.0b
vimboss
parents:
diff changeset
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
6beb2c667935 updated for version 7.0b
vimboss
parents:
diff changeset
354 long_u minsize;
6beb2c667935 updated for version 7.0b
vimboss
parents:
diff changeset
355 long_u newmask;
6beb2c667935 updated for version 7.0b
vimboss
parents:
diff changeset
356 hash_T perturb;
6beb2c667935 updated for version 7.0b
vimboss
parents:
diff changeset
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
6beb2c667935 updated for version 7.0b
vimboss
parents:
diff changeset
359 if (ht->ht_locked > 0)
6beb2c667935 updated for version 7.0b
vimboss
parents:
diff changeset
360 return OK;
6beb2c667935 updated for version 7.0b
vimboss
parents:
diff changeset
361
6beb2c667935 updated for version 7.0b
vimboss
parents:
diff changeset
362 #ifdef HT_DEBUG
6beb2c667935 updated for version 7.0b
vimboss
parents:
diff changeset
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
6beb2c667935 updated for version 7.0b
vimboss
parents:
diff changeset
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
6beb2c667935 updated for version 7.0b
vimboss
parents:
diff changeset
367 #endif
6beb2c667935 updated for version 7.0b
vimboss
parents:
diff changeset
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
6beb2c667935 updated for version 7.0b
vimboss
parents:
diff changeset
370 if (minitems == 0)
6beb2c667935 updated for version 7.0b
vimboss
parents:
diff changeset
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
6beb2c667935 updated for version 7.0b
vimboss
parents:
diff changeset
374 if (ht->ht_filled < HT_INIT_SIZE - 1
6beb2c667935 updated for version 7.0b
vimboss
parents:
diff changeset
375 && ht->ht_array == ht->ht_smallarray)
6beb2c667935 updated for version 7.0b
vimboss
parents:
diff changeset
376 return OK;
6beb2c667935 updated for version 7.0b
vimboss
parents:
diff changeset
377
6beb2c667935 updated for version 7.0b
vimboss
parents:
diff changeset
378 /*
6beb2c667935 updated for version 7.0b
vimboss
parents:
diff changeset
379 * Grow or refill the array when it's more than 2/3 full (including
6beb2c667935 updated for version 7.0b
vimboss
parents:
diff changeset
380 * removed items, so that they get cleaned up).
6beb2c667935 updated for version 7.0b
vimboss
parents:
diff changeset
381 * Shrink the array when it's less than 1/5 full. When growing it is
6beb2c667935 updated for version 7.0b
vimboss
parents:
diff changeset
382 * at least 1/4 full (avoids repeated grow-shrink operations)
6beb2c667935 updated for version 7.0b
vimboss
parents:
diff changeset
383 */
6beb2c667935 updated for version 7.0b
vimboss
parents:
diff changeset
384 if (ht->ht_filled * 3 < oldsize * 2 && ht->ht_used > oldsize / 5)
6beb2c667935 updated for version 7.0b
vimboss
parents:
diff changeset
385 return OK;
6beb2c667935 updated for version 7.0b
vimboss
parents:
diff changeset
386
6beb2c667935 updated for version 7.0b
vimboss
parents:
diff changeset
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
6beb2c667935 updated for version 7.0b
vimboss
parents:
diff changeset
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
6beb2c667935 updated for version 7.0b
vimboss
parents:
diff changeset
391 }
6beb2c667935 updated for version 7.0b
vimboss
parents:
diff changeset
392 else
6beb2c667935 updated for version 7.0b
vimboss
parents:
diff changeset
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
8bebcabccc2c updated for version 7.0e01
vimboss
parents: 799
diff changeset
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
6beb2c667935 updated for version 7.0b
vimboss
parents:
diff changeset
398 }
6beb2c667935 updated for version 7.0b
vimboss
parents:
diff changeset
399
6beb2c667935 updated for version 7.0b
vimboss
parents:
diff changeset
400 newsize = HT_INIT_SIZE;
6beb2c667935 updated for version 7.0b
vimboss
parents:
diff changeset
401 while (newsize < minsize)
6beb2c667935 updated for version 7.0b
vimboss
parents:
diff changeset
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
6beb2c667935 updated for version 7.0b
vimboss
parents:
diff changeset
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
6beb2c667935 updated for version 7.0b
vimboss
parents:
diff changeset
406 }
6beb2c667935 updated for version 7.0b
vimboss
parents:
diff changeset
407
6beb2c667935 updated for version 7.0b
vimboss
parents:
diff changeset
408 if (newsize == HT_INIT_SIZE)
6beb2c667935 updated for version 7.0b
vimboss
parents:
diff changeset
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
6beb2c667935 updated for version 7.0b
vimboss
parents:
diff changeset
411 newarray = ht->ht_smallarray;
6beb2c667935 updated for version 7.0b
vimboss
parents:
diff changeset
412 if (ht->ht_array == newarray)
6beb2c667935 updated for version 7.0b
vimboss
parents:
diff changeset
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
6beb2c667935 updated for version 7.0b
vimboss
parents:
diff changeset
417 mch_memmove(temparray, newarray, sizeof(temparray));
6beb2c667935 updated for version 7.0b
vimboss
parents:
diff changeset
418 oldarray = temparray;
6beb2c667935 updated for version 7.0b
vimboss
parents:
diff changeset
419 }
6beb2c667935 updated for version 7.0b
vimboss
parents:
diff changeset
420 else
6beb2c667935 updated for version 7.0b
vimboss
parents:
diff changeset
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
6beb2c667935 updated for version 7.0b
vimboss
parents:
diff changeset
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
6beb2c667935 updated for version 7.0b
vimboss
parents:
diff changeset
432 else
6beb2c667935 updated for version 7.0b
vimboss
parents:
diff changeset
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
6beb2c667935 updated for version 7.0b
vimboss
parents:
diff changeset
436 if (newarray == NULL)
6beb2c667935 updated for version 7.0b
vimboss
parents:
diff changeset
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
6beb2c667935 updated for version 7.0b
vimboss
parents:
diff changeset
441 if (ht->ht_filled < ht->ht_mask)
6beb2c667935 updated for version 7.0b
vimboss
parents:
diff changeset
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
6beb2c667935 updated for version 7.0b
vimboss
parents:
diff changeset
444 return FAIL;
6beb2c667935 updated for version 7.0b
vimboss
parents:
diff changeset
445 }
6beb2c667935 updated for version 7.0b
vimboss
parents:
diff changeset
446 oldarray = ht->ht_array;
6beb2c667935 updated for version 7.0b
vimboss
parents:
diff changeset
447 }
6beb2c667935 updated for version 7.0b
vimboss
parents:
diff changeset
448
6beb2c667935 updated for version 7.0b
vimboss
parents:
diff changeset
449 /*
6beb2c667935 updated for version 7.0b
vimboss
parents:
diff changeset
450 * Move all the items from the old array to the new one, placing them in
6beb2c667935 updated for version 7.0b
vimboss
parents:
diff changeset
451 * the right spot. The new array won't have any removed items, thus this
6beb2c667935 updated for version 7.0b
vimboss
parents:
diff changeset
452 * is also a cleanup action.
6beb2c667935 updated for version 7.0b
vimboss
parents:
diff changeset
453 */
6beb2c667935 updated for version 7.0b
vimboss
parents:
diff changeset
454 newmask = newsize - 1;
835
8bebcabccc2c updated for version 7.0e01
vimboss
parents: 799
diff changeset
455 todo = (int)ht->ht_used;
799
6beb2c667935 updated for version 7.0b
vimboss
parents:
diff changeset
456 for (olditem = oldarray; todo > 0; ++olditem)
6beb2c667935 updated for version 7.0b
vimboss
parents:
diff changeset
457 if (!HASHITEM_EMPTY(olditem))
6beb2c667935 updated for version 7.0b
vimboss
parents:
diff changeset
458 {
6beb2c667935 updated for version 7.0b
vimboss
parents:
diff changeset
459 /*
6beb2c667935 updated for version 7.0b
vimboss
parents:
diff changeset
460 * The algorithm to find the spot to add the item is identical to
6beb2c667935 updated for version 7.0b
vimboss
parents:
diff changeset
461 * the algorithm to find an item in hash_lookup(). But we only
6beb2c667935 updated for version 7.0b
vimboss
parents:
diff changeset
462 * need to search for a NULL key, thus it's simpler.
6beb2c667935 updated for version 7.0b
vimboss
parents:
diff changeset
463 */
3970
2c12cd5c1381 updated for version 7.3.740
Bram Moolenaar <bram@vim.org>
parents: 2520
diff changeset
464 newi = (unsigned)(olditem->hi_hash & newmask);
799
6beb2c667935 updated for version 7.0b
vimboss
parents:
diff changeset
465 newitem = &newarray[newi];
6beb2c667935 updated for version 7.0b
vimboss
parents:
diff changeset
466
6beb2c667935 updated for version 7.0b
vimboss
parents:
diff changeset
467 if (newitem->hi_key != NULL)
6beb2c667935 updated for version 7.0b
vimboss
parents:
diff changeset
468 for (perturb = olditem->hi_hash; ; perturb >>= PERTURB_SHIFT)
6beb2c667935 updated for version 7.0b
vimboss
parents:
diff changeset
469 {
3970
2c12cd5c1381 updated for version 7.3.740
Bram Moolenaar <bram@vim.org>
parents: 2520
diff changeset
470 newi = (unsigned)((newi << 2U) + newi + perturb + 1U);
799
6beb2c667935 updated for version 7.0b
vimboss
parents:
diff changeset
471 newitem = &newarray[newi & newmask];
6beb2c667935 updated for version 7.0b
vimboss
parents:
diff changeset
472 if (newitem->hi_key == NULL)
6beb2c667935 updated for version 7.0b
vimboss
parents:
diff changeset
473 break;
6beb2c667935 updated for version 7.0b
vimboss
parents:
diff changeset
474 }
6beb2c667935 updated for version 7.0b
vimboss
parents:
diff changeset
475 *newitem = *olditem;
6beb2c667935 updated for version 7.0b
vimboss
parents:
diff changeset
476 --todo;
6beb2c667935 updated for version 7.0b
vimboss
parents:
diff changeset
477 }
6beb2c667935 updated for version 7.0b
vimboss
parents:
diff changeset
478
6beb2c667935 updated for version 7.0b
vimboss
parents:
diff changeset
479 if (ht->ht_array != ht->ht_smallarray)
6beb2c667935 updated for version 7.0b
vimboss
parents:
diff changeset
480 vim_free(ht->ht_array);
6beb2c667935 updated for version 7.0b
vimboss
parents:
diff changeset
481 ht->ht_array = newarray;
6beb2c667935 updated for version 7.0b
vimboss
parents:
diff changeset
482 ht->ht_mask = newmask;
6beb2c667935 updated for version 7.0b
vimboss
parents:
diff changeset
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
6beb2c667935 updated for version 7.0b
vimboss
parents:
diff changeset
486
6beb2c667935 updated for version 7.0b
vimboss
parents:
diff changeset
487 return OK;
6beb2c667935 updated for version 7.0b
vimboss
parents:
diff changeset
488 }
6beb2c667935 updated for version 7.0b
vimboss
parents:
diff changeset
489
6beb2c667935 updated for version 7.0b
vimboss
parents:
diff changeset
490 /*
6beb2c667935 updated for version 7.0b
vimboss
parents:
diff changeset
491 * Get the hash number for a key.
6beb2c667935 updated for version 7.0b
vimboss
parents:
diff changeset
492 * If you think you know a better hash function: Compile with HT_DEBUG set and
6beb2c667935 updated for version 7.0b
vimboss
parents:
diff changeset
493 * run a script that uses hashtables a lot. Vim will then print statistics
6beb2c667935 updated for version 7.0b
vimboss
parents:
diff changeset
494 * when exiting. Try that with the current hash algorithm and yours. The
6beb2c667935 updated for version 7.0b
vimboss
parents:
diff changeset
495 * lower the percentage the better.
6beb2c667935 updated for version 7.0b
vimboss
parents:
diff changeset
496 */
6beb2c667935 updated for version 7.0b
vimboss
parents:
diff changeset
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
6beb2c667935 updated for version 7.0b
vimboss
parents:
diff changeset
499 {
6beb2c667935 updated for version 7.0b
vimboss
parents:
diff changeset
500 hash_T hash;
6beb2c667935 updated for version 7.0b
vimboss
parents:
diff changeset
501 char_u *p;
6beb2c667935 updated for version 7.0b
vimboss
parents:
diff changeset
502
6beb2c667935 updated for version 7.0b
vimboss
parents:
diff changeset
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
6beb2c667935 updated for version 7.0b
vimboss
parents:
diff changeset
505 p = key + 1;
6beb2c667935 updated for version 7.0b
vimboss
parents:
diff changeset
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
6beb2c667935 updated for version 7.0b
vimboss
parents:
diff changeset
509 while (*p != NUL)
6beb2c667935 updated for version 7.0b
vimboss
parents:
diff changeset
510 hash = hash * 101 + *p++;
6beb2c667935 updated for version 7.0b
vimboss
parents:
diff changeset
511
6beb2c667935 updated for version 7.0b
vimboss
parents:
diff changeset
512 return hash;
6beb2c667935 updated for version 7.0b
vimboss
parents:
diff changeset
513 }