1// Copyright 2014 Google LLC 2// Modified 2018 by Jonathan Amsterdam (jbamsterdam@gmail.com) 3// 4// Licensed under the Apache License, Version 2.0 (the "License"); 5// you may not use this file except in compliance with the License. 6// You may obtain a copy of the License at 7// 8// http://www.apache.org/licenses/LICENSE-2.0 9// 10// Unless required by applicable law or agreed to in writing, software 11// distributed under the License is distributed on an "AS IS" BASIS, 12// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. 13// See the License for the specific language governing permissions and 14// limitations under the License. 15 16// Package btree implements in-memory B-Trees of arbitrary degree. 17// 18// This implementation is based on google/btree (http://github.com/google/btree), and 19// much of the code is taken from there. But the API has been changed significantly, 20// particularly around iteration, and support for indexing by position has been 21// added. 22// 23// btree implements an in-memory B-Tree for use as an ordered data structure. 24// It is not meant for persistent storage solutions. 25// 26// It has a flatter structure than an equivalent red-black or other binary tree, 27// which in some cases yields better memory usage and/or performance. 28// See some discussion on the matter here: 29// http://google-opensource.blogspot.com/2013/01/c-containers-that-save-memory-and-time.html 30// Note, though, that this project is in no way related to the C++ B-Tree 31// implementation written about there. 32// 33// Within this tree, each node contains a slice of items and a (possibly nil) 34// slice of children. For basic numeric values or raw structs, this can cause 35// efficiency differences when compared to equivalent C++ template code that 36// stores values in arrays within the node: 37// * Due to the overhead of storing values as interfaces (each 38// value needs to be stored as the value itself, then 2 words for the 39// interface pointing to that value and its type), resulting in higher 40// memory use. 41// * Since interfaces can point to values anywhere in memory, values are 42// most likely not stored in contiguous blocks, resulting in a higher 43// number of cache misses. 44// These issues don't tend to matter, though, when working with strings or other 45// heap-allocated structures, since C++-equivalent structures also must store 46// pointers and also distribute their values across the heap. 47package btree 48 49import ( 50 "sort" 51 "sync" 52) 53 54// Key represents a key into the tree. 55type Key interface{} 56 57// Value represents a value in the tree. 58type Value interface{} 59 60// item is a key-value pair. 61type item struct { 62 key Key 63 value Value 64} 65 66type lessFunc func(interface{}, interface{}) bool 67 68// New creates a new B-Tree with the given degree and comparison function. 69// 70// New(2, less), for example, will create a 2-3-4 tree (each node contains 1-3 items 71// and 2-4 children). 72// 73// The less function tests whether the current item is less than the given argument. 74// It must provide a strict weak ordering. 75// If !less(a, b) && !less(b, a), we treat this to mean a == b (i.e. the tree 76// can hold only one of a or b). 77func New(degree int, less func(interface{}, interface{}) bool) *BTree { 78 if degree <= 1 { 79 panic("bad degree") 80 } 81 return &BTree{ 82 degree: degree, 83 less: less, 84 cow: ©OnWriteContext{}, 85 } 86} 87 88// items stores items in a node. 89type items []item 90 91// insertAt inserts a value into the given index, pushing all subsequent values 92// forward. 93func (s *items) insertAt(index int, m item) { 94 *s = append(*s, item{}) 95 if index < len(*s) { 96 copy((*s)[index+1:], (*s)[index:]) 97 } 98 (*s)[index] = m 99} 100 101// removeAt removes a value at a given index, pulling all subsequent values 102// back. 103func (s *items) removeAt(index int) item { 104 m := (*s)[index] 105 copy((*s)[index:], (*s)[index+1:]) 106 (*s)[len(*s)-1] = item{} 107 *s = (*s)[:len(*s)-1] 108 return m 109} 110 111// pop removes and returns the last element in the list. 112func (s *items) pop() item { 113 index := len(*s) - 1 114 out := (*s)[index] 115 (*s)[index] = item{} 116 *s = (*s)[:index] 117 return out 118} 119 120var nilItems = make(items, 16) 121 122// truncate truncates this instance at index so that it contains only the 123// first index items. index must be less than or equal to length. 124func (s *items) truncate(index int) { 125 var toClear items 126 *s, toClear = (*s)[:index], (*s)[index:] 127 for len(toClear) > 0 { 128 toClear = toClear[copy(toClear, nilItems):] 129 } 130} 131 132// find returns the index where an item with key should be inserted into this 133// list. 'found' is true if the item already exists in the list at the given 134// index. 135func (s items) find(k Key, less lessFunc) (index int, found bool) { 136 i := sort.Search(len(s), func(i int) bool { return less(k, s[i].key) }) 137 // i is the smallest index of s for which k.Less(s[i].Key), or len(s). 138 if i > 0 && !less(s[i-1].key, k) { 139 return i - 1, true 140 } 141 return i, false 142} 143 144// children stores child nodes in a node. 145type children []*node 146 147// insertAt inserts a value into the given index, pushing all subsequent values 148// forward. 149func (s *children) insertAt(index int, n *node) { 150 *s = append(*s, nil) 151 if index < len(*s) { 152 copy((*s)[index+1:], (*s)[index:]) 153 } 154 (*s)[index] = n 155} 156 157// removeAt removes a value at a given index, pulling all subsequent values 158// back. 159func (s *children) removeAt(index int) *node { 160 n := (*s)[index] 161 copy((*s)[index:], (*s)[index+1:]) 162 (*s)[len(*s)-1] = nil 163 *s = (*s)[:len(*s)-1] 164 return n 165} 166 167// pop removes and returns the last element in the list. 168func (s *children) pop() (out *node) { 169 index := len(*s) - 1 170 out = (*s)[index] 171 (*s)[index] = nil 172 *s = (*s)[:index] 173 return 174} 175 176var nilChildren = make(children, 16) 177 178// truncate truncates this instance at index so that it contains only the 179// first index children. index must be less than or equal to length. 180func (s *children) truncate(index int) { 181 var toClear children 182 *s, toClear = (*s)[:index], (*s)[index:] 183 for len(toClear) > 0 { 184 toClear = toClear[copy(toClear, nilChildren):] 185 } 186} 187 188// node is an internal node in a tree. 189// 190// It must at all times maintain the invariant that either 191// * len(children) == 0, len(items) unconstrained 192// * len(children) == len(items) + 1 193type node struct { 194 items items 195 children children 196 size int // number of items in the subtree: len(items) + sum over i of children[i].size 197 cow *copyOnWriteContext 198} 199 200func (n *node) computeSize() int { 201 sz := len(n.items) 202 for _, c := range n.children { 203 sz += c.size 204 } 205 return sz 206} 207 208func (n *node) mutableFor(cow *copyOnWriteContext) *node { 209 if n.cow == cow { 210 return n 211 } 212 out := cow.newNode() 213 if cap(out.items) >= len(n.items) { 214 out.items = out.items[:len(n.items)] 215 } else { 216 out.items = make(items, len(n.items), cap(n.items)) 217 } 218 copy(out.items, n.items) 219 // Copy children 220 if cap(out.children) >= len(n.children) { 221 out.children = out.children[:len(n.children)] 222 } else { 223 out.children = make(children, len(n.children), cap(n.children)) 224 } 225 copy(out.children, n.children) 226 out.size = n.size 227 return out 228} 229 230func (n *node) mutableChild(i int) *node { 231 c := n.children[i].mutableFor(n.cow) 232 n.children[i] = c 233 return c 234} 235 236// split splits the given node at the given index. The current node shrinks, 237// and this function returns the item that existed at that index and a new node 238// containing all items/children after it. 239func (n *node) split(i int) (item, *node) { 240 item := n.items[i] 241 next := n.cow.newNode() 242 next.items = append(next.items, n.items[i+1:]...) 243 n.items.truncate(i) 244 if len(n.children) > 0 { 245 next.children = append(next.children, n.children[i+1:]...) 246 n.children.truncate(i + 1) 247 } 248 n.size = n.computeSize() 249 next.size = next.computeSize() 250 return item, next 251} 252 253// maybeSplitChild checks if a child should be split, and if so splits it. 254// Returns whether or not a split occurred. 255func (n *node) maybeSplitChild(i, maxItems int) bool { 256 if len(n.children[i].items) < maxItems { 257 return false 258 } 259 first := n.mutableChild(i) 260 item, second := first.split(maxItems / 2) 261 n.items.insertAt(i, item) 262 n.children.insertAt(i+1, second) 263 // The size of n doesn't change. 264 return true 265} 266 267// insert inserts an item into the subtree rooted at this node, making sure 268// no nodes in the subtree exceed maxItems items. Should an equivalent item be 269// be found/replaced by insert, its value will be returned. 270// 271// If computeIndex is true, the third return value is the index of the value with respect to n. 272func (n *node) insert(m item, maxItems int, less lessFunc, computeIndex bool) (old Value, present bool, idx int) { 273 i, found := n.items.find(m.key, less) 274 if found { 275 out := n.items[i] 276 n.items[i] = m 277 if computeIndex { 278 idx = n.itemIndex(i) 279 } 280 return out.value, true, idx 281 } 282 if len(n.children) == 0 { 283 n.items.insertAt(i, m) 284 n.size++ 285 return old, false, i 286 } 287 if n.maybeSplitChild(i, maxItems) { 288 inTree := n.items[i] 289 switch { 290 case less(m.key, inTree.key): 291 // no change, we want first split node 292 case less(inTree.key, m.key): 293 i++ // we want second split node 294 default: 295 out := n.items[i] 296 n.items[i] = m 297 if computeIndex { 298 idx = n.itemIndex(i) 299 } 300 return out.value, true, idx 301 } 302 } 303 old, present, idx = n.mutableChild(i).insert(m, maxItems, less, computeIndex) 304 if !present { 305 n.size++ 306 } 307 if computeIndex { 308 idx += n.partialSize(i) 309 } 310 return old, present, idx 311} 312 313// get finds the given key in the subtree and returns the corresponding item, along with a boolean reporting 314// whether it was found. 315// If computeIndex is true, it also returns the index of the key relative to the node's subtree. 316func (n *node) get(k Key, computeIndex bool, less lessFunc) (item, bool, int) { 317 i, found := n.items.find(k, less) 318 if found { 319 return n.items[i], true, n.itemIndex(i) 320 } 321 if len(n.children) > 0 { 322 m, found, idx := n.children[i].get(k, computeIndex, less) 323 if computeIndex && found { 324 idx += n.partialSize(i) 325 } 326 return m, found, idx 327 } 328 return item{}, false, -1 329} 330 331// itemIndex returns the index w.r.t. n of the ith item in n. 332func (n *node) itemIndex(i int) int { 333 if len(n.children) == 0 { 334 return i 335 } 336 // Get the size of the node up to but not including the child to the right of 337 // item i. Subtract 1 because the index is 0-based. 338 return n.partialSize(i+1) - 1 339} 340 341// Returns the size of the non-leaf node up to but not including child i. 342func (n *node) partialSize(i int) int { 343 var sz int 344 for j, c := range n.children { 345 if j == i { 346 break 347 } 348 sz += c.size + 1 349 } 350 return sz 351} 352 353// cursorStackForKey returns a stack of cursors for the key, along with whether the key was found and the index. 354func (n *node) cursorStackForKey(k Key, cs cursorStack, less lessFunc) (cursorStack, bool, int) { 355 i, found := n.items.find(k, less) 356 cs.push(cursor{n, i}) 357 idx := i 358 if found { 359 if len(n.children) > 0 { 360 idx = n.partialSize(i+1) - 1 361 } 362 return cs, true, idx 363 } 364 if len(n.children) > 0 { 365 cs, found, idx := n.children[i].cursorStackForKey(k, cs, less) 366 return cs, found, idx + n.partialSize(i) 367 } 368 return cs, false, idx 369} 370 371// at returns the item at the i'th position in the subtree rooted at n. 372// It assumes i is in range. 373func (n *node) at(i int) item { 374 if len(n.children) == 0 { 375 return n.items[i] 376 } 377 for j, c := range n.children { 378 if i < c.size { 379 return c.at(i) 380 } 381 i -= c.size 382 if i == 0 { 383 return n.items[j] 384 } 385 i-- 386 } 387 panic("impossible") 388} 389 390// cursorStackForIndex returns a stack of cursors for the index. 391// It assumes i is in range. 392func (n *node) cursorStackForIndex(i int, cs cursorStack) cursorStack { 393 if len(n.children) == 0 { 394 return cs.push(cursor{n, i}) 395 } 396 for j, c := range n.children { 397 if i < c.size { 398 return c.cursorStackForIndex(i, cs.push(cursor{n, j})) 399 } 400 i -= c.size 401 if i == 0 { 402 return cs.push(cursor{n, j}) 403 } 404 i-- 405 } 406 panic("impossible") 407} 408 409// toRemove details what item to remove in a node.remove call. 410type toRemove int 411 412const ( 413 removeItem toRemove = iota // removes the given item 414 removeMin // removes smallest item in the subtree 415 removeMax // removes largest item in the subtree 416) 417 418// remove removes an item from the subtree rooted at this node. 419func (n *node) remove(key Key, minItems int, typ toRemove, less lessFunc) (item, bool) { 420 var i int 421 var found bool 422 switch typ { 423 case removeMax: 424 if len(n.children) == 0 { 425 n.size-- 426 return n.items.pop(), true 427 428 } 429 i = len(n.items) 430 case removeMin: 431 if len(n.children) == 0 { 432 n.size-- 433 return n.items.removeAt(0), true 434 } 435 i = 0 436 case removeItem: 437 i, found = n.items.find(key, less) 438 if len(n.children) == 0 { 439 if found { 440 n.size-- 441 return n.items.removeAt(i), true 442 } 443 return item{}, false 444 } 445 default: 446 panic("invalid type") 447 } 448 // If we get to here, we have children. 449 if len(n.children[i].items) <= minItems { 450 return n.growChildAndRemove(i, key, minItems, typ, less) 451 } 452 child := n.mutableChild(i) 453 // Either we had enough items to begin with, or we've done some 454 // merging/stealing, because we've got enough now and we're ready to return 455 // stuff. 456 if found { 457 // The item exists at index 'i', and the child we've selected can give us a 458 // predecessor, since if we've gotten here it's got > minItems items in it. 459 out := n.items[i] 460 // We use our special-case 'remove' call with typ=maxItem to pull the 461 // predecessor of item i (the rightmost leaf of our immediate left child) 462 // and set it into where we pulled the item from. 463 n.items[i], _ = child.remove(nil, minItems, removeMax, less) 464 n.size-- 465 return out, true 466 } 467 // Final recursive call. Once we're here, we know that the item isn't in this 468 // node and that the child is big enough to remove from. 469 m, removed := child.remove(key, minItems, typ, less) 470 if removed { 471 n.size-- 472 } 473 return m, removed 474} 475 476// growChildAndRemove grows child 'i' to make sure it's possible to remove an 477// item from it while keeping it at minItems, then calls remove to actually 478// remove it. 479// 480// Most documentation says we have to do two sets of special casing: 481// 1) item is in this node 482// 2) item is in child 483// In both cases, we need to handle the two subcases: 484// A) node has enough values that it can spare one 485// B) node doesn't have enough values 486// For the latter, we have to check: 487// a) left sibling has node to spare 488// b) right sibling has node to spare 489// c) we must merge 490// To simplify our code here, we handle cases #1 and #2 the same: 491// If a node doesn't have enough items, we make sure it does (using a,b,c). 492// We then simply redo our remove call, and the second time (regardless of 493// whether we're in case 1 or 2), we'll have enough items and can guarantee 494// that we hit case A. 495func (n *node) growChildAndRemove(i int, key Key, minItems int, typ toRemove, less lessFunc) (item, bool) { 496 if i > 0 && len(n.children[i-1].items) > minItems { 497 // Steal from left child 498 child := n.mutableChild(i) 499 stealFrom := n.mutableChild(i - 1) 500 stolenItem := stealFrom.items.pop() 501 stealFrom.size-- 502 child.items.insertAt(0, n.items[i-1]) 503 child.size++ 504 n.items[i-1] = stolenItem 505 if len(stealFrom.children) > 0 { 506 c := stealFrom.children.pop() 507 stealFrom.size -= c.size 508 child.children.insertAt(0, c) 509 child.size += c.size 510 } 511 } else if i < len(n.items) && len(n.children[i+1].items) > minItems { 512 // steal from right child 513 child := n.mutableChild(i) 514 stealFrom := n.mutableChild(i + 1) 515 stolenItem := stealFrom.items.removeAt(0) 516 stealFrom.size-- 517 child.items = append(child.items, n.items[i]) 518 child.size++ 519 n.items[i] = stolenItem 520 if len(stealFrom.children) > 0 { 521 c := stealFrom.children.removeAt(0) 522 stealFrom.size -= c.size 523 child.children = append(child.children, c) 524 child.size += c.size 525 } 526 } else { 527 if i >= len(n.items) { 528 i-- 529 } 530 child := n.mutableChild(i) 531 // merge with right child 532 mergeItem := n.items.removeAt(i) 533 mergeChild := n.children.removeAt(i + 1) 534 child.items = append(child.items, mergeItem) 535 child.items = append(child.items, mergeChild.items...) 536 child.children = append(child.children, mergeChild.children...) 537 child.size = child.computeSize() 538 n.cow.freeNode(mergeChild) 539 } 540 return n.remove(key, minItems, typ, less) 541} 542 543// BTree is an implementation of a B-Tree. 544// 545// BTree stores item instances in an ordered structure, allowing easy insertion, 546// removal, and iteration. 547// 548// Write operations are not safe for concurrent mutation by multiple 549// goroutines, but Read operations are. 550type BTree struct { 551 degree int 552 less lessFunc 553 root *node 554 cow *copyOnWriteContext 555} 556 557// copyOnWriteContext pointers determine node ownership. A tree with a cow 558// context equivalent to a node's cow context is allowed to modify that node. 559// A tree whose write context does not match a node's is not allowed to modify 560// it, and must create a new, writable copy (IE: it's a Clone). 561// 562// When doing any write operation, we maintain the invariant that the current 563// node's context is equal to the context of the tree that requested the write. 564// We do this by, before we descend into any node, creating a copy with the 565// correct context if the contexts don't match. 566// 567// Since the node we're currently visiting on any write has the requesting 568// tree's context, that node is modifiable in place. Children of that node may 569// not share context, but before we descend into them, we'll make a mutable 570// copy. 571type copyOnWriteContext struct{ byte } // non-empty, because empty structs may have same addr 572 573// Clone clones the btree, lazily. Clone should not be called concurrently, 574// but the original tree (t) and the new tree (t2) can be used concurrently 575// once the Clone call completes. 576// 577// The internal tree structure of b is marked read-only and shared between t and 578// t2. Writes to both t and t2 use copy-on-write logic, creating new nodes 579// whenever one of b's original nodes would have been modified. Read operations 580// should have no performance degredation. Write operations for both t and t2 581// will initially experience minor slow-downs caused by additional allocs and 582// copies due to the aforementioned copy-on-write logic, but should converge to 583// the original performance characteristics of the original tree. 584func (t *BTree) Clone() *BTree { 585 // Create two entirely new copy-on-write contexts. 586 // This operation effectively creates three trees: 587 // the original, shared nodes (old b.cow) 588 // the new b.cow nodes 589 // the new out.cow nodes 590 cow1, cow2 := *t.cow, *t.cow 591 out := *t 592 t.cow = &cow1 593 out.cow = &cow2 594 return &out 595} 596 597// maxItems returns the max number of items to allow per node. 598func (t *BTree) maxItems() int { 599 return t.degree*2 - 1 600} 601 602// minItems returns the min number of items to allow per node (ignored for the 603// root node). 604func (t *BTree) minItems() int { 605 return t.degree - 1 606} 607 608var nodePool = sync.Pool{New: func() interface{} { return new(node) }} 609 610func (c *copyOnWriteContext) newNode() *node { 611 n := nodePool.Get().(*node) 612 n.cow = c 613 return n 614} 615 616func (c *copyOnWriteContext) freeNode(n *node) { 617 if n.cow == c { 618 // clear to allow GC 619 n.items.truncate(0) 620 n.children.truncate(0) 621 n.cow = nil 622 nodePool.Put(n) 623 } 624} 625 626// Set sets the given key to the given value in the tree. If the key is present in 627// the tree, its value is changed and the old value is returned along with a second 628// return value of true. If the key is not in the tree, it is added, and the second 629// return value is false. 630func (t *BTree) Set(k Key, v Value) (old Value, present bool) { 631 old, present, _ = t.set(k, v, false) 632 return old, present 633} 634 635// SetWithIndex sets the given key to the given value in the tree, and returns the 636// index at which it was inserted. 637func (t *BTree) SetWithIndex(k Key, v Value) (old Value, present bool, index int) { 638 return t.set(k, v, true) 639} 640 641func (t *BTree) set(k Key, v Value, computeIndex bool) (old Value, present bool, idx int) { 642 if t.root == nil { 643 t.root = t.cow.newNode() 644 t.root.items = append(t.root.items, item{k, v}) 645 t.root.size = 1 646 return old, false, 0 647 } 648 t.root = t.root.mutableFor(t.cow) 649 if len(t.root.items) >= t.maxItems() { 650 sz := t.root.size 651 item2, second := t.root.split(t.maxItems() / 2) 652 oldroot := t.root 653 t.root = t.cow.newNode() 654 t.root.items = append(t.root.items, item2) 655 t.root.children = append(t.root.children, oldroot, second) 656 t.root.size = sz 657 } 658 659 return t.root.insert(item{k, v}, t.maxItems(), t.less, computeIndex) 660} 661 662// Delete removes the item with the given key, returning its value. The second return value 663// reports whether the key was found. 664func (t *BTree) Delete(k Key) (Value, bool) { 665 m, removed := t.deleteItem(k, removeItem) 666 return m.value, removed 667} 668 669// DeleteMin removes the smallest item in the tree and returns its key and value. 670// If the tree is empty, it returns zero values. 671func (t *BTree) DeleteMin() (Key, Value) { 672 item, _ := t.deleteItem(nil, removeMin) 673 return item.key, item.value 674} 675 676// DeleteMax removes the largest item in the tree and returns its key and value. 677// If the tree is empty, it returns zero values. 678func (t *BTree) DeleteMax() (Key, Value) { 679 item, _ := t.deleteItem(nil, removeMax) 680 return item.key, item.value 681} 682 683func (t *BTree) deleteItem(key Key, typ toRemove) (item, bool) { 684 if t.root == nil || len(t.root.items) == 0 { 685 return item{}, false 686 } 687 t.root = t.root.mutableFor(t.cow) 688 out, removed := t.root.remove(key, t.minItems(), typ, t.less) 689 if len(t.root.items) == 0 && len(t.root.children) > 0 { 690 oldroot := t.root 691 t.root = t.root.children[0] 692 t.cow.freeNode(oldroot) 693 } 694 return out, removed 695} 696 697// Get returns the value for the given key in the tree, or the zero value if the 698// key is not in the tree. 699// 700// To distinguish a zero value from a key that is not present, use GetWithIndex. 701func (t *BTree) Get(k Key) Value { 702 var z Value 703 if t.root == nil { 704 return z 705 } 706 item, ok, _ := t.root.get(k, false, t.less) 707 if !ok { 708 return z 709 } 710 return item.value 711} 712 713// GetWithIndex returns the value and index for the given key in the tree, or the 714// zero value and -1 if the key is not in the tree. 715func (t *BTree) GetWithIndex(k Key) (Value, int) { 716 var z Value 717 if t.root == nil { 718 return z, -1 719 } 720 item, _, index := t.root.get(k, true, t.less) 721 return item.value, index 722} 723 724// At returns the key and value at index i. The minimum item has index 0. 725// If i is outside the range [0, t.Len()), At panics. 726func (t *BTree) At(i int) (Key, Value) { 727 if i < 0 || i >= t.Len() { 728 panic("btree: index out of range") 729 } 730 item := t.root.at(i) 731 return item.key, item.value 732} 733 734// Has reports whether the given key is in the tree. 735func (t *BTree) Has(k Key) bool { 736 if t.root == nil { 737 return false 738 } 739 _, ok, _ := t.root.get(k, false, t.less) 740 return ok 741} 742 743// Min returns the smallest key in the tree and its value. If the tree is empty, it 744// returns zero values. 745func (t *BTree) Min() (Key, Value) { 746 var k Key 747 var v Value 748 if t.root == nil { 749 return k, v 750 } 751 n := t.root 752 for len(n.children) > 0 { 753 n = n.children[0] 754 } 755 if len(n.items) == 0 { 756 return k, v 757 } 758 return n.items[0].key, n.items[0].value 759} 760 761// Max returns the largest key in the tree and its value. If the tree is empty, both 762// return values are zero values. 763func (t *BTree) Max() (Key, Value) { 764 var k Key 765 var v Value 766 if t.root == nil { 767 return k, v 768 } 769 n := t.root 770 for len(n.children) > 0 { 771 n = n.children[len(n.children)-1] 772 } 773 if len(n.items) == 0 { 774 return k, v 775 } 776 m := n.items[len(n.items)-1] 777 return m.key, m.value 778} 779 780// Len returns the number of items currently in the tree. 781func (t *BTree) Len() int { 782 if t.root == nil { 783 return 0 784 } 785 return t.root.size 786} 787 788// Before returns an iterator positioned just before k. After the first call to Next, 789// the Iterator will be at k, or at the key just greater than k if k is not in the tree. 790// Subsequent calls to Next will traverse the tree's items in ascending order. 791func (t *BTree) Before(k Key) *Iterator { 792 if t.root == nil { 793 return &Iterator{} 794 } 795 var cs cursorStack 796 cs, found, idx := t.root.cursorStackForKey(k, cs, t.less) 797 // If we found the key, the cursor stack is pointing to it. Since that is 798 // the first element we want, don't advance the iterator on the initial call to Next. 799 // If we haven't found the key, then the top of the cursor stack is either pointing at the 800 // item just after k, in which case we do not want to move the iterator; or the index 801 // is past the end of the items slice, in which case we do. 802 var stay bool 803 top := cs[len(cs)-1] 804 if found { 805 stay = true 806 } else if top.index < len(top.node.items) { 807 stay = true 808 } else { 809 idx-- 810 } 811 return &Iterator{ 812 cursors: cs, 813 stay: stay, 814 descending: false, 815 Index: idx, 816 } 817} 818 819// After returns an iterator positioned just after k. After the first call to Next, 820// the Iterator will be at k, or at the key just less than k if k is not in the tree. 821// Subsequent calls to Next will traverse the tree's items in descending order. 822func (t *BTree) After(k Key) *Iterator { 823 if t.root == nil { 824 return &Iterator{} 825 } 826 var cs cursorStack 827 cs, found, idx := t.root.cursorStackForKey(k, cs, t.less) 828 // If we found the key, the cursor stack is pointing to it. Since that is 829 // the first element we want, don't advance the iterator on the initial call to Next. 830 // If we haven't found the key, the cursor stack is pointing just after the first item, 831 // so we do want to advance. 832 return &Iterator{ 833 cursors: cs, 834 stay: found, 835 descending: true, 836 Index: idx, 837 } 838} 839 840// BeforeIndex returns an iterator positioned just before the item with the given index. 841// The iterator will traverse the tree's items in ascending order. 842// If i is not in the range [0, tr.Len()], BeforeIndex panics. 843// Note that it is not an error to provide an index of tr.Len(). 844func (t *BTree) BeforeIndex(i int) *Iterator { 845 return t.indexIterator(i, false) 846} 847 848// AfterIndex returns an iterator positioned just after the item with the given index. 849// The iterator will traverse the tree's items in descending order. 850// If i is not in the range [0, tr.Len()], AfterIndex panics. 851// Note that it is not an error to provide an index of tr.Len(). 852func (t *BTree) AfterIndex(i int) *Iterator { 853 return t.indexIterator(i, true) 854} 855 856func (t *BTree) indexIterator(i int, descending bool) *Iterator { 857 if i < 0 || i > t.Len() { 858 panic("btree: index out of range") 859 } 860 if i == t.Len() { 861 return &Iterator{} 862 } 863 var cs cursorStack 864 return &Iterator{ 865 cursors: t.root.cursorStackForIndex(i, cs), 866 stay: true, 867 descending: descending, 868 Index: i, 869 } 870} 871 872// An Iterator supports traversing the items in the tree. 873type Iterator struct { 874 Key Key 875 Value Value 876 // Index is the position of the item in the tree viewed as a sequence. 877 // The minimum item has index zero. 878 Index int 879 880 cursors cursorStack // stack of nodes with indices; last element is the top 881 stay bool // don't do anything on the first call to Next. 882 descending bool // traverse the items in descending order 883} 884 885// Next advances the Iterator to the next item in the tree. If Next returns true, 886// the Iterator's Key, Value and Index fields refer to the next item. If Next returns 887// false, there are no more items and the values of Key, Value and Index are undefined. 888// 889// If the tree is modified during iteration, the behavior is undefined. 890func (it *Iterator) Next() bool { 891 var more bool 892 switch { 893 case len(it.cursors) == 0: 894 more = false 895 case it.stay: 896 it.stay = false 897 more = true 898 case it.descending: 899 more = it.dec() 900 default: 901 more = it.inc() 902 } 903 if !more { 904 return false 905 } 906 top := it.cursors[len(it.cursors)-1] 907 item := top.node.items[top.index] 908 it.Key = item.key 909 it.Value = item.value 910 return true 911} 912 913// When inc returns true, the top cursor on the stack refers to the new current item. 914func (it *Iterator) inc() bool { 915 // Useful invariants for understanding this function: 916 // - Leaf nodes have zero children, and zero or more items. 917 // - Nonleaf nodes have one more child than item, and children[i] < items[i] < children[i+1]. 918 // - The current item in the iterator is top.node.items[top.index]. 919 920 it.Index++ 921 // If we are at a non-leaf node, the current item is items[i], so 922 // now we want to continue with children[i+1], which must exist 923 // by the node invariant. We want the minimum item in that child's subtree. 924 top := it.cursors.incTop(1) 925 for len(top.node.children) > 0 { 926 top = cursor{top.node.children[top.index], 0} 927 it.cursors.push(top) 928 } 929 // Here, we are at a leaf node. top.index points to 930 // the new current item, if it's within the items slice. 931 for top.index >= len(top.node.items) { 932 // We've gone through everything in this node. Pop it off the stack. 933 it.cursors.pop() 934 // If the stack is now empty,we're past the last item in the tree. 935 if it.cursors.empty() { 936 return false 937 } 938 top = it.cursors.top() 939 // The new top's index points to a child, which we've just finished 940 // exploring. The next item is the one at the same index in the items slice. 941 } 942 // Here, the top cursor on the stack points to the new current item. 943 return true 944} 945 946func (it *Iterator) dec() bool { 947 // See the invariants for inc, above. 948 it.Index-- 949 top := it.cursors.top() 950 // If we are at a non-leaf node, the current item is items[i], so 951 // now we want to continue with children[i]. We want the maximum item in that child's subtree. 952 for len(top.node.children) > 0 { 953 c := top.node.children[top.index] 954 top = cursor{c, len(c.items)} 955 it.cursors.push(top) 956 } 957 top = it.cursors.incTop(-1) 958 // Here, we are at a leaf node. top.index points to 959 // the new current item, if it's within the items slice. 960 for top.index < 0 { 961 // We've gone through everything in this node. Pop it off the stack. 962 it.cursors.pop() 963 // If the stack is now empty,we're past the last item in the tree. 964 if it.cursors.empty() { 965 return false 966 } 967 // The new top's index points to a child, which we've just finished 968 // exploring. That child is to the right of the item we want to advance to, 969 // so decrement the index. 970 top = it.cursors.incTop(-1) 971 } 972 return true 973} 974 975// A cursor is effectively a pointer into a node. A stack of cursors identifies an item in the tree, 976// and makes it possible to move to the next or previous item efficiently. 977// 978// If the cursor is on the top of the stack, its index points into the node's items slice, selecting 979// the current item. Otherwise, the index points into the children slice and identifies the child 980// that is next in the stack. 981type cursor struct { 982 node *node 983 index int 984} 985 986// A cursorStack is a stack of cursors, representing a path of nodes from the root of the tree. 987type cursorStack []cursor 988 989func (s *cursorStack) push(c cursor) cursorStack { 990 *s = append(*s, c) 991 return *s 992} 993 994func (s *cursorStack) pop() cursor { 995 last := len(*s) - 1 996 t := (*s)[last] 997 *s = (*s)[:last] 998 return t 999} 1000 1001func (s *cursorStack) top() cursor { 1002 return (*s)[len(*s)-1] 1003} 1004 1005func (s *cursorStack) empty() bool { 1006 return len(*s) == 0 1007} 1008 1009// incTop increments top's index by n and returns it. 1010func (s *cursorStack) incTop(n int) cursor { 1011 (*s)[len(*s)-1].index += n // Don't call top: modify the original, not a copy. 1012 return s.top() 1013} 1014