The skip list for the cljs timers has a bug which is readily apparent: a loop without a recur:
(let [x (skip-list-node k v (make-array new-level))]
(loop [i 0]
(when (<= i level)
(let [links (.-forward (aget update i))]
(aset (.-forward x) i (aget links i))
(aset links i x)))))
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:
(ceilingEntry [coll k]
(loop [x header level level]
(if-not (neg? level)
(let [nx (loop [x x]
(let [x' (when (< level (alength (.-forward x)))
(aget (.-forward x) level))]
(when-not (nil? x')
(if (>= (.-key x') k)
(if-not (nil? nx)
(recur nx (dec level))
(recur x (dec level))))
(when-not (identical? x header)
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.