Line data Source code
1 : // Copyright 2018 The LevelDB-Go and Pebble Authors. All rights reserved. Use 2 : // of this source code is governed by a BSD-style license that can be found in 3 : // the LICENSE file. 4 : 5 : package pebble 6 : 7 : type mergingIterHeap struct { 8 : cmp Compare 9 : reverse bool 10 : items []*mergingIterLevel 11 : } 12 : 13 2 : func (h *mergingIterHeap) len() int { 14 2 : return len(h.items) 15 2 : } 16 : 17 2 : func (h *mergingIterHeap) clear() { 18 2 : h.items = h.items[:0] 19 2 : } 20 : 21 2 : func (h *mergingIterHeap) less(i, j int) bool { 22 2 : ikey, jkey := h.items[i].iterKey, h.items[j].iterKey 23 2 : if c := h.cmp(ikey.UserKey, jkey.UserKey); c != 0 { 24 2 : if h.reverse { 25 2 : return c > 0 26 2 : } 27 2 : return c < 0 28 : } 29 2 : if h.reverse { 30 2 : return ikey.Trailer < jkey.Trailer 31 2 : } 32 2 : return ikey.Trailer > jkey.Trailer 33 : } 34 : 35 2 : func (h *mergingIterHeap) swap(i, j int) { 36 2 : h.items[i], h.items[j] = h.items[j], h.items[i] 37 2 : } 38 : 39 : // init, fix, up and down are copied from the go stdlib. 40 2 : func (h *mergingIterHeap) init() { 41 2 : // heapify 42 2 : n := h.len() 43 2 : for i := n/2 - 1; i >= 0; i-- { 44 2 : h.down(i, n) 45 2 : } 46 : } 47 : 48 2 : func (h *mergingIterHeap) fix(i int) { 49 2 : if !h.down(i, h.len()) { 50 2 : h.up(i) 51 2 : } 52 : } 53 : 54 2 : func (h *mergingIterHeap) pop() *mergingIterLevel { 55 2 : n := h.len() - 1 56 2 : h.swap(0, n) 57 2 : h.down(0, n) 58 2 : item := h.items[n] 59 2 : h.items = h.items[:n] 60 2 : return item 61 2 : } 62 : 63 2 : func (h *mergingIterHeap) up(j int) { 64 2 : for { 65 2 : i := (j - 1) / 2 // parent 66 2 : if i == j || !h.less(j, i) { 67 2 : break 68 : } 69 0 : h.swap(i, j) 70 0 : j = i 71 : } 72 : } 73 : 74 2 : func (h *mergingIterHeap) down(i0, n int) bool { 75 2 : i := i0 76 2 : for { 77 2 : j1 := 2*i + 1 78 2 : if j1 >= n || j1 < 0 { // j1 < 0 after int overflow 79 2 : break 80 : } 81 2 : j := j1 // left child 82 2 : if j2 := j1 + 1; j2 < n && h.less(j2, j1) { 83 2 : j = j2 // = 2*i + 2 // right child 84 2 : } 85 2 : if !h.less(j, i) { 86 2 : break 87 : } 88 2 : h.swap(i, j) 89 2 : i = j 90 : } 91 2 : return i > i0 92 : }