ceph/src/rocksdb/java/src/main/java/org/rocksdb/util/DirectBytewiseComparator.java

   1 // Copyright (c) 2011-present, Facebook, Inc.  All rights reserved.
   2 // This source code is licensed under the BSD-style license found in the
   3 // LICENSE file in the root directory of this source tree. An additional grant
   4 // of patent rights can be found in the PATENTS file in the same directory.
   5
   6 package org.rocksdb.util;
   7
   8 import org.rocksdb.ComparatorOptions;
   9 import org.rocksdb.DirectComparator;
  10 import org.rocksdb.DirectSlice;
  11
  12 import java.nio.ByteBuffer;
  13
  14 /**
  15  * This is a Java Native implementation of the C++
  16  * equivalent BytewiseComparatorImpl using {@link DirectSlice}
  17  *
  18  * The performance of Comparators implemented in Java is always
  19  * less than their C++ counterparts due to the bridging overhead,
  20  * as such you likely don't want to use this apart from benchmarking
  21  * and you most likely instead wanted
  22  * {@link org.rocksdb.BuiltinComparator#BYTEWISE_COMPARATOR}
  23  */
  24 public class DirectBytewiseComparator extends DirectComparator {
  25
  26   public DirectBytewiseComparator(final ComparatorOptions copt) {
  27     super(copt);
  28   }
  29
  30   @Override
  31   public String name() {
  32     return "rocksdb.java.DirectBytewiseComparator";
  33   }
  34
  35   @Override
  36   public int compare(final DirectSlice a, final DirectSlice b) {
  37     return a.data().compareTo(b.data());
  38   }
  39
  40   @Override
  41   public String findShortestSeparator(final String start,
  42       final DirectSlice limit) {
  43     final byte[] startBytes = start.getBytes();
  44
  45     // Find length of common prefix
  46     final int min_length = Math.min(startBytes.length, limit.size());
  47     int diff_index = 0;
  48     while ((diff_index < min_length) &&
  49         (startBytes[diff_index] == limit.get(diff_index))) {
  50       diff_index++;
  51     }
  52
  53     if (diff_index >= min_length) {
  54       // Do not shorten if one string is a prefix of the other
  55     } else {
  56       final byte diff_byte = startBytes[diff_index];
  57       if(diff_byte < 0xff && diff_byte + 1 < limit.get(diff_index)) {
  58         final byte shortest[] = new byte[diff_index + 1];
  59         System.arraycopy(startBytes, 0, shortest, 0, diff_index + 1);
  60         shortest[diff_index]++;
  61         assert(ByteBuffer.wrap(shortest).compareTo(limit.data()) < 0);
  62         return new String(shortest);
  63       }
  64     }
  65
  66     return null;
  67   }
  68
  69   @Override
  70   public String findShortSuccessor(final String key) {
  71     final byte[] keyBytes = key.getBytes();
  72
  73     // Find first character that can be incremented
  74     final int n = keyBytes.length;
  75     for (int i = 0; i < n; i++) {
  76       final byte byt = keyBytes[i];
  77       if (byt != 0xff) {
  78         final byte shortSuccessor[] = new byte[i + 1];
  79         System.arraycopy(keyBytes, 0, shortSuccessor, 0, i + 1);
  80         shortSuccessor[i]++;
  81         return new String(shortSuccessor);
  82       }
  83     }
  84     // *key is a run of 0xffs.  Leave it alone.
  85
  86     return null;
  87   }
  88 }