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
size_t initialSize
initial number of buckets
size_t HashValue
a single hash value
void foreachNode(N *head, const F &func)
invoke a function for each node in a doubly linked list
HashSequence computeHashes(const Name &name, size_t prefixLen)
computes hash values for each prefix of name.getPrefix(prefixLen)
Node(HashValue h, const Name &name)
HashValue computeHash(const Name &name, size_t prefixLen)
computes hash value of name.getPrefix(prefixLen)
size_t computeBucketIndex(HashValue h) const
std::vector< HashValue > HashSequence
a sequence of hash values
const Node * getBucket(size_t bucket) const
provides options for Hashtable
Copyright (c) 2014-2015, Regents of the University of California, Arizona Board of Regents...
Definition: algorithm.hpp:32
Node * getNode(const Entry &entry)
An entry in the name tree.
size_t minSize
minimal number of buckets
a hashtable for fast exact name lookup