• Kirill Smelkov's avatar
    wcfs: xbtree: blib += RangedMap, RangedKeySet · b7c560c5
    Kirill Smelkov authored
    RangedMap is Key->VALUE map with adjacent keys mapped to the same value coalesced into Ranges.
    RangedKeySet is set of Keys with adjacent keys coalesced into Ranges.
    
    This data structures will be needed for ΔBtail.
    
    For now the implementation is simple since it keeps whole map in a
    linear slice because both RangedMap and RangedKeySet will be used in
    ΔBtail to keep something proportional to δ of a change, which is assumed
    to be small or medium most of the time.
    
    Some preliminary history:
    
    6ea5920a    X xbtree: Less copy/garbage in RangedKeySet ops
    3ecacd99    X need to keep Value first so that sizeof(set-entry) = sizeof(KeyRange)
    a5b9b19b    X SetRange draftly works
    ed2de0de    X Tests for Get
    3b7b69e6    X fixes for empty set/range
    6972f999    X xbtree/blib: RangedMap, RangedSet += IntersectsRange, Intersection
    b7c560c5
gen-rangemap 2.05 KB