1// Copyright 2014 Google Inc. 2// 3// Licensed under the Apache License, Version 2.0 (the "License"); 4// you may not use this file except in compliance with the License. 5// You may obtain a copy of the License at 6// 7// http://www.apache.org/licenses/LICENSE-2.0 8// 9// Unless required by applicable law or agreed to in writing, software 10// distributed under the License is distributed on an "AS IS" BASIS, 11// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. 12// See the License for the specific language governing permissions and 13// limitations under the License. 14 15// Package btree implements in-memory B-Trees of arbitrary degree. 16// 17// btree implements an in-memory B-Tree for use as an ordered data structure. 18// It is not meant for persistent storage solutions. 19// 20// It has a flatter structure than an equivalent red-black or other binary tree, 21// which in some cases yields better memory usage and/or performance. 22// See some discussion on the matter here: 23// http://google-opensource.blogspot.com/2013/01/c-containers-that-save-memory-and-time.html 24// Note, though, that this project is in no way related to the C++ B-Tree 25// implementation written about there. 26// 27// Within this tree, each node contains a slice of items and a (possibly nil) 28// slice of children. For basic numeric values or raw structs, this can cause 29// efficiency differences when compared to equivalent C++ template code that 30// stores values in arrays within the node: 31// * Due to the overhead of storing values as interfaces (each 32// value needs to be stored as the value itself, then 2 words for the 33// interface pointing to that value and its type), resulting in higher 34// memory use. 35// * Since interfaces can point to values anywhere in memory, values are 36// most likely not stored in contiguous blocks, resulting in a higher 37// number of cache misses. 38// These issues don't tend to matter, though, when working with strings or other 39// heap-allocated structures, since C++-equivalent structures also must store 40// pointers and also distribute their values across the heap. 41// 42// This implementation is designed to be a drop-in replacement to gollrb.LLRB 43// trees, (http://github.com/petar/gollrb), an excellent and probably the most 44// widely used ordered tree implementation in the Go ecosystem currently. 45// Its functions, therefore, exactly mirror those of 46// llrb.LLRB where possible. Unlike gollrb, though, we currently don't 47// support storing multiple equivalent values. 48package btree 49 50import ( 51 "fmt" 52 "io" 53 "sort" 54 "strings" 55 "sync" 56) 57 58// Item represents a single object in the tree. 59type Item interface { 60 // Less tests whether the current item is less than the given argument. 61 // 62 // This must provide a strict weak ordering. 63 // If !a.Less(b) && !b.Less(a), we treat this to mean a == b (i.e. we can only 64 // hold one of either a or b in the tree). 65 Less(than Item) bool 66} 67 68const ( 69 DefaultFreeListSize = 32 70) 71 72var ( 73 nilItems = make(items, 16) 74 nilChildren = make(children, 16) 75) 76 77// FreeList represents a free list of btree nodes. By default each 78// BTree has its own FreeList, but multiple BTrees can share the same 79// FreeList. 80// Two Btrees using the same freelist are safe for concurrent write access. 81type FreeList struct { 82 mu sync.Mutex 83 freelist []*node 84} 85 86// NewFreeList creates a new free list. 87// size is the maximum size of the returned free list. 88func NewFreeList(size int) *FreeList { 89 return &FreeList{freelist: make([]*node, 0, size)} 90} 91 92func (f *FreeList) newNode() (n *node) { 93 f.mu.Lock() 94 index := len(f.freelist) - 1 95 if index < 0 { 96 f.mu.Unlock() 97 return new(node) 98 } 99 n = f.freelist[index] 100 f.freelist[index] = nil 101 f.freelist = f.freelist[:index] 102 f.mu.Unlock() 103 return 104} 105 106// freeNode adds the given node to the list, returning true if it was added 107// and false if it was discarded. 108func (f *FreeList) freeNode(n *node) (out bool) { 109 f.mu.Lock() 110 if len(f.freelist) < cap(f.freelist) { 111 f.freelist = append(f.freelist, n) 112 out = true 113 } 114 f.mu.Unlock() 115 return 116} 117 118// ItemIterator allows callers of Ascend* to iterate in-order over portions of 119// the tree. When this function returns false, iteration will stop and the 120// associated Ascend* function will immediately return. 121type ItemIterator func(i Item) bool 122 123// New creates a new B-Tree with the given degree. 124// 125// New(2), for example, will create a 2-3-4 tree (each node contains 1-3 items 126// and 2-4 children). 127func New(degree int) *BTree { 128 return NewWithFreeList(degree, NewFreeList(DefaultFreeListSize)) 129} 130 131// NewWithFreeList creates a new B-Tree that uses the given node free list. 132func NewWithFreeList(degree int, f *FreeList) *BTree { 133 if degree <= 1 { 134 panic("bad degree") 135 } 136 return &BTree{ 137 degree: degree, 138 cow: ©OnWriteContext{freelist: f}, 139 } 140} 141 142// items stores items in a node. 143type items []Item 144 145// insertAt inserts a value into the given index, pushing all subsequent values 146// forward. 147func (s *items) insertAt(index int, item Item) { 148 *s = append(*s, nil) 149 if index < len(*s) { 150 copy((*s)[index+1:], (*s)[index:]) 151 } 152 (*s)[index] = item 153} 154 155// removeAt removes a value at a given index, pulling all subsequent values 156// back. 157func (s *items) removeAt(index int) Item { 158 item := (*s)[index] 159 copy((*s)[index:], (*s)[index+1:]) 160 (*s)[len(*s)-1] = nil 161 *s = (*s)[:len(*s)-1] 162 return item 163} 164 165// pop removes and returns the last element in the list. 166func (s *items) pop() (out Item) { 167 index := len(*s) - 1 168 out = (*s)[index] 169 (*s)[index] = nil 170 *s = (*s)[:index] 171 return 172} 173 174// truncate truncates this instance at index so that it contains only the 175// first index items. index must be less than or equal to length. 176func (s *items) truncate(index int) { 177 var toClear items 178 *s, toClear = (*s)[:index], (*s)[index:] 179 for len(toClear) > 0 { 180 toClear = toClear[copy(toClear, nilItems):] 181 } 182} 183 184// find returns the index where the given item should be inserted into this 185// list. 'found' is true if the item already exists in the list at the given 186// index. 187func (s items) find(item Item) (index int, found bool) { 188 i := sort.Search(len(s), func(i int) bool { 189 return item.Less(s[i]) 190 }) 191 if i > 0 && !s[i-1].Less(item) { 192 return i - 1, true 193 } 194 return i, false 195} 196 197// children stores child nodes in a node. 198type children []*node 199 200// insertAt inserts a value into the given index, pushing all subsequent values 201// forward. 202func (s *children) insertAt(index int, n *node) { 203 *s = append(*s, nil) 204 if index < len(*s) { 205 copy((*s)[index+1:], (*s)[index:]) 206 } 207 (*s)[index] = n 208} 209 210// removeAt removes a value at a given index, pulling all subsequent values 211// back. 212func (s *children) removeAt(index int) *node { 213 n := (*s)[index] 214 copy((*s)[index:], (*s)[index+1:]) 215 (*s)[len(*s)-1] = nil 216 *s = (*s)[:len(*s)-1] 217 return n 218} 219 220// pop removes and returns the last element in the list. 221func (s *children) pop() (out *node) { 222 index := len(*s) - 1 223 out = (*s)[index] 224 (*s)[index] = nil 225 *s = (*s)[:index] 226 return 227} 228 229// truncate truncates this instance at index so that it contains only the 230// first index children. index must be less than or equal to length. 231func (s *children) truncate(index int) { 232 var toClear children 233 *s, toClear = (*s)[:index], (*s)[index:] 234 for len(toClear) > 0 { 235 toClear = toClear[copy(toClear, nilChildren):] 236 } 237} 238 239// node is an internal node in a tree. 240// 241// It must at all times maintain the invariant that either 242// * len(children) == 0, len(items) unconstrained 243// * len(children) == len(items) + 1 244type node struct { 245 items items 246 children children 247 cow *copyOnWriteContext 248} 249 250func (n *node) mutableFor(cow *copyOnWriteContext) *node { 251 if n.cow == cow { 252 return n 253 } 254 out := cow.newNode() 255 if cap(out.items) >= len(n.items) { 256 out.items = out.items[:len(n.items)] 257 } else { 258 out.items = make(items, len(n.items), cap(n.items)) 259 } 260 copy(out.items, n.items) 261 // Copy children 262 if cap(out.children) >= len(n.children) { 263 out.children = out.children[:len(n.children)] 264 } else { 265 out.children = make(children, len(n.children), cap(n.children)) 266 } 267 copy(out.children, n.children) 268 return out 269} 270 271func (n *node) mutableChild(i int) *node { 272 c := n.children[i].mutableFor(n.cow) 273 n.children[i] = c 274 return c 275} 276 277// split splits the given node at the given index. The current node shrinks, 278// and this function returns the item that existed at that index and a new node 279// containing all items/children after it. 280func (n *node) split(i int) (Item, *node) { 281 item := n.items[i] 282 next := n.cow.newNode() 283 next.items = append(next.items, n.items[i+1:]...) 284 n.items.truncate(i) 285 if len(n.children) > 0 { 286 next.children = append(next.children, n.children[i+1:]...) 287 n.children.truncate(i + 1) 288 } 289 return item, next 290} 291 292// maybeSplitChild checks if a child should be split, and if so splits it. 293// Returns whether or not a split occurred. 294func (n *node) maybeSplitChild(i, maxItems int) bool { 295 if len(n.children[i].items) < maxItems { 296 return false 297 } 298 first := n.mutableChild(i) 299 item, second := first.split(maxItems / 2) 300 n.items.insertAt(i, item) 301 n.children.insertAt(i+1, second) 302 return true 303} 304 305// insert inserts an item into the subtree rooted at this node, making sure 306// no nodes in the subtree exceed maxItems items. Should an equivalent item be 307// be found/replaced by insert, it will be returned. 308func (n *node) insert(item Item, maxItems int) Item { 309 i, found := n.items.find(item) 310 if found { 311 out := n.items[i] 312 n.items[i] = item 313 return out 314 } 315 if len(n.children) == 0 { 316 n.items.insertAt(i, item) 317 return nil 318 } 319 if n.maybeSplitChild(i, maxItems) { 320 inTree := n.items[i] 321 switch { 322 case item.Less(inTree): 323 // no change, we want first split node 324 case inTree.Less(item): 325 i++ // we want second split node 326 default: 327 out := n.items[i] 328 n.items[i] = item 329 return out 330 } 331 } 332 return n.mutableChild(i).insert(item, maxItems) 333} 334 335// get finds the given key in the subtree and returns it. 336func (n *node) get(key Item) Item { 337 i, found := n.items.find(key) 338 if found { 339 return n.items[i] 340 } else if len(n.children) > 0 { 341 return n.children[i].get(key) 342 } 343 return nil 344} 345 346// min returns the first item in the subtree. 347func min(n *node) Item { 348 if n == nil { 349 return nil 350 } 351 for len(n.children) > 0 { 352 n = n.children[0] 353 } 354 if len(n.items) == 0 { 355 return nil 356 } 357 return n.items[0] 358} 359 360// max returns the last item in the subtree. 361func max(n *node) Item { 362 if n == nil { 363 return nil 364 } 365 for len(n.children) > 0 { 366 n = n.children[len(n.children)-1] 367 } 368 if len(n.items) == 0 { 369 return nil 370 } 371 return n.items[len(n.items)-1] 372} 373 374// toRemove details what item to remove in a node.remove call. 375type toRemove int 376 377const ( 378 removeItem toRemove = iota // removes the given item 379 removeMin // removes smallest item in the subtree 380 removeMax // removes largest item in the subtree 381) 382 383// remove removes an item from the subtree rooted at this node. 384func (n *node) remove(item Item, minItems int, typ toRemove) Item { 385 var i int 386 var found bool 387 switch typ { 388 case removeMax: 389 if len(n.children) == 0 { 390 return n.items.pop() 391 } 392 i = len(n.items) 393 case removeMin: 394 if len(n.children) == 0 { 395 return n.items.removeAt(0) 396 } 397 i = 0 398 case removeItem: 399 i, found = n.items.find(item) 400 if len(n.children) == 0 { 401 if found { 402 return n.items.removeAt(i) 403 } 404 return nil 405 } 406 default: 407 panic("invalid type") 408 } 409 // If we get to here, we have children. 410 if len(n.children[i].items) <= minItems { 411 return n.growChildAndRemove(i, item, minItems, typ) 412 } 413 child := n.mutableChild(i) 414 // Either we had enough items to begin with, or we've done some 415 // merging/stealing, because we've got enough now and we're ready to return 416 // stuff. 417 if found { 418 // The item exists at index 'i', and the child we've selected can give us a 419 // predecessor, since if we've gotten here it's got > minItems items in it. 420 out := n.items[i] 421 // We use our special-case 'remove' call with typ=maxItem to pull the 422 // predecessor of item i (the rightmost leaf of our immediate left child) 423 // and set it into where we pulled the item from. 424 n.items[i] = child.remove(nil, minItems, removeMax) 425 return out 426 } 427 // Final recursive call. Once we're here, we know that the item isn't in this 428 // node and that the child is big enough to remove from. 429 return child.remove(item, minItems, typ) 430} 431 432// growChildAndRemove grows child 'i' to make sure it's possible to remove an 433// item from it while keeping it at minItems, then calls remove to actually 434// remove it. 435// 436// Most documentation says we have to do two sets of special casing: 437// 1) item is in this node 438// 2) item is in child 439// In both cases, we need to handle the two subcases: 440// A) node has enough values that it can spare one 441// B) node doesn't have enough values 442// For the latter, we have to check: 443// a) left sibling has node to spare 444// b) right sibling has node to spare 445// c) we must merge 446// To simplify our code here, we handle cases #1 and #2 the same: 447// If a node doesn't have enough items, we make sure it does (using a,b,c). 448// We then simply redo our remove call, and the second time (regardless of 449// whether we're in case 1 or 2), we'll have enough items and can guarantee 450// that we hit case A. 451func (n *node) growChildAndRemove(i int, item Item, minItems int, typ toRemove) Item { 452 if i > 0 && len(n.children[i-1].items) > minItems { 453 // Steal from left child 454 child := n.mutableChild(i) 455 stealFrom := n.mutableChild(i - 1) 456 stolenItem := stealFrom.items.pop() 457 child.items.insertAt(0, n.items[i-1]) 458 n.items[i-1] = stolenItem 459 if len(stealFrom.children) > 0 { 460 child.children.insertAt(0, stealFrom.children.pop()) 461 } 462 } else if i < len(n.items) && len(n.children[i+1].items) > minItems { 463 // steal from right child 464 child := n.mutableChild(i) 465 stealFrom := n.mutableChild(i + 1) 466 stolenItem := stealFrom.items.removeAt(0) 467 child.items = append(child.items, n.items[i]) 468 n.items[i] = stolenItem 469 if len(stealFrom.children) > 0 { 470 child.children = append(child.children, stealFrom.children.removeAt(0)) 471 } 472 } else { 473 if i >= len(n.items) { 474 i-- 475 } 476 child := n.mutableChild(i) 477 // merge with right child 478 mergeItem := n.items.removeAt(i) 479 mergeChild := n.children.removeAt(i + 1) 480 child.items = append(child.items, mergeItem) 481 child.items = append(child.items, mergeChild.items...) 482 child.children = append(child.children, mergeChild.children...) 483 n.cow.freeNode(mergeChild) 484 } 485 return n.remove(item, minItems, typ) 486} 487 488type direction int 489 490const ( 491 descend = direction(-1) 492 ascend = direction(+1) 493) 494 495// iterate provides a simple method for iterating over elements in the tree. 496// 497// When ascending, the 'start' should be less than 'stop' and when descending, 498// the 'start' should be greater than 'stop'. Setting 'includeStart' to true 499// will force the iterator to include the first item when it equals 'start', 500// thus creating a "greaterOrEqual" or "lessThanEqual" rather than just a 501// "greaterThan" or "lessThan" queries. 502func (n *node) iterate(dir direction, start, stop Item, includeStart bool, hit bool, iter ItemIterator) (bool, bool) { 503 var ok, found bool 504 var index int 505 switch dir { 506 case ascend: 507 if start != nil { 508 index, _ = n.items.find(start) 509 } 510 for i := index; i < len(n.items); i++ { 511 if len(n.children) > 0 { 512 if hit, ok = n.children[i].iterate(dir, start, stop, includeStart, hit, iter); !ok { 513 return hit, false 514 } 515 } 516 if !includeStart && !hit && start != nil && !start.Less(n.items[i]) { 517 hit = true 518 continue 519 } 520 hit = true 521 if stop != nil && !n.items[i].Less(stop) { 522 return hit, false 523 } 524 if !iter(n.items[i]) { 525 return hit, false 526 } 527 } 528 if len(n.children) > 0 { 529 if hit, ok = n.children[len(n.children)-1].iterate(dir, start, stop, includeStart, hit, iter); !ok { 530 return hit, false 531 } 532 } 533 case descend: 534 if start != nil { 535 index, found = n.items.find(start) 536 if !found { 537 index = index - 1 538 } 539 } else { 540 index = len(n.items) - 1 541 } 542 for i := index; i >= 0; i-- { 543 if start != nil && !n.items[i].Less(start) { 544 if !includeStart || hit || start.Less(n.items[i]) { 545 continue 546 } 547 } 548 if len(n.children) > 0 { 549 if hit, ok = n.children[i+1].iterate(dir, start, stop, includeStart, hit, iter); !ok { 550 return hit, false 551 } 552 } 553 if stop != nil && !stop.Less(n.items[i]) { 554 return hit, false // continue 555 } 556 hit = true 557 if !iter(n.items[i]) { 558 return hit, false 559 } 560 } 561 if len(n.children) > 0 { 562 if hit, ok = n.children[0].iterate(dir, start, stop, includeStart, hit, iter); !ok { 563 return hit, false 564 } 565 } 566 } 567 return hit, true 568} 569 570// Used for testing/debugging purposes. 571func (n *node) print(w io.Writer, level int) { 572 fmt.Fprintf(w, "%sNODE:%v\n", strings.Repeat(" ", level), n.items) 573 for _, c := range n.children { 574 c.print(w, level+1) 575 } 576} 577 578// BTree is an implementation of a B-Tree. 579// 580// BTree stores Item instances in an ordered structure, allowing easy insertion, 581// removal, and iteration. 582// 583// Write operations are not safe for concurrent mutation by multiple 584// goroutines, but Read operations are. 585type BTree struct { 586 degree int 587 length int 588 root *node 589 cow *copyOnWriteContext 590} 591 592// copyOnWriteContext pointers determine node ownership... a tree with a write 593// context equivalent to a node's write context is allowed to modify that node. 594// A tree whose write context does not match a node's is not allowed to modify 595// it, and must create a new, writable copy (IE: it's a Clone). 596// 597// When doing any write operation, we maintain the invariant that the current 598// node's context is equal to the context of the tree that requested the write. 599// We do this by, before we descend into any node, creating a copy with the 600// correct context if the contexts don't match. 601// 602// Since the node we're currently visiting on any write has the requesting 603// tree's context, that node is modifiable in place. Children of that node may 604// not share context, but before we descend into them, we'll make a mutable 605// copy. 606type copyOnWriteContext struct { 607 freelist *FreeList 608} 609 610// Clone clones the btree, lazily. Clone should not be called concurrently, 611// but the original tree (t) and the new tree (t2) can be used concurrently 612// once the Clone call completes. 613// 614// The internal tree structure of b is marked read-only and shared between t and 615// t2. Writes to both t and t2 use copy-on-write logic, creating new nodes 616// whenever one of b's original nodes would have been modified. Read operations 617// should have no performance degredation. Write operations for both t and t2 618// will initially experience minor slow-downs caused by additional allocs and 619// copies due to the aforementioned copy-on-write logic, but should converge to 620// the original performance characteristics of the original tree. 621func (t *BTree) Clone() (t2 *BTree) { 622 // Create two entirely new copy-on-write contexts. 623 // This operation effectively creates three trees: 624 // the original, shared nodes (old b.cow) 625 // the new b.cow nodes 626 // the new out.cow nodes 627 cow1, cow2 := *t.cow, *t.cow 628 out := *t 629 t.cow = &cow1 630 out.cow = &cow2 631 return &out 632} 633 634// maxItems returns the max number of items to allow per node. 635func (t *BTree) maxItems() int { 636 return t.degree*2 - 1 637} 638 639// minItems returns the min number of items to allow per node (ignored for the 640// root node). 641func (t *BTree) minItems() int { 642 return t.degree - 1 643} 644 645func (c *copyOnWriteContext) newNode() (n *node) { 646 n = c.freelist.newNode() 647 n.cow = c 648 return 649} 650 651type freeType int 652 653const ( 654 ftFreelistFull freeType = iota // node was freed (available for GC, not stored in freelist) 655 ftStored // node was stored in the freelist for later use 656 ftNotOwned // node was ignored by COW, since it's owned by another one 657) 658 659// freeNode frees a node within a given COW context, if it's owned by that 660// context. It returns what happened to the node (see freeType const 661// documentation). 662func (c *copyOnWriteContext) freeNode(n *node) freeType { 663 if n.cow == c { 664 // clear to allow GC 665 n.items.truncate(0) 666 n.children.truncate(0) 667 n.cow = nil 668 if c.freelist.freeNode(n) { 669 return ftStored 670 } else { 671 return ftFreelistFull 672 } 673 } else { 674 return ftNotOwned 675 } 676} 677 678// ReplaceOrInsert adds the given item to the tree. If an item in the tree 679// already equals the given one, it is removed from the tree and returned. 680// Otherwise, nil is returned. 681// 682// nil cannot be added to the tree (will panic). 683func (t *BTree) ReplaceOrInsert(item Item) Item { 684 if item == nil { 685 panic("nil item being added to BTree") 686 } 687 if t.root == nil { 688 t.root = t.cow.newNode() 689 t.root.items = append(t.root.items, item) 690 t.length++ 691 return nil 692 } else { 693 t.root = t.root.mutableFor(t.cow) 694 if len(t.root.items) >= t.maxItems() { 695 item2, second := t.root.split(t.maxItems() / 2) 696 oldroot := t.root 697 t.root = t.cow.newNode() 698 t.root.items = append(t.root.items, item2) 699 t.root.children = append(t.root.children, oldroot, second) 700 } 701 } 702 out := t.root.insert(item, t.maxItems()) 703 if out == nil { 704 t.length++ 705 } 706 return out 707} 708 709// Delete removes an item equal to the passed in item from the tree, returning 710// it. If no such item exists, returns nil. 711func (t *BTree) Delete(item Item) Item { 712 return t.deleteItem(item, removeItem) 713} 714 715// DeleteMin removes the smallest item in the tree and returns it. 716// If no such item exists, returns nil. 717func (t *BTree) DeleteMin() Item { 718 return t.deleteItem(nil, removeMin) 719} 720 721// DeleteMax removes the largest item in the tree and returns it. 722// If no such item exists, returns nil. 723func (t *BTree) DeleteMax() Item { 724 return t.deleteItem(nil, removeMax) 725} 726 727func (t *BTree) deleteItem(item Item, typ toRemove) Item { 728 if t.root == nil || len(t.root.items) == 0 { 729 return nil 730 } 731 t.root = t.root.mutableFor(t.cow) 732 out := t.root.remove(item, t.minItems(), typ) 733 if len(t.root.items) == 0 && len(t.root.children) > 0 { 734 oldroot := t.root 735 t.root = t.root.children[0] 736 t.cow.freeNode(oldroot) 737 } 738 if out != nil { 739 t.length-- 740 } 741 return out 742} 743 744// AscendRange calls the iterator for every value in the tree within the range 745// [greaterOrEqual, lessThan), until iterator returns false. 746func (t *BTree) AscendRange(greaterOrEqual, lessThan Item, iterator ItemIterator) { 747 if t.root == nil { 748 return 749 } 750 t.root.iterate(ascend, greaterOrEqual, lessThan, true, false, iterator) 751} 752 753// AscendLessThan calls the iterator for every value in the tree within the range 754// [first, pivot), until iterator returns false. 755func (t *BTree) AscendLessThan(pivot Item, iterator ItemIterator) { 756 if t.root == nil { 757 return 758 } 759 t.root.iterate(ascend, nil, pivot, false, false, iterator) 760} 761 762// AscendGreaterOrEqual calls the iterator for every value in the tree within 763// the range [pivot, last], until iterator returns false. 764func (t *BTree) AscendGreaterOrEqual(pivot Item, iterator ItemIterator) { 765 if t.root == nil { 766 return 767 } 768 t.root.iterate(ascend, pivot, nil, true, false, iterator) 769} 770 771// Ascend calls the iterator for every value in the tree within the range 772// [first, last], until iterator returns false. 773func (t *BTree) Ascend(iterator ItemIterator) { 774 if t.root == nil { 775 return 776 } 777 t.root.iterate(ascend, nil, nil, false, false, iterator) 778} 779 780// DescendRange calls the iterator for every value in the tree within the range 781// [lessOrEqual, greaterThan), until iterator returns false. 782func (t *BTree) DescendRange(lessOrEqual, greaterThan Item, iterator ItemIterator) { 783 if t.root == nil { 784 return 785 } 786 t.root.iterate(descend, lessOrEqual, greaterThan, true, false, iterator) 787} 788 789// DescendLessOrEqual calls the iterator for every value in the tree within the range 790// [pivot, first], until iterator returns false. 791func (t *BTree) DescendLessOrEqual(pivot Item, iterator ItemIterator) { 792 if t.root == nil { 793 return 794 } 795 t.root.iterate(descend, pivot, nil, true, false, iterator) 796} 797 798// DescendGreaterThan calls the iterator for every value in the tree within 799// the range (pivot, last], until iterator returns false. 800func (t *BTree) DescendGreaterThan(pivot Item, iterator ItemIterator) { 801 if t.root == nil { 802 return 803 } 804 t.root.iterate(descend, nil, pivot, false, false, iterator) 805} 806 807// Descend calls the iterator for every value in the tree within the range 808// [last, first], until iterator returns false. 809func (t *BTree) Descend(iterator ItemIterator) { 810 if t.root == nil { 811 return 812 } 813 t.root.iterate(descend, nil, nil, false, false, iterator) 814} 815 816// Get looks for the key item in the tree, returning it. It returns nil if 817// unable to find that item. 818func (t *BTree) Get(key Item) Item { 819 if t.root == nil { 820 return nil 821 } 822 return t.root.get(key) 823} 824 825// Min returns the smallest item in the tree, or nil if the tree is empty. 826func (t *BTree) Min() Item { 827 return min(t.root) 828} 829 830// Max returns the largest item in the tree, or nil if the tree is empty. 831func (t *BTree) Max() Item { 832 return max(t.root) 833} 834 835// Has returns true if the given key is in the tree. 836func (t *BTree) Has(key Item) bool { 837 return t.Get(key) != nil 838} 839 840// Len returns the number of items currently in the tree. 841func (t *BTree) Len() int { 842 return t.length 843} 844 845// Clear removes all items from the btree. If addNodesToFreelist is true, 846// t's nodes are added to its freelist as part of this call, until the freelist 847// is full. Otherwise, the root node is simply dereferenced and the subtree 848// left to Go's normal GC processes. 849// 850// This can be much faster 851// than calling Delete on all elements, because that requires finding/removing 852// each element in the tree and updating the tree accordingly. It also is 853// somewhat faster than creating a new tree to replace the old one, because 854// nodes from the old tree are reclaimed into the freelist for use by the new 855// one, instead of being lost to the garbage collector. 856// 857// This call takes: 858// O(1): when addNodesToFreelist is false, this is a single operation. 859// O(1): when the freelist is already full, it breaks out immediately 860// O(freelist size): when the freelist is empty and the nodes are all owned 861// by this tree, nodes are added to the freelist until full. 862// O(tree size): when all nodes are owned by another tree, all nodes are 863// iterated over looking for nodes to add to the freelist, and due to 864// ownership, none are. 865func (t *BTree) Clear(addNodesToFreelist bool) { 866 if t.root != nil && addNodesToFreelist { 867 t.root.reset(t.cow) 868 } 869 t.root, t.length = nil, 0 870} 871 872// reset returns a subtree to the freelist. It breaks out immediately if the 873// freelist is full, since the only benefit of iterating is to fill that 874// freelist up. Returns true if parent reset call should continue. 875func (n *node) reset(c *copyOnWriteContext) bool { 876 for _, child := range n.children { 877 if !child.reset(c) { 878 return false 879 } 880 } 881 return c.freeNode(n) != ftFreelistFull 882} 883 884// Int implements the Item interface for integers. 885type Int int 886 887// Less returns true if int(a) < int(b). 888func (a Int) Less(b Item) bool { 889 return a < b.(Int) 890} 891