http://stxxl.sourceforge.net
<R-Steffen@gmx.de>
http://www.boost.org/LICENSE_1_0.txt
#ifndef STXXL_BLOCK_SCHEDULER_HEADER
#define STXXL_BLOCK_SCHEDULER_HEADER
#include <stack>
#include <queue>
#include <limits>
#include <stxxl/bits/mng/mng.h>
#include <stxxl/bits/mng/typed_block.h>
#include <stxxl/bits/common/addressable_queues.h>
__STXXL_BEGIN_NAMESPACE
template <typename ValueType, unsigned BlockSize>
class swappable_block
{
protected:
static const unsigned_type raw_block_size = BlockSize * sizeof(ValueType);
public:
typedef typed_block<raw_block_size, ValueType> internal_block_type;
typedef typename internal_block_type::bid_type external_block_type;
protected:
external_block_type external_data;
internal_block_type * internal_data;
bool dirty;
int_type reference_count;
static unsigned_type disk_allocation_offset;
void get_external_block()
{ block_manager::get_instance()->new_block(striping(), external_data, ++disk_allocation_offset); }
void free_external_block()
{
block_manager::get_instance()->delete_block(external_data);
external_data = external_block_type();
}
public:
swappable_block()
: external_data() , internal_data(0), dirty(false), reference_count(0) {}
~swappable_block() {}
bool is_internal() const
{ return internal_data; }
bool is_dirty() const
{ return dirty; }
bool has_external_block() const
{ return external_data.valid(); }
bool is_external() const
{ return has_external_block() && ! is_dirty(); }
bool is_acquired() const
{ return reference_count > 0; }
bool is_evictable() const
{ return ! is_acquired() && is_internal(); }
bool is_initialized() const
{ return is_internal() || is_external(); }
bool make_dirty_if(const bool make_dirty)
{
assert(is_acquired());
return dirty = make_dirty || dirty;
}
internal_block_type & acquire()
{
assert(is_internal());
++ reference_count;
return * internal_data;
}
void release()
{
assert(is_acquired());
-- reference_count;
}
const internal_block_type & get_internal_block() const
{
assert(is_acquired());
return * internal_data;
}
internal_block_type & get_internal_block()
{
assert(is_acquired());
return * internal_data;
}
void fill_default() {}
request_ptr read_async(completion_handler on_cmpl = default_completion_handler())
{
assert(is_internal());
assert(has_external_block());
#ifdef RW_VERBOSE
STXXL_MSG("reading block");
#endif
dirty = false;
return internal_data->read(external_data, on_cmpl);
}
void read_sync()
{ read_async()->wait(); }
request_ptr clean_async(completion_handler on_cmpl = default_completion_handler())
{
if (! is_dirty())
return request_ptr();
if (! has_external_block())
get_external_block();
#ifdef RW_VERBOSE
STXXL_MSG("writing block");
#endif
dirty = false;
return internal_data->write(external_data, on_cmpl);
}
void clean_sync()
{
request_ptr rp = clean_async();
if (rp.valid())
rp->wait();
}
void attach_internal_block(internal_block_type * iblock)
{
assert(! is_internal());
internal_data = iblock;
}
internal_block_type * detach_internal_block()
{
assert(is_evictable());
clean_sync();
internal_block_type * iblock = internal_data;
internal_data = 0;
return iblock;
}
internal_block_type * deinitialize()
{
assert(! is_acquired());
dirty = false;
if (has_external_block())
free_external_block();
internal_block_type * iblock = internal_data;
internal_data = 0;
return iblock;
}
void initialize(external_block_type eblock)
{
assert(! is_initialized());
external_data = eblock;
}
external_block_type extract_external_block()
{
assert(! is_internal());
external_block_type eblock = external_data;
external_data = external_block_type();
return eblock;
}
};
template <typename ValueType, unsigned BlockSize>
unsigned_type swappable_block<ValueType, BlockSize>::disk_allocation_offset = 0;
template <class SwappableBlockType> class block_scheduler_algorithm;
template <class SwappableBlockType> class block_scheduler_algorithm_online_lru;
template <class SwappableBlockType>
class block_scheduler : private noncopyable
{
protected:
static const int_type max_internal_blocks_alloc_at_once;
typedef int_type time_type;
public:
typedef typename SwappableBlockType::internal_block_type internal_block_type;
typedef typename SwappableBlockType::external_block_type external_block_type;
typedef typename std::vector<SwappableBlockType>::size_type swappable_block_identifier_type;
public:
enum block_scheduler_operation
{
op_acquire,
op_acquire_uninitialized,
op_release,
op_release_dirty,
op_deinitialize,
op_initialize,
op_extract_external_block
};
struct prediction_sequence_element
{
block_scheduler_operation op;
swappable_block_identifier_type id;
time_type time;
prediction_sequence_element(block_scheduler_operation op,
swappable_block_identifier_type id, int_type time)
: op(op), id(id), time(time) {}
};
typedef std::deque<prediction_sequence_element> prediction_sequence_type;
protected:
template <class SBT> friend class block_scheduler_algorithm;
const int_type max_internal_blocks;
int_type remaining_internal_blocks;
std::stack<internal_block_type *> internal_blocks_blocks;
std::stack<internal_block_type * > free_internal_blocks;
mutable std::vector<SwappableBlockType> swappable_blocks;
std::priority_queue<swappable_block_identifier_type, std::vector<swappable_block_identifier_type>,
std::greater<swappable_block_identifier_type> > free_swappable_blocks;
block_manager * bm;
block_scheduler_algorithm<SwappableBlockType> * algo;
internal_block_type * get_free_internal_block()
{
if (! free_internal_blocks.empty())
{
internal_block_type * iblock = free_internal_blocks.top();
free_internal_blocks.pop();
return iblock;
}
else if (remaining_internal_blocks > 0)
{
int_type num_blocks = std::min(max_internal_blocks_alloc_at_once, remaining_internal_blocks);
remaining_internal_blocks -= num_blocks;
internal_block_type * iblocks = new internal_block_type[num_blocks];
internal_blocks_blocks.push(iblocks);
for (int_type i = num_blocks - 1; i > 0; --i)
free_internal_blocks.push(iblocks + i);
return iblocks;
}
else
{
return 0;
}
}
void return_free_internal_block(internal_block_type * iblock)
{ free_internal_blocks.push(iblock); }
public:
explicit block_scheduler(const int_type max_internal_memory)
: max_internal_blocks(div_ceil(max_internal_memory, sizeof(internal_block_type))),
remaining_internal_blocks(max_internal_blocks),
bm(block_manager::get_instance()),
algo(0)
{ algo = new block_scheduler_algorithm_online_lru<SwappableBlockType>(*this); }
~block_scheduler()
{
delete algo;
int_type num_freed_internal_blocks = 0;
if (free_swappable_blocks.size() != swappable_blocks.size())
{
STXXL_ERRMSG("not all swappable_blocks are free, those not acquired will be deinitialized");
for (typename std::vector<SwappableBlockType>::iterator it = swappable_blocks.begin();
it != swappable_blocks.end(); ++it)
if (! it->is_acquired())
num_freed_internal_blocks += bool(it->deinitialize());
}
if (int_type nlost = (max_internal_blocks - remaining_internal_blocks)
- (free_internal_blocks.size() + num_freed_internal_blocks))
STXXL_ERRMSG(nlost << " internal_blocks are lost. They will get deallocated.");
while (! internal_blocks_blocks.empty())
{
delete [] internal_blocks_blocks.top();
internal_blocks_blocks.pop();
}
}
internal_block_type & acquire(const swappable_block_identifier_type sbid, const bool uninitialized = false)
{ return algo->acquire(sbid, uninitialized); }
void release(const swappable_block_identifier_type sbid, const bool dirty)
{ algo->release(sbid, dirty); }
void deinitialize(const swappable_block_identifier_type sbid)
{ algo->deinitialize(sbid); }
void initialize(const swappable_block_identifier_type sbid, external_block_type eblock)
{ algo->initialize(sbid, eblock); }
external_block_type extract_external_block(const swappable_block_identifier_type sbid)
{ return algo->extract_external_block(sbid); }
bool is_initialized(const swappable_block_identifier_type sbid) const
{ return algo->is_initialized(sbid); }
void explicit_timestep()
{ algo->explicit_timestep(); }
internal_block_type & get_internal_block(const swappable_block_identifier_type sbid) const
{ return swappable_blocks[sbid].get_internal_block(); }
swappable_block_identifier_type allocate_swappable_block()
{
swappable_block_identifier_type sbid;
if (free_swappable_blocks.empty())
{
sbid = swappable_blocks.size();
swappable_blocks.resize(sbid + 1);
algo->swappable_blocks_resize(sbid + 1);
}
else
{
sbid = free_swappable_blocks.top();
free_swappable_blocks.pop();
}
return sbid;
}
void free_swappable_block(const swappable_block_identifier_type sbid)
{
deinitialize(sbid);
free_swappable_blocks.push(sbid);
}
bool is_simulating() const
{ return algo->is_simulating(); }
block_scheduler_algorithm<SwappableBlockType> * switch_algorithm_to(block_scheduler_algorithm<SwappableBlockType> * new_algo)
{
assert(&new_algo->bs == this);
block_scheduler_algorithm<SwappableBlockType> * old_algo = algo;
algo = new_algo;
return old_algo;
}
const prediction_sequence_type & get_prediction_sequence() const
{ return algo->get_prediction_sequence(); }
void flush()
{
std::vector<request_ptr> requests;
while (! algo->evictable_blocks_empty())
{
swappable_block_identifier_type sbid = algo->evictable_blocks_pop();
request_ptr rq = swappable_blocks[sbid].clean_async();
if (rq.valid())
requests.push_back(rq);
return_free_internal_block(swappable_blocks[sbid].detach_internal_block());
}
for (typename std::vector<request_ptr>::reverse_iterator it = requests.rbegin();
it != requests.rend(); ++it)
(*it)->wait();
}
};
template <class SwappableBlockType>
const int_type block_scheduler<SwappableBlockType>::max_internal_blocks_alloc_at_once = 128;
template <class SwappableBlockType>
class block_scheduler_algorithm : private noncopyable
{
protected:
typedef block_scheduler<SwappableBlockType> block_scheduler_type;
typedef typename block_scheduler_type::internal_block_type internal_block_type;
typedef typename block_scheduler_type::external_block_type external_block_type;
typedef typename block_scheduler_type::swappable_block_identifier_type swappable_block_identifier_type;
typedef typename block_scheduler_type::prediction_sequence_type prediction_sequence_type;
typedef typename block_scheduler_type::time_type time_type;
public:
block_scheduler_type & bs;
protected:
std::vector<SwappableBlockType> & swappable_blocks;
prediction_sequence_type prediction_sequence;
block_scheduler_algorithm * get_algorithm_from_block_scheduler()
{ return bs.algo; }
internal_block_type * get_free_internal_block_from_block_scheduler()
{ return bs.get_free_internal_block(); }
void return_free_internal_block_to_block_scheduler(internal_block_type * iblock)
{ bs.return_free_internal_block(iblock); }
public:
block_scheduler_algorithm(block_scheduler_type & bs)
: bs(bs),
swappable_blocks(bs.swappable_blocks)
{}
block_scheduler_algorithm(block_scheduler_algorithm * old)
: bs(old->bs),
swappable_blocks(bs.swappable_blocks)
{}
virtual ~block_scheduler_algorithm() {};
virtual bool evictable_blocks_empty() = 0;
virtual swappable_block_identifier_type evictable_blocks_pop() = 0;
virtual void swappable_blocks_resize(swappable_block_identifier_type ) {}
virtual internal_block_type & acquire(const swappable_block_identifier_type sbid, const bool uninitialized = false) = 0;
virtual void release(swappable_block_identifier_type sbid, const bool dirty) = 0;
virtual void deinitialize(swappable_block_identifier_type sbid) = 0;
virtual void initialize(swappable_block_identifier_type sbid, external_block_type eblock) = 0;
virtual external_block_type extract_external_block(swappable_block_identifier_type sbid) = 0;
virtual bool is_initialized(const swappable_block_identifier_type sbid) const
{ return swappable_blocks[sbid].is_initialized(); }
virtual void explicit_timestep() {}
virtual bool is_simulating() const
{ return false; }
virtual const prediction_sequence_type & get_prediction_sequence() const
{ return prediction_sequence; }
};
template <class SwappableBlockType>
class block_scheduler_algorithm_online_lru : public block_scheduler_algorithm<SwappableBlockType>
{
protected:
typedef block_scheduler<SwappableBlockType> block_scheduler_type;
typedef block_scheduler_algorithm<SwappableBlockType> block_scheduler_algorithm_type;
typedef typename block_scheduler_type::internal_block_type internal_block_type;
typedef typename block_scheduler_type::external_block_type external_block_type;
typedef typename block_scheduler_type::swappable_block_identifier_type swappable_block_identifier_type;
using block_scheduler_algorithm_type::bs;
using block_scheduler_algorithm_type::swappable_blocks;
using block_scheduler_algorithm_type::get_algorithm_from_block_scheduler;
using block_scheduler_algorithm_type::get_free_internal_block_from_block_scheduler;
using block_scheduler_algorithm_type::return_free_internal_block_to_block_scheduler;
addressable_fifo_queue<swappable_block_identifier_type> evictable_blocks;
internal_block_type * get_free_internal_block()
{
if (internal_block_type * iblock = get_free_internal_block_from_block_scheduler())
return iblock;
assert(! evictable_blocks.empty());
return swappable_blocks[evictable_blocks.pop()].detach_internal_block();
}
void return_free_internal_block(internal_block_type * iblock)
{ return_free_internal_block_to_block_scheduler(iblock); }
void init()
{
if (get_algorithm_from_block_scheduler())
while (! get_algorithm_from_block_scheduler()->evictable_blocks_empty())
evictable_blocks.insert(get_algorithm_from_block_scheduler()->evictable_blocks_pop());
}
public:
block_scheduler_algorithm_online_lru(block_scheduler_type & bs)
: block_scheduler_algorithm_type(bs)
{ init(); }
block_scheduler_algorithm_online_lru(block_scheduler_algorithm_type * old)
: block_scheduler_algorithm_type(old)
{ init(); }
virtual ~block_scheduler_algorithm_online_lru()
{
if (! evictable_blocks.empty())
STXXL_ERRMSG("Destructing block_scheduler_algorithm_online that still holds evictable blocks. They get deinitialized.");
while (! evictable_blocks.empty())
{
SwappableBlockType & sblock = swappable_blocks[evictable_blocks.pop()];
if (internal_block_type * iblock = sblock.deinitialize())
return_free_internal_block(iblock);
}
}
virtual bool evictable_blocks_empty()
{ return evictable_blocks.empty(); }
virtual swappable_block_identifier_type evictable_blocks_pop()
{ return evictable_blocks.pop(); }
virtual internal_block_type & acquire(const swappable_block_identifier_type sbid, const bool uninitialized = false)
{
SwappableBlockType & sblock = swappable_blocks[sbid];
if (sblock.is_internal())
{
if (! sblock.is_acquired())
evictable_blocks.erase(sbid);
sblock.acquire();
}
else if (sblock.is_initialized())
{
sblock.attach_internal_block(get_free_internal_block());
if (! uninitialized)
sblock.read_sync();
sblock.acquire();
}
else
{
sblock.attach_internal_block(get_free_internal_block());
sblock.acquire();
if (! uninitialized)
sblock.fill_default();
}
return sblock.get_internal_block();
}
virtual void release(swappable_block_identifier_type sbid, const bool dirty)
{
SwappableBlockType & sblock = swappable_blocks[sbid];
sblock.make_dirty_if(dirty);
sblock.release();
if (! sblock.is_acquired())
{
if (sblock.is_dirty() || sblock.is_external())
evictable_blocks.insert(sbid);
else
return_free_internal_block(sblock.detach_internal_block());
}
}
virtual void deinitialize(swappable_block_identifier_type sbid)
{
SwappableBlockType & sblock = swappable_blocks[sbid];
if (sblock.is_evictable())
evictable_blocks.erase(sbid);
if (internal_block_type * iblock = sblock.deinitialize())
return_free_internal_block(iblock);
}
virtual void initialize(swappable_block_identifier_type sbid, external_block_type eblock)
{
SwappableBlockType & sblock = swappable_blocks[sbid];
sblock.initialize(eblock);
}
virtual external_block_type extract_external_block(swappable_block_identifier_type sbid)
{
SwappableBlockType & sblock = swappable_blocks[sbid];
if (sblock.is_evictable())
evictable_blocks.erase(sbid);
if (sblock.is_internal())
return_free_internal_block(sblock.detach_internal_block());
return sblock.extract_external_block();
}
};
template <class SwappableBlockType>
class block_scheduler_algorithm_simulation : public block_scheduler_algorithm<SwappableBlockType>
{
protected:
typedef block_scheduler<SwappableBlockType> block_scheduler_type;
typedef block_scheduler_algorithm<SwappableBlockType> block_scheduler_algorithm_type;
typedef typename block_scheduler_type::internal_block_type internal_block_type;
typedef typename block_scheduler_type::external_block_type external_block_type;
typedef typename block_scheduler_type::swappable_block_identifier_type swappable_block_identifier_type;
typedef typename block_scheduler_type::prediction_sequence_element prediction_sequence_element_type;
typedef typename block_scheduler_algorithm_type::time_type time_type;
using block_scheduler_algorithm_type::bs;
using block_scheduler_algorithm_type::prediction_sequence;
using block_scheduler_algorithm_type::swappable_blocks;
using block_scheduler_algorithm_type::get_algorithm_from_block_scheduler;
using block_scheduler_algorithm_type::get_free_internal_block_from_block_scheduler;
using block_scheduler_algorithm_type::return_free_internal_block_to_block_scheduler;
std::stack<swappable_block_identifier_type> evictable_blocks;
time_type time_count;
bool last_op_release;
std::vector<int_type> reference_counts;
internal_block_type dummy_block;
void return_free_internal_block(internal_block_type * iblock)
{ return_free_internal_block_to_block_scheduler(iblock); }
void init()
{
if (get_algorithm_from_block_scheduler())
while (! get_algorithm_from_block_scheduler()->evictable_blocks_empty())
evictable_blocks.push(get_algorithm_from_block_scheduler()->evictable_blocks_pop());
for (swappable_block_identifier_type i = 0; i < reference_counts.size(); ++i)
reference_counts[i] = swappable_blocks[i].is_initialized();
}
public:
block_scheduler_algorithm_simulation(block_scheduler_type & bs)
: block_scheduler_algorithm_type(bs),
time_count(0),
last_op_release(false),
reference_counts(swappable_blocks.size())
{ init(); }
block_scheduler_algorithm_simulation(block_scheduler_algorithm_type * old)
: block_scheduler_algorithm_type(old),
time_count(0),
last_op_release(false),
reference_counts(swappable_blocks.size())
{ init(); }
virtual ~block_scheduler_algorithm_simulation()
{
if (! evictable_blocks.empty())
STXXL_ERRMSG("Destructing block_scheduler_algorithm_record_prediction_sequence that still holds evictable blocks. They get deinitialized.");
while (! evictable_blocks.empty())
{
SwappableBlockType & sblock = swappable_blocks[evictable_blocks.top()];
if (internal_block_type * iblock = sblock.deinitialize())
return_free_internal_block(iblock);
evictable_blocks.pop();
}
}
virtual bool evictable_blocks_empty()
{ return evictable_blocks.empty(); }
virtual swappable_block_identifier_type evictable_blocks_pop()
{
swappable_block_identifier_type sbid = evictable_blocks.top();
evictable_blocks.pop();
return sbid;
}
virtual internal_block_type & acquire(const swappable_block_identifier_type sbid, const bool uninitialized = false)
{
++reference_counts[sbid];
last_op_release = false;
if (uninitialized)
prediction_sequence.push_back(prediction_sequence_element_type
(block_scheduler_type::op_acquire_uninitialized, sbid, time_count));
else
prediction_sequence.push_back(prediction_sequence_element_type
(block_scheduler_type::op_acquire, sbid, time_count));
return dummy_block;
}
virtual void release(swappable_block_identifier_type sbid, const bool dirty)
{
--reference_counts[sbid] += dirty;
time_count += ! last_op_release;
last_op_release = true;
if (dirty)
prediction_sequence.push_back(prediction_sequence_element_type
(block_scheduler_type::op_release_dirty, sbid, time_count));
else
prediction_sequence.push_back(prediction_sequence_element_type
(block_scheduler_type::op_release, sbid, time_count));
}
virtual void deinitialize(swappable_block_identifier_type sbid)
{
reference_counts[sbid] = false;
prediction_sequence.push_back(prediction_sequence_element_type
(block_scheduler_type::op_deinitialize, sbid, time_count));
}
virtual void initialize(swappable_block_identifier_type sbid, external_block_type)
{
reference_counts[sbid] = true;
prediction_sequence.push_back(prediction_sequence_element_type
(block_scheduler_type::op_initialize, sbid, time_count));
}
virtual external_block_type extract_external_block(swappable_block_identifier_type sbid)
{
reference_counts[sbid] = false;
prediction_sequence.push_back(prediction_sequence_element_type
(block_scheduler_type::op_extract_external_block, sbid, time_count));
return external_block_type();
}
virtual void swappable_blocks_resize(swappable_block_identifier_type size)
{
reference_counts.resize(size, 0);
}
virtual bool is_initialized(const swappable_block_identifier_type sbid) const
{
return reference_counts[sbid] > 0;
}
virtual void explicit_timestep()
{ ++time_count; };
virtual bool is_simulating() const
{ return true; }
};
template <class SwappableBlockType>
class block_scheduler_algorithm_offline_lfd : public block_scheduler_algorithm<SwappableBlockType>
{
protected:
typedef block_scheduler<SwappableBlockType> block_scheduler_type;
typedef block_scheduler_algorithm<SwappableBlockType> block_scheduler_algorithm_type;
typedef typename block_scheduler_type::internal_block_type internal_block_type;
typedef typename block_scheduler_type::external_block_type external_block_type;
typedef typename block_scheduler_type::swappable_block_identifier_type swappable_block_identifier_type;
typedef typename block_scheduler_algorithm_type::time_type time_type;
typedef typename block_scheduler_type::prediction_sequence_type prediction_sequence_type;
using block_scheduler_algorithm_type::bs;
using block_scheduler_algorithm_type::swappable_blocks;
using block_scheduler_algorithm_type::get_algorithm_from_block_scheduler;
using block_scheduler_algorithm_type::get_free_internal_block_from_block_scheduler;
using block_scheduler_algorithm_type::return_free_internal_block_to_block_scheduler;
class priority
{
unsigned_type p;
public:
priority(const SwappableBlockType & sblock, const std::pair<bool, time_type> & t)
{
if (t.first)
{
p = unsigned_type(t.second) << 2;
p |= unsigned_type(! sblock.is_dirty()) << 1;
p |= unsigned_type(sblock.has_external_block()) << 0;
}
else
{
p = std::numeric_limits<unsigned_type>::max() << 2;
p |= unsigned_type(t.second) << 0;
}
}
bool operator < (const priority & right) const
{ return p > right.p; }
};
addressable_priority_queue<swappable_block_identifier_type, priority> evictable_blocks;
std::deque< std::pair<bool, time_type> > next_use;
internal_block_type * get_free_internal_block()
{
if (internal_block_type * iblock = get_free_internal_block_from_block_scheduler())
return iblock;
assert(! evictable_blocks.empty());
return swappable_blocks[evictable_blocks.pop()].detach_internal_block();
}
void return_free_internal_block(internal_block_type * iblock)
{ return_free_internal_block_to_block_scheduler(iblock); }
void init(block_scheduler_algorithm_type * old_algo)
{
std::vector< std::pair<bool, time_type> >
blocks_next_acquire(swappable_blocks.size(), std::make_pair(false, 1));
if(old_algo)
{
const prediction_sequence_type & ps = old_algo->get_prediction_sequence();
for (typename prediction_sequence_type::const_reverse_iterator it = ps.rbegin(); it != ps.rend(); ++it)
switch (it->op)
{
case (block_scheduler_type::op_acquire):
case (block_scheduler_type::op_acquire_uninitialized):
blocks_next_acquire[it->id] = std::make_pair(true, it->time);
break;
case (block_scheduler_type::op_release):
case (block_scheduler_type::op_release_dirty):
next_use.push_front(blocks_next_acquire[it->id]);
break;
case (block_scheduler_type::op_deinitialize):
blocks_next_acquire[it->id] = std::make_pair(false, 0);
break;
case (block_scheduler_type::op_initialize):
blocks_next_acquire[it->id] = std::make_pair(false, 3);
break;
case (block_scheduler_type::op_extract_external_block):
blocks_next_acquire[it->id] = std::make_pair(false, 2);
break;
}
}
if (get_algorithm_from_block_scheduler())
{
while (! get_algorithm_from_block_scheduler()->evictable_blocks_empty())
{
const swappable_block_identifier_type sbid = get_algorithm_from_block_scheduler()->evictable_blocks_pop();
evictable_blocks.insert(sbid, priority(swappable_blocks[sbid], blocks_next_acquire[sbid]));
}
}
}
public:
block_scheduler_algorithm_offline_lfd(block_scheduler_type & bs)
: block_scheduler_algorithm_type(bs)
{ init(get_algorithm_from_block_scheduler()); }
block_scheduler_algorithm_offline_lfd(block_scheduler_algorithm_type * old)
: block_scheduler_algorithm_type(old)
{ init(old); }
virtual ~block_scheduler_algorithm_offline_lfd()
{
if (! evictable_blocks.empty())
STXXL_ERRMSG("Destructing block_scheduler_algorithm_offline_lfd that still holds evictable blocks. They get deinitialized.");
while (! evictable_blocks.empty())
{
SwappableBlockType & sblock = swappable_blocks[evictable_blocks.pop()];
if (internal_block_type * iblock = sblock.deinitialize())
return_free_internal_block(iblock);
}
}
virtual bool evictable_blocks_empty()
{ return evictable_blocks.empty(); }
virtual swappable_block_identifier_type evictable_blocks_pop()
{ return evictable_blocks.pop(); }
virtual internal_block_type & acquire(const swappable_block_identifier_type sbid, const bool uninitialized = false)
{
SwappableBlockType & sblock = swappable_blocks[sbid];
if (sblock.is_internal())
{
if (! sblock.is_acquired())
evictable_blocks.erase(sbid);
sblock.acquire();
}
else if (sblock.is_initialized())
{
sblock.attach_internal_block(get_free_internal_block());
if (! uninitialized)
sblock.read_sync();
sblock.acquire();
}
else
{
sblock.attach_internal_block(get_free_internal_block());
sblock.acquire();
if (! uninitialized)
sblock.fill_default();
}
return sblock.get_internal_block();
}
virtual void release(swappable_block_identifier_type sbid, const bool dirty)
{
if (next_use.empty())
{
STXXL_ERRMSG("block_scheduler_algorithm_offline_lfd got release-request but prediction sequence ended. Switching to block_scheduler_algorithm_online.");
block_scheduler_algorithm_type * new_algo,
* old_algo;
new_algo = new block_scheduler_algorithm_online_lru<SwappableBlockType>(bs);
old_algo = bs.switch_algorithm_to(new_algo);
new_algo->release(sbid, dirty);
delete old_algo;
return;
}
SwappableBlockType & sblock = swappable_blocks[sbid];
sblock.make_dirty_if(dirty);
sblock.release();
if (! sblock.is_acquired())
{
if (sblock.is_dirty() || sblock.is_external())
evictable_blocks.insert(sbid, priority(swappable_blocks[sbid], next_use.front()));
else
return_free_internal_block(sblock.detach_internal_block());
}
next_use.pop_front();
}
virtual void deinitialize(swappable_block_identifier_type sbid)
{
SwappableBlockType & sblock = swappable_blocks[sbid];
if (sblock.is_evictable())
evictable_blocks.erase(sbid);
if (internal_block_type * iblock = sblock.deinitialize())
return_free_internal_block(iblock);
}
virtual void initialize(swappable_block_identifier_type sbid, external_block_type eblock)
{
SwappableBlockType & sblock = swappable_blocks[sbid];
sblock.initialize(eblock);
}
virtual external_block_type extract_external_block(swappable_block_identifier_type sbid)
{
SwappableBlockType & sblock = swappable_blocks[sbid];
if (sblock.is_evictable())
evictable_blocks.erase(sbid);
if (sblock.is_internal())
return_free_internal_block(sblock.detach_internal_block());
return sblock.extract_external_block();
}
};
template <class SwappableBlockType>
class block_scheduler_algorithm_offline_lru_prefetching : public block_scheduler_algorithm<SwappableBlockType>
{
protected:
struct scheduled_block_meta;
struct write_read_request;
typedef block_scheduler<SwappableBlockType> block_scheduler_type;
typedef block_scheduler_algorithm<SwappableBlockType> block_scheduler_algorithm_type;
typedef typename block_scheduler_type::internal_block_type internal_block_type;
typedef typename block_scheduler_type::external_block_type external_block_type;
typedef typename block_scheduler_type::swappable_block_identifier_type swappable_block_identifier_type;
typedef typename block_scheduler_algorithm_type::time_type time_type;
typedef typename block_scheduler_type::prediction_sequence_type prediction_sequence_type;
typedef typename block_scheduler_type::block_scheduler_operation block_scheduler_operation;
typedef typename std::vector<SwappableBlockType>::iterator swappable_blocks_iterator;
typedef std::map<swappable_block_identifier_type, scheduled_block_meta> scheduled_blocks_type;
typedef typename scheduled_blocks_type::iterator scheduled_blocks_iterator;
typedef typename scheduled_blocks_type::reference scheduled_blocks_reference;
typedef std::map<swappable_block_identifier_type, write_read_request *> write_scheduled_blocks_type;
typedef typename write_scheduled_blocks_type::iterator write_scheduled_blocks_iterator;
typedef typename write_scheduled_blocks_type::reference write_scheduled_blocks_reference;
using block_scheduler_algorithm_type::bs;
using block_scheduler_algorithm_type::swappable_blocks;
using block_scheduler_algorithm_type::get_algorithm_from_block_scheduler;
using block_scheduler_algorithm_type::get_free_internal_block_from_block_scheduler;
using block_scheduler_algorithm_type::return_free_internal_block_to_block_scheduler;
using block_scheduler_algorithm_type::prediction_sequence;
struct write_read_request
{
bool write_done_soon;
bool shall_read;
swappable_blocks_iterator block_to_start_read;
scheduled_blocks_iterator taker;
request_ptr write_req;
write_read_request()
: write_done_soon(false), shall_read(false), block_to_start_read(), taker(), write_req(0) {}
};
struct read_after_write
{
write_read_request * wrr;
read_after_write(write_read_request * write_read_req)
: wrr(write_read_req) {}
void operator () (request *)
{
wrr->write_done_soon = true;
if (wrr->shall_read)
wrr->taker->second.read_req = wrr->block_to_start_read->read_async();
}
};
struct scheduled_block_meta
{
internal_block_type * reserved_iblock;
std::pair<bool, swappable_block_identifier_type> giver;
request_ptr read_req;
std::deque<block_scheduler_operation> operations;
scheduled_block_meta(block_scheduler_operation op)
: reserved_iblock(0),
giver(false, 0),
read_req(0),
operations()
{ operations.push_front(op); }
};
std::set<swappable_block_identifier_type> free_evictable_blocks;
std::set<swappable_block_identifier_type> scheduled_evictable_blocks;
scheduled_blocks_type scheduled_blocks;
write_scheduled_blocks_type write_scheduled_blocks;
typename prediction_sequence_type::iterator next_op_to_schedule;
write_read_request * schedule_write(const swappable_block_identifier_type sbid)
{
SwappableBlockType & sblock = swappable_blocks[sbid];
write_read_request * wrr = new write_read_request;
wrr->write_req = sblock.clean_async(read_after_write(wrr));
if (wrr->write_req.valid())
{
bool t = write_scheduled_blocks.insert(std::make_pair(sbid, wrr)).second;
assert(t);
return wrr;
}
else
{
delete wrr;
return 0;
}
}
bool try_interrupt_read(const write_scheduled_blocks_iterator & writing_block)
{
writing_block->second->shall_read = false;
if (! writing_block->second->write_done_soon)
return true;
scheduled_blocks_reference taker = *writing_block->second->taker;
wait_on_write(writing_block);
if (taker.second.read_req.valid())
return false;
else
return true;
}
void schedule_read(scheduled_blocks_iterator block_to_read)
{
write_scheduled_blocks_iterator it = write_scheduled_blocks.find(block_to_read->first);
if (it != write_scheduled_blocks.end())
{
scheduled_blocks_iterator other_block_to_read = it->second->taker;
if (it->second->shall_read)
{
if (try_interrupt_read(it))
{
std::swap(other_block_to_read->second.giver, block_to_read->second.giver);
if (other_block_to_read->second.giver.first)
{
write_scheduled_blocks_iterator it = write_scheduled_blocks.find(other_block_to_read->second.giver.second);
if (it != write_scheduled_blocks.end())
it->second->taker = other_block_to_read;
else
other_block_to_read->second.giver.first = false;
}
if (block_to_read->second.giver.first)
{
write_scheduled_blocks_iterator it = write_scheduled_blocks.find(block_to_read->second.giver.second);
if (it != write_scheduled_blocks.end())
it->second->taker = block_to_read;
else
block_to_read->second.giver.first = false;
}
internal_block_type * tmp_iblock = swappable_blocks[block_to_read->first].detach_internal_block();
swappable_blocks[block_to_read->first].attach_internal_block(
swappable_blocks[other_block_to_read->first].detach_internal_block());
swappable_blocks[other_block_to_read->first].attach_internal_block(tmp_iblock);
schedule_read(other_block_to_read);
return;
}
}
else
{
std::swap(other_block_to_read->second.giver, block_to_read->second.giver);
if (other_block_to_read->second.giver.first)
{
write_scheduled_blocks_iterator it = write_scheduled_blocks.find(other_block_to_read->second.giver.second);
if (it != write_scheduled_blocks.end())
it->second->taker = other_block_to_read;
else
other_block_to_read->second.giver.first = false;
}
if (block_to_read->second.giver.first)
{
write_scheduled_blocks_iterator it = write_scheduled_blocks.find(block_to_read->second.giver.second);
if (it != write_scheduled_blocks.end())
it->second->taker = block_to_read;
else
block_to_read->second.giver.first = false;
}
internal_block_type * tmp_iblock = swappable_blocks[block_to_read->first].detach_internal_block();
swappable_blocks[block_to_read->first].attach_internal_block(
other_block_to_read->second.reserved_iblock);
other_block_to_read->second.reserved_iblock = tmp_iblock;
return;
}
}
if (block_to_read->second.giver.first)
{
write_scheduled_blocks_iterator writing_block = write_scheduled_blocks.find(block_to_read->second.giver.second);
if (writing_block != write_scheduled_blocks.end())
{
writing_block->second->block_to_start_read = swappable_blocks.begin() + block_to_read->first;
writing_block->second->taker = block_to_read;
writing_block->second->shall_read = true;
if (writing_block->second->write_done_soon)
{
wait_on_write(writing_block);
block_to_read->second.giver.first = false;
if (block_to_read->second.read_req.valid())
return;
}
else
return;
}
else
block_to_read->second.giver.first = false;
}
block_to_read->second.read_req = swappable_blocks[block_to_read->first].read_async();
}
void wait_on_write(const write_scheduled_blocks_iterator & writing_block)
{
writing_block->second->write_req->wait();
delete writing_block->second;
write_scheduled_blocks.erase(writing_block);
}
void wait_on_write(const swappable_block_identifier_type & writing_block)
{
write_scheduled_blocks_iterator it = write_scheduled_blocks.find(writing_block);
if (it != write_scheduled_blocks.end())
wait_on_write(it);
}
void wait_on_write(const scheduled_blocks_iterator & schedule_meta)
{
if (schedule_meta->second.giver.first)
{
wait_on_write(schedule_meta->second.giver.second);
schedule_meta->second.giver.first = false;
}
}
void wait_on_read(const scheduled_blocks_iterator & schedule_meta)
{
wait_on_write(schedule_meta);
if (schedule_meta->second.read_req.valid())
{
schedule_meta->second.read_req->wait();
schedule_meta->second.read_req = 0;
}
}
internal_block_type * get_ready_block(const scheduled_blocks_iterator & schedule_meta)
{
wait_on_write(schedule_meta);
internal_block_type * r = schedule_meta->second.reserved_iblock;
schedule_meta->second.reserved_iblock = 0;
return r;
}
bool shall_keep_internal_block(const scheduled_blocks_iterator & schedule_meta, const bool ignore_first = true) const
{
for (typename std::deque<block_scheduler_operation>::reverse_iterator
rit = schedule_meta->second.operations.rbegin() + ignore_first;
rit != schedule_meta->second.operations.rend(); ++rit)
switch (*rit)
{
case block_scheduler_type::op_acquire:
case block_scheduler_type::op_acquire_uninitialized:
return true; break;
case block_scheduler_type::op_release:
case block_scheduler_type::op_release_dirty:
break;
case block_scheduler_type::op_deinitialize:
if (swappable_blocks[schedule_meta->first].is_dirty()) return true; break;
case block_scheduler_type::op_initialize:
case block_scheduler_type::op_extract_external_block:
break;
}
return false;
}
bool shall_be_cleaned(const scheduled_blocks_iterator & schedule_meta) const
{
for (typename std::deque<block_scheduler_operation>::reverse_iterator
rit = schedule_meta->second.operations.rbegin() + 1;
rit != schedule_meta->second.operations.rend(); ++rit)
switch (*rit)
{
case block_scheduler_type::op_acquire:
case block_scheduler_type::op_acquire_uninitialized:
case block_scheduler_type::op_release:
break;
case block_scheduler_type::op_release_dirty:
case block_scheduler_type::op_deinitialize:
case block_scheduler_type::op_initialize:
return false; break;
case block_scheduler_type::op_extract_external_block:
return true; break;
}
return false;
}
bool shall_be_read(const scheduled_blocks_iterator & schedule_meta, const bool ignore_first = true) const
{
return swappable_blocks[schedule_meta->first].is_initialized()
&& schedule_meta->second.operations.rbegin() + ignore_first != schedule_meta->second.operations.rend()
&& *(schedule_meta->second.operations.rbegin() + ignore_first) == block_scheduler_type::op_acquire;
}
void operation_done(scheduled_blocks_iterator & schedule_meta)
{
schedule_meta->second.operations.pop_back();
if (schedule_meta->second.operations.empty())
{
assert(! schedule_meta->second.giver.first);
scheduled_blocks.erase(schedule_meta);
}
}
block_scheduler_algorithm_type * give_up(std::string err_msg = "detected some error in the prediction sequence")
{
STXXL_ERRMSG("block_scheduler_algorithm_offline_lru_prefetching: " << err_msg << ". Switching to block_scheduler_algorithm_online.");
block_scheduler_algorithm_type * new_algo
= new block_scheduler_algorithm_online_lru<SwappableBlockType>(bs);
delete bs.switch_algorithm_to(new_algo);
return new_algo;
}
void return_free_internal_block(internal_block_type * iblock)
{ return_free_internal_block_to_block_scheduler(iblock); }
void schedule_next_operations()
{
while (next_op_to_schedule != prediction_sequence.end())
{
std::pair<scheduled_blocks_iterator, bool> ins_res = scheduled_blocks.insert(
std::make_pair(next_op_to_schedule->id, next_op_to_schedule->op));
scheduled_blocks_iterator schedule_meta = ins_res.first;
if (! ins_res.second)
schedule_meta->second.operations.push_front(next_op_to_schedule->op);
SwappableBlockType & sblock = swappable_blocks[next_op_to_schedule->id];
if (next_op_to_schedule->op == block_scheduler_type::op_acquire
|| next_op_to_schedule->op == block_scheduler_type::op_acquire_uninitialized)
{
if (sblock.is_internal())
{
if (free_evictable_blocks.erase(next_op_to_schedule->id))
scheduled_evictable_blocks.insert(next_op_to_schedule->id);
}
else
if (! schedule_meta->second.reserved_iblock)
{
if (! (schedule_meta->second.reserved_iblock = get_free_internal_block_from_block_scheduler()))
{
if (free_evictable_blocks.empty())
{
if (ins_res.second)
scheduled_blocks.erase(ins_res.first);
else
schedule_meta->second.operations.pop_front();
return;
}
swappable_block_identifier_type giver = pop_begin(free_evictable_blocks);
{
scheduled_blocks_iterator giver_meta;
assert((giver_meta = scheduled_blocks.find(giver)) == scheduled_blocks.end()
|| ! shall_keep_internal_block(giver_meta, false));
}
write_read_request * wrr = schedule_write(giver);
schedule_meta->second.giver.first = bool(wrr);
schedule_meta->second.giver.second = giver;
schedule_meta->second.reserved_iblock = swappable_blocks[giver].detach_internal_block();
if (wrr)
wrr->taker = schedule_meta;
}
if (shall_be_read(schedule_meta, false))
{
sblock.attach_internal_block(schedule_meta->second.reserved_iblock);
schedule_meta->second.reserved_iblock = 0;
scheduled_evictable_blocks.insert(next_op_to_schedule->id);
schedule_read(schedule_meta);
}
}
}
else if (next_op_to_schedule->op == block_scheduler_type::op_deinitialize)
{
if (sblock.is_dirty())
if (free_evictable_blocks.erase(next_op_to_schedule->id))
scheduled_evictable_blocks.insert(next_op_to_schedule->id);
}
++ next_op_to_schedule;
}
for (typename std::set<swappable_block_identifier_type>::iterator it = free_evictable_blocks.begin();
it != free_evictable_blocks.end(); ++it)
if (! write_scheduled_blocks.count(*it))
schedule_write(*it);
}
void init(block_scheduler_algorithm_type * old_algo)
{
if(old_algo)
prediction_sequence = old_algo->get_prediction_sequence();
next_op_to_schedule = prediction_sequence.begin();
if (get_algorithm_from_block_scheduler())
while (! get_algorithm_from_block_scheduler()->evictable_blocks_empty())
free_evictable_blocks.insert(get_algorithm_from_block_scheduler()->evictable_blocks_pop());
schedule_next_operations();
}
void deinit()
{
if (! scheduled_blocks.empty())
STXXL_MSG("deinit while scheduled_blocks not empty");
if (! scheduled_evictable_blocks.empty())
STXXL_MSG("deinit while scheduled_evictable_blocks not empty");
free_evictable_blocks.insert(scheduled_evictable_blocks.begin(), scheduled_evictable_blocks.end());
scheduled_evictable_blocks.clear();
while (! scheduled_blocks.empty())
{
scheduled_blocks_iterator it = scheduled_blocks.begin();
wait_on_read(it);
if (it->second.reserved_iblock)
return_free_internal_block(it->second.reserved_iblock);
scheduled_blocks.erase(it);
}
while (! write_scheduled_blocks.empty())
{
write_scheduled_blocks_iterator it = write_scheduled_blocks.begin();
wait_on_write(it);
}
}
public:
block_scheduler_algorithm_offline_lru_prefetching(block_scheduler_type & bs)
: block_scheduler_algorithm_type(bs)
{ init(get_algorithm_from_block_scheduler()); }
block_scheduler_algorithm_offline_lru_prefetching(block_scheduler_algorithm_type * old)
: block_scheduler_algorithm_type(old)
{ init(old); }
virtual ~block_scheduler_algorithm_offline_lru_prefetching()
{
deinit();
if (! free_evictable_blocks.empty())
STXXL_ERRMSG("Destructing block_scheduler_algorithm_offline_lru_prefetching that still holds evictable blocks. They get deinitialized.");
while (! free_evictable_blocks.empty())
{
SwappableBlockType & sblock = swappable_blocks[pop_begin(free_evictable_blocks)];
if (internal_block_type * iblock = sblock.deinitialize())
return_free_internal_block(iblock);
}
}
virtual bool evictable_blocks_empty()
{
deinit();
return free_evictable_blocks.empty();
}
virtual swappable_block_identifier_type evictable_blocks_pop()
{ return pop_begin(free_evictable_blocks); }
virtual internal_block_type & acquire(const swappable_block_identifier_type sbid, const bool uninitialized = false)
{
assert(! prediction_sequence.empty());
assert(prediction_sequence.front().op ==
((uninitialized) ? block_scheduler_type::op_acquire_uninitialized : block_scheduler_type::op_acquire));
assert(prediction_sequence.front().id == sbid);
prediction_sequence.pop_front();
scheduled_blocks_iterator schedule_meta = scheduled_blocks.find(sbid);
assert(schedule_meta != scheduled_blocks.end());
assert(schedule_meta->second.operations.back() ==
((uninitialized) ? block_scheduler_type::op_acquire_uninitialized : block_scheduler_type::op_acquire));
SwappableBlockType & sblock = swappable_blocks[sbid];
if (sblock.is_internal())
{
if (! sblock.is_acquired())
{
bool t = scheduled_evictable_blocks.erase(sbid);
assert(t);
wait_on_read(schedule_meta);
}
sblock.acquire();
}
else
{
assert(uninitialized || ! sblock.is_initialized());
sblock.attach_internal_block(get_ready_block(schedule_meta));
sblock.acquire();
if (! uninitialized)
sblock.fill_default();
}
operation_done(schedule_meta);
return sblock.get_internal_block();
}
virtual void release(swappable_block_identifier_type sbid, const bool dirty)
{
assert(! prediction_sequence.empty());
assert(prediction_sequence.front().op ==
((dirty) ? block_scheduler_type::op_release_dirty : block_scheduler_type::op_release));
assert(prediction_sequence.front().id == sbid);
prediction_sequence.pop_front();
scheduled_blocks_iterator schedule_meta = scheduled_blocks.find(sbid);
assert(schedule_meta != scheduled_blocks.end());
assert(schedule_meta->second.operations.back() ==
((dirty) ? block_scheduler_type::op_release_dirty : block_scheduler_type::op_release));
SwappableBlockType & sblock = swappable_blocks[sbid];
sblock.make_dirty_if(dirty);
sblock.release();
if (! sblock.is_acquired())
{
if (sblock.is_dirty() || sblock.is_external())
{
if (shall_keep_internal_block(schedule_meta))
{
scheduled_evictable_blocks.insert(sbid);
if (shall_be_cleaned(schedule_meta))
schedule_write(sbid);
}
else
{
free_evictable_blocks.insert(sbid);
if (next_op_to_schedule != prediction_sequence.end())
schedule_next_operations();
else
if (! write_scheduled_blocks.count(sbid))
schedule_write(sbid);
}
}
else
{
if (shall_keep_internal_block(schedule_meta))
schedule_meta->second.reserved_iblock = sblock.detach_internal_block();
else
{
return_free_internal_block(sblock.detach_internal_block());
if (next_op_to_schedule != prediction_sequence.end())
schedule_next_operations();
}
}
}
operation_done(schedule_meta);
}
virtual void deinitialize(swappable_block_identifier_type sbid)
{
assert(! prediction_sequence.empty());
assert(prediction_sequence.front().op == block_scheduler_type::op_deinitialize);
assert(prediction_sequence.front().id == sbid);
prediction_sequence.pop_front();
scheduled_blocks_iterator schedule_meta = scheduled_blocks.find(sbid);
assert(schedule_meta != scheduled_blocks.end());
assert(schedule_meta->second.operations.back() == block_scheduler_type::op_deinitialize);
SwappableBlockType & sblock = swappable_blocks[sbid];
if (sblock.is_evictable())
{
bool t;
if (shall_keep_internal_block(schedule_meta, false))
{
if (! (t = scheduled_evictable_blocks.erase(sbid)))
{
STXXL_ERRMSG("dirty block not scheduled on deinitialize");
t = free_evictable_blocks.erase(sbid);
}
}
else
t = free_evictable_blocks.erase(sbid);
assert(t);
}
if (internal_block_type * iblock = sblock.deinitialize())
{
if (shall_keep_internal_block(schedule_meta))
schedule_meta->second.reserved_iblock = iblock;
else
{
return_free_internal_block(iblock);
if (next_op_to_schedule != prediction_sequence.end())
schedule_next_operations();
}
}
operation_done(schedule_meta);
}
virtual void initialize(swappable_block_identifier_type sbid, external_block_type eblock)
{
assert(! prediction_sequence.empty());
assert(prediction_sequence.front().op == block_scheduler_type::op_initialize);
assert(prediction_sequence.front().id == sbid);
prediction_sequence.pop_front();
scheduled_blocks_iterator schedule_meta = scheduled_blocks.find(sbid);
assert(schedule_meta != scheduled_blocks.end());
assert(schedule_meta->second.operations.back() == block_scheduler_type::op_initialize);
SwappableBlockType & sblock = swappable_blocks[sbid];
sblock.initialize(eblock);
if (shall_be_read(schedule_meta))
{
sblock.attach_internal_block(schedule_meta->second.reserved_iblock);
schedule_meta->second.reserved_iblock = 0;
scheduled_evictable_blocks.insert(sbid);
schedule_read(schedule_meta);
}
operation_done(schedule_meta);
}
virtual external_block_type extract_external_block(swappable_block_identifier_type sbid)
{
assert(! prediction_sequence.empty());
assert(prediction_sequence.front().op == block_scheduler_type::op_extract_external_block);
assert(prediction_sequence.front().id == sbid);
prediction_sequence.pop_front();
scheduled_blocks_iterator schedule_meta = scheduled_blocks.find(sbid);
assert(schedule_meta != scheduled_blocks.end());
assert(schedule_meta->second.operations.back() == block_scheduler_type::op_extract_external_block);
SwappableBlockType & sblock = swappable_blocks[sbid];
wait_on_write(sbid);
operation_done(schedule_meta);
return sblock.extract_external_block();
}
};
__STXXL_END_NAMESPACE
#endif