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 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...
const Node *	getBucket (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 148 of file name-tree-hashtable.hpp.

Member Typedef Documentation

Options

using nfd::name_tree::Hashtable::Options = HashtableOptions

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

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

getNBuckets()

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

inline

Returns

number of buckets

Definition at line 171 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 163 of file name-tree-hashtable.hpp.