Re: [17/17] check hash table insertions

[Alexandre Oliva <oliva@adacore.com>]

On Dec 28, 2022, Richard Biener <richard.guenther@gmail.com> wrote:

> I wonder if on INSERT, pushing a DELETED marker would fix the dangling
> insert and search during delete problem be whether that would be
> better from a design point of view? (It of course requires a DELETED
> representation)

I'm undecided whether a design that rules out the possibility of not
having DELETED would qualify as unequivocally better.

Unless DELETED takes over the NULL representation, and something else is
used for EMPTY, every INSERT point would have to be adjusted to look for
the non-NULL DELETED representation.  That alone was enough for me to
rule out going down that path.

If we were to change the INSERT callers, it would make sense to
e.g. return a smart pointer that enforced the completion of the
insertion.  But that wouldn't fix lookups during insertion without
requiring a separate DELETED representation.

The one-pending-insertion strategy I implemented was the only one I
could find that addressed all of the pitfalls without significant
overhead.  It caught even one case that the mere element-counting had
failed to catch.

-- 
Alexandre Oliva, happy hacker                https://FSFLA.org/blogs/lxo/
   Free Software Activist                       GNU Toolchain Engineer
Disinformation flourishes because many people care deeply about injustice
but very few check the facts.  Ask me about <https://stallmansupport.org>