Line data    Source code

       1             : package pebble
       2             : 
       3             : import "github.com/cockroachdb/pebble/internal/base"
       4             : 
       5             : // The maximum number of elements in the readCompactions queue.
       6             : // We want to limit the number of elements so that we only do
       7             : // compactions for ranges which are being read recently.
       8             : const readCompactionMaxQueueSize = 5
       9             : 
      10             : // The readCompactionQueue is a queue of read compactions with
      11             : // 0 overlapping ranges.
      12             : type readCompactionQueue struct {
      13             :         // Invariant: A contiguous prefix of the queue contains
      14             :         // all the elements in the queue, in order of insertion.
      15             :         // When we remove duplicates from the queue, we break
      16             :         // the invariant that a contiguous prefix of the queue
      17             :         // has all the elements in it. To fix this, we shift
      18             :         // the elements of the queue to the left. This is cheap
      19             :         // because the queue has a max length of 5.
      20             :         queue [readCompactionMaxQueueSize]*readCompaction
      21             : 
      22             :         // The size of the queue which is occupied.
      23             :         // A size of k, implies that the first k elements
      24             :         // of the queue are occupied.
      25             :         // The size will be <= readCompactionMaxQueueSize.
      26             :         size int
      27             : }
      28             : 
      29             : // combine should be used to combine an older queue with a newer
      30             : // queue.
      31           1 : func (qu *readCompactionQueue) combine(newQu *readCompactionQueue, cmp base.Compare) {
      32           1 : 
      33           1 :         for i := 0; i < newQu.size; i++ {
      34           1 :                 qu.add(newQu.queue[i], cmp)
      35           1 :         }
      36             : }
      37             : 
      38             : // add adds read compactions to the queue, while maintaining the invariant
      39             : // that there are no overlapping ranges in the queue.
      40           1 : func (qu *readCompactionQueue) add(rc *readCompaction, cmp base.Compare) {
      41           1 :         sz := qu.size
      42           1 :         for i := 0; i < sz; i++ {
      43           1 :                 left := qu.queue[i]
      44           1 :                 right := rc
      45           1 :                 if cmp(left.start, right.start) > 0 {
      46           1 :                         left, right = right, left
      47           1 :                 }
      48           1 :                 if cmp(right.start, left.end) <= 0 {
      49           1 :                         qu.queue[i] = nil
      50           1 :                         qu.size--
      51           1 :                 }
      52             :         }
      53             : 
      54             :         // Get rid of the holes which may have been formed
      55             :         // in the queue.
      56           1 :         qu.shiftLeft()
      57           1 : 
      58           1 :         if qu.size == readCompactionMaxQueueSize {
      59           1 :                 // Make space at the end.
      60           1 :                 copy(qu.queue[0:], qu.queue[1:])
      61           1 :                 qu.queue[qu.size-1] = rc
      62           1 :         } else {
      63           1 :                 qu.size++
      64           1 :                 qu.queue[qu.size-1] = rc
      65           1 :         }
      66             : }
      67             : 
      68             : // Shifts the non-nil elements of the queue to the left so
      69             : // that a continguous prefix of the queue is non-nil.
      70           1 : func (qu *readCompactionQueue) shiftLeft() {
      71           1 :         nilPos := -1
      72           1 :         for i := 0; i < readCompactionMaxQueueSize; i++ {
      73           1 :                 if qu.queue[i] == nil && nilPos == -1 {
      74           1 :                         nilPos = i
      75           1 :                 } else if qu.queue[i] != nil && nilPos != -1 {
      76           1 :                         qu.queue[nilPos] = qu.queue[i]
      77           1 :                         qu.queue[i] = nil
      78           1 :                         nilPos++
      79           1 :                 }
      80             :         }
      81             : }
      82             : 
      83             : // remove will remove the oldest element from the queue.
      84           1 : func (qu *readCompactionQueue) remove() *readCompaction {
      85           1 :         if qu.size == 0 {
      86           1 :                 return nil
      87           1 :         }
      88             : 
      89           1 :         c := qu.queue[0]
      90           1 :         copy(qu.queue[0:], qu.queue[1:])
      91           1 :         qu.queue[qu.size-1] = nil
      92           1 :         qu.size--
      93           1 :         return c
      94             : }