annotate src/hashtable.c @ 375:f14cbd913415 v7.0097

updated for version 7.0097
author vimboss
date Wed, 29 Jun 2005 22:40:58 +0000
parents 4b9fef49d7ff
children 81fe2ccc1207
Ignore whitespace changes - Everywhere: Within whitespace: At end of lines:
rev   line source
120
34423a71d203 updated for version 7.0042
vimboss
parents:
diff changeset
1 /* vi:set ts=8 sts=4 sw=4:
34423a71d203 updated for version 7.0042
vimboss
parents:
diff changeset
2 *
34423a71d203 updated for version 7.0042
vimboss
parents:
diff changeset
3 * VIM - Vi IMproved by Bram Moolenaar
34423a71d203 updated for version 7.0042
vimboss
parents:
diff changeset
4 *
34423a71d203 updated for version 7.0042
vimboss
parents:
diff changeset
5 * Do ":help uganda" in Vim to read copying and usage conditions.
34423a71d203 updated for version 7.0042
vimboss
parents:
diff changeset
6 * Do ":help credits" in Vim to see a list of people who contributed.
34423a71d203 updated for version 7.0042
vimboss
parents:
diff changeset
7 * See README.txt for an overview of the Vim source code.
34423a71d203 updated for version 7.0042
vimboss
parents:
diff changeset
8 */
34423a71d203 updated for version 7.0042
vimboss
parents:
diff changeset
9
34423a71d203 updated for version 7.0042
vimboss
parents:
diff changeset
10 /*
34423a71d203 updated for version 7.0042
vimboss
parents:
diff changeset
11 * hashtable.c: Handling of a hashtable with Vim-specific properties.
34423a71d203 updated for version 7.0042
vimboss
parents:
diff changeset
12 *
34423a71d203 updated for version 7.0042
vimboss
parents:
diff changeset
13 * Each item in a hashtable has a NUL terminated string key. A key can appear
34423a71d203 updated for version 7.0042
vimboss
parents:
diff changeset
14 * only once in the table.
34423a71d203 updated for version 7.0042
vimboss
parents:
diff changeset
15 *
34423a71d203 updated for version 7.0042
vimboss
parents:
diff changeset
16 * A hash number is computed from the key for quick lookup. When the hashes
34423a71d203 updated for version 7.0042
vimboss
parents:
diff changeset
17 * of two different keys point to the same entry an algorithm is used to
34423a71d203 updated for version 7.0042
vimboss
parents:
diff changeset
18 * iterate over other entries in the table until the right one is found.
34423a71d203 updated for version 7.0042
vimboss
parents:
diff changeset
19 * To make the iteration work removed keys are different from entries where a
34423a71d203 updated for version 7.0042
vimboss
parents:
diff changeset
20 * key was never present.
34423a71d203 updated for version 7.0042
vimboss
parents:
diff changeset
21 *
34423a71d203 updated for version 7.0042
vimboss
parents:
diff changeset
22 * The mechanism has been partly based on how Python Dictionaries are
34423a71d203 updated for version 7.0042
vimboss
parents:
diff changeset
23 * implemented. The algorithm is from Knuth Vol. 3, Sec. 6.4.
34423a71d203 updated for version 7.0042
vimboss
parents:
diff changeset
24 *
34423a71d203 updated for version 7.0042
vimboss
parents:
diff changeset
25 * The hashtable grows to accommodate more entries when needed. At least 1/3
34423a71d203 updated for version 7.0042
vimboss
parents:
diff changeset
26 * of the entries is empty to keep the lookup efficient (at the cost of extra
34423a71d203 updated for version 7.0042
vimboss
parents:
diff changeset
27 * memory).
34423a71d203 updated for version 7.0042
vimboss
parents:
diff changeset
28 */
34423a71d203 updated for version 7.0042
vimboss
parents:
diff changeset
29
34423a71d203 updated for version 7.0042
vimboss
parents:
diff changeset
30 #include "vim.h"
34423a71d203 updated for version 7.0042
vimboss
parents:
diff changeset
31
34423a71d203 updated for version 7.0042
vimboss
parents:
diff changeset
32 #if defined(FEAT_EVAL) || defined(FEAT_SYN_HL) || defined(PROTO)
34423a71d203 updated for version 7.0042
vimboss
parents:
diff changeset
33
154
1a145815483e updated for version 7.0047
vimboss
parents: 140
diff changeset
34 #if 0
242
a711f7a6852d updated for version 7.0067
vimboss
parents: 237
diff changeset
35 # define HT_DEBUG /* extra checks for table consistency and statistics */
a711f7a6852d updated for version 7.0067
vimboss
parents: 237
diff changeset
36
a711f7a6852d updated for version 7.0067
vimboss
parents: 237
diff changeset
37 static long hash_count_lookup = 0; /* count number of hashtab lookups */
a711f7a6852d updated for version 7.0067
vimboss
parents: 237
diff changeset
38 static long hash_count_perturb = 0; /* count number of "misses" */
120
34423a71d203 updated for version 7.0042
vimboss
parents:
diff changeset
39 #endif
34423a71d203 updated for version 7.0042
vimboss
parents:
diff changeset
40
34423a71d203 updated for version 7.0042
vimboss
parents:
diff changeset
41 /* Magic value for algorithm that walks through the array. */
34423a71d203 updated for version 7.0042
vimboss
parents:
diff changeset
42 #define PERTURB_SHIFT 5
34423a71d203 updated for version 7.0042
vimboss
parents:
diff changeset
43
237
73354c21f1e4 updated for version 7.0066
vimboss
parents: 154
diff changeset
44 static int hash_may_resize __ARGS((hashtab_T *ht, int minitems));
120
34423a71d203 updated for version 7.0042
vimboss
parents:
diff changeset
45
242
a711f7a6852d updated for version 7.0067
vimboss
parents: 237
diff changeset
46 #if 0 /* currently not used */
120
34423a71d203 updated for version 7.0042
vimboss
parents:
diff changeset
47 /*
34423a71d203 updated for version 7.0042
vimboss
parents:
diff changeset
48 * Create an empty hash table.
34423a71d203 updated for version 7.0042
vimboss
parents:
diff changeset
49 * Returns NULL when out of memory.
34423a71d203 updated for version 7.0042
vimboss
parents:
diff changeset
50 */
135
b5fc81a825a1 updated for version 7.0044
vimboss
parents: 123
diff changeset
51 hashtab_T *
120
34423a71d203 updated for version 7.0042
vimboss
parents:
diff changeset
52 hash_create()
34423a71d203 updated for version 7.0042
vimboss
parents:
diff changeset
53 {
135
b5fc81a825a1 updated for version 7.0044
vimboss
parents: 123
diff changeset
54 hashtab_T *ht;
120
34423a71d203 updated for version 7.0042
vimboss
parents:
diff changeset
55
135
b5fc81a825a1 updated for version 7.0044
vimboss
parents: 123
diff changeset
56 ht = (hashtab_T *)alloc(sizeof(hashtab_T));
120
34423a71d203 updated for version 7.0042
vimboss
parents:
diff changeset
57 if (ht != NULL)
34423a71d203 updated for version 7.0042
vimboss
parents:
diff changeset
58 hash_init(ht);
34423a71d203 updated for version 7.0042
vimboss
parents:
diff changeset
59 return ht;
34423a71d203 updated for version 7.0042
vimboss
parents:
diff changeset
60 }
34423a71d203 updated for version 7.0042
vimboss
parents:
diff changeset
61 #endif
34423a71d203 updated for version 7.0042
vimboss
parents:
diff changeset
62
34423a71d203 updated for version 7.0042
vimboss
parents:
diff changeset
63 /*
34423a71d203 updated for version 7.0042
vimboss
parents:
diff changeset
64 * Initialize an empty hash table.
34423a71d203 updated for version 7.0042
vimboss
parents:
diff changeset
65 */
34423a71d203 updated for version 7.0042
vimboss
parents:
diff changeset
66 void
34423a71d203 updated for version 7.0042
vimboss
parents:
diff changeset
67 hash_init(ht)
135
b5fc81a825a1 updated for version 7.0044
vimboss
parents: 123
diff changeset
68 hashtab_T *ht;
120
34423a71d203 updated for version 7.0042
vimboss
parents:
diff changeset
69 {
34423a71d203 updated for version 7.0042
vimboss
parents:
diff changeset
70 /* This zeroes all "ht_" entries and all the "hi_key" in "ht_smallarray". */
135
b5fc81a825a1 updated for version 7.0044
vimboss
parents: 123
diff changeset
71 vim_memset(ht, 0, sizeof(hashtab_T));
120
34423a71d203 updated for version 7.0042
vimboss
parents:
diff changeset
72 ht->ht_array = ht->ht_smallarray;
34423a71d203 updated for version 7.0042
vimboss
parents:
diff changeset
73 ht->ht_mask = HT_INIT_SIZE - 1;
34423a71d203 updated for version 7.0042
vimboss
parents:
diff changeset
74 }
34423a71d203 updated for version 7.0042
vimboss
parents:
diff changeset
75
34423a71d203 updated for version 7.0042
vimboss
parents:
diff changeset
76 /*
123
f67f8a8d81ba updated for version 7.0043
vimboss
parents: 120
diff changeset
77 * Free the array of a hash table. Does not free the items it contains!
f67f8a8d81ba updated for version 7.0043
vimboss
parents: 120
diff changeset
78 * If "ht" is not freed then you should call hash_init() next!
120
34423a71d203 updated for version 7.0042
vimboss
parents:
diff changeset
79 */
34423a71d203 updated for version 7.0042
vimboss
parents:
diff changeset
80 void
123
f67f8a8d81ba updated for version 7.0043
vimboss
parents: 120
diff changeset
81 hash_clear(ht)
135
b5fc81a825a1 updated for version 7.0044
vimboss
parents: 123
diff changeset
82 hashtab_T *ht;
120
34423a71d203 updated for version 7.0042
vimboss
parents:
diff changeset
83 {
34423a71d203 updated for version 7.0042
vimboss
parents:
diff changeset
84 if (ht->ht_array != ht->ht_smallarray)
34423a71d203 updated for version 7.0042
vimboss
parents:
diff changeset
85 vim_free(ht->ht_array);
34423a71d203 updated for version 7.0042
vimboss
parents:
diff changeset
86 }
34423a71d203 updated for version 7.0042
vimboss
parents:
diff changeset
87
34423a71d203 updated for version 7.0042
vimboss
parents:
diff changeset
88 /*
34423a71d203 updated for version 7.0042
vimboss
parents:
diff changeset
89 * Find "key" in hashtable "ht". "key" must not be NULL.
34423a71d203 updated for version 7.0042
vimboss
parents:
diff changeset
90 * Always returns a pointer to a hashitem. If the item was not found then
34423a71d203 updated for version 7.0042
vimboss
parents:
diff changeset
91 * HASHITEM_EMPTY() is TRUE. The pointer is then the place where the key
34423a71d203 updated for version 7.0042
vimboss
parents:
diff changeset
92 * would be added.
34423a71d203 updated for version 7.0042
vimboss
parents:
diff changeset
93 * WARNING: The returned pointer becomes invalid when the hashtable is changed
34423a71d203 updated for version 7.0042
vimboss
parents:
diff changeset
94 * (adding, setting or removing an item)!
34423a71d203 updated for version 7.0042
vimboss
parents:
diff changeset
95 */
135
b5fc81a825a1 updated for version 7.0044
vimboss
parents: 123
diff changeset
96 hashitem_T *
120
34423a71d203 updated for version 7.0042
vimboss
parents:
diff changeset
97 hash_find(ht, key)
135
b5fc81a825a1 updated for version 7.0044
vimboss
parents: 123
diff changeset
98 hashtab_T *ht;
120
34423a71d203 updated for version 7.0042
vimboss
parents:
diff changeset
99 char_u *key;
34423a71d203 updated for version 7.0042
vimboss
parents:
diff changeset
100 {
34423a71d203 updated for version 7.0042
vimboss
parents:
diff changeset
101 return hash_lookup(ht, key, hash_hash(key));
34423a71d203 updated for version 7.0042
vimboss
parents:
diff changeset
102 }
34423a71d203 updated for version 7.0042
vimboss
parents:
diff changeset
103
34423a71d203 updated for version 7.0042
vimboss
parents:
diff changeset
104 /*
34423a71d203 updated for version 7.0042
vimboss
parents:
diff changeset
105 * Like hash_find(), but caller computes "hash".
34423a71d203 updated for version 7.0042
vimboss
parents:
diff changeset
106 */
135
b5fc81a825a1 updated for version 7.0044
vimboss
parents: 123
diff changeset
107 hashitem_T *
120
34423a71d203 updated for version 7.0042
vimboss
parents:
diff changeset
108 hash_lookup(ht, key, hash)
135
b5fc81a825a1 updated for version 7.0044
vimboss
parents: 123
diff changeset
109 hashtab_T *ht;
120
34423a71d203 updated for version 7.0042
vimboss
parents:
diff changeset
110 char_u *key;
135
b5fc81a825a1 updated for version 7.0044
vimboss
parents: 123
diff changeset
111 hash_T hash;
120
34423a71d203 updated for version 7.0042
vimboss
parents:
diff changeset
112 {
135
b5fc81a825a1 updated for version 7.0044
vimboss
parents: 123
diff changeset
113 hash_T perturb;
b5fc81a825a1 updated for version 7.0044
vimboss
parents: 123
diff changeset
114 hashitem_T *freeitem;
b5fc81a825a1 updated for version 7.0044
vimboss
parents: 123
diff changeset
115 hashitem_T *hi;
120
34423a71d203 updated for version 7.0042
vimboss
parents:
diff changeset
116 int idx;
34423a71d203 updated for version 7.0042
vimboss
parents:
diff changeset
117
242
a711f7a6852d updated for version 7.0067
vimboss
parents: 237
diff changeset
118 #ifdef HT_DEBUG
a711f7a6852d updated for version 7.0067
vimboss
parents: 237
diff changeset
119 ++hash_count_lookup;
a711f7a6852d updated for version 7.0067
vimboss
parents: 237
diff changeset
120 #endif
a711f7a6852d updated for version 7.0067
vimboss
parents: 237
diff changeset
121
120
34423a71d203 updated for version 7.0042
vimboss
parents:
diff changeset
122 /*
34423a71d203 updated for version 7.0042
vimboss
parents:
diff changeset
123 * Quickly handle the most common situations:
34423a71d203 updated for version 7.0042
vimboss
parents:
diff changeset
124 * - return if there is no item at all
34423a71d203 updated for version 7.0042
vimboss
parents:
diff changeset
125 * - skip over a removed item
34423a71d203 updated for version 7.0042
vimboss
parents:
diff changeset
126 * - return if the item matches
34423a71d203 updated for version 7.0042
vimboss
parents:
diff changeset
127 */
34423a71d203 updated for version 7.0042
vimboss
parents:
diff changeset
128 idx = hash & ht->ht_mask;
34423a71d203 updated for version 7.0042
vimboss
parents:
diff changeset
129 hi = &ht->ht_array[idx];
34423a71d203 updated for version 7.0042
vimboss
parents:
diff changeset
130
34423a71d203 updated for version 7.0042
vimboss
parents:
diff changeset
131 if (hi->hi_key == NULL)
34423a71d203 updated for version 7.0042
vimboss
parents:
diff changeset
132 return hi;
34423a71d203 updated for version 7.0042
vimboss
parents:
diff changeset
133 if (hi->hi_key == HI_KEY_REMOVED)
34423a71d203 updated for version 7.0042
vimboss
parents:
diff changeset
134 freeitem = hi;
34423a71d203 updated for version 7.0042
vimboss
parents:
diff changeset
135 else if (hi->hi_hash == hash && STRCMP(hi->hi_key, key) == 0)
34423a71d203 updated for version 7.0042
vimboss
parents:
diff changeset
136 return hi;
34423a71d203 updated for version 7.0042
vimboss
parents:
diff changeset
137 else
34423a71d203 updated for version 7.0042
vimboss
parents:
diff changeset
138 freeitem = NULL;
34423a71d203 updated for version 7.0042
vimboss
parents:
diff changeset
139
34423a71d203 updated for version 7.0042
vimboss
parents:
diff changeset
140 /*
34423a71d203 updated for version 7.0042
vimboss
parents:
diff changeset
141 * Need to search through the table to find the key. The algorithm
34423a71d203 updated for version 7.0042
vimboss
parents:
diff changeset
142 * to step through the table starts with large steps, gradually becoming
34423a71d203 updated for version 7.0042
vimboss
parents:
diff changeset
143 * smaller down to (1/4 table size + 1). This means it goes through all
34423a71d203 updated for version 7.0042
vimboss
parents:
diff changeset
144 * table entries in the end.
34423a71d203 updated for version 7.0042
vimboss
parents:
diff changeset
145 * When we run into a NULL key it's clear that the key isn't there.
34423a71d203 updated for version 7.0042
vimboss
parents:
diff changeset
146 * Return the first available slot found (can be a slot of a removed
34423a71d203 updated for version 7.0042
vimboss
parents:
diff changeset
147 * item).
34423a71d203 updated for version 7.0042
vimboss
parents:
diff changeset
148 */
34423a71d203 updated for version 7.0042
vimboss
parents:
diff changeset
149 for (perturb = hash; ; perturb >>= PERTURB_SHIFT)
34423a71d203 updated for version 7.0042
vimboss
parents:
diff changeset
150 {
242
a711f7a6852d updated for version 7.0067
vimboss
parents: 237
diff changeset
151 #ifdef HT_DEBUG
a711f7a6852d updated for version 7.0067
vimboss
parents: 237
diff changeset
152 ++hash_count_perturb; /* count a "miss" for hashtab lookup */
a711f7a6852d updated for version 7.0067
vimboss
parents: 237
diff changeset
153 #endif
120
34423a71d203 updated for version 7.0042
vimboss
parents:
diff changeset
154 idx = (idx << 2) + idx + perturb + 1;
34423a71d203 updated for version 7.0042
vimboss
parents:
diff changeset
155 hi = &ht->ht_array[idx & ht->ht_mask];
34423a71d203 updated for version 7.0042
vimboss
parents:
diff changeset
156 if (hi->hi_key == NULL)
34423a71d203 updated for version 7.0042
vimboss
parents:
diff changeset
157 return freeitem == NULL ? hi : freeitem;
34423a71d203 updated for version 7.0042
vimboss
parents:
diff changeset
158 if (hi->hi_hash == hash
34423a71d203 updated for version 7.0042
vimboss
parents:
diff changeset
159 && hi->hi_key != HI_KEY_REMOVED
34423a71d203 updated for version 7.0042
vimboss
parents:
diff changeset
160 && STRCMP(hi->hi_key, key) == 0)
34423a71d203 updated for version 7.0042
vimboss
parents:
diff changeset
161 return hi;
34423a71d203 updated for version 7.0042
vimboss
parents:
diff changeset
162 if (hi->hi_key == HI_KEY_REMOVED && freeitem == NULL)
34423a71d203 updated for version 7.0042
vimboss
parents:
diff changeset
163 freeitem = hi;
34423a71d203 updated for version 7.0042
vimboss
parents:
diff changeset
164 }
34423a71d203 updated for version 7.0042
vimboss
parents:
diff changeset
165 }
34423a71d203 updated for version 7.0042
vimboss
parents:
diff changeset
166
34423a71d203 updated for version 7.0042
vimboss
parents:
diff changeset
167 /*
242
a711f7a6852d updated for version 7.0067
vimboss
parents: 237
diff changeset
168 * Print the efficiency of hashtable lookups.
a711f7a6852d updated for version 7.0067
vimboss
parents: 237
diff changeset
169 * Useful when trying different hash algorithms.
a711f7a6852d updated for version 7.0067
vimboss
parents: 237
diff changeset
170 * Called when exiting.
a711f7a6852d updated for version 7.0067
vimboss
parents: 237
diff changeset
171 */
a711f7a6852d updated for version 7.0067
vimboss
parents: 237
diff changeset
172 void
a711f7a6852d updated for version 7.0067
vimboss
parents: 237
diff changeset
173 hash_debug_results()
a711f7a6852d updated for version 7.0067
vimboss
parents: 237
diff changeset
174 {
a711f7a6852d updated for version 7.0067
vimboss
parents: 237
diff changeset
175 #ifdef HT_DEBUG
a711f7a6852d updated for version 7.0067
vimboss
parents: 237
diff changeset
176 fprintf(stderr, "\r\n\r\n\r\n\r\n");
a711f7a6852d updated for version 7.0067
vimboss
parents: 237
diff changeset
177 fprintf(stderr, "Number of hashtable lookups: %ld\r\n", hash_count_lookup);
a711f7a6852d updated for version 7.0067
vimboss
parents: 237
diff changeset
178 fprintf(stderr, "Number of perturb loops: %ld\r\n", hash_count_perturb);
a711f7a6852d updated for version 7.0067
vimboss
parents: 237
diff changeset
179 fprintf(stderr, "Percentage of perturb loops: %ld%%\r\n",
a711f7a6852d updated for version 7.0067
vimboss
parents: 237
diff changeset
180 hash_count_perturb * 100 / hash_count_lookup);
a711f7a6852d updated for version 7.0067
vimboss
parents: 237
diff changeset
181 #endif
a711f7a6852d updated for version 7.0067
vimboss
parents: 237
diff changeset
182 }
a711f7a6852d updated for version 7.0067
vimboss
parents: 237
diff changeset
183
a711f7a6852d updated for version 7.0067
vimboss
parents: 237
diff changeset
184 /*
120
34423a71d203 updated for version 7.0042
vimboss
parents:
diff changeset
185 * Add item with key "key" to hashtable "ht".
34423a71d203 updated for version 7.0042
vimboss
parents:
diff changeset
186 * Returns FAIL when out of memory or the key is already present.
34423a71d203 updated for version 7.0042
vimboss
parents:
diff changeset
187 */
34423a71d203 updated for version 7.0042
vimboss
parents:
diff changeset
188 int
34423a71d203 updated for version 7.0042
vimboss
parents:
diff changeset
189 hash_add(ht, key)
135
b5fc81a825a1 updated for version 7.0044
vimboss
parents: 123
diff changeset
190 hashtab_T *ht;
120
34423a71d203 updated for version 7.0042
vimboss
parents:
diff changeset
191 char_u *key;
34423a71d203 updated for version 7.0042
vimboss
parents:
diff changeset
192 {
135
b5fc81a825a1 updated for version 7.0044
vimboss
parents: 123
diff changeset
193 hash_T hash = hash_hash(key);
b5fc81a825a1 updated for version 7.0044
vimboss
parents: 123
diff changeset
194 hashitem_T *hi;
120
34423a71d203 updated for version 7.0042
vimboss
parents:
diff changeset
195
34423a71d203 updated for version 7.0042
vimboss
parents:
diff changeset
196 hi = hash_lookup(ht, key, hash);
34423a71d203 updated for version 7.0042
vimboss
parents:
diff changeset
197 if (!HASHITEM_EMPTY(hi))
34423a71d203 updated for version 7.0042
vimboss
parents:
diff changeset
198 {
34423a71d203 updated for version 7.0042
vimboss
parents:
diff changeset
199 EMSG2(_(e_intern2), "hash_add()");
34423a71d203 updated for version 7.0042
vimboss
parents:
diff changeset
200 return FAIL;
34423a71d203 updated for version 7.0042
vimboss
parents:
diff changeset
201 }
34423a71d203 updated for version 7.0042
vimboss
parents:
diff changeset
202 return hash_add_item(ht, hi, key, hash);
34423a71d203 updated for version 7.0042
vimboss
parents:
diff changeset
203 }
34423a71d203 updated for version 7.0042
vimboss
parents:
diff changeset
204
34423a71d203 updated for version 7.0042
vimboss
parents:
diff changeset
205 /*
34423a71d203 updated for version 7.0042
vimboss
parents:
diff changeset
206 * Add item "hi" with "key" to hashtable "ht". "key" must not be NULL and
34423a71d203 updated for version 7.0042
vimboss
parents:
diff changeset
207 * "hi" must have been obtained with hash_lookup() and point to an empty item.
34423a71d203 updated for version 7.0042
vimboss
parents:
diff changeset
208 * "hi" is invalid after this!
34423a71d203 updated for version 7.0042
vimboss
parents:
diff changeset
209 * Returns OK or FAIL (out of memory).
34423a71d203 updated for version 7.0042
vimboss
parents:
diff changeset
210 */
135
b5fc81a825a1 updated for version 7.0044
vimboss
parents: 123
diff changeset
211 int
120
34423a71d203 updated for version 7.0042
vimboss
parents:
diff changeset
212 hash_add_item(ht, hi, key, hash)
135
b5fc81a825a1 updated for version 7.0044
vimboss
parents: 123
diff changeset
213 hashtab_T *ht;
b5fc81a825a1 updated for version 7.0044
vimboss
parents: 123
diff changeset
214 hashitem_T *hi;
120
34423a71d203 updated for version 7.0042
vimboss
parents:
diff changeset
215 char_u *key;
135
b5fc81a825a1 updated for version 7.0044
vimboss
parents: 123
diff changeset
216 hash_T hash;
120
34423a71d203 updated for version 7.0042
vimboss
parents:
diff changeset
217 {
34423a71d203 updated for version 7.0042
vimboss
parents:
diff changeset
218 /* If resizing failed before and it fails again we can't add an item. */
237
73354c21f1e4 updated for version 7.0066
vimboss
parents: 154
diff changeset
219 if (ht->ht_error && hash_may_resize(ht, 0) == FAIL)
120
34423a71d203 updated for version 7.0042
vimboss
parents:
diff changeset
220 return FAIL;
34423a71d203 updated for version 7.0042
vimboss
parents:
diff changeset
221
34423a71d203 updated for version 7.0042
vimboss
parents:
diff changeset
222 ++ht->ht_used;
34423a71d203 updated for version 7.0042
vimboss
parents:
diff changeset
223 if (hi->hi_key == NULL)
34423a71d203 updated for version 7.0042
vimboss
parents:
diff changeset
224 ++ht->ht_filled;
34423a71d203 updated for version 7.0042
vimboss
parents:
diff changeset
225 hi->hi_key = key;
34423a71d203 updated for version 7.0042
vimboss
parents:
diff changeset
226 hi->hi_hash = hash;
34423a71d203 updated for version 7.0042
vimboss
parents:
diff changeset
227
34423a71d203 updated for version 7.0042
vimboss
parents:
diff changeset
228 /* When the space gets low may resize the array. */
237
73354c21f1e4 updated for version 7.0066
vimboss
parents: 154
diff changeset
229 return hash_may_resize(ht, 0);
120
34423a71d203 updated for version 7.0042
vimboss
parents:
diff changeset
230 }
34423a71d203 updated for version 7.0042
vimboss
parents:
diff changeset
231
34423a71d203 updated for version 7.0042
vimboss
parents:
diff changeset
232 #if 0 /* not used */
34423a71d203 updated for version 7.0042
vimboss
parents:
diff changeset
233 /*
34423a71d203 updated for version 7.0042
vimboss
parents:
diff changeset
234 * Overwrite hashtable item "hi" with "key". "hi" must point to the item that
34423a71d203 updated for version 7.0042
vimboss
parents:
diff changeset
235 * is to be overwritten. Thus the number of items in the hashtable doesn't
34423a71d203 updated for version 7.0042
vimboss
parents:
diff changeset
236 * change.
34423a71d203 updated for version 7.0042
vimboss
parents:
diff changeset
237 * Although the key must be identical, the pointer may be different, thus it's
34423a71d203 updated for version 7.0042
vimboss
parents:
diff changeset
238 * set anyway (the key is part of an item with that key).
34423a71d203 updated for version 7.0042
vimboss
parents:
diff changeset
239 * The caller must take care of freeing the old item.
34423a71d203 updated for version 7.0042
vimboss
parents:
diff changeset
240 * "hi" is invalid after this!
34423a71d203 updated for version 7.0042
vimboss
parents:
diff changeset
241 */
34423a71d203 updated for version 7.0042
vimboss
parents:
diff changeset
242 void
34423a71d203 updated for version 7.0042
vimboss
parents:
diff changeset
243 hash_set(hi, key)
135
b5fc81a825a1 updated for version 7.0044
vimboss
parents: 123
diff changeset
244 hashitem_T *hi;
120
34423a71d203 updated for version 7.0042
vimboss
parents:
diff changeset
245 char_u *key;
34423a71d203 updated for version 7.0042
vimboss
parents:
diff changeset
246 {
34423a71d203 updated for version 7.0042
vimboss
parents:
diff changeset
247 hi->hi_key = key;
34423a71d203 updated for version 7.0042
vimboss
parents:
diff changeset
248 }
34423a71d203 updated for version 7.0042
vimboss
parents:
diff changeset
249 #endif
34423a71d203 updated for version 7.0042
vimboss
parents:
diff changeset
250
34423a71d203 updated for version 7.0042
vimboss
parents:
diff changeset
251 /*
34423a71d203 updated for version 7.0042
vimboss
parents:
diff changeset
252 * Remove item "hi" from hashtable "ht". "hi" must have been obtained with
371
4b9fef49d7ff updated for version 7.0095
vimboss
parents: 301
diff changeset
253 * hash_lookup().
123
f67f8a8d81ba updated for version 7.0043
vimboss
parents: 120
diff changeset
254 * The caller must take care of freeing the item itself.
120
34423a71d203 updated for version 7.0042
vimboss
parents:
diff changeset
255 */
34423a71d203 updated for version 7.0042
vimboss
parents:
diff changeset
256 void
34423a71d203 updated for version 7.0042
vimboss
parents:
diff changeset
257 hash_remove(ht, hi)
135
b5fc81a825a1 updated for version 7.0044
vimboss
parents: 123
diff changeset
258 hashtab_T *ht;
b5fc81a825a1 updated for version 7.0044
vimboss
parents: 123
diff changeset
259 hashitem_T *hi;
120
34423a71d203 updated for version 7.0042
vimboss
parents:
diff changeset
260 {
34423a71d203 updated for version 7.0042
vimboss
parents:
diff changeset
261 --ht->ht_used;
34423a71d203 updated for version 7.0042
vimboss
parents:
diff changeset
262 hi->hi_key = HI_KEY_REMOVED;
237
73354c21f1e4 updated for version 7.0066
vimboss
parents: 154
diff changeset
263 hash_may_resize(ht, 0);
120
34423a71d203 updated for version 7.0042
vimboss
parents:
diff changeset
264 }
34423a71d203 updated for version 7.0042
vimboss
parents:
diff changeset
265
34423a71d203 updated for version 7.0042
vimboss
parents:
diff changeset
266 /*
123
f67f8a8d81ba updated for version 7.0043
vimboss
parents: 120
diff changeset
267 * Lock a hashtable: prevent that ht_array changes.
f67f8a8d81ba updated for version 7.0043
vimboss
parents: 120
diff changeset
268 * Don't use this when items are to be added!
f67f8a8d81ba updated for version 7.0043
vimboss
parents: 120
diff changeset
269 * Must call hash_unlock() later.
f67f8a8d81ba updated for version 7.0043
vimboss
parents: 120
diff changeset
270 */
f67f8a8d81ba updated for version 7.0043
vimboss
parents: 120
diff changeset
271 void
f67f8a8d81ba updated for version 7.0043
vimboss
parents: 120
diff changeset
272 hash_lock(ht)
135
b5fc81a825a1 updated for version 7.0044
vimboss
parents: 123
diff changeset
273 hashtab_T *ht;
123
f67f8a8d81ba updated for version 7.0043
vimboss
parents: 120
diff changeset
274 {
f67f8a8d81ba updated for version 7.0043
vimboss
parents: 120
diff changeset
275 ++ht->ht_locked;
f67f8a8d81ba updated for version 7.0043
vimboss
parents: 120
diff changeset
276 }
f67f8a8d81ba updated for version 7.0043
vimboss
parents: 120
diff changeset
277
301
006e9c8a6a8a updated for version 7.0079
vimboss
parents: 242
diff changeset
278 #if 0 /* currently not used */
123
f67f8a8d81ba updated for version 7.0043
vimboss
parents: 120
diff changeset
279 /*
237
73354c21f1e4 updated for version 7.0066
vimboss
parents: 154
diff changeset
280 * Lock a hashtable at the specified number of entries.
73354c21f1e4 updated for version 7.0066
vimboss
parents: 154
diff changeset
281 * Caller must make sure no more than "size" entries will be added.
73354c21f1e4 updated for version 7.0066
vimboss
parents: 154
diff changeset
282 * Must call hash_unlock() later.
73354c21f1e4 updated for version 7.0066
vimboss
parents: 154
diff changeset
283 */
73354c21f1e4 updated for version 7.0066
vimboss
parents: 154
diff changeset
284 void
73354c21f1e4 updated for version 7.0066
vimboss
parents: 154
diff changeset
285 hash_lock_size(ht, size)
73354c21f1e4 updated for version 7.0066
vimboss
parents: 154
diff changeset
286 hashtab_T *ht;
73354c21f1e4 updated for version 7.0066
vimboss
parents: 154
diff changeset
287 int size;
73354c21f1e4 updated for version 7.0066
vimboss
parents: 154
diff changeset
288 {
73354c21f1e4 updated for version 7.0066
vimboss
parents: 154
diff changeset
289 (void)hash_may_resize(ht, size);
73354c21f1e4 updated for version 7.0066
vimboss
parents: 154
diff changeset
290 ++ht->ht_locked;
73354c21f1e4 updated for version 7.0066
vimboss
parents: 154
diff changeset
291 }
301
006e9c8a6a8a updated for version 7.0079
vimboss
parents: 242
diff changeset
292 #endif
237
73354c21f1e4 updated for version 7.0066
vimboss
parents: 154
diff changeset
293
73354c21f1e4 updated for version 7.0066
vimboss
parents: 154
diff changeset
294 /*
123
f67f8a8d81ba updated for version 7.0043
vimboss
parents: 120
diff changeset
295 * Unlock a hashtable: allow ht_array changes again.
f67f8a8d81ba updated for version 7.0043
vimboss
parents: 120
diff changeset
296 * Table will be resized (shrink) when necessary.
f67f8a8d81ba updated for version 7.0043
vimboss
parents: 120
diff changeset
297 * This must balance a call to hash_lock().
f67f8a8d81ba updated for version 7.0043
vimboss
parents: 120
diff changeset
298 */
f67f8a8d81ba updated for version 7.0043
vimboss
parents: 120
diff changeset
299 void
f67f8a8d81ba updated for version 7.0043
vimboss
parents: 120
diff changeset
300 hash_unlock(ht)
135
b5fc81a825a1 updated for version 7.0044
vimboss
parents: 123
diff changeset
301 hashtab_T *ht;
123
f67f8a8d81ba updated for version 7.0043
vimboss
parents: 120
diff changeset
302 {
f67f8a8d81ba updated for version 7.0043
vimboss
parents: 120
diff changeset
303 --ht->ht_locked;
237
73354c21f1e4 updated for version 7.0066
vimboss
parents: 154
diff changeset
304 (void)hash_may_resize(ht, 0);
123
f67f8a8d81ba updated for version 7.0043
vimboss
parents: 120
diff changeset
305 }
f67f8a8d81ba updated for version 7.0043
vimboss
parents: 120
diff changeset
306
f67f8a8d81ba updated for version 7.0043
vimboss
parents: 120
diff changeset
307 /*
120
34423a71d203 updated for version 7.0042
vimboss
parents:
diff changeset
308 * Shrink a hashtable when there is too much empty space.
34423a71d203 updated for version 7.0042
vimboss
parents:
diff changeset
309 * Grow a hashtable when there is not enough empty space.
34423a71d203 updated for version 7.0042
vimboss
parents:
diff changeset
310 * Returns OK or FAIL (out of memory).
34423a71d203 updated for version 7.0042
vimboss
parents:
diff changeset
311 */
34423a71d203 updated for version 7.0042
vimboss
parents:
diff changeset
312 static int
237
73354c21f1e4 updated for version 7.0066
vimboss
parents: 154
diff changeset
313 hash_may_resize(ht, minitems)
135
b5fc81a825a1 updated for version 7.0044
vimboss
parents: 123
diff changeset
314 hashtab_T *ht;
237
73354c21f1e4 updated for version 7.0066
vimboss
parents: 154
diff changeset
315 int minitems; /* minimal number of items */
120
34423a71d203 updated for version 7.0042
vimboss
parents:
diff changeset
316 {
135
b5fc81a825a1 updated for version 7.0044
vimboss
parents: 123
diff changeset
317 hashitem_T temparray[HT_INIT_SIZE];
b5fc81a825a1 updated for version 7.0044
vimboss
parents: 123
diff changeset
318 hashitem_T *oldarray, *newarray;
b5fc81a825a1 updated for version 7.0044
vimboss
parents: 123
diff changeset
319 hashitem_T *olditem, *newitem;
120
34423a71d203 updated for version 7.0042
vimboss
parents:
diff changeset
320 int newi;
34423a71d203 updated for version 7.0042
vimboss
parents:
diff changeset
321 int todo;
34423a71d203 updated for version 7.0042
vimboss
parents:
diff changeset
322 long_u oldsize, newsize;
34423a71d203 updated for version 7.0042
vimboss
parents:
diff changeset
323 long_u minsize;
34423a71d203 updated for version 7.0042
vimboss
parents:
diff changeset
324 long_u newmask;
135
b5fc81a825a1 updated for version 7.0044
vimboss
parents: 123
diff changeset
325 hash_T perturb;
120
34423a71d203 updated for version 7.0042
vimboss
parents:
diff changeset
326
123
f67f8a8d81ba updated for version 7.0043
vimboss
parents: 120
diff changeset
327 /* Don't resize a locked table. */
f67f8a8d81ba updated for version 7.0043
vimboss
parents: 120
diff changeset
328 if (ht->ht_locked > 0)
f67f8a8d81ba updated for version 7.0043
vimboss
parents: 120
diff changeset
329 return OK;
f67f8a8d81ba updated for version 7.0043
vimboss
parents: 120
diff changeset
330
120
34423a71d203 updated for version 7.0042
vimboss
parents:
diff changeset
331 #ifdef HT_DEBUG
34423a71d203 updated for version 7.0042
vimboss
parents:
diff changeset
332 if (ht->ht_used > ht->ht_filled)
34423a71d203 updated for version 7.0042
vimboss
parents:
diff changeset
333 EMSG("hash_may_resize(): more used than filled");
34423a71d203 updated for version 7.0042
vimboss
parents:
diff changeset
334 if (ht->ht_filled >= ht->ht_mask + 1)
34423a71d203 updated for version 7.0042
vimboss
parents:
diff changeset
335 EMSG("hash_may_resize(): table completely filled");
34423a71d203 updated for version 7.0042
vimboss
parents:
diff changeset
336 #endif
34423a71d203 updated for version 7.0042
vimboss
parents:
diff changeset
337
237
73354c21f1e4 updated for version 7.0066
vimboss
parents: 154
diff changeset
338 if (minitems == 0)
73354c21f1e4 updated for version 7.0066
vimboss
parents: 154
diff changeset
339 {
73354c21f1e4 updated for version 7.0066
vimboss
parents: 154
diff changeset
340 /* Return quickly for small tables with at least two NULL items. NULL
73354c21f1e4 updated for version 7.0066
vimboss
parents: 154
diff changeset
341 * items are required for the lookup to decide a key isn't there. */
73354c21f1e4 updated for version 7.0066
vimboss
parents: 154
diff changeset
342 if (ht->ht_filled < HT_INIT_SIZE - 1
73354c21f1e4 updated for version 7.0066
vimboss
parents: 154
diff changeset
343 && ht->ht_array == ht->ht_smallarray)
73354c21f1e4 updated for version 7.0066
vimboss
parents: 154
diff changeset
344 return OK;
120
34423a71d203 updated for version 7.0042
vimboss
parents:
diff changeset
345
237
73354c21f1e4 updated for version 7.0066
vimboss
parents: 154
diff changeset
346 /*
73354c21f1e4 updated for version 7.0066
vimboss
parents: 154
diff changeset
347 * Grow or refill the array when it's more than 2/3 full (including
73354c21f1e4 updated for version 7.0066
vimboss
parents: 154
diff changeset
348 * removed items, so that they get cleaned up).
73354c21f1e4 updated for version 7.0066
vimboss
parents: 154
diff changeset
349 * Shrink the array when it's less than 1/5 full. When growing it is
73354c21f1e4 updated for version 7.0066
vimboss
parents: 154
diff changeset
350 * at least 1/4 full (avoids repeated grow-shrink operations)
73354c21f1e4 updated for version 7.0066
vimboss
parents: 154
diff changeset
351 */
73354c21f1e4 updated for version 7.0066
vimboss
parents: 154
diff changeset
352 oldsize = ht->ht_mask + 1;
73354c21f1e4 updated for version 7.0066
vimboss
parents: 154
diff changeset
353 if (ht->ht_filled * 3 < oldsize * 2 && ht->ht_used > oldsize / 5)
73354c21f1e4 updated for version 7.0066
vimboss
parents: 154
diff changeset
354 return OK;
120
34423a71d203 updated for version 7.0042
vimboss
parents:
diff changeset
355
237
73354c21f1e4 updated for version 7.0066
vimboss
parents: 154
diff changeset
356 if (ht->ht_used > 1000)
73354c21f1e4 updated for version 7.0066
vimboss
parents: 154
diff changeset
357 minsize = ht->ht_used * 2; /* it's big, don't make too much room */
73354c21f1e4 updated for version 7.0066
vimboss
parents: 154
diff changeset
358 else
73354c21f1e4 updated for version 7.0066
vimboss
parents: 154
diff changeset
359 minsize = ht->ht_used * 4; /* make plenty of room */
73354c21f1e4 updated for version 7.0066
vimboss
parents: 154
diff changeset
360 }
120
34423a71d203 updated for version 7.0042
vimboss
parents:
diff changeset
361 else
237
73354c21f1e4 updated for version 7.0066
vimboss
parents: 154
diff changeset
362 {
73354c21f1e4 updated for version 7.0066
vimboss
parents: 154
diff changeset
363 /* Use specified size. */
242
a711f7a6852d updated for version 7.0067
vimboss
parents: 237
diff changeset
364 if ((long_u)minitems < ht->ht_used) /* just in case... */
237
73354c21f1e4 updated for version 7.0066
vimboss
parents: 154
diff changeset
365 minitems = ht->ht_used;
73354c21f1e4 updated for version 7.0066
vimboss
parents: 154
diff changeset
366 minsize = minitems * 3 / 2; /* array is up to 2/3 full */
73354c21f1e4 updated for version 7.0066
vimboss
parents: 154
diff changeset
367 }
73354c21f1e4 updated for version 7.0066
vimboss
parents: 154
diff changeset
368
120
34423a71d203 updated for version 7.0042
vimboss
parents:
diff changeset
369 newsize = HT_INIT_SIZE;
34423a71d203 updated for version 7.0042
vimboss
parents:
diff changeset
370 while (newsize < minsize)
34423a71d203 updated for version 7.0042
vimboss
parents:
diff changeset
371 {
34423a71d203 updated for version 7.0042
vimboss
parents:
diff changeset
372 newsize <<= 1; /* make sure it's always a power of 2 */
34423a71d203 updated for version 7.0042
vimboss
parents:
diff changeset
373 if (newsize == 0)
34423a71d203 updated for version 7.0042
vimboss
parents:
diff changeset
374 return FAIL; /* overflow */
34423a71d203 updated for version 7.0042
vimboss
parents:
diff changeset
375 }
34423a71d203 updated for version 7.0042
vimboss
parents:
diff changeset
376
34423a71d203 updated for version 7.0042
vimboss
parents:
diff changeset
377 if (newsize == HT_INIT_SIZE)
34423a71d203 updated for version 7.0042
vimboss
parents:
diff changeset
378 {
34423a71d203 updated for version 7.0042
vimboss
parents:
diff changeset
379 /* Use the small array inside the hashdict structure. */
34423a71d203 updated for version 7.0042
vimboss
parents:
diff changeset
380 newarray = ht->ht_smallarray;
34423a71d203 updated for version 7.0042
vimboss
parents:
diff changeset
381 if (ht->ht_array == newarray)
34423a71d203 updated for version 7.0042
vimboss
parents:
diff changeset
382 {
34423a71d203 updated for version 7.0042
vimboss
parents:
diff changeset
383 /* Moving from ht_smallarray to ht_smallarray! Happens when there
34423a71d203 updated for version 7.0042
vimboss
parents:
diff changeset
384 * are many removed items. Copy the items to be able to clean up
34423a71d203 updated for version 7.0042
vimboss
parents:
diff changeset
385 * removed items. */
34423a71d203 updated for version 7.0042
vimboss
parents:
diff changeset
386 mch_memmove(temparray, newarray, sizeof(temparray));
34423a71d203 updated for version 7.0042
vimboss
parents:
diff changeset
387 oldarray = temparray;
34423a71d203 updated for version 7.0042
vimboss
parents:
diff changeset
388 }
34423a71d203 updated for version 7.0042
vimboss
parents:
diff changeset
389 else
34423a71d203 updated for version 7.0042
vimboss
parents:
diff changeset
390 oldarray = ht->ht_array;
34423a71d203 updated for version 7.0042
vimboss
parents:
diff changeset
391 }
34423a71d203 updated for version 7.0042
vimboss
parents:
diff changeset
392 else
34423a71d203 updated for version 7.0042
vimboss
parents:
diff changeset
393 {
34423a71d203 updated for version 7.0042
vimboss
parents:
diff changeset
394 /* Allocate an array. */
140
8ecb0db93e9a updated for version 7.0045
vimboss
parents: 135
diff changeset
395 newarray = (hashitem_T *)alloc((unsigned)
8ecb0db93e9a updated for version 7.0045
vimboss
parents: 135
diff changeset
396 (sizeof(hashitem_T) * newsize));
120
34423a71d203 updated for version 7.0042
vimboss
parents:
diff changeset
397 if (newarray == NULL)
34423a71d203 updated for version 7.0042
vimboss
parents:
diff changeset
398 {
34423a71d203 updated for version 7.0042
vimboss
parents:
diff changeset
399 /* Out of memory. When there are NULL items still return OK.
34423a71d203 updated for version 7.0042
vimboss
parents:
diff changeset
400 * Otherwise set ht_error, because lookup may result in a hang if
34423a71d203 updated for version 7.0042
vimboss
parents:
diff changeset
401 * we add another item. */
34423a71d203 updated for version 7.0042
vimboss
parents:
diff changeset
402 if (ht->ht_filled < ht->ht_mask)
34423a71d203 updated for version 7.0042
vimboss
parents:
diff changeset
403 return OK;
34423a71d203 updated for version 7.0042
vimboss
parents:
diff changeset
404 ht->ht_error = TRUE;
34423a71d203 updated for version 7.0042
vimboss
parents:
diff changeset
405 return FAIL;
34423a71d203 updated for version 7.0042
vimboss
parents:
diff changeset
406 }
34423a71d203 updated for version 7.0042
vimboss
parents:
diff changeset
407 oldarray = ht->ht_array;
34423a71d203 updated for version 7.0042
vimboss
parents:
diff changeset
408 }
135
b5fc81a825a1 updated for version 7.0044
vimboss
parents: 123
diff changeset
409 vim_memset(newarray, 0, (size_t)(sizeof(hashitem_T) * newsize));
120
34423a71d203 updated for version 7.0042
vimboss
parents:
diff changeset
410
34423a71d203 updated for version 7.0042
vimboss
parents:
diff changeset
411 /*
34423a71d203 updated for version 7.0042
vimboss
parents:
diff changeset
412 * Move all the items from the old array to the new one, placing them in
34423a71d203 updated for version 7.0042
vimboss
parents:
diff changeset
413 * the right spot. The new array won't have any removed items, thus this
34423a71d203 updated for version 7.0042
vimboss
parents:
diff changeset
414 * is also a cleanup action.
34423a71d203 updated for version 7.0042
vimboss
parents:
diff changeset
415 */
34423a71d203 updated for version 7.0042
vimboss
parents:
diff changeset
416 newmask = newsize - 1;
34423a71d203 updated for version 7.0042
vimboss
parents:
diff changeset
417 todo = ht->ht_used;
34423a71d203 updated for version 7.0042
vimboss
parents:
diff changeset
418 for (olditem = oldarray; todo > 0; ++olditem)
154
1a145815483e updated for version 7.0047
vimboss
parents: 140
diff changeset
419 if (!HASHITEM_EMPTY(olditem))
120
34423a71d203 updated for version 7.0042
vimboss
parents:
diff changeset
420 {
34423a71d203 updated for version 7.0042
vimboss
parents:
diff changeset
421 /*
34423a71d203 updated for version 7.0042
vimboss
parents:
diff changeset
422 * The algorithm to find the spot to add the item is identical to
34423a71d203 updated for version 7.0042
vimboss
parents:
diff changeset
423 * the algorithm to find an item in hash_lookup(). But we only
34423a71d203 updated for version 7.0042
vimboss
parents:
diff changeset
424 * need to search for a NULL key, thus it's simpler.
34423a71d203 updated for version 7.0042
vimboss
parents:
diff changeset
425 */
34423a71d203 updated for version 7.0042
vimboss
parents:
diff changeset
426 newi = olditem->hi_hash & newmask;
34423a71d203 updated for version 7.0042
vimboss
parents:
diff changeset
427 newitem = &newarray[newi];
34423a71d203 updated for version 7.0042
vimboss
parents:
diff changeset
428
34423a71d203 updated for version 7.0042
vimboss
parents:
diff changeset
429 if (newitem->hi_key != NULL)
34423a71d203 updated for version 7.0042
vimboss
parents:
diff changeset
430 for (perturb = olditem->hi_hash; ; perturb >>= PERTURB_SHIFT)
34423a71d203 updated for version 7.0042
vimboss
parents:
diff changeset
431 {
34423a71d203 updated for version 7.0042
vimboss
parents:
diff changeset
432 newi = (newi << 2) + newi + perturb + 1;
34423a71d203 updated for version 7.0042
vimboss
parents:
diff changeset
433 newitem = &newarray[newi & newmask];
34423a71d203 updated for version 7.0042
vimboss
parents:
diff changeset
434 if (newitem->hi_key == NULL)
34423a71d203 updated for version 7.0042
vimboss
parents:
diff changeset
435 break;
34423a71d203 updated for version 7.0042
vimboss
parents:
diff changeset
436 }
34423a71d203 updated for version 7.0042
vimboss
parents:
diff changeset
437 *newitem = *olditem;
34423a71d203 updated for version 7.0042
vimboss
parents:
diff changeset
438 --todo;
34423a71d203 updated for version 7.0042
vimboss
parents:
diff changeset
439 }
34423a71d203 updated for version 7.0042
vimboss
parents:
diff changeset
440
34423a71d203 updated for version 7.0042
vimboss
parents:
diff changeset
441 if (ht->ht_array != ht->ht_smallarray)
34423a71d203 updated for version 7.0042
vimboss
parents:
diff changeset
442 vim_free(ht->ht_array);
34423a71d203 updated for version 7.0042
vimboss
parents:
diff changeset
443 ht->ht_array = newarray;
34423a71d203 updated for version 7.0042
vimboss
parents:
diff changeset
444 ht->ht_mask = newmask;
34423a71d203 updated for version 7.0042
vimboss
parents:
diff changeset
445 ht->ht_filled = ht->ht_used;
34423a71d203 updated for version 7.0042
vimboss
parents:
diff changeset
446 ht->ht_error = FALSE;
34423a71d203 updated for version 7.0042
vimboss
parents:
diff changeset
447
34423a71d203 updated for version 7.0042
vimboss
parents:
diff changeset
448 return OK;
34423a71d203 updated for version 7.0042
vimboss
parents:
diff changeset
449 }
34423a71d203 updated for version 7.0042
vimboss
parents:
diff changeset
450
34423a71d203 updated for version 7.0042
vimboss
parents:
diff changeset
451 /*
242
a711f7a6852d updated for version 7.0067
vimboss
parents: 237
diff changeset
452 * Get the hash number for a key.
a711f7a6852d updated for version 7.0067
vimboss
parents: 237
diff changeset
453 * If you think you know a better hash function: Compile with HT_DEBUG set and
a711f7a6852d updated for version 7.0067
vimboss
parents: 237
diff changeset
454 * run a script that uses hashtables a lot. Vim will then print statistics
a711f7a6852d updated for version 7.0067
vimboss
parents: 237
diff changeset
455 * when exiting. Try that with the current hash algorithm and yours. The
a711f7a6852d updated for version 7.0067
vimboss
parents: 237
diff changeset
456 * lower the percentage the better.
120
34423a71d203 updated for version 7.0042
vimboss
parents:
diff changeset
457 */
135
b5fc81a825a1 updated for version 7.0044
vimboss
parents: 123
diff changeset
458 hash_T
120
34423a71d203 updated for version 7.0042
vimboss
parents:
diff changeset
459 hash_hash(key)
34423a71d203 updated for version 7.0042
vimboss
parents:
diff changeset
460 char_u *key;
34423a71d203 updated for version 7.0042
vimboss
parents:
diff changeset
461 {
242
a711f7a6852d updated for version 7.0067
vimboss
parents: 237
diff changeset
462 hash_T hash;
a711f7a6852d updated for version 7.0067
vimboss
parents: 237
diff changeset
463 char_u *p;
a711f7a6852d updated for version 7.0067
vimboss
parents: 237
diff changeset
464
a711f7a6852d updated for version 7.0067
vimboss
parents: 237
diff changeset
465 if ((hash = *key) == 0)
a711f7a6852d updated for version 7.0067
vimboss
parents: 237
diff changeset
466 return (hash_T)0; /* Empty keys are not allowed, but we don't
a711f7a6852d updated for version 7.0067
vimboss
parents: 237
diff changeset
467 want to crash if we get one. */
a711f7a6852d updated for version 7.0067
vimboss
parents: 237
diff changeset
468 p = key + 1;
a711f7a6852d updated for version 7.0067
vimboss
parents: 237
diff changeset
469
a711f7a6852d updated for version 7.0067
vimboss
parents: 237
diff changeset
470 #if 0
a711f7a6852d updated for version 7.0067
vimboss
parents: 237
diff changeset
471 /* ElfHash algorithm, which is supposed to have an even distribution.
a711f7a6852d updated for version 7.0067
vimboss
parents: 237
diff changeset
472 * Suggested by Charles Campbell. */
135
b5fc81a825a1 updated for version 7.0044
vimboss
parents: 123
diff changeset
473 hash_T g;
120
34423a71d203 updated for version 7.0042
vimboss
parents:
diff changeset
474
34423a71d203 updated for version 7.0042
vimboss
parents:
diff changeset
475 while (*p != NUL)
34423a71d203 updated for version 7.0042
vimboss
parents:
diff changeset
476 {
34423a71d203 updated for version 7.0042
vimboss
parents:
diff changeset
477 hash = (hash << 4) + *p++; /* clear low 4 bits of hash, add char */
34423a71d203 updated for version 7.0042
vimboss
parents:
diff changeset
478 g = hash & 0xf0000000L; /* g has high 4 bits of hash only */
34423a71d203 updated for version 7.0042
vimboss
parents:
diff changeset
479 if (g != 0)
34423a71d203 updated for version 7.0042
vimboss
parents:
diff changeset
480 hash ^= g >> 24; /* xor g's high 4 bits into hash */
34423a71d203 updated for version 7.0042
vimboss
parents:
diff changeset
481 }
242
a711f7a6852d updated for version 7.0067
vimboss
parents: 237
diff changeset
482 #else
a711f7a6852d updated for version 7.0067
vimboss
parents: 237
diff changeset
483
a711f7a6852d updated for version 7.0067
vimboss
parents: 237
diff changeset
484 /* A simplistic algorithm that appears to do very well.
a711f7a6852d updated for version 7.0067
vimboss
parents: 237
diff changeset
485 * Suggested by George Reilly. */
a711f7a6852d updated for version 7.0067
vimboss
parents: 237
diff changeset
486 while (*p != NUL)
a711f7a6852d updated for version 7.0067
vimboss
parents: 237
diff changeset
487 hash = hash * 101 + *p++;
a711f7a6852d updated for version 7.0067
vimboss
parents: 237
diff changeset
488 #endif
120
34423a71d203 updated for version 7.0042
vimboss
parents:
diff changeset
489
34423a71d203 updated for version 7.0042
vimboss
parents:
diff changeset
490 return hash;
34423a71d203 updated for version 7.0042
vimboss
parents:
diff changeset
491 }
34423a71d203 updated for version 7.0042
vimboss
parents:
diff changeset
492
34423a71d203 updated for version 7.0042
vimboss
parents:
diff changeset
493 #endif