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            0 : func (qu *readCompactionQueue) combine(newQu *readCompactionQueue, cmp base.Compare) {
      32            0 : 
      33            0 :         for i := 0; i < newQu.size; i++ {
      34            0 :                 qu.add(newQu.queue[i], cmp)
      35            0 :         }
      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            0 : func (qu *readCompactionQueue) add(rc *readCompaction, cmp base.Compare) {
      41            0 :         sz := qu.size
      42            0 :         for i := 0; i < sz; i++ {
      43            0 :                 left := qu.queue[i]
      44            0 :                 right := rc
      45            0 :                 if cmp(left.start, right.start) > 0 {
      46            0 :                         left, right = right, left
      47            0 :                 }
      48            0 :                 if cmp(right.start, left.end) <= 0 {
      49            0 :                         qu.queue[i] = nil
      50            0 :                         qu.size--
      51            0 :                 }
      52              :         }
      53              : 
      54              :         // Get rid of the holes which may have been formed
      55              :         // in the queue.
      56            0 :         qu.shiftLeft()
      57            0 : 
      58            0 :         if qu.size == readCompactionMaxQueueSize {
      59            0 :                 // Make space at the end.
      60            0 :                 copy(qu.queue[0:], qu.queue[1:])
      61            0 :                 qu.queue[qu.size-1] = rc
      62            0 :         } else {
      63            0 :                 qu.size++
      64            0 :                 qu.queue[qu.size-1] = rc
      65            0 :         }
      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            0 : func (qu *readCompactionQueue) shiftLeft() {
      71            0 :         nilPos := -1
      72            0 :         for i := 0; i < readCompactionMaxQueueSize; i++ {
      73            0 :                 if qu.queue[i] == nil && nilPos == -1 {
      74            0 :                         nilPos = i
      75            0 :                 } else if qu.queue[i] != nil && nilPos != -1 {
      76            0 :                         qu.queue[nilPos] = qu.queue[i]
      77            0 :                         qu.queue[i] = nil
      78            0 :                         nilPos++
      79            0 :                 }
      80              :         }
      81              : }
      82              : 
      83              : // remove will remove the oldest element from the queue.
      84            0 : func (qu *readCompactionQueue) remove() *readCompaction {
      85            0 :         if qu.size == 0 {
      86            0 :                 return nil
      87            0 :         }
      88              : 
      89            0 :         c := qu.queue[0]
      90            0 :         copy(qu.queue[0:], qu.queue[1:])
      91            0 :         qu.queue[qu.size-1] = nil
      92            0 :         qu.size--
      93            0 :         return c
      94              : }