NS-3 based Named Data Networking (NDN) simulator
ndnSIM 2.5: NDN, CCN, CCNx, content centric networks
API Documentation
name-tree-hashtable.hpp
Go to the documentation of this file.
1 /* -*- Mode:C++; c-file-style:"gnu"; indent-tabs-mode:nil; -*- */
2 /*
3  * Copyright (c) 2014-2017, 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_NAME_TREE_HASHTABLE_HPP
27 #define NFD_DAEMON_TABLE_NAME_TREE_HASHTABLE_HPP
28 
29 #include "name-tree-entry.hpp"
30 
31 namespace nfd {
32 namespace name_tree {
33 
34 class Entry;
35 
38 using HashValue = size_t;
39 
43 using HashSequence = std::vector<HashValue>;
44 
48 computeHash(const Name& name, size_t prefixLen = std::numeric_limits<size_t>::max());
49 
54 computeHashes(const Name& name, size_t prefixLen = std::numeric_limits<size_t>::max());
55 
61 class Node : noncopyable
62 {
63 public:
67  Node(HashValue h, const Name& name);
68 
72  ~Node();
73 
74 public:
75  const HashValue hash;
78  mutable Entry entry;
79 };
80 
84 Node*
85 getNode(const Entry& entry);
86 
92 template<typename N, typename F>
93 void
94 foreachNode(N* head, const F& func)
95 {
96  N* node = head;
97  while (node != nullptr) {
98  N* next = node->next;
99  func(node);
100  node = next;
101  }
102 }
103 
107 {
108 public:
113  explicit
114  HashtableOptions(size_t size = 16);
115 
116 public:
119  size_t initialSize;
120 
123  size_t minSize;
124 
127  float expandLoadFactor = 0.5;
128 
131  float expandFactor = 2.0;
132 
135  float shrinkLoadFactor = 0.1;
136 
139  float shrinkFactor = 0.5;
140 };
141 
150 {
151 public:
153 
154  explicit
155  Hashtable(const Options& options);
156 
159  ~Hashtable();
160 
163  size_t
164  size() const
165  {
166  return m_size;
167  }
168 
171  size_t
172  getNBuckets() const
173  {
174  return m_buckets.size();
175  }
176 
179  size_t
181  {
182  return h % this->getNBuckets();
183  }
184 
188  const Node*
189  getBucket(size_t bucket) const
190  {
191  BOOST_ASSERT(bucket < this->getNBuckets());
192  return m_buckets[bucket]; // don't use m_bucket.at() for better performance
193  }
194 
198  const Node*
199  find(const Name& name, size_t prefixLen) const;
200 
205  const Node*
206  find(const Name& name, size_t prefixLen, const HashSequence& hashes) const;
207 
212  std::pair<const Node*, bool>
213  insert(const Name& name, size_t prefixLen, const HashSequence& hashes);
214 
218  void
219  erase(Node* node);
220 
221 private:
224  void
225  attach(size_t bucket, Node* node);
226 
229  void
230  detach(size_t bucket, Node* node);
231 
232  std::pair<const Node*, bool>
233  findOrInsert(const Name& name, size_t prefixLen, HashValue h, bool allowInsert);
234 
235  void
236  computeThresholds();
237 
238  void
239  resize(size_t newNBuckets);
240 
241 private:
242  std::vector<Node*> m_buckets;
243  Options m_options;
244  size_t m_size;
245  size_t m_expandThreshold;
246  size_t m_shrinkThreshold;
247 };
248 
249 } // namespace name_tree
250 } // namespace nfd
251 
252 #endif // NFD_DAEMON_TABLE_NAME_TREE_HASHTABLE_HPP
nfd::name_tree::Entry
An entry in the name tree.
Definition: name-tree-entry.hpp:42
nfd::name_tree::HashtableOptions::initialSize
size_t initialSize
initial number of buckets
Definition: name-tree-hashtable.hpp:119
nfd::name_tree::Hashtable::size
size_t size() const
Definition: name-tree-hashtable.hpp:164
nfd::name_tree::Hashtable::Options
HashtableOptions Options
Definition: name-tree-hashtable.hpp:152
nfd::name_tree::Hashtable::getNBuckets
size_t getNBuckets() const
Definition: name-tree-hashtable.hpp:172
nfd::name_tree::computeHashes
HashSequence computeHashes(const Name &name, size_t prefixLen)
computes hash values for each prefix of name.getPrefix(prefixLen)
Definition: name-tree-hashtable.cpp:73
nfd::name_tree::getNode
Node * getNode(const Entry &entry)
Definition: name-tree-hashtable.cpp:107
nfd::name_tree::foreachNode
void foreachNode(N *head, const F &func)
invoke a function for each node in a doubly linked list
Definition: name-tree-hashtable.hpp:94
nfd::name_tree::Node::prev
Node * prev
Definition: name-tree-hashtable.hpp:76
nfd::name_tree::HashtableOptions::minSize
size_t minSize
minimal number of buckets
Definition: name-tree-hashtable.hpp:123
nfd::name_tree::Hashtable::Hashtable
Hashtable(const Options &options)
Definition: name-tree-hashtable.cpp:118
name-tree-entry.hpp
ndn::Name
Represents an absolute name.
Definition: name.hpp:44
nfd
Copyright (c) 2011-2015 Regents of the University of California.
Definition: ndn-common.hpp:40
nfd::name_tree::Node::Node
Node(HashValue h, const Name &name)
Definition: name-tree-hashtable.cpp:92
nfd::name_tree::Node
a hashtable node
Definition: name-tree-hashtable.hpp:62
nfd::name_tree::Node::next
Node * next
Definition: name-tree-hashtable.hpp:77
nfd::name_tree::HashtableOptions::HashtableOptions
HashtableOptions(size_t size=16)
constructor
Definition: name-tree-hashtable.cpp:112
nfd::name_tree::HashtableOptions::shrinkLoadFactor
float shrinkLoadFactor
if hashtable has less than nBuckets*shrinkLoadFactor nodes, it will be shrunk
Definition: name-tree-hashtable.hpp:135
nfd::name_tree::HashValue
size_t HashValue
a single hash value
Definition: name-tree-hashtable.hpp:38
nfd::name_tree::Node::hash
const HashValue hash
Definition: name-tree-hashtable.hpp:75
nfd::name_tree::Hashtable
a hashtable for fast exact name lookup
Definition: name-tree-hashtable.hpp:150
nfd::name_tree::Node::entry
Entry entry
Definition: name-tree-hashtable.hpp:78
nfd::name_tree::Hashtable::getBucket
const Node * getBucket(size_t bucket) const
Definition: name-tree-hashtable.hpp:189
nfd::name_tree::computeHash
HashValue computeHash(const Name &name, size_t prefixLen)
computes hash value of name.getPrefix(prefixLen)
Definition: name-tree-hashtable.cpp:60
nfd::name_tree::Hashtable::find
const Node * find(const Name &name, size_t prefixLen) const
find node for name.getPrefix(prefixLen)
Definition: name-tree-hashtable.cpp:210
nfd::name_tree::Node::~Node
~Node()
Definition: name-tree-hashtable.cpp:100
nfd::name_tree::HashtableOptions::expandFactor
float expandFactor
when hashtable is expanded, its new size is nBuckets*expandFactor
Definition: name-tree-hashtable.hpp:131
ndn::name
Definition: name-component-types.hpp:33
nfd::name_tree::HashSequence
std::vector< HashValue > HashSequence
a sequence of hash values
Definition: name-tree-hashtable.hpp:43
nfd::name_tree::HashtableOptions::shrinkFactor
float shrinkFactor
when hashtable is shrunk, its new size is max(nBuckets*shrinkFactor, minSize)
Definition: name-tree-hashtable.hpp:139
nfd::name_tree::Hashtable::~Hashtable
~Hashtable()
deallocates all nodes
Definition: name-tree-hashtable.cpp:136
nfd::name_tree::HashtableOptions::expandLoadFactor
float expandLoadFactor
if hashtable has more than nBuckets*expandLoadFactor nodes, it will be expanded
Definition: name-tree-hashtable.hpp:127
nfd::name_tree::HashtableOptions
provides options for Hashtable
Definition: name-tree-hashtable.hpp:107
nfd::name_tree::Hashtable::erase
void erase(Node *node)
delete node
Definition: name-tree-hashtable.cpp:231
nfd::name_tree::Hashtable::computeBucketIndex
size_t computeBucketIndex(HashValue h) const
Definition: name-tree-hashtable.hpp:180
nfd::name_tree::Hashtable::insert
std::pair< const Node *, bool > insert(const Name &name, size_t prefixLen, const HashSequence &hashes)
find or insert node for name.getPrefix(prefixLen)
Definition: name-tree-hashtable.cpp:224