tpie::bbits::builder< T, O > Class Template Reference

Augmented btree builder. More...

#include <tpie/btree/base.h>

Public Member Functions
template<typename X = enab>
	builder (std::string path, comp_type comp=comp_type(), augmenter_type augmenter=augmenter_type(), btree_flags flags=btree_flags::defaults, enable< X, !is_internal >=enab())
	Construct a btree builder with the given storage. More...
template<typename X = enab>
	builder (comp_type comp=comp_type(), augmenter_type augmenter=augmenter_type(), memory_bucket_ref bucket=memory_bucket_ref(), enable< X, is_internal >=enab())
void	push (value_type v)
	Push a value to the builder. More...
tree_type	build (const std::string &metadata=std::string())
	Constructs and returns a btree from the value that was pushed to the builder. More...

Detailed Description

template<typename T, typename O>
class tpie::bbits::builder< T, O >

Augmented btree builder.

The fanout and location of nodes is decided by the store type S C is the item comparator type A is the type of the augmentation computation fuctor

Definition at line 248 of file base.h.

Constructor & Destructor Documentation

builder()

template<typename T , typename O >

template<typename X = enab>

tpie::bbits::builder< T, O >::builder ( std::string  path, comp_type  comp = comp_type(), augmenter_type  augmenter = augmenter_type(), btree_flags  flags = btree_flags::defaults, enable< X, !is_internal >  = enab()  )

inlineexplicit

Construct a btree builder with the given storage.

Definition at line 214 of file btree_builder.h.

        : m_state(store_type(path, (flags | btree_flags::write) & ~btree_flags::read ), std::move(augmenter), typename state_type::keyextract_type())
        , m_comp(comp)
        , m_serialized_size(0)
        , m_size(0)
    {}

Member Function Documentation

build()

template<typename T , typename O >

tree_type tpie::bbits::builder< T, O >::build ( const std::string &  metadata = std::string() )

inline

Constructs and returns a btree from the value that was pushed to the builder.

The btree builder should not be used again after this point.

Definition at line 257 of file btree_builder.h.

                                                              {
        m_state.store().set_size(m_size);
 
        // finish building the tree by traversing all levels and constructing leaves/nodes
        // construct one or two leaves if neccesary
        if(m_items.size() > 0) {
            if(!is_serialized && m_items.size() > S::max_leaf_size()) // construct two leaves if necessary
                construct_leaf(m_items.size()/2);
            construct_leaf(m_items.size()); // construct a leaf with the remaining items
        }
 
        // if there already exists internal nodes and there are leaves left: construct a new internal node(since there is guaranteed to be atleast S::min_internal_size leaves)
        // if there do not exist internal nodes, then only construct an internal node if there is more than one leaf
        if((m_internal_nodes.size() == 0 && m_leaves.size() > 1) || (m_internal_nodes.size() > 0 && m_leaves.size() > 0)) {
            if(m_leaves.size() > 2*S::max_internal_size() ) // construct two nodes if necessary
                construct_internal_from_leaves(m_leaves.size()/3);
            if(m_leaves.size() > S::max_internal_size()) // construct two nodes if necessary
                construct_internal_from_leaves(m_leaves.size()/2);
            construct_internal_from_leaves(m_leaves.size()); // construct a node from the remaining leaves
        }
 
        for(size_t i = 0; i < m_internal_nodes.size(); ++i) {
            // if there already exists internal nodes at a higher level and there are nodes at this level left: construct a new internal node at the higher level.
            // if there do not exist internal nodes at a higher level, then only construct an internal nodes at that level if there are more than one node at this level.
            if((m_internal_nodes.size() == i+1 && m_internal_nodes[i].size() > 1)
                || (m_internal_nodes.size() > i+1 && m_internal_nodes[i].size() > 0)) {
                if(m_internal_nodes[i].size() > 2*S::max_internal_size())
                    construct_internal_from_internal(m_internal_nodes[i].size()/3, i);
                if(m_internal_nodes[i].size() > S::max_internal_size())
                    construct_internal_from_internal(m_internal_nodes[i].size()/2, i);
                construct_internal_from_internal(m_internal_nodes[i].size(), i);
            }
        }
 
        // find the root and set it as such
 
        if(m_internal_nodes.size() == 0 && m_leaves.size() == 0) // no items were pushed
            m_state.store().set_height(0);
        else {
            m_state.store().set_height(m_internal_nodes.size() + 1);
            if(m_leaves.size() == 1)
                m_state.store().set_root(m_leaves.front().leaf);
            else
                m_state.store().set_root(m_internal_nodes.back().front().internal);
        }
        if (metadata.size()) {
            m_state.store().flush();
            m_state.store().set_metadata(metadata);
        }
        m_state.store().finalize_build();
        return tree_type(std::move(m_state), std::move(m_comp));
    }

push()

template<typename T , typename O >

void tpie::bbits::builder< T, O >::push ( value_type  v )

inline

Push a value to the builder.

Values are expected to be received in order

Parameters

v	The value to be pushed

Definition at line 236 of file btree_builder.h.

                            {
        ++m_size;
        if (is_serialized) {
            size_t s = serialized_size(v);
            if (m_items.size() == S::max_leaf_size() ||
                (s + m_serialized_size > block_size_getter<S, is_serialized>::v() && m_serialized_size))
                extract_nodes();
            m_items.push_back(v);
            m_serialized_size += s;
        } else {
            m_items.push_back(v);
            
            // try to construct nodes from items if possible
            if(m_items.size() < leaf_tipping_point()) return;
            extract_nodes();
        }
    }

References tpie::serialized_size().

---

The documentation for this class was generated from the following files:

• btree/base.h
• btree/btree_builder.h