Stxxl
1.2.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 Roman Dementiev <dementiev@mpi-sb.mpg.de> 00007 * 00008 * Distributed under the Boost Software License, Version 1.0. 00009 * (See accompanying file LICENSE_1_0.txt or copy at 00010 * http://www.boost.org/LICENSE_1_0.txt) 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 // workaround for buggy GCC 3.4 STL 00087 //std::swap(history,obj.history); 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