CernVM-FS
2.12.0
|
#include <smallhash.h>
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) | |
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.
|
inline |
Definition at line 42 of file smallhash.h.
|
inline |
Definition at line 56 of file smallhash.h.
|
inlineprotected |
Definition at line 170 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().
|
inline |
Definition at line 138 of file smallhash.h.
|
inline |
Definition at line 152 of file smallhash.h.
|
inline |
Definition at line 134 of file smallhash.h.
Referenced by glue::PathMap::Clear(), and glue::InodeReferences::Clear().
|
inline |
Definition at line 102 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().
|
inlineprotected |
Definition at line 182 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().
|
inlineprotected |
Definition at line 225 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().
|
inlineprotected |
Definition at line 198 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().
|
inlineprotected |
Definition at line 213 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().
|
inline |
Definition at line 153 of file smallhash.h.
Referenced by glue::InodeReferences::Next().
|
inline |
Definition at line 115 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().
|
private |
|
inline |
Definition at line 144 of file smallhash.h.
|
inlinestatic |
Definition at line 139 of file smallhash.h.
|
inlineprotected |
Definition at line 235 of file smallhash.h.
Referenced by SmallHashBase< uint64_t, shash_v1::Md5, SmallHashDynamic< uint64_t, shash_v1::Md5 > >::Insert().
|
inline |
Definition at line 60 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().
|
inline |
Definition at line 109 of file smallhash.h.
Referenced by SmallHashDynamic< glue::InodeEx, shash::Md5 >::CopyFrom(), cvmfs::cvmfs_open(), cvmfs::cvmfs_read(), cvmfs::cvmfs_release(), SmallhashFilter::Fill(), swissknife::CatalogTraversalParallel< ObjectFetcherT >::FinalizeJob(), swissknife::CommandCheck::Find(), glue::InodeReferences::Get(), glue::PathMap::Insert(), compat::chunk_tables::Migrate(), compat::chunk_tables_v2::Migrate(), SmallHashDynamic< glue::InodeEx, shash::Md5 >::Migrate(), FdRefcountMgr::Open(), TaskCompress::Process(), TaskChunk::Process(), glue::InodeReferences::Put(), glue::PathMap::Replace(), glue::InodeReferences::Replace(), and StreamingCacheManager::Stream().
|
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().
|
inline |
Definition at line 73 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().
|
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 89 of file smallhash.h.
|
inlineprotected |
Definition at line 237 of file smallhash.h.
Referenced by SmallHashBase< uint64_t, shash_v1::Md5, SmallHashDynamic< uint64_t, shash_v1::Md5 > >::DoClear().
|
inlineprotected |
Definition at line 163 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().
|
inline |
Definition at line 158 of file smallhash.h.
Referenced by compat::inode_tracker_v3::Migrate().
|
inlineprotected |
Definition at line 234 of file smallhash.h.
Referenced by SmallHashBase< uint64_t, shash_v1::Md5, SmallHashDynamic< uint64_t, shash_v1::Md5 > >::Init().
|
inlineprotected |
Definition at line 236 of file smallhash.h.
Referenced by SmallHashBase< uint64_t, shash_v1::Md5, SmallHashDynamic< uint64_t, shash_v1::Md5 > >::Erase().
|
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().
|
protected |
Definition at line 246 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().
|
protected |
Definition at line 242 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 > >::capacity(), SmallHashDynamic< glue::InodeEx, shash::Md5 >::capacity(), SmallHashDynamic< glue::InodeEx, shash::Md5 >::CopyFrom(), 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 > >::DoLookup(), 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 > >::Init(), SmallHashBase< uint64_t, shash_v1::Md5, SmallHashDynamic< uint64_t, shash_v1::Md5 > >::LookupEx(), SmallHashDynamic< glue::InodeEx, shash::Md5 >::Migrate(), SmallHashDynamic< glue::InodeEx, shash::Md5 >::ResetCapacity(), 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 > >::SmallHashBase(), and SmallHashBase< uint64_t, shash_v1::Md5, SmallHashDynamic< uint64_t, shash_v1::Md5 > >::~SmallHashBase().
|
protected |
Definition at line 249 of file smallhash.h.
Referenced by SmallHashDynamic< glue::InodeEx, shash::Md5 >::CopyFrom(), 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 > >::DoLookup(), SmallHashBase< uint64_t, shash_v1::Md5, SmallHashDynamic< uint64_t, shash_v1::Md5 > >::empty_key(), 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 > >::Init(), SmallHashBase< uint64_t, shash_v1::Md5, SmallHashDynamic< uint64_t, shash_v1::Md5 > >::LookupEx(), and SmallHashDynamic< glue::InodeEx, shash::Md5 >::Migrate().
|
protected |
Definition at line 245 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().
|
protected |
Definition at line 243 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().
|
protected |
Definition at line 240 of file smallhash.h.
Referenced by SmallHashBase< uint64_t, shash_v1::Md5, SmallHashDynamic< uint64_t, shash_v1::Md5 > >::AllocMemory(), SmallHashDynamic< glue::InodeEx, shash::Md5 >::CopyFrom(), 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 > >::DoInsert(), SmallHashBase< uint64_t, shash_v1::Md5, SmallHashDynamic< uint64_t, shash_v1::Md5 > >::DoLookup(), 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 > >::keys(), SmallHashBase< uint64_t, shash_v1::Md5, SmallHashDynamic< uint64_t, shash_v1::Md5 > >::LookupEx(), SmallHashDynamic< glue::InodeEx, shash::Md5 >::Migrate(), SmallHashDynamic< glue::InodeEx, shash::Md5 >::ResetCapacity(), SmallHashBase< uint64_t, shash_v1::Md5, SmallHashDynamic< uint64_t, shash_v1::Md5 > >::SmallHashBase(), and SmallHashBase< uint64_t, shash_v1::Md5, SmallHashDynamic< uint64_t, shash_v1::Md5 > >::~SmallHashBase().
|
static |
|
static |
Definition at line 39 of file smallhash.h.
|
static |
Definition at line 40 of file smallhash.h.
|
protected |
maximum collisions for a single insert
Definition at line 248 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().
|
protected |
Definition at line 247 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().
|
protected |
Definition at line 244 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().
|
protected |
Definition at line 241 of file smallhash.h.
Referenced by SmallHashBase< uint64_t, shash_v1::Md5, SmallHashDynamic< uint64_t, shash_v1::Md5 > >::AllocMemory(), SmallHashDynamic< glue::InodeEx, shash::Md5 >::CopyFrom(), 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(), SmallHashBase< uint64_t, shash_v1::Md5, SmallHashDynamic< uint64_t, shash_v1::Md5 > >::Lookup(), SmallHashBase< uint64_t, shash_v1::Md5, SmallHashDynamic< uint64_t, shash_v1::Md5 > >::LookupEx(), SmallHashDynamic< glue::InodeEx, shash::Md5 >::Migrate(), SmallHashDynamic< glue::InodeEx, shash::Md5 >::ResetCapacity(), SmallHashBase< uint64_t, shash_v1::Md5, SmallHashDynamic< uint64_t, shash_v1::Md5 > >::SmallHashBase(), SmallHashBase< uint64_t, shash_v1::Md5, SmallHashDynamic< uint64_t, shash_v1::Md5 > >::values(), and SmallHashBase< uint64_t, shash_v1::Md5, SmallHashDynamic< uint64_t, shash_v1::Md5 > >::~SmallHashBase().