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

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