prefetch_pool.h

/***************************************************************************
 * include/stxxl/bits/mng/prefetch_pool.h
 *
 * Part of the STXXL. See http://stxxl.sourceforge.net
 *
 * Copyright (C) 2003-2004 Roman Dementiev <[email protected]>
 * Copyright (C) 2009 Andreas Beckmann <[email protected]>
 *
 * Distributed under the Boost Software License, Version 1.0.
 * (See accompanying file LICENSE_1_0.txt or copy at
 * http://www.boost.org/LICENSE_1_0.txt)
 **************************************************************************/

#ifndef STXXL_PREFETCH_POOL_HEADER
#define STXXL_PREFETCH_POOL_HEADER

#include <list>

#ifdef STXXL_BOOST_CONFIG
 #include <boost/config.hpp>
#endif

#include <stxxl/bits/mng/write_pool.h>
#include <stxxl/bits/compat_hash_map.h>


__STXXL_BEGIN_NAMESPACE


template <class BlockType>
class prefetch_pool : private noncopyable
{
public:
 typedef BlockType block_type;
 typedef typename block_type::bid_type bid_type;

protected:
 struct bid_hash
 {
 size_t operator () (const bid_type & bid) const
 {
 size_t result = size_t(bid.storage) +
 size_t(bid.offset & 0xffffffff) + size_t(bid.offset >> 32);
 return result;
 }
#ifdef BOOST_MSVC
 bool operator () (const bid_type & a, const bid_type & b) const
 {
 return (a.storage < b.storage) || (a.storage == b.storage && a.offset < b.offset);
 }
 enum
 { // parameters for hash table
 bucket_size = 4, // 0 < bucket_size
 min_buckets = 8 // min_buckets = 2 ^^ N, 0 < N
 };
#endif
 };
 typedef std::pair<block_type *, request_ptr> busy_entry;
 typedef typename compat_hash_map<bid_type, busy_entry, bid_hash>::result hash_map_type;
 typedef typename std::list<block_type *>::iterator free_blocks_iterator;
 typedef typename hash_map_type::iterator busy_blocks_iterator;

 // contains free prefetch blocks
 std::list<block_type *> free_blocks;
 // blocks that are in reading or already read but not retrieved by user
 hash_map_type busy_blocks;

 unsigned_type free_blocks_size;

public:
 explicit prefetch_pool(unsigned_type init_size = 1) : free_blocks_size(init_size)
 {
 unsigned_type i = 0;
 for ( ; i < init_size; ++i)
 free_blocks.push_back(new block_type);
 }

 void swap(prefetch_pool & obj)
 {
 std::swap(free_blocks, obj.free_blocks);
 std::swap(busy_blocks, obj.busy_blocks);
 std::swap(free_blocks_size, obj.free_blocks_size);
 }

 virtual ~prefetch_pool()
 {
 while (!free_blocks.empty())
 {
 delete free_blocks.back();
 free_blocks.pop_back();
 }

 try
 {
 busy_blocks_iterator i2 = busy_blocks.begin();
 for ( ; i2 != busy_blocks.end(); ++i2)
 {
 i2->second.second->wait();
 delete i2->second.first;
 }
 }
 catch (...)
 { }
 }
 unsigned_type size() const { return free_blocks_size + busy_blocks.size(); }

 bool hint(bid_type bid)
 {
 // if block is already hinted, no need to hint it again
 if (in_prefetching(bid)) {
 STXXL_VERBOSE2("prefetch_pool::hint2 bid=" << bid << " was already cached");
 return true;
 }

 if (free_blocks_size) // only if we have a free block
 {
 --free_blocks_size;
 block_type * block = free_blocks.back();
 free_blocks.pop_back();
 STXXL_VERBOSE2("prefetch_pool::hint bid=" << bid << " => prefetching");
 request_ptr req = block->read(bid);
 busy_blocks[bid] = busy_entry(block, req);
 return true;
 }
 STXXL_VERBOSE2("prefetch_pool::hint bid=" << bid << " => no free blocks for prefetching");
 return false;
 }

 bool hint(bid_type bid, write_pool<block_type> & w_pool)
 {
 // if block is already hinted, no need to hint it again
 if (in_prefetching(bid)) {
 STXXL_VERBOSE2("prefetch_pool::hint2 bid=" << bid << " was already cached");
 return true;
 }

 if (free_blocks_size) // only if we have a free block
 {
 --free_blocks_size;
 block_type * block = free_blocks.back();
 free_blocks.pop_back();
 if (w_pool.has_request(bid))
 {
 busy_entry wp_request = w_pool.steal_request(bid);
 STXXL_VERBOSE1("prefetch_pool::hint2 bid=" << bid << " was in write cache at " << wp_request.first);
 assert(wp_request.first != 0);
 w_pool.add(block); //in exchange
 busy_blocks[bid] = wp_request;
 return true;
 }
 STXXL_VERBOSE2("prefetch_pool::hint2 bid=" << bid << " => prefetching");
 request_ptr req = block->read(bid);
 busy_blocks[bid] = busy_entry(block, req);
 return true;
 }
 STXXL_VERBOSE2("prefetch_pool::hint2 bid=" << bid << " => no free blocks for prefetching");
 return false;
 }

 bool invalidate(bid_type bid)
 {
 busy_blocks_iterator cache_el = busy_blocks.find(bid);
 if (cache_el == busy_blocks.end())
 return false;

 // cancel request if it is a read request, there might be
 // write requests 'stolen' from a write_pool that may not be canceled
 if (cache_el->second.second->get_type() == request::READ)
 cache_el->second.second->cancel();
 // finish the request
 cache_el->second.second->wait();
 ++free_blocks_size;
 free_blocks.push_back(cache_el->second.first);
 busy_blocks.erase(cache_el);
 return true;
 }

 bool in_prefetching(bid_type bid)
 {
 return (busy_blocks.find(bid) != busy_blocks.end());
 }

 request_ptr read(block_type * & block, bid_type bid)
 {
 busy_blocks_iterator cache_el = busy_blocks.find(bid);
 if (cache_el == busy_blocks.end())
 {
 // not cached
 STXXL_VERBOSE1("prefetch_pool::read bid=" << bid << " => no copy in cache, retrieving to " << block);
 return block->read(bid);
 }

 // cached
 STXXL_VERBOSE1("prefetch_pool::read bid=" << bid << " => copy in cache exists");
 ++free_blocks_size;
 free_blocks.push_back(block);
 block = cache_el->second.first;
 request_ptr result = cache_el->second.second;
 busy_blocks.erase(cache_el);
 return result;
 }

 request_ptr read(block_type * & block, bid_type bid, write_pool<block_type> & w_pool)
 {
 // try cache
 busy_blocks_iterator cache_el = busy_blocks.find(bid);
 if (cache_el != busy_blocks.end())
 {
 // cached
 STXXL_VERBOSE1("prefetch_pool::read bid=" << bid << " => copy in cache exists");
 ++free_blocks_size;
 free_blocks.push_back(block);
 block = cache_el->second.first;
 request_ptr result = cache_el->second.second;
 busy_blocks.erase(cache_el);
 return result;
 }

 // try w_pool cache
 if (w_pool.has_request(bid))
 {
 busy_entry wp_request = w_pool.steal_request(bid);
 STXXL_VERBOSE1("prefetch_pool::read bid=" << bid << " was in write cache at " << wp_request.first);
 assert(wp_request.first != 0);
 w_pool.add(block); //in exchange
 block = wp_request.first;
 return wp_request.second;
 }

 // not cached
 STXXL_VERBOSE1("prefetch_pool::read bid=" << bid << " => no copy in cache, retrieving to " << block);
 return block->read(bid);
 }

 unsigned_type resize(unsigned_type new_size)
 {
 int_type diff = int_type(new_size) - int_type(size());
 if (diff > 0)
 {
 free_blocks_size += diff;
 while (--diff >= 0)
 free_blocks.push_back(new block_type);


 return size();
 }

 while (diff < 0 && free_blocks_size > 0)
 {
 ++diff;
 --free_blocks_size;
 delete free_blocks.back();
 free_blocks.pop_back();
 }
 return size();
 }
};


__STXXL_END_NAMESPACE

namespace std
{
 template <class BlockType>
 void swap(stxxl::prefetch_pool<BlockType> & a,
 stxxl::prefetch_pool<BlockType> & b)
 {
 a.swap(b);
 }
}

#endif // !STXXL_PREFETCH_POOL_HEADER
// vim: et:ts=4:sw=4