NS-3 based Named Data Networking (NDN) simulator
ndnSIM 2.5: NDN, CCN, CCNx, content centric networks
API Documentation
nfd::name_tree::Hashtable Class Reference

a hashtable for fast exact name lookup More...

#include <name-tree-hashtable.hpp>

Public Types

typedef HashtableOptions Options
 

Public Member Functions

 Hashtable (const Options &options)
 
 ~Hashtable ()
 deallocates all nodes More...
 
size_t size () const
 
size_t getNBuckets () const
 
size_t computeBucketIndex (HashValue h) const
 
const NodegetBucket (size_t bucket) const
 
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...
 
std::pair< const Node *, bool > insert (const Name &name, size_t prefixLen, const HashSequence &hashes)
 find or insert node for name.getPrefix(prefixLen) More...
 
void erase (Node *node)
 delete node More...
 

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 149 of file name-tree-hashtable.hpp.

Member Typedef Documentation

◆ Options

Constructor & Destructor Documentation

◆ Hashtable()

◆ ~Hashtable()

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

deallocates all nodes

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

References nfd::name_tree::foreachNode(), nfd::name_tree::Node::next, and nfd::name_tree::Node::prev.

Member Function Documentation

◆ size()

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

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

Referenced by nfd::name_tree::NameTree::size().

◆ getNBuckets()

size_t nfd::name_tree::Hashtable::getNBuckets ( ) const
inline

◆ computeBucketIndex()

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

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

References getNBuckets().

Referenced by nfd::name_tree::FullEnumerationImpl::advance(), and erase().

◆ getBucket()

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

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

References getNBuckets().

Referenced by nfd::name_tree::FullEnumerationImpl::advance().

◆ 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.

References nfd::name_tree::computeHash().

Referenced by nfd::name_tree::NameTree::findExactMatch(), and nfd::name_tree::NameTree::findLongestPrefixMatch().

◆ 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.

References nfd::name_tree::computeHash().

◆ 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.

References nfd::name_tree::computeHash().

Referenced by nfd::name_tree::NameTree::lookup().

◆ erase()


The documentation for this class was generated from the following files: