CernVM-FS  2.12.0
 All Classes Namespaces Files Functions Variables Typedefs Enumerations Enumerator Friends Macros Pages
SmallHashDynamic< Key, Value > Class Template Reference

#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>
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

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
template<class Key, class Value>
const double SmallHashDynamic< Key, Value >::kThresholdGrow = 0.75
static
template<class Key, class Value>
const double SmallHashDynamic< Key, Value >::kThresholdShrink = 0.25
static

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