#include <smallhash.h>

Inheritance diagram for SmallHashDynamic< Key, Value >:

Collaboration diagram for SmallHashDynamic< Key, Value >:

Public Types
typedef SmallHashBase< Key, Value, SmallHashDynamic< Key, Value > >	Base

Public Member Functions
	SmallHashDynamic ()

	SmallHashDynamic (const SmallHashDynamic< Key, Value > &other)

SmallHashDynamic< Key, Value > &	operator= (const SmallHashDynamic< Key, Value > &other)

uint32_t	capacity () const

uint32_t	size () const

uint32_t	num_migrates () const

Public Member Functions inherited from SmallHashBase< Key, Value, Derived >
	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 Attributes
static const double	kThresholdGrow = 0.75

static const double	kThresholdShrink = 0.25

Static Public Attributes inherited from SmallHashBase< Key, Value, Derived >
static const double	kLoadFactor = 0.75

static const double	kThresholdGrow

static const double	kThresholdShrink

Protected Member Functions
void	SetThresholds ()

void	Grow ()

void	Shrink ()

void	ResetCapacity ()

Protected Member Functions inherited from SmallHashBase< Key, Value, Derived >
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 ()

Private Member Functions
uint32_t *	ShuffleIndices (const uint32_t N)

void	Migrate (const uint32_t new_capacity)

void	CopyFrom (const SmallHashDynamic< Key, Value > &other)

Private Attributes
uint32_t	num_migrates_

uint32_t	threshold_grow_

uint32_t	threshold_shrink_

Static Private Attributes
static Prng	g_prng

Friends
class	SmallHashBase< Key, Value, SmallHashDynamic< Key, Value > >

Additional Inherited Members
Static Public Member Functions inherited from SmallHashBase< Key, Value, Derived >
static double	GetEntrySize ()

Protected Attributes inherited from SmallHashBase< Key, Value, Derived >
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_

Detailed Description

template<class Key, class Value>
class SmallHashDynamic< Key, Value >

Definition at line 268 of file smallhash.h.

Member Typedef Documentation

template<class Key, class Value>

typedef SmallHashBase< Key, Value, SmallHashDynamic<Key, Value> > SmallHashDynamic< Key, Value >::Base

Definition at line 273 of file smallhash.h.

Constructor & Destructor Documentation

template<class Key, class Value>

SmallHashDynamic< Key, Value >::SmallHashDynamic ( )

inline

Definition at line 277 of file smallhash.h.

template<class Key, class Value>

SmallHashDynamic< Key, Value >::SmallHashDynamic ( const SmallHashDynamic< Key, Value > & other )

inline

Definition at line 285 of file smallhash.h.

Member Function Documentation

template<class Key, class Value>

uint32_t SmallHashDynamic< Key, Value >::capacity ( ) const

inline

Definition at line 301 of file smallhash.h.

Referenced by SmallHashDynamic< glue::InodeEx, shash::Md5 >::Grow(), compat::inode_tracker_v3::Migrate(), compat::chunk_tables::Migrate(), compat::chunk_tables_v2::Migrate(), SmallHashDynamic< glue::InodeEx, shash::Md5 >::Migrate(), glue::InodeReferences::Next(), SmallHashDynamic< glue::InodeEx, shash::Md5 >::SetThresholds(), and SmallHashDynamic< glue::InodeEx, shash::Md5 >::Shrink().

Here is the caller graph for this function:

template<class Key, class Value>

void SmallHashDynamic< Key, Value >::CopyFrom ( const SmallHashDynamic< Key, Value > & other )

inlineprivate

Definition at line 383 of file smallhash.h.

Referenced by SmallHashDynamic< glue::InodeEx, shash::Md5 >::operator=(), and SmallHashDynamic< glue::InodeEx, shash::Md5 >::SmallHashDynamic().

Here is the caller graph for this function:

template<class Key, class Value>

void SmallHashDynamic< Key, Value >::Grow ( )

inlineprotected

Definition at line 313 of file smallhash.h.

template<class Key, class Value>

void SmallHashDynamic< Key, Value >::Migrate ( const uint32_t new_capacity )

inlineprivate

Definition at line 352 of file smallhash.h.

Referenced by SmallHashDynamic< glue::InodeEx, shash::Md5 >::Grow(), and SmallHashDynamic< glue::InodeEx, shash::Md5 >::Shrink().

Here is the caller graph for this function:

template<class Key, class Value>

uint32_t SmallHashDynamic< Key, Value >::num_migrates ( ) const

inline

Definition at line 303 of file smallhash.h.

template<class Key, class Value>

SmallHashDynamic<Key, Value>& SmallHashDynamic< Key, Value >::operator= ( const SmallHashDynamic< Key, Value > & other )

inline

Definition at line 291 of file smallhash.h.

template<class Key, class Value>

void SmallHashDynamic< Key, Value >::ResetCapacity ( )

inlineprotected

Definition at line 326 of file smallhash.h.

template<class Key, class Value>

void SmallHashDynamic< Key, Value >::SetThresholds ( )

inlineprotected

Definition at line 306 of file smallhash.h.

Referenced by 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>

void SmallHashDynamic< Key, Value >::Shrink ( )

inlineprotected

Definition at line 318 of file smallhash.h.

template<class Key, class Value>

uint32_t* SmallHashDynamic< Key, Value >::ShuffleIndices ( const uint32_t N )

inlineprivate

Definition at line 336 of file smallhash.h.

Referenced by SmallHashDynamic< glue::InodeEx, shash::Md5 >::CopyFrom(), and SmallHashDynamic< glue::InodeEx, shash::Md5 >::Migrate().

Here is the caller graph for this function:

template<class Key, class Value>

uint32_t SmallHashDynamic< Key, Value >::size ( ) const

inline

Definition at line 302 of file smallhash.h.

Referenced by SmallhashFilter::Count(), SmallHashDynamic< glue::InodeEx, shash::Md5 >::Grow(), SmallHashDynamic< glue::InodeEx, shash::Md5 >::Migrate(), RestoreState(), and SmallHashDynamic< glue::InodeEx, shash::Md5 >::Shrink().

Here is the caller graph for this function:

Friends And Related Function Documentation

template<class Key, class Value>

friend class SmallHashBase< Key, Value, SmallHashDynamic< Key, Value > >

friend

Definition at line 271 of file smallhash.h.

Member Data Documentation

template<class Key, class Value>

Prng SmallHashDynamic< Key, Value >::g_prng

staticprivate

Definition at line 397 of file smallhash.h.

Referenced by SmallHashDynamic< glue::InodeEx, shash::Md5 >::ShuffleIndices().

template<class Key, class Value>

const double SmallHashDynamic< Key, Value >::kThresholdGrow = 0.75

static

Definition at line 274 of file smallhash.h.

Referenced by SmallHashDynamic< glue::InodeEx, shash::Md5 >::SetThresholds().

template<class Key, class Value>

const double SmallHashDynamic< Key, Value >::kThresholdShrink = 0.25

static

Definition at line 275 of file smallhash.h.

Referenced by SmallHashDynamic< glue::InodeEx, shash::Md5 >::SetThresholds().

template<class Key, class Value>

uint32_t SmallHashDynamic< Key, Value >::num_migrates_

private

Definition at line 394 of file smallhash.h.

Referenced by SmallHashDynamic< glue::InodeEx, shash::Md5 >::Migrate(), SmallHashDynamic< glue::InodeEx, shash::Md5 >::num_migrates(), and SmallHashDynamic< glue::InodeEx, shash::Md5 >::SmallHashDynamic().

template<class Key, class Value>

uint32_t SmallHashDynamic< Key, Value >::threshold_grow_

private

Definition at line 395 of file smallhash.h.

Referenced by SmallHashDynamic< glue::InodeEx, shash::Md5 >::Grow(), SmallHashDynamic< glue::InodeEx, shash::Md5 >::SetThresholds(), and SmallHashDynamic< glue::InodeEx, shash::Md5 >::SmallHashDynamic().

template<class Key, class Value>

uint32_t SmallHashDynamic< Key, Value >::threshold_shrink_

private

Definition at line 396 of file smallhash.h.

Referenced by SmallHashDynamic< glue::InodeEx, shash::Md5 >::SetThresholds(), SmallHashDynamic< glue::InodeEx, shash::Md5 >::Shrink(), and SmallHashDynamic< glue::InodeEx, shash::Md5 >::SmallHashDynamic().

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 Types

Public Member Functions

Static Public Attributes

Protected Member Functions

Private Member Functions

Private Attributes

Static Private Attributes

Friends

Additional Inherited Members

Detailed Description

template<class Key, class Value> class SmallHashDynamic< Key, Value >

Member Typedef Documentation

Constructor & Destructor Documentation

Member Function Documentation

Friends And Related Function Documentation

Member Data Documentation

template<class Key, class Value>
class SmallHashDynamic< Key, Value >