hitchhiker.tree — io.replikativ/hitchhiker-tree 0.1.9

Default tree implementation

The parts of the serialization system that seem like they're need hooks are:

• Must provide a function that takes a node, serializes it, and returns an addr

• Must be able to rollback writing an addr

• Whatever the addr it returns, it should cache its resolve in-mem somehow

• The serialize a node & rollback a node functions should accept a 'stats' object as well

• The 'stats' object must be convertible to a summary or whatever at the end

<-cache clj/s

(<-cache cache calc-fn)

<?-resolve clj/s macro

(<?-resolve n)

b-tree clj/s

(b-tree cfg & kvs)

backtrack-up-path-until clj/s

(backtrack-up-path-until path pred)

Given a path (starting with root and ending with an index), searches backwards, passing each pair of parent & index we just came from to the predicate function. When that function returns true, we return the path ending in the index for which it was true, or else we return the empty path

cache clj/s

(cache)

Config clj/s

data-node clj/s

(data-node children cfg)

Creates a new data node

data-node? clj/s

(data-node? node)

DataNode clj/s

delete clj/s

(delete {:keys [cfg] :as tree} key)

empty-sorted-map-by-compare clj/s

flush-children clj/s

(flush-children children backend session)

flush-children-without-root clj/s

(flush-children-without-root children backend session)

flush-tree clj/s

(flush-tree tree backend)

(flush-tree tree backend stats)

Given the tree, finds all dirty nodes, delivering addrs into them. Every dirty node also gets replaced with its TestingAddr. These form a GC cycle, have fun with the unmanaged memory port :)

flush-tree-without-root clj/s

(flush-tree-without-root tree backend)

(flush-tree-without-root tree backend stats root-node?)

Given the tree, finds all dirty nodes, delivering addrs into them. Does not flush root node, but returns it.

forward-iterator clj/s

(forward-iterator path start-key)

Takes the result of a search and returns an iterator going forward over the tree. Does lg(n) backtracking sometimes.

index-node clj/s

(index-node children op-buf cfg)

index-node-keys clj/s

(index-node-keys children)

Calculates the separating keys given the children of an index node

index-node? clj/s

(index-node? node)

IndexNode clj/s

insert clj/s

(insert {:keys [cfg] :as tree} k v)

lookup-fwd-iter clj/s

(lookup-fwd-iter tree key)

lookup-key clj/s

(lookup-key tree key)

(lookup-key tree key not-found)

Given a B-tree and a key, gets an iterator into the tree

lookup-path clj/s

(lookup-path tree key)

Given a B-tree and a key, gets a path into the tree

nth-of-set clj/s

(nth-of-set set index)

Like nth, but for sorted sets. O(n) in worst case, 0(1) when idx out of bounds.

resolved? clj/s

(resolved? node)

right-successor clj/s

(right-successor path)

Given a node on a path, find's that node's right successor node

Split clj/s