Stxxl
1.3.1
|
00001 /*************************************************************************** 00002 * include/stxxl/bits/mng/write_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 * Copyright (C) 2009 Andreas Beckmann <beckmann@cs.uni-frankfurt.de> 00008 * 00009 * Distributed under the Boost Software License, Version 1.0. 00010 * (See accompanying file LICENSE_1_0.txt or copy at 00011 * http://www.boost.org/LICENSE_1_0.txt) 00012 **************************************************************************/ 00013 00014 #ifndef STXXL_WRITE_POOL_HEADER 00015 #define STXXL_WRITE_POOL_HEADER 00016 00017 #include <list> 00018 00019 #ifdef STXXL_BOOST_CONFIG 00020 #include <boost/config.hpp> 00021 #endif 00022 00023 #include <stxxl/bits/noncopyable.h> 00024 #include <stxxl/bits/deprecated.h> 00025 #include <stxxl/bits/io/request_operations.h> 00026 00027 00028 __STXXL_BEGIN_NAMESPACE 00029 00032 00033 00035 template <class BlockType> 00036 class write_pool : private noncopyable 00037 { 00038 public: 00039 typedef BlockType block_type; 00040 typedef typename block_type::bid_type bid_type; 00041 00042 // a hack to make wait_any work with busy_entry type 00043 struct busy_entry 00044 { 00045 block_type * block; 00046 request_ptr req; 00047 bid_type bid; 00048 00049 busy_entry() : block(NULL) { } 00050 busy_entry(const busy_entry & a) : block(a.block), req(a.req), bid(a.bid) { } 00051 busy_entry(block_type * & bl, request_ptr & r, bid_type & bi) : 00052 block(bl), req(r), bid(bi) { } 00053 00054 operator request_ptr () { return req; } 00055 }; 00056 typedef typename std::list<block_type *>::iterator free_blocks_iterator; 00057 typedef typename std::list<busy_entry>::iterator busy_blocks_iterator; 00058 00059 protected: 00060 // contains free write blocks 00061 std::list<block_type *> free_blocks; 00062 // blocks that are in writing 00063 std::list<busy_entry> busy_blocks; 00064 00065 unsigned_type free_blocks_size, busy_blocks_size; 00066 00067 public: 00070 explicit write_pool(unsigned_type init_size = 1) : free_blocks_size(init_size), busy_blocks_size(0) 00071 { 00072 unsigned_type i = 0; 00073 for ( ; i < init_size; ++i) 00074 free_blocks.push_back(new block_type); 00075 } 00076 00077 void swap(write_pool & obj) 00078 { 00079 std::swap(free_blocks, obj.free_blocks); 00080 std::swap(busy_blocks, obj.busy_blocks); 00081 std::swap(free_blocks_size, obj.free_blocks_size); 00082 std::swap(busy_blocks_size, busy_blocks_size); 00083 } 00084 00086 virtual ~write_pool() 00087 { 00088 STXXL_VERBOSE2("write_pool::~write_pool free_blocks_size: " << 00089 free_blocks_size << " busy_blocks_size: " << busy_blocks_size); 00090 while (!free_blocks.empty()) 00091 { 00092 delete free_blocks.back(); 00093 free_blocks.pop_back(); 00094 } 00095 00096 try 00097 { 00098 for (busy_blocks_iterator i2 = busy_blocks.begin(); i2 != busy_blocks.end(); ++i2) 00099 { 00100 i2->req->wait(); 00101 delete i2->block; 00102 } 00103 } 00104 catch (...) 00105 { } 00106 } 00107 00109 unsigned_type size() const { return free_blocks_size + busy_blocks_size; } 00110 00117 request_ptr write(block_type * & block, bid_type bid) 00118 { 00119 STXXL_VERBOSE1("write_pool::write: " << block << " @ " << bid); 00120 for (busy_blocks_iterator i2 = busy_blocks.begin(); i2 != busy_blocks.end(); ++i2) 00121 { 00122 if (i2->bid == bid) { 00123 assert(i2->block != block); 00124 STXXL_VERBOSE1("WAW dependency"); 00125 // try to cancel the obsolete request 00126 i2->req->cancel(); 00127 // invalidate the bid of the stale write request, 00128 // prevents prefetch_pool from stealing a stale block 00129 i2->bid.storage = 0; 00130 } 00131 } 00132 request_ptr result = block->write(bid); 00133 ++busy_blocks_size; 00134 busy_blocks.push_back(busy_entry(block, result, bid)); 00135 block = NULL; // prevent caller from using the block any further 00136 return result; 00137 } 00138 00141 block_type * steal() 00142 { 00143 assert(size() > 0); 00144 if (free_blocks_size) 00145 { 00146 STXXL_VERBOSE1("write_pool::steal : " << free_blocks_size << " free blocks available"); 00147 --free_blocks_size; 00148 block_type * p = free_blocks.back(); 00149 free_blocks.pop_back(); 00150 return p; 00151 } 00152 STXXL_VERBOSE1("write_pool::steal : all " << busy_blocks_size << " are busy"); 00153 busy_blocks_iterator completed = wait_any(busy_blocks.begin(), busy_blocks.end()); 00154 assert(completed != busy_blocks.end()); // we got something reasonable from wait_any 00155 assert(completed->req->poll()); // and it is *really* completed 00156 block_type * p = completed->block; 00157 busy_blocks.erase(completed); 00158 --busy_blocks_size; 00159 check_all_busy(); // for debug 00160 return p; 00161 } 00162 00163 // deprecated name for the steal() 00164 _STXXL_DEPRECATED(block_type * get()) 00165 { 00166 return steal(); 00167 } 00168 00171 void resize(unsigned_type new_size) 00172 { 00173 int_type diff = int_type(new_size) - int_type(size()); 00174 if (diff > 0) 00175 { 00176 free_blocks_size += diff; 00177 while (--diff >= 0) 00178 free_blocks.push_back(new block_type); 00179 00180 return; 00181 } 00182 00183 while (++diff <= 0) 00184 delete steal(); 00185 } 00186 00187 _STXXL_DEPRECATED(request_ptr get_request(bid_type bid)) 00188 { 00189 busy_blocks_iterator i2 = busy_blocks.begin(); 00190 for ( ; i2 != busy_blocks.end(); ++i2) 00191 { 00192 if (i2->bid == bid) 00193 return i2->req; 00194 } 00195 return request_ptr(); 00196 } 00197 00198 bool has_request(bid_type bid) 00199 { 00200 for (busy_blocks_iterator i2 = busy_blocks.begin(); i2 != busy_blocks.end(); ++i2) 00201 { 00202 if (i2->bid == bid) 00203 return true; 00204 } 00205 return false; 00206 } 00207 00208 _STXXL_DEPRECATED(block_type * steal(bid_type bid)) 00209 { 00210 busy_blocks_iterator i2 = busy_blocks.begin(); 00211 for ( ; i2 != busy_blocks.end(); ++i2) 00212 { 00213 if (i2->bid == bid) 00214 { 00215 block_type * p = i2->block; 00216 i2->req->wait(); 00217 busy_blocks.erase(i2); 00218 --busy_blocks_size; 00219 return p; 00220 } 00221 } 00222 return NULL; 00223 } 00224 00225 // returns a block and a (potentially unfinished) I/O request associated with it 00226 std::pair<block_type *, request_ptr> steal_request(bid_type bid) 00227 { 00228 for (busy_blocks_iterator i2 = busy_blocks.begin(); i2 != busy_blocks.end(); ++i2) 00229 { 00230 if (i2->bid == bid) 00231 { 00232 // remove busy block from list, request has not yet been waited for! 00233 block_type * blk = i2->block; 00234 request_ptr req = i2->req; 00235 busy_blocks.erase(i2); 00236 --busy_blocks_size; 00237 00238 // hand over block and (unfinished) request to caller 00239 return std::pair<block_type *, request_ptr>(blk, req); 00240 } 00241 } 00242 // not matching request found, return a dummy 00243 return std::pair<block_type *, request_ptr>((block_type *)NULL, request_ptr()); 00244 } 00245 00246 void add(block_type * & block) 00247 { 00248 free_blocks.push_back(block); 00249 ++free_blocks_size; 00250 block = NULL; // prevent caller from using the block any further 00251 } 00252 00253 protected: 00254 void check_all_busy() 00255 { 00256 busy_blocks_iterator cur = busy_blocks.begin(); 00257 int_type cnt = 0; 00258 while (cur != busy_blocks.end()) 00259 { 00260 if (cur->req->poll()) 00261 { 00262 free_blocks.push_back(cur->block); 00263 cur = busy_blocks.erase(cur); 00264 ++cnt; 00265 --busy_blocks_size; 00266 ++free_blocks_size; 00267 continue; 00268 } 00269 ++cur; 00270 } 00271 STXXL_VERBOSE1("write_pool::check_all_busy : " << cnt << 00272 " are completed out of " << busy_blocks_size + cnt << " busy blocks"); 00273 } 00274 }; 00275 00277 00278 __STXXL_END_NAMESPACE 00279 00280 00281 namespace std 00282 { 00283 template <class BlockType> 00284 void swap(stxxl::write_pool<BlockType> & a, 00285 stxxl::write_pool<BlockType> & b) 00286 { 00287 a.swap(b); 00288 } 00289 } 00290 00291 #endif // !STXXL_WRITE_POOL_HEADER 00292 // vim: et:ts=4:sw=4