20 #ifndef _TPIE_BTREE_TREE_H_
21 #define _TPIE_BTREE_TREE_H_
24 #include <tpie/btree/base.h>
25 #include <tpie/btree/node.h>
37 template <
typename T,
typename O>
40 typedef tree_state<T, O> state_type;
42 static const bool is_internal = state_type::is_internal;
43 static const bool is_static = state_type::is_static;
44 static const bool is_ordered = state_type::is_ordered;
46 typedef typename state_type::augmenter_type augmenter_type;
52 typedef typename state_type::keyextract_type keyextract_type;
54 typedef typename state_type::augment_type augment_type;
60 typedef typename state_type::key_type
key_type;
62 typedef typename O::C comp_type;
64 typedef typename state_type::store_type store_type;
82 typedef typename store_type::leaf_type leaf_type;
83 typedef typename store_type::internal_type internal_type;
86 size_t count_child(internal_type node,
size_t i, leaf_type)
const {
87 return m_state.store().count_child_leaf(node, i);
90 size_t count_child(internal_type node,
size_t i, internal_type)
const {
91 return m_state.store().count_child_internal(node, i);
94 internal_type get_child(internal_type node,
size_t i, internal_type)
const {
95 return m_state.store().get_child_internal(node, i);
98 leaf_type get_child(internal_type node,
size_t i, leaf_type)
const {
99 return m_state.store().get_child_leaf(node, i);
102 template <
bool upper_bound = false,
typename K>
103 leaf_type find_leaf(std::vector<internal_type> & path, K k)
const {
105 if (m_state.store().height() == 1)
return m_state.store().get_root_leaf();
106 internal_type n = m_state.store().get_root_internal();
107 for (
size_t i=2;; ++i) {
109 for (
size_t j=0; ; ++j) {
110 if (j+1 == m_state.store().count(n) ||
112 ? m_comp(k, m_state.min_key(n, j+1))
113 : !m_comp(m_state.min_key(n, j+1), k))) {
114 if (i == m_state.store().height())
return m_state.store().get_child_leaf(n, j);
115 n = m_state.store().get_child_internal(n, j);
122 void augment(leaf_type l, internal_type p) {
123 m_state.store().set_augment(l, p, m_state.m_augmenter(
node_type(&m_state, l)));
130 void augment(internal_type l, internal_type p) {
131 m_state.store().set_augment(l, p, m_state.m_augmenter(
node_type(&m_state, l)));
134 size_t max_size(internal_type)
const throw() {
135 return m_state.store().max_internal_size();
138 size_t max_size(leaf_type)
const throw() {
139 return m_state.store().max_leaf_size();
142 size_t min_size(internal_type)
const throw() {
143 return m_state.store().min_internal_size();
146 size_t min_size(leaf_type)
const throw() {
147 return m_state.store().min_leaf_size();
150 template <
typename N>
152 tp_assert(m_state.store().count(left) == max_size(left),
"Node not full");
153 size_t left_size = max_size(left)/2;
154 size_t right_size = max_size(left)-left_size;
155 N right = m_state.store().create(left);
156 for (
size_t i=0; i < right_size; ++i)
157 m_state.store().move(left, left_size+i, right, i);
158 m_state.store().set_count(left, left_size);
159 m_state.store().set_count(right, right_size);
163 template <
typename NT,
typename VT>
164 void insert_part(NT n, VT v) {
165 size_t z = m_state.store().count(n);
167 for (;i > 0 && m_comp(m_state.min_key(v), m_state.min_key(n, i-1)); --i)
168 m_state.store().move(n, i-1, n, i);
169 m_state.store().set(n, i, v);
170 m_state.store().set_count(n, z+1);
174 template <
typename CT,
typename NT>
175 NT split_and_insert(CT c, NT p) {
176 tp_assert(m_state.store().count(p) == max_size(p),
"Node not full");
178 if (m_comp(m_state.min_key(c), m_state.min_key(p2)))
185 void augment_path(leaf_type) {
189 void augment_path(std::vector<internal_type> & path) {
190 while (path.size() >= 2) {
191 internal_type c=path.back();
193 augment(c, path.back());
198 template <
typename CT,
typename PT>
199 bool remove_fixup_round(CT c, PT p) {
200 size_t z=m_state.store().count(c);
201 size_t i=m_state.store().index(c, p);
202 if (i != 0 && count_child(p, i-1, c) > min_size(c)) {
204 CT left = get_child(p, i-1, c);
205 size_t left_size = m_state.store().count(left);
206 for (
size_t j=0; j < z; ++j)
207 m_state.store().move(c, z-j-1, c, z-j);
208 m_state.store().move(left, left_size-1, c, 0);
209 m_state.store().set_count(left, left_size-1);
210 m_state.store().set_count(c, z+1);
217 if (i +1 != m_state.store().count(p) &&
218 count_child(p, i+1, c) > min_size(c)) {
220 CT right = get_child(p, i+1, c);
221 size_t right_size = m_state.store().count(right);
222 m_state.store().move(right, 0, c, z);
223 for (
size_t i=0; i+1 < right_size ; ++i)
224 m_state.store().move(right, i+1, right, i);
225 m_state.store().set_count(right, right_size-1);
226 m_state.store().set_count(c, z+1);
236 c2 = get_child(p, i+1, c);
238 c1 = get_child(p, i-1, c);
243 size_t z1 = m_state.store().count(c1);
244 size_t z2 = m_state.store().count(c2);
245 for (
size_t i=0; i < z2; ++i)
246 m_state.store().move(c2, i, c1, i+z1);
247 m_state.store().set_count(c1, z1+z2);
248 m_state.store().set_count(c2, 0);
251 size_t id = m_state.store().index(c2, p);
252 size_t z_ = m_state.store().count(p) -1;
253 for (;
id != z_; ++id)
254 m_state.store().move(p,
id+1, p,
id);
255 m_state.store().set_count(p, z_);
256 m_state.store().destroy(c2);
259 return z_ >= min_size(p);
284 template <
typename X=enab>
286 m_state.store().set_size(m_state.store().size() + 1);
289 if (m_state.store().height() == 0) {
290 leaf_type n = m_state.store().create_leaf();
291 m_state.store().set_count(n, 1);
292 m_state.store().set(n, 0, v);
293 m_state.store().set_height(1);
294 m_state.store().set_root(n);
299 std::vector<internal_type> path;
302 leaf_type l = find_leaf(path, m_state.min_key(v));
304 if (m_state.store().count(l) != m_state.store().max_leaf_size()) {
306 if (!path.empty()) augment(l, path.back());
312 leaf_type l2 = split_and_insert(v, l);
316 internal_type i=m_state.store().create_internal();
317 m_state.store().set_count(i, 2);
318 m_state.store().set(i, 0, l);
319 m_state.store().set(i, 1, l2);
320 m_state.store().set_root(i);
321 m_state.store().set_height(m_state.store().height()+1);
329 internal_type p = path.back();
333 if (m_state.store().count(p) != m_state.store().max_internal_size()) {
340 internal_type n2 = split_and_insert(l2, p);
341 internal_type n1 = p;
343 while (!path.empty()) {
344 internal_type p = path.back();
346 if (m_state.store().count(p) != m_state.store().max_internal_size()) {
352 n2 = split_and_insert(n2, p);
358 internal_type i=m_state.store().create_internal();
359 m_state.store().set_count(i, 2);
360 m_state.store().set(i, 0, n1);
361 m_state.store().set(i, 1, n2);
362 m_state.store().set_root(i);
363 m_state.store().set_height(m_state.store().height()+1);
373 template <
typename K,
typename X=enab>
377 if(m_state.store().height() == 0) {
382 std::vector<internal_type> path;
383 leaf_type l = find_leaf<true>(path, v);
386 size_t z = m_state.store().count(l);
392 if (!m_comp(m_state.min_key(l, i), v) &&
393 !m_comp(v, m_state.min_key(l, i)))
break;
396 itr.goto_item(path, l, i);
404 template <
typename K,
typename X=enab>
407 if (m_state.store().height() == 0) {
412 std::vector<internal_type> path;
413 leaf_type l = find_leaf(path, v);
415 const size_t z = m_state.store().count(l);
416 for (
size_t i = 0 ; i < z ; ++i) {
417 if (!m_comp(m_state.min_key(l, i), v)) {
418 itr.goto_item(path, l, i);
422 itr.goto_item(path, l, z-1);
430 template <
typename K,
typename X=enab>
433 if (m_state.store().height() == 0) {
438 std::vector<internal_type> path;
439 leaf_type l = find_leaf<true>(path, v);
441 const size_t z = m_state.store().count(l);
442 for (
size_t i = 0 ; i < z ; ++i) {
443 if (m_comp(v, m_state.min_key(l, i))) {
444 itr.goto_item(path, l, i);
448 itr.goto_item(path, l, z-1);
455 template <
typename X=enab>
457 std::vector<internal_type> path=itr.m_path;
458 leaf_type l = itr.m_leaf;
460 size_t z = m_state.store().count(l);
461 size_t i = itr.m_index;
463 m_state.store().set_size(m_state.store().size()-1);
466 m_state.store().move(l, i+1, l, i);
467 m_state.store().set_count(l, z);
470 if (z >= m_state.store().min_leaf_size()) {
476 augment(l, path.back());
485 m_state.store().destroy(l);
486 m_state.store().set_height(0);
494 if (remove_fixup_round(l, path.back())) {
500 if (path.size() == 1) {
501 if (m_state.store().count(path.back()) == 1) {
502 l = m_state.store().get_child_leaf(path.back(), 0);
503 m_state.store().set_count(path.back(), 0);
504 m_state.store().destroy(path.back());
505 m_state.store().set_height(1);
506 m_state.store().set_root(l);
516 internal_type p = path.back();
518 if (remove_fixup_round(p, path.back())) {
523 if (path.size() == 1) {
524 if (m_state.store().count(path.back()) == 1) {
525 p = m_state.store().get_child_internal(path.back(), 0);
526 m_state.store().set_count(path.back(), 0);
527 m_state.store().destroy(path.back());
528 m_state.store().set_height(m_state.store().height()-1);
529 m_state.store().set_root(p);
544 template <
typename X=enab>
562 if (m_state.store().height() == 1)
return node_type(&m_state, m_state.store().get_root_leaf());
563 return node_type(&m_state, m_state.store().get_root_internal());
570 return m_state.store().size();
577 return m_state.store().size() == 0;
580 void set_metadata(
const std::string & data) {
581 m_state.store().set_metadata(data);
584 std::string get_metadata() {
585 return m_state.store().get_metadata();
591 template <
typename X=enab>
592 explicit tree(std::string path, comp_type comp=comp_type(), augmenter_type augmenter=augmenter_type(), enable<X, !is_internal> =
enab() ):
593 m_state(store_type(path), std::move(augmenter), keyextract_type()),
599 template <
typename X=enab>
600 explicit tree(comp_type comp=comp_type(),
601 augmenter_type augmenter=augmenter_type(),
603 enable<X, is_internal> =
enab() ):
604 m_state(store_type(bucket), std::move(augmenter), keyextract_type()),
609 const comp_type & comp()
const {
614 explicit tree(state_type state, comp_type comp):
615 m_state(std::move(state)),
624 template <
typename T,
typename ... Opts>
625 using btree = bbits::tree<T,
typename bbits::OptComp<Opts...>::type>;
tree(std::string path, comp_type comp=comp_type(), augmenter_type augmenter=augmenter_type(), enable< X,!is_internal >=enab())
Construct a btree with the given storage.
btree_node< state_type > node_type
Type of node wrapper.
Memory management subsystem.
iterator upper_bound(K v, enable< X, is_ordered >=enab()) const
Return an interator to the first element that is "greater" than the given key.
void insert(value_type v, enable< X,!is_static >=enab())
Insert given value into the btree.
state_type::key_type key_type
The type of key used.
iterator find(K v, enable< X, is_ordered >=enab()) const
Return an iterator to the first item with the given key.
This file contains a few deprecated definitions for legacy code.
size_type erase(key_type v, enable< X,!is_static &&is_ordered >=enab())
remove all items with given key
Class storring a reference to a memory bucket.
size_type size() const
Return the number of elements in the tree.
iterator begin() const
Returns an iterator pointing to the beginning of the tree.
void erase(const iterator &itr, enable< X,!is_static >=enab())
remove item at iterator
iterator lower_bound(K v, enable< X, is_ordered >=enab()) const
Return an interator to the first element that is "not less" than the given key.
Type that is useful for navigating a btree.
#define tp_assert(condition, message)
bool empty() const
Check if the tree is empty.
store_type::size_type size_type
Type of the size.
tree(comp_type comp=comp_type(), augmenter_type augmenter=augmenter_type(), memory_bucket_ref bucket=memory_bucket_ref(), enable< X, is_internal >=enab())
Construct a btree with the given storage.
state_type::value_type value_type
Type of value stored.
node_type root() const
Return the root node.
btree_iterator< state_type > iterator
Iterator type.
iterator end() const
Returns an iterator pointing to the end of the tree.