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

#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 Contains (const Key &key) const
 
void Insert (const Key &key, const Value &value)
 
void 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
template<class Key, class Value, class Derived>
uint64_t SmallHashBase< Key, Value, Derived >::bytes_allocated ( ) const
inline

Definition at line 117 of file smallhash.h.

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

Definition at line 131 of file smallhash.h.

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

Definition at line 113 of file smallhash.h.

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

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
template<class Key, class Value, class Derived>
void SmallHashBase< Key, Value, Derived >::DoClear ( const bool  reset_capacity)
inlineprotected
template<class Key, class Value, class Derived>
bool SmallHashBase< Key, Value, Derived >::DoInsert ( const Key &  key,
const Value &  value,
const bool  count_collisions 
)
inlineprotected
template<class Key, class Value, class Derived>
bool SmallHashBase< Key, Value, Derived >::DoLookup ( const Key &  key,
uint32_t *  bucket,
uint32_t *  collisions 
) const
inlineprotected
template<class Key, class Value, class Derived>
Key SmallHashBase< Key, Value, Derived >::empty_key ( ) const
inline

Definition at line 132 of file smallhash.h.

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

Here is the caller graph for this function:

template<class Key, class Value, class Derived>
void SmallHashBase< Key, Value, Derived >::Erase ( const Key &  key)
inline

Definition at line 95 of file smallhash.h.

Referenced by cvmfs::cvmfs_release(), glue::PathMap::Erase(), glue::InodeMap::Erase(), TaskCompress::Process(), TaskChunk::Process(), and glue::InodeReferences::Put().

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 123 of file smallhash.h.

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

Definition at line 118 of file smallhash.h.

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

Definition at line 212 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
template<class Key, class Value, class Derived>
Key* SmallHashBase< Key, Value, Derived >::keys ( ) const
inline

Definition at line 133 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
template<class Key, class Value, class Derived>
void SmallHashBase< Key, Value, Derived >::ResetCapacity ( )
inlineprotected

Definition at line 214 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 142 of file smallhash.h.

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

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 137 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 211 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 213 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 134 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>
const double SmallHashBase< Key, Value, Derived >::kLoadFactor = 0.75
static
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.


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