Re: [17/17] check hash table insertions

[Alexandre Oliva <oliva@adacore.com>]

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

>> Am 29.12.2022 um 00:06 schrieb 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.

> Not sure what you mean

I meant existing code tests that dereferencing the returned slot pointer
yields NULL.  If we were to change the slot value during insert, we'd
have to adjust all callers.

> I think turning EMPTY (or DELETED) into
> DELETED at insert time would make the slot occupied for lookups and
> thus fix lookup during insert.

Yup.

> Of course insert during insert would
> still fail and possibly return the same slot again.

Yeah.

> So the most foolproof design would be a new INSERTING representation.

There's a glitch there: we can't expand with a pending insert.  So we
might need to count inserting nodes separately, or (ideally) be able to
check quickly that insertions have completed.

But then, inserting with a pending insert ought to be caught and
reported, because an insertion invalidates previously-returned slot
pointers, including that of the pending insert.  And that's how I got to
the proposed patch.

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

Record the slot with the pending insert, and at any subsequent operation
(that could be affected by the pending insert), check and report in case
the insertion was not completed.


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