nfd::name_tree::Hashtable Class Reference

a hashtable for fast exact name lookup More...

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

Public Types
typedef HashtableOptions	Options

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

Member Typedef Documentation

Options

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

Definition at line 152 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 180 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 189 of file name-tree-hashtable.hpp.

getNBuckets()

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

inline

Returns

number of buckets

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