silo/masstree/ksearch.hh

   1 /* Masstree
   2  * Eddie Kohler, Yandong Mao, Robert Morris
   3  * Copyright (c) 2012-2014 President and Fellows of Harvard College
   4  * Copyright (c) 2012-2014 Massachusetts Institute of Technology
   5  *
   6  * Permission is hereby granted, free of charge, to any person obtaining a
   7  * copy of this software and associated documentation files (the "Software"),
   8  * to deal in the Software without restriction, subject to the conditions
   9  * listed in the Masstree LICENSE file. These conditions include: you must
  10  * preserve this copyright notice, and you cannot mention the copyright
  11  * holders in advertising related to the Software without their permission.
  12  * The Software is provided WITHOUT ANY WARRANTY, EXPRESS OR IMPLIED. This
  13  * notice is a summary of the Masstree LICENSE file; the license in that file
  14  * is legally binding.
  15  */
  16 #ifndef KSEARCH_HH
  17 #define KSEARCH_HH 1
  18 #include "kpermuter.hh"
  19
  20 template <typename KA, typename T>
  21 struct key_comparator {
  22     int operator()(const KA& ka, const T& n, int p) {
  23         return n.compare_key(ka, p);
  24     }
  25 };
  26
  27 struct key_indexed_position {
  28     int i;
  29     int p;
  30     inline key_indexed_position() {
  31     }
  32     inline constexpr key_indexed_position(int i_, int p_)
  33         : i(i_), p(p_) {
  34     }
  35 };
  36
  37
  38 template <typename KA, typename T, typename F>
  39 int key_upper_bound_by(const KA& ka, const T& n, F comparator)
  40 {
  41     typename key_permuter<T>::type perm = key_permuter<T>::permutation(n);
  42     int l = 0, r = perm.size();
  43     while (l < r) {
  44         int m = (l + r) >> 1;
  45         int mp = perm[m];
  46         int cmp = comparator(ka, n, mp);
  47         if (cmp < 0)
  48             r = m;
  49         else if (cmp == 0)
  50             return m + 1;
  51         else
  52             l = m + 1;
  53     }
  54     return l;
  55 }
  56
  57 template <typename KA, typename T>
  58 inline int key_upper_bound(const KA& ka, const T& n)
  59 {
  60     return key_upper_bound_by(ka, n, key_comparator<KA, T>());
  61 }
  62
  63 template <typename KA, typename T, typename F>
  64 key_indexed_position key_lower_bound_by(const KA& ka, const T& n, F comparator)
  65 {
  66     typename key_permuter<T>::type perm = key_permuter<T>::permutation(n);
  67     int l = 0, r = perm.size();
  68     while (l < r) {
  69         int m = (l + r) >> 1;
  70         int mp = perm[m];
  71         int cmp = comparator(ka, n, mp);
  72         if (cmp < 0)
  73             r = m;
  74         else if (cmp == 0)
  75             return key_indexed_position(m, mp);
  76         else
  77             l = m + 1;
  78     }
  79     return key_indexed_position(l, -1);
  80 }
  81
  82 template <typename KA, typename T>
  83 inline key_indexed_position key_lower_bound(const KA& ka, const T& n)
  84 {
  85     return key_lower_bound_by(ka, n, key_comparator<KA, T>());
  86 }
  87
  88
  89 template <typename KA, typename T, typename F>
  90 int key_find_upper_bound_by(const KA& ka, const T& n, F comparator)
  91 {
  92     typename key_permuter<T>::type perm = key_permuter<T>::permutation(n);
  93     int l = 0, r = perm.size();
  94     while (l < r) {
  95         int lp = perm[l];
  96         int cmp = comparator(ka, n, lp);
  97         if (cmp < 0)
  98             break;
  99         else
 100             ++l;
 101     }
 102     return l;
 103 }
 104
 105 template <typename KA, typename T, typename F>
 106 key_indexed_position key_find_lower_bound_by(const KA& ka, const T& n, F comparator)
 107 {
 108     typename key_permuter<T>::type perm = key_permuter<T>::permutation(n);
 109     int l = 0, r = perm.size();
 110     while (l < r) {
 111         int lp = perm[l];
 112         int cmp = comparator(ka, n, lp);
 113         if (cmp < 0)
 114             break;
 115         else if (cmp == 0)
 116             return key_indexed_position(l, lp);
 117         else
 118             ++l;
 119     }
 120     return key_indexed_position(l, -1);
 121 }
 122
 123
 124 struct key_bound_binary {
 125     static constexpr bool is_binary = true;
 126     template <typename KA, typename T>
 127     static inline int upper(const KA& ka, const T& n) {
 128         return key_upper_bound_by(ka, n, key_comparator<KA, T>());
 129     }
 130     template <typename KA, typename T>
 131     static inline key_indexed_position lower(const KA& ka, const T& n) {
 132         return key_lower_bound_by(ka, n, key_comparator<KA, T>());
 133     }
 134     template <typename KA, typename T, typename F>
 135     static inline key_indexed_position lower_by(const KA& ka, const T& n, F comparator) {
 136         return key_lower_bound_by(ka, n, comparator);
 137     }
 138 };
 139
 140 struct key_bound_linear {
 141     static constexpr bool is_binary = false;
 142     template <typename KA, typename T>
 143     static inline int upper(const KA& ka, const T& n) {
 144         return key_find_upper_bound_by(ka, n, key_comparator<KA, T>());
 145     }
 146     template <typename KA, typename T>
 147     static inline key_indexed_position lower(const KA& ka, const T& n) {
 148         return key_find_lower_bound_by(ka, n, key_comparator<KA, T>());
 149     }
 150     template <typename KA, typename T, typename F>
 151     static inline key_indexed_position lower_by(const KA& ka, const T& n, F comparator) {
 152         return key_find_lower_bound_by(ka, n, comparator);
 153     }
 154 };
 155
 156
 157 enum {
 158     bound_method_fast = 0,
 159     bound_method_binary,
 160     bound_method_linear
 161 };
 162 template <int max_size, int method = bound_method_fast> struct key_bound {};
 163 template <int max_size> struct key_bound<max_size, bound_method_binary> {
 164     typedef key_bound_binary type;
 165 };
 166 template <int max_size> struct key_bound<max_size, bound_method_linear> {
 167     typedef key_bound_linear type;
 168 };
 169 template <int max_size> struct key_bound<max_size, bound_method_fast> {
 170     typedef typename key_bound<max_size, (max_size > 16 ? bound_method_binary : bound_method_linear)>::type type;
 171 };
 172
 173 #endif