hbase-server/src/main/java/org/apache/hadoop/hbase/regionserver/ReversedKeyValueHeap.java

   1 /**
   2  * Copyright The Apache Software Foundation
   3  *
   4  * Licensed to the Apache Software Foundation (ASF) under one or more
   5  * contributor license agreements. See the NOTICE file distributed with this
   6  * work for additional information regarding copyright ownership. The ASF
   7  * licenses this file to you under the Apache License, Version 2.0 (the
   8  * "License"); you may not use this file except in compliance with the License.
   9  * You may obtain a copy of the License at
  10  *
  11  * http://www.apache.org/licenses/LICENSE-2.0
  12  *
  13  * Unless required by applicable law or agreed to in writing, software
  14  * distributed under the License is distributed on an "AS IS" BASIS, WITHOUT
  15  * WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. See the
  16  * License for the specific language governing permissions and limitations
  17  * under the License.
  18  */
  19 package org.apache.hadoop.hbase.regionserver;
  20
  21 import java.io.IOException;
  22 import java.util.List;
  23
  24 import org.apache.commons.lang3.NotImplementedException;
  25 import org.apache.hadoop.hbase.HConstants;
  26 import org.apache.yetus.audience.InterfaceAudience;
  27 import org.apache.hadoop.hbase.Cell;
  28 import org.apache.hadoop.hbase.CellComparator;
  29 import org.apache.hadoop.hbase.CellUtil;
  30
  31 /**
  32  * ReversedKeyValueHeap is used for supporting reversed scanning. Compared with
  33  * KeyValueHeap, its scanner comparator is a little different (see
  34  * ReversedKVScannerComparator), all seek is backward seek(see
  35  * {@link KeyValueScanner#backwardSeek}), and it will jump to the previous row
  36  * if it is already at the end of one row when calling next().
  37  */
  38 @InterfaceAudience.Private
  39 public class ReversedKeyValueHeap extends KeyValueHeap {
  40
  41   /**
  42    * @param scanners
  43    * @param comparator
  44    * @throws IOException
  45    */
  46   public ReversedKeyValueHeap(List<? extends KeyValueScanner> scanners,
  47       CellComparator comparator) throws IOException {
  48     super(scanners, new ReversedKVScannerComparator(comparator));
  49   }
  50
  51   @Override
  52   public boolean seek(Cell seekKey) throws IOException {
  53     throw new IllegalStateException(
  54         "seek cannot be called on ReversedKeyValueHeap");
  55   }
  56
  57   @Override
  58   public boolean reseek(Cell seekKey) throws IOException {
  59     throw new IllegalStateException(
  60         "reseek cannot be called on ReversedKeyValueHeap");
  61   }
  62
  63   @Override
  64   public boolean requestSeek(Cell key, boolean forward, boolean useBloom)
  65       throws IOException {
  66     throw new IllegalStateException(
  67         "requestSeek cannot be called on ReversedKeyValueHeap");
  68   }
  69
  70   @Override
  71   public boolean seekToPreviousRow(Cell seekKey) throws IOException {
  72     if (current == null) {
  73       return false;
  74     }
  75     heap.add(current);
  76     current = null;
  77
  78     KeyValueScanner scanner;
  79     while ((scanner = heap.poll()) != null) {
  80       Cell topKey = scanner.peek();
  81       if (comparator.getComparator().compareRows(topKey, seekKey) < 0) {
  82         // Row of Top KeyValue is before Seek row.
  83         heap.add(scanner);
  84         current = pollRealKV();
  85         return current != null;
  86       }
  87
  88       if (!scanner.seekToPreviousRow(seekKey)) {
  89         this.scannersForDelayedClose.add(scanner);
  90       } else {
  91         heap.add(scanner);
  92       }
  93     }
  94
  95     // Heap is returning empty, scanner is done
  96     return false;
  97   }
  98
  99   @Override
 100   public boolean backwardSeek(Cell seekKey) throws IOException {
 101     if (current == null) {
 102       return false;
 103     }
 104     heap.add(current);
 105     current = null;
 106
 107     KeyValueScanner scanner;
 108     while ((scanner = heap.poll()) != null) {
 109       Cell topKey = scanner.peek();
 110       if ((CellUtil.matchingRows(seekKey, topKey) && comparator
 111           .getComparator().compare(seekKey, topKey) <= 0)
 112           || comparator.getComparator().compareRows(seekKey, topKey) > 0) {
 113         heap.add(scanner);
 114         current = pollRealKV();
 115         return current != null;
 116       }
 117       if (!scanner.backwardSeek(seekKey)) {
 118         this.scannersForDelayedClose.add(scanner);
 119       } else {
 120         heap.add(scanner);
 121       }
 122     }
 123     return false;
 124   }
 125
 126   @Override
 127   public Cell next() throws IOException {
 128     if (this.current == null) {
 129       return null;
 130     }
 131     Cell kvReturn = this.current.next();
 132     Cell kvNext = this.current.peek();
 133     if (kvNext == null
 134         || this.comparator.kvComparator.compareRows(kvNext, kvReturn) > 0) {
 135       if (this.current.seekToPreviousRow(kvReturn)) {
 136         this.heap.add(this.current);
 137       } else {
 138         this.scannersForDelayedClose.add(this.current);
 139       }
 140       this.current = null;
 141       this.current = pollRealKV();
 142     } else {
 143       KeyValueScanner topScanner = this.heap.peek();
 144       if (topScanner != null
 145           && this.comparator.compare(this.current, topScanner) > 0) {
 146         this.heap.add(this.current);
 147         this.current = null;
 148         this.current = pollRealKV();
 149       }
 150     }
 151     return kvReturn;
 152   }
 153
 154   /**
 155    * In ReversedKVScannerComparator, we compare the row of scanners' peek values
 156    * first, sort bigger one before the smaller one. Then compare the KeyValue if
 157    * they have the equal row, sort smaller one before the bigger one
 158    */
 159   private static class ReversedKVScannerComparator extends
 160       KVScannerComparator {
 161
 162     /**
 163      * Constructor
 164      * @param kvComparator
 165      */
 166     public ReversedKVScannerComparator(CellComparator kvComparator) {
 167       super(kvComparator);
 168     }
 169
 170     @Override
 171     public int compare(KeyValueScanner left, KeyValueScanner right) {
 172       int rowComparison = compareRows(left.peek(), right.peek());
 173       if (rowComparison != 0) {
 174         return -rowComparison;
 175       }
 176       return super.compare(left, right);
 177     }
 178
 179     /**
 180      * Compares rows of two KeyValue
 181      * @param left
 182      * @param right
 183      * @return less than 0 if left is smaller, 0 if equal etc..
 184      */
 185     public int compareRows(Cell left, Cell right) {
 186       return super.kvComparator.compareRows(left, right);
 187     }
 188   }
 189
 190   @Override
 191   public boolean seekToLastRow() throws IOException {
 192     throw new NotImplementedException(HConstants.NOT_IMPLEMENTED);
 193   }
 194 }