X-Git-Url: http://plrg.eecs.uci.edu/git/?a=blobdiff_plain;f=silo%2Fmasstree%2Fksearch.hh;fp=silo%2Fmasstree%2Fksearch.hh;h=aeb4a28ae59a3678c06b94b8210fab522bbb4fa8;hb=19b84c667216ff74f1b747e18b5542444dc54716;hp=0000000000000000000000000000000000000000;hpb=72045f68e6d1ad46133bdc507b409b676ce64957;p=c11concurrency-benchmarks.git

diff --git a/silo/masstree/ksearch.hh b/silo/masstree/ksearch.hh
new file mode 100644
index 0000000..aeb4a28
--- /dev/null
+++ b/silo/masstree/ksearch.hh
@@ -0,0 +1,173 @@
+/* Masstree
+ * Eddie Kohler, Yandong Mao, Robert Morris
+ * Copyright (c) 2012-2014 President and Fellows of Harvard College
+ * Copyright (c) 2012-2014 Massachusetts Institute of Technology
+ *
+ * Permission is hereby granted, free of charge, to any person obtaining a
+ * copy of this software and associated documentation files (the "Software"),
+ * to deal in the Software without restriction, subject to the conditions
+ * listed in the Masstree LICENSE file. These conditions include: you must
+ * preserve this copyright notice, and you cannot mention the copyright
+ * holders in advertising related to the Software without their permission.
+ * The Software is provided WITHOUT ANY WARRANTY, EXPRESS OR IMPLIED. This
+ * notice is a summary of the Masstree LICENSE file; the license in that file
+ * is legally binding.
+ */
+#ifndef KSEARCH_HH
+#define KSEARCH_HH 1
+#include "kpermuter.hh"
+
+template <typename KA, typename T>
+struct key_comparator {
+    int operator()(const KA& ka, const T& n, int p) {
+        return n.compare_key(ka, p);
+    }
+};
+
+struct key_indexed_position {
+    int i;
+    int p;
+    inline key_indexed_position() {
+    }
+    inline constexpr key_indexed_position(int i_, int p_)
+        : i(i_), p(p_) {
+    }
+};
+
+
+template <typename KA, typename T, typename F>
+int key_upper_bound_by(const KA& ka, const T& n, F comparator)
+{
+    typename key_permuter<T>::type perm = key_permuter<T>::permutation(n);
+    int l = 0, r = perm.size();
+    while (l < r) {
+        int m = (l + r) >> 1;
+        int mp = perm[m];
+        int cmp = comparator(ka, n, mp);
+        if (cmp < 0)
+            r = m;
+        else if (cmp == 0)
+            return m + 1;
+        else
+            l = m + 1;
+    }
+    return l;
+}
+
+template <typename KA, typename T>
+inline int key_upper_bound(const KA& ka, const T& n)
+{
+    return key_upper_bound_by(ka, n, key_comparator<KA, T>());
+}
+
+template <typename KA, typename T, typename F>
+key_indexed_position key_lower_bound_by(const KA& ka, const T& n, F comparator)
+{
+    typename key_permuter<T>::type perm = key_permuter<T>::permutation(n);
+    int l = 0, r = perm.size();
+    while (l < r) {
+        int m = (l + r) >> 1;
+        int mp = perm[m];
+        int cmp = comparator(ka, n, mp);
+        if (cmp < 0)
+            r = m;
+        else if (cmp == 0)
+            return key_indexed_position(m, mp);
+        else
+            l = m + 1;
+    }
+    return key_indexed_position(l, -1);
+}
+
+template <typename KA, typename T>
+inline key_indexed_position key_lower_bound(const KA& ka, const T& n)
+{
+    return key_lower_bound_by(ka, n, key_comparator<KA, T>());
+}
+
+
+template <typename KA, typename T, typename F>
+int key_find_upper_bound_by(const KA& ka, const T& n, F comparator)
+{
+    typename key_permuter<T>::type perm = key_permuter<T>::permutation(n);
+    int l = 0, r = perm.size();
+    while (l < r) {
+        int lp = perm[l];
+        int cmp = comparator(ka, n, lp);
+        if (cmp < 0)
+            break;
+        else
+            ++l;
+    }
+    return l;
+}
+
+template <typename KA, typename T, typename F>
+key_indexed_position key_find_lower_bound_by(const KA& ka, const T& n, F comparator)
+{
+    typename key_permuter<T>::type perm = key_permuter<T>::permutation(n);
+    int l = 0, r = perm.size();
+    while (l < r) {
+        int lp = perm[l];
+        int cmp = comparator(ka, n, lp);
+        if (cmp < 0)
+            break;
+        else if (cmp == 0)
+            return key_indexed_position(l, lp);
+        else
+            ++l;
+    }
+    return key_indexed_position(l, -1);
+}
+
+
+struct key_bound_binary {
+    static constexpr bool is_binary = true;
+    template <typename KA, typename T>
+    static inline int upper(const KA& ka, const T& n) {
+        return key_upper_bound_by(ka, n, key_comparator<KA, T>());
+    }
+    template <typename KA, typename T>
+    static inline key_indexed_position lower(const KA& ka, const T& n) {
+        return key_lower_bound_by(ka, n, key_comparator<KA, T>());
+    }
+    template <typename KA, typename T, typename F>
+    static inline key_indexed_position lower_by(const KA& ka, const T& n, F comparator) {
+        return key_lower_bound_by(ka, n, comparator);
+    }
+};
+
+struct key_bound_linear {
+    static constexpr bool is_binary = false;
+    template <typename KA, typename T>
+    static inline int upper(const KA& ka, const T& n) {
+        return key_find_upper_bound_by(ka, n, key_comparator<KA, T>());
+    }
+    template <typename KA, typename T>
+    static inline key_indexed_position lower(const KA& ka, const T& n) {
+        return key_find_lower_bound_by(ka, n, key_comparator<KA, T>());
+    }
+    template <typename KA, typename T, typename F>
+    static inline key_indexed_position lower_by(const KA& ka, const T& n, F comparator) {
+        return key_find_lower_bound_by(ka, n, comparator);
+    }
+};
+
+
+enum {
+    bound_method_fast = 0,
+    bound_method_binary,
+    bound_method_linear
+};
+template <int max_size, int method = bound_method_fast> struct key_bound {};
+template <int max_size> struct key_bound<max_size, bound_method_binary> {
+    typedef key_bound_binary type;
+};
+template <int max_size> struct key_bound<max_size, bound_method_linear> {
+    typedef key_bound_linear type;
+};
+template <int max_size> struct key_bound<max_size, bound_method_fast> {
+    typedef typename key_bound<max_size, (max_size > 16 ? bound_method_binary : bound_method_linear)>::type type;
+};
+
+#endif