attractivechaos / klib

A standalone and lightweight C library
http://attractivechaos.github.io/klib/
MIT License
4.18k stars 556 forks source link

Is wraparound check absent for deletion in khashl? #135

Closed sprgchma closed 4 years ago

sprgchma commented 4 years ago

You gave a link to deletion pseudocode in the blog post 'Deletion from hash tables without tombstones', in particular

if (j > i and (k <= i or k > j)) or
   (j < i and (k <= i and k > j)) (note 2)
       slot[i] := slot[j]
       i := j

But your implementation does not have a wraparound branch in the if condition

if (k <= i || k > j)
   keys[i] = keys[j], i = j;

Do i miss something?

attractivechaos commented 4 years ago

Thank you. I somewhat thought those two conditions are equivalent. I was wrong.