nfd::name_tree::Hashtable Class Reference

A hashtable for fast exact name lookup. More...

#include <daemon/table/name-tree-hashtable.hpp>

Public Types

using Options = HashtableOptions
 

Public Member Functions

 Hashtable (const Options &options)
 
 ~Hashtable ()
 Deallocates all nodes. More...
 
size_t computeBucketIndex (HashValue h) const
 
void erase (Node *node)
 Delete node. More...
 
const Nodefind (const Name &name, size_t prefixLen) const
 Find node for name.getPrefix(prefixLen). More...
 
const Nodefind (const Name &name, size_t prefixLen, const HashSequence &hashes) const
 Find node for name.getPrefix(prefixLen). More...
 
const NodegetBucket (size_t bucket) const
 
size_t getNBuckets () const
 
std::pair< const Node *, bool > insert (const Name &name, size_t prefixLen, const HashSequence &hashes)
 Find or insert node for name.getPrefix(prefixLen). More...
 
size_t size () const
 

Detailed Description

A hashtable for fast exact name lookup.

The Hashtable contains a number of buckets. Each node is placed into a bucket determined by a hash value computed from its name. Hash collision is resolved through a doubly linked list in each bucket. The number of buckets is adjusted according to how many nodes are stored.

Definition at line 150 of file name-tree-hashtable.hpp.

Member Typedef Documentation

◆ Options

Constructor & Destructor Documentation

◆ Hashtable()

nfd::name_tree::Hashtable::Hashtable ( const Options options)
explicit

Definition at line 118 of file name-tree-hashtable.cpp.

◆ ~Hashtable()

nfd::name_tree::Hashtable::~Hashtable ( )

Deallocates all nodes.

Definition at line 136 of file name-tree-hashtable.cpp.

Member Function Documentation

◆ computeBucketIndex()

size_t nfd::name_tree::Hashtable::computeBucketIndex ( HashValue  h) const
inline
Returns
bucket index for hash value h

Definition at line 181 of file name-tree-hashtable.hpp.

◆ erase()

void nfd::name_tree::Hashtable::erase ( Node node)

Delete node.

Precondition
node exists in this hashtable

Definition at line 231 of file name-tree-hashtable.cpp.

◆ find() [1/2]

const Node * nfd::name_tree::Hashtable::find ( const Name &  name,
size_t  prefixLen 
) const

Find node for name.getPrefix(prefixLen).

Precondition
name.size() > prefixLen

Definition at line 210 of file name-tree-hashtable.cpp.

◆ find() [2/2]

const Node * nfd::name_tree::Hashtable::find ( const Name &  name,
size_t  prefixLen,
const HashSequence hashes 
) const

Find node for name.getPrefix(prefixLen).

Precondition
name.size() > prefixLen
hashes == computeHashes(name)

Definition at line 217 of file name-tree-hashtable.cpp.

◆ getBucket()

const Node* nfd::name_tree::Hashtable::getBucket ( size_t  bucket) const
inline
Returns
i-th bucket
Precondition
bucket < getNBuckets()

Definition at line 190 of file name-tree-hashtable.hpp.

◆ getNBuckets()

size_t nfd::name_tree::Hashtable::getNBuckets ( ) const
inline
Returns
number of buckets

Definition at line 173 of file name-tree-hashtable.hpp.

◆ insert()

std::pair< const Node *, bool > nfd::name_tree::Hashtable::insert ( const Name &  name,
size_t  prefixLen,
const HashSequence hashes 
)

Find or insert node for name.getPrefix(prefixLen).

Precondition
name.size() > prefixLen
hashes == computeHashes(name)

Definition at line 224 of file name-tree-hashtable.cpp.

◆ size()

size_t nfd::name_tree::Hashtable::size ( ) const
inline
Returns
number of nodes

Definition at line 165 of file name-tree-hashtable.hpp.