#include <smallhash.h>

Inheritance diagram for SmallHashBase< Key, Value, Derived >:

Collaboration diagram for SmallHashBase< Key, Value, Derived >:

Public Member Functions
	SmallHashBase ()

	~SmallHashBase ()

void	Init (uint32_t expected_size, Key empty, uint32_t(*hasher)(const Key &key))

bool	Lookup (const Key &key, Value *value) const

bool	LookupEx (Key key, Value value) const

bool	Contains (const Key &key) const

void	Insert (const Key &key, const Value &value)

bool	Erase (const Key &key)

void	Clear ()

uint64_t	bytes_allocated () const

void	GetCollisionStats (uint64_t num_collisions, uint32_t max_collisions) const

uint32_t	capacity () const

Key	empty_key () const

Key *	keys () const

Value *	values () const

void	SetHasher (uint32_t(*hasher)(const Key &key))

Static Public Member Functions
static double	GetEntrySize ()

Static Public Attributes
static const double	kLoadFactor = 0.75

static const double	kThresholdGrow

static const double	kThresholdShrink

Protected Member Functions
uint32_t	ScaleHash (const Key &key) const

void	AllocMemory ()

void	DeallocMemory (Key k, Value v, uint32_t c)

bool	DoInsert (const Key &key, const Value &value, const bool count_collisions)

bool	DoLookup (const Key &key, uint32_t bucket, uint32_t collisions) const

void	DoClear (const bool reset_capacity)

void	SetThresholds ()

void	Grow ()

void	Shrink ()

void	ResetCapacity ()

Protected Attributes
Key *	keys_

Value *	values_

uint32_t	capacity_

uint32_t	initial_capacity_

uint32_t	size_

uint32_t(*	hasher_ )(const Key &key)

uint64_t	bytes_allocated_

uint64_t	num_collisions_

uint32_t	max_collisions_

Key	empty_key_

Private Member Functions
	FRIEND_TEST (T_Smallhash, InsertAndCopyMd5Slow)

Detailed Description

template<class Key, class Value, class Derived>
class SmallHashBase< Key, Value, Derived >

Hash table with linear probing as collision resolution. Works only for a fixed (maximum) number of elements, i.e. no resizing. Load factor fixed to 0.7.

Definition at line 34 of file smallhash.h.

Constructor & Destructor Documentation

template<class Key, class Value, class Derived>

SmallHashBase< Key, Value, Derived >::SmallHashBase ( )

inline

Definition at line 42 of file smallhash.h.

template<class Key, class Value, class Derived>

SmallHashBase< Key, Value, Derived >::~SmallHashBase ( )

inline

Definition at line 56 of file smallhash.h.

Member Function Documentation

template<class Key, class Value, class Derived>

void SmallHashBase< Key, Value, Derived >::AllocMemory ( )

inlineprotected

Definition at line 162 of file smallhash.h.

Referenced by SmallHashBase< uint64_t, shash_v1::Md5, SmallHashDynamic< uint64_t, shash_v1::Md5 > >::Init(), SmallHashDynamic< glue::InodeEx, shash::Md5 >::Migrate(), and SmallHashDynamic< glue::InodeEx, shash::Md5 >::ResetCapacity().

Here is the caller graph for this function:

template<class Key, class Value, class Derived>

uint64_t SmallHashBase< Key, Value, Derived >::bytes_allocated ( ) const

inline

Definition at line 133 of file smallhash.h.

template<class Key, class Value, class Derived>

uint32_t SmallHashBase< Key, Value, Derived >::capacity ( ) const

inline

Definition at line 146 of file smallhash.h.

template<class Key, class Value, class Derived>

void SmallHashBase< Key, Value, Derived >::Clear ( )

inline

Definition at line 131 of file smallhash.h.

Referenced by glue::PathMap::Clear(), and glue::InodeReferences::Clear().

Here is the caller graph for this function:

template<class Key, class Value, class Derived>

bool SmallHashBase< Key, Value, Derived >::Contains ( const Key & key ) const

inline

Definition at line 99 of file smallhash.h.

Referenced by SmallhashFilter::Contains(), cvmfs::cvmfs_open(), glue::PathMap::Erase(), swissknife::CommandCheck::Find(), glue::PathMap::Insert(), swissknife::CatalogTraversalParallel< ObjectFetcherT >::PushNestedCatalogs(), swissknife::CatalogTraversalParallel< ObjectFetcherT >::PushPreviousRevision(), swissknife::CatalogTraversalParallel< ObjectFetcherT >::Traverse(), and swissknife::CatalogTraversalParallel< ObjectFetcherT >::TraverseList().

Here is the caller graph for this function:

template<class Key, class Value, class Derived>

void SmallHashBase< Key, Value, Derived >::DeallocMemory	(	Key *	k,
		Value *	v,
		uint32_t	c
	)

inlineprotected

Definition at line 174 of file smallhash.h.

Referenced by SmallHashDynamic< glue::InodeEx, shash::Md5 >::Migrate(), SmallHashDynamic< glue::InodeEx, shash::Md5 >::ResetCapacity(), and SmallHashBase< uint64_t, shash_v1::Md5, SmallHashDynamic< uint64_t, shash_v1::Md5 > >::~SmallHashBase().

Here is the caller graph for this function:

template<class Key, class Value, class Derived>

void SmallHashBase< Key, Value, Derived >::DoClear ( const bool reset_capacity )

inlineprotected

Definition at line 216 of file smallhash.h.

Referenced by SmallHashBase< uint64_t, shash_v1::Md5, SmallHashDynamic< uint64_t, shash_v1::Md5 > >::Clear(), SmallHashBase< uint64_t, shash_v1::Md5, SmallHashDynamic< uint64_t, shash_v1::Md5 > >::Init(), and SmallHashDynamic< glue::InodeEx, shash::Md5 >::Migrate().

Here is the caller graph for this function:

template<class Key, class Value, class Derived>

bool SmallHashBase< Key, Value, Derived >::DoInsert	(	const Key &	key,
		const Value &	value,
		const bool	count_collisions
	)

inlineprotected

Definition at line 190 of file smallhash.h.

Referenced by SmallHashBase< uint64_t, shash_v1::Md5, SmallHashDynamic< uint64_t, shash_v1::Md5 > >::Erase(), and SmallHashBase< uint64_t, shash_v1::Md5, SmallHashDynamic< uint64_t, shash_v1::Md5 > >::Insert().

Here is the caller graph for this function:

template<class Key, class Value, class Derived>

bool SmallHashBase< Key, Value, Derived >::DoLookup	(	const Key &	key,
		uint32_t *	bucket,
		uint32_t *	collisions
	)		const

inlineprotected

Definition at line 204 of file smallhash.h.

Referenced by SmallHashBase< uint64_t, shash_v1::Md5, SmallHashDynamic< uint64_t, shash_v1::Md5 > >::Contains(), SmallHashBase< uint64_t, shash_v1::Md5, SmallHashDynamic< uint64_t, shash_v1::Md5 > >::DoInsert(), SmallHashBase< uint64_t, shash_v1::Md5, SmallHashDynamic< uint64_t, shash_v1::Md5 > >::Erase(), and SmallHashBase< uint64_t, shash_v1::Md5, SmallHashDynamic< uint64_t, shash_v1::Md5 > >::Lookup().

Here is the caller graph for this function:

template<class Key, class Value, class Derived>

Key SmallHashBase< Key, Value, Derived >::empty_key ( ) const

inline

Definition at line 147 of file smallhash.h.

Referenced by glue::InodeReferences::Next().

Here is the caller graph for this function:

template<class Key, class Value, class Derived>

bool SmallHashBase< Key, Value, Derived >::Erase ( const Key & key )

inline

Definition at line 112 of file smallhash.h.

Referenced by FdRefcountMgr::Close(), cvmfs::cvmfs_release(), glue::PathMap::Erase(), TaskCompress::Process(), TaskChunk::Process(), glue::InodeReferences::Put(), glue::InodeReferences::Replace(), and StreamingCacheManager::Stream().

Here is the caller graph for this function:

template<class Key, class Value, class Derived>

SmallHashBase< Key, Value, Derived >::FRIEND_TEST	(	T_Smallhash	,
		InsertAndCopyMd5Slow
	)

private

template<class Key, class Value, class Derived>

void SmallHashBase< Key, Value, Derived >::GetCollisionStats	(	uint64_t *	num_collisions,
		uint32_t *	max_collisions
	)		const

inline

Definition at line 139 of file smallhash.h.

template<class Key, class Value, class Derived>

static double SmallHashBase< Key, Value, Derived >::GetEntrySize ( )

inlinestatic

Definition at line 134 of file smallhash.h.

template<class Key, class Value, class Derived>

void SmallHashBase< Key, Value, Derived >::Grow ( )

inlineprotected

Definition at line 226 of file smallhash.h.

Referenced by SmallHashBase< uint64_t, shash_v1::Md5, SmallHashDynamic< uint64_t, shash_v1::Md5 > >::Insert().

Here is the caller graph for this function:

template<class Key, class Value, class Derived>

void SmallHashBase< Key, Value, Derived >::Init	(	uint32_t	expected_size,
		Key	empty,
		uint32_t(*)(const Key &key)	hasher
	)

inline

Definition at line 58 of file smallhash.h.

Referenced by swissknife::CatalogTraversalParallel< ObjectFetcherT >::CatalogTraversalParallel(), swissknife::CommandCheck::CommandCheck(), FdRefcountMgr::FdRefcountMgr(), glue::InodeReferences::InodeReferences(), glue::PathMap::PathMap(), swissknife::CommandListReflog::Run(), SmallhashFilter::SmallhashFilter(), StreamingCacheManager::StreamingCacheManager(), TaskChunk::TaskChunk(), and TaskCompress::TaskCompress().

Here is the caller graph for this function:

template<class Key, class Value, class Derived>

void SmallHashBase< Key, Value, Derived >::Insert	(	const Key &	key,
		const Value &	value
	)

inline

template<class Key, class Value, class Derived>

Key* SmallHashBase< Key, Value, Derived >::keys ( ) const

inline

Definition at line 148 of file smallhash.h.

Referenced by compat::inode_tracker_v3::Migrate(), compat::chunk_tables::Migrate(), compat::chunk_tables_v2::Migrate(), and glue::InodeReferences::Next().

Here is the caller graph for this function:

template<class Key, class Value, class Derived>

bool SmallHashBase< Key, Value, Derived >::Lookup	(	const Key &	key,
		Value *	value
	)		const

inline

Definition at line 70 of file smallhash.h.

Referenced by cvmfs::cvmfs_open(), cvmfs::cvmfs_read(), cvmfs::cvmfs_release(), glue::InodeReferences::Get(), glue::PathMap::LookupInodeByMd5Path(), glue::PathMap::LookupInodeByPath(), compat::inode_tracker_v3::InodeMap::LookupMd5Path(), FdRefcountMgr::Open(), TaskCompress::Process(), TaskChunk::Process(), glue::InodeReferences::Put(), and StreamingCacheManager::Stream().

Here is the caller graph for this function:

template<class Key, class Value, class Derived>

bool SmallHashBase< Key, Value, Derived >::LookupEx	(	Key *	key,
		Value *	value
	)		const

inline

Returns both the key and the value. That is useful if Key's equality operator implements an equivalence relation on Key. In this case, LookupEx returns the key representing the equivalence class that has been used during Insert(). Used to return a glue::InodeEx element when looking for an inode.

Definition at line 86 of file smallhash.h.

template<class Key, class Value, class Derived>

void SmallHashBase< Key, Value, Derived >::ResetCapacity ( )

inlineprotected

Definition at line 228 of file smallhash.h.

Referenced by SmallHashBase< uint64_t, shash_v1::Md5, SmallHashDynamic< uint64_t, shash_v1::Md5 > >::DoClear().

Here is the caller graph for this function:

template<class Key, class Value, class Derived>

uint32_t SmallHashBase< Key, Value, Derived >::ScaleHash ( const Key & key ) const

inlineprotected

Definition at line 155 of file smallhash.h.

Referenced by SmallHashBase< uint64_t, shash_v1::Md5, SmallHashDynamic< uint64_t, shash_v1::Md5 > >::DoLookup(), and SmallHashBase< uint64_t, shash_v1::Md5, SmallHashDynamic< uint64_t, shash_v1::Md5 > >::LookupEx().

Here is the caller graph for this function:

template<class Key, class Value, class Derived>

void SmallHashBase< Key, Value, Derived >::SetHasher ( uint32_t(*)(const Key &key) hasher )

inline

Definition at line 152 of file smallhash.h.

Referenced by compat::inode_tracker_v3::Migrate().

Here is the caller graph for this function:

template<class Key, class Value, class Derived>

void SmallHashBase< Key, Value, Derived >::SetThresholds ( )

inlineprotected

Definition at line 225 of file smallhash.h.

Referenced by SmallHashBase< uint64_t, shash_v1::Md5, SmallHashDynamic< uint64_t, shash_v1::Md5 > >::Init().

Here is the caller graph for this function:

template<class Key, class Value, class Derived>

void SmallHashBase< Key, Value, Derived >::Shrink ( )

inlineprotected

Definition at line 227 of file smallhash.h.

Referenced by SmallHashBase< uint64_t, shash_v1::Md5, SmallHashDynamic< uint64_t, shash_v1::Md5 > >::Erase().

Here is the caller graph for this function:

template<class Key, class Value, class Derived>

Value* SmallHashBase< Key, Value, Derived >::values ( ) const

inline

Definition at line 149 of file smallhash.h.

Referenced by compat::inode_tracker_v3::Migrate(), compat::chunk_tables::Migrate(), and compat::chunk_tables_v2::Migrate().

Here is the caller graph for this function:

Member Data Documentation

template<class Key, class Value, class Derived>

uint64_t SmallHashBase< Key, Value, Derived >::bytes_allocated_

protected

Definition at line 237 of file smallhash.h.

Referenced by SmallHashBase< uint64_t, shash_v1::Md5, SmallHashDynamic< uint64_t, shash_v1::Md5 > >::AllocMemory(), SmallHashBase< uint64_t, shash_v1::Md5, SmallHashDynamic< uint64_t, shash_v1::Md5 > >::bytes_allocated(), and SmallHashBase< uint64_t, shash_v1::Md5, SmallHashDynamic< uint64_t, shash_v1::Md5 > >::SmallHashBase().

template<class Key, class Value, class Derived>

uint32_t SmallHashBase< Key, Value, Derived >::capacity_

protected

Definition at line 233 of file smallhash.h.

template<class Key, class Value, class Derived>

Key SmallHashBase< Key, Value, Derived >::empty_key_

protected

Definition at line 240 of file smallhash.h.

template<class Key, class Value, class Derived>

uint32_t(* SmallHashBase< Key, Value, Derived >::hasher_)(const Key &key)

protected

Definition at line 236 of file smallhash.h.

Referenced by SmallHashBase< uint64_t, shash_v1::Md5, SmallHashDynamic< uint64_t, shash_v1::Md5 > >::Init(), SmallHashBase< uint64_t, shash_v1::Md5, SmallHashDynamic< uint64_t, shash_v1::Md5 > >::ScaleHash(), SmallHashBase< uint64_t, shash_v1::Md5, SmallHashDynamic< uint64_t, shash_v1::Md5 > >::SetHasher(), and SmallHashBase< uint64_t, shash_v1::Md5, SmallHashDynamic< uint64_t, shash_v1::Md5 > >::SmallHashBase().

template<class Key, class Value, class Derived>

uint32_t SmallHashBase< Key, Value, Derived >::initial_capacity_

protected

Definition at line 234 of file smallhash.h.

Referenced by SmallHashBase< uint64_t, shash_v1::Md5, SmallHashDynamic< uint64_t, shash_v1::Md5 > >::Init(), SmallHashDynamic< glue::InodeEx, shash::Md5 >::ResetCapacity(), SmallHashDynamic< glue::InodeEx, shash::Md5 >::Shrink(), and SmallHashBase< uint64_t, shash_v1::Md5, SmallHashDynamic< uint64_t, shash_v1::Md5 > >::SmallHashBase().

template<class Key, class Value, class Derived>

Key* SmallHashBase< Key, Value, Derived >::keys_

protected

Definition at line 231 of file smallhash.h.

template<class Key, class Value, class Derived>

const double SmallHashBase< Key, Value, Derived >::kLoadFactor = 0.75

static

Definition at line 38 of file smallhash.h.

Referenced by SmallHashBase< uint64_t, shash_v1::Md5, SmallHashDynamic< uint64_t, shash_v1::Md5 > >::GetEntrySize(), and SmallHashBase< uint64_t, shash_v1::Md5, SmallHashDynamic< uint64_t, shash_v1::Md5 > >::Init().

template<class Key, class Value, class Derived>

const double SmallHashBase< Key, Value, Derived >::kThresholdGrow

static

Definition at line 39 of file smallhash.h.

template<class Key, class Value, class Derived>

const double SmallHashBase< Key, Value, Derived >::kThresholdShrink

static

Definition at line 40 of file smallhash.h.

template<class Key, class Value, class Derived>

uint32_t SmallHashBase< Key, Value, Derived >::max_collisions_

protected

maximum collisions for a single insert

Definition at line 239 of file smallhash.h.

Referenced by SmallHashBase< uint64_t, shash_v1::Md5, SmallHashDynamic< uint64_t, shash_v1::Md5 > >::DoInsert(), SmallHashBase< uint64_t, shash_v1::Md5, SmallHashDynamic< uint64_t, shash_v1::Md5 > >::GetCollisionStats(), and SmallHashBase< uint64_t, shash_v1::Md5, SmallHashDynamic< uint64_t, shash_v1::Md5 > >::SmallHashBase().

template<class Key, class Value, class Derived>

uint64_t SmallHashBase< Key, Value, Derived >::num_collisions_

protected

Definition at line 238 of file smallhash.h.

Referenced by SmallHashBase< uint64_t, shash_v1::Md5, SmallHashDynamic< uint64_t, shash_v1::Md5 > >::DoInsert(), SmallHashBase< uint64_t, shash_v1::Md5, SmallHashDynamic< uint64_t, shash_v1::Md5 > >::GetCollisionStats(), and SmallHashBase< uint64_t, shash_v1::Md5, SmallHashDynamic< uint64_t, shash_v1::Md5 > >::SmallHashBase().

template<class Key, class Value, class Derived>

uint32_t SmallHashBase< Key, Value, Derived >::size_

protected

Definition at line 235 of file smallhash.h.

Referenced by SmallHashBase< uint64_t, shash_v1::Md5, SmallHashDynamic< uint64_t, shash_v1::Md5 > >::DoClear(), SmallHashBase< uint64_t, shash_v1::Md5, SmallHashDynamic< uint64_t, shash_v1::Md5 > >::Erase(), SmallHashBase< uint64_t, shash_v1::Md5, SmallHashDynamic< uint64_t, shash_v1::Md5 > >::Insert(), SmallHashDynamic< glue::InodeEx, shash::Md5 >::size(), and SmallHashBase< uint64_t, shash_v1::Md5, SmallHashDynamic< uint64_t, shash_v1::Md5 > >::SmallHashBase().

template<class Key, class Value, class Derived>

Value* SmallHashBase< Key, Value, Derived >::values_

protected

Definition at line 232 of file smallhash.h.

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

/home/sftnight/jenkins/workspace/CvmfsDoxygen/label/docker-x86_64/cvmfs/cvmfs/smallhash.h

Public Member Functions

Static Public Member Functions

Static Public Attributes

Protected Member Functions

Protected Attributes

Private Member Functions

Detailed Description

template<class Key, class Value, class Derived> class SmallHashBase< Key, Value, Derived >

Constructor & Destructor Documentation

Member Function Documentation

Member Data Documentation

template<class Key, class Value, class Derived>
class SmallHashBase< Key, Value, Derived >