| 1 | /*
|
| 2 | * Souffle - A Datalog Compiler
|
| 3 | * Copyright (c) 2013, 2015, Oracle and/or its affiliates. All rights reserved
|
| 4 | * Licensed under the Universal Permissive License v 1.0 as shown at:
|
| 5 | * - https://opensource.org/licenses/UPL
|
| 6 | * - <souffle root>/licenses/SOUFFLE-UPL.txt
|
| 7 | */
|
| 8 |
|
| 9 | /************************************************************************
|
| 10 | *
|
| 11 | * @file BTreeUtil.h
|
| 12 | *
|
| 13 | * Utilities for a generic B-tree data structure
|
| 14 | *
|
| 15 | ***********************************************************************/
|
| 16 |
|
| 17 | #pragma once
|
| 18 |
|
| 19 | #include <tuple>
|
| 20 |
|
| 21 | namespace souffle {
|
| 22 |
|
| 23 | namespace detail {
|
| 24 |
|
| 25 | // ---------- comparators --------------
|
| 26 |
|
| 27 | /**
|
| 28 | * A generic comparator implementation as it is used by
|
| 29 | * a b-tree based on types that can be less-than and
|
| 30 | * equality comparable.
|
| 31 | */
|
| 32 | template <typename T>
|
| 33 | struct comparator {
|
| 34 | /**
|
| 35 | * Compares the values of a and b and returns
|
| 36 | * -1 if a<b, 1 if a>b and 0 otherwise
|
| 37 | */
|
| 38 | int operator()(const T& a, const T& b) const {
|
| 39 | return (a > b) - (a < b);
|
| 40 | }
|
| 41 | bool less(const T& a, const T& b) const {
|
| 42 | return a < b;
|
| 43 | }
|
| 44 | bool equal(const T& a, const T& b) const {
|
| 45 | return a == b;
|
| 46 | }
|
| 47 | };
|
| 48 |
|
| 49 | // ---------- search strategies --------------
|
| 50 |
|
| 51 | /**
|
| 52 | * A common base class for search strategies in b-trees.
|
| 53 | */
|
| 54 | struct search_strategy {};
|
| 55 |
|
| 56 | /**
|
| 57 | * A linear search strategy for looking up keys in b-tree nodes.
|
| 58 | */
|
| 59 | struct linear_search : public search_strategy {
|
| 60 | /**
|
| 61 | * Required user-defined default constructor.
|
| 62 | */
|
| 63 | linear_search() = default;
|
| 64 |
|
| 65 | /**
|
| 66 | * Obtains an iterator referencing an element equivalent to the
|
| 67 | * given key in the given range. If no such element is present,
|
| 68 | * a reference to the first element not less than the given key
|
| 69 | * is returned.
|
| 70 | */
|
| 71 | template <typename Key, typename Iter, typename Comp>
|
| 72 | inline Iter operator()(const Key& k, Iter a, Iter b, Comp& comp) const {
|
| 73 | return lower_bound(k, a, b, comp);
|
| 74 | }
|
| 75 |
|
| 76 | /**
|
| 77 | * Obtains a reference to the first element in the given range that
|
| 78 | * is not less than the given key.
|
| 79 | */
|
| 80 | template <typename Key, typename Iter, typename Comp>
|
| 81 | inline Iter lower_bound(const Key& k, Iter a, Iter b, Comp& comp) const {
|
| 82 | auto c = a;
|
| 83 | while (c < b) {
|
| 84 | auto r = comp(*c, k);
|
| 85 | if (r >= 0) {
|
| 86 | return c;
|
| 87 | }
|
| 88 | ++c;
|
| 89 | }
|
| 90 | return b;
|
| 91 | }
|
| 92 |
|
| 93 | /**
|
| 94 | * Obtains a reference to the first element in the given range that
|
| 95 | * such that the given key is less than the referenced element.
|
| 96 | */
|
| 97 | template <typename Key, typename Iter, typename Comp>
|
| 98 | inline Iter upper_bound(const Key& k, Iter a, Iter b, Comp& comp) const {
|
| 99 | auto c = a;
|
| 100 | while (c < b) {
|
| 101 | if (comp(*c, k) > 0) {
|
| 102 | return c;
|
| 103 | }
|
| 104 | ++c;
|
| 105 | }
|
| 106 | return b;
|
| 107 | }
|
| 108 | };
|
| 109 |
|
| 110 | /**
|
| 111 | * A binary search strategy for looking up keys in b-tree nodes.
|
| 112 | */
|
| 113 | struct binary_search : public search_strategy {
|
| 114 | /**
|
| 115 | * Required user-defined default constructor.
|
| 116 | */
|
| 117 | binary_search() = default;
|
| 118 |
|
| 119 | /**
|
| 120 | * Obtains an iterator pointing to some element within the given
|
| 121 | * range that is equal to the given key, if available. If multiple
|
| 122 | * elements are equal to the given key, an undefined instance will
|
| 123 | * be obtained (no guaranteed lower or upper boundary). If no such
|
| 124 | * element is present, a reference to the first element not less than
|
| 125 | * the given key will be returned.
|
| 126 | */
|
| 127 | template <typename Key, typename Iter, typename Comp>
|
| 128 | Iter operator()(const Key& k, Iter a, Iter b, Comp& comp) const {
|
| 129 | Iter c;
|
| 130 | auto count = b - a;
|
| 131 | while (count > 0) {
|
| 132 | auto step = count >> 1;
|
| 133 | c = a + step;
|
| 134 | auto r = comp(*c, k);
|
| 135 | if (r == 0) {
|
| 136 | return c;
|
| 137 | }
|
| 138 | if (r < 0) {
|
| 139 | a = ++c;
|
| 140 | count -= step + 1;
|
| 141 | } else {
|
| 142 | count = step;
|
| 143 | }
|
| 144 | }
|
| 145 | return a;
|
| 146 | }
|
| 147 |
|
| 148 | /**
|
| 149 | * Obtains a reference to the first element in the given range that
|
| 150 | * is not less than the given key.
|
| 151 | */
|
| 152 | template <typename Key, typename Iter, typename Comp>
|
| 153 | Iter lower_bound(const Key& k, Iter a, Iter b, Comp& comp) const {
|
| 154 | Iter c;
|
| 155 | auto count = b - a;
|
| 156 | while (count > 0) {
|
| 157 | auto step = count >> 1;
|
| 158 | c = a + step;
|
| 159 | if (comp(*c, k) < 0) {
|
| 160 | a = ++c;
|
| 161 | count -= step + 1;
|
| 162 | } else {
|
| 163 | count = step;
|
| 164 | }
|
| 165 | }
|
| 166 | return a;
|
| 167 | }
|
| 168 |
|
| 169 | /**
|
| 170 | * Obtains a reference to the first element in the given range that
|
| 171 | * such that the given key is less than the referenced element.
|
| 172 | */
|
| 173 | template <typename Key, typename Iter, typename Comp>
|
| 174 | Iter upper_bound(const Key& k, Iter a, Iter b, Comp& comp) const {
|
| 175 | Iter c;
|
| 176 | auto count = b - a;
|
| 177 | while (count > 0) {
|
| 178 | auto step = count >> 1;
|
| 179 | c = a + step;
|
| 180 | if (comp(k, *c) >= 0) {
|
| 181 | a = ++c;
|
| 182 | count -= step + 1;
|
| 183 | } else {
|
| 184 | count = step;
|
| 185 | }
|
| 186 | }
|
| 187 | return a;
|
| 188 | }
|
| 189 | };
|
| 190 |
|
| 191 | // ---------- search strategies selection --------------
|
| 192 |
|
| 193 | /**
|
| 194 | * A template-meta class to select search strategies for b-trees
|
| 195 | * depending on the key type.
|
| 196 | */
|
| 197 | template <typename S>
|
| 198 | struct strategy_selection {
|
| 199 | using type = S;
|
| 200 | };
|
| 201 |
|
| 202 | struct linear : public strategy_selection<linear_search> {};
|
| 203 | struct binary : public strategy_selection<binary_search> {};
|
| 204 |
|
| 205 | // by default every key utilizes binary search
|
| 206 | template <typename Key>
|
| 207 | struct default_strategy : public binary {};
|
| 208 |
|
| 209 | template <>
|
| 210 | struct default_strategy<int> : public linear {};
|
| 211 |
|
| 212 | template <typename... Ts>
|
| 213 | struct default_strategy<std::tuple<Ts...>> : public linear {};
|
| 214 |
|
| 215 | /**
|
| 216 | * The default non-updater
|
| 217 | */
|
| 218 | template <typename T>
|
| 219 | struct updater {
|
| 220 | bool update(T& /* old_t */, const T& /* new_t */) {
|
| 221 | return false;
|
| 222 | }
|
| 223 | };
|
| 224 |
|
| 225 | } // end of namespace detail
|
| 226 | } // end of namespace souffle
|