Stxxl
1.3.1
|
00001 /*************************************************************************** 00002 * include/stxxl/bits/containers/pager.h 00003 * 00004 * Part of the STXXL. See http://stxxl.sourceforge.net 00005 * 00006 * Copyright (C) 2002, 2003, 2006 Roman Dementiev <dementiev@ira.uka.de> 00007 * Copyright (C) 2011 Andreas Beckmann <beckmann@cs.uni-frankfurt.de> 00008 * 00009 * Distributed under the Boost Software License, Version 1.0. 00010 * (See accompanying file LICENSE_1_0.txt or copy at 00011 * http://www.boost.org/LICENSE_1_0.txt) 00012 **************************************************************************/ 00013 00014 #ifndef STXXL_PAGER_HEADER 00015 #define STXXL_PAGER_HEADER 00016 00017 #include <list> 00018 #include <cassert> 00019 00020 #include <stxxl/bits/noncopyable.h> 00021 #include <stxxl/bits/common/rand.h> 00022 #include <stxxl/bits/common/simple_vector.h> 00023 00024 00025 __STXXL_BEGIN_NAMESPACE 00026 00029 00030 enum pager_type 00031 { 00032 random, 00033 lru 00034 }; 00035 00037 template <unsigned npages_> 00038 class random_pager 00039 { 00040 random_number<random_uniform_fast> rnd; 00041 00042 public: 00043 enum { n_pages = npages_ }; 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_ = 0> 00058 class lru_pager : private noncopyable 00059 { 00060 typedef unsigned_type size_type; 00061 typedef std::list<size_type> list_type; 00062 00063 list_type history; 00064 simple_vector<list_type::iterator> history_entry; 00065 00066 public: 00067 enum { n_pages = npages_ }; 00068 00069 lru_pager() : history_entry(n_pages) 00070 { 00071 for (size_type i = 0; i < n_pages; ++i) 00072 history_entry[i] = history.insert(history.end(), i); 00073 } 00074 00075 size_type kick() 00076 { 00077 return history.back(); 00078 } 00079 00080 void hit(size_type ipage) 00081 { 00082 assert(ipage < n_pages); 00083 history.splice(history.begin(), history, history_entry[ipage]); 00084 } 00085 00086 void swap(lru_pager & obj) 00087 { 00088 history.swap(obj.history); 00089 history_entry.swap(obj.history_entry); 00090 } 00091 }; 00092 00093 // specialization, size is specified at runtime 00094 template <> 00095 class lru_pager<0> : private noncopyable 00096 { 00097 typedef unsigned_type size_type; 00098 typedef std::list<size_type> list_type; 00099 00100 size_type n_pages; 00101 list_type history; 00102 simple_vector<list_type::iterator> history_entry; 00103 00104 public: 00105 lru_pager(size_type npages_ = 0) : n_pages(npages_), history_entry(n_pages) 00106 { 00107 for (size_type i = 0; i < n_pages; ++i) 00108 history_entry[i] = history.insert(history.end(), i); 00109 } 00110 00111 size_type kick() 00112 { 00113 return history.back(); 00114 } 00115 00116 void hit(size_type ipage) 00117 { 00118 assert(ipage < n_pages); 00119 history.splice(history.begin(), history, history_entry[ipage]); 00120 } 00121 00122 void swap(lru_pager & obj) 00123 { 00124 std::swap(n_pages, obj.n_pages); 00125 history.swap(obj.history); 00126 history_entry.swap(obj.history_entry); 00127 } 00128 }; 00129 00131 00132 __STXXL_END_NAMESPACE 00133 00134 namespace std 00135 { 00136 template <unsigned npages_> 00137 void swap(stxxl::lru_pager<npages_> & a, 00138 stxxl::lru_pager<npages_> & b) 00139 { 00140 a.swap(b); 00141 } 00142 } 00143 00144 #endif // !STXXL_PAGER_HEADER 00145 // vim: et:ts=4:sw=4