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              : import "github.com/cockroachdb/pebble/internal/invariants"
       8              : 
       9              : // mergingIterHeap is a heap of mergingIterLevels. It only reads
      10              : // mergingIterLevel.iterKV.K.
      11              : //
      12              : // REQUIRES: Every mergingIterLevel.iterKV is non-nil.
      13              : //
      14              : // TODO(sumeer): consider using golang generics.
      15              : type mergingIterHeap struct {
      16              :         cmp     Compare
      17              :         reverse bool
      18              :         items   []mergingIterHeapItem
      19              : }
      20              : 
      21              : type mergingIterHeapItem struct {
      22              :         *mergingIterLevel
      23              :         winnerChild winnerChild
      24              : }
      25              : 
      26              : // winnerChild represents the child that is less than the other child, i.e.,
      27              : // would get promoted up the heap before the other child if the parent was
      28              : // removed, or the parent's value "increased".
      29              : //
      30              : // It can be unknown, represented by winnerChildUnknown. If both children are
      31              : // equal, or if there is only one child, any of the three values are
      32              : // permitted.
      33              : type winnerChild uint8
      34              : 
      35              : const (
      36              :         winnerChildUnknown winnerChild = iota
      37              :         winnerChildLeft
      38              :         winnerChildRight
      39              : )
      40              : 
      41              : // len returns the number of elements in the heap.
      42            1 : func (h *mergingIterHeap) len() int {
      43            1 :         return len(h.items)
      44            1 : }
      45              : 
      46              : // clear empties the heap.
      47            1 : func (h *mergingIterHeap) clear() {
      48            1 :         h.items = h.items[:0]
      49            1 : }
      50              : 
      51              : // less is an internal method, to compare the elements at i and j.
      52            1 : func (h *mergingIterHeap) less(i, j int) bool {
      53            1 :         ikv, jkv := h.items[i].iterKV, h.items[j].iterKV
      54            1 :         if c := h.cmp(ikv.K.UserKey, jkv.K.UserKey); c != 0 {
      55            1 :                 if h.reverse {
      56            1 :                         return c > 0
      57            1 :                 }
      58            1 :                 return c < 0
      59              :         }
      60            1 :         if h.reverse {
      61            1 :                 return ikv.K.Trailer < jkv.K.Trailer
      62            1 :         }
      63            1 :         return ikv.K.Trailer > jkv.K.Trailer
      64              : }
      65              : 
      66              : // swap is an internal method, used to swap the elements at i and j.
      67            1 : func (h *mergingIterHeap) swap(i, j int) {
      68            1 :         h.items[i].mergingIterLevel, h.items[j].mergingIterLevel =
      69            1 :                 h.items[j].mergingIterLevel, h.items[i].mergingIterLevel
      70            1 : }
      71              : 
      72              : // init initializes the heap.
      73            1 : func (h *mergingIterHeap) init() {
      74            1 :         // heapify
      75            1 :         n := h.len()
      76            1 :         for i := n/2 - 1; i >= 0; i-- {
      77            1 :                 h.down(i, n)
      78            1 :         }
      79              : }
      80              : 
      81              : // fixTop restores the heap property after the top of the heap has been
      82              : // modified.
      83            1 : func (h *mergingIterHeap) fixTop() {
      84            1 :         h.down(0, h.len())
      85            1 : }
      86              : 
      87              : // pop removes the top of the heap.
      88            1 : func (h *mergingIterHeap) pop() *mergingIterLevel {
      89            1 :         n := h.len() - 1
      90            1 :         h.swap(0, n)
      91            1 :         // Parent of n does not know which child is the winner. But since index n is
      92            1 :         // removed, the parent of n will have at most one child, and so the value of
      93            1 :         // winnerChild is irrelevant, and we don't need to do:
      94            1 :         //  h.items[(n-1)/2].winnerChild = winnerChildUnknown
      95            1 :         h.down(0, n)
      96            1 :         item := h.items[n]
      97            1 :         h.items = h.items[:n]
      98            1 :         return item.mergingIterLevel
      99            1 : }
     100              : 
     101              : // down is an internal method. It moves i down the heap, which has length n,
     102              : // until the heap property is restored.
     103            1 : func (h *mergingIterHeap) down(i, n int) {
     104            1 :         for {
     105            1 :                 j1 := 2*i + 1
     106            1 :                 if j1 >= n || j1 < 0 { // j1 < 0 after int overflow
     107            1 :                         break
     108              :                 }
     109            1 :                 j := j1 // left child
     110            1 :                 if j2 := j1 + 1; j2 < n {
     111            1 :                         if h.items[i].winnerChild == winnerChildUnknown {
     112            1 :                                 if h.less(j2, j1) {
     113            1 :                                         h.items[i].winnerChild = winnerChildRight
     114            1 :                                 } else {
     115            1 :                                         h.items[i].winnerChild = winnerChildLeft
     116            1 :                                 }
     117            1 :                         } else if invariants.Enabled {
     118            1 :                                 wc := winnerChildUnknown
     119            1 :                                 if h.less(j1, j2) {
     120            1 :                                         wc = winnerChildLeft
     121            1 :                                 } else if h.less(j2, j1) {
     122            1 :                                         wc = winnerChildRight
     123            1 :                                 }
     124            1 :                                 if wc != winnerChildUnknown && wc != h.items[i].winnerChild {
     125            0 :                                         panic("winnerChild mismatch")
     126              :                                 }
     127              :                         }
     128            1 :                         if h.items[i].winnerChild == winnerChildRight {
     129            1 :                                 j = j2 // = 2*i + 2  // right child
     130            1 :                         }
     131              :                 }
     132            1 :                 if !h.less(j, i) {
     133            1 :                         break
     134              :                 }
     135              :                 // NB: j is a child of i.
     136            1 :                 h.swap(i, j)
     137            1 :                 h.items[i].winnerChild = winnerChildUnknown
     138            1 :                 i = j
     139              :         }
     140              : }