CernVM-FS  2.11.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 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
template<class Key, class Value, class Derived>
uint64_t SmallHashBase< Key, Value, Derived >::bytes_allocated ( ) const
inline

Definition at line 138 of file smallhash.h.

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

Definition at line 152 of file smallhash.h.

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

Definition at line 134 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>
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 153 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
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 144 of file smallhash.h.

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

Definition at line 139 of file smallhash.h.

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

Definition at line 233 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 154 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>
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 equivalance class that has been used during Insert(). Used to return a glue::InodeEx element when looking for an inode.

Definition at line 89 of file smallhash.h.

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

Definition at line 235 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
template<class Key, class Value, class Derived>
void SmallHashBase< Key, Value, Derived >::SetHasher ( uint32_t(*)(const Key &key)  hasher)
inline

Definition at line 158 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 232 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 234 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 155 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: