tree 00e91a0d5fd8550eb33cf972bfb3a3d482519bc3
parent 81dab9f25cb2381400c237fdea7030d5068f9a73
author Andrew Grieve <agrieve@google.com> 1750216089 -0400
committer GN LUCI <gn-scoped@luci-project-accounts.iam.gserviceaccount.com> 1750251335 -0700

Fix bug in Grow logic in HashTableBase

NodeLookup() returns only when a null slot is found, but if tombstones
accumulate, it can infinite loop due to no null slots existing.

This changes the hash table to track the number of tombstones, and grow
when the number of null entries is < 25%.

This bug does not affect any existing uses of PointerSet, since it
happens only for sets that alternate between add() and erase() (which
afaict, no existing uses do).

Change-Id: I846ae0468faa8084d84d0c042bfaf5a06995e4f6
Reviewed-on: https://gn-review.googlesource.com/c/gn/+/19160
Reviewed-by: David Turner <digit@google.com>
Commit-Queue: Andrew Grieve <agrieve@google.com>