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
|