00001
00002
00003
00004
00005
00006
00007
00008
00009
00010
00011
00012
00013 #ifndef STXXL_CONTAINERS_BTREE__NODE_CACHE_H
00014 #define STXXL_CONTAINERS_BTREE__NODE_CACHE_H
00015
00016 #ifdef STXXL_BOOST_CONFIG
00017 #include <boost/config.hpp>
00018 #endif
00019
00020 #include <stxxl/bits/compat_hash_map.h>
00021 #include <stxxl/bits/io/request_ptr.h>
00022 #include <stxxl/bits/mng/mng.h>
00023 #include <stxxl/bits/mng/typed_block.h>
00024 #include <stxxl/bits/containers/pager.h>
00025 #include <stxxl/bits/common/error_handling.h>
00026
00027
00028 __STXXL_BEGIN_NAMESPACE
00029
00030
00031
00032 namespace btree
00033 {
00034 template <class NodeType, class BTreeType>
00035 class node_cache : private noncopyable
00036 {
00037 public:
00038 typedef BTreeType btree_type;
00039 typedef NodeType node_type;
00040 typedef typename node_type::block_type block_type;
00041 typedef typename node_type::bid_type bid_type;
00042 typedef typename btree_type::key_compare key_compare;
00043
00044 typedef typename btree_type::alloc_strategy_type alloc_strategy_type;
00045 typedef stxxl::lru_pager<> pager_type;
00046
00047 private:
00048 btree_type * btree_;
00049 key_compare comp_;
00050
00051
00052
00053
00054
00055
00056
00057
00058
00059
00060
00061 struct bid_hash
00062 {
00063 size_t operator () (const bid_type & bid) const
00064 {
00065 size_t result =
00066 longhash1(bid.offset + uint64(unsigned_type(bid.storage)));
00067 return result;
00068 }
00069 #ifdef BOOST_MSVC
00070 bool operator () (const bid_type & a, const bid_type & b) const
00071 {
00072 return (a.storage < b.storage) || (a.storage == b.storage && a.offset < b.offset);
00073 }
00074 enum
00075 {
00076 bucket_size = 4,
00077 min_buckets = 8
00078 };
00079 #endif
00080 };
00081
00082 std::vector<node_type *> nodes_;
00083 std::vector<request_ptr> reqs_;
00084 std::vector<bool> fixed_;
00085 std::vector<bool> dirty_;
00086 std::vector<int_type> free_nodes_;
00087 typedef typename compat_hash_map<bid_type, int_type, bid_hash>::result hash_map_type;
00088
00089
00090 typedef hash_map_type BID2node_type;
00091
00092 BID2node_type BID2node_;
00093 pager_type pager_;
00094 block_manager * bm;
00095 alloc_strategy_type alloc_strategy_;
00096
00097 int64 n_found;
00098 int64 n_not_found;
00099 int64 n_created;
00100 int64 n_deleted;
00101 int64 n_read;
00102 int64 n_written;
00103 int64 n_clean_forced;
00104
00105
00106 void change_btree_pointers(btree_type * b)
00107 {
00108 typename std::vector<node_type *>::const_iterator it = nodes_.begin();
00109 for ( ; it != nodes_.end(); ++it)
00110 {
00111 (*it)->btree_ = b;
00112 }
00113 }
00114
00115 public:
00116 node_cache(unsigned_type cache_size_in_bytes,
00117 btree_type * btree__,
00118 key_compare comp__
00119 ) :
00120 btree_(btree__),
00121 comp_(comp__),
00122 bm(block_manager::get_instance()),
00123 n_found(0),
00124 n_not_found(0),
00125 n_created(0),
00126 n_deleted(0),
00127 n_read(0),
00128 n_written(0),
00129 n_clean_forced(0)
00130 {
00131 const unsigned_type nnodes = cache_size_in_bytes / block_type::raw_size;
00132 STXXL_VERBOSE1("btree::node_cache constructor nodes=" << nnodes);
00133 if (nnodes < 3)
00134 {
00135 STXXL_THROW(std::runtime_error, "btree::node_cache::node_cache", "Too few memory for a node cache (<3)");
00136 }
00137 nodes_.reserve(nnodes);
00138 reqs_.resize(nnodes);
00139 free_nodes_.reserve(nnodes);
00140 fixed_.resize(nnodes, false);
00141 dirty_.resize(nnodes, true);
00142 for (unsigned_type i = 0; i < nnodes; ++i)
00143 {
00144 nodes_.push_back(new node_type(btree_, comp_));
00145 free_nodes_.push_back(i);
00146 }
00147
00148 pager_type tmp_pager(nnodes);
00149 std::swap(pager_, tmp_pager);
00150 }
00151
00152 unsigned_type size() const
00153 {
00154 return nodes_.size();
00155 }
00156
00157
00158 unsigned_type nfixed() const
00159 {
00160 typename BID2node_type::const_iterator i = BID2node_.begin();
00161 typename BID2node_type::const_iterator end = BID2node_.end();
00162 unsigned_type cnt = 0;
00163 for ( ; i != end; ++i)
00164 {
00165 if (fixed_[(*i).second])
00166 ++cnt;
00167 }
00168 return cnt;
00169 }
00170
00171 ~node_cache()
00172 {
00173 STXXL_VERBOSE1("btree::node_cache destructor addr=" << this);
00174 typename BID2node_type::const_iterator i = BID2node_.begin();
00175 typename BID2node_type::const_iterator end = BID2node_.end();
00176 for ( ; i != end; ++i)
00177 {
00178 const unsigned_type p = (*i).second;
00179 if (reqs_[p].valid())
00180 reqs_[p]->wait();
00181
00182 if (dirty_[p])
00183 nodes_[p]->save();
00184 }
00185 for (unsigned_type i = 0; i < size(); ++i)
00186 delete nodes_[i];
00187 }
00188
00189 node_type * get_new_node(bid_type & new_bid)
00190 {
00191 ++n_created;
00192
00193 if (free_nodes_.empty())
00194 {
00195
00196 int_type node2kick;
00197 unsigned_type i = 0;
00198 const unsigned_type max_tries = size() + 1;
00199 do
00200 {
00201 ++i;
00202 node2kick = pager_.kick();
00203 if (i == max_tries)
00204 {
00205 STXXL_ERRMSG(
00206 "The node cache is too small, no node can be kicked out (all nodes are fixed) !");
00207 STXXL_ERRMSG("Returning NULL node.");
00208 return NULL;
00209 }
00210 pager_.hit(node2kick);
00211 } while (fixed_[node2kick]);
00212
00213
00214 if (reqs_[node2kick].valid())
00215 reqs_[node2kick]->wait();
00216
00217
00218 node_type & Node = *(nodes_[node2kick]);
00219
00220 if (dirty_[node2kick])
00221 {
00222 Node.save();
00223 ++n_written;
00224 }
00225 else
00226 ++n_clean_forced;
00227
00228
00229
00230
00231 assert(BID2node_.find(Node.my_bid()) != BID2node_.end());
00232 BID2node_.erase(Node.my_bid());
00233 bm->new_block(alloc_strategy_, new_bid);
00234
00235 BID2node_[new_bid] = node2kick;
00236
00237 Node.init(new_bid);
00238
00239 dirty_[node2kick] = true;
00240
00241 assert(size() == BID2node_.size() + free_nodes_.size());
00242
00243 STXXL_VERBOSE1("btree::node_cache get_new_node, need to kick node " << node2kick);
00244
00245 return &Node;
00246 }
00247
00248
00249 int_type free_node = free_nodes_.back();
00250 free_nodes_.pop_back();
00251 assert(fixed_[free_node] == false);
00252
00253 bm->new_block(alloc_strategy_, new_bid);
00254 BID2node_[new_bid] = free_node;
00255 node_type & Node = *(nodes_[free_node]);
00256 Node.init(new_bid);
00257
00258
00259
00260 pager_.hit(free_node);
00261
00262 dirty_[free_node] = true;
00263
00264 assert(size() == BID2node_.size() + free_nodes_.size());
00265
00266 STXXL_VERBOSE1("btree::node_cache get_new_node, free node " << free_node << "available");
00267
00268 return &Node;
00269 }
00270
00271
00272 node_type * get_node(const bid_type & bid, bool fix = false)
00273 {
00274 typename BID2node_type::const_iterator it = BID2node_.find(bid);
00275 ++n_read;
00276
00277 if (it != BID2node_.end())
00278 {
00279
00280 const int_type nodeindex = it->second;
00281 STXXL_VERBOSE1("btree::node_cache get_node, the node " << nodeindex << "is in cache , fix=" << fix);
00282 fixed_[nodeindex] = fix;
00283 pager_.hit(nodeindex);
00284 dirty_[nodeindex] = true;
00285
00286 if (reqs_[nodeindex].valid() && !reqs_[nodeindex]->poll())
00287 reqs_[nodeindex]->wait();
00288
00289
00290 ++n_found;
00291 return nodes_[nodeindex];
00292 }
00293
00294 ++n_not_found;
00295
00296
00297 if (free_nodes_.empty())
00298 {
00299
00300 int_type node2kick;
00301 unsigned_type i = 0;
00302 const unsigned_type max_tries = size() + 1;
00303 do
00304 {
00305 ++i;
00306 node2kick = pager_.kick();
00307 if (i == max_tries)
00308 {
00309 STXXL_ERRMSG(
00310 "The node cache is too small, no node can be kicked out (all nodes are fixed) !");
00311 STXXL_ERRMSG("Returning NULL node.");
00312 return NULL;
00313 }
00314 pager_.hit(node2kick);
00315 } while (fixed_[node2kick]);
00316
00317 if (reqs_[node2kick].valid())
00318 reqs_[node2kick]->wait();
00319
00320
00321 node_type & Node = *(nodes_[node2kick]);
00322
00323 if (dirty_[node2kick])
00324 {
00325 Node.save();
00326 ++n_written;
00327 }
00328 else
00329 ++n_clean_forced;
00330
00331
00332 BID2node_.erase(Node.my_bid());
00333
00334 reqs_[node2kick] = Node.load(bid);
00335 BID2node_[bid] = node2kick;
00336
00337 fixed_[node2kick] = fix;
00338
00339 dirty_[node2kick] = true;
00340
00341 assert(size() == BID2node_.size() + free_nodes_.size());
00342
00343 STXXL_VERBOSE1("btree::node_cache get_node, need to kick node" << node2kick << " fix=" << fix);
00344
00345 return &Node;
00346 }
00347
00348 int_type free_node = free_nodes_.back();
00349 free_nodes_.pop_back();
00350 assert(fixed_[free_node] == false);
00351
00352 node_type & Node = *(nodes_[free_node]);
00353 reqs_[free_node] = Node.load(bid);
00354 BID2node_[bid] = free_node;
00355
00356 pager_.hit(free_node);
00357
00358 fixed_[free_node] = fix;
00359
00360 dirty_[free_node] = true;
00361
00362 assert(size() == BID2node_.size() + free_nodes_.size());
00363
00364 STXXL_VERBOSE1("btree::node_cache get_node, free node " << free_node << "available, fix=" << fix);
00365
00366 return &Node;
00367 }
00368
00369 node_type const * get_const_node(const bid_type & bid, bool fix = false)
00370 {
00371 typename BID2node_type::const_iterator it = BID2node_.find(bid);
00372 ++n_read;
00373
00374 if (it != BID2node_.end())
00375 {
00376
00377 const int_type nodeindex = it->second;
00378 STXXL_VERBOSE1("btree::node_cache get_node, the node " << nodeindex << "is in cache , fix=" << fix);
00379 fixed_[nodeindex] = fix;
00380 pager_.hit(nodeindex);
00381
00382 if (reqs_[nodeindex].valid() && !reqs_[nodeindex]->poll())
00383 reqs_[nodeindex]->wait();
00384
00385
00386 ++n_found;
00387 return nodes_[nodeindex];
00388 }
00389
00390 ++n_not_found;
00391
00392
00393 if (free_nodes_.empty())
00394 {
00395
00396 int_type node2kick;
00397 unsigned_type i = 0;
00398 const unsigned_type max_tries = size() + 1;
00399 do
00400 {
00401 ++i;
00402 node2kick = pager_.kick();
00403 if (i == max_tries)
00404 {
00405 STXXL_ERRMSG(
00406 "The node cache is too small, no node can be kicked out (all nodes are fixed) !");
00407 STXXL_ERRMSG("Returning NULL node.");
00408 return NULL;
00409 }
00410 pager_.hit(node2kick);
00411 } while (fixed_[node2kick]);
00412
00413 if (reqs_[node2kick].valid())
00414 reqs_[node2kick]->wait();
00415
00416
00417 node_type & Node = *(nodes_[node2kick]);
00418 if (dirty_[node2kick])
00419 {
00420 Node.save();
00421 ++n_written;
00422 }
00423 else
00424 ++n_clean_forced;
00425
00426
00427 BID2node_.erase(Node.my_bid());
00428
00429 reqs_[node2kick] = Node.load(bid);
00430 BID2node_[bid] = node2kick;
00431
00432 fixed_[node2kick] = fix;
00433
00434 dirty_[node2kick] = false;
00435
00436 assert(size() == BID2node_.size() + free_nodes_.size());
00437
00438 STXXL_VERBOSE1("btree::node_cache get_node, need to kick node" << node2kick << " fix=" << fix);
00439
00440 return &Node;
00441 }
00442
00443 int_type free_node = free_nodes_.back();
00444 free_nodes_.pop_back();
00445 assert(fixed_[free_node] == false);
00446
00447 node_type & Node = *(nodes_[free_node]);
00448 reqs_[free_node] = Node.load(bid);
00449 BID2node_[bid] = free_node;
00450
00451 pager_.hit(free_node);
00452
00453 fixed_[free_node] = fix;
00454
00455 dirty_[free_node] = false;
00456
00457 assert(size() == BID2node_.size() + free_nodes_.size());
00458
00459 STXXL_VERBOSE1("btree::node_cache get_node, free node " << free_node << "available, fix=" << fix);
00460
00461 return &Node;
00462 }
00463
00464 void delete_node(const bid_type & bid)
00465 {
00466 typename BID2node_type::const_iterator it = BID2node_.find(bid);
00467 try
00468 {
00469 if (it != BID2node_.end())
00470 {
00471
00472 const int_type nodeindex = it->second;
00473 STXXL_VERBOSE1("btree::node_cache delete_node " << nodeindex << " from cache.");
00474 if (reqs_[nodeindex].valid())
00475 reqs_[nodeindex]->wait();
00476
00477
00478 free_nodes_.push_back(nodeindex);
00479 BID2node_.erase(bid);
00480 fixed_[nodeindex] = false;
00481 }
00482 ++n_deleted;
00483 } catch (const io_error & ex)
00484 {
00485 bm->delete_block(bid);
00486 throw io_error(ex.what());
00487 }
00488 bm->delete_block(bid);
00489 }
00490
00491
00492 void prefetch_node(const bid_type & bid)
00493 {
00494 if (BID2node_.find(bid) != BID2node_.end())
00495 return;
00496
00497
00498
00499 if (free_nodes_.empty())
00500 {
00501
00502 int_type node2kick;
00503 unsigned_type i = 0;
00504 const unsigned_type max_tries = size() + 1;
00505 do
00506 {
00507 ++i;
00508 node2kick = pager_.kick();
00509 if (i == max_tries)
00510 {
00511 STXXL_ERRMSG(
00512 "The node cache is too small, no node can be kicked out (all nodes are fixed) !");
00513 STXXL_ERRMSG("Returning NULL node.");
00514 return;
00515 }
00516 pager_.hit(node2kick);
00517 } while (fixed_[node2kick]);
00518
00519 if (reqs_[node2kick].valid())
00520 reqs_[node2kick]->wait();
00521
00522
00523 node_type & Node = *(nodes_[node2kick]);
00524
00525 if (dirty_[node2kick])
00526 {
00527 Node.save();
00528 ++n_written;
00529 }
00530 else
00531 ++n_clean_forced;
00532
00533
00534 BID2node_.erase(Node.my_bid());
00535
00536 reqs_[node2kick] = Node.prefetch(bid);
00537 BID2node_[bid] = node2kick;
00538
00539 fixed_[node2kick] = false;
00540
00541 dirty_[node2kick] = false;
00542
00543 assert(size() == BID2node_.size() + free_nodes_.size());
00544
00545 STXXL_VERBOSE1("btree::node_cache prefetch_node, need to kick node" << node2kick << " ");
00546
00547 return;
00548 }
00549
00550 int_type free_node = free_nodes_.back();
00551 free_nodes_.pop_back();
00552 assert(fixed_[free_node] == false);
00553
00554 node_type & Node = *(nodes_[free_node]);
00555 reqs_[free_node] = Node.prefetch(bid);
00556 BID2node_[bid] = free_node;
00557
00558 pager_.hit(free_node);
00559
00560 fixed_[free_node] = false;
00561
00562 dirty_[free_node] = false;
00563
00564 assert(size() == BID2node_.size() + free_nodes_.size());
00565
00566 STXXL_VERBOSE1("btree::node_cache prefetch_node, free node " << free_node << "available");
00567
00568 return;
00569 }
00570
00571 void unfix_node(const bid_type & bid)
00572 {
00573 assert(BID2node_.find(bid) != BID2node_.end());
00574 fixed_[BID2node_[bid]] = false;
00575 STXXL_VERBOSE1("btree::node_cache unfix_node, node " << BID2node_[bid]);
00576 }
00577
00578 void swap(node_cache & obj)
00579 {
00580 std::swap(comp_, obj.comp_);
00581 std::swap(nodes_, obj.nodes_);
00582 std::swap(reqs_, obj.reqs_);
00583 change_btree_pointers(btree_);
00584 obj.change_btree_pointers(obj.btree_);
00585 std::swap(fixed_, obj.fixed_);
00586 std::swap(free_nodes_, obj.free_nodes_);
00587 std::swap(BID2node_, obj.BID2node_);
00588 std::swap(pager_, obj.pager_);
00589 std::swap(alloc_strategy_, obj.alloc_strategy_);
00590 std::swap(n_found, obj.n_found);
00591 std::swap(n_not_found, obj.n_found);
00592 std::swap(n_created, obj.n_created);
00593 std::swap(n_deleted, obj.n_deleted);
00594 std::swap(n_read, obj.n_read);
00595 std::swap(n_written, obj.n_written);
00596 std::swap(n_clean_forced, obj.n_clean_forced);
00597 }
00598
00599 void print_statistics(std::ostream & o) const
00600 {
00601 if (n_read)
00602 o << "Found blocks : " << n_found << " (" <<
00603 100. * double(n_found) / double(n_read) << "%)" << std::endl;
00604
00605 else
00606 o << "Found blocks : " << n_found << " (" <<
00607 100 << "%)" << std::endl;
00608
00609 o << "Not found blocks : " << n_not_found << std::endl;
00610 o << "Created in the cache blocks : " << n_created << std::endl;
00611 o << "Deleted blocks : " << n_deleted << std::endl;
00612 o << "Read blocks : " << n_read << std::endl;
00613 o << "Written blocks : " << n_written << std::endl;
00614 o << "Clean blocks forced from the cache: " << n_clean_forced << std::endl;
00615 }
00616 void reset_statistics()
00617 {
00618 n_found = 0;
00619 n_not_found = 0;
00620 n_created = 0;
00621 n_deleted = 0;
00622 n_read = 0;
00623 n_written = 0;
00624 n_clean_forced = 0;
00625 }
00626 };
00627 }
00628
00629 __STXXL_END_NAMESPACE
00630
00631
00632 namespace std
00633 {
00634 template <class NodeType, class BTreeType>
00635 void swap(stxxl::btree::node_cache<NodeType, BTreeType> & a,
00636 stxxl::btree::node_cache<NodeType, BTreeType> & b)
00637 {
00638 a.swap(b);
00639 }
00640 }
00641
00642 #endif
