name-tree-hashtable.cpp
Go to the documentation of this file.
1 /* -*- Mode:C++; c-file-style:"gnu"; indent-tabs-mode:nil; -*- */
2 /*
3  * Copyright (c) 2014-2022, 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 #include "name-tree-hashtable.hpp"
27 #include "common/city-hash.hpp"
28 #include "common/logger.hpp"
29 
30 namespace nfd::name_tree {
31 
32 NFD_LOG_INIT(NameTreeHashtable);
33 
34 class Hash32
35 {
36 public:
37  static HashValue
38  compute(const void* buffer, size_t length)
39  {
40  return static_cast<HashValue>(CityHash32(reinterpret_cast<const char*>(buffer), length));
41  }
42 };
43 
44 class Hash64
45 {
46 public:
47  static HashValue
48  compute(const void* buffer, size_t length)
49  {
50  return static_cast<HashValue>(CityHash64(reinterpret_cast<const char*>(buffer), length));
51  }
52 };
53 
57 using HashFunc = std::conditional_t<(sizeof(HashValue) > 4), Hash64, Hash32>;
58 
60 computeHash(const Name& name, size_t prefixLen)
61 {
62  name.wireEncode(); // ensure wire buffer exists
63 
64  HashValue h = 0;
65  for (size_t i = 0, last = std::min(prefixLen, name.size()); i < last; ++i) {
66  const name::Component& comp = name[i];
67  h ^= HashFunc::compute(comp.data(), comp.size());
68  }
69  return h;
70 }
71 
73 computeHashes(const Name& name, size_t prefixLen)
74 {
75  name.wireEncode(); // ensure wire buffer exists
76 
77  size_t last = std::min(prefixLen, name.size());
78  HashSequence seq;
79  seq.reserve(last + 1);
80 
81  HashValue h = 0;
82  seq.push_back(h);
83 
84  for (size_t i = 0; i < last; ++i) {
85  const name::Component& comp = name[i];
86  h ^= HashFunc::compute(comp.data(), comp.size());
87  seq.push_back(h);
88  }
89  return seq;
90 }
91 
92 Node::Node(HashValue h, const Name& name)
93  : hash(h)
94  , prev(nullptr)
95  , next(nullptr)
96  , entry(name, this)
97 {
98 }
99 
101 {
102  BOOST_ASSERT(prev == nullptr);
103  BOOST_ASSERT(next == nullptr);
104 }
105 
106 Node*
107 getNode(const Entry& entry)
108 {
109  return entry.m_node;
110 }
111 
113  : initialSize(size)
114  , minSize(size)
115 {
116 }
117 
119  : m_options(options)
120  , m_size(0)
121 {
122  BOOST_ASSERT(m_options.minSize > 0);
123  BOOST_ASSERT(m_options.initialSize >= m_options.minSize);
124  BOOST_ASSERT(m_options.expandLoadFactor > 0.0);
125  BOOST_ASSERT(m_options.expandLoadFactor <= 1.0);
126  BOOST_ASSERT(m_options.expandFactor > 1.0);
127  BOOST_ASSERT(m_options.shrinkLoadFactor >= 0.0);
128  BOOST_ASSERT(m_options.shrinkLoadFactor < 1.0);
129  BOOST_ASSERT(m_options.shrinkFactor > 0.0);
130  BOOST_ASSERT(m_options.shrinkFactor < 1.0);
131 
132  m_buckets.resize(options.initialSize);
133  this->computeThresholds();
134 }
135 
137 {
138  for (size_t i = 0; i < m_buckets.size(); ++i) {
139  foreachNode(m_buckets[i], [] (Node* node) {
140  node->prev = node->next = nullptr;
141  delete node;
142  });
143  }
144 }
145 
146 void
147 Hashtable::attach(size_t bucket, Node* node)
148 {
149  node->prev = nullptr;
150  node->next = m_buckets[bucket];
151 
152  if (node->next != nullptr) {
153  BOOST_ASSERT(node->next->prev == nullptr);
154  node->next->prev = node;
155  }
156 
157  m_buckets[bucket] = node;
158 }
159 
160 void
161 Hashtable::detach(size_t bucket, Node* node)
162 {
163  if (node->prev != nullptr) {
164  BOOST_ASSERT(node->prev->next == node);
165  node->prev->next = node->next;
166  }
167  else {
168  BOOST_ASSERT(m_buckets[bucket] == node);
169  m_buckets[bucket] = node->next;
170  }
171 
172  if (node->next != nullptr) {
173  BOOST_ASSERT(node->next->prev == node);
174  node->next->prev = node->prev;
175  }
176 
177  node->prev = node->next = nullptr;
178 }
179 
180 std::pair<const Node*, bool>
181 Hashtable::findOrInsert(const Name& name, size_t prefixLen, HashValue h, bool allowInsert)
182 {
183  size_t bucket = this->computeBucketIndex(h);
184 
185  for (const Node* node = m_buckets[bucket]; node != nullptr; node = node->next) {
186  if (node->hash == h && name.compare(0, prefixLen, node->entry.getName()) == 0) {
187  NFD_LOG_TRACE("found " << name.getPrefix(prefixLen) << " hash=" << h << " bucket=" << bucket);
188  return {node, false};
189  }
190  }
191 
192  if (!allowInsert) {
193  NFD_LOG_TRACE("not-found " << name.getPrefix(prefixLen) << " hash=" << h << " bucket=" << bucket);
194  return {nullptr, false};
195  }
196 
197  Node* node = new Node(h, name.getPrefix(prefixLen));
198  this->attach(bucket, node);
199  NFD_LOG_TRACE("insert " << node->entry.getName() << " hash=" << h << " bucket=" << bucket);
200  ++m_size;
201 
202  if (m_size > m_expandThreshold) {
203  this->resize(static_cast<size_t>(m_options.expandFactor * this->getNBuckets()));
204  }
205 
206  return {node, true};
207 }
208 
209 const Node*
210 Hashtable::find(const Name& name, size_t prefixLen) const
211 {
212  HashValue h = computeHash(name, prefixLen);
213  return const_cast<Hashtable*>(this)->findOrInsert(name, prefixLen, h, false).first;
214 }
215 
216 const Node*
217 Hashtable::find(const Name& name, size_t prefixLen, const HashSequence& hashes) const
218 {
219  BOOST_ASSERT(hashes.at(prefixLen) == computeHash(name, prefixLen));
220  return const_cast<Hashtable*>(this)->findOrInsert(name, prefixLen, hashes[prefixLen], false).first;
221 }
222 
223 std::pair<const Node*, bool>
224 Hashtable::insert(const Name& name, size_t prefixLen, const HashSequence& hashes)
225 {
226  BOOST_ASSERT(hashes.at(prefixLen) == computeHash(name, prefixLen));
227  return this->findOrInsert(name, prefixLen, hashes[prefixLen], true);
228 }
229 
230 void
232 {
233  BOOST_ASSERT(node != nullptr);
234  BOOST_ASSERT(node->entry.getParent() == nullptr);
235 
236  size_t bucket = this->computeBucketIndex(node->hash);
237  NFD_LOG_TRACE("erase " << node->entry.getName() << " hash=" << node->hash << " bucket=" << bucket);
238 
239  this->detach(bucket, node);
240  delete node;
241  --m_size;
242 
243  if (m_size < m_shrinkThreshold) {
244  size_t newNBuckets = std::max(m_options.minSize,
245  static_cast<size_t>(m_options.shrinkFactor * this->getNBuckets()));
246  this->resize(newNBuckets);
247  }
248 }
249 
250 void
251 Hashtable::computeThresholds()
252 {
253  m_expandThreshold = static_cast<size_t>(m_options.expandLoadFactor * this->getNBuckets());
254  m_shrinkThreshold = static_cast<size_t>(m_options.shrinkLoadFactor * this->getNBuckets());
255  NFD_LOG_TRACE("thresholds expand=" << m_expandThreshold << " shrink=" << m_shrinkThreshold);
256 }
257 
258 void
259 Hashtable::resize(size_t newNBuckets)
260 {
261  if (this->getNBuckets() == newNBuckets) {
262  return;
263  }
264  NFD_LOG_DEBUG("resize from=" << this->getNBuckets() << " to=" << newNBuckets);
265 
266  std::vector<Node*> oldBuckets;
267  oldBuckets.swap(m_buckets);
268  m_buckets.resize(newNBuckets);
269 
270  for (Node* head : oldBuckets) {
271  foreachNode(head, [this] (Node* node) {
272  size_t bucket = this->computeBucketIndex(node->hash);
273  this->attach(bucket, node);
274  });
275  }
276 
277  this->computeThresholds();
278 }
279 
280 } // namespace nfd::name_tree
uint32 CityHash32(const char *s, size_t len)
Definition: city-hash.cpp:182
uint64 CityHash64(const char *s, size_t len)
Definition: city-hash.cpp:359
An entry in the name tree.
Entry * getParent() const noexcept
const Name & getName() const noexcept
A hashtable for fast exact name lookup.
void erase(Node *node)
Delete node.
std::pair< const Node *, bool > insert(const Name &name, size_t prefixLen, const HashSequence &hashes)
Find or insert node for name.getPrefix(prefixLen).
const Node * find(const Name &name, size_t prefixLen) const
Find node for name.getPrefix(prefixLen).
Hashtable(const Options &options)
~Hashtable()
Deallocates all nodes.
size_t computeBucketIndex(HashValue h) const
Node(HashValue h, const Name &name)
#define NFD_LOG_INIT(name)
Definition: logger.hpp:31
#define NFD_LOG_DEBUG
Definition: logger.hpp:38
#define NFD_LOG_TRACE
Definition: logger.hpp:37
std::vector< HashValue > HashSequence
A sequence of hash values.
HashValue computeHash(const Name &name, size_t prefixLen)
Computes hash value of name.getPrefix(prefixLen).
Node * getNode(const Entry &entry)
std::conditional_t<(sizeof(HashValue) > 4), Hash64, Hash32 > HashFunc
A type with a compute() static method to compute the hash value from a raw buffer.
void foreachNode(N *head, const F &func)
Invoke a function for each node in a doubly linked list.
size_t HashValue
A single hash value.
HashSequence computeHashes(const Name &name, size_t prefixLen)
Computes hash values for each prefix of name.getPrefix(prefixLen).
Provides options for Hashtable.
float expandFactor
When the hashtable is expanded, its new size will be nBuckets*expandFactor.
float shrinkLoadFactor
If the hashtable has less than nBuckets*shrinkLoadFactor nodes, it will be shrunk.
float shrinkFactor
When the hashtable is shrunk, its new size will be max(nBuckets*shrinkFactor, minSize).
float expandLoadFactor
If the hashtable has more than nBuckets*expandLoadFactor nodes, it will be expanded.
HashtableOptions(size_t size=16)
Constructor.
size_t minSize
Minimal number of buckets.
size_t initialSize
Initial number of buckets.