26 #ifndef NFD_DAEMON_TABLE_NAME_TREE_HASHTABLE_HPP
27 #define NFD_DAEMON_TABLE_NAME_TREE_HASHTABLE_HPP
49 computeHash(
const Name& name,
size_t prefixLen = std::numeric_limits<size_t>::max());
55 computeHashes(
const Name& name,
size_t prefixLen = std::numeric_limits<size_t>::max());
93 template<
typename N,
typename F>
98 while (node !=
nullptr) {
175 return m_buckets.size();
193 return m_buckets[bucket];
200 find(
const Name& name,
size_t prefixLen)
const;
213 std::pair<const Node*, bool>
226 attach(
size_t bucket,
Node* node);
231 detach(
size_t bucket,
Node* node);
233 std::pair<const Node*, bool>
234 findOrInsert(
const Name& name,
size_t prefixLen,
HashValue h,
bool allowInsert);
240 resize(
size_t newNBuckets);
243 std::vector<Node*> m_buckets;
246 size_t m_expandThreshold;
247 size_t m_shrinkThreshold;
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
size_t getNBuckets() 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.