20 #ifndef _TPIE_BTREE_BTREE_BUILDER_H_
21 #define _TPIE_BTREE_BTREE_BUILDER_H_
24 #include <tpie/btree/base.h>
25 #include <tpie/btree/node.h>
35 template <
typename T,
bool b>
36 struct block_size_getter {
37 static constexpr
size_t v() {
return 0;}
42 static constexpr
size_t v() {
return T::block_size();}
45 template <
typename T,
typename O>
51 typedef typename state_type::key_type key_type;
53 static const bool is_internal = state_type::is_internal;
55 static const bool is_static = state_type::is_static;
57 static const bool is_serialized = state_type::is_serialized;
59 static_assert(!is_serialized || is_static,
"The builder currently only supports static serialized trees");
63 typedef typename O::C comp_type;
65 typedef typename O::A augmenter_type;
67 typedef typename tree_type::augment_type augment_type;
71 typedef typename state_type::combined_augment combined_augment;
73 typedef typename state_type::store_type store_type;
75 typedef typename state_type::store_type S;
77 typedef typename S::leaf_type leaf_type;
79 typedef typename S::internal_type internal_type;
86 combined_augment augment;
90 struct internal_summary {
91 internal_type
internal;
92 combined_augment augment;
96 void construct_leaf(
size_t size) {
97 tp_assert(size != 0,
"we should not construct an empty leaf");
98 tp_assert(size <= m_items.size(),
"we should not construct a leaf with more items then we have");
99 tp_assert(size <= S::max_leaf_size(),
"we should not construct a leaf with more items then the max leaf size");
101 leaf.leaf = m_state.store().create_leaf();
103 m_state.store().set_count(leaf.leaf, size);
105 for(
size_t i = 0; i < size; ++i) {
106 m_state.store().set(leaf.leaf, i, m_items.front());
110 leaf.augment = m_state.m_augmenter(node_type(&m_state, leaf.leaf));
111 m_state.store().flush();
112 m_leaves.push_back(leaf);
115 tp_assert(m_items.empty(),
"we should only construct complete leafs when serializing");
116 m_serialized_size = 0;
120 void construct_internal_from_leaves(
size_t size) {
121 internal_summary
internal;
122 internal.internal = m_state.store().create_internal();
124 m_state.store().set_count(
internal.
internal, size);
126 for(
size_t i = 0; i < size; ++i) {
127 leaf_summary child = m_leaves.front();
128 m_state.store().set(
internal.
internal, i, child.leaf);
129 m_state.store().set_augment(child.leaf,
internal.internal, child.augment);
130 m_leaves.pop_front();
133 internal.augment = m_state.m_augmenter(node_type(&m_state,
internal.
internal));
134 m_state.store().flush();
137 if(m_internal_nodes.size() < 1) m_internal_nodes.push_back(std::deque<internal_summary>());
138 m_internal_nodes[0].push_back(
internal);
141 void construct_internal_from_internal(
size_t size,
size_t level) {
143 internal_summary
internal;
144 internal.internal = m_state.store().create_internal();
145 m_state.store().set_count(
internal.
internal, size);
146 for(
size_t i = 0; i < size; ++i) {
147 internal_summary child = m_internal_nodes[level].front();
148 m_state.store().set(
internal.
internal, i, child.internal);
149 m_state.store().set_augment(child.internal,
internal.internal, child.augment);
150 m_internal_nodes[level].pop_front();
152 internal.augment = m_state.m_augmenter(node_type(&m_state,
internal.
internal));
153 m_state.store().flush();
156 if(m_internal_nodes.size() < level+2) m_internal_nodes.push_back(std::deque<internal_summary>());
157 m_internal_nodes[level+1].push_back(
internal);
163 static constexpr
size_t desired_leaf_size() noexcept {
166 : ((S::min_leaf_size() + S::max_leaf_size()) / 2);
172 static constexpr
size_t leaf_tipping_point() noexcept {
173 return desired_leaf_size() + S::min_leaf_size();
179 static constexpr
size_t desired_internal_size() noexcept {
181 ? S::max_internal_size()
182 : ((S::min_internal_size() + S::max_internal_size()) / 2);
188 static constexpr
size_t internal_tipping_point() noexcept {
189 return desired_internal_size() + S::min_internal_size();
195 void extract_nodes() {
196 construct_leaf(is_serialized?m_items.size() : desired_leaf_size());
198 if(m_leaves.size() < internal_tipping_point())
return;
199 construct_internal_from_leaves(desired_internal_size());
202 for(
size_t i = 0; i < m_internal_nodes.size(); ++i) {
204 if(m_internal_nodes[i].size() < internal_tipping_point())
return;
206 construct_internal_from_internal(desired_internal_size(), i);
213 template <
typename X=enab>
214 explicit builder(std::string path, comp_type comp=comp_type(), augmenter_type augmenter=augmenter_type(), enable<X, !is_internal> =
enab() )
215 : m_state(store_type(path, true), std::move(augmenter), typename
state_type::keyextract_type())
217 , m_serialized_size(0)
221 template <
typename X=enab>
222 explicit builder(comp_type comp=comp_type(), augmenter_type augmenter=augmenter_type(),
224 : m_state(store_type(bucket), std::move(augmenter), typename state_type::keyextract_type())
226 , m_serialized_size(0)
239 if (m_items.size() == S::max_leaf_size() ||
242 m_items.push_back(v);
243 m_serialized_size += s;
245 m_items.push_back(v);
248 if(m_items.size() < leaf_tipping_point())
return;
257 m_state.store().set_size(m_size);
261 if(m_items.size() > 0) {
262 if(!is_serialized && m_items.size() > S::max_leaf_size())
263 construct_leaf(m_items.size()/2);
264 construct_leaf(m_items.size());
269 if((m_internal_nodes.size() == 0 && m_leaves.size() > 1) || (m_internal_nodes.size() > 0 && m_leaves.size() > 0)) {
270 if(m_leaves.size() > 2*S::max_internal_size() )
271 construct_internal_from_leaves(m_leaves.size()/3);
272 if(m_leaves.size() > S::max_internal_size())
273 construct_internal_from_leaves(m_leaves.size()/2);
274 construct_internal_from_leaves(m_leaves.size());
277 for(
size_t i = 0; i < m_internal_nodes.size(); ++i) {
280 if((m_internal_nodes.size() == i+1 && m_internal_nodes[i].size() > 1)
281 || (m_internal_nodes.size() > i+1 && m_internal_nodes[i].size() > 0)) {
282 if(m_internal_nodes[i].size() > 2*S::max_internal_size())
283 construct_internal_from_internal(m_internal_nodes[i].size()/3, i);
284 if(m_internal_nodes[i].size() > S::max_internal_size())
285 construct_internal_from_internal(m_internal_nodes[i].size()/2, i);
286 construct_internal_from_internal(m_internal_nodes[i].size(), i);
292 if(m_internal_nodes.size() == 0 && m_leaves.size() == 0)
293 m_state.store().set_height(0);
295 m_state.store().set_height(m_internal_nodes.size() + 1);
296 if(m_leaves.size() == 1)
297 m_state.store().set_root(m_leaves.front().leaf);
299 m_state.store().set_root(m_internal_nodes.back().front().internal);
301 if (metadata.size()) {
302 m_state.store().flush();
303 m_state.store().set_metadata(metadata);
305 m_state.store().finalize_build();
306 return tree_type(std::move(m_state), std::move(m_comp));
310 std::deque<value_type> m_items;
311 std::deque<leaf_summary> m_leaves;
312 std::vector<std::deque<internal_summary>> m_internal_nodes;
316 size_t m_serialized_size;
317 stream_size_type m_size;
322 template <
typename T,
typename ... Opts>
323 using btree_builder = bbits::builder<T,
typename bbits::OptComp<Opts...>::type>;
size_t serialized_size(const T &v)
Given a serializable, serialize it and measure its serialized size.
Memory management subsystem.
This file contains a few deprecated definitions for legacy code.
void push(value_type v)
Push a value to the builder.
Class storring a reference to a memory bucket.
builder(std::string path, comp_type comp=comp_type(), augmenter_type augmenter=augmenter_type(), enable< X,!is_internal >=enab())
Construct a btree builder with the given storage.
tree_type build(const std::string &metadata=std::string())
Constructs and returns a btree from the value that was pushed to the builder.
Type that is useful for navigating a btree.
#define tp_assert(condition, message)
store_type::size_type size_type
Type of the size.