SortedMultiDict losing elements

[dantaras]

s = SortedMultiDict{Int, Int}()           
insert!(s, 4, 41)
insert!(s, 3, 31)
insert!(s, 2, 21)
insert!(s, 2, 22)
insert!(s, 2, 23)
insert!(s, 2, 24)
insert!(s, 2, 25)
insert!(s, 2, 26)
insert!(s, 1, 11)
insert!(s, 1, 12)

st1 = insert!(s, 1, 13)
st2 = insert!(s, 1, 14)
st3 = insert!(s, 1, 15)
st4 = insert!(s, 1, 16)
st5 = insert!(s, 1, 17)
st6 = insert!(s, 1, 18)

delete!((s, st6))
delete!((s, st5))
delete!((s, st4))
delete!((s, st3))
delete!((s, st2))
delete!((s, st1))

@show s
insert!(s, 1, 19)
@show s

count = sum(1 for _ in s)
@assert count == length(s) "$count $(length(s))"

Running the above I get an assertion error:

ERROR: LoadError: AssertionError: 6 11

Some of the items in the SortedMultiDict are lost after the last insert.

[StephenVavasis]

Thanks for reporting this; I have confirmed the issue and am looking into it.

[StephenVavasis]

I have created a pull request that fixes the bug. It would be great if the OP could also test the new code on their actual application. The fix is in a branch called fix_sortedmultidict_bug

#775

Here is the explanation of the bug. In order to insert a data item as a leaf in a balanced 2-3 tree, it is necessary to adjust ancestors of the leaf by splitting ancestor nodes and reconnecting them to children. When I originally wrote the balanced tree substrate in 2013, for some inexplicable reason, I wrote insert! code that reconnects ancestors to children via comparison of keys rather than simply extending existing parent-child relations. Unfortunately, I missed an edge-case in the key comparisons, so that the previous code occasionally (and only for SortedMultiDict, not for the other two containers) reconnected ancestor nodes incorrectly. The new version of insert! navigates and reconnects ancestors without any key comparisons. So the new code for insert! is shorter, faster, and hopefully bug-free.

[dantaras]

I can confirm that the fix works. Thanks for the quick response!

[StephenVavasis]

I guess we can close this issue with the new release of 0.18.11. Should I make an announcement on discourse.julialang.org? I'm not sure how many users of SortedMultiDict are out there.

[oxinabox]

I do not think it needs an announcement