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