blob: e45381366fceda56029e11b149d6faa1c16e7b93 [file] [log] [blame]
Alexander Afanasyev41824bd2013-01-23 23:57:59 -08001/* -*- Mode: C++; c-file-style: "gnu"; indent-tabs-mode:nil; -*- */
2/*
3 * Copyright (c) 2011 University of California, Los Angeles
4 *
5 * This program is free software; you can redistribute it and/or modify
6 * it under the terms of the GNU General Public License version 2 as
7 * published by the Free Software Foundation;
8 *
9 * This program is distributed in the hope that it will be useful,
10 * but WITHOUT ANY WARRANTY; without even the implied warranty of
11 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
12 * GNU General Public License for more details.
13 *
14 * You should have received a copy of the GNU General Public License
15 * along with this program; if not, write to the Free Software
16 * Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA
17 *
18 * Author: Alexander Afanasyev <alexander.afanasyev@ucla.edu>
19 */
20
21#ifndef LFU_POLICY_H_
22#define LFU_POLICY_H_
23
24#include <boost/intrusive/options.hpp>
25#include <boost/intrusive/set.hpp>
26
27namespace ns3 {
28namespace ndn {
29namespace ndnSIM {
30
31/**
32 * @brief Traits for LFU replacement policy
33 */
34struct lfu_policy_traits
35{
36 /// @brief Name that can be used to identify the policy (for NS-3 object model and logging)
37 static std::string GetName () { return "Lfu"; }
38
39 struct policy_hook_type : public boost::intrusive::set_member_hook<> { double frequency; };
40
41 template<class Container>
42 struct container_hook
43 {
44 typedef boost::intrusive::member_hook< Container,
45 policy_hook_type,
46 &Container::policy_hook_ > type;
47 };
48
49 template<class Base,
50 class Container,
51 class Hook>
52 struct policy
53 {
54 static double& get_order (typename Container::iterator item)
55 {
56 return static_cast<typename policy_container::value_traits::hook_type*>
57 (policy_container::value_traits::to_node_ptr(*item))->frequency;
58 }
59
60 static const double& get_order (typename Container::const_iterator item)
61 {
62 return static_cast<const typename policy_container::value_traits::hook_type*>
63 (policy_container::value_traits::to_node_ptr(*item))->frequency;
64 }
65
66 template<class Key>
67 struct MemberHookLess
68 {
69 bool operator () (const Key &a, const Key &b) const
70 {
71 return get_order (&a) < get_order (&b);
72 }
73 };
74
75 typedef boost::intrusive::multiset< Container,
76 boost::intrusive::compare< MemberHookLess< Container > >,
77 Hook > policy_container;
78
79 // could be just typedef
80 class type : public policy_container
81 {
82 public:
83 typedef policy policy_base; // to get access to get_order methods from outside
84 typedef Container parent_trie;
85
86 type (Base &base)
87 : base_ (base)
88 , max_size_ (100)
89 {
90 }
91
92 inline void
93 update (typename parent_trie::iterator item)
94 {
95 policy_container::erase (*item);
96 get_order (item) += 1;
97 policy_container::insert (*item);
98 }
99
100 inline bool
101 insert (typename parent_trie::iterator item)
102 {
103 get_order (item) = 0;
104
105 if (max_size_ != 0 && policy_container::size () >= max_size_)
106 {
107 // this erases the "least frequently used item" from cache
108 base_.erase (&(*policy_container::begin ()));
109 }
110
111 policy_container::insert (*item);
112 return true;
113 }
114
115 inline void
116 lookup (typename parent_trie::iterator item)
117 {
118 policy_container::erase (*item);
119 get_order (item) += 1;
120 policy_container::insert (*item);
121 }
122
123 inline void
124 erase (typename parent_trie::iterator item)
125 {
126 policy_container::erase (policy_container::s_iterator_to (*item));
127 }
128
129 inline void
130 clear ()
131 {
132 policy_container::clear ();
133 }
134
135 inline void
136 set_max_size (size_t max_size)
137 {
138 max_size_ = max_size;
139 }
140
141 inline size_t
142 get_max_size () const
143 {
144 return max_size_;
145 }
146
147 private:
148 type () : base_(*((Base*)0)) { };
149
150 private:
151 Base &base_;
152 size_t max_size_;
153 };
154 };
155};
156
157} // ndnSIM
158} // ndn
159} // ns3
160
161#endif // LFU_POLICY_H