pager.h

/***************************************************************************
 *  include/stxxl/bits/containers/pager.h
 *
 *  Part of the STXXL. See http://stxxl.sourceforge.net
 *
 *  Copyright (C) 2002, 2003, 2006 Roman Dementiev <[email protected]>
 *  Copyright (C) 2011 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_PAGER_HEADER
#define STXXL_PAGER_HEADER

#include <list>
#include <cassert>

#include <stxxl/bits/noncopyable.h>
#include <stxxl/bits/common/rand.h>
#include <stxxl/bits/common/simple_vector.h>


__STXXL_BEGIN_NAMESPACE


enum pager_type
{
    random,
    lru
};

template <unsigned npages_>
class random_pager
{
    random_number<random_uniform_fast> rnd;

public:
    enum { n_pages = npages_ };
    random_pager() { }
    int_type kick()
    {
        return rnd(npages_);
    }
    void hit(int_type ipage)
    {
        assert(ipage < int_type(npages_));
        assert(ipage >= 0);
    }
};

template <unsigned npages_ = 0>
class lru_pager : private noncopyable
{
    typedef unsigned_type size_type;
    typedef std::list<size_type> list_type;

    list_type history;
    simple_vector<list_type::iterator> history_entry;

public:
    enum { n_pages = npages_ };

    lru_pager() : history_entry(n_pages)
    {
        for (size_type i = 0; i < n_pages; ++i)
            history_entry[i] = history.insert(history.end(), i);
    }

    size_type kick()
    {
        return history.back();
    }

    void hit(size_type ipage)
    {
        assert(ipage < n_pages);
        history.splice(history.begin(), history, history_entry[ipage]);
    }

    void swap(lru_pager & obj)
    {
        history.swap(obj.history);
        history_entry.swap(obj.history_entry);
    }
};

// specialization, size is specified at runtime
template <>
class lru_pager<0> : private noncopyable
{
    typedef unsigned_type size_type;
    typedef std::list<size_type> list_type;

    size_type n_pages;
    list_type history;
    simple_vector<list_type::iterator> history_entry;

public:
    lru_pager(size_type npages_ = 0) : n_pages(npages_), history_entry(n_pages)
    {
        for (size_type i = 0; i < n_pages; ++i)
            history_entry[i] = history.insert(history.end(), i);
    }

    size_type kick()
    {
        return history.back();
    }

    void hit(size_type ipage)
    {
        assert(ipage < n_pages);
        history.splice(history.begin(), history, history_entry[ipage]);
    }

    void swap(lru_pager & obj)
    {
        std::swap(n_pages, obj.n_pages);
        history.swap(obj.history);
        history_entry.swap(obj.history_entry);
    }
};


__STXXL_END_NAMESPACE

namespace std
{
    template <unsigned npages_>
    void swap(stxxl::lru_pager<npages_> & a,
              stxxl::lru_pager<npages_> & b)
    {
        a.swap(b);
    }
}

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