00001
00002
00003
00004
00005
00006
00007
00008
00009
00010
00011
00012
00013 #ifndef STXXL_PAGER_HEADER
00014 #define STXXL_PAGER_HEADER
00015
00016 #include <list>
00017
00018 #include <stxxl/bits/noncopyable.h>
00019 #include <stxxl/bits/common/rand.h>
00020 #include <stxxl/bits/common/simple_vector.h>
00021 #include <stxxl/bits/compat_auto_ptr.h>
00022
00023
00024 __STXXL_BEGIN_NAMESPACE
00025
00028
00029 enum pager_type
00030 {
00031 random,
00032 lru
00033 };
00034
00036 template <unsigned npages_>
00037 class random_pager
00038 {
00039 random_number<random_uniform_fast> rnd;
00040
00041 public:
00042 enum { n_pages = npages_ };
00043 random_pager() { }
00044 ~random_pager() { }
00045 int_type kick()
00046 {
00047 return rnd(npages_);
00048 }
00049 void hit(int_type ipage)
00050 {
00051 assert(ipage < int_type(npages_));
00052 assert(ipage >= 0);
00053 }
00054 };
00055
00057 template <unsigned npages_>
00058 class lru_pager : private noncopyable
00059 {
00060 typedef std::list<int_type> list_type;
00061
00062 compat_auto_ptr<list_type>::result history;
00063 simple_vector<list_type::iterator> history_entry;
00064
00065 public:
00066 enum { n_pages = npages_ };
00067
00068 lru_pager() : history(new list_type), history_entry(npages_)
00069 {
00070 for (unsigned_type i = 0; i < npages_; i++)
00071 history_entry[i] = history->insert(history->end(), static_cast<int_type>(i));
00072 }
00073 ~lru_pager() { }
00074 int_type kick()
00075 {
00076 return history->back();
00077 }
00078 void hit(int_type ipage)
00079 {
00080 assert(ipage < int_type(npages_));
00081 assert(ipage >= 0);
00082 history->splice(history->begin(), *history, history_entry[ipage]);
00083 }
00084 void swap(lru_pager & obj)
00085 {
00086
00087
00088 compat_auto_ptr<list_type>::result tmp = obj.history;
00089 obj.history = history;
00090 history = tmp;
00091 std::swap(history_entry, obj.history_entry);
00092 }
00093 };
00094
00096
00097 __STXXL_END_NAMESPACE
00098
00099 namespace std
00100 {
00101 template <unsigned npages_>
00102 void swap(stxxl::lru_pager<npages_> & a,
00103 stxxl::lru_pager<npages_> & b)
00104 {
00105 a.swap(b);
00106 }
00107 }
00108
00109 #endif // !STXXL_PAGER_HEADER