| // Copyright 2014-2022 Google Inc. |
| // |
| // Licensed under the Apache License, Version 2.0 (the "License"); |
| // you may not use this file except in compliance with the License. |
| // You may obtain a copy of the License at |
| // |
| // http://www.apache.org/licenses/LICENSE-2.0 |
| // |
| // Unless required by applicable law or agreed to in writing, software |
| // distributed under the License is distributed on an "AS IS" BASIS, |
| // WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. |
| // See the License for the specific language governing permissions and |
| // limitations under the License. |
| |
| //go:build go1.18 |
| // +build go1.18 |
| |
| // In Go 1.18 and beyond, a BTreeG generic is created, and BTree is a specific |
| // instantiation of that generic for the Item interface, with a backwards- |
| // compatible API. Before go1.18, generics are not supported, |
| // and BTree is just an implementation based around the Item interface. |
| |
| // Package btree implements in-memory B-Trees of arbitrary degree. |
| // |
| // btree implements an in-memory B-Tree for use as an ordered data structure. |
| // It is not meant for persistent storage solutions. |
| // |
| // It has a flatter structure than an equivalent red-black or other binary tree, |
| // which in some cases yields better memory usage and/or performance. |
| // See some discussion on the matter here: |
| // http://google-opensource.blogspot.com/2013/01/c-containers-that-save-memory-and-time.html |
| // Note, though, that this project is in no way related to the C++ B-Tree |
| // implementation written about there. |
| // |
| // Within this tree, each node contains a slice of items and a (possibly nil) |
| // slice of children. For basic numeric values or raw structs, this can cause |
| // efficiency differences when compared to equivalent C++ template code that |
| // stores values in arrays within the node: |
| // * Due to the overhead of storing values as interfaces (each |
| // value needs to be stored as the value itself, then 2 words for the |
| // interface pointing to that value and its type), resulting in higher |
| // memory use. |
| // * Since interfaces can point to values anywhere in memory, values are |
| // most likely not stored in contiguous blocks, resulting in a higher |
| // number of cache misses. |
| // These issues don't tend to matter, though, when working with strings or other |
| // heap-allocated structures, since C++-equivalent structures also must store |
| // pointers and also distribute their values across the heap. |
| // |
| // This implementation is designed to be a drop-in replacement to gollrb.LLRB |
| // trees, (http://github.com/petar/gollrb), an excellent and probably the most |
| // widely used ordered tree implementation in the Go ecosystem currently. |
| // Its functions, therefore, exactly mirror those of |
| // llrb.LLRB where possible. Unlike gollrb, though, we currently don't |
| // support storing multiple equivalent values. |
| // |
| // There are two implementations; those suffixed with 'G' are generics, usable |
| // for any type, and require a passed-in "less" function to define their ordering. |
| // Those without this prefix are specific to the 'Item' interface, and use |
| // its 'Less' function for ordering. |
| package btree |
| |
| import ( |
| "fmt" |
| "io" |
| "sort" |
| "strings" |
| "sync" |
| ) |
| |
| // Item represents a single object in the tree. |
| type Item interface { |
| // Less tests whether the current item is less than the given argument. |
| // |
| // This must provide a strict weak ordering. |
| // If !a.Less(b) && !b.Less(a), we treat this to mean a == b (i.e. we can only |
| // hold one of either a or b in the tree). |
| Less(than Item) bool |
| } |
| |
| const ( |
| DefaultFreeListSize = 32 |
| ) |
| |
| // FreeListG represents a free list of btree nodes. By default each |
| // BTree has its own FreeList, but multiple BTrees can share the same |
| // FreeList, in particular when they're created with Clone. |
| // Two Btrees using the same freelist are safe for concurrent write access. |
| type FreeListG[T any] struct { |
| mu sync.Mutex |
| freelist []*node[T] |
| } |
| |
| // NewFreeListG creates a new free list. |
| // size is the maximum size of the returned free list. |
| func NewFreeListG[T any](size int) *FreeListG[T] { |
| return &FreeListG[T]{freelist: make([]*node[T], 0, size)} |
| } |
| |
| func (f *FreeListG[T]) newNode() (n *node[T]) { |
| f.mu.Lock() |
| index := len(f.freelist) - 1 |
| if index < 0 { |
| f.mu.Unlock() |
| return new(node[T]) |
| } |
| n = f.freelist[index] |
| f.freelist[index] = nil |
| f.freelist = f.freelist[:index] |
| f.mu.Unlock() |
| return |
| } |
| |
| func (f *FreeListG[T]) freeNode(n *node[T]) (out bool) { |
| f.mu.Lock() |
| if len(f.freelist) < cap(f.freelist) { |
| f.freelist = append(f.freelist, n) |
| out = true |
| } |
| f.mu.Unlock() |
| return |
| } |
| |
| // ItemIteratorG allows callers of {A/De}scend* to iterate in-order over portions of |
| // the tree. When this function returns false, iteration will stop and the |
| // associated Ascend* function will immediately return. |
| type ItemIteratorG[T any] func(item T) bool |
| |
| // Ordered represents the set of types for which the '<' operator work. |
| type Ordered interface { |
| ~int | ~int8 | ~int16 | ~int32 | ~int64 | ~uint | ~uint8 | ~uint16 | ~uint32 | ~uint64 | ~float32 | ~float64 | string |
| } |
| |
| // Less[T] returns a default LessFunc that uses the '<' operator for types that support it. |
| func Less[T Ordered]() LessFunc[T] { |
| return func(a, b T) bool { return a < b } |
| } |
| |
| // NewOrderedG creates a new B-Tree for ordered types. |
| func NewOrderedG[T Ordered](degree int) *BTreeG[T] { |
| return NewG[T](degree, Less[T]()) |
| } |
| |
| // NewG creates a new B-Tree with the given degree. |
| // |
| // NewG(2), for example, will create a 2-3-4 tree (each node contains 1-3 items |
| // and 2-4 children). |
| // |
| // The passed-in LessFunc determines how objects of type T are ordered. |
| func NewG[T any](degree int, less LessFunc[T]) *BTreeG[T] { |
| return NewWithFreeListG(degree, less, NewFreeListG[T](DefaultFreeListSize)) |
| } |
| |
| // NewWithFreeListG creates a new B-Tree that uses the given node free list. |
| func NewWithFreeListG[T any](degree int, less LessFunc[T], f *FreeListG[T]) *BTreeG[T] { |
| if degree <= 1 { |
| panic("bad degree") |
| } |
| return &BTreeG[T]{ |
| degree: degree, |
| cow: ©OnWriteContext[T]{freelist: f, less: less}, |
| } |
| } |
| |
| // items stores items in a node. |
| type items[T any] []T |
| |
| // insertAt inserts a value into the given index, pushing all subsequent values |
| // forward. |
| func (s *items[T]) insertAt(index int, item T) { |
| var zero T |
| *s = append(*s, zero) |
| if index < len(*s) { |
| copy((*s)[index+1:], (*s)[index:]) |
| } |
| (*s)[index] = item |
| } |
| |
| // removeAt removes a value at a given index, pulling all subsequent values |
| // back. |
| func (s *items[T]) removeAt(index int) T { |
| item := (*s)[index] |
| copy((*s)[index:], (*s)[index+1:]) |
| var zero T |
| (*s)[len(*s)-1] = zero |
| *s = (*s)[:len(*s)-1] |
| return item |
| } |
| |
| // pop removes and returns the last element in the list. |
| func (s *items[T]) pop() (out T) { |
| index := len(*s) - 1 |
| out = (*s)[index] |
| var zero T |
| (*s)[index] = zero |
| *s = (*s)[:index] |
| return |
| } |
| |
| // truncate truncates this instance at index so that it contains only the |
| // first index items. index must be less than or equal to length. |
| func (s *items[T]) truncate(index int) { |
| var toClear items[T] |
| *s, toClear = (*s)[:index], (*s)[index:] |
| var zero T |
| for i := 0; i < len(toClear); i++ { |
| toClear[i] = zero |
| } |
| } |
| |
| // find returns the index where the given item should be inserted into this |
| // list. 'found' is true if the item already exists in the list at the given |
| // index. |
| func (s items[T]) find(item T, less func(T, T) bool) (index int, found bool) { |
| i := sort.Search(len(s), func(i int) bool { |
| return less(item, s[i]) |
| }) |
| if i > 0 && !less(s[i-1], item) { |
| return i - 1, true |
| } |
| return i, false |
| } |
| |
| // node is an internal node in a tree. |
| // |
| // It must at all times maintain the invariant that either |
| // * len(children) == 0, len(items) unconstrained |
| // * len(children) == len(items) + 1 |
| type node[T any] struct { |
| items items[T] |
| children items[*node[T]] |
| cow *copyOnWriteContext[T] |
| } |
| |
| func (n *node[T]) mutableFor(cow *copyOnWriteContext[T]) *node[T] { |
| if n.cow == cow { |
| return n |
| } |
| out := cow.newNode() |
| if cap(out.items) >= len(n.items) { |
| out.items = out.items[:len(n.items)] |
| } else { |
| out.items = make(items[T], len(n.items), cap(n.items)) |
| } |
| copy(out.items, n.items) |
| // Copy children |
| if cap(out.children) >= len(n.children) { |
| out.children = out.children[:len(n.children)] |
| } else { |
| out.children = make(items[*node[T]], len(n.children), cap(n.children)) |
| } |
| copy(out.children, n.children) |
| return out |
| } |
| |
| func (n *node[T]) mutableChild(i int) *node[T] { |
| c := n.children[i].mutableFor(n.cow) |
| n.children[i] = c |
| return c |
| } |
| |
| // split splits the given node at the given index. The current node shrinks, |
| // and this function returns the item that existed at that index and a new node |
| // containing all items/children after it. |
| func (n *node[T]) split(i int) (T, *node[T]) { |
| item := n.items[i] |
| next := n.cow.newNode() |
| next.items = append(next.items, n.items[i+1:]...) |
| n.items.truncate(i) |
| if len(n.children) > 0 { |
| next.children = append(next.children, n.children[i+1:]...) |
| n.children.truncate(i + 1) |
| } |
| return item, next |
| } |
| |
| // maybeSplitChild checks if a child should be split, and if so splits it. |
| // Returns whether or not a split occurred. |
| func (n *node[T]) maybeSplitChild(i, maxItems int) bool { |
| if len(n.children[i].items) < maxItems { |
| return false |
| } |
| first := n.mutableChild(i) |
| item, second := first.split(maxItems / 2) |
| n.items.insertAt(i, item) |
| n.children.insertAt(i+1, second) |
| return true |
| } |
| |
| // insert inserts an item into the subtree rooted at this node, making sure |
| // no nodes in the subtree exceed maxItems items. Should an equivalent item be |
| // be found/replaced by insert, it will be returned. |
| func (n *node[T]) insert(item T, maxItems int) (_ T, _ bool) { |
| i, found := n.items.find(item, n.cow.less) |
| if found { |
| out := n.items[i] |
| n.items[i] = item |
| return out, true |
| } |
| if len(n.children) == 0 { |
| n.items.insertAt(i, item) |
| return |
| } |
| if n.maybeSplitChild(i, maxItems) { |
| inTree := n.items[i] |
| switch { |
| case n.cow.less(item, inTree): |
| // no change, we want first split node |
| case n.cow.less(inTree, item): |
| i++ // we want second split node |
| default: |
| out := n.items[i] |
| n.items[i] = item |
| return out, true |
| } |
| } |
| return n.mutableChild(i).insert(item, maxItems) |
| } |
| |
| // get finds the given key in the subtree and returns it. |
| func (n *node[T]) get(key T) (_ T, _ bool) { |
| i, found := n.items.find(key, n.cow.less) |
| if found { |
| return n.items[i], true |
| } else if len(n.children) > 0 { |
| return n.children[i].get(key) |
| } |
| return |
| } |
| |
| // min returns the first item in the subtree. |
| func min[T any](n *node[T]) (_ T, found bool) { |
| if n == nil { |
| return |
| } |
| for len(n.children) > 0 { |
| n = n.children[0] |
| } |
| if len(n.items) == 0 { |
| return |
| } |
| return n.items[0], true |
| } |
| |
| // max returns the last item in the subtree. |
| func max[T any](n *node[T]) (_ T, found bool) { |
| if n == nil { |
| return |
| } |
| for len(n.children) > 0 { |
| n = n.children[len(n.children)-1] |
| } |
| if len(n.items) == 0 { |
| return |
| } |
| return n.items[len(n.items)-1], true |
| } |
| |
| // toRemove details what item to remove in a node.remove call. |
| type toRemove int |
| |
| const ( |
| removeItem toRemove = iota // removes the given item |
| removeMin // removes smallest item in the subtree |
| removeMax // removes largest item in the subtree |
| ) |
| |
| // remove removes an item from the subtree rooted at this node. |
| func (n *node[T]) remove(item T, minItems int, typ toRemove) (_ T, _ bool) { |
| var i int |
| var found bool |
| switch typ { |
| case removeMax: |
| if len(n.children) == 0 { |
| return n.items.pop(), true |
| } |
| i = len(n.items) |
| case removeMin: |
| if len(n.children) == 0 { |
| return n.items.removeAt(0), true |
| } |
| i = 0 |
| case removeItem: |
| i, found = n.items.find(item, n.cow.less) |
| if len(n.children) == 0 { |
| if found { |
| return n.items.removeAt(i), true |
| } |
| return |
| } |
| default: |
| panic("invalid type") |
| } |
| // If we get to here, we have children. |
| if len(n.children[i].items) <= minItems { |
| return n.growChildAndRemove(i, item, minItems, typ) |
| } |
| child := n.mutableChild(i) |
| // Either we had enough items to begin with, or we've done some |
| // merging/stealing, because we've got enough now and we're ready to return |
| // stuff. |
| if found { |
| // The item exists at index 'i', and the child we've selected can give us a |
| // predecessor, since if we've gotten here it's got > minItems items in it. |
| out := n.items[i] |
| // We use our special-case 'remove' call with typ=maxItem to pull the |
| // predecessor of item i (the rightmost leaf of our immediate left child) |
| // and set it into where we pulled the item from. |
| var zero T |
| n.items[i], _ = child.remove(zero, minItems, removeMax) |
| return out, true |
| } |
| // Final recursive call. Once we're here, we know that the item isn't in this |
| // node and that the child is big enough to remove from. |
| return child.remove(item, minItems, typ) |
| } |
| |
| // growChildAndRemove grows child 'i' to make sure it's possible to remove an |
| // item from it while keeping it at minItems, then calls remove to actually |
| // remove it. |
| // |
| // Most documentation says we have to do two sets of special casing: |
| // 1) item is in this node |
| // 2) item is in child |
| // In both cases, we need to handle the two subcases: |
| // A) node has enough values that it can spare one |
| // B) node doesn't have enough values |
| // For the latter, we have to check: |
| // a) left sibling has node to spare |
| // b) right sibling has node to spare |
| // c) we must merge |
| // To simplify our code here, we handle cases #1 and #2 the same: |
| // If a node doesn't have enough items, we make sure it does (using a,b,c). |
| // We then simply redo our remove call, and the second time (regardless of |
| // whether we're in case 1 or 2), we'll have enough items and can guarantee |
| // that we hit case A. |
| func (n *node[T]) growChildAndRemove(i int, item T, minItems int, typ toRemove) (T, bool) { |
| if i > 0 && len(n.children[i-1].items) > minItems { |
| // Steal from left child |
| child := n.mutableChild(i) |
| stealFrom := n.mutableChild(i - 1) |
| stolenItem := stealFrom.items.pop() |
| child.items.insertAt(0, n.items[i-1]) |
| n.items[i-1] = stolenItem |
| if len(stealFrom.children) > 0 { |
| child.children.insertAt(0, stealFrom.children.pop()) |
| } |
| } else if i < len(n.items) && len(n.children[i+1].items) > minItems { |
| // steal from right child |
| child := n.mutableChild(i) |
| stealFrom := n.mutableChild(i + 1) |
| stolenItem := stealFrom.items.removeAt(0) |
| child.items = append(child.items, n.items[i]) |
| n.items[i] = stolenItem |
| if len(stealFrom.children) > 0 { |
| child.children = append(child.children, stealFrom.children.removeAt(0)) |
| } |
| } else { |
| if i >= len(n.items) { |
| i-- |
| } |
| child := n.mutableChild(i) |
| // merge with right child |
| mergeItem := n.items.removeAt(i) |
| mergeChild := n.children.removeAt(i + 1) |
| child.items = append(child.items, mergeItem) |
| child.items = append(child.items, mergeChild.items...) |
| child.children = append(child.children, mergeChild.children...) |
| n.cow.freeNode(mergeChild) |
| } |
| return n.remove(item, minItems, typ) |
| } |
| |
| type direction int |
| |
| const ( |
| descend = direction(-1) |
| ascend = direction(+1) |
| ) |
| |
| type optionalItem[T any] struct { |
| item T |
| valid bool |
| } |
| |
| func optional[T any](item T) optionalItem[T] { |
| return optionalItem[T]{item: item, valid: true} |
| } |
| func empty[T any]() optionalItem[T] { |
| return optionalItem[T]{} |
| } |
| |
| // iterate provides a simple method for iterating over elements in the tree. |
| // |
| // When ascending, the 'start' should be less than 'stop' and when descending, |
| // the 'start' should be greater than 'stop'. Setting 'includeStart' to true |
| // will force the iterator to include the first item when it equals 'start', |
| // thus creating a "greaterOrEqual" or "lessThanEqual" rather than just a |
| // "greaterThan" or "lessThan" queries. |
| func (n *node[T]) iterate(dir direction, start, stop optionalItem[T], includeStart bool, hit bool, iter ItemIteratorG[T]) (bool, bool) { |
| var ok, found bool |
| var index int |
| switch dir { |
| case ascend: |
| if start.valid { |
| index, _ = n.items.find(start.item, n.cow.less) |
| } |
| for i := index; i < len(n.items); i++ { |
| if len(n.children) > 0 { |
| if hit, ok = n.children[i].iterate(dir, start, stop, includeStart, hit, iter); !ok { |
| return hit, false |
| } |
| } |
| if !includeStart && !hit && start.valid && !n.cow.less(start.item, n.items[i]) { |
| hit = true |
| continue |
| } |
| hit = true |
| if stop.valid && !n.cow.less(n.items[i], stop.item) { |
| return hit, false |
| } |
| if !iter(n.items[i]) { |
| return hit, false |
| } |
| } |
| if len(n.children) > 0 { |
| if hit, ok = n.children[len(n.children)-1].iterate(dir, start, stop, includeStart, hit, iter); !ok { |
| return hit, false |
| } |
| } |
| case descend: |
| if start.valid { |
| index, found = n.items.find(start.item, n.cow.less) |
| if !found { |
| index = index - 1 |
| } |
| } else { |
| index = len(n.items) - 1 |
| } |
| for i := index; i >= 0; i-- { |
| if start.valid && !n.cow.less(n.items[i], start.item) { |
| if !includeStart || hit || n.cow.less(start.item, n.items[i]) { |
| continue |
| } |
| } |
| if len(n.children) > 0 { |
| if hit, ok = n.children[i+1].iterate(dir, start, stop, includeStart, hit, iter); !ok { |
| return hit, false |
| } |
| } |
| if stop.valid && !n.cow.less(stop.item, n.items[i]) { |
| return hit, false // continue |
| } |
| hit = true |
| if !iter(n.items[i]) { |
| return hit, false |
| } |
| } |
| if len(n.children) > 0 { |
| if hit, ok = n.children[0].iterate(dir, start, stop, includeStart, hit, iter); !ok { |
| return hit, false |
| } |
| } |
| } |
| return hit, true |
| } |
| |
| // print is used for testing/debugging purposes. |
| func (n *node[T]) print(w io.Writer, level int) { |
| fmt.Fprintf(w, "%sNODE:%v\n", strings.Repeat(" ", level), n.items) |
| for _, c := range n.children { |
| c.print(w, level+1) |
| } |
| } |
| |
| // BTreeG is a generic implementation of a B-Tree. |
| // |
| // BTreeG stores items of type T in an ordered structure, allowing easy insertion, |
| // removal, and iteration. |
| // |
| // Write operations are not safe for concurrent mutation by multiple |
| // goroutines, but Read operations are. |
| type BTreeG[T any] struct { |
| degree int |
| length int |
| root *node[T] |
| cow *copyOnWriteContext[T] |
| } |
| |
| // LessFunc[T] determines how to order a type 'T'. It should implement a strict |
| // ordering, and should return true if within that ordering, 'a' < 'b'. |
| type LessFunc[T any] func(a, b T) bool |
| |
| // copyOnWriteContext pointers determine node ownership... a tree with a write |
| // context equivalent to a node's write context is allowed to modify that node. |
| // A tree whose write context does not match a node's is not allowed to modify |
| // it, and must create a new, writable copy (IE: it's a Clone). |
| // |
| // When doing any write operation, we maintain the invariant that the current |
| // node's context is equal to the context of the tree that requested the write. |
| // We do this by, before we descend into any node, creating a copy with the |
| // correct context if the contexts don't match. |
| // |
| // Since the node we're currently visiting on any write has the requesting |
| // tree's context, that node is modifiable in place. Children of that node may |
| // not share context, but before we descend into them, we'll make a mutable |
| // copy. |
| type copyOnWriteContext[T any] struct { |
| freelist *FreeListG[T] |
| less LessFunc[T] |
| } |
| |
| // Clone clones the btree, lazily. Clone should not be called concurrently, |
| // but the original tree (t) and the new tree (t2) can be used concurrently |
| // once the Clone call completes. |
| // |
| // The internal tree structure of b is marked read-only and shared between t and |
| // t2. Writes to both t and t2 use copy-on-write logic, creating new nodes |
| // whenever one of b's original nodes would have been modified. Read operations |
| // should have no performance degredation. Write operations for both t and t2 |
| // will initially experience minor slow-downs caused by additional allocs and |
| // copies due to the aforementioned copy-on-write logic, but should converge to |
| // the original performance characteristics of the original tree. |
| func (t *BTreeG[T]) Clone() (t2 *BTreeG[T]) { |
| // Create two entirely new copy-on-write contexts. |
| // This operation effectively creates three trees: |
| // the original, shared nodes (old b.cow) |
| // the new b.cow nodes |
| // the new out.cow nodes |
| cow1, cow2 := *t.cow, *t.cow |
| out := *t |
| t.cow = &cow1 |
| out.cow = &cow2 |
| return &out |
| } |
| |
| // maxItems returns the max number of items to allow per node. |
| func (t *BTreeG[T]) maxItems() int { |
| return t.degree*2 - 1 |
| } |
| |
| // minItems returns the min number of items to allow per node (ignored for the |
| // root node). |
| func (t *BTreeG[T]) minItems() int { |
| return t.degree - 1 |
| } |
| |
| func (c *copyOnWriteContext[T]) newNode() (n *node[T]) { |
| n = c.freelist.newNode() |
| n.cow = c |
| return |
| } |
| |
| type freeType int |
| |
| const ( |
| ftFreelistFull freeType = iota // node was freed (available for GC, not stored in freelist) |
| ftStored // node was stored in the freelist for later use |
| ftNotOwned // node was ignored by COW, since it's owned by another one |
| ) |
| |
| // freeNode frees a node within a given COW context, if it's owned by that |
| // context. It returns what happened to the node (see freeType const |
| // documentation). |
| func (c *copyOnWriteContext[T]) freeNode(n *node[T]) freeType { |
| if n.cow == c { |
| // clear to allow GC |
| n.items.truncate(0) |
| n.children.truncate(0) |
| n.cow = nil |
| if c.freelist.freeNode(n) { |
| return ftStored |
| } else { |
| return ftFreelistFull |
| } |
| } else { |
| return ftNotOwned |
| } |
| } |
| |
| // ReplaceOrInsert adds the given item to the tree. If an item in the tree |
| // already equals the given one, it is removed from the tree and returned, |
| // and the second return value is true. Otherwise, (zeroValue, false) |
| // |
| // nil cannot be added to the tree (will panic). |
| func (t *BTreeG[T]) ReplaceOrInsert(item T) (_ T, _ bool) { |
| if t.root == nil { |
| t.root = t.cow.newNode() |
| t.root.items = append(t.root.items, item) |
| t.length++ |
| return |
| } else { |
| t.root = t.root.mutableFor(t.cow) |
| if len(t.root.items) >= t.maxItems() { |
| item2, second := t.root.split(t.maxItems() / 2) |
| oldroot := t.root |
| t.root = t.cow.newNode() |
| t.root.items = append(t.root.items, item2) |
| t.root.children = append(t.root.children, oldroot, second) |
| } |
| } |
| out, outb := t.root.insert(item, t.maxItems()) |
| if !outb { |
| t.length++ |
| } |
| return out, outb |
| } |
| |
| // Delete removes an item equal to the passed in item from the tree, returning |
| // it. If no such item exists, returns (zeroValue, false). |
| func (t *BTreeG[T]) Delete(item T) (T, bool) { |
| return t.deleteItem(item, removeItem) |
| } |
| |
| // DeleteMin removes the smallest item in the tree and returns it. |
| // If no such item exists, returns (zeroValue, false). |
| func (t *BTreeG[T]) DeleteMin() (T, bool) { |
| var zero T |
| return t.deleteItem(zero, removeMin) |
| } |
| |
| // DeleteMax removes the largest item in the tree and returns it. |
| // If no such item exists, returns (zeroValue, false). |
| func (t *BTreeG[T]) DeleteMax() (T, bool) { |
| var zero T |
| return t.deleteItem(zero, removeMax) |
| } |
| |
| func (t *BTreeG[T]) deleteItem(item T, typ toRemove) (_ T, _ bool) { |
| if t.root == nil || len(t.root.items) == 0 { |
| return |
| } |
| t.root = t.root.mutableFor(t.cow) |
| out, outb := t.root.remove(item, t.minItems(), typ) |
| if len(t.root.items) == 0 && len(t.root.children) > 0 { |
| oldroot := t.root |
| t.root = t.root.children[0] |
| t.cow.freeNode(oldroot) |
| } |
| if outb { |
| t.length-- |
| } |
| return out, outb |
| } |
| |
| // AscendRange calls the iterator for every value in the tree within the range |
| // [greaterOrEqual, lessThan), until iterator returns false. |
| func (t *BTreeG[T]) AscendRange(greaterOrEqual, lessThan T, iterator ItemIteratorG[T]) { |
| if t.root == nil { |
| return |
| } |
| t.root.iterate(ascend, optional[T](greaterOrEqual), optional[T](lessThan), true, false, iterator) |
| } |
| |
| // AscendLessThan calls the iterator for every value in the tree within the range |
| // [first, pivot), until iterator returns false. |
| func (t *BTreeG[T]) AscendLessThan(pivot T, iterator ItemIteratorG[T]) { |
| if t.root == nil { |
| return |
| } |
| t.root.iterate(ascend, empty[T](), optional(pivot), false, false, iterator) |
| } |
| |
| // AscendGreaterOrEqual calls the iterator for every value in the tree within |
| // the range [pivot, last], until iterator returns false. |
| func (t *BTreeG[T]) AscendGreaterOrEqual(pivot T, iterator ItemIteratorG[T]) { |
| if t.root == nil { |
| return |
| } |
| t.root.iterate(ascend, optional[T](pivot), empty[T](), true, false, iterator) |
| } |
| |
| // Ascend calls the iterator for every value in the tree within the range |
| // [first, last], until iterator returns false. |
| func (t *BTreeG[T]) Ascend(iterator ItemIteratorG[T]) { |
| if t.root == nil { |
| return |
| } |
| t.root.iterate(ascend, empty[T](), empty[T](), false, false, iterator) |
| } |
| |
| // DescendRange calls the iterator for every value in the tree within the range |
| // [lessOrEqual, greaterThan), until iterator returns false. |
| func (t *BTreeG[T]) DescendRange(lessOrEqual, greaterThan T, iterator ItemIteratorG[T]) { |
| if t.root == nil { |
| return |
| } |
| t.root.iterate(descend, optional[T](lessOrEqual), optional[T](greaterThan), true, false, iterator) |
| } |
| |
| // DescendLessOrEqual calls the iterator for every value in the tree within the range |
| // [pivot, first], until iterator returns false. |
| func (t *BTreeG[T]) DescendLessOrEqual(pivot T, iterator ItemIteratorG[T]) { |
| if t.root == nil { |
| return |
| } |
| t.root.iterate(descend, optional[T](pivot), empty[T](), true, false, iterator) |
| } |
| |
| // DescendGreaterThan calls the iterator for every value in the tree within |
| // the range [last, pivot), until iterator returns false. |
| func (t *BTreeG[T]) DescendGreaterThan(pivot T, iterator ItemIteratorG[T]) { |
| if t.root == nil { |
| return |
| } |
| t.root.iterate(descend, empty[T](), optional[T](pivot), false, false, iterator) |
| } |
| |
| // Descend calls the iterator for every value in the tree within the range |
| // [last, first], until iterator returns false. |
| func (t *BTreeG[T]) Descend(iterator ItemIteratorG[T]) { |
| if t.root == nil { |
| return |
| } |
| t.root.iterate(descend, empty[T](), empty[T](), false, false, iterator) |
| } |
| |
| // Get looks for the key item in the tree, returning it. It returns |
| // (zeroValue, false) if unable to find that item. |
| func (t *BTreeG[T]) Get(key T) (_ T, _ bool) { |
| if t.root == nil { |
| return |
| } |
| return t.root.get(key) |
| } |
| |
| // Min returns the smallest item in the tree, or (zeroValue, false) if the tree is empty. |
| func (t *BTreeG[T]) Min() (_ T, _ bool) { |
| return min(t.root) |
| } |
| |
| // Max returns the largest item in the tree, or (zeroValue, false) if the tree is empty. |
| func (t *BTreeG[T]) Max() (_ T, _ bool) { |
| return max(t.root) |
| } |
| |
| // Has returns true if the given key is in the tree. |
| func (t *BTreeG[T]) Has(key T) bool { |
| _, ok := t.Get(key) |
| return ok |
| } |
| |
| // Len returns the number of items currently in the tree. |
| func (t *BTreeG[T]) Len() int { |
| return t.length |
| } |
| |
| // Clear removes all items from the btree. If addNodesToFreelist is true, |
| // t's nodes are added to its freelist as part of this call, until the freelist |
| // is full. Otherwise, the root node is simply dereferenced and the subtree |
| // left to Go's normal GC processes. |
| // |
| // This can be much faster |
| // than calling Delete on all elements, because that requires finding/removing |
| // each element in the tree and updating the tree accordingly. It also is |
| // somewhat faster than creating a new tree to replace the old one, because |
| // nodes from the old tree are reclaimed into the freelist for use by the new |
| // one, instead of being lost to the garbage collector. |
| // |
| // This call takes: |
| // O(1): when addNodesToFreelist is false, this is a single operation. |
| // O(1): when the freelist is already full, it breaks out immediately |
| // O(freelist size): when the freelist is empty and the nodes are all owned |
| // by this tree, nodes are added to the freelist until full. |
| // O(tree size): when all nodes are owned by another tree, all nodes are |
| // iterated over looking for nodes to add to the freelist, and due to |
| // ownership, none are. |
| func (t *BTreeG[T]) Clear(addNodesToFreelist bool) { |
| if t.root != nil && addNodesToFreelist { |
| t.root.reset(t.cow) |
| } |
| t.root, t.length = nil, 0 |
| } |
| |
| // reset returns a subtree to the freelist. It breaks out immediately if the |
| // freelist is full, since the only benefit of iterating is to fill that |
| // freelist up. Returns true if parent reset call should continue. |
| func (n *node[T]) reset(c *copyOnWriteContext[T]) bool { |
| for _, child := range n.children { |
| if !child.reset(c) { |
| return false |
| } |
| } |
| return c.freeNode(n) != ftFreelistFull |
| } |
| |
| // Int implements the Item interface for integers. |
| type Int int |
| |
| // Less returns true if int(a) < int(b). |
| func (a Int) Less(b Item) bool { |
| return a < b.(Int) |
| } |
| |
| // BTree is an implementation of a B-Tree. |
| // |
| // BTree stores Item instances in an ordered structure, allowing easy insertion, |
| // removal, and iteration. |
| // |
| // Write operations are not safe for concurrent mutation by multiple |
| // goroutines, but Read operations are. |
| type BTree BTreeG[Item] |
| |
| var itemLess LessFunc[Item] = func(a, b Item) bool { |
| return a.Less(b) |
| } |
| |
| // New creates a new B-Tree with the given degree. |
| // |
| // New(2), for example, will create a 2-3-4 tree (each node contains 1-3 items |
| // and 2-4 children). |
| func New(degree int) *BTree { |
| return (*BTree)(NewG[Item](degree, itemLess)) |
| } |
| |
| // FreeList represents a free list of btree nodes. By default each |
| // BTree has its own FreeList, but multiple BTrees can share the same |
| // FreeList. |
| // Two Btrees using the same freelist are safe for concurrent write access. |
| type FreeList FreeListG[Item] |
| |
| // NewFreeList creates a new free list. |
| // size is the maximum size of the returned free list. |
| func NewFreeList(size int) *FreeList { |
| return (*FreeList)(NewFreeListG[Item](size)) |
| } |
| |
| // NewWithFreeList creates a new B-Tree that uses the given node free list. |
| func NewWithFreeList(degree int, f *FreeList) *BTree { |
| return (*BTree)(NewWithFreeListG[Item](degree, itemLess, (*FreeListG[Item])(f))) |
| } |
| |
| // ItemIterator allows callers of Ascend* to iterate in-order over portions of |
| // the tree. When this function returns false, iteration will stop and the |
| // associated Ascend* function will immediately return. |
| type ItemIterator ItemIteratorG[Item] |
| |
| // Clone clones the btree, lazily. Clone should not be called concurrently, |
| // but the original tree (t) and the new tree (t2) can be used concurrently |
| // once the Clone call completes. |
| // |
| // The internal tree structure of b is marked read-only and shared between t and |
| // t2. Writes to both t and t2 use copy-on-write logic, creating new nodes |
| // whenever one of b's original nodes would have been modified. Read operations |
| // should have no performance degredation. Write operations for both t and t2 |
| // will initially experience minor slow-downs caused by additional allocs and |
| // copies due to the aforementioned copy-on-write logic, but should converge to |
| // the original performance characteristics of the original tree. |
| func (t *BTree) Clone() (t2 *BTree) { |
| return (*BTree)((*BTreeG[Item])(t).Clone()) |
| } |
| |
| // Delete removes an item equal to the passed in item from the tree, returning |
| // it. If no such item exists, returns nil. |
| func (t *BTree) Delete(item Item) Item { |
| i, _ := (*BTreeG[Item])(t).Delete(item) |
| return i |
| } |
| |
| // DeleteMax removes the largest item in the tree and returns it. |
| // If no such item exists, returns nil. |
| func (t *BTree) DeleteMax() Item { |
| i, _ := (*BTreeG[Item])(t).DeleteMax() |
| return i |
| } |
| |
| // DeleteMin removes the smallest item in the tree and returns it. |
| // If no such item exists, returns nil. |
| func (t *BTree) DeleteMin() Item { |
| i, _ := (*BTreeG[Item])(t).DeleteMin() |
| return i |
| } |
| |
| // Get looks for the key item in the tree, returning it. It returns nil if |
| // unable to find that item. |
| func (t *BTree) Get(key Item) Item { |
| i, _ := (*BTreeG[Item])(t).Get(key) |
| return i |
| } |
| |
| // Max returns the largest item in the tree, or nil if the tree is empty. |
| func (t *BTree) Max() Item { |
| i, _ := (*BTreeG[Item])(t).Max() |
| return i |
| } |
| |
| // Min returns the smallest item in the tree, or nil if the tree is empty. |
| func (t *BTree) Min() Item { |
| i, _ := (*BTreeG[Item])(t).Min() |
| return i |
| } |
| |
| // ReplaceOrInsert adds the given item to the tree. If an item in the tree |
| // already equals the given one, it is removed from the tree and returned. |
| // Otherwise, nil is returned. |
| // |
| // nil cannot be added to the tree (will panic). |
| func (t *BTree) ReplaceOrInsert(item Item) Item { |
| i, _ := (*BTreeG[Item])(t).ReplaceOrInsert(item) |
| return i |
| } |
| |
| // AscendRange calls the iterator for every value in the tree within the range |
| // [greaterOrEqual, lessThan), until iterator returns false. |
| func (t *BTree) AscendRange(greaterOrEqual, lessThan Item, iterator ItemIterator) { |
| (*BTreeG[Item])(t).AscendRange(greaterOrEqual, lessThan, (ItemIteratorG[Item])(iterator)) |
| } |
| |
| // AscendLessThan calls the iterator for every value in the tree within the range |
| // [first, pivot), until iterator returns false. |
| func (t *BTree) AscendLessThan(pivot Item, iterator ItemIterator) { |
| (*BTreeG[Item])(t).AscendLessThan(pivot, (ItemIteratorG[Item])(iterator)) |
| } |
| |
| // AscendGreaterOrEqual calls the iterator for every value in the tree within |
| // the range [pivot, last], until iterator returns false. |
| func (t *BTree) AscendGreaterOrEqual(pivot Item, iterator ItemIterator) { |
| (*BTreeG[Item])(t).AscendGreaterOrEqual(pivot, (ItemIteratorG[Item])(iterator)) |
| } |
| |
| // Ascend calls the iterator for every value in the tree within the range |
| // [first, last], until iterator returns false. |
| func (t *BTree) Ascend(iterator ItemIterator) { |
| (*BTreeG[Item])(t).Ascend((ItemIteratorG[Item])(iterator)) |
| } |
| |
| // DescendRange calls the iterator for every value in the tree within the range |
| // [lessOrEqual, greaterThan), until iterator returns false. |
| func (t *BTree) DescendRange(lessOrEqual, greaterThan Item, iterator ItemIterator) { |
| (*BTreeG[Item])(t).DescendRange(lessOrEqual, greaterThan, (ItemIteratorG[Item])(iterator)) |
| } |
| |
| // DescendLessOrEqual calls the iterator for every value in the tree within the range |
| // [pivot, first], until iterator returns false. |
| func (t *BTree) DescendLessOrEqual(pivot Item, iterator ItemIterator) { |
| (*BTreeG[Item])(t).DescendLessOrEqual(pivot, (ItemIteratorG[Item])(iterator)) |
| } |
| |
| // DescendGreaterThan calls the iterator for every value in the tree within |
| // the range [last, pivot), until iterator returns false. |
| func (t *BTree) DescendGreaterThan(pivot Item, iterator ItemIterator) { |
| (*BTreeG[Item])(t).DescendGreaterThan(pivot, (ItemIteratorG[Item])(iterator)) |
| } |
| |
| // Descend calls the iterator for every value in the tree within the range |
| // [last, first], until iterator returns false. |
| func (t *BTree) Descend(iterator ItemIterator) { |
| (*BTreeG[Item])(t).Descend((ItemIteratorG[Item])(iterator)) |
| } |
| |
| // Len returns the number of items currently in the tree. |
| func (t *BTree) Len() int { |
| return (*BTreeG[Item])(t).Len() |
| } |
| |
| // Clear removes all items from the btree. If addNodesToFreelist is true, |
| // t's nodes are added to its freelist as part of this call, until the freelist |
| // is full. Otherwise, the root node is simply dereferenced and the subtree |
| // left to Go's normal GC processes. |
| // |
| // This can be much faster |
| // than calling Delete on all elements, because that requires finding/removing |
| // each element in the tree and updating the tree accordingly. It also is |
| // somewhat faster than creating a new tree to replace the old one, because |
| // nodes from the old tree are reclaimed into the freelist for use by the new |
| // one, instead of being lost to the garbage collector. |
| // |
| // This call takes: |
| // O(1): when addNodesToFreelist is false, this is a single operation. |
| // O(1): when the freelist is already full, it breaks out immediately |
| // O(freelist size): when the freelist is empty and the nodes are all owned |
| // by this tree, nodes are added to the freelist until full. |
| // O(tree size): when all nodes are owned by another tree, all nodes are |
| // iterated over looking for nodes to add to the freelist, and due to |
| // ownership, none are. |
| func (t *BTree) Clear(addNodesToFreelist bool) { |
| (*BTreeG[Item])(t).Clear(addNodesToFreelist) |
| } |