-
Kirill Smelkov authored
This data structures will be used in ΔBtail to maintain sef of tracked BTree nodes, and to represent δ to such set. Some preliminary history: 78f2f88b X wcfs/xbtree: Fix treediff(a, ø) 5324547c X wcfs/xbtree: root(a) must stay in trackSet even after treediff(a,ø) f65f775b X wcfs/xbtree: treediff(ø, b) 66bc41ce X Fix bug in PPTreeSubSet.Difference - it was always leaving root node alive ddb28043 X rebuild: Don't return nil for empty ΔPPTreeSubSet - that leads to SIGSEGV a87cc6de X rebuild: tests: Don't recompute trackSet(keys1R2) several times Quoting PPTreeSubSet and ΔPPTreeSubSet documentation: ---- 8< ---- PPTreeSubSet represents PP-connected subset of tree node objects. It is PP(xleafs) where PP(node) maps node to {node, node.parent, node.parent,parent, ...} up to top root from where the node is reached. The nodes in the set are represented by their Oid. Usually PPTreeSubSet is built as PP(some-leafs), but in general the starting nodes are arbitrary. PPTreeSubSet can also have many root nodes, thus not necessarily representing a subset of a single tree. Usual set operations are provided: Union, Difference and Intersection. Nodes can be added into the set via AddPath. Path is reverse operation - it returns path to tree node given its oid. Every node in the set comes with .parent pointer. ~~~~ ΔPPTreeSubSet represents a change to PPTreeSubSet. It can be applied via PPTreeSubSet.ApplyΔ . The result B of applying δ to A is: B = A.xDifference(δ.Del).xUnion(δ.Add) (*) (*) NOTE δ.Del and δ.Add might have their leafs starting from non-leaf nodes in A/B. This situation arises when δ represents a change in path to particular node, but that node itself does not change, for example: c* c / \ / 41* 42 41 | | | \ 22 43 46 43 | | | 44 22 44 Here nodes {c, 41} are changed, node 42 is unlinked, and node 46 is added. Nodes 43 and 44 stay unchanged. δ.Del = c-42-43 | c-41-22 δ.Add = c-41-43 | c-41-46-22 The second component with "-22" builds from leaf, but the first component with "-43" builds from non-leaf node. ΔnchildNonLeafs = {43: +1} Only complete result of applying all - xfixup(-1, ΔnchildNonLeafs) - δ.Del, - δ.Add, and - xfixup(+1, ΔnchildNonLeafs) produces correctly PP-connected set.
27df5a3b