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-2024, 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 #include <limits>
32 
33 namespace nfd::name_tree {
34 
35 class Entry;
36 
39 using HashValue = size_t;
40 
44 using HashSequence = std::vector<HashValue>;
45 
49 computeHash(const Name& name, size_t prefixLen = std::numeric_limits<size_t>::max());
50 
55 computeHashes(const Name& name, size_t prefixLen = std::numeric_limits<size_t>::max());
56 
62 class Node : noncopyable
63 {
64 public:
68  Node(HashValue h, const Name& name);
69 
73  ~Node();
74 
75 public:
76  const HashValue hash;
79  mutable Entry entry;
80 };
81 
85 Node*
86 getNode(const Entry& entry);
87 
93 template<typename N, typename F>
94 void
95 foreachNode(N* head, const F& func)
96 {
97  N* node = head;
98  while (node != nullptr) {
99  N* next = node->next;
100  func(node);
101  node = next;
102  }
103 }
104 
109 {
114  explicit
115  HashtableOptions(size_t size = 16);
116 
119  size_t initialSize;
120 
123  size_t minSize;
124 
127  float expandLoadFactor = 0.5f;
128 
131  float expandFactor = 2.0f;
132 
135  float shrinkLoadFactor = 0.1f;
136 
139  float shrinkFactor = 0.5f;
140 };
141 
151 {
152 public:
154 
155  explicit
156  Hashtable(const Options& options);
157 
160  ~Hashtable();
161 
164  size_t
165  size() const
166  {
167  return m_size;
168  }
169 
172  size_t
173  getNBuckets() const
174  {
175  return m_buckets.size();
176  }
177 
180  size_t
182  {
183  return h % this->getNBuckets();
184  }
185 
189  const Node*
190  getBucket(size_t bucket) const
191  {
192  BOOST_ASSERT(bucket < this->getNBuckets());
193  return m_buckets[bucket]; // don't use m_bucket.at() for better performance
194  }
195 
199  const Node*
200  find(const Name& name, size_t prefixLen) const;
201 
206  const Node*
207  find(const Name& name, size_t prefixLen, const HashSequence& hashes) const;
208 
213  std::pair<const Node*, bool>
214  insert(const Name& name, size_t prefixLen, const HashSequence& hashes);
215 
219  void
220  erase(Node* node);
221 
222 private:
225  void
226  attach(size_t bucket, Node* node);
227 
230  void
231  detach(size_t bucket, Node* node);
232 
233  std::pair<const Node*, bool>
234  findOrInsert(const Name& name, size_t prefixLen, HashValue h, bool allowInsert);
235 
236  void
237  computeThresholds();
238 
239  void
240  resize(size_t newNBuckets);
241 
242 private:
243  std::vector<Node*> m_buckets;
244  Options m_options;
245  size_t m_size;
246  size_t m_expandThreshold;
247  size_t m_shrinkThreshold;
248 };
249 
250 } // namespace nfd::name_tree
251 
252 #endif // NFD_DAEMON_TABLE_NAME_TREE_HASHTABLE_HPP
An entry in the name tree.
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)
const Node * getBucket(size_t bucket) const
~Hashtable()
Deallocates all nodes.
size_t computeBucketIndex(HashValue h) const
Node(HashValue h, const Name &name)
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)
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.