|
Stxxl
1.4.0
|
|
Stxxl
1.4.0
|
00001 /*************************************************************************** 00002 * include/stxxl/bits/containers/btree/node_cache.h 00003 * 00004 * Part of the STXXL. See http://stxxl.sourceforge.net 00005 * 00006 * Copyright (C) 2006 Roman Dementiev <dementiev@ira.uka.de> 00007 * 00008 * Distributed under the Boost Software License, Version 1.0. 00009 * (See accompanying file LICENSE_1_0.txt or copy at 00010 * http://www.boost.org/LICENSE_1_0.txt) 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 // TODO: speedup BID2node_ access using search result iterator in the methods 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 struct bid_comp 00053 { 00054 bool operator () (const bid_type & a, const bid_type & b) const 00055 { 00056 return (a.storage < b.storage) || ( a.storage == b.storage && a.offset < b.offset); 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 { // parameters for hash table 00076 bucket_size = 4, // 0 < bucket_size 00077 min_buckets = 8 // min_buckets = 2 ^^ N, 0 < N 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 //typedef std::map<bid_type,int_type,bid_comp> BID2node_type; 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 // changes btree pointer in all contained iterators 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 // returns the number of fixed pages 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 // need to kick a node 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 //reqs_[node2kick] = request_ptr(); // reset request 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 // assert(!(reqs_[free_node].valid())); 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 // the node is in cache 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 // the node is not in cache 00297 if (free_nodes_.empty()) 00298 { 00299 // need to kick a node 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 // the node is in cache 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 // the node is not in cache 00393 if (free_nodes_.empty()) 00394 { 00395 // need to kick a node 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 // the node is in the cache 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 //reqs_[nodeindex] = request_ptr(); // reset request 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 // the node is not in cache 00499 if (free_nodes_.empty()) 00500 { 00501 // need to kick a node 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 /* STXXL_CONTAINERS_BTREE__NODE_CACHE_H */
1.7.6.1
