Welcome! Please see the About page for a little more info on how this works.

0 votes
in core.async by
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)
                         (recur x')))))]
          (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.

2 Answers

0 votes
_Comment made by: dpsutton_

{:current {:extra-deps {org.clojure/core.async {:mvn/version "0.4.500"}}}
  :patched {:extra-deps {:org.clojure/core.async
                         {:git/url "https://github.com/dpsutton/core.async"
                          :sha "e01932e6763cc155b86ef2098df1a49bee0e6d38"}}}}

0 votes
Reference: https://clojure.atlassian.net/browse/ASYNC-228 (reported by dpsutton)