20 #ifndef _TPIE_BTREE_EXTERNAL_STORE_H_
21 #define _TPIE_BTREE_EXTERNAL_STORE_H_
24 #include <tpie/btree/base.h>
26 #include <tpie/blocks/block_collection_cache.h>
27 #include <tpie/btree/external_store_base.h>
47 class external_store :
public external_store_base {
59 typedef size_t size_type;
61 static constexpr memory_size_type cacheSize() {
return 32;}
62 static constexpr memory_size_type blockSize() {
return bs?bs:7000;}
71 count =
reinterpret_cast<memory_size_type *
>(b->get());
72 values =
reinterpret_cast<internal_content *
>(b->get() +
sizeof(memory_size_type));
75 memory_size_type * count;
81 count =
reinterpret_cast<memory_size_type *
>(b->
get());
82 values =
reinterpret_cast<T *
>(b->
get() +
sizeof(memory_size_type));
85 memory_size_type * count;
96 return handle == other.handle;
106 bool operator==(
const leaf_type & other)
const {
107 return handle == other.handle;
117 m_collection = std::make_shared<blocks::block_collection_cache>(
118 path, blockSize(), cacheSize(),
true);
124 m_collection.reset();
127 static constexpr
size_t min_internal_size() {
128 return fanout_a?fanout_a:(max_internal_size() + 3) / 4;
131 static constexpr
size_t max_internal_size() {
132 return fanout_b?fanout_b:(blockSize() -
sizeof(memory_size_type)) /
sizeof(internal_content);
135 static constexpr
size_t min_leaf_size() {
136 return fanout_a?fanout_a:(max_leaf_size() + 3) / 4;
139 static constexpr
size_t max_leaf_size() {
140 return fanout_b?fanout_b:(blockSize() -
sizeof(memory_size_type)) /
sizeof(T);
143 void move(internal_type src,
size_t src_i,
144 internal_type dst,
size_t dst_i) {
145 blocks::block * srcBlock = m_collection->read_block(src.handle);
146 blocks::block * dstBlock = m_collection->read_block(dst.handle);
148 internal srcInter(srcBlock);
149 internal dstInter(dstBlock);
151 dstInter.values[dst_i] = srcInter.values[src_i];
153 m_collection->write_block(src.handle);
154 m_collection->write_block(dst.handle);
157 void move(leaf_type src,
size_t src_i,
158 leaf_type dst,
size_t dst_i) {
159 blocks::block * srcBlock = m_collection->read_block(src.handle);
160 blocks::block * dstBlock = m_collection->read_block(dst.handle);
162 leaf srcInter(srcBlock);
163 leaf dstInter(dstBlock);
165 dstInter.values[dst_i] = srcInter.values[src_i];
167 m_collection->write_block(src.handle);
168 m_collection->write_block(dst.handle);
171 void set(leaf_type dst,
size_t dst_i, T c) {
172 blocks::block * dstBlock = m_collection->read_block(dst.handle);
173 leaf dstInter(dstBlock);
175 dstInter.values[dst_i] = c;
177 m_collection->write_block(dst.handle);
180 void set(internal_type node,
size_t i, internal_type c) {
181 blocks::block * nodeBlock = m_collection->read_block(node.handle);
182 internal nodeInter(nodeBlock);
184 nodeInter.values[i].handle = c.handle;
186 m_collection->write_block(node.handle);
189 void set(internal_type node,
size_t i, leaf_type c) {
190 blocks::block * nodeBlock = m_collection->read_block(node.handle);
191 internal nodeInter(nodeBlock);
193 nodeInter.values[i].handle = c.handle;
195 m_collection->write_block(node.handle);
198 const T &
get(leaf_type node,
size_t i)
const {
199 blocks::block * nodeBlock = m_collection->read_block(node.handle);
200 leaf nodeInter(nodeBlock);
202 return nodeInter.values[i];
205 size_t count(internal_type node)
const {
206 blocks::block * nodeBlock = m_collection->read_block(node.handle);
207 internal nodeInter(nodeBlock);
209 return *(nodeInter.count);
212 size_t count(leaf_type node)
const {
213 blocks::block * nodeBlock = m_collection->read_block(node.handle);
214 leaf nodeInter(nodeBlock);
216 return *(nodeInter.count);
219 size_t count_child_leaf(internal_type node,
size_t i)
const {
220 blocks::block * nodeBlock = m_collection->read_block(node.handle);
221 internal nodeInter(nodeBlock);
223 leaf_type wrap(nodeInter.values[i].handle);
227 size_t count_child_internal(internal_type node,
size_t i)
const {
228 blocks::block * nodeBlock = m_collection->read_block(node.handle);
229 internal nodeInter(nodeBlock);
231 internal_type wrap(nodeInter.values[i].handle);
235 void set_count(internal_type node,
size_t i) {
236 blocks::block * nodeBlock = m_collection->read_block(node.handle);
237 internal nodeInter(nodeBlock);
239 *(nodeInter.count) = i;
241 m_collection->write_block(node.handle);
244 void set_count(leaf_type node,
size_t i) {
245 blocks::block * nodeBlock = m_collection->read_block(node.handle);
246 leaf nodeInter(nodeBlock);
248 *(nodeInter.count) = i;
250 m_collection->write_block(node.handle);
253 leaf_type create_leaf() {
254 blocks::block_handle h = m_collection->get_free_block();
255 blocks::block * b = m_collection->read_block(h);
258 m_collection->write_block(h);
262 leaf_type create(leaf_type) {
263 return create_leaf();
266 internal_type create_internal() {
267 blocks::block_handle h = m_collection->get_free_block();
268 blocks::block * b = m_collection->read_block(h);
271 m_collection->write_block(h);
272 return internal_type(h);
275 internal_type create(internal_type) {
276 return create_internal();
279 void destroy(internal_type node) {
280 m_collection->free_block(node.handle);
283 void destroy(leaf_type node) {
284 m_collection->free_block(node.handle);
287 void set_root(internal_type node) {
288 m_root = node.handle;
291 void set_root(leaf_type node) {
292 m_root = node.handle;
295 internal_type get_root_internal()
const throw() {
296 return internal_type(m_root);
299 leaf_type get_root_leaf()
const throw() {
300 return leaf_type(m_root);
303 internal_type get_child_internal(internal_type node,
size_t i)
const {
304 blocks::block * nodeBlock = m_collection->read_block(node.handle);
305 internal dstInter(nodeBlock);
307 return internal_type(dstInter.values[i].handle);
310 leaf_type get_child_leaf(internal_type node,
size_t i)
const {
311 blocks::block * nodeBlock = m_collection->read_block(node.handle);
312 internal dstInter(nodeBlock);
314 return leaf_type(dstInter.values[i].handle);
317 size_t index(leaf_type child, internal_type node)
const {
318 blocks::block * nodeBlock = m_collection->read_block(node.handle);
319 internal dstInter(nodeBlock);
321 for (
size_t i=0; i < *(dstInter.count); ++i)
322 if (dstInter.values[i].handle == child.handle)
return i;
327 size_t index(internal_type child, internal_type node)
const {
328 blocks::block * nodeBlock = m_collection->read_block(node.handle);
329 internal dstInter(nodeBlock);
331 for (
size_t i=0; i < *(dstInter.count); ++i)
332 if (dstInter.values[i].handle == child.handle)
return i;
337 void set_augment(blocks::block_handle child, internal_type node,
augment_type augment) {
338 blocks::block * nodeBlock = m_collection->read_block(node.handle);
339 internal nodeInter(nodeBlock);
341 for (
size_t i=0; i < *(nodeInter.count); ++i)
343 if (nodeInter.values[i].handle == child) {
344 nodeInter.values[i].augment = augment;
345 m_collection->write_block(node.handle);
355 void set_augment(leaf_type child, internal_type node,
augment_type augment) {
356 set_augment(child.handle, node, augment);
359 void set_augment(internal_type child, internal_type node,
augment_type augment) {
360 set_augment(child.handle, node, augment);
363 const augment_type & augment(internal_type node,
size_t i)
const {
364 blocks::block * nodeBlock = m_collection->read_block(node.handle);
365 internal nodeInter(nodeBlock);
367 return nodeInter.values[i].augment;
370 size_t height()
const throw() {
374 void set_height(
size_t height)
throw() {
378 size_t size()
const throw() {
382 void set_size(
size_t size)
throw() {
387 void finalize_build() {}
389 void set_metadata(
const std::string & ) {
390 throw exception(
"Not yet implemnted.");
393 std::string get_metadata() {
394 throw exception(
"Not yet implemnted.");
397 std::shared_ptr<blocks::block_collection_cache> m_collection;
400 friend class btree_node;
403 friend class btree_iterator;
405 template <
typename,
typename>
406 friend class bbits::tree_state;
408 template <
typename,
typename>
409 friend class bbits::tree;
411 template <
typename,
typename>
412 friend class bbits::builder;
Defines the tp_assert macro.
T * get()
Return a raw pointer to the array content.
A augment_type
Type of augmentation stored.
This file contains a few deprecated definitions for legacy code.
Storage used for an external btree.
T value_type
Type of value of items stored.
external_store(const std::string &path, bool=false)
Construct a new empty btree storage.
#define tp_assert(condition, message)