00001
00002
00003
00004
00005
00006
00007
00008
00009
00010
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 {
00056 bucket_size = 4,
00057 min_buckets = 8
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
00067 std::list<block_type *> free_blocks;
00068
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
00124 if (busy_blocks.find(bid) != busy_blocks.end())
00125 return true;
00126
00127
00128 if (free_blocks_size)
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
00146 if (busy_blocks.find(bid) != busy_blocks.end())
00147 return true;
00148
00149
00150 if (free_blocks_size)
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);
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
00191 STXXL_VERBOSE1("prefetch_pool::read bid=" << bid << " => no copy in cache, retrieving to " << block);
00192 return block->read(bid);
00193 }
00194
00195
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