• Kirill Smelkov's avatar
    wcfs: xbtree: blib += PPTreeSubSet, ΔPPTreeSubSet · 27df5a3b
    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
pptreesubset_test.go 3.05 KB