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