20 #ifndef _TPIE_BTREE_BASE_H_
21 #define _TPIE_BTREE_BASE_H_
47 const T & operator()(
const T & t)
const noexcept {
return t;}
54 template <
typename L,
typename R>
55 bool operator()(
const L & l,
const R & r)
const noexcept {
71 static const int f_internal = 1;
72 static const int f_static = 2;
73 static const int f_unordered = 4;
74 static const int f_serialized = 8;
87 template <
int a_,
int b_>
89 static const int a = a_;
90 static const int b = b_;
95 static const size_t bs = bs_;
113 template <
int O_,
int a_,
int b_,
size_t bs_,
typename C_,
typename K_,
typename A_>
115 static const int O=O_;
116 static const int a=a_;
117 static const int b=b_;
118 static const size_t bs=bs_;
124 template <
typename ...
Opt>
132 template <
int i,
typename ... T>
138 template <
typename C,
typename ... T>
144 template <
typename K,
typename ... T>
150 template <
typename A,
typename ... T>
156 template <
int a,
int b,
typename ... T>
162 template <
size_t bs,
typename ... T>
177 template <
typename S>
181 template <
typename S>
193 template <
typename T,
204 template <
typename T,
typename O>
207 template <
typename,
bool>
210 template <
typename T,
typename A, std::
size_t a, std::
size_t b>
213 template <
typename T,
typename A, std::
size_t a, std::
size_t b, std::
size_t bs>
216 template <
typename T,
typename A, std::
size_t a, std::
size_t b, std::
size_t bs>
221 template <
typename X,
bool b>
227 template <
typename X,
bool b>
230 template <
typename T,
typename O>
233 static const bool is_internal = O::O & bbits::f_internal;
234 static const bool is_static = O::O & bbits::f_static;
235 static const bool is_ordered = ! (O::O & bbits::f_unordered);
236 static const bool is_serialized = O::O & bbits::f_serialized;
237 static_assert(!is_serialized || is_static,
"Serialized B-tree cannot be dynamic.");
239 typedef typename std::conditional<
242 no_key>::type keyextract_type;
244 typedef typename O::A augmenter_type;
246 typedef T value_type;
248 typedef typename std::decay<decltype(std::declval<augmenter_type>()(std::declval<value_type>()))>::type augment_type;
250 typedef typename std::decay<decltype(std::declval<keyextract_type>()(std::declval<value_type>()))>::type key_type;
258 ,
public augment_type {};
262 template <
typename N>
265 *
static_cast<augment_type*
>(&ans) = m_augmenter(node);
269 ? m_key_extract(node.value(0))
270 : static_cast<const key_augment*>(&node.get_combined_augmentation(0))->key;
276 keyextract_type key_extract)
277 : m_key_extract(std::move(key_extract))
278 , m_augmenter(std::move(a)) {}
280 keyextract_type m_key_extract;
281 augmenter_type m_augmenter;
284 typedef typename std::conditional<
287 typename std::conditional<
294 typedef typename store_type::internal_type internal_type;
295 typedef typename store_type::leaf_type leaf_type;
297 key_type min_key(internal_type node,
size_t i)
const {
298 return static_cast<const key_augment*
>(&m_store.augment(node, i))->key;
301 key_type min_key(leaf_type node,
size_t i)
const {
302 return m_augmenter.m_key_extract(m_store.get(node, i));
305 key_type min_key(T v)
const {
306 return m_augmenter.m_key_extract(v);
309 key_type min_key(internal_type v)
const {
310 return min_key(v, 0);
313 key_type min_key(leaf_type v)
const {
314 return min_key(v, 0);
317 const store_type & store()
const {
321 store_type & store() {
325 static const augment_type & user_augment(
const combined_augment & a) {
326 return *
static_cast<const augment_type *
>(&a);
329 tree_state(store_type store, augmenter_type augmenter, keyextract_type keyextract)
330 : m_augmenter(std::move(augmenter), std::move(keyextract))
331 , m_store(std::move(store)) {}
333 combined_augmenter m_augmenter;
Default < comparator for the btree.
Augmentation struct used in an un-augmented btree.
Storage used for an internal btree.
This file contains a few deprecated definitions for legacy code.
Functor used to extract the key from a value in case keys and values are the same.
Storage used for an external btree.
Type that is useful for navigating a btree.
Functor used to augment an un-augmented btree.