Back
pushTail (clj)
(source)interface
(pushTail level parent tailnode)
Examples
clojure/core.rrb-vector
(ns clojure.core.rrb-vector.transients
(:require [clojure.core.rrb-vector.parameters :as p]
[clojure.core.rrb-vector.nodes :refer [ranges last-range
overflow?]])
(:import (clojure.core.rrb_vector.nodes NodeManager)
(clojure.core ArrayManager)
(java.util.concurrent.atomic AtomicReference)))
(definterface ITransientHelper
(editableRoot [^clojure.core.rrb_vector.nodes.NodeManager nm
^clojure.core.ArrayManager am
root])
(editableTail [^clojure.core.ArrayManager am
tail])
(ensureEditable [^clojure.core.rrb_vector.nodes.NodeManager nm
root])
(ensureEditable [^clojure.core.rrb_vector.nodes.NodeManager nm
^clojure.core.ArrayManager am
^java.util.concurrent.atomic.AtomicReference root-edit
current-node
^int shift])
(pushTail [^clojure.core.rrb_vector.nodes.NodeManager nm
^clojure.core.ArrayManager am
^int shift
^int cnt
^java.util.concurrent.atomic.AtomicReference root-edit
current-node
tail-node])
(popTail [^clojure.core.rrb_vector.nodes.NodeManager nm
^clojure.core.ArrayManager am
^int shift
^int cnt
^java.util.concurrent.atomic.AtomicReference root-edit
current-node])
(doAssoc [^clojure.core.rrb_vector.nodes.NodeManager nm
^clojure.core.ArrayManager am
^int shift
^java.util.concurrent.atomic.AtomicReference root-edit
current-node
^int i
val])
(newPath [^clojure.core.rrb_vector.nodes.NodeManager nm
^clojure.core.ArrayManager am
tail
^java.util.concurrent.atomic.AtomicReference edit
^int shift
current-node]))
;; Note 2: In the worst case, when the tree is nearly full,
;; calling overflow? here takes run time O(tree_depth^2) here.
;; That could be made O(tree_depth). One way would be to call
;; pushTail in hopes that it succeeds, but return some distinctive
;; value indicating a failure on the full condition, and create
;; the node via a .newPath call at most recent recursive pushTail
;; call that has an empty slot available.
(pushTail [this nm am shift cnt root-edit current-node tail-node]
(let [ret (.ensureEditable this nm am root-edit current-node shift)]
(if (.regular nm ret)
(do (loop [n ret shift shift]
(let [arr (.array nm n)
subidx (bit-and (bit-shift-right (dec cnt) shift) 0x1f)]
(if (== shift 5)
(aset ^objects arr subidx tail-node)
(let [child (aget ^objects arr subidx)]
(if (nil? child)
(aset ^objects arr subidx
(.newPath this nm am
(.array nm tail-node)
root-edit
(unchecked-subtract-int shift 5)
tail-node))
(let [editable-child
(.ensureEditable this nm am
root-edit
child
(unchecked-subtract-int
shift 5))]
(aset ^objects arr subidx editable-child)
(recur editable-child (- shift (int 5)))))))))
ret)
(let [arr (.array nm ret)
rngs (ranges nm ret)
li (unchecked-dec-int (aget rngs 32))
cret (if (== shift 5)
nil
(let [child (.ensureEditable this nm am
root-edit
(aget ^objects arr li)
(unchecked-subtract-int
shift 5))
ccnt (unchecked-add-int
(int (if (pos? li)
(unchecked-subtract-int
(aget rngs li)
(aget rngs (unchecked-dec-int li)))
(aget rngs 0)))
;; add 32 elems to account for the
;; new full tail we plan to add to
;; the subtree.
(int 32))]
;; See Note 2
(if-not (overflow? nm child
(unchecked-subtract-int shift 5)
ccnt)
(.pushTail this nm am
(unchecked-subtract-int shift 5)
ccnt
root-edit
child
tail-node))))]
(if cret
(do (aset ^objects arr li cret)
(aset rngs li (unchecked-add-int (aget rngs li) 32))
ret)
(do (when (>= li 31)
;; See Note 1
(let [msg (str "Assigning index " (inc li) " of vector"
" object array to become a node, when that"
" index should only be used for storing"
" range arrays.")
data {:shift shift, :cnd cnt,
:current-node current-node,
:tail-node tail-node, :rngs rngs, :li li,
:cret cret}]
(throw (ex-info msg data))))
(aset ^objects arr (inc li)
(.newPath this nm am
(.array nm tail-node)
root-edit
(unchecked-subtract-int shift 5)
tail-node))
(aset rngs (unchecked-inc-int li)
(unchecked-add-int (aget rngs li) 32))
(aset rngs 32 (unchecked-inc-int (aget rngs 32)))
ret))))))
clojure/core.rrb-vector
(ns clojure.core.rrb-vector.transients
(:require [clojure.core.rrb-vector.parameters :as p]
[clojure.core.rrb-vector.nodes :refer [ranges last-range
overflow?]])
(:import (clojure.core.rrb_vector.nodes NodeManager)
(clojure.core ArrayManager)
(java.util.concurrent.atomic AtomicReference)))
(definterface ITransientHelper
(editableRoot [^clojure.core.rrb_vector.nodes.NodeManager nm
^clojure.core.ArrayManager am
root])
(editableTail [^clojure.core.ArrayManager am
tail])
(ensureEditable [^clojure.core.rrb_vector.nodes.NodeManager nm
root])
(ensureEditable [^clojure.core.rrb_vector.nodes.NodeManager nm
^clojure.core.ArrayManager am
^java.util.concurrent.atomic.AtomicReference root-edit
current-node
^int shift])
(pushTail [^clojure.core.rrb_vector.nodes.NodeManager nm
^clojure.core.ArrayManager am
^int shift
^int cnt
^java.util.concurrent.atomic.AtomicReference root-edit
current-node
tail-node])
(popTail [^clojure.core.rrb_vector.nodes.NodeManager nm
^clojure.core.ArrayManager am
^int shift
^int cnt
^java.util.concurrent.atomic.AtomicReference root-edit
current-node])
(doAssoc [^clojure.core.rrb_vector.nodes.NodeManager nm
^clojure.core.ArrayManager am
^int shift
^java.util.concurrent.atomic.AtomicReference root-edit
current-node
^int i
val])
(newPath [^clojure.core.rrb_vector.nodes.NodeManager nm
^clojure.core.ArrayManager am
tail
^java.util.concurrent.atomic.AtomicReference edit
^int shift
current-node]))
;; Note 2: In the worst case, when the tree is nearly full,
;; calling overflow? here takes run time O(tree_depth^2) here.
;; That could be made O(tree_depth). One way would be to call
;; pushTail in hopes that it succeeds, but return some distinctive
;; value indicating a failure on the full condition, and create
;; the node via a .newPath call at most recent recursive pushTail
;; call that has an empty slot available.
(pushTail [this nm am shift cnt root-edit current-node tail-node]
(let [ret (.ensureEditable this nm am root-edit current-node shift)]
(if (.regular nm ret)
(do (loop [n ret shift shift]
(let [arr (.array nm n)
subidx (bit-and (bit-shift-right (dec cnt) shift) p/branch-mask)]
(if (== shift p/shift-increment)
(aset ^objects arr subidx tail-node)
(let [child (aget ^objects arr subidx)]
(if (nil? child)
(aset ^objects arr subidx
(.newPath this nm am
(.array nm tail-node)
root-edit
(unchecked-subtract-int shift p/shift-increment)
tail-node))
(let [editable-child
(.ensureEditable this nm am
root-edit
child
(unchecked-subtract-int
shift p/shift-increment))]
(aset ^objects arr subidx editable-child)
(recur editable-child (- shift (int p/shift-increment)))))))))
ret)
(let [arr (.array nm ret)
rngs (ranges nm ret)
li (unchecked-dec-int (aget rngs p/max-branches))
cret (if (== shift p/shift-increment)
nil
(let [child (.ensureEditable this nm am
root-edit
(aget ^objects arr li)
(unchecked-subtract-int
shift p/shift-increment))
ccnt (unchecked-add-int
(int (if (pos? li)
(unchecked-subtract-int
(aget rngs li)
(aget rngs (unchecked-dec-int li)))
(aget rngs 0)))
;; add p/max-branches elems to account for the
;; new full tail we plan to add to
;; the subtree.
(int p/max-branches))]
;; See Note 2
(if-not (overflow? nm child
(unchecked-subtract-int shift p/shift-increment)
ccnt)
(.pushTail this nm am
(unchecked-subtract-int shift p/shift-increment)
ccnt
root-edit
child
tail-node))))]
(if cret
(do (aset ^objects arr li cret)
(aset rngs li (unchecked-add-int (aget rngs li) p/max-branches))
ret)
(do (when (>= li p/max-branches-minus-1)
;; See Note 1
(let [msg (str "Assigning index " (inc li) " of vector"
" object array to become a node, when that"
" index should only be used for storing"
" range arrays.")
data {:shift shift, :cnd cnt,
:current-node current-node,
:tail-node tail-node, :rngs rngs, :li li,
:cret cret}]
(throw (ex-info msg data))))
(aset ^objects arr (inc li)
(.newPath this nm am
(.array nm tail-node)
root-edit
(unchecked-subtract-int shift p/shift-increment)
tail-node))
(aset rngs (unchecked-inc-int li)
(unchecked-add-int (aget rngs li) p/max-branches))
(aset rngs p/max-branches (unchecked-inc-int (aget rngs p/max-branches)))
ret))))))
datastax/fallout
(ns clojure.core.rrb-vector.transients
(:require [clojure.core.rrb-vector.nodes :refer [ranges last-range]])
(:import (clojure.core.rrb_vector.nodes NodeManager)
(clojure.core ArrayManager)
(java.util.concurrent.atomic AtomicReference)))
(definterface ITransientHelper
(editableRoot [^clojure.core.rrb_vector.nodes.NodeManager nm
^clojure.core.ArrayManager am
root])
(editableTail [^clojure.core.ArrayManager am
tail])
(ensureEditable [^clojure.core.rrb_vector.nodes.NodeManager nm
root])
(ensureEditable [^clojure.core.rrb_vector.nodes.NodeManager nm
^clojure.core.ArrayManager am
^java.util.concurrent.atomic.AtomicReference root-edit
current-node
^int shift])
(pushTail [^clojure.core.rrb_vector.nodes.NodeManager nm
^clojure.core.ArrayManager am
^int shift
^int cnt
^java.util.concurrent.atomic.AtomicReference root-edit
current-node
tail-node])
(popTail [^clojure.core.rrb_vector.nodes.NodeManager nm
^clojure.core.ArrayManager am
^int shift
^int cnt
^java.util.concurrent.atomic.AtomicReference root-edit
current-node])
(doAssoc [^clojure.core.rrb_vector.nodes.NodeManager nm
^clojure.core.ArrayManager am
^int shift
^java.util.concurrent.atomic.AtomicReference root-edit
current-node
^int i
val])
(newPath [^clojure.core.rrb_vector.nodes.NodeManager nm
^clojure.core.ArrayManager am
tail
^java.util.concurrent.atomic.AtomicReference edit
^int shift
current-node]))
(pushTail [this nm am shift cnt root-edit current-node tail-node]
(let [ret (.ensureEditable this nm am root-edit current-node shift)]
(if (.regular nm ret)
(do (loop [n ret shift shift]
(let [arr (.array nm n)
subidx (bit-and (bit-shift-right (dec cnt) shift) 0x1f)]
(if (== shift 5)
(aset ^objects arr subidx tail-node)
(let [child (aget ^objects arr subidx)]
(if (nil? child)
(aset ^objects arr subidx
(.newPath this nm am
(.array nm tail-node)
root-edit
(unchecked-subtract-int shift 5)
tail-node))
(let [editable-child
(.ensureEditable this nm am
root-edit
child
(unchecked-subtract-int
shift 5))]
(aset ^objects arr subidx editable-child)
(recur editable-child (- shift 5))))))))
ret)
(let [arr (.array nm ret)
rngs (ranges nm ret)
li (unchecked-dec-int (aget rngs 32))
cret (if (== shift 5)
nil
(let [child (.ensureEditable this nm am
root-edit
(aget ^objects arr li)
(unchecked-subtract-int
shift 5))
ccnt (if (pos? li)
(unchecked-subtract-int
(aget rngs li)
(aget rngs (unchecked-dec-int li)))
(aget rngs 0))]
(if-not (== ccnt (bit-shift-left 1 shift))
(.pushTail this nm am
(unchecked-subtract-int shift 5)
(unchecked-inc-int ccnt)
root-edit
child
tail-node))))]
(if cret
(do (aset ^objects arr li cret)
(aset rngs li (unchecked-add-int (aget rngs li) 32))
ret)
(do (aset ^objects arr (inc li)
(.newPath this nm am
(.array nm tail-node)
root-edit
(unchecked-subtract-int shift 5)
tail-node))
(aset rngs (unchecked-inc-int li)
(unchecked-add-int (aget rngs li) 32))
(aset rngs 32 (unchecked-inc-int (aget rngs 32)))
ret))))))