annotate src/hashtab.c @ 1585:4a317df16962 v7.1.298

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