1//===- HashBase.h ---------------------------------------------------------===// 2// 3// The MCLinker Project 4// 5// This file is distributed under the University of Illinois Open Source 6// License. See LICENSE.TXT for details. 7// 8//===----------------------------------------------------------------------===// 9#ifndef MCLD_HASH_BASE_H 10#define MCLD_HASH_BASE_H 11#ifdef ENABLE_UNITTEST 12#include <gtest.h> 13#endif 14#include <llvm/ADT/StringRef.h> 15#include <cstdlib> 16 17namespace mcld { 18 19/** forward declaration **/ 20template<typename HashTableImplTy> 21class ChainIteratorBase; 22 23template<typename HashTableImplTy> 24class EntryIteratorBase; 25 26/** \class HashBucket 27 * \brief HashBucket is an entry in the hash table. 28 */ 29template<typename HashEntryTy> 30class HashBucket 31{ 32public: 33 typedef HashEntryTy entry_type; 34 35public: 36 unsigned int FullHashValue; 37 entry_type *Entry; 38 39public: 40 static entry_type* getEmptyBucket(); 41 static entry_type* getTombstone(); 42 43}; 44 45/** \class HashTableImpl 46 * \brief HashTableImpl is the base class of HashTable. 47 * 48 * HashTableImpl uses open-addressing, linear probing hash table. 49 * linear probing hash table obviously has high performance when the 50 * load factor is less than 0.7. 51 * The drawback is that the number of the stored items can notbe more 52 * than the size of the hash table. 53 * 54 * MCLinker tries to merge every things in the same HashEntry. It can 55 * keep every thing in the same cache line and improve the locality 56 * efficiently. HashTableImpl provides a template argument to change the 57 * definition of HashEntries. 58 * 59 * HashEntryTy must provide getKey() and getKenLength() functions. 60 * 61 * Different environments have different demands of HashFunctions. For 62 * example, on-device linkers needs a more light-weight hash function 63 * than static linkers. HashTableImpl also provides a template argument to 64 * change the hash functions. 65 */ 66template<typename HashEntryTy, 67 typename HashFunctionTy> 68class HashTableImpl 69{ 70private: 71 static const unsigned int NumOfInitBuckets = 16; 72 73public: 74 typedef size_t size_type; 75 typedef HashFunctionTy hasher; 76 typedef HashEntryTy entry_type; 77 typedef typename HashEntryTy::key_type key_type; 78 typedef HashBucket<HashEntryTy> bucket_type; 79 typedef HashTableImpl<HashEntryTy, HashFunctionTy> Self; 80 81 82public: 83 HashTableImpl(); 84 explicit HashTableImpl(unsigned int pInitSize); 85 virtual ~HashTableImpl(); 86 87 // ----- observers ----- // 88 bool empty() const; 89 90 size_t numOfBuckets() const 91 { return m_NumOfBuckets; } 92 93 size_t numOfEntries() const 94 { return m_NumOfEntries; } 95 96 hasher& hash() 97 { return m_Hasher; } 98 99 const hasher& hash() const 100 { return m_Hasher; } 101 102protected: 103 /// initialize the hash table. 104 void init(unsigned int pInitSize); 105 106 /// lookUpBucketFor - search the index of bucket whose key is p>ey 107 // @return the index of the found bucket 108 unsigned int lookUpBucketFor(const key_type& pKey); 109 110 /// findKey - finds an element with key pKey 111 // return the index of the element, or -1 when the element does not exist. 112 int findKey(const key_type& pKey) const; 113 114 /// mayRehash - check the load_factor, compute the new size, and then doRehash 115 void mayRehash(); 116 117 /// doRehash - re-new the hash table, and rehash all elements into the new buckets 118 void doRehash(unsigned int pNewSize); 119 120friend class ChainIteratorBase<Self>; 121friend class ChainIteratorBase<const Self>; 122friend class EntryIteratorBase<Self>; 123friend class EntryIteratorBase<const Self>; 124protected: 125 // Array of Buckets 126 bucket_type* m_Buckets; 127 unsigned int m_NumOfBuckets; 128 unsigned int m_NumOfEntries; 129 unsigned int m_NumOfTombstones; 130 hasher m_Hasher; 131 132}; 133 134#include "HashBase.tcc" 135 136} // namespace of mcld 137 138#endif 139