Stxxl  1.2.1
prefetch_pool.h
1 /***************************************************************************
2  * include/stxxl/bits/mng/prefetch_pool.h
3  *
4  * Part of the STXXL. See http://stxxl.sourceforge.net
5  *
6  * Copyright (C) 2003-2004 Roman Dementiev <dementiev@mpi-sb.mpg.de>
7  *
8  * Distributed under the Boost Software License, Version 1.0.
9  * (See accompanying file LICENSE_1_0.txt or copy at
10  * http://www.boost.org/LICENSE_1_0.txt)
11  **************************************************************************/
12 
13 #ifndef STXXL_PREFETCH_POOL_HEADER
14 #define STXXL_PREFETCH_POOL_HEADER
15 
16 #include <list>
17 
18 #ifdef STXXL_BOOST_CONFIG
19  #include <boost/config.hpp>
20 #endif
21 
22 #include <stxxl/bits/mng/mng.h>
23 #include <stxxl/bits/mng/write_pool.h>
24 #include <stxxl/bits/compat_hash_map.h>
25 
26 
27 __STXXL_BEGIN_NAMESPACE
28 
31 
33 template <class BlockType>
34 class prefetch_pool : private noncopyable
35 {
36 public:
37  typedef BlockType block_type;
38  typedef typename block_type::bid_type bid_type;
39 
40 protected:
41  struct bid_hash
42  {
43  size_t operator () (const bid_type & bid) const
44  {
45  size_t result = size_t(bid.storage) +
46  size_t(bid.offset & 0xffffffff) + size_t(bid.offset >> 32);
47  return result;
48  }
49 #ifdef BOOST_MSVC
50  bool operator () (const bid_type & a, const bid_type & b) const
51  {
52  return (a.storage < b.storage) || (a.storage == b.storage && a.offset < b.offset);
53  }
54  enum
55  { // parameters for hash table
56  bucket_size = 4, // 0 < bucket_size
57  min_buckets = 8 // min_buckets = 2 ^^ N, 0 < N
58  };
59 #endif
60  };
61  typedef std::pair<block_type *, request_ptr> busy_entry;
62  typedef typename compat_hash_map<bid_type, busy_entry, bid_hash>::result hash_map_type;
63  typedef typename std::list<block_type *>::iterator free_blocks_iterator;
64  typedef typename hash_map_type::iterator busy_blocks_iterator;
65 
66  // contains free prefetch blocks
67  std::list<block_type *> free_blocks;
68  // blocks that are in reading or already read but not retrieved by user
69  hash_map_type busy_blocks;
70 
71  unsigned_type free_blocks_size;
72 
73 public:
76  explicit prefetch_pool(unsigned_type init_size = 1) : free_blocks_size(init_size)
77  {
78  unsigned_type i = 0;
79  for ( ; i < init_size; ++i)
80  free_blocks.push_back(new block_type);
81  }
82 
83  void swap(prefetch_pool & obj)
84  {
85  std::swap(free_blocks, obj.free_blocks);
86  std::swap(busy_blocks, obj.busy_blocks);
87  std::swap(free_blocks_size, obj.free_blocks_size);
88  }
89 
91  virtual ~prefetch_pool()
92  {
93  while (!free_blocks.empty())
94  {
95  delete free_blocks.back();
96  free_blocks.pop_back();
97  }
98 
99  try
100  {
101  busy_blocks_iterator i2 = busy_blocks.begin();
102  for ( ; i2 != busy_blocks.end(); ++i2)
103  {
104  i2->second.second->wait();
105  delete i2->second.first;
106  }
107  }
108  catch (...)
109  { }
110  }
112  unsigned_type size() const { return free_blocks_size + busy_blocks.size(); }
113 
121  bool hint(bid_type bid)
122  {
123  // if block is already hinted, no need to hint it again
124  if (busy_blocks.find(bid) != busy_blocks.end())
125  return true;
126 
127 
128  if (free_blocks_size) // only if we have a free block
129  {
130  STXXL_VERBOSE2("prefetch_pool::hint bid= " << bid << " => prefetching");
131 
132  --free_blocks_size;
133  block_type * block = free_blocks.back();
134  free_blocks.pop_back();
135  request_ptr req = block->read(bid);
136  busy_blocks[bid] = busy_entry(block, req);
137  return true;
138  }
139  STXXL_VERBOSE2("prefetch_pool::hint bid=" << bid << " => no free blocks for prefetching");
140  return false;
141  }
142 
143  bool hint(bid_type bid, write_pool<block_type> & w_pool)
144  {
145  // if block is already hinted, no need to hint it again
146  if (busy_blocks.find(bid) != busy_blocks.end())
147  return true;
148 
149 
150  if (free_blocks_size) // only if we have a free block
151  {
152  STXXL_VERBOSE2("prefetch_pool::hint2 bid= " << bid << " => prefetching");
153  --free_blocks_size;
154  block_type * block = free_blocks.back();
155  free_blocks.pop_back();
156  request_ptr req = w_pool.get_request(bid);
157  if (req.valid())
158  {
159  block_type * w_block = w_pool.steal(bid);
160  STXXL_VERBOSE1("prefetch_pool::hint2 bid= " << bid << " was in write cache at " << w_block);
161  assert(w_block != 0);
162  w_pool.add(block); //in exchange
163  busy_blocks[bid] = busy_entry(w_block, req);
164  return true;
165  }
166  req = block->read(bid);
167  busy_blocks[bid] = busy_entry(block, req);
168  return true;
169  }
170  STXXL_VERBOSE2("prefetch_pool::hint2 bid=" << bid << " => no free blocks for prefetching");
171  return false;
172  }
173 
174  bool in_prefetching(bid_type bid)
175  {
176  return (busy_blocks.find(bid) != busy_blocks.end());
177  }
178 
185  request_ptr read(block_type * & block, bid_type bid)
186  {
187  busy_blocks_iterator cache_el = busy_blocks.find(bid);
188  if (cache_el == busy_blocks.end())
189  {
190  // not cached
191  STXXL_VERBOSE1("prefetch_pool::read bid=" << bid << " => no copy in cache, retrieving to " << block);
192  return block->read(bid);
193  }
194 
195  // cached
196  STXXL_VERBOSE1("prefetch_pool::read bid=" << bid << " => copy in cache exists");
197  ++free_blocks_size;
198  free_blocks.push_back(block);
199  block = cache_el->second.first;
200  request_ptr result = cache_el->second.second;
201  busy_blocks.erase(cache_el);
202  return result;
203  }
204 
211  unsigned_type resize(unsigned_type new_size)
212  {
213  int_type diff = int_type(new_size) - int_type(size());
214  if (diff > 0)
215  {
216  free_blocks_size += diff;
217  while (--diff >= 0)
218  free_blocks.push_back(new block_type);
219 
220 
221  return size();
222  }
223 
224  while (diff < 0 && free_blocks_size > 0)
225  {
226  ++diff;
227  --free_blocks_size;
228  delete free_blocks.back();
229  free_blocks.pop_back();
230  }
231  return size();
232  }
233 };
234 
236 
237 __STXXL_END_NAMESPACE
238 
239 namespace std
240 {
241  template <class BlockType>
242  void swap(stxxl::prefetch_pool<BlockType> & a,
243  stxxl::prefetch_pool<BlockType> & b)
244  {
245  a.swap(b);
246  }
247 }
248 
249 #endif // !STXXL_PREFETCH_POOL_HEADER