From 9907b61c574baf0747747f1c512f7cdd88ebed25 Mon Sep 17 00:00:00 2001
From: KunoiSayami <i@leanhe.dev>
Date: Tue, 9 Nov 2021 22:00:01 +0800
Subject: init

---
 util/comparator.cc | 75 ++++++++++++++++++++++++++++++++++++++++++++++++++++++
 1 file changed, 75 insertions(+)
 create mode 100644 util/comparator.cc

(limited to 'util/comparator.cc')

diff --git a/util/comparator.cc b/util/comparator.cc
new file mode 100644
index 0000000..c5766e9
--- /dev/null
+++ b/util/comparator.cc
@@ -0,0 +1,75 @@
+// Copyright (c) 2011 The LevelDB Authors. All rights reserved.
+// Use of this source code is governed by a BSD-style license that can be
+// found in the LICENSE file. See the AUTHORS file for names of contributors.
+
+#include "leveldb/comparator.h"
+
+#include <algorithm>
+#include <cstdint>
+#include <string>
+#include <type_traits>
+
+#include "leveldb/slice.h"
+#include "util/logging.h"
+#include "util/no_destructor.h"
+
+namespace leveldb {
+
+Comparator::~Comparator() = default;
+
+namespace {
+class BytewiseComparatorImpl : public Comparator {
+ public:
+  BytewiseComparatorImpl() = default;
+
+  const char* Name() const override { return "leveldb.BytewiseComparator"; }
+
+  int Compare(const Slice& a, const Slice& b) const override {
+    return a.compare(b);
+  }
+
+  void FindShortestSeparator(std::string* start,
+                             const Slice& limit) const override {
+    // Find length of common prefix
+    size_t min_length = std::min(start->size(), limit.size());
+    size_t diff_index = 0;
+    while ((diff_index < min_length) &&
+           ((*start)[diff_index] == limit[diff_index])) {
+      diff_index++;
+    }
+
+    if (diff_index >= min_length) {
+      // Do not shorten if one string is a prefix of the other
+    } else {
+      uint8_t diff_byte = static_cast<uint8_t>((*start)[diff_index]);
+      if (diff_byte < static_cast<uint8_t>(0xff) &&
+          diff_byte + 1 < static_cast<uint8_t>(limit[diff_index])) {
+        (*start)[diff_index]++;
+        start->resize(diff_index + 1);
+        assert(Compare(*start, limit) < 0);
+      }
+    }
+  }
+
+  void FindShortSuccessor(std::string* key) const override {
+    // Find first character that can be incremented
+    size_t n = key->size();
+    for (size_t i = 0; i < n; i++) {
+      const uint8_t byte = (*key)[i];
+      if (byte != static_cast<uint8_t>(0xff)) {
+        (*key)[i] = byte + 1;
+        key->resize(i + 1);
+        return;
+      }
+    }
+    // *key is a run of 0xffs.  Leave it alone.
+  }
+};
+}  // namespace
+
+const Comparator* BytewiseComparator() {
+  static NoDestructor<BytewiseComparatorImpl> singleton;
+  return singleton.get();
+}
+
+}  // namespace leveldb
-- 
cgit v1.3.1