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 1 : func (h *mergingIterHeap) len() int { 14 1 : return len(h.items) 15 1 : } 16 : 17 1 : func (h *mergingIterHeap) clear() { 18 1 : h.items = h.items[:0] 19 1 : } 20 : 21 1 : func (h *mergingIterHeap) less(i, j int) bool { 22 1 : ikv, jkv := h.items[i].iterKV, h.items[j].iterKV 23 1 : if c := h.cmp(ikv.K.UserKey, jkv.K.UserKey); c != 0 { 24 1 : if h.reverse { 25 1 : return c > 0 26 1 : } 27 1 : return c < 0 28 : } 29 1 : if h.reverse { 30 1 : return ikv.K.Trailer < jkv.K.Trailer 31 1 : } 32 1 : return ikv.K.Trailer > jkv.K.Trailer 33 : } 34 : 35 1 : func (h *mergingIterHeap) swap(i, j int) { 36 1 : h.items[i], h.items[j] = h.items[j], h.items[i] 37 1 : } 38 : 39 : // init, fix, up and down are copied from the go stdlib. 40 1 : func (h *mergingIterHeap) init() { 41 1 : // heapify 42 1 : n := h.len() 43 1 : for i := n/2 - 1; i >= 0; i-- { 44 1 : h.down(i, n) 45 1 : } 46 : } 47 : 48 1 : func (h *mergingIterHeap) fix(i int) { 49 1 : if !h.down(i, h.len()) { 50 1 : h.up(i) 51 1 : } 52 : } 53 : 54 1 : func (h *mergingIterHeap) pop() *mergingIterLevel { 55 1 : n := h.len() - 1 56 1 : h.swap(0, n) 57 1 : h.down(0, n) 58 1 : item := h.items[n] 59 1 : h.items = h.items[:n] 60 1 : return item 61 1 : } 62 : 63 1 : func (h *mergingIterHeap) up(j int) { 64 1 : for { 65 1 : i := (j - 1) / 2 // parent 66 1 : if i == j || !h.less(j, i) { 67 1 : break 68 : } 69 0 : h.swap(i, j) 70 0 : j = i 71 : } 72 : } 73 : 74 1 : func (h *mergingIterHeap) down(i0, n int) bool { 75 1 : i := i0 76 1 : for { 77 1 : j1 := 2*i + 1 78 1 : if j1 >= n || j1 < 0 { // j1 < 0 after int overflow 79 1 : break 80 : } 81 1 : j := j1 // left child 82 1 : if j2 := j1 + 1; j2 < n && h.less(j2, j1) { 83 1 : j = j2 // = 2*i + 2 // right child 84 1 : } 85 1 : if !h.less(j, i) { 86 1 : break 87 : } 88 1 : h.swap(i, j) 89 1 : i = j 90 : } 91 1 : return i > i0 92 : }