Re: [17/17] check hash table insertions

[Richard Biener via Gcc-patches]

> Am 29.12.2022 um 00:06 schrieb Alexandre Oliva <ol...@adacore.com>:
> 
> On Dec 28, 2022, Richard Biener <richard.guent...@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.

Not sure what you mean - I think turning EMPTY (or DELETED) into DELETED at 
insert time would make the slot occupied for lookups and thus fix lookup during 
insert.  Of course insert during insert would still fail and possibly return 
the same slot again.  So the most foolproof design would be a new INSERTING 
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.

Yes, it’s true that this addresses all issues with just imposing constraints on 
API use.  But the I wondered how you catched the completion of the insertion?  
(I’ll have to
Dig into the patch to see)

Richard 

> 
> -- 
> 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>