dead-nonce-list.hpp
Go to the documentation of this file.
1 /* -*- Mode:C++; c-file-style:"gnu"; indent-tabs-mode:nil; -*- */
2 /*
3  * Copyright (c) 2014-2020, Regents of the University of California,
4  * Arizona Board of Regents,
5  * Colorado State University,
6  * University Pierre & Marie Curie, Sorbonne University,
7  * Washington University in St. Louis,
8  * Beijing Institute of Technology,
9  * The University of Memphis.
10  *
11  * This file is part of NFD (Named Data Networking Forwarding Daemon).
12  * See AUTHORS.md for complete list of NFD authors and contributors.
13  *
14  * NFD is free software: you can redistribute it and/or modify it under the terms
15  * of the GNU General Public License as published by the Free Software Foundation,
16  * either version 3 of the License, or (at your option) any later version.
17  *
18  * NFD is distributed in the hope that it will be useful, but WITHOUT ANY WARRANTY;
19  * without even the implied warranty of MERCHANTABILITY or FITNESS FOR A PARTICULAR
20  * PURPOSE. See the GNU General Public License for more details.
21  *
22  * You should have received a copy of the GNU General Public License along with
23  * NFD, e.g., in COPYING.md file. If not, see <http://www.gnu.org/licenses/>.
24  */
25 
26 #ifndef NFD_DAEMON_TABLE_DEAD_NONCE_LIST_HPP
27 #define NFD_DAEMON_TABLE_DEAD_NONCE_LIST_HPP
28 
29 #include "core/common.hpp"
30 
31 #include <boost/multi_index_container.hpp>
32 #include <boost/multi_index/hashed_index.hpp>
33 #include <boost/multi_index/sequenced_index.hpp>
34 
35 namespace nfd {
36 
54 class DeadNonceList : noncopyable
55 {
56 public:
64  explicit
65  DeadNonceList(time::nanoseconds lifetime = DEFAULT_LIFETIME);
66 
68 
72  bool
73  has(const Name& name, Interest::Nonce nonce) const;
74 
77  void
78  add(const Name& name, Interest::Nonce nonce);
79 
83  size_t
84  size() const;
85 
88  time::nanoseconds
89  getLifetime() const
90  {
91  return m_lifetime;
92  }
93 
94 private: // Entry and Index
95  typedef uint64_t Entry;
96 
97  static Entry
98  makeEntry(const Name& name, Interest::Nonce nonce);
99 
100  typedef boost::multi_index_container<
101  Entry,
102  boost::multi_index::indexed_by<
103  boost::multi_index::sequenced<>,
104  boost::multi_index::hashed_non_unique<
105  boost::multi_index::identity<Entry>
106  >
107  >
108  > Index;
109 
110  typedef Index::nth_index<0>::type Queue;
111  typedef Index::nth_index<1>::type Hashtable;
112 
113 private: // actual lifetime estimation and capacity control
116  size_t
117  countMarks() const;
118 
121  void
122  mark();
123 
129  void
130  adjustCapacity();
131 
134  void
135  evictEntries();
136 
137 public:
139  static const time::nanoseconds DEFAULT_LIFETIME;
141  static const time::nanoseconds MIN_LIFETIME;
142 
143 private:
144  time::nanoseconds m_lifetime;
145  Index m_index;
146  Queue& m_queue;
147  Hashtable& m_ht;
148 
149 PUBLIC_WITH_TESTS_ELSE_PRIVATE: // actual lifetime estimation and capacity control
150 
151  // ---- current capacity and hard limits
152 
160  size_t m_capacity;
161 
162  static const size_t INITIAL_CAPACITY;
163 
168  static const size_t MIN_CAPACITY;
169 
174  static const size_t MAX_CAPACITY;
175 
176  // ---- actual entry lifetime estimation
177 
184  static const Entry MARK;
185 
188  static const size_t EXPECTED_MARK_COUNT;
189 
195  std::multiset<size_t> m_actualMarkCounts;
196 
197  time::nanoseconds m_markInterval;
198  scheduler::EventId m_markEvent;
199 
200  // ---- capacity adjustments
201 
202  static const double CAPACITY_UP;
203  static const double CAPACITY_DOWN;
204  time::nanoseconds m_adjustCapacityInterval;
205  scheduler::EventId m_adjustCapacityEvent;
206 
208  static const size_t EVICT_LIMIT;
209 };
210 
211 } // namespace nfd
212 
213 #endif // NFD_DAEMON_TABLE_DEAD_NONCE_LIST_HPP
Copyright (c) 2014-2015, Regents of the University of California, Arizona Board of Regents...
Definition: algorithm.hpp:32
time::nanoseconds getLifetime() const
Represents the Dead Nonce List.
DeadNonceList(time::nanoseconds lifetime=DEFAULT_LIFETIME)
Constructs the Dead Nonce List.
#define PUBLIC_WITH_TESTS_ELSE_PRIVATE
Definition: common.hpp:41
static const time::nanoseconds MIN_LIFETIME
Minimum entry lifetime.
bool has(const Name &name, Interest::Nonce nonce) const
Determines if name+nonce exists.
size_t size() const
void add(const Name &name, Interest::Nonce nonce)
Records name+nonce.
static const time::nanoseconds DEFAULT_LIFETIME
Default entry lifetime.