26 #ifndef NFD_DAEMON_TABLE_NAME_TREE_HASHTABLE_HPP
27 #define NFD_DAEMON_TABLE_NAME_TREE_HASHTABLE_HPP
51 computeHash(
const Name& name, ssize_t prefixLen = -1);
70 Node(HashValue h,
const Name& name);
95 template<
typename N,
typename F>
100 while (node !=
nullptr) {
101 N* next = node->next;
177 return m_buckets.size();
195 return m_buckets[bucket];
202 find(
const Name& name,
size_t prefixLen)
const;
209 find(
const Name& name,
size_t prefixLen,
const HashSequence& hashes)
const;
215 std::pair<const Node*, bool>
216 insert(
const Name& name,
size_t prefixLen,
const HashSequence& hashes);
228 attach(
size_t bucket,
Node* node);
233 detach(
size_t bucket,
Node* node);
235 std::pair<const Node*, bool>
236 findOrInsert(
const Name& name,
size_t prefixLen, HashValue h,
bool allowInsert);
242 resize(
size_t newNBuckets);
245 std::vector<Node*> m_buckets;
248 size_t m_expandThreshold;
249 size_t m_shrinkThreshold;
255 #endif // NFD_DAEMON_TABLE_NAME_TREE_HASHTABLE_HPP
float shrinkFactor
when hashtable is shrunk, its new size is max(nBuckets*shrinkFactor, minSize)
size_t initialSize
initial number of buckets
HashSequence computeHashes(const Name &name)
computes hash values for each prefix of name
HashtableOptions(size_t size=16)
constructor
void foreachNode(N *head, const F &func)
invoke a function for each node in a doubly linked list
Node(HashValue h, const Name &name)
float expandFactor
when hashtable is expanded, its new size is nBuckets*expandFactor
float shrinkLoadFactor
if hashtable has less than nBuckets*shrinkLoadFactor nodes, it will be shrunk
provides options for Hashtable
Copyright (c) 2014-2015, Regents of the University of California, Arizona Board of Regents...
std::pair< const Node *, bool > insert(const Name &name, size_t prefixLen, const HashSequence &hashes)
find or insert node for name.getPrefix(prefixLen)
size_t computeBucketIndex(HashValue h) const
Hashtable(const Options &options)
size_t HashValue
a single hash value
std::vector< HashValue > HashSequence
a sequence of hash values
const Node * find(const Name &name, size_t prefixLen) const
find node for name.getPrefix(prefixLen)
Node * getNode(const Entry &entry)
an entry in the name tree
float expandLoadFactor
if hashtable has more than nBuckets*expandLoadFactor nodes, it will be expanded
HashValue computeHash(const Name &name, ssize_t prefixLen)
computes a single hash value
~Hashtable()
deallocates all nodes
size_t getNBuckets() const
void erase(Node *node)
delete node
size_t minSize
minimal number of buckets
const Node * getBucket(size_t bucket) const
a hashtable for fast exact name lookup