kudu-commits mailing list archives

Site index · List index
Message view « Date » · « Thread »
Top « Date » · « Thread »
From danburk...@apache.org
Subject incubator-kudu git commit: Add TypeInfo::AreConsecutive(a, b)
Date Wed, 17 Feb 2016 01:34:10 GMT
Repository: incubator-kudu
Updated Branches:
  refs/heads/master 3378c7c06 -> a2a2f3f71


Add TypeInfo::AreConsecutive(a, b)

AreConsecutive tests if two column values are consecutive
(e.g. 1, 2 or "abc", "abc\0"). This method will be used in the future to
determine whether a lower-bound inclusive/upper-bound exclusive column range
predicate is actually an equality predicate.

Change-Id: I64b8ffb5400be1132e400385a5995849874100b2
Reviewed-on: http://gerrit.cloudera.org:8080/2136
Reviewed-by: Todd Lipcon <todd@apache.org>
Tested-by: Kudu Jenkins


Project: http://git-wip-us.apache.org/repos/asf/incubator-kudu/repo
Commit: http://git-wip-us.apache.org/repos/asf/incubator-kudu/commit/a2a2f3f7
Tree: http://git-wip-us.apache.org/repos/asf/incubator-kudu/tree/a2a2f3f7
Diff: http://git-wip-us.apache.org/repos/asf/incubator-kudu/diff/a2a2f3f7

Branch: refs/heads/master
Commit: a2a2f3f7106aa625471cfa93db000f6452818dee
Parents: 3378c7c
Author: Dan Burkert <dan@cloudera.com>
Authored: Thu Feb 4 18:25:14 2016 -0800
Committer: Dan Burkert <dan@cloudera.com>
Committed: Wed Feb 17 01:33:16 2016 +0000

----------------------------------------------------------------------
 src/kudu/common/types-test.cc | 68 ++++++++++++++++++++++++++++++++++
 src/kudu/common/types.cc      |  7 +++-
 src/kudu/common/types.h       | 75 +++++++++++++++++++++++++++++++++++++-
 3 files changed, 147 insertions(+), 3 deletions(-)
----------------------------------------------------------------------


http://git-wip-us.apache.org/repos/asf/incubator-kudu/blob/a2a2f3f7/src/kudu/common/types-test.cc
----------------------------------------------------------------------
diff --git a/src/kudu/common/types-test.cc b/src/kudu/common/types-test.cc
index ed56606..49280d5 100644
--- a/src/kudu/common/types-test.cc
+++ b/src/kudu/common/types-test.cc
@@ -15,11 +15,21 @@
 // specific language governing permissions and limitations
 // under the License.
 
+#include <cmath>
 #include <gtest/gtest.h>
+#include <string>
+#include <tuple>
+#include <vector>
 
 #include "kudu/common/types.h"
+#include "kudu/gutil/strings/substitute.h"
 
+using std::get;
+using std::make_tuple;
+using std::nextafter;
 using std::string;
+using std::tuple;
+using std::vector;
 
 namespace kudu {
 
@@ -60,5 +70,63 @@ TEST(TestTypes, TestTimestampPrinting) {
   ASSERT_EQ("294247-01-10 04:00:54.775807 GMT", result);
 }
 
+namespace {
+  template <typename T>
+  void TestAreConsecutive(DataType type, vector<tuple<T, T, bool>> test_cases)
{
+    const TypeInfo* info = GetTypeInfo(type);
+    for (auto test_case : test_cases) {
+      string lower, upper;
+      info->AppendDebugStringForValue(&get<0>(test_case), &lower);
+      info->AppendDebugStringForValue(&get<1>(test_case), &upper);
+      SCOPED_TRACE(strings::Substitute("lower: $0, upper: $1, expected: $2",
+                                       lower, upper, get<2>(test_case)));
+
+      ASSERT_EQ(get<2>(test_case), info->AreConsecutive(&get<0>(test_case),
&get<1>(test_case)));
+    }
+  }
+} // anonymous namespace
+
+TEST(TestTypes, TestAreConsecutiveInteger) {
+  vector<tuple<int64_t, int64_t, bool>> test_cases {
+    make_tuple(0, 0, false),
+    make_tuple(0, 1, true),
+    make_tuple(-1, 0, true),
+    make_tuple(INT64_MAX, 0, false),
+    make_tuple(0, INT64_MAX, false),
+    make_tuple(INT64_MAX - 1, INT64_MAX, true),
+    make_tuple(INT64_MIN, 0, false),
+    make_tuple(INT64_MIN, INT64_MIN + 1, true),
+    make_tuple(INT64_MIN, 0, false),
+    make_tuple(-32, -31, true),
+    make_tuple(42, 43, true),
+    make_tuple(99, -98, false),
+  };
+  TestAreConsecutive(INT64, test_cases);
+}
+
+TEST(TestTypes, TestAreConsecutiveDouble) {
+  vector<tuple<double, double, bool>> test_cases {
+    make_tuple(0.0, 1.0, false),
+    make_tuple(0.0, 0.1, false),
+    make_tuple(0, nextafter(0, INFINITY), true),
+    make_tuple(123.45, nextafter(123.45, INFINITY), true),
+    make_tuple(-123.45, nextafter(-123.45, INFINITY), true),
+    make_tuple(123.45, 88.0, false),
+  };
+  TestAreConsecutive(DOUBLE, test_cases);
+}
+
+TEST(TestTypes, TestAreConsecutiveString) {
+  vector<tuple<Slice, Slice, bool>> test_cases {
+    make_tuple("abc", "abc", false),
+    make_tuple("abc", Slice("abc\0", 4), true),
+    make_tuple("", Slice("\0", 1), true),
+    make_tuple("", Slice("\1", 1), false),
+    make_tuple("", "", false),
+    make_tuple("", "a", false),
+    make_tuple("abacadaba", Slice("abacadaba\0", 10), true),
+  };
+  TestAreConsecutive(STRING, test_cases);
+}
 
 } // namespace kudu

http://git-wip-us.apache.org/repos/asf/incubator-kudu/blob/a2a2f3f7/src/kudu/common/types.cc
----------------------------------------------------------------------
diff --git a/src/kudu/common/types.cc b/src/kudu/common/types.cc
index ca29e41..7c1277d 100644
--- a/src/kudu/common/types.cc
+++ b/src/kudu/common/types.cc
@@ -35,7 +35,8 @@ TypeInfo::TypeInfo(TypeTraitsClass t)
     size_(TypeTraitsClass::size),
     min_value_(TypeTraitsClass::min_value()),
     append_func_(TypeTraitsClass::AppendDebugStringForValue),
-    compare_func_(TypeTraitsClass::Compare) {
+    compare_func_(TypeTraitsClass::Compare),
+    are_consecutive_func_(TypeTraitsClass::AreConsecutive) {
 }
 
 void TypeInfo::AppendDebugStringForValue(const void *ptr, string *str) const {
@@ -46,6 +47,10 @@ int TypeInfo::Compare(const void *lhs, const void *rhs) const {
   return compare_func_(lhs, rhs);
 }
 
+bool TypeInfo::AreConsecutive(const void* a, const void* b) const {
+  return are_consecutive_func_(a, b);
+}
+
 class TypeInfoResolver {
  public:
   const TypeInfo* GetTypeInfo(DataType t) {

http://git-wip-us.apache.org/repos/asf/incubator-kudu/blob/a2a2f3f7/src/kudu/common/types.h
----------------------------------------------------------------------
diff --git a/src/kudu/common/types.h b/src/kudu/common/types.h
index 470a12b..f10e6d7 100644
--- a/src/kudu/common/types.h
+++ b/src/kudu/common/types.h
@@ -20,6 +20,7 @@
 
 #include <glog/logging.h>
 
+#include <cmath>
 #include <stdint.h>
 #include <string>
 
@@ -54,6 +55,8 @@ class TypeInfo {
   const size_t size() const { return size_; }
   void AppendDebugStringForValue(const void *ptr, string *str) const;
   int Compare(const void *lhs, const void *rhs) const;
+  // Returns true if increment(a) is equal to b.
+  bool AreConsecutive(const void* a, const void* b) const;
   void CopyMinValue(void* dst) const {
     memcpy(dst, min_value_, size_);
   }
@@ -73,6 +76,9 @@ class TypeInfo {
 
   typedef int (*CompareFunc)(const void *, const void *);
   const CompareFunc compare_func_;
+
+  typedef bool (*AreConsecutiveFunc)(const void*, const void*);
+  const AreConsecutiveFunc are_consecutive_func_;
 };
 
 template<DataType Type> struct DataTypeTraits {};
@@ -91,6 +97,23 @@ static int GenericCompare(const void *lhs, const void *rhs) {
   }
 }
 
+template<DataType Type>
+static int AreIntegersConsecutive(const void* a, const void* b) {
+  typedef typename DataTypeTraits<Type>::cpp_type CppType;
+  CppType a_int = *reinterpret_cast<const CppType*>(a);
+  CppType b_int = *reinterpret_cast<const CppType*>(b);
+  // Avoid overflow by checking relative position first.
+  return a_int < b_int && a_int + 1 == b_int;
+}
+
+template<DataType Type>
+static int AreFloatsConsecutive(const void* a, const void* b) {
+  typedef typename DataTypeTraits<Type>::cpp_type CppType;
+  CppType a_float = *reinterpret_cast<const CppType*>(a);
+  CppType b_float = *reinterpret_cast<const CppType*>(b);
+  return a_float < b_float && std::nextafter(a_float, b_float) == b_float;
+}
+
 template<>
 struct DataTypeTraits<UINT8> {
   static const DataType physical_type = UINT8;
@@ -104,6 +127,9 @@ struct DataTypeTraits<UINT8> {
   static int Compare(const void *lhs, const void *rhs) {
     return GenericCompare<UINT8>(lhs, rhs);
   }
+  static bool AreConsecutive(const void* a, const void* b) {
+    return AreIntegersConsecutive<UINT8>(a, b);
+  }
   static const cpp_type* min_value() {
     return &MathLimits<cpp_type>::kMin;
   }
@@ -122,6 +148,9 @@ struct DataTypeTraits<INT8> {
   static int Compare(const void *lhs, const void *rhs) {
     return GenericCompare<INT8>(lhs, rhs);
   }
+  static bool AreConsecutive(const void* a, const void* b) {
+    return AreIntegersConsecutive<INT8>(a, b);
+  }
   static const cpp_type* min_value() {
     return &MathLimits<cpp_type>::kMin;
   }
@@ -140,6 +169,9 @@ struct DataTypeTraits<UINT16> {
   static int Compare(const void *lhs, const void *rhs) {
     return GenericCompare<UINT16>(lhs, rhs);
   }
+  static bool AreConsecutive(const void* a, const void* b) {
+    return AreIntegersConsecutive<UINT16>(a, b);
+  }
   static const cpp_type* min_value() {
     return &MathLimits<cpp_type>::kMin;
   }
@@ -158,6 +190,9 @@ struct DataTypeTraits<INT16> {
   static int Compare(const void *lhs, const void *rhs) {
     return GenericCompare<INT16>(lhs, rhs);
   }
+  static bool AreConsecutive(const void* a, const void* b) {
+    return AreIntegersConsecutive<INT16>(a, b);
+  }
   static const cpp_type* min_value() {
     return &MathLimits<cpp_type>::kMin;
   }
@@ -176,6 +211,9 @@ struct DataTypeTraits<UINT32> {
   static int Compare(const void *lhs, const void *rhs) {
     return GenericCompare<UINT32>(lhs, rhs);
   }
+  static bool AreConsecutive(const void* a, const void* b) {
+    return AreIntegersConsecutive<UINT32>(a, b);
+  }
   static const cpp_type* min_value() {
     return &MathLimits<cpp_type>::kMin;
   }
@@ -194,6 +232,9 @@ struct DataTypeTraits<INT32> {
   static int Compare(const void *lhs, const void *rhs) {
     return GenericCompare<INT32>(lhs, rhs);
   }
+  static bool AreConsecutive(const void* a, const void* b) {
+    return AreIntegersConsecutive<INT32>(a, b);
+  }
   static const cpp_type* min_value() {
     return &MathLimits<cpp_type>::kMin;
   }
@@ -212,6 +253,9 @@ struct DataTypeTraits<UINT64> {
   static int Compare(const void *lhs, const void *rhs) {
     return GenericCompare<UINT64>(lhs, rhs);
   }
+  static bool AreConsecutive(const void* a, const void* b) {
+    return AreIntegersConsecutive<UINT64>(a, b);
+  }
   static const cpp_type* min_value() {
     return &MathLimits<cpp_type>::kMin;
   }
@@ -230,6 +274,9 @@ struct DataTypeTraits<INT64> {
   static int Compare(const void *lhs, const void *rhs) {
     return GenericCompare<INT64>(lhs, rhs);
   }
+  static bool AreConsecutive(const void* a, const void* b) {
+    return AreIntegersConsecutive<INT64>(a, b);
+  }
   static const cpp_type* min_value() {
     return &MathLimits<cpp_type>::kMin;
   }
@@ -248,6 +295,9 @@ struct DataTypeTraits<FLOAT> {
   static int Compare(const void *lhs, const void *rhs) {
     return GenericCompare<FLOAT>(lhs, rhs);
   }
+  static bool AreConsecutive(const void* a, const void* b) {
+    return AreFloatsConsecutive<FLOAT>(a, b);
+  }
   static const cpp_type* min_value() {
     return &MathLimits<cpp_type>::kMin;
   }
@@ -266,6 +316,9 @@ struct DataTypeTraits<DOUBLE> {
   static int Compare(const void *lhs, const void *rhs) {
     return GenericCompare<DOUBLE>(lhs, rhs);
   }
+  static bool AreConsecutive(const void* a, const void* b) {
+    return AreFloatsConsecutive<DOUBLE>(a, b);
+  }
   static const cpp_type* min_value() {
     return &MathLimits<cpp_type>::kMin;
   }
@@ -282,12 +335,24 @@ struct DataTypeTraits<BINARY> {
     const Slice *s = reinterpret_cast<const Slice *>(val);
     str->append(strings::CHexEscape(s->ToString()));
   }
-
   static int Compare(const void *lhs, const void *rhs) {
     const Slice *lhs_slice = reinterpret_cast<const Slice *>(lhs);
     const Slice *rhs_slice = reinterpret_cast<const Slice *>(rhs);
     return lhs_slice->compare(*rhs_slice);
   }
+  static bool AreConsecutive(const void* a, const void* b) {
+    const Slice *a_slice = reinterpret_cast<const Slice *>(a);
+    const Slice *b_slice = reinterpret_cast<const Slice *>(b);
+    size_t a_size = a_slice->size();
+    size_t b_size = b_slice->size();
+
+    // Strings are consecutive if the larger is equal to the lesser with an
+    // additional null byte.
+
+    return a_size + 1 == b_size
+        && (*b_slice)[a_size] == 0
+        && a_slice->compare(Slice(b_slice->data(), a_size)) == 0;
+  }
   static const cpp_type* min_value() {
     static Slice s("");
     return &s;
@@ -304,10 +369,12 @@ struct DataTypeTraits<BOOL> {
   static void AppendDebugStringForValue(const void* val, string* str) {
     str->append(*reinterpret_cast<const bool *>(val) ? "true" : "false");
   }
-
   static int Compare(const void *lhs, const void *rhs) {
     return GenericCompare<BOOL>(lhs, rhs);
   }
+  static bool AreConsecutive(const void* a, const void* b) {
+    return AreIntegersConsecutive<BOOL>(a, b);
+  }
   static const cpp_type* min_value() {
     static bool b = false;
     return &b;
@@ -329,6 +396,10 @@ struct DerivedTypeTraits {
     return DataTypeTraits<PhysicalType>::Compare(lhs, rhs);
   }
 
+  static bool AreConsecutive(const void* a, const void* b) {
+    return DataTypeTraits<PhysicalType>::AreConsecutive(a, b);
+  }
+
   static const cpp_type* min_value() {
     return DataTypeTraits<PhysicalType>::min_value();
   }


Mime
View raw message