1// Copyright 2014 The b Authors. All rights reserved. 2// Use of this source code is governed by a BSD-style 3// license that can be found in the LICENSE file. 4 5// Package b implements a B+tree. 6// 7// Changelog 8// 9// 2014-06-26: Lower GC presure by recycling things. 10// 11// 2014-04-18: Added new method Put. 12// 13// Generic types 14// 15// Keys and their associated values are interface{} typed, similar to all of 16// the containers in the standard library. 17// 18// Semiautomatic production of a type specific variant of this package is 19// supported via 20// 21// $ make generic 22// 23// This command will write to stdout a version of the btree.go file where 24// every key type occurrence is replaced by the word 'key' (written in all 25// CAPS) and every value type occurrence is replaced by the word 'value' 26// (written in all CAPS). Then you have to replace these tokens with your 27// desired type(s), using any technique you're comfortable with. 28// 29// This is how, for example, 'example/int.go' was created: 30// 31// $ mkdir example 32// $ 33// $ # Note: the command bellow must be actually written using the words 34// $ # 'key' and 'value' in all CAPS. The proper form is avoided in this 35// $ # documentation to not confuse any text replacement mechanism. 36// $ 37// $ make generic | sed -e 's/key/int/g' -e 's/value/int/g' > example/int.go 38// 39// No other changes to int.go are necessary, it compiles just fine. 40// 41// Running the benchmarks for 1000 keys on a machine with Intel i5-4670 CPU @ 42// 3.4GHz, Go release 1.3. 43// 44// $ go test -bench 1e3 example/all_test.go example/int.go 45// PASS 46// BenchmarkSetSeq1e3 10000 146740 ns/op 47// BenchmarkGetSeq1e3 10000 108261 ns/op 48// BenchmarkSetRnd1e3 10000 254359 ns/op 49// BenchmarkGetRnd1e3 10000 134621 ns/op 50// BenchmarkDelRnd1e3 10000 211864 ns/op 51// BenchmarkSeekSeq1e3 10000 148628 ns/op 52// BenchmarkSeekRnd1e3 10000 215166 ns/op 53// BenchmarkNext1e3 200000 9211 ns/op 54// BenchmarkPrev1e3 200000 8843 ns/op 55// ok command-line-arguments 25.071s 56// $ 57package memstore 58 59import ( 60 "fmt" 61 "io" 62 "sync" 63) 64 65const ( 66 kx = 32 //TODO benchmark tune this number if using custom key/value type(s). 67 kd = 32 //TODO benchmark tune this number if using custom key/value type(s). 68) 69 70func init() { 71 if kd < 1 { 72 panic(fmt.Errorf("kd %d: out of range", kd)) 73 } 74 75 if kx < 2 { 76 panic(fmt.Errorf("kx %d: out of range", kx)) 77 } 78} 79 80var ( 81 btDPool = sync.Pool{New: func() interface{} { return &d{} }} 82 btEPool = btEpool{sync.Pool{New: func() interface{} { return &Enumerator{} }}} 83 btTPool = btTpool{sync.Pool{New: func() interface{} { return &Tree{} }}} 84 btXPool = sync.Pool{New: func() interface{} { return &x{} }} 85) 86 87type btTpool struct{ sync.Pool } 88 89func (p *btTpool) get(cmp Cmp) *Tree { 90 x := p.Get().(*Tree) 91 x.cmp = cmp 92 return x 93} 94 95type btEpool struct{ sync.Pool } 96 97func (p *btEpool) get(err error, hit bool, i int, k int64, q *d, t *Tree, ver int64) *Enumerator { 98 x := p.Get().(*Enumerator) 99 x.err, x.hit, x.i, x.k, x.q, x.t, x.ver = err, hit, i, k, q, t, ver 100 return x 101} 102 103type ( 104 // Cmp compares a and b. Return value is: 105 // 106 // < 0 if a < b 107 // 0 if a == b 108 // > 0 if a > b 109 // 110 Cmp func(a, b int64) int 111 112 d struct { // data page 113 c int 114 d [2*kd + 1]de 115 n *d 116 p *d 117 } 118 119 de struct { // d element 120 k int64 121 v *primitive 122 } 123 124 // Enumerator captures the state of enumerating a tree. It is returned 125 // from the Seek* methods. The enumerator is aware of any mutations 126 // made to the tree in the process of enumerating it and automatically 127 // resumes the enumeration at the proper key, if possible. 128 // 129 // However, once an Enumerator returns io.EOF to signal "no more 130 // items", it does no more attempt to "resync" on tree mutation(s). In 131 // other words, io.EOF from an Enumaretor is "sticky" (idempotent). 132 Enumerator struct { 133 err error 134 hit bool 135 i int 136 k int64 137 q *d 138 t *Tree 139 ver int64 140 } 141 142 // Tree is a B+tree. 143 Tree struct { 144 c int 145 cmp Cmp 146 first *d 147 last *d 148 r interface{} 149 ver int64 150 } 151 152 xe struct { // x element 153 ch interface{} 154 k int64 155 } 156 157 x struct { // index page 158 c int 159 x [2*kx + 2]xe 160 } 161) 162 163var ( // R/O zero values 164 zd d 165 zde de 166 ze Enumerator 167 zk int64 168 zt Tree 169 zx x 170 zxe xe 171) 172 173func clr(q interface{}) { 174 switch x := q.(type) { 175 case *x: 176 for i := 0; i <= x.c; i++ { // Ch0 Sep0 ... Chn-1 Sepn-1 Chn 177 clr(x.x[i].ch) 178 } 179 *x = zx 180 btXPool.Put(x) 181 case *d: 182 *x = zd 183 btDPool.Put(x) 184 } 185} 186 187// -------------------------------------------------------------------------- x 188 189func newX(ch0 interface{}) *x { 190 r := btXPool.Get().(*x) 191 r.x[0].ch = ch0 192 return r 193} 194 195func (q *x) extract(i int) { 196 q.c-- 197 if i < q.c { 198 copy(q.x[i:], q.x[i+1:q.c+1]) 199 q.x[q.c].ch = q.x[q.c+1].ch 200 q.x[q.c].k = zk // GC 201 q.x[q.c+1] = zxe // GC 202 } 203} 204 205func (q *x) insert(i int, k int64, ch interface{}) *x { 206 c := q.c 207 if i < c { 208 q.x[c+1].ch = q.x[c].ch 209 copy(q.x[i+2:], q.x[i+1:c]) 210 q.x[i+1].k = q.x[i].k 211 } 212 c++ 213 q.c = c 214 q.x[i].k = k 215 q.x[i+1].ch = ch 216 return q 217} 218 219func (q *x) siblings(i int) (l, r *d) { 220 if i >= 0 { 221 if i > 0 { 222 l = q.x[i-1].ch.(*d) 223 } 224 if i < q.c { 225 r = q.x[i+1].ch.(*d) 226 } 227 } 228 return 229} 230 231// -------------------------------------------------------------------------- d 232 233func (l *d) mvL(r *d, c int) { 234 copy(l.d[l.c:], r.d[:c]) 235 copy(r.d[:], r.d[c:r.c]) 236 l.c += c 237 r.c -= c 238} 239 240func (l *d) mvR(r *d, c int) { 241 copy(r.d[c:], r.d[:r.c]) 242 copy(r.d[:c], l.d[l.c-c:]) 243 r.c += c 244 l.c -= c 245} 246 247// ----------------------------------------------------------------------- Tree 248 249// TreeNew returns a newly created, empty Tree. The compare function is used 250// for key collation. 251func TreeNew(cmp Cmp) *Tree { 252 return btTPool.get(cmp) 253} 254 255// Clear removes all K/V pairs from the tree. 256func (t *Tree) Clear() { 257 if t.r == nil { 258 return 259 } 260 261 clr(t.r) 262 t.c, t.first, t.last, t.r = 0, nil, nil, nil 263 t.ver++ 264} 265 266// Close performs Clear and recycles t to a pool for possible later reuse. No 267// references to t should exist or such references must not be used afterwards. 268func (t *Tree) Close() { 269 t.Clear() 270 *t = zt 271 btTPool.Put(t) 272} 273 274func (t *Tree) cat(p *x, q, r *d, pi int) { 275 t.ver++ 276 q.mvL(r, r.c) 277 if r.n != nil { 278 r.n.p = q 279 } else { 280 t.last = q 281 } 282 q.n = r.n 283 *r = zd 284 btDPool.Put(r) 285 if p.c > 1 { 286 p.extract(pi) 287 p.x[pi].ch = q 288 } else { 289 switch x := t.r.(type) { 290 case *x: 291 *x = zx 292 btXPool.Put(x) 293 case *d: 294 *x = zd 295 btDPool.Put(x) 296 } 297 t.r = q 298 } 299} 300 301func (t *Tree) catX(p, q, r *x, pi int) { 302 t.ver++ 303 q.x[q.c].k = p.x[pi].k 304 copy(q.x[q.c+1:], r.x[:r.c]) 305 q.c += r.c + 1 306 q.x[q.c].ch = r.x[r.c].ch 307 *r = zx 308 btXPool.Put(r) 309 if p.c > 1 { 310 p.c-- 311 pc := p.c 312 if pi < pc { 313 p.x[pi].k = p.x[pi+1].k 314 copy(p.x[pi+1:], p.x[pi+2:pc+1]) 315 p.x[pc].ch = p.x[pc+1].ch 316 p.x[pc].k = zk // GC 317 p.x[pc+1].ch = nil // GC 318 } 319 return 320 } 321 322 switch x := t.r.(type) { 323 case *x: 324 *x = zx 325 btXPool.Put(x) 326 case *d: 327 *x = zd 328 btDPool.Put(x) 329 } 330 t.r = q 331} 332 333// Delete removes the k's KV pair, if it exists, in which case Delete returns 334// true. 335func (t *Tree) Delete(k int64) (ok bool) { 336 pi := -1 337 var p *x 338 q := t.r 339 if q == nil { 340 return false 341 } 342 343 for { 344 var i int 345 i, ok = t.find(q, k) 346 if ok { 347 switch x := q.(type) { 348 case *x: 349 if x.c < kx && q != t.r { 350 x, i = t.underflowX(p, x, pi, i) 351 } 352 pi = i + 1 353 p = x 354 q = x.x[pi].ch 355 ok = false 356 continue 357 case *d: 358 t.extract(x, i) 359 if x.c >= kd { 360 return true 361 } 362 363 if q != t.r { 364 t.underflow(p, x, pi) 365 } else if t.c == 0 { 366 t.Clear() 367 } 368 return true 369 } 370 } 371 372 switch x := q.(type) { 373 case *x: 374 if x.c < kx && q != t.r { 375 x, i = t.underflowX(p, x, pi, i) 376 } 377 pi = i 378 p = x 379 q = x.x[i].ch 380 case *d: 381 return false 382 } 383 } 384} 385 386func (t *Tree) extract(q *d, i int) { // (r *primitive) { 387 t.ver++ 388 //r = q.d[i].v // prepared for Extract 389 q.c-- 390 if i < q.c { 391 copy(q.d[i:], q.d[i+1:q.c+1]) 392 } 393 q.d[q.c] = zde // GC 394 t.c-- 395 return 396} 397 398func (t *Tree) find(q interface{}, k int64) (i int, ok bool) { 399 var mk int64 400 l := 0 401 switch x := q.(type) { 402 case *x: 403 h := x.c - 1 404 for l <= h { 405 m := (l + h) >> 1 406 mk = x.x[m].k 407 switch cmp := t.cmp(k, mk); { 408 case cmp > 0: 409 l = m + 1 410 case cmp == 0: 411 return m, true 412 default: 413 h = m - 1 414 } 415 } 416 case *d: 417 h := x.c - 1 418 for l <= h { 419 m := (l + h) >> 1 420 mk = x.d[m].k 421 switch cmp := t.cmp(k, mk); { 422 case cmp > 0: 423 l = m + 1 424 case cmp == 0: 425 return m, true 426 default: 427 h = m - 1 428 } 429 } 430 } 431 return l, false 432} 433 434// First returns the first item of the tree in the key collating order, or 435// (zero-value, zero-value) if the tree is empty. 436func (t *Tree) First() (k int64, v *primitive) { 437 if q := t.first; q != nil { 438 q := &q.d[0] 439 k, v = q.k, q.v 440 } 441 return 442} 443 444// Get returns the value associated with k and true if it exists. Otherwise Get 445// returns (zero-value, false). 446func (t *Tree) Get(k int64) (v *primitive, ok bool) { 447 q := t.r 448 if q == nil { 449 return 450 } 451 452 for { 453 var i int 454 if i, ok = t.find(q, k); ok { 455 switch x := q.(type) { 456 case *x: 457 q = x.x[i+1].ch 458 continue 459 case *d: 460 return x.d[i].v, true 461 } 462 } 463 switch x := q.(type) { 464 case *x: 465 q = x.x[i].ch 466 default: 467 return 468 } 469 } 470} 471 472func (t *Tree) insert(q *d, i int, k int64, v *primitive) *d { 473 t.ver++ 474 c := q.c 475 if i < c { 476 copy(q.d[i+1:], q.d[i:c]) 477 } 478 c++ 479 q.c = c 480 q.d[i].k, q.d[i].v = k, v 481 t.c++ 482 return q 483} 484 485// Last returns the last item of the tree in the key collating order, or 486// (zero-value, zero-value) if the tree is empty. 487func (t *Tree) Last() (k int64, v *primitive) { 488 if q := t.last; q != nil { 489 q := &q.d[q.c-1] 490 k, v = q.k, q.v 491 } 492 return 493} 494 495// Len returns the number of items in the tree. 496func (t *Tree) Len() int { 497 return t.c 498} 499 500func (t *Tree) overflow(p *x, q *d, pi, i int, k int64, v *primitive) { 501 t.ver++ 502 l, r := p.siblings(pi) 503 504 if l != nil && l.c < 2*kd { 505 l.mvL(q, 1) 506 t.insert(q, i-1, k, v) 507 p.x[pi-1].k = q.d[0].k 508 return 509 } 510 511 if r != nil && r.c < 2*kd { 512 if i < 2*kd { 513 q.mvR(r, 1) 514 t.insert(q, i, k, v) 515 p.x[pi].k = r.d[0].k 516 } else { 517 t.insert(r, 0, k, v) 518 p.x[pi].k = k 519 } 520 return 521 } 522 523 t.split(p, q, pi, i, k, v) 524} 525 526// Seek returns an Enumerator positioned on a an item such that k >= item's 527// key. ok reports if k == item.key The Enumerator's position is possibly 528// after the last item in the tree. 529func (t *Tree) Seek(k int64) (e *Enumerator, ok bool) { 530 q := t.r 531 if q == nil { 532 e = btEPool.get(nil, false, 0, k, nil, t, t.ver) 533 return 534 } 535 536 for { 537 var i int 538 if i, ok = t.find(q, k); ok { 539 switch x := q.(type) { 540 case *x: 541 q = x.x[i+1].ch 542 continue 543 case *d: 544 return btEPool.get(nil, ok, i, k, x, t, t.ver), true 545 } 546 } 547 548 switch x := q.(type) { 549 case *x: 550 q = x.x[i].ch 551 case *d: 552 return btEPool.get(nil, ok, i, k, x, t, t.ver), false 553 } 554 } 555} 556 557// SeekFirst returns an enumerator positioned on the first KV pair in the tree, 558// if any. For an empty tree, err == io.EOF is returned and e will be nil. 559func (t *Tree) SeekFirst() (e *Enumerator, err error) { 560 q := t.first 561 if q == nil { 562 return nil, io.EOF 563 } 564 565 return btEPool.get(nil, true, 0, q.d[0].k, q, t, t.ver), nil 566} 567 568// SeekLast returns an enumerator positioned on the last KV pair in the tree, 569// if any. For an empty tree, err == io.EOF is returned and e will be nil. 570func (t *Tree) SeekLast() (e *Enumerator, err error) { 571 q := t.last 572 if q == nil { 573 return nil, io.EOF 574 } 575 576 return btEPool.get(nil, true, q.c-1, q.d[q.c-1].k, q, t, t.ver), nil 577} 578 579// Set sets the value associated with k. 580func (t *Tree) Set(k int64, v *primitive) { 581 //dbg("--- PRE Set(%v, %v)\n%s", k, v, t.dump()) 582 //defer func() { 583 // dbg("--- POST\n%s\n====\n", t.dump()) 584 //}() 585 586 pi := -1 587 var p *x 588 q := t.r 589 if q == nil { 590 z := t.insert(btDPool.Get().(*d), 0, k, v) 591 t.r, t.first, t.last = z, z, z 592 return 593 } 594 595 for { 596 i, ok := t.find(q, k) 597 if ok { 598 switch x := q.(type) { 599 case *x: 600 if x.c > 2*kx { 601 x, i = t.splitX(p, x, pi, i) 602 } 603 pi = i + 1 604 p = x 605 q = x.x[i+1].ch 606 continue 607 case *d: 608 x.d[i].v = v 609 } 610 return 611 } 612 613 switch x := q.(type) { 614 case *x: 615 if x.c > 2*kx { 616 x, i = t.splitX(p, x, pi, i) 617 } 618 pi = i 619 p = x 620 q = x.x[i].ch 621 case *d: 622 switch { 623 case x.c < 2*kd: 624 t.insert(x, i, k, v) 625 default: 626 t.overflow(p, x, pi, i, k, v) 627 } 628 return 629 } 630 } 631} 632 633// Put combines Get and Set in a more efficient way where the tree is walked 634// only once. The upd(ater) receives (old-value, true) if a KV pair for k 635// exists or (zero-value, false) otherwise. It can then return a (new-value, 636// true) to create or overwrite the existing value in the KV pair, or 637// (whatever, false) if it decides not to create or not to update the value of 638// the KV pair. 639// 640// tree.Set(k, v) call conceptually equals calling 641// 642// tree.Put(k, func(int64, bool){ return v, true }) 643// 644// modulo the differing return values. 645func (t *Tree) Put(k int64, upd func(oldV *primitive, exists bool) (newV *primitive, write bool)) (oldV *primitive, written bool) { 646 pi := -1 647 var p *x 648 q := t.r 649 var newV *primitive 650 if q == nil { 651 // new KV pair in empty tree 652 newV, written = upd(newV, false) 653 if !written { 654 return 655 } 656 657 z := t.insert(btDPool.Get().(*d), 0, k, newV) 658 t.r, t.first, t.last = z, z, z 659 return 660 } 661 662 for { 663 i, ok := t.find(q, k) 664 if ok { 665 switch x := q.(type) { 666 case *x: 667 if x.c > 2*kx { 668 x, i = t.splitX(p, x, pi, i) 669 } 670 pi = i + 1 671 p = x 672 q = x.x[i+1].ch 673 continue 674 case *d: 675 oldV = x.d[i].v 676 newV, written = upd(oldV, true) 677 if !written { 678 return 679 } 680 681 x.d[i].v = newV 682 } 683 return 684 } 685 686 switch x := q.(type) { 687 case *x: 688 if x.c > 2*kx { 689 x, i = t.splitX(p, x, pi, i) 690 } 691 pi = i 692 p = x 693 q = x.x[i].ch 694 case *d: // new KV pair 695 newV, written = upd(newV, false) 696 if !written { 697 return 698 } 699 700 switch { 701 case x.c < 2*kd: 702 t.insert(x, i, k, newV) 703 default: 704 t.overflow(p, x, pi, i, k, newV) 705 } 706 return 707 } 708 } 709} 710 711func (t *Tree) split(p *x, q *d, pi, i int, k int64, v *primitive) { 712 t.ver++ 713 r := btDPool.Get().(*d) 714 if q.n != nil { 715 r.n = q.n 716 r.n.p = r 717 } else { 718 t.last = r 719 } 720 q.n = r 721 r.p = q 722 723 copy(r.d[:], q.d[kd:2*kd]) 724 for i := range q.d[kd:] { 725 q.d[kd+i] = zde 726 } 727 q.c = kd 728 r.c = kd 729 var done bool 730 if i > kd { 731 done = true 732 t.insert(r, i-kd, k, v) 733 } 734 if pi >= 0 { 735 p.insert(pi, r.d[0].k, r) 736 } else { 737 t.r = newX(q).insert(0, r.d[0].k, r) 738 } 739 if done { 740 return 741 } 742 743 t.insert(q, i, k, v) 744} 745 746func (t *Tree) splitX(p *x, q *x, pi int, i int) (*x, int) { 747 t.ver++ 748 r := btXPool.Get().(*x) 749 copy(r.x[:], q.x[kx+1:]) 750 q.c = kx 751 r.c = kx 752 if pi >= 0 { 753 p.insert(pi, q.x[kx].k, r) 754 q.x[kx].k = zk 755 for i := range q.x[kx+1:] { 756 q.x[kx+i+1] = zxe 757 } 758 759 switch { 760 case i < kx: 761 return q, i 762 case i == kx: 763 return p, pi 764 default: // i > kx 765 return r, i - kx - 1 766 } 767 } 768 769 nr := newX(q).insert(0, q.x[kx].k, r) 770 t.r = nr 771 q.x[kx].k = zk 772 for i := range q.x[kx+1:] { 773 q.x[kx+i+1] = zxe 774 } 775 776 switch { 777 case i < kx: 778 return q, i 779 case i == kx: 780 return nr, 0 781 default: // i > kx 782 return r, i - kx - 1 783 } 784} 785 786func (t *Tree) underflow(p *x, q *d, pi int) { 787 t.ver++ 788 l, r := p.siblings(pi) 789 790 if l != nil && l.c+q.c >= 2*kd { 791 l.mvR(q, 1) 792 p.x[pi-1].k = q.d[0].k 793 } else if r != nil && q.c+r.c >= 2*kd { 794 q.mvL(r, 1) 795 p.x[pi].k = r.d[0].k 796 r.d[r.c] = zde // GC 797 } else if l != nil { 798 t.cat(p, l, q, pi-1) 799 } else { 800 t.cat(p, q, r, pi) 801 } 802} 803 804func (t *Tree) underflowX(p *x, q *x, pi int, i int) (*x, int) { 805 t.ver++ 806 var l, r *x 807 808 if pi >= 0 { 809 if pi > 0 { 810 l = p.x[pi-1].ch.(*x) 811 } 812 if pi < p.c { 813 r = p.x[pi+1].ch.(*x) 814 } 815 } 816 817 if l != nil && l.c > kx { 818 q.x[q.c+1].ch = q.x[q.c].ch 819 copy(q.x[1:], q.x[:q.c]) 820 q.x[0].ch = l.x[l.c].ch 821 q.x[0].k = p.x[pi-1].k 822 q.c++ 823 i++ 824 l.c-- 825 p.x[pi-1].k = l.x[l.c].k 826 return q, i 827 } 828 829 if r != nil && r.c > kx { 830 q.x[q.c].k = p.x[pi].k 831 q.c++ 832 q.x[q.c].ch = r.x[0].ch 833 p.x[pi].k = r.x[0].k 834 copy(r.x[:], r.x[1:r.c]) 835 r.c-- 836 rc := r.c 837 r.x[rc].ch = r.x[rc+1].ch 838 r.x[rc].k = zk 839 r.x[rc+1].ch = nil 840 return q, i 841 } 842 843 if l != nil { 844 i += l.c + 1 845 t.catX(p, l, q, pi-1) 846 q = l 847 return q, i 848 } 849 850 t.catX(p, q, r, pi) 851 return q, i 852} 853 854// ----------------------------------------------------------------- Enumerator 855 856// Close recycles e to a pool for possible later reuse. No references to e 857// should exist or such references must not be used afterwards. 858func (e *Enumerator) Close() { 859 *e = ze 860 btEPool.Put(e) 861} 862 863// Next returns the currently enumerated item, if it exists and moves to the 864// next item in the key collation order. If there is no item to return, err == 865// io.EOF is returned. 866func (e *Enumerator) Next() (k int64, v *primitive, err error) { 867 if err = e.err; err != nil { 868 return 869 } 870 871 if e.ver != e.t.ver { 872 f, hit := e.t.Seek(e.k) 873 if !e.hit && hit { 874 if err = f.next(); err != nil { 875 return 876 } 877 } 878 879 *e = *f 880 f.Close() 881 } 882 if e.q == nil { 883 e.err, err = io.EOF, io.EOF 884 return 885 } 886 887 if e.i >= e.q.c { 888 if err = e.next(); err != nil { 889 return 890 } 891 } 892 893 i := e.q.d[e.i] 894 k, v = i.k, i.v 895 e.k, e.hit = k, false 896 e.next() 897 return 898} 899 900func (e *Enumerator) next() error { 901 if e.q == nil { 902 e.err = io.EOF 903 return io.EOF 904 } 905 906 switch { 907 case e.i < e.q.c-1: 908 e.i++ 909 default: 910 if e.q, e.i = e.q.n, 0; e.q == nil { 911 e.err = io.EOF 912 } 913 } 914 return e.err 915} 916 917// Prev returns the currently enumerated item, if it exists and moves to the 918// previous item in the key collation order. If there is no item to return, err 919// == io.EOF is returned. 920func (e *Enumerator) Prev() (k int64, v *primitive, err error) { 921 if err = e.err; err != nil { 922 return 923 } 924 925 if e.ver != e.t.ver { 926 f, hit := e.t.Seek(e.k) 927 if !e.hit && hit { 928 if err = f.prev(); err != nil { 929 return 930 } 931 } 932 933 *e = *f 934 f.Close() 935 } 936 if e.q == nil { 937 e.err, err = io.EOF, io.EOF 938 return 939 } 940 941 if e.i >= e.q.c { 942 if err = e.next(); err != nil { 943 return 944 } 945 } 946 947 i := e.q.d[e.i] 948 k, v = i.k, i.v 949 e.k, e.hit = k, false 950 e.prev() 951 return 952} 953 954func (e *Enumerator) prev() error { 955 if e.q == nil { 956 e.err = io.EOF 957 return io.EOF 958 } 959 960 switch { 961 case e.i > 0: 962 e.i-- 963 default: 964 if e.q = e.q.p; e.q == nil { 965 e.err = io.EOF 966 break 967 } 968 969 e.i = e.q.c - 1 970 } 971 return e.err 972} 973