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 Node *	getBucket (size_t bucket) const
const Node *	find (const Name &name, size_t prefixLen) const
	find node for name.getPrefix(prefixLen) More...
const Node *	find (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 152 of file name-tree-hashtable.hpp.

Member Typedef Documentation

Options

typedef HashtableOptions nfd::name_tree::Hashtable::Options

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

Constructor & Destructor Documentation

Hashtable()

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

explicit

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

References nfd::name_tree::HashtableOptions::expandFactor, nfd::name_tree::HashtableOptions::expandLoadFactor, nfd::name_tree::HashtableOptions::initialSize, nfd::name_tree::HashtableOptions::minSize, nfd::name_tree::HashtableOptions::shrinkFactor, and nfd::name_tree::HashtableOptions::shrinkLoadFactor.

~Hashtable()

nfd::name_tree::Hashtable::~Hashtable

(

)

deallocates all nodes

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

References ndn::Name::compare(), computeBucketIndex(), nfd::name_tree::Node::entry, nfd::name_tree::HashtableOptions::expandFactor, nfd::name_tree::foreachNode(), nfd::name_tree::Entry::getName(), ndn::Name::getPrefix(), nfd::name_tree::Node::hash, nfd::name_tree::Node::next, NFD_LOG_TRACE, 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 167 of file name-tree-hashtable.hpp.

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

getNBuckets()

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

inline

Returns

number of buckets

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

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

computeBucketIndex()

size_t nfd::name_tree::Hashtable::computeBucketIndex ( HashValue  h ) const

inline

Returns

bucket index for hash value h

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

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

getBucket()

const Node* nfd::name_tree::Hashtable::getBucket ( size_t  bucket ) const

inline

Returns

i-th bucket

Precondition

bucket < getNBuckets()

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

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 208 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 215 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 222 of file name-tree-hashtable.cpp.

References nfd::name_tree::computeHash().

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

erase()

void nfd::name_tree::Hashtable::erase

(

Node *

node

)

delete node

Precondition

node exists in this hashtable

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

References computeBucketIndex(), nfd::name_tree::Node::entry, nfd::name_tree::HashtableOptions::expandLoadFactor, nfd::name_tree::foreachNode(), nfd::name_tree::Entry::getName(), getNBuckets(), nfd::name_tree::Entry::getParent(), nfd::name_tree::Node::hash, nfd::name_tree::HashtableOptions::minSize, NFD_LOG_DEBUG, NFD_LOG_TRACE, nfd::name_tree::HashtableOptions::shrinkFactor, and nfd::name_tree::HashtableOptions::shrinkLoadFactor.

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

---

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

• ndnSIM/NFD/daemon/table/name-tree-hashtable.hpp
• ndnSIM/NFD/daemon/table/name-tree-hashtable.cpp