(CLJS) timeout timers skiplist is naive linked list

Description

The skip list for the cljs timers has a bug which is readily apparent: a loop without a recur:

This is from the `put` function. This ordinarily would be a terrible bug except that the link at 0 is just the naive linked-list link and it omits the "skips" of the skip list. A trivial patch fixes this to recur from the when form.

This has an implication to the ceilingEntry function however:

This function allows to "overshoot" the key you are searching for, presumably finding the "next" node. With a simple linked list this is fine and well-defined. However, with a skip list, this allows for drastic and non-deterministic overshooting depending on how big a skip is.

This needs to be patched to only overshoot when in the lowest linked list and not in any of the skip list links.

Environment

None

Activity

Show:
Alex Miller
March 31, 2020, 7:54 PM

Released in core.async 1.1.582

Daniel Sutton
June 17, 2019, 1:50 PM
Fixed

Assignee

David Nolen

Reporter

Daniel Sutton

Patch

Code