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