Stxxl 1.2.1
|
00001 /*************************************************************************** 00002 * include/stxxl/bits/mng/prefetch_pool.h 00003 * 00004 * Part of the STXXL. See http://stxxl.sourceforge.net 00005 * 00006 * Copyright (C) 2003-2004 Roman Dementiev <dementiev@mpi-sb.mpg.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_PREFETCH_POOL_HEADER 00014 #define STXXL_PREFETCH_POOL_HEADER 00015 00016 #include <list> 00017 00018 #ifdef STXXL_BOOST_CONFIG 00019 #include <boost/config.hpp> 00020 #endif 00021 00022 #include <stxxl/bits/mng/mng.h> 00023 #include <stxxl/bits/mng/write_pool.h> 00024 #include <stxxl/bits/compat_hash_map.h> 00025 00026 00027 __STXXL_BEGIN_NAMESPACE 00028 00031 00033 template <class BlockType> 00034 class prefetch_pool : private noncopyable 00035 { 00036 public: 00037 typedef BlockType block_type; 00038 typedef typename block_type::bid_type bid_type; 00039 00040 protected: 00041 struct bid_hash 00042 { 00043 size_t operator () (const bid_type & bid) const 00044 { 00045 size_t result = size_t(bid.storage) + 00046 size_t(bid.offset & 0xffffffff) + size_t(bid.offset >> 32); 00047 return result; 00048 } 00049 #ifdef BOOST_MSVC 00050 bool operator () (const bid_type & a, const bid_type & b) const 00051 { 00052 return (a.storage < b.storage) || (a.storage == b.storage && a.offset < b.offset); 00053 } 00054 enum 00055 { // parameters for hash table 00056 bucket_size = 4, // 0 < bucket_size 00057 min_buckets = 8 // min_buckets = 2 ^^ N, 0 < N 00058 }; 00059 #endif 00060 }; 00061 typedef std::pair<block_type *, request_ptr> busy_entry; 00062 typedef typename compat_hash_map<bid_type, busy_entry, bid_hash>::result hash_map_type; 00063 typedef typename std::list<block_type *>::iterator free_blocks_iterator; 00064 typedef typename hash_map_type::iterator busy_blocks_iterator; 00065 00066 // contains free prefetch blocks 00067 std::list<block_type *> free_blocks; 00068 // blocks that are in reading or already read but not retrieved by user 00069 hash_map_type busy_blocks; 00070 00071 unsigned_type free_blocks_size; 00072 00073 public: 00076 explicit prefetch_pool(unsigned_type init_size = 1) : free_blocks_size(init_size) 00077 { 00078 unsigned_type i = 0; 00079 for ( ; i < init_size; ++i) 00080 free_blocks.push_back(new block_type); 00081 } 00082 00083 void swap(prefetch_pool & obj) 00084 { 00085 std::swap(free_blocks, obj.free_blocks); 00086 std::swap(busy_blocks, obj.busy_blocks); 00087 std::swap(free_blocks_size, obj.free_blocks_size); 00088 } 00089 00091 virtual ~prefetch_pool() 00092 { 00093 while (!free_blocks.empty()) 00094 { 00095 delete free_blocks.back(); 00096 free_blocks.pop_back(); 00097 } 00098 00099 try 00100 { 00101 busy_blocks_iterator i2 = busy_blocks.begin(); 00102 for ( ; i2 != busy_blocks.end(); ++i2) 00103 { 00104 i2->second.second->wait(); 00105 delete i2->second.first; 00106 } 00107 } 00108 catch (...) 00109 { } 00110 } 00112 unsigned_type size() const { return free_blocks_size + busy_blocks.size(); } 00113 00121 bool hint(bid_type bid) 00122 { 00123 // if block is already hinted, no need to hint it again 00124 if (busy_blocks.find(bid) != busy_blocks.end()) 00125 return true; 00126 00127 00128 if (free_blocks_size) // only if we have a free block 00129 { 00130 STXXL_VERBOSE2("prefetch_pool::hint bid= " << bid << " => prefetching"); 00131 00132 --free_blocks_size; 00133 block_type * block = free_blocks.back(); 00134 free_blocks.pop_back(); 00135 request_ptr req = block->read(bid); 00136 busy_blocks[bid] = busy_entry(block, req); 00137 return true; 00138 } 00139 STXXL_VERBOSE2("prefetch_pool::hint bid=" << bid << " => no free blocks for prefetching"); 00140 return false; 00141 } 00142 00143 bool hint(bid_type bid, write_pool<block_type> & w_pool) 00144 { 00145 // if block is already hinted, no need to hint it again 00146 if (busy_blocks.find(bid) != busy_blocks.end()) 00147 return true; 00148 00149 00150 if (free_blocks_size) // only if we have a free block 00151 { 00152 STXXL_VERBOSE2("prefetch_pool::hint2 bid= " << bid << " => prefetching"); 00153 --free_blocks_size; 00154 block_type * block = free_blocks.back(); 00155 free_blocks.pop_back(); 00156 request_ptr req = w_pool.get_request(bid); 00157 if (req.valid()) 00158 { 00159 block_type * w_block = w_pool.steal(bid); 00160 STXXL_VERBOSE1("prefetch_pool::hint2 bid= " << bid << " was in write cache at " << w_block); 00161 assert(w_block != 0); 00162 w_pool.add(block); //in exchange 00163 busy_blocks[bid] = busy_entry(w_block, req); 00164 return true; 00165 } 00166 req = block->read(bid); 00167 busy_blocks[bid] = busy_entry(block, req); 00168 return true; 00169 } 00170 STXXL_VERBOSE2("prefetch_pool::hint2 bid=" << bid << " => no free blocks for prefetching"); 00171 return false; 00172 } 00173 00174 bool in_prefetching(bid_type bid) 00175 { 00176 return (busy_blocks.find(bid) != busy_blocks.end()); 00177 } 00178 00185 request_ptr read(block_type * & block, bid_type bid) 00186 { 00187 busy_blocks_iterator cache_el = busy_blocks.find(bid); 00188 if (cache_el == busy_blocks.end()) 00189 { 00190 // not cached 00191 STXXL_VERBOSE1("prefetch_pool::read bid=" << bid << " => no copy in cache, retrieving to " << block); 00192 return block->read(bid); 00193 } 00194 00195 // cached 00196 STXXL_VERBOSE1("prefetch_pool::read bid=" << bid << " => copy in cache exists"); 00197 ++free_blocks_size; 00198 free_blocks.push_back(block); 00199 block = cache_el->second.first; 00200 request_ptr result = cache_el->second.second; 00201 busy_blocks.erase(cache_el); 00202 return result; 00203 } 00204 00211 unsigned_type resize(unsigned_type new_size) 00212 { 00213 int_type diff = int_type(new_size) - int_type(size()); 00214 if (diff > 0) 00215 { 00216 free_blocks_size += diff; 00217 while (--diff >= 0) 00218 free_blocks.push_back(new block_type); 00219 00220 00221 return size(); 00222 } 00223 00224 while (diff < 0 && free_blocks_size > 0) 00225 { 00226 ++diff; 00227 --free_blocks_size; 00228 delete free_blocks.back(); 00229 free_blocks.pop_back(); 00230 } 00231 return size(); 00232 } 00233 }; 00234 00236 00237 __STXXL_END_NAMESPACE 00238 00239 namespace std 00240 { 00241 template <class BlockType> 00242 void swap(stxxl::prefetch_pool<BlockType> & a, 00243 stxxl::prefetch_pool<BlockType> & b) 00244 { 00245 a.swap(b); 00246 } 00247 } 00248 00249 #endif // !STXXL_PREFETCH_POOL_HEADER