Mercurial > vim

comparison src/hashtab.c @ 31535:8b9771b827c1 v9.0.1100

Find changesets by keywords (author, files, the commit message), revision number or hash, or revset expression.
patch 9.0.1100: a hashtab with many removed items is not cleaned up Commit: https://github.com/vim/vim/commit/d0883faac6a74f777c9a6be9d035c59ee1c969c5 Author: Bram Moolenaar <Bram@vim.org> Date: Mon Dec 26 13:51:26 2022 +0000 patch 9.0.1100: a hashtab with many removed items is not cleaned up Problem: A hashtab with many removed items is not cleaned up. Solution: Re-hash a hashtab even when the size didn't change if too many items were removed.
author Bram Moolenaar <Bram@vim.org>
date Mon, 26 Dec 2022 15:00:04 +0100
parents a5959e14771a
children 04d9dff67d99
comparison
equal deleted inserted replaced
31534:47e108c175d2 31535:8b9771b827c1
348 hashitem_T temparray[HT_INIT_SIZE]; 348 hashitem_T temparray[HT_INIT_SIZE];
349 hashitem_T *oldarray, *newarray; 349 hashitem_T *oldarray, *newarray;
350 hashitem_T *olditem, *newitem; 350 hashitem_T *olditem, *newitem;
351 unsigned newi; 351 unsigned newi;
352 int todo; 352 int todo;
353 long_u oldsize, newsize; 353 long_u newsize;
354 long_u minsize; 354 long_u minsize;
355 long_u newmask; 355 long_u newmask;
356 hash_T perturb; 356 hash_T perturb;
357 357
358 // Don't resize a locked table. 358 // Don't resize a locked table.
364 emsg("hash_may_resize(): more used than filled"); 364 emsg("hash_may_resize(): more used than filled");
365 if (ht->ht_filled >= ht->ht_mask + 1) 365 if (ht->ht_filled >= ht->ht_mask + 1)
366 emsg("hash_may_resize(): table completely filled"); 366 emsg("hash_may_resize(): table completely filled");
367 #endif 367 #endif
368 368
369 long_u oldsize = ht->ht_mask + 1;
369 if (minitems == 0) 370 if (minitems == 0)
370 { 371 {
371 // Return quickly for small tables with at least two NULL items. NULL 372 // Return quickly for small tables with at least two NULL items. NULL
372 // items are required for the lookup to decide a key isn't there. 373 // items are required for the lookup to decide a key isn't there.
373 if (ht->ht_filled < HT_INIT_SIZE - 1 374 if (ht->ht_filled < HT_INIT_SIZE - 1
378 * Grow or refill the array when it's more than 2/3 full (including 379 * Grow or refill the array when it's more than 2/3 full (including
379 * removed items, so that they get cleaned up). 380 * removed items, so that they get cleaned up).
380 * Shrink the array when it's less than 1/5 full. When growing it is 381 * Shrink the array when it's less than 1/5 full. When growing it is
381 * at least 1/4 full (avoids repeated grow-shrink operations) 382 * at least 1/4 full (avoids repeated grow-shrink operations)
382 */ 383 */
383 oldsize = ht->ht_mask + 1;
384 if (ht->ht_filled * 3 < oldsize * 2 && ht->ht_used > oldsize / 5) 384 if (ht->ht_filled * 3 < oldsize * 2 && ht->ht_used > oldsize / 5)
385 return OK; 385 return OK;
386 386
387 if (ht->ht_used > 1000) 387 if (ht->ht_used > 1000)
388 minsize = ht->ht_used * 2; // it's big, don't make too much room 388 minsize = ht->ht_used * 2; // it's big, don't make too much room
420 else 420 else
421 oldarray = ht->ht_array; 421 oldarray = ht->ht_array;
422 CLEAR_FIELD(ht->ht_smallarray); 422 CLEAR_FIELD(ht->ht_smallarray);
423 } 423 }
424 424
425 else if (newsize == ht->ht_mask + 1) 425 else if (newsize == oldsize && ht->ht_filled * 3 < oldsize * 2)
426 { 426 {
427 // the hashtab is already at the desired size, bail out 427 // The hashtab is already at the desired size, and there are not too
428 // many removed items, bail out.
428 return OK; 429 return OK;
429 } 430 }
430 431
431 else 432 else
432 { 433 {