blob: 76410ab1edffe66fcda132c7441616de373348d8 [file] [log] [blame]
//===- HashBase.h ---------------------------------------------------------===//
//
// The MCLinker Project
//
// This file is distributed under the University of Illinois Open Source
// License. See LICENSE.TXT for details.
//
//===----------------------------------------------------------------------===//
#ifndef MCLD_HASH_BASE_H
#define MCLD_HASH_BASE_H
#ifdef ENABLE_UNITTEST
#include <gtest.h>
#endif
#include <llvm/ADT/StringRef.h>
#include <cstdlib>
namespace mcld {
/** forward declaration **/
template<typename HashTableImplTy>
class ChainIteratorBase;
template<typename HashTableImplTy>
class EntryIteratorBase;
/** \class HashBucket
* \brief HashBucket is an entry in the hash table.
*/
template<typename HashEntryTy>
class HashBucket
{
public:
typedef HashEntryTy entry_type;
public:
unsigned int FullHashValue;
entry_type *Entry;
public:
static entry_type* getEmptyBucket();
static entry_type* getTombstone();
};
/** \class HashTableImpl
* \brief HashTableImpl is the base class of HashTable.
*
* HashTableImpl uses open-addressing, linear probing hash table.
* linear probing hash table obviously has high performance when the
* load factor is less than 0.7.
* The drawback is that the number of the stored items can notbe more
* than the size of the hash table.
*
* MCLinker tries to merge every things in the same HashEntry. It can
* keep every thing in the same cache line and improve the locality
* efficiently. HashTableImpl provides a template argument to change the
* definition of HashEntries.
*
* HashEntryTy must provide getKey() and getKenLength() functions.
*
* Different environments have different demands of HashFunctions. For
* example, on-device linkers needs a more light-weight hash function
* than static linkers. HashTableImpl also provides a template argument to
* change the hash functions.
*/
template<typename HashEntryTy,
typename HashFunctionTy>
class HashTableImpl
{
private:
static const unsigned int NumOfInitBuckets = 16;
public:
typedef size_t size_type;
typedef HashFunctionTy hasher;
typedef HashEntryTy entry_type;
typedef typename HashEntryTy::key_type key_type;
typedef HashBucket<HashEntryTy> bucket_type;
typedef HashTableImpl<HashEntryTy, HashFunctionTy> Self;
public:
HashTableImpl();
explicit HashTableImpl(unsigned int pInitSize);
virtual ~HashTableImpl();
// ----- observers ----- //
bool empty() const;
size_t numOfBuckets() const
{ return m_NumOfBuckets; }
size_t numOfEntries() const
{ return m_NumOfEntries; }
hasher& hash()
{ return m_Hasher; }
const hasher& hash() const
{ return m_Hasher; }
protected:
/// initialize the hash table.
void init(unsigned int pInitSize);
/// lookUpBucketFor - search the index of bucket whose key is p>ey
// @return the index of the found bucket
unsigned int lookUpBucketFor(const key_type& pKey);
/// findKey - finds an element with key pKey
// return the index of the element, or -1 when the element does not exist.
int findKey(const key_type& pKey) const;
/// mayRehash - check the load_factor, compute the new size, and then doRehash
void mayRehash();
/// doRehash - re-new the hash table, and rehash all elements into the new buckets
void doRehash(unsigned int pNewSize);
friend class ChainIteratorBase<Self>;
friend class ChainIteratorBase<const Self>;
friend class EntryIteratorBase<Self>;
friend class EntryIteratorBase<const Self>;
protected:
// Array of Buckets
bucket_type* m_Buckets;
unsigned int m_NumOfBuckets;
unsigned int m_NumOfEntries;
unsigned int m_NumOfTombstones;
hasher m_Hasher;
};
#include "HashBase.tcc"
} // namespace of mcld
#endif