hbase-commits mailing list archives

Site index · List index
Message view « Date » · « Thread »
Top « Date » · « Thread »
From ramkris...@apache.org
Subject svn commit: r1583031 [1/2] - in /hbase/trunk: hbase-common/src/main/java/org/apache/hadoop/hbase/ hbase-common/src/main/java/org/apache/hadoop/hbase/io/encoding/ hbase-common/src/main/java/org/apache/hadoop/hbase/util/ hbase-common/src/test/java/org/ap...
Date Sat, 29 Mar 2014 17:18:57 GMT
Author: ramkrishna
Date: Sat Mar 29 17:18:56 2014
New Revision: 1583031

URL: http://svn.apache.org/r1583031
Log:
HBASE-10531-Revisit how the key byte[] is passed to HFileScanner.seekTo and reseekTo (Ram)

Added:
    hbase/trunk/hbase-common/src/test/java/org/apache/hadoop/hbase/TestCellComparator.java
    hbase/trunk/hbase-server/src/test/java/org/apache/hadoop/hbase/io/encoding/TestSeekToBlockWithEncoders.java
Modified:
    hbase/trunk/hbase-common/src/main/java/org/apache/hadoop/hbase/CellComparator.java
    hbase/trunk/hbase-common/src/main/java/org/apache/hadoop/hbase/KeyValue.java
    hbase/trunk/hbase-common/src/main/java/org/apache/hadoop/hbase/io/encoding/BufferedDataBlockEncoder.java
    hbase/trunk/hbase-common/src/main/java/org/apache/hadoop/hbase/io/encoding/DataBlockEncoder.java
    hbase/trunk/hbase-common/src/main/java/org/apache/hadoop/hbase/util/Bytes.java
    hbase/trunk/hbase-prefix-tree/src/main/java/org/apache/hadoop/hbase/codec/prefixtree/PrefixTreeSeeker.java
    hbase/trunk/hbase-prefix-tree/src/main/java/org/apache/hadoop/hbase/codec/prefixtree/decode/PrefixTreeArrayScanner.java
    hbase/trunk/hbase-prefix-tree/src/main/java/org/apache/hadoop/hbase/codec/prefixtree/decode/PrefixTreeCell.java
    hbase/trunk/hbase-server/src/main/java/org/apache/hadoop/hbase/io/HalfStoreFileReader.java
    hbase/trunk/hbase-server/src/main/java/org/apache/hadoop/hbase/io/hfile/HFileBlockIndex.java
    hbase/trunk/hbase-server/src/main/java/org/apache/hadoop/hbase/io/hfile/HFileReaderV2.java
    hbase/trunk/hbase-server/src/main/java/org/apache/hadoop/hbase/io/hfile/HFileReaderV3.java
    hbase/trunk/hbase-server/src/main/java/org/apache/hadoop/hbase/io/hfile/HFileScanner.java
    hbase/trunk/hbase-server/src/main/java/org/apache/hadoop/hbase/regionserver/HStore.java
    hbase/trunk/hbase-server/src/main/java/org/apache/hadoop/hbase/regionserver/StoreFileScanner.java
    hbase/trunk/hbase-server/src/main/java/org/apache/hadoop/hbase/util/BloomFilterFactory.java
    hbase/trunk/hbase-server/src/main/java/org/apache/hadoop/hbase/util/ByteBloomFilter.java
    hbase/trunk/hbase-server/src/main/java/org/apache/hadoop/hbase/util/CompoundBloomFilter.java
    hbase/trunk/hbase-server/src/test/java/org/apache/hadoop/hbase/io/TestHalfStoreFileReader.java
    hbase/trunk/hbase-server/src/test/java/org/apache/hadoop/hbase/io/encoding/TestDataBlockEncoders.java
    hbase/trunk/hbase-server/src/test/java/org/apache/hadoop/hbase/io/encoding/TestPrefixTreeEncoding.java
    hbase/trunk/hbase-server/src/test/java/org/apache/hadoop/hbase/io/hfile/TestHFile.java
    hbase/trunk/hbase-server/src/test/java/org/apache/hadoop/hbase/io/hfile/TestHFileBlockIndex.java
    hbase/trunk/hbase-server/src/test/java/org/apache/hadoop/hbase/io/hfile/TestHFileEncryption.java
    hbase/trunk/hbase-server/src/test/java/org/apache/hadoop/hbase/io/hfile/TestHFileInlineToRootChunkConversion.java
    hbase/trunk/hbase-server/src/test/java/org/apache/hadoop/hbase/io/hfile/TestHFileSeek.java
    hbase/trunk/hbase-server/src/test/java/org/apache/hadoop/hbase/io/hfile/TestReseekTo.java
    hbase/trunk/hbase-server/src/test/java/org/apache/hadoop/hbase/io/hfile/TestSeekTo.java

Modified: hbase/trunk/hbase-common/src/main/java/org/apache/hadoop/hbase/CellComparator.java
URL: http://svn.apache.org/viewvc/hbase/trunk/hbase-common/src/main/java/org/apache/hadoop/hbase/CellComparator.java?rev=1583031&r1=1583030&r2=1583031&view=diff
==============================================================================
--- hbase/trunk/hbase-common/src/main/java/org/apache/hadoop/hbase/CellComparator.java (original)
+++ hbase/trunk/hbase-common/src/main/java/org/apache/hadoop/hbase/CellComparator.java Sat Mar 29 17:18:56 2014
@@ -45,54 +45,85 @@ public class CellComparator implements C
 
   @Override
   public int compare(Cell a, Cell b) {
-    return compareStatic(a, b);
+    return compareStatic(a, b, false);
   }
 
-
-  public static int compareStatic(Cell a, Cell b) {
-    //row
-    int c = Bytes.compareTo(
-        a.getRowArray(), a.getRowOffset(), a.getRowLength(),
-        b.getRowArray(), b.getRowOffset(), b.getRowLength());
+  public static int compareStatic(Cell a, Cell b, boolean onlyKey) {
+    // row
+    int c = compareRows(a, b);
     if (c != 0) return c;
 
-    // If the column is not specified, the "minimum" key type appears the
-    // latest in the sorted order, regardless of the timestamp. This is used
-    // for specifying the last key/value in a given row, because there is no
-    // "lexicographically last column" (it would be infinitely long). The
-    // "maximum" key type does not need this behavior.
-    if (a.getFamilyLength() == 0 && a.getTypeByte() == Type.Minimum.getCode()) {
-      // a is "bigger", i.e. it appears later in the sorted order
-      return 1;
-    }
-    if (b.getFamilyLength() == 0 && b.getTypeByte() == Type.Minimum.getCode()) {
-      return -1;
+    c = compareWithoutRow(a, b);
+    if(c != 0) return c;
+
+    if (!onlyKey) {
+      // Negate following comparisons so later edits show up first
+
+      // compare log replay tag value if there is any
+      // when either keyvalue tagged with log replay sequence number, we need to compare them:
+      // 1) when both keyvalues have the tag, then use the tag values for comparison
+      // 2) when one has and the other doesn't have, the one without the log
+      // replay tag wins because
+      // it means the edit isn't from recovery but new one coming from clients during recovery
+      // 3) when both doesn't have, then skip to the next mvcc comparison
+      long leftChangeSeqNum = getReplaySeqNum(a);
+      long RightChangeSeqNum = getReplaySeqNum(b);
+      if (leftChangeSeqNum != Long.MAX_VALUE || RightChangeSeqNum != Long.MAX_VALUE) {
+        return Longs.compare(RightChangeSeqNum, leftChangeSeqNum);
+      }
+      // mvccVersion: later sorts first
+      return Longs.compare(b.getMvccVersion(), a.getMvccVersion());
+    } else {
+      return c;
     }
+  }
 
-    //family
-    c = Bytes.compareTo(
-      a.getFamilyArray(), a.getFamilyOffset(), a.getFamilyLength(),
-      b.getFamilyArray(), b.getFamilyOffset(), b.getFamilyLength());
-    if (c != 0) return c;
+  /**
+   * Return replay log sequence number for the cell
+   *
+   * @param c
+   * @return Long.MAX_VALUE if there is no LOG_REPLAY_TAG
+   */
+  private static long getReplaySeqNum(final Cell c) {
+    Tag tag = Tag.getTag(c.getTagsArray(), c.getTagsOffset(), c.getTagsLength(),
+        TagType.LOG_REPLAY_TAG_TYPE);
 
-    //qualifier
-    c = Bytes.compareTo(
-        a.getQualifierArray(), a.getQualifierOffset(), a.getQualifierLength(),
-        b.getQualifierArray(), b.getQualifierOffset(), b.getQualifierLength());
-    if (c != 0) return c;
+    if (tag != null) {
+      return Bytes.toLong(tag.getBuffer(), tag.getTagOffset(), tag.getTagLength());
+    }
+    return Long.MAX_VALUE;
+  }
 
-    //timestamp: later sorts first
-    c = Longs.compare(b.getTimestamp(), a.getTimestamp());
-    if (c != 0) return c;
+  public static int findCommonPrefixInRowPart(Cell left, Cell right, int rowCommonPrefix) {
+    return findCommonPrefix(left.getRowArray(), right.getRowArray(), left.getRowLength()
+        - rowCommonPrefix, right.getRowLength() - rowCommonPrefix, left.getRowOffset()
+        + rowCommonPrefix, right.getRowOffset() + rowCommonPrefix);
+  }
 
-    //type
-    c = (0xff & b.getTypeByte()) - (0xff & a.getTypeByte());
-    if (c != 0) return c;
+  private static int findCommonPrefix(byte[] left, byte[] right, int leftLength, int rightLength,
+      int leftOffset, int rightOffset) {
+    int length = Math.min(leftLength, rightLength);
+    int result = 0;
 
-    //mvccVersion: later sorts first
-    return Longs.compare(b.getMvccVersion(), a.getMvccVersion());
+    while (result < length && left[leftOffset + result] == right[rightOffset + result]) {
+      result++;
+    }
+    return result;
   }
 
+  public static int findCommonPrefixInFamilyPart(Cell left, Cell right, int familyCommonPrefix) {
+    return findCommonPrefix(left.getFamilyArray(), right.getFamilyArray(), left.getFamilyLength()
+        - familyCommonPrefix, right.getFamilyLength() - familyCommonPrefix, left.getFamilyOffset()
+        + familyCommonPrefix, right.getFamilyOffset() + familyCommonPrefix);
+  }
+
+  public static int findCommonPrefixInQualifierPart(Cell left, Cell right,
+      int qualifierCommonPrefix) {
+    return findCommonPrefix(left.getQualifierArray(), right.getQualifierArray(),
+        left.getQualifierLength() - qualifierCommonPrefix, right.getQualifierLength()
+            - qualifierCommonPrefix, left.getQualifierOffset() + qualifierCommonPrefix,
+        right.getQualifierOffset() + qualifierCommonPrefix);
+  }
 
   /**************** equals ****************************/
 
@@ -130,6 +161,88 @@ public class CellComparator implements C
     return a.getTypeByte() == b.getTypeByte();
   }
 
+  public static int compareColumns(final Cell left, final Cell right) {
+    int lfoffset = left.getFamilyOffset();
+    int rfoffset = right.getFamilyOffset();
+    int lclength = left.getQualifierLength();
+    int rclength = right.getQualifierLength();
+    int lfamilylength = left.getFamilyLength();
+    int rfamilylength = right.getFamilyLength();
+    int diff = compare(left.getFamilyArray(), lfoffset, lfamilylength, right.getFamilyArray(),
+        rfoffset, rfamilylength);
+    if (diff != 0) {
+      return diff;
+    } else {
+      return compare(left.getQualifierArray(), left.getQualifierOffset(), lclength,
+          right.getQualifierArray(), right.getQualifierOffset(), rclength);
+    }
+  }
+
+  public static int compareFamilies(Cell left, Cell right) {
+    return Bytes.compareTo(left.getFamilyArray(), left.getFamilyOffset(), left.getFamilyLength(),
+        right.getFamilyArray(), right.getFamilyOffset(), right.getFamilyLength());
+  }
+
+  public static int compareQualifiers(Cell left, Cell right) {
+    return Bytes.compareTo(left.getQualifierArray(), left.getQualifierOffset(),
+        left.getQualifierLength(), right.getQualifierArray(), right.getQualifierOffset(),
+        right.getQualifierLength());
+  }
+
+  public int compareFlatKey(Cell left, Cell right) {
+    int compare = compareRows(left, right);
+    if (compare != 0) {
+      return compare;
+    }
+    return compareWithoutRow(left, right);
+  }
+
+  public static int compareRows(final Cell left, final Cell right) {
+    return Bytes.compareTo(left.getRowArray(), left.getRowOffset(), left.getRowLength(),
+        right.getRowArray(), right.getRowOffset(), right.getRowLength());
+  }
+
+  public static int compareRows(byte[] left, int loffset, int llength, byte[] right, int roffset,
+      int rlength) {
+    return Bytes.compareTo(left, loffset, llength, right, roffset, rlength);
+  }
+
+  public static int compareWithoutRow(final Cell leftCell, final Cell rightCell) {
+    if (leftCell.getFamilyLength() + leftCell.getQualifierLength() == 0
+        && leftCell.getTypeByte() == Type.Minimum.getCode()) {
+      // left is "bigger", i.e. it appears later in the sorted order
+      return 1;
+    }
+    if (rightCell.getFamilyLength() + rightCell.getQualifierLength() == 0
+        && rightCell.getTypeByte() == Type.Minimum.getCode()) {
+      return -1;
+    }
+    boolean sameFamilySize = (leftCell.getFamilyLength() == rightCell.getFamilyLength());
+    if (!sameFamilySize) {
+      // comparing column family is enough.
+
+      return Bytes.compareTo(leftCell.getFamilyArray(), leftCell.getFamilyOffset(),
+          leftCell.getFamilyLength(), rightCell.getFamilyArray(), rightCell.getFamilyOffset(),
+          rightCell.getFamilyLength());
+    }
+    int diff = compareColumns(leftCell, rightCell);
+    if (diff != 0) return diff;
+
+    diff = compareTimestamps(leftCell, rightCell);
+    if (diff != 0) return diff;
+
+    // Compare types. Let the delete types sort ahead of puts; i.e. types
+    // of higher numbers sort before those of lesser numbers. Maximum (255)
+    // appears ahead of everything, and minimum (0) appears after
+    // everything.
+    return (0xff & rightCell.getTypeByte()) - (0xff & leftCell.getTypeByte());
+  }
+
+  public static int compareTimestamps(final Cell left, final Cell right) {
+    long ltimestamp = left.getTimestamp();
+    long rtimestamp = right.getTimestamp();
+    return compareTimestamps(ltimestamp, rtimestamp);
+  }
 
   /********************* hashCode ************************/
 
@@ -172,32 +285,54 @@ public class CellComparator implements C
   }
 
 
-  /***************** special cases ****************************/
+  /*********************common prefixes*************************/
+
+  private static int compare(byte[] left, int leftOffset, int leftLength, byte[] right,
+      int rightOffset, int rightLength) {
+    return Bytes.compareTo(left, leftOffset, leftLength, right, rightOffset, rightLength);
+  }
+
+  public static int compareCommonRowPrefix(Cell left, Cell right, int rowCommonPrefix) {
+    return compare(left.getRowArray(), left.getRowOffset() + rowCommonPrefix, left.getRowLength()
+        - rowCommonPrefix, right.getRowArray(), right.getRowOffset() + rowCommonPrefix,
+        right.getRowLength() - rowCommonPrefix);
+  }
+
+  public static int compareCommonFamilyPrefix(Cell left, Cell right,
+      int familyCommonPrefix) {
+    return compare(left.getFamilyArray(), left.getFamilyOffset() + familyCommonPrefix,
+        left.getFamilyLength() - familyCommonPrefix, right.getFamilyArray(),
+        right.getFamilyOffset() + familyCommonPrefix,
+        right.getFamilyLength() - familyCommonPrefix);
+  }
+
+  public static int compareCommonQualifierPrefix(Cell left, Cell right,
+      int qualCommonPrefix) {
+    return compare(left.getQualifierArray(), left.getQualifierOffset() + qualCommonPrefix,
+        left.getQualifierLength() - qualCommonPrefix, right.getQualifierArray(),
+        right.getQualifierOffset() + qualCommonPrefix, right.getQualifierLength()
+            - qualCommonPrefix);
+  }
 
+  /***************** special cases ****************************/
   /**
    * special case for KeyValue.equals
    */
-  private static int compareStaticIgnoreMvccVersion(Cell a, Cell b) {
-    //row
-    int c = Bytes.compareTo(
-        a.getRowArray(), a.getRowOffset(), a.getRowLength(),
-        b.getRowArray(), b.getRowOffset(), b.getRowLength());
-    if (c != 0) return c;
+  public static boolean equalsIgnoreMvccVersion(Cell a, Cell b){
+    return 0 == compareStaticIgnoreMvccVersion(a, b);
+  }
 
-    //family
-    c = Bytes.compareTo(
-      a.getFamilyArray(), a.getFamilyOffset(), a.getFamilyLength(),
-      b.getFamilyArray(), b.getFamilyOffset(), b.getFamilyLength());
+  private static int compareStaticIgnoreMvccVersion(Cell a, Cell b) {
+    // row
+    int c = compareRows(a, b);
     if (c != 0) return c;
 
-    //qualifier
-    c = Bytes.compareTo(
-        a.getQualifierArray(), a.getQualifierOffset(), a.getQualifierLength(),
-        b.getQualifierArray(), b.getQualifierOffset(), b.getQualifierLength());
+    // family
+    c = compareColumns(a, b);
     if (c != 0) return c;
 
-    //timestamp: later sorts first
-    c = Longs.compare(b.getTimestamp(), a.getTimestamp());
+    // timestamp: later sorts first
+    c = compareTimestamps(a, b);
     if (c != 0) return c;
 
     //type
@@ -205,11 +340,17 @@ public class CellComparator implements C
     return c;
   }
 
-  /**
-   * special case for KeyValue.equals
-   */
-  public static boolean equalsIgnoreMvccVersion(Cell a, Cell b){
-    return 0 == compareStaticIgnoreMvccVersion(a, b);
+  private static int compareTimestamps(final long ltimestamp, final long rtimestamp) {
+    // The below older timestamps sorting ahead of newer timestamps looks
+    // wrong but it is intentional. This way, newer timestamps are first
+    // found when we iterate over a memstore and newer versions are the
+    // first we trip over when reading from a store file.
+    if (ltimestamp < rtimestamp) {
+      return 1;
+    } else if (ltimestamp > rtimestamp) {
+      return -1;
+    }
+    return 0;
   }
 
 }

Modified: hbase/trunk/hbase-common/src/main/java/org/apache/hadoop/hbase/KeyValue.java
URL: http://svn.apache.org/viewvc/hbase/trunk/hbase-common/src/main/java/org/apache/hadoop/hbase/KeyValue.java?rev=1583031&r1=1583030&r2=1583031&view=diff
==============================================================================
--- hbase/trunk/hbase-common/src/main/java/org/apache/hadoop/hbase/KeyValue.java (original)
+++ hbase/trunk/hbase-common/src/main/java/org/apache/hadoop/hbase/KeyValue.java Sat Mar 29 17:18:56 2014
@@ -43,7 +43,7 @@ import org.apache.hadoop.hbase.util.Clas
 import org.apache.hadoop.io.IOUtils;
 import org.apache.hadoop.io.RawComparator;
 
-import com.google.common.primitives.Longs;
+import com.google.common.annotations.VisibleForTesting;
 
 /**
  * An HBase Key/Value. This is the fundamental HBase Type.  
@@ -1839,6 +1839,20 @@ public class KeyValue implements Cell, H
      * table.
      */
     @Override
+    public int compare(final Cell left, final Cell right) {
+      int c = compareRowKey(left, right);
+      if (c != 0) {
+        return c;
+      }
+      return CellComparator.compareWithoutRow(left, right);
+    }
+
+    @Override
+    public int compareOnlyKeyPortion(Cell left, Cell right) {
+      return compare(left, right);
+    }
+
+    @Override
     public int compareRows(byte [] left, int loffset, int llength,
         byte [] right, int roffset, int rlength) {
       int leftDelimiter = getDelimiter(left, loffset, llength,
@@ -1952,9 +1966,7 @@ public class KeyValue implements Cell, H
      * @return 0 if equal, <0 if left smaller, >0 if right smaller
      */
     protected int compareRowKey(final Cell left, final Cell right) {
-      return Bytes.compareTo(
-          left.getRowArray(),  left.getRowOffset(),  left.getRowLength(),
-          right.getRowArray(), right.getRowOffset(), right.getRowLength());
+      return CellComparator.compareRows(left, right);
     }
 
     /**
@@ -1990,109 +2002,22 @@ public class KeyValue implements Cell, H
       return compareFlatKey(left, 0, left.length, right, 0, right.length);
     }
 
+    public int compareOnlyKeyPortion(Cell left, Cell right) {
+      return CellComparator.compareStatic(left, right, true);
+    }
+
     /**
      * Compares the Key of a cell -- with fields being more significant in this order:
      * rowkey, colfam/qual, timestamp, type, mvcc
      */
+    @Override
     public int compare(final Cell left, final Cell right) {
-      // compare row
-      int compare = compareRowKey(left, right);
-      if (compare != 0) {
-        return compare;
-      }
-
-      // compare vs minimum
-      byte ltype = left.getTypeByte();
-      byte rtype = right.getTypeByte();
-      // If the column is not specified, the "minimum" key type appears the
-      // latest in the sorted order, regardless of the timestamp. This is used
-      // for specifying the last key/value in a given row, because there is no
-      // "lexicographically last column" (it would be infinitely long). The
-      // "maximum" key type does not need this behavior.
-      int lcfqLen = left.getFamilyLength() + left.getQualifierLength() ;
-      int rcfqLen = right.getFamilyLength() + right.getQualifierLength() ;
-      if (lcfqLen == 0 && ltype == Type.Minimum.getCode()) {
-        // left is "bigger", i.e. it appears later in the sorted order
-        return 1;
-      }
-      if (rcfqLen == 0 && rtype == Type.Minimum.getCode()) {
-        return -1;
-      }
-
-
-      // compare col family / col fam + qual
-      // If left family size is not equal to right family size, we need not
-      // compare the qualifiers.
-      compare = Bytes.compareTo(
-        left.getFamilyArray(),  left.getFamilyOffset(),  left.getFamilyLength(),
-        right.getFamilyArray(), right.getFamilyOffset(), right.getFamilyLength());
-      if (compare != 0) {
-        return compare;
-      }
-
-      // Compare qualifier
-      compare = Bytes.compareTo(
-          left.getQualifierArray(), left.getQualifierOffset(), left.getQualifierLength(),
-          right.getQualifierArray(), right.getQualifierOffset(), right.getQualifierLength());
-      if (compare!= 0) {
-        return compare;
-      }
-
-      // compare timestamp
-      long ltimestamp = left.getTimestamp();
-      long rtimestamp = right.getTimestamp();
-      compare = compareTimestamps(ltimestamp, rtimestamp);
-      if (compare != 0) {
-        return compare;
-      }
-
-      // Compare types. Let the delete types sort ahead of puts; i.e. types
-      // of higher numbers sort before those of lesser numbers. Maximum (255)
-      // appears ahead of everything, and minimum (0) appears after
-      // everything.
-      compare = (0xff & rtype) - (0xff & ltype);
-      if (compare != 0) {
-        return compare;
-      }
-
-      // Negate following comparisons so later edits show up first
-
-      // compare log replay tag value if there is any
-      // when either keyvalue tagged with log replay sequence number, we need to compare them:
-      // 1) when both keyvalues have the tag, then use the tag values for comparison
-      // 2) when one has and the other doesn't have, the one without the log replay tag wins because
-      // it means the edit isn't from recovery but new one coming from clients during recovery
-      // 3) when both doesn't have, then skip to the next mvcc comparison
-      long leftChangeSeqNum = getReplaySeqNum(left);
-      long RightChangeSeqNum = getReplaySeqNum(right);
-      if (leftChangeSeqNum != Long.MAX_VALUE || RightChangeSeqNum != Long.MAX_VALUE) {
-        return Longs.compare(RightChangeSeqNum, leftChangeSeqNum);
-      }
-
-      // compare Mvcc Version
-      return Longs.compare(right.getMvccVersion(), left.getMvccVersion());
-    }
-    
-    /**
-     * Return replay log sequence number for the cell
-     * @param c
-     * @return Long.MAX_VALUE if there is no LOG_REPLAY_TAG
-     */
-    private long getReplaySeqNum(final Cell c) {
-      Tag tag = Tag.getTag(c.getTagsArray(), c.getTagsOffset(), c.getTagsLength(), 
-        TagType.LOG_REPLAY_TAG_TYPE);
-
-      if(tag != null) {
-        return Bytes.toLong(tag.getBuffer(), tag.getTagOffset(), tag.getTagLength());
-      }
-      return Long.MAX_VALUE;
+      int compare = CellComparator.compareStatic(left, right, false);
+      return compare;
     }
 
-    public int compareTimestamps(final KeyValue left, final KeyValue right) {
-      // Compare timestamps
-      long ltimestamp = left.getTimestamp(left.getKeyLength());
-      long rtimestamp = right.getTimestamp(right.getKeyLength());
-      return compareTimestamps(ltimestamp, rtimestamp);
+    public int compareTimestamps(final Cell left, final Cell right) {
+      return CellComparator.compareTimestamps(left, right);
     }
 
     /**
@@ -2100,7 +2025,7 @@ public class KeyValue implements Cell, H
      * @param right
      * @return Result comparing rows.
      */
-    public int compareRows(final KeyValue left, final KeyValue right) {
+    public int compareRows(final Cell left, final Cell right) {
       return compareRows(left.getRowArray(),left.getRowOffset(), left.getRowLength(),
       right.getRowArray(), right.getRowOffset(), right.getRowLength());
     }
@@ -2120,17 +2045,9 @@ public class KeyValue implements Cell, H
       return Bytes.compareTo(left, loffset, llength, right, roffset, rlength);
     }
 
-    int compareColumns(final KeyValue left, final short lrowlength,
-        final KeyValue right, final short rrowlength) {
-      int lfoffset = left.getFamilyOffset(lrowlength);
-      int rfoffset = right.getFamilyOffset(rrowlength);
-      int lclength = left.getTotalColumnLength(lrowlength,lfoffset);
-      int rclength = right.getTotalColumnLength(rrowlength, rfoffset);
-      int lfamilylength = left.getFamilyLength(lfoffset);
-      int rfamilylength = right.getFamilyLength(rfoffset);
-      return compareColumns(left.getBuffer(), lfoffset,
-          lclength, lfamilylength,
-        right.getBuffer(), rfoffset, rclength, rfamilylength);
+    int compareColumns(final Cell left, final short lrowlength, final Cell right,
+        final short rrowlength) {
+      return CellComparator.compareColumns(left, right);
     }
 
     protected int compareColumns(
@@ -2297,20 +2214,31 @@ public class KeyValue implements Cell, H
       return (0xff & rtype) - (0xff & ltype);
     }
 
+    protected int compareFamilies(final byte[] left, final int loffset, final int lfamilylength,
+        final byte[] right, final int roffset, final int rfamilylength) {
+      int diff = Bytes.compareTo(left, loffset, lfamilylength, right, roffset, rfamilylength);
+      return diff;
+    }
+
+    protected int compareColumns(final byte[] left, final int loffset, final int lquallength,
+        final byte[] right, final int roffset, final int rquallength) {
+      int diff = Bytes.compareTo(left, loffset, lquallength, right, roffset, rquallength);
+      return diff;
+    }
     /**
      * Compares the row and column of two keyvalues for equality
      * @param left
      * @param right
      * @return True if same row and column.
      */
-    public boolean matchingRowColumn(final KeyValue left,
-        final KeyValue right) {
+    public boolean matchingRowColumn(final Cell left,
+        final Cell right) {
       short lrowlength = left.getRowLength();
       short rrowlength = right.getRowLength();
 
       // TsOffset = end of column data. just comparing Row+CF length of each
-      if ((left.getTimestampOffset() - left.getOffset()) !=
-          (right.getTimestampOffset() - right.getOffset())) {
+      if ((left.getRowLength() + left.getFamilyLength() + left.getQualifierLength()) != (right
+          .getRowLength() + right.getFamilyLength() + right.getQualifierLength())) {
         return false;
       }
 
@@ -2318,15 +2246,21 @@ public class KeyValue implements Cell, H
         return false;
       }
 
-      int lfoffset = left.getFamilyOffset(lrowlength);
-      int rfoffset = right.getFamilyOffset(rrowlength);
-      int lclength = left.getTotalColumnLength(lrowlength,lfoffset);
-      int rclength = right.getTotalColumnLength(rrowlength, rfoffset);
-      int lfamilylength = left.getFamilyLength(lfoffset);
-      int rfamilylength = right.getFamilyLength(rfoffset);
-      int ccRes = compareColumns(left.getBuffer(), lfoffset, lclength, lfamilylength,
-          right.getBuffer(), rfoffset, rclength, rfamilylength);
-      return ccRes == 0;
+      int lfoffset = left.getFamilyOffset();
+      int rfoffset = right.getFamilyOffset();
+      int lclength = left.getQualifierLength();
+      int rclength = right.getQualifierLength();
+      int lfamilylength = left.getFamilyLength();
+      int rfamilylength = right.getFamilyLength();
+      int diff = compareFamilies(left.getFamilyArray(), lfoffset, lfamilylength,
+          right.getFamilyArray(), rfoffset, rfamilylength);
+      if (diff != 0) {
+        return false;
+      } else {
+        diff = compareColumns(left.getQualifierArray(), left.getQualifierOffset(), lclength,
+            right.getQualifierArray(), right.getQualifierOffset(), rclength);
+        return diff == 0;
+      }
     }
 
     /**
@@ -2335,7 +2269,7 @@ public class KeyValue implements Cell, H
      * @param right
      * @return True if rows match.
      */
-    public boolean matchingRows(final KeyValue left, final KeyValue right) {
+    public boolean matchingRows(final Cell left, final Cell right) {
       short lrowlength = left.getRowLength();
       short rrowlength = right.getRowLength();
       return matchingRows(left, lrowlength, right, rrowlength);
@@ -2348,8 +2282,8 @@ public class KeyValue implements Cell, H
      * @param rrowlength
      * @return True if rows match.
      */
-    private boolean matchingRows(final KeyValue left, final short lrowlength,
-        final KeyValue right, final short rrowlength) {
+    private boolean matchingRows(final Cell left, final short lrowlength,
+        final Cell right, final short rrowlength) {
       return lrowlength == rrowlength &&
           matchingRows(left.getRowArray(), left.getRowOffset(), lrowlength,
               right.getRowArray(), right.getRowOffset(), rrowlength);
@@ -2929,6 +2863,37 @@ public class KeyValue implements Cell, H
       return Bytes.BYTES_RAWCOMPARATOR.compare(left,  loffset, llength, right, roffset, rlength);
     }
 
+    @Override
+    public int compare(Cell left, Cell right) {
+      return compareOnlyKeyPortion(left, right);
+    }
+
+    @VisibleForTesting
+    public int compareOnlyKeyPortion(Cell left, Cell right) {
+      int c = Bytes.BYTES_RAWCOMPARATOR.compare(left.getRowArray(), left.getRowOffset(),
+          left.getRowLength(), right.getRowArray(), right.getRowOffset(), right.getRowLength());
+      if (c != 0) {
+        return c;
+      }
+      c = Bytes.BYTES_RAWCOMPARATOR.compare(left.getFamilyArray(), left.getFamilyOffset(),
+          left.getFamilyLength(), right.getFamilyArray(), right.getFamilyOffset(),
+          right.getFamilyLength());
+      if (c != 0) {
+        return c;
+      }
+      c = Bytes.BYTES_RAWCOMPARATOR.compare(left.getQualifierArray(), left.getQualifierOffset(),
+          left.getQualifierLength(), right.getQualifierArray(), right.getQualifierOffset(),
+          right.getQualifierLength());
+      if (c != 0) {
+        return c;
+      }
+      c = compareTimestamps(left.getTimestamp(), right.getTimestamp());
+      if (c != 0) {
+        return c;
+      }
+      return (0xff & left.getTypeByte()) - (0xff & right.getTypeByte());
+    }
+
     public byte[] calcIndexKey(byte[] lastKeyOfPreviousBlock, byte[] firstKeyInBlock) {
       return firstKeyInBlock;
     }
@@ -2952,4 +2917,171 @@ public class KeyValue implements Cell, H
     sum += Bytes.SIZEOF_LONG;// memstoreTS
     return ClassSize.align(sum);
   }
+
+  /**
+   * A simple form of KeyValue that creates a keyvalue with only the key part of the byte[]
+   * Mainly used in places where we need to compare two cells.  Avoids copying of bytes
+   * In places like block index keys, we need to compare the key byte[] with a cell.
+   * Hence create a Keyvalue(aka Cell) that would help in comparing as two cells
+   */
+  public static class KeyOnlyKeyValue extends KeyValue {
+    private int length = 0;
+    private int offset = 0;
+    private byte[] b;
+
+    public KeyOnlyKeyValue() {
+
+    }
+
+    public KeyOnlyKeyValue(byte[] b, int offset, int length) {
+      this.b = b;
+      this.length = length;
+      this.offset = offset;
+    }
+
+    @Override
+    public int getKeyOffset() {
+      return this.offset;
+    }
+
+    /**
+     * A setter that helps to avoid object creation every time and whenever
+     * there is a need to create new KeyOnlyKeyValue.
+     * @param key
+     * @param offset
+     * @param length
+     */
+    public void setKey(byte[] key, int offset, int length) {
+      this.b = key;
+      this.offset = offset;
+      this.length = length;
+    }
+
+    @Override
+    public byte[] getKey() {
+      int keylength = getKeyLength();
+      byte[] key = new byte[keylength];
+      System.arraycopy(this.b, getKeyOffset(), key, 0, keylength);
+      return key;
+    }
+
+    @Override
+    public byte[] getRowArray() {
+      return b;
+    }
+
+    @Override
+    public int getRowOffset() {
+      return getKeyOffset() + Bytes.SIZEOF_SHORT;
+    }
+
+    @Override
+    public byte[] getFamilyArray() {
+      return b;
+    }
+
+    @Override
+    public byte getFamilyLength() {
+      return this.b[getFamilyOffset() - 1];
+    }
+
+    @Override
+    public int getFamilyOffset() {
+      return this.offset + Bytes.SIZEOF_SHORT + getRowLength() + Bytes.SIZEOF_BYTE;
+    }
+
+    @Override
+    public byte[] getQualifierArray() {
+      return b;
+    }
+
+    @Override
+    public int getQualifierLength() {
+      return getQualifierLength(getRowLength(), getFamilyLength());
+    }
+
+    @Override
+    public int getQualifierOffset() {
+      return getFamilyOffset() + getFamilyLength();
+    }
+
+    @Override
+    public int getKeyLength() {
+      return length;
+    }
+
+    @Override
+    public short getRowLength() {
+      return Bytes.toShort(this.b, getKeyOffset());
+    }
+
+    @Override
+    public byte getTypeByte() {
+      return this.b[this.offset + getKeyLength() - 1];
+    }
+
+    private int getQualifierLength(int rlength, int flength) {
+      return getKeyLength() - (int) getKeyDataStructureSize(rlength, flength, 0);
+    }
+
+    @Override
+    public long getTimestamp() {
+      int tsOffset = getTimestampOffset();
+      return Bytes.toLong(this.b, tsOffset);
+    }
+
+    @Override
+    public int getTimestampOffset() {
+      return getKeyOffset() + getKeyLength() - TIMESTAMP_TYPE_SIZE;
+    }
+
+    @Override
+    public byte[] getTagsArray() {
+      return HConstants.EMPTY_BYTE_ARRAY;
+    }
+
+    @Override
+    public int getTagsOffset() {
+      return (short) 0;
+    }
+
+    @Override
+    public byte[] getValueArray() {
+      throw new IllegalArgumentException("KeyOnlyKeyValue does not work with values.");
+    }
+
+    @Override
+    public int getValueOffset() {
+      throw new IllegalArgumentException("KeyOnlyKeyValue does not work with values.");
+    }
+
+    @Override
+    public int getValueLength() {
+      throw new IllegalArgumentException("KeyOnlyKeyValue does not work with values.");
+    }
+
+    @Override
+    public short getTagsLength() {
+      return (short) 0;
+    }
+
+    @Override
+    public String toString() {
+      if (this.b == null || this.b.length == 0) {
+        return "empty";
+      }
+      return keyToString(this.b, this.offset + ROW_OFFSET, getKeyLength()) + "/vlen="
+          + getValueLength() + "/mvcc=" + 0;
+    }
+
+    @Override
+    public int hashCode() {
+      return super.hashCode();
+    }
+
+    @Override
+    public boolean equals(Object other) {
+      return super.equals(other);
+    }
+  }
 }

Modified: hbase/trunk/hbase-common/src/main/java/org/apache/hadoop/hbase/io/encoding/BufferedDataBlockEncoder.java
URL: http://svn.apache.org/viewvc/hbase/trunk/hbase-common/src/main/java/org/apache/hadoop/hbase/io/encoding/BufferedDataBlockEncoder.java?rev=1583031&r1=1583030&r2=1583031&view=diff
==============================================================================
--- hbase/trunk/hbase-common/src/main/java/org/apache/hadoop/hbase/io/encoding/BufferedDataBlockEncoder.java (original)
+++ hbase/trunk/hbase-common/src/main/java/org/apache/hadoop/hbase/io/encoding/BufferedDataBlockEncoder.java Sat Mar 29 17:18:56 2014
@@ -22,10 +22,13 @@ import java.io.IOException;
 import java.nio.ByteBuffer;
 
 import org.apache.hadoop.classification.InterfaceAudience;
+import org.apache.hadoop.hbase.Cell;
+import org.apache.hadoop.hbase.CellComparator;
 import org.apache.hadoop.hbase.HConstants;
 import org.apache.hadoop.hbase.KeyValue;
 import org.apache.hadoop.hbase.KeyValue.KVComparator;
 import org.apache.hadoop.hbase.KeyValue.SamePrefixComparator;
+import org.apache.hadoop.hbase.KeyValue.Type;
 import org.apache.hadoop.hbase.io.TagCompressionContext;
 import org.apache.hadoop.hbase.io.hfile.BlockType;
 import org.apache.hadoop.hbase.io.hfile.HFileContext;
@@ -194,6 +197,12 @@ abstract class BufferedDataBlockEncoder 
     }
 
     @Override
+    public int compareKey(KVComparator comparator, Cell key) {
+      return comparator.compareOnlyKeyPortion(key,
+          new KeyValue.KeyOnlyKeyValue(current.keyBuffer, 0, current.keyLength));
+    }
+
+    @Override
     public void setCurrentBuffer(ByteBuffer buffer) {
       if (this.tagCompressionContext != null) {
         this.tagCompressionContext.clear();
@@ -304,36 +313,89 @@ abstract class BufferedDataBlockEncoder 
     }
 
     @Override
-    public int seekToKeyInBlock(byte[] key, int offset, int length,
-        boolean seekBefore) {
-      int commonPrefix = 0;
+    public int seekToKeyInBlock(byte[] key, int offset, int length, boolean seekBefore) {
+      return seekToKeyInBlock(new KeyValue.KeyOnlyKeyValue(key, offset, length), seekBefore);
+    }
+
+    @Override
+    public int seekToKeyInBlock(Cell seekCell, boolean seekBefore) {
+      int rowCommonPrefix = 0;
+      int familyCommonPrefix = 0;
+      int qualCommonPrefix = 0;
       previous.invalidate();
+      KeyValue.KeyOnlyKeyValue currentCell = new KeyValue.KeyOnlyKeyValue();
       do {
         int comp;
         if (samePrefixComparator != null) {
-          commonPrefix = Math.min(commonPrefix, current.lastCommonPrefix);
-
-          // extend commonPrefix
-          commonPrefix += ByteBufferUtils.findCommonPrefix(
-              key, offset + commonPrefix, length - commonPrefix,
-              current.keyBuffer, commonPrefix,
-              current.keyLength - commonPrefix);
-
-          comp = samePrefixComparator.compareIgnoringPrefix(commonPrefix, key,
-              offset, length, current.keyBuffer, 0, current.keyLength);
+          currentCell.setKey(current.keyBuffer, 0, current.keyLength);
+          if (current.lastCommonPrefix != 0) {
+            // The KV format has row key length also in the byte array. The
+            // common prefix
+            // includes it. So we need to subtract to find out the common prefix
+            // in the
+            // row part alone
+            rowCommonPrefix = Math.min(rowCommonPrefix, current.lastCommonPrefix - 2);
+          }
+          if (current.lastCommonPrefix <= 2) {
+            rowCommonPrefix = 0;
+          }
+          rowCommonPrefix += CellComparator.findCommonPrefixInRowPart(seekCell, currentCell,
+              rowCommonPrefix);
+          comp = CellComparator.compareCommonRowPrefix(seekCell, currentCell, rowCommonPrefix);
+          if (comp == 0) {
+            comp = compareTypeBytes(seekCell, currentCell);
+            if (comp == 0) {
+              // Subtract the fixed row key length and the family key fixed length
+              familyCommonPrefix = Math.max(
+                  0,
+                  Math.min(familyCommonPrefix,
+                      current.lastCommonPrefix - (3 + currentCell.getRowLength())));
+              familyCommonPrefix += CellComparator.findCommonPrefixInFamilyPart(seekCell,
+                  currentCell, familyCommonPrefix);
+              comp = CellComparator.compareCommonFamilyPrefix(seekCell, currentCell,
+                  familyCommonPrefix);
+              if (comp == 0) {
+                // subtract the rowkey fixed length and the family key fixed
+                // length
+                qualCommonPrefix = Math.max(
+                    0,
+                    Math.min(
+                        qualCommonPrefix,
+                        current.lastCommonPrefix
+                            - (3 + currentCell.getRowLength() + currentCell.getFamilyLength())));
+                qualCommonPrefix += CellComparator.findCommonPrefixInQualifierPart(seekCell,
+                    currentCell, qualCommonPrefix);
+                comp = CellComparator.compareCommonQualifierPrefix(seekCell, currentCell,
+                    qualCommonPrefix);
+                if (comp == 0) {
+                  comp = CellComparator.compareTimestamps(seekCell, currentCell);
+                  if (comp == 0) {
+                    // Compare types. Let the delete types sort ahead of puts;
+                    // i.e. types
+                    // of higher numbers sort before those of lesser numbers.
+                    // Maximum
+                    // (255)
+                    // appears ahead of everything, and minimum (0) appears
+                    // after
+                    // everything.
+                    comp = (0xff & currentCell.getTypeByte()) - (0xff & seekCell.getTypeByte());
+                  }
+                }
+              }
+            }
+          }
         } else {
-          comp = comparator.compareFlatKey(key, offset, length,
-              current.keyBuffer, 0, current.keyLength);
+          Cell r = new KeyValue.KeyOnlyKeyValue(current.keyBuffer, 0, current.keyLength);
+          comp = comparator.compareOnlyKeyPortion(seekCell, r);
         }
-
         if (comp == 0) { // exact match
           if (seekBefore) {
             if (!previous.isValid()) {
               // The caller (seekBefore) has to ensure that we are not at the
               // first key in the block.
-              throw new IllegalStateException("Cannot seekBefore if " +
-                  "positioned at the first key in the block: key=" +
-                  Bytes.toStringBinary(key, offset, length));
+              throw new IllegalStateException("Cannot seekBefore if "
+                  + "positioned at the first key in the block: key="
+                  + Bytes.toStringBinary(seekCell.getRowArray()));
             }
             moveToPrevious();
             return 1;
@@ -363,6 +425,20 @@ abstract class BufferedDataBlockEncoder 
       return 1;
     }
 
+    private int compareTypeBytes(Cell key, Cell right) {
+      if (key.getFamilyLength() + key.getQualifierLength() == 0
+          && key.getTypeByte() == Type.Minimum.getCode()) {
+        // left is "bigger", i.e. it appears later in the sorted order
+        return 1;
+      }
+      if (right.getFamilyLength() + right.getQualifierLength() == 0
+          && right.getTypeByte() == Type.Minimum.getCode()) {
+        return -1;
+      }
+      return 0;
+    }
+
+
     private void moveToPrevious() {
       if (!previous.isValid()) {
         throw new IllegalStateException(

Modified: hbase/trunk/hbase-common/src/main/java/org/apache/hadoop/hbase/io/encoding/DataBlockEncoder.java
URL: http://svn.apache.org/viewvc/hbase/trunk/hbase-common/src/main/java/org/apache/hadoop/hbase/io/encoding/DataBlockEncoder.java?rev=1583031&r1=1583030&r2=1583031&view=diff
==============================================================================
--- hbase/trunk/hbase-common/src/main/java/org/apache/hadoop/hbase/io/encoding/DataBlockEncoder.java (original)
+++ hbase/trunk/hbase-common/src/main/java/org/apache/hadoop/hbase/io/encoding/DataBlockEncoder.java Sat Mar 29 17:18:56 2014
@@ -21,6 +21,7 @@ import java.io.IOException;
 import java.nio.ByteBuffer;
 
 import org.apache.hadoop.classification.InterfaceAudience;
+import org.apache.hadoop.hbase.Cell;
 import org.apache.hadoop.hbase.KeyValue;
 import org.apache.hadoop.hbase.KeyValue.KVComparator;
 import org.apache.hadoop.hbase.io.hfile.HFileContext;
@@ -174,9 +175,26 @@ public interface DataBlockEncoder {
      *          of an exact match. Does not matter in case of an inexact match.
      * @return 0 on exact match, 1 on inexact match.
      */
+    @Deprecated
     int seekToKeyInBlock(
       byte[] key, int offset, int length, boolean seekBefore
     );
+    /**
+     * Moves the seeker position within the current block to:
+     * <ul>
+     * <li>the last key that that is less than or equal to the given key if
+     * <code>seekBefore</code> is false</li>
+     * <li>the last key that is strictly less than the given key if <code>
+     * seekBefore</code> is true. The caller is responsible for loading the
+     * previous block if the requested key turns out to be the first key of the
+     * current block.</li>
+     * </ul>
+     * @param key - Cell to which the seek should happen
+     * @param seekBefore find the key strictly less than the given key in case
+     *          of an exact match. Does not matter in case of an inexact match.
+     * @return 0 on exact match, 1 on inexact match.
+     */
+    int seekToKeyInBlock(Cell key, boolean seekBefore);
 
     /**
      * Compare the given key against the current key
@@ -187,5 +205,7 @@ public interface DataBlockEncoder {
      * @return -1 is the passed key is smaller than the current key, 0 if equal and 1 if greater
      */
     public int compareKey(KVComparator comparator, byte[] key, int offset, int length);
+
+    public int compareKey(KVComparator comparator, Cell key);
   }
 }

Modified: hbase/trunk/hbase-common/src/main/java/org/apache/hadoop/hbase/util/Bytes.java
URL: http://svn.apache.org/viewvc/hbase/trunk/hbase-common/src/main/java/org/apache/hadoop/hbase/util/Bytes.java?rev=1583031&r1=1583030&r2=1583031&view=diff
==============================================================================
--- hbase/trunk/hbase-common/src/main/java/org/apache/hadoop/hbase/util/Bytes.java (original)
+++ hbase/trunk/hbase-common/src/main/java/org/apache/hadoop/hbase/util/Bytes.java Sat Mar 29 17:18:56 2014
@@ -43,6 +43,8 @@ import org.apache.commons.logging.Log;
 import org.apache.commons.logging.LogFactory;
 import org.apache.hadoop.classification.InterfaceAudience;
 import org.apache.hadoop.classification.InterfaceStability;
+import org.apache.hadoop.hbase.Cell;
+import org.apache.hadoop.hbase.KeyValue;
 import org.apache.hadoop.hbase.io.ImmutableBytesWritable;
 import org.apache.hadoop.io.RawComparator;
 import org.apache.hadoop.io.WritableComparator;
@@ -1635,6 +1637,43 @@ public class Bytes {
   }
 
   /**
+   * Binary search for keys in indexes.
+   *
+   * @param arr array of byte arrays to search for
+   * @param key the key you want to find
+   * @param comparator a comparator to compare.
+   * @return zero-based index of the key, if the key is present in the array.
+   *         Otherwise, a value -(i + 1) such that the key is between arr[i -
+   *         1] and arr[i] non-inclusively, where i is in [0, i], if we define
+   *         arr[-1] = -Inf and arr[N] = Inf for an N-element array. The above
+   *         means that this function can return 2N + 1 different values
+   *         ranging from -(N + 1) to N - 1.
+   * @return the index of the block
+   */
+  public static int binarySearch(byte[][] arr, Cell key, RawComparator<Cell> comparator) {
+    int low = 0;
+    int high = arr.length - 1;
+    KeyValue.KeyOnlyKeyValue r = new KeyValue.KeyOnlyKeyValue();
+    while (low <= high) {
+      int mid = (low+high) >>> 1;
+      // we have to compare in this order, because the comparator order
+      // has special logic when the 'left side' is a special key.
+      r.setKey(arr[mid], 0, arr[mid].length);
+      int cmp = comparator.compare(key, r);
+      // key lives above the midpoint
+      if (cmp > 0)
+        low = mid + 1;
+      // key lives below the midpoint
+      else if (cmp < 0)
+        high = mid - 1;
+      // BAM. how often does this really happen?
+      else
+        return mid;
+    }
+    return - (low+1);
+  }
+
+  /**
    * Bytewise binary increment/deincrement of long contained in byte array
    * on given amount.
    *

Added: hbase/trunk/hbase-common/src/test/java/org/apache/hadoop/hbase/TestCellComparator.java
URL: http://svn.apache.org/viewvc/hbase/trunk/hbase-common/src/test/java/org/apache/hadoop/hbase/TestCellComparator.java?rev=1583031&view=auto
==============================================================================
--- hbase/trunk/hbase-common/src/test/java/org/apache/hadoop/hbase/TestCellComparator.java (added)
+++ hbase/trunk/hbase-common/src/test/java/org/apache/hadoop/hbase/TestCellComparator.java Sat Mar 29 17:18:56 2014
@@ -0,0 +1,76 @@
+/*
+ * Licensed to the Apache Software Foundation (ASF) under one
+ * or more contributor license agreements.  See the NOTICE file
+ * distributed with this work for additional information
+ * regarding copyright ownership.  The ASF licenses this file
+ * to you under the Apache License, Version 2.0 (the
+ * "License"); you may not use this file except in compliance
+ * with the License.  You may obtain a copy of the License at
+ *
+ *     http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License.
+ */
+package org.apache.hadoop.hbase;
+
+import static org.junit.Assert.assertTrue;
+
+import org.apache.hadoop.hbase.KeyValue.Type;
+import org.apache.hadoop.hbase.util.Bytes;
+import org.junit.Test;
+import org.junit.experimental.categories.Category;
+@Category(SmallTests.class)
+public class TestCellComparator {
+
+  byte[] row1 = Bytes.toBytes("row1");
+  byte[] row2 = Bytes.toBytes("row2");
+  byte[] row_1_0 = Bytes.toBytes("row10");
+
+  byte[] fam1 = Bytes.toBytes("fam1");
+  byte[] fam2 = Bytes.toBytes("fam2");
+  byte[] fam_1_2 = Bytes.toBytes("fam12");
+
+  byte[] qual1 = Bytes.toBytes("qual1");
+  byte[] qual2 = Bytes.toBytes("qual2");
+
+  byte[] val = Bytes.toBytes("val");
+
+  @Test
+  public void testCompareCells() {
+    KeyValue kv1 = new KeyValue(row1, fam1, qual1, val);
+    KeyValue kv2 = new KeyValue(row2, fam1, qual1, val);
+    assertTrue((CellComparator.compareStatic(kv1, kv2, false)) < 0);
+
+    kv1 = new KeyValue(row1, fam2, qual1, val);
+    kv2 = new KeyValue(row1, fam1, qual1, val);
+    assertTrue((CellComparator.compareFamilies(kv1, kv2) > 0));
+
+    kv1 = new KeyValue(row1, fam1, qual1, 1l, val);
+    kv2 = new KeyValue(row1, fam1, qual1, 2l, val);
+    assertTrue((CellComparator.compareStatic(kv1, kv2, false) > 0));
+
+    kv1 = new KeyValue(row1, fam1, qual1, 1l, Type.Put);
+    kv2 = new KeyValue(row1, fam1, qual1, 1l, Type.Maximum);
+    assertTrue((CellComparator.compareStatic(kv1, kv2, false) > 0));
+
+    kv1 = new KeyValue(row1, fam1, qual1, 1l, Type.Put);
+    kv2 = new KeyValue(row1, fam_1_2, qual1, 1l, Type.Maximum);
+    assertTrue((CellComparator.compareCommonFamilyPrefix(kv1, kv2, 4) < 0));
+
+    kv1 = new KeyValue(row1, fam1, qual1, 1l, Type.Put);
+    kv2 = new KeyValue(row_1_0, fam_1_2, qual1, 1l, Type.Maximum);
+    assertTrue((CellComparator.compareCommonRowPrefix(kv1, kv2, 4) < 0));
+
+    kv1 = new KeyValue(row1, fam1, qual2, 1l, Type.Put);
+    kv2 = new KeyValue(row1, fam1, qual1, 1l, Type.Maximum);
+    assertTrue((CellComparator.compareCommonQualifierPrefix(kv1, kv2, 4) > 0));
+
+    kv1 = new KeyValue(row1, fam1, qual1, 1l, Type.Put);
+    kv2 = new KeyValue(row1, fam1, qual1, 1l, Type.Put);
+    assertTrue((CellComparator.equals(kv1, kv2)));
+  }
+}

Modified: hbase/trunk/hbase-prefix-tree/src/main/java/org/apache/hadoop/hbase/codec/prefixtree/PrefixTreeSeeker.java
URL: http://svn.apache.org/viewvc/hbase/trunk/hbase-prefix-tree/src/main/java/org/apache/hadoop/hbase/codec/prefixtree/PrefixTreeSeeker.java?rev=1583031&r1=1583030&r2=1583031&view=diff
==============================================================================
--- hbase/trunk/hbase-prefix-tree/src/main/java/org/apache/hadoop/hbase/codec/prefixtree/PrefixTreeSeeker.java (original)
+++ hbase/trunk/hbase-prefix-tree/src/main/java/org/apache/hadoop/hbase/codec/prefixtree/PrefixTreeSeeker.java Sat Mar 29 17:18:56 2014
@@ -24,8 +24,8 @@ import org.apache.hadoop.classification.
 import org.apache.hadoop.hbase.Cell;
 import org.apache.hadoop.hbase.CellUtil;
 import org.apache.hadoop.hbase.KeyValue;
-import org.apache.hadoop.hbase.KeyValueUtil;
 import org.apache.hadoop.hbase.KeyValue.KVComparator;
+import org.apache.hadoop.hbase.KeyValueUtil;
 import org.apache.hadoop.hbase.codec.prefixtree.decode.DecoderFactory;
 import org.apache.hadoop.hbase.codec.prefixtree.decode.PrefixTreeArraySearcher;
 import org.apache.hadoop.hbase.codec.prefixtree.scanner.CellScannerPosition;
@@ -152,15 +152,13 @@ public class PrefixTreeSeeker implements
       boolean forceBeforeOnExactMatch) {
     if (USE_POSITION_BEFORE) {
       return seekToOrBeforeUsingPositionAtOrBefore(keyOnlyBytes, offset, length,
-        forceBeforeOnExactMatch);
-    }else{
+          forceBeforeOnExactMatch);
+    } else {
       return seekToOrBeforeUsingPositionAtOrAfter(keyOnlyBytes, offset, length,
-        forceBeforeOnExactMatch);
+          forceBeforeOnExactMatch);
     }
   }
 
-
-
   /*
    * Support both of these options since the underlying PrefixTree supports both.  Possibly
    * expand the EncodedSeeker to utilize them both.
@@ -169,11 +167,22 @@ public class PrefixTreeSeeker implements
   protected int seekToOrBeforeUsingPositionAtOrBefore(byte[] keyOnlyBytes, int offset, int length,
       boolean seekBefore){
     // this does a deep copy of the key byte[] because the CellSearcher interface wants a Cell
-    KeyValue kv = KeyValue.createKeyValueFromKey(keyOnlyBytes, offset, length);
+    KeyValue kv = new KeyValue.KeyOnlyKeyValue(keyOnlyBytes, offset, length);
+
+    return seekToOrBeforeUsingPositionAtOrBefore(kv, seekBefore);
+  }
+
+  /*
+   * Support both of these options since the underlying PrefixTree supports
+   * both. Possibly expand the EncodedSeeker to utilize them both.
+   */
 
+  protected int seekToOrBeforeUsingPositionAtOrBefore(Cell kv, boolean seekBefore) {
+    // this does a deep copy of the key byte[] because the CellSearcher
+    // interface wants a Cell
     CellScannerPosition position = ptSearcher.seekForwardToOrBefore(kv);
 
-    if(CellScannerPosition.AT == position){
+    if (CellScannerPosition.AT == position) {
       if (seekBefore) {
         ptSearcher.previous();
         return 1;
@@ -184,16 +193,19 @@ public class PrefixTreeSeeker implements
     return 1;
   }
 
-
   protected int seekToOrBeforeUsingPositionAtOrAfter(byte[] keyOnlyBytes, int offset, int length,
-      boolean seekBefore){
-    // this does a deep copy of the key byte[] because the CellSearcher interface wants a Cell
-    KeyValue kv = KeyValue.createKeyValueFromKey(keyOnlyBytes, offset, length);
+      boolean seekBefore) {
+    // this does a deep copy of the key byte[] because the CellSearcher
+    // interface wants a Cell
+    KeyValue kv = new KeyValue.KeyOnlyKeyValue(keyOnlyBytes, offset, length);
+    return seekToOrBeforeUsingPositionAtOrAfter(kv, seekBefore);
+  }
 
-    //should probably switch this to use the seekForwardToOrBefore method
+  protected int seekToOrBeforeUsingPositionAtOrAfter(Cell kv, boolean seekBefore) {
+    // should probably switch this to use the seekForwardToOrBefore method
     CellScannerPosition position = ptSearcher.seekForwardToOrAfter(kv);
 
-    if(CellScannerPosition.AT == position){
+    if (CellScannerPosition.AT == position) {
       if (seekBefore) {
         ptSearcher.previous();
         return 1;
@@ -202,21 +214,21 @@ public class PrefixTreeSeeker implements
 
     }
 
-    if(CellScannerPosition.AFTER == position){
-      if(!ptSearcher.isBeforeFirst()){
+    if (CellScannerPosition.AFTER == position) {
+      if (!ptSearcher.isBeforeFirst()) {
         ptSearcher.previous();
       }
       return 1;
     }
 
-    if(position == CellScannerPosition.AFTER_LAST){
+    if (position == CellScannerPosition.AFTER_LAST) {
       if (seekBefore) {
         ptSearcher.previous();
       }
       return 1;
     }
 
-    throw new RuntimeException("unexpected CellScannerPosition:"+position);
+    throw new RuntimeException("unexpected CellScannerPosition:" + position);
   }
 
   @Override
@@ -225,4 +237,20 @@ public class PrefixTreeSeeker implements
     ByteBuffer bb = getKeyDeepCopy();
     return comparator.compareFlatKey(key, offset, length, bb.array(), bb.arrayOffset(), bb.limit());
   }
+
+  @Override
+  public int seekToKeyInBlock(Cell key, boolean forceBeforeOnExactMatch) {
+    if (USE_POSITION_BEFORE) {
+      return seekToOrBeforeUsingPositionAtOrBefore(key, forceBeforeOnExactMatch);
+    }else{
+      return seekToOrBeforeUsingPositionAtOrAfter(key, forceBeforeOnExactMatch);
+    }
+  }
+
+  @Override
+  public int compareKey(KVComparator comparator, Cell key) {
+    ByteBuffer bb = getKeyDeepCopy();
+    return comparator.compare(key,
+        new KeyValue.KeyOnlyKeyValue(bb.array(), bb.arrayOffset(), bb.limit()));
+  }
 }

Modified: hbase/trunk/hbase-prefix-tree/src/main/java/org/apache/hadoop/hbase/codec/prefixtree/decode/PrefixTreeArrayScanner.java
URL: http://svn.apache.org/viewvc/hbase/trunk/hbase-prefix-tree/src/main/java/org/apache/hadoop/hbase/codec/prefixtree/decode/PrefixTreeArrayScanner.java?rev=1583031&r1=1583030&r2=1583031&view=diff
==============================================================================
--- hbase/trunk/hbase-prefix-tree/src/main/java/org/apache/hadoop/hbase/codec/prefixtree/decode/PrefixTreeArrayScanner.java (original)
+++ hbase/trunk/hbase-prefix-tree/src/main/java/org/apache/hadoop/hbase/codec/prefixtree/decode/PrefixTreeArrayScanner.java Sat Mar 29 17:18:56 2014
@@ -28,7 +28,6 @@ import org.apache.hadoop.hbase.codec.pre
 import org.apache.hadoop.hbase.codec.prefixtree.decode.timestamp.MvccVersionDecoder;
 import org.apache.hadoop.hbase.codec.prefixtree.decode.timestamp.TimestampDecoder;
 import org.apache.hadoop.hbase.codec.prefixtree.encode.other.ColumnNodeType;
-import org.apache.hadoop.hbase.util.Bytes;
 
 /**
  * Extends PtCell and manipulates its protected fields.  Could alternatively contain a PtCell and
@@ -420,7 +419,7 @@ public class PrefixTreeArrayScanner exte
 
   protected int populateNonRowFieldsAndCompareTo(int cellNum, Cell key) {
     populateNonRowFields(cellNum);
-    return CellComparator.compareStatic(this, key);
+    return CellComparator.compareStatic(this, key, false);
   }
 
   protected void populateFirstNonRowFields() {

Modified: hbase/trunk/hbase-prefix-tree/src/main/java/org/apache/hadoop/hbase/codec/prefixtree/decode/PrefixTreeCell.java
URL: http://svn.apache.org/viewvc/hbase/trunk/hbase-prefix-tree/src/main/java/org/apache/hadoop/hbase/codec/prefixtree/decode/PrefixTreeCell.java?rev=1583031&r1=1583030&r2=1583031&view=diff
==============================================================================
--- hbase/trunk/hbase-prefix-tree/src/main/java/org/apache/hadoop/hbase/codec/prefixtree/decode/PrefixTreeCell.java (original)
+++ hbase/trunk/hbase-prefix-tree/src/main/java/org/apache/hadoop/hbase/codec/prefixtree/decode/PrefixTreeCell.java Sat Mar 29 17:18:56 2014
@@ -106,7 +106,7 @@ public class PrefixTreeCell implements C
 
   @Override
   public int compareTo(Cell other) {
-    return CellComparator.compareStatic(this, other);
+    return CellComparator.compareStatic(this, other, false);
   }
 
   @Override

Modified: hbase/trunk/hbase-server/src/main/java/org/apache/hadoop/hbase/io/HalfStoreFileReader.java
URL: http://svn.apache.org/viewvc/hbase/trunk/hbase-server/src/main/java/org/apache/hadoop/hbase/io/HalfStoreFileReader.java?rev=1583031&r1=1583030&r2=1583031&view=diff
==============================================================================
--- hbase/trunk/hbase-server/src/main/java/org/apache/hadoop/hbase/io/HalfStoreFileReader.java (original)
+++ hbase/trunk/hbase-server/src/main/java/org/apache/hadoop/hbase/io/HalfStoreFileReader.java Sat Mar 29 17:18:56 2014
@@ -27,6 +27,7 @@ import org.apache.hadoop.classification.
 import org.apache.hadoop.conf.Configuration;
 import org.apache.hadoop.fs.FileSystem;
 import org.apache.hadoop.fs.Path;
+import org.apache.hadoop.hbase.Cell;
 import org.apache.hadoop.hbase.HConstants;
 import org.apache.hadoop.hbase.KeyValue;
 import org.apache.hadoop.hbase.client.Scan;
@@ -55,9 +56,11 @@ public class HalfStoreFileReader extends
   // This is the key we split around.  Its the first possible entry on a row:
   // i.e. empty column and a timestamp of LATEST_TIMESTAMP.
   protected final byte [] splitkey;
-  
+
+  protected final Cell splitCell;
+
   private byte[] firstKey = null;
-  
+
   private boolean firstKeySeeked = false;
 
   /**
@@ -79,6 +82,7 @@ public class HalfStoreFileReader extends
     // have an actual midkey themselves. No midkey is how we indicate file is
     // not splittable.
     this.splitkey = r.getSplitKey();
+    this.splitCell = new KeyValue.KeyOnlyKeyValue(this.splitkey, 0, this.splitkey.length);
     // Is it top or bottom half?
     this.top = Reference.isTopFileRegion(r.getFileRegion());
   }
@@ -104,6 +108,7 @@ public class HalfStoreFileReader extends
     // have an actual midkey themselves. No midkey is how we indicate file is
     // not splittable.
     this.splitkey = r.getSplitKey();
+    this.splitCell = new KeyValue.KeyOnlyKeyValue(this.splitkey, 0, this.splitkey.length);
     // Is it top or bottom half?
     this.top = Reference.isTopFileRegion(r.getFileRegion());
   }
@@ -168,33 +173,21 @@ public class HalfStoreFileReader extends
         return true;
       }
 
+      @Override
       public boolean seekBefore(byte[] key) throws IOException {
         return seekBefore(key, 0, key.length);
       }
 
+      @Override
       public boolean seekBefore(byte [] key, int offset, int length)
       throws IOException {
-        if (top) {
-          byte[] fk = getFirstKey();
-          // This will be null when the file is empty in which we can not seekBefore to any key
-          if (fk == null) return false;
-          if (getComparator().compareFlatKey(key, offset, length, fk, 0,
-              fk.length) <= 0) {
-            return false;
-          }
-        } else {
-          // The equals sign isn't strictly necessary just here to be consistent with seekTo
-          if (getComparator().compareFlatKey(key, offset, length, splitkey, 0,
-              splitkey.length) >= 0) {
-            return this.delegate.seekBefore(splitkey, 0, splitkey.length);
-          }
-        }
-        return this.delegate.seekBefore(key, offset, length);
+        return seekBefore(new KeyValue.KeyOnlyKeyValue(key, offset, length));
       }
 
+      @Override
       public boolean seekTo() throws IOException {
         if (top) {
-          int r = this.delegate.seekTo(splitkey);
+          int r = this.delegate.seekTo(new KeyValue.KeyOnlyKeyValue(splitkey, 0, splitkey.length));
           if (r == HConstants.INDEX_KEY_MAGIC) {
             return true;
           }
@@ -219,55 +212,76 @@ public class HalfStoreFileReader extends
             splitkey, 0, splitkey.length) < 0;
       }
 
+      @Override
       public int seekTo(byte[] key) throws IOException {
         return seekTo(key, 0, key.length);
       }
 
+      @Override
       public int seekTo(byte[] key, int offset, int length) throws IOException {
+        return seekTo(new KeyValue.KeyOnlyKeyValue(key, offset, length));
+      }
+
+      @Override
+      public int reseekTo(byte[] key) throws IOException {
+        return reseekTo(key, 0, key.length);
+      }
+
+      @Override
+      public int reseekTo(byte[] key, int offset, int length)
+      throws IOException {
+        //This function is identical to the corresponding seekTo function except
+        //that we call reseekTo (and not seekTo) on the delegate.
+        return reseekTo(new KeyValue.KeyOnlyKeyValue(key, offset, length));
+      }
+
+      public org.apache.hadoop.hbase.io.hfile.HFile.Reader getReader() {
+        return this.delegate.getReader();
+      }
+
+      public boolean isSeeked() {
+        return this.delegate.isSeeked();
+      }
+
+      @Override
+      public int seekTo(Cell key) throws IOException {
         if (top) {
-          if (getComparator().compareFlatKey(key, offset, length, splitkey, 0,
-              splitkey.length) < 0) {
+          if (getComparator().compareOnlyKeyPortion(key, splitCell) < 0) {
             return -1;
           }
         } else {
-          if (getComparator().compareFlatKey(key, offset, length, splitkey, 0,
-              splitkey.length) >= 0) {
+          if (getComparator().compareOnlyKeyPortion(key, splitCell) >= 0) {
             // we would place the scanner in the second half.
             // it might be an error to return false here ever...
-            boolean res = delegate.seekBefore(splitkey, 0, splitkey.length);
+            boolean res = delegate.seekBefore(splitCell);
             if (!res) {
-              throw new IOException("Seeking for a key in bottom of file, but key exists in top of file, failed on seekBefore(midkey)");
+              throw new IOException(
+                  "Seeking for a key in bottom of file, but key exists in top of file, " +
+                  "failed on seekBefore(midkey)");
             }
             return 1;
           }
         }
-        return delegate.seekTo(key, offset, length);
-      }
-
-      @Override
-      public int reseekTo(byte[] key) throws IOException {
-        return reseekTo(key, 0, key.length);
+        return delegate.seekTo(key);
       }
 
       @Override
-      public int reseekTo(byte[] key, int offset, int length)
-      throws IOException {
-        //This function is identical to the corresponding seekTo function except
-        //that we call reseekTo (and not seekTo) on the delegate.
+      public int reseekTo(Cell key) throws IOException {
+        // This function is identical to the corresponding seekTo function
+        // except
+        // that we call reseekTo (and not seekTo) on the delegate.
         if (top) {
-          if (getComparator().compareFlatKey(key, offset, length, splitkey, 0,
-              splitkey.length) < 0) {
+          if (getComparator().compareOnlyKeyPortion(key, splitCell) < 0) {
             return -1;
           }
         } else {
-          if (getComparator().compareFlatKey(key, offset, length, splitkey, 0,
-              splitkey.length) >= 0) {
+          if (getComparator().compareOnlyKeyPortion(key, splitCell) >= 0) {
             // we would place the scanner in the second half.
             // it might be an error to return false here ever...
-            boolean res = delegate.seekBefore(splitkey, 0, splitkey.length);
+            boolean res = delegate.seekBefore(splitCell);
             if (!res) {
-              throw new IOException("Seeking for a key in bottom of file, but" +
-                  " key exists in top of file, failed on seekBefore(midkey)");
+              throw new IOException("Seeking for a key in bottom of file, but"
+                  + " key exists in top of file, failed on seekBefore(midkey)");
             }
             return 1;
           }
@@ -276,15 +290,28 @@ public class HalfStoreFileReader extends
           // skip the 'reseek' and just return 1.
           return 1;
         }
-        return delegate.reseekTo(key, offset, length);
+        return delegate.reseekTo(key);
       }
 
-      public org.apache.hadoop.hbase.io.hfile.HFile.Reader getReader() {
-        return this.delegate.getReader();
-      }
-
-      public boolean isSeeked() {
-        return this.delegate.isSeeked();
+      @Override
+      public boolean seekBefore(Cell key) throws IOException {
+        if (top) {
+          Cell fk = new KeyValue.KeyOnlyKeyValue(getFirstKey(), 0, getFirstKey().length);
+          // This will be null when the file is empty in which we can not
+          // seekBefore to any key
+          if (fk == null)
+            return false;
+          if (getComparator().compareOnlyKeyPortion(key, fk) <= 0) {
+            return false;
+          }
+        } else {
+          // The equals sign isn't strictly necessary just here to be consistent
+          // with seekTo
+          if (getComparator().compareOnlyKeyPortion(key, splitCell) >= 0) {
+            return this.delegate.seekBefore(splitCell);
+          }
+        }
+        return this.delegate.seekBefore(key);
       }
     };
   }
@@ -316,7 +343,7 @@ public class HalfStoreFileReader extends
     // Returns null to indicate file is not splitable.
     return null;
   }
-  
+
   @Override
   public byte[] getFirstKey() {
     if (!firstKeySeeked) {

Modified: hbase/trunk/hbase-server/src/main/java/org/apache/hadoop/hbase/io/hfile/HFileBlockIndex.java
URL: http://svn.apache.org/viewvc/hbase/trunk/hbase-server/src/main/java/org/apache/hadoop/hbase/io/hfile/HFileBlockIndex.java?rev=1583031&r1=1583030&r2=1583031&view=diff
==============================================================================
--- hbase/trunk/hbase-server/src/main/java/org/apache/hadoop/hbase/io/hfile/HFileBlockIndex.java (original)
+++ hbase/trunk/hbase-server/src/main/java/org/apache/hadoop/hbase/io/hfile/HFileBlockIndex.java Sat Mar 29 17:18:56 2014
@@ -36,9 +36,11 @@ import org.apache.commons.logging.LogFac
 import org.apache.hadoop.classification.InterfaceAudience;
 import org.apache.hadoop.conf.Configuration;
 import org.apache.hadoop.fs.FSDataOutputStream;
+import org.apache.hadoop.hbase.Cell;
 import org.apache.hadoop.hbase.HConstants;
 import org.apache.hadoop.hbase.KeyValue;
 import org.apache.hadoop.hbase.KeyValue.KVComparator;
+import org.apache.hadoop.hbase.KeyValueUtil;
 import org.apache.hadoop.hbase.io.HeapSize;
 import org.apache.hadoop.hbase.io.encoding.DataBlockEncoding;
 import org.apache.hadoop.hbase.io.hfile.HFile.CachingBlockReader;
@@ -165,8 +167,6 @@ public class HFileBlockIndex {
      * be called when the HFile version is larger than 1.
      *
      * @param key the key we are looking for
-     * @param keyOffset the offset of the key in its byte array
-     * @param keyLength the length of the key
      * @param currentBlock the current block, to avoid re-reading the same block
      * @param cacheBlocks
      * @param pread
@@ -177,12 +177,12 @@ public class HFileBlockIndex {
      * @return reader a basic way to load blocks
      * @throws IOException
      */
-    public HFileBlock seekToDataBlock(final byte[] key, int keyOffset,
-        int keyLength, HFileBlock currentBlock, boolean cacheBlocks,
+    public HFileBlock seekToDataBlock(final Cell key, HFileBlock currentBlock, boolean cacheBlocks,
         boolean pread, boolean isCompaction, DataBlockEncoding expectedDataBlockEncoding)
         throws IOException {
-      BlockWithScanInfo blockWithScanInfo = loadDataBlockWithScanInfo(key, keyOffset, keyLength,
-          currentBlock, cacheBlocks, pread, isCompaction, expectedDataBlockEncoding);
+      BlockWithScanInfo blockWithScanInfo = loadDataBlockWithScanInfo(key, currentBlock,
+          cacheBlocks,
+          pread, isCompaction, expectedDataBlockEncoding);
       if (blockWithScanInfo == null) {
         return null;
       } else {
@@ -191,30 +191,29 @@ public class HFileBlockIndex {
     }
 
     /**
-     * Return the BlockWithScanInfo which contains the DataBlock with other scan info
-     * such as nextIndexedKey.
-     * This function will only be called when the HFile version is larger than 1.
-     *
-     * @param key the key we are looking for
-     * @param keyOffset the offset of the key in its byte array
-     * @param keyLength the length of the key
-     * @param currentBlock the current block, to avoid re-reading the same
-     *          block
+     * Return the BlockWithScanInfo which contains the DataBlock with other scan
+     * info such as nextIndexedKey. This function will only be called when the
+     * HFile version is larger than 1.
+     * 
+     * @param key
+     *          the key we are looking for
+     * @param currentBlock
+     *          the current block, to avoid re-reading the same block
      * @param cacheBlocks
      * @param pread
      * @param isCompaction
      * @param expectedDataBlockEncoding the data block encoding the caller is
      *          expecting the data block to be in, or null to not perform this
      *          check and return the block irrespective of the encoding.
-     * @return the BlockWithScanInfo which contains the DataBlock with other scan info
-     *         such as nextIndexedKey.
+     * @return the BlockWithScanInfo which contains the DataBlock with other
+     *         scan info such as nextIndexedKey.
      * @throws IOException
      */
-    public BlockWithScanInfo loadDataBlockWithScanInfo(final byte[] key, int keyOffset,
-        int keyLength, HFileBlock currentBlock, boolean cacheBlocks,
+    public BlockWithScanInfo loadDataBlockWithScanInfo(Cell key, HFileBlock currentBlock,
+        boolean cacheBlocks,
         boolean pread, boolean isCompaction, DataBlockEncoding expectedDataBlockEncoding)
         throws IOException {
-      int rootLevelIndex = rootBlockContainingKey(key, keyOffset, keyLength);
+      int rootLevelIndex = rootBlockContainingKey(key);
       if (rootLevelIndex < 0 || rootLevelIndex >= blockOffsets.length) {
         return null;
       }
@@ -283,10 +282,13 @@ public class HFileBlockIndex {
         // Locate the entry corresponding to the given key in the non-root
         // (leaf or intermediate-level) index block.
         ByteBuffer buffer = block.getBufferWithoutHeader();
-        index = locateNonRootIndexEntry(buffer, key, keyOffset, keyLength, comparator);
+        index = locateNonRootIndexEntry(buffer, key, comparator);
         if (index == -1) {
+          // This has to be changed
+          // For now change this to key value
+          KeyValue kv = KeyValueUtil.ensureKeyValue(key);
           throw new IOException("The key "
-              + Bytes.toStringBinary(key, keyOffset, keyLength)
+              + Bytes.toStringBinary(kv.getKey(), kv.getKeyOffset(), kv.getKeyLength())
               + " is before the" + " first key of the non-root index block "
               + block);
         }
@@ -395,10 +397,35 @@ public class HFileBlockIndex {
      *         number of blocks - 1) or -1 if this file does not contain the
      *         request.
      */
-    public int rootBlockContainingKey(final byte[] key, int offset,
-        int length) {
-      int pos = Bytes.binarySearch(blockKeys, key, offset, length,
-          comparator);
+    public int rootBlockContainingKey(final byte[] key, int offset, int length) {
+      int pos = Bytes.binarySearch(blockKeys, key, offset, length, comparator);
+      // pos is between -(blockKeys.length + 1) to blockKeys.length - 1, see
+      // binarySearch's javadoc.
+
+      if (pos >= 0) {
+        // This means this is an exact match with an element of blockKeys.
+        assert pos < blockKeys.length;
+        return pos;
+      }
+
+      // Otherwise, pos = -(i + 1), where blockKeys[i - 1] < key < blockKeys[i],
+      // and i is in [0, blockKeys.length]. We are returning j = i - 1 such that
+      // blockKeys[j] <= key < blockKeys[j + 1]. In particular, j = -1 if
+      // key < blockKeys[0], meaning the file does not contain the given key.
+
+      int i = -pos - 1;
+      assert 0 <= i && i <= blockKeys.length;
+      return i - 1;
+    }
+
+    /**
+     * Finds the root-level index block containing the given key.
+     *
+     * @param key
+     *          Key to find
+     */
+    public int rootBlockContainingKey(final Cell key) {
+      int pos = Bytes.binarySearch(blockKeys, key, comparator);
       // pos is between -(blockKeys.length + 1) to blockKeys.length - 1, see
       // binarySearch's javadoc.
 
@@ -471,20 +498,19 @@ public class HFileBlockIndex {
      * Performs a binary search over a non-root level index block. Utilizes the
      * secondary index, which records the offsets of (offset, onDiskSize,
      * firstKey) tuples of all entries.
-     *
-     * @param key the key we are searching for offsets to individual entries in
+     * 
+     * @param key
+     *          the key we are searching for offsets to individual entries in
      *          the blockIndex buffer
-     * @param keyOffset the offset of the key in its byte array
-     * @param keyLength the length of the key
-     * @param nonRootIndex the non-root index block buffer, starting with the
-     *          secondary index. The position is ignored.
+     * @param nonRootIndex
+     *          the non-root index block buffer, starting with the secondary
+     *          index. The position is ignored.
      * @return the index i in [0, numEntries - 1] such that keys[i] <= key <
      *         keys[i + 1], if keys is the array of all keys being searched, or
      *         -1 otherwise
      * @throws IOException
      */
-    static int binarySearchNonRootIndex(byte[] key, int keyOffset,
-        int keyLength, ByteBuffer nonRootIndex,
+    static int binarySearchNonRootIndex(Cell key, ByteBuffer nonRootIndex,
         KVComparator comparator) {
 
       int numEntries = nonRootIndex.getInt(0);
@@ -499,7 +525,7 @@ public class HFileBlockIndex {
       // If we imagine that keys[-1] = -Infinity and
       // keys[numEntries] = Infinity, then we are maintaining an invariant that
       // keys[low - 1] < key < keys[high + 1] while narrowing down the range.
-
+      KeyValue.KeyOnlyKeyValue nonRootIndexKV = new KeyValue.KeyOnlyKeyValue();
       while (low <= high) {
         mid = (low + high) >>> 1;
 
@@ -520,9 +546,9 @@ public class HFileBlockIndex {
 
         // we have to compare in this order, because the comparator order
         // has special logic when the 'left side' is a special key.
-        int cmp = comparator.compareFlatKey(key, keyOffset, keyLength,
-            nonRootIndex.array(), nonRootIndex.arrayOffset() + midKeyOffset,
-            midLength);
+        nonRootIndexKV.setKey(nonRootIndex.array(),
+            nonRootIndex.arrayOffset() + midKeyOffset, midLength);
+        int cmp = comparator.compareOnlyKeyPortion(key, nonRootIndexKV);
 
         // key lives above the midpoint
         if (cmp > 0)
@@ -562,19 +588,18 @@ public class HFileBlockIndex {
      * of success, positions the provided buffer at the entry of interest, where
      * the file offset and the on-disk-size can be read.
      *
-     * @param nonRootBlock a non-root block without header. Initial position
-     *          does not matter.
-     * @param key the byte array containing the key
-     * @param keyOffset the offset of the key in its byte array
-     * @param keyLength the length of the key
-     * @return the index position where the given key was found,
-     *         otherwise return -1 in the case the given key is before the first key.
+     * @param nonRootBlock
+     *          a non-root block without header. Initial position does not
+     *          matter.
+     * @param key
+     *          the byte array containing the key
+     * @return the index position where the given key was found, otherwise
+     *         return -1 in the case the given key is before the first key.
      *
      */
-    static int locateNonRootIndexEntry(ByteBuffer nonRootBlock, byte[] key,
-        int keyOffset, int keyLength, KVComparator comparator) {
-      int entryIndex = binarySearchNonRootIndex(key, keyOffset, keyLength,
-          nonRootBlock, comparator);
+    static int locateNonRootIndexEntry(ByteBuffer nonRootBlock, Cell key,
+        KVComparator comparator) {
+      int entryIndex = binarySearchNonRootIndex(key, nonRootBlock, comparator);
 
       if (entryIndex != -1) {
         int numEntries = nonRootBlock.getInt(0);
@@ -584,8 +609,7 @@ public class HFileBlockIndex {
 
         // The offset of the entry we are interested in relative to the end of
         // the secondary index.
-        int entryRelOffset = nonRootBlock.getInt(Bytes.SIZEOF_INT
-            * (1 + entryIndex));
+        int entryRelOffset = nonRootBlock.getInt(Bytes.SIZEOF_INT * (1 + entryIndex));
 
         nonRootBlock.position(entriesOffset + entryRelOffset);
       }



Mime
View raw message