NS-3 based Named Data Networking (NDN) simulator
ndnSIM 2.3: 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; -*- */
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 typedef size_t HashValue;
39 
43 typedef std::vector<HashValue> HashSequence;
44 
50 HashValue
51 computeHash(const Name& name, ssize_t prefixLen = -1);
52 
56 HashSequence
57 computeHashes(const Name& name);
58 
64 class Node : noncopyable
65 {
66 public:
70  Node(HashValue h, const Name& name);
71 
75  ~Node();
76 
77 public:
78  const HashValue hash;
81  mutable Entry entry;
82 };
83 
87 Node*
88 getNode(const Entry& entry);
89 
95 template<typename N, typename F>
96 void
97 foreachNode(N* head, const F& func)
98 {
99  N* node = head;
100  while (node != nullptr) {
101  N* next = node->next;
102  func(node);
103  node = next;
104  }
105 }
106 
110 {
111 public:
116  explicit
117  HashtableOptions(size_t size = 16);
118 
119 public:
122  size_t initialSize;
123 
126  size_t minSize;
127 
130  float expandLoadFactor = 0.5;
131 
134  float expandFactor = 2.0;
135 
138  float shrinkLoadFactor = 0.1;
139 
142  float shrinkFactor = 0.5;
143 };
144 
153 {
154 public:
156 
157  explicit
158  Hashtable(const Options& options);
159 
162  ~Hashtable();
163 
166  size_t
167  size() const
168  {
169  return m_size;
170  }
171 
174  size_t
175  getNBuckets() const
176  {
177  return m_buckets.size();
178  }
179 
182  size_t
183  computeBucketIndex(HashValue h) const
184  {
185  return h % this->getNBuckets();
186  }
187 
191  const Node*
192  getBucket(size_t bucket) const
193  {
194  BOOST_ASSERT(bucket < this->getNBuckets());
195  return m_buckets[bucket]; // don't use m_bucket.at() for better performance
196  }
197 
201  const Node*
202  find(const Name& name, size_t prefixLen) const;
203 
208  const Node*
209  find(const Name& name, size_t prefixLen, const HashSequence& hashes) const;
210 
215  std::pair<const Node*, bool>
216  insert(const Name& name, size_t prefixLen, const HashSequence& hashes);
217 
221  void
222  erase(Node* node);
223 
224 private:
227  void
228  attach(size_t bucket, Node* node);
229 
232  void
233  detach(size_t bucket, Node* node);
234 
235  std::pair<const Node*, bool>
236  findOrInsert(const Name& name, size_t prefixLen, HashValue h, bool allowInsert);
237 
238  void
239  computeThresholds();
240 
241  void
242  resize(size_t newNBuckets);
243 
244 private:
245  std::vector<Node*> m_buckets;
246  Options m_options;
247  size_t m_size;
248  size_t m_expandThreshold;
249  size_t m_shrinkThreshold;
250 };
251 
252 } // namespace name_tree
253 } // namespace nfd
254 
255 #endif // NFD_DAEMON_TABLE_NAME_TREE_HASHTABLE_HPP
HashSequence computeHashes(const Name &name)
computes hash values for each prefix of name
void foreachNode(N *head, const F &func)
invoke a function for each node in a doubly linked list
Node(HashValue h, const Name &name)
const Node * getBucket(size_t bucket) const
size_t computeBucketIndex(HashValue h) const
provides options for Hashtable
a hashtable for fast exact name lookup
Copyright (c) 2011-2015 Regents of the University of California.
Definition: ndn-common.hpp:40
Name abstraction to represent an absolute name.
Definition: name.hpp:46
size_t HashValue
a single hash value
std::vector< HashValue > HashSequence
a sequence of hash values
Node * getNode(const Entry &entry)
HashValue computeHash(const Name &name, ssize_t prefixLen)
computes a single hash value
size_t initialSize
initial number of buckets
size_t minSize
minimal number of buckets
an entry in the name tree