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 12 #include <llvm/ADT/StringRef.h> 13 14 #include <cstdlib> 15 16 namespace mcld { 17 18 /** forward declaration **/ 19 template <typename HashTableImplTy> 20 class ChainIteratorBase; 21 22 template <typename HashTableImplTy> 23 class EntryIteratorBase; 24 25 /** \class HashBucket 26 * \brief HashBucket is an entry in the hash table. 27 */ 28 template <typename HashEntryTy> 29 class HashBucket { 30 public: 31 typedef HashEntryTy entry_type; 32 33 public: 34 unsigned int FullHashValue; 35 entry_type* Entry; 36 37 public: 38 static entry_type* getEmptyBucket(); 39 static entry_type* getTombstone(); 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, typename HashFunctionTy> 64 class HashTableImpl { 65 private: 66 static const unsigned int NumOfInitBuckets = 16; 67 68 public: 69 typedef size_t size_type; 70 typedef HashFunctionTy hasher; 71 typedef HashEntryTy entry_type; 72 typedef typename HashEntryTy::key_type key_type; 73 typedef HashBucket<HashEntryTy> bucket_type; 74 typedef HashTableImpl<HashEntryTy, HashFunctionTy> Self; 75 76 public: 77 HashTableImpl(); 78 explicit HashTableImpl(unsigned int pInitSize); 79 virtual ~HashTableImpl(); 80 81 // ----- observers ----- // 82 bool empty() const; 83 numOfBuckets()84 size_t numOfBuckets() const { return m_NumOfBuckets; } 85 numOfEntries()86 size_t numOfEntries() const { return m_NumOfEntries; } 87 hash()88 hasher& hash() { return m_Hasher; } 89 hash()90 const hasher& hash() const { return m_Hasher; } 91 92 protected: 93 /// initialize the hash table. 94 void init(unsigned int pInitSize); 95 96 void clear(); 97 98 /// lookUpBucketFor - search the index of bucket whose key is p>ey 99 // @return the index of the found bucket 100 unsigned int lookUpBucketFor(const key_type& pKey); 101 102 /// findKey - finds an element with key pKey 103 // return the index of the element, or -1 when the element does not exist. 104 int findKey(const key_type& pKey) const; 105 106 /// mayRehash - check the load_factor, compute the new size, and then doRehash 107 void mayRehash(); 108 109 /// doRehash - re-new the hash table, and rehash all elements into the new 110 /// buckets 111 void doRehash(unsigned int pNewSize); 112 113 friend class ChainIteratorBase<Self>; 114 friend class ChainIteratorBase<const Self>; 115 friend class EntryIteratorBase<Self>; 116 friend class EntryIteratorBase<const Self>; 117 118 protected: 119 // Array of Buckets 120 bucket_type* m_Buckets; 121 unsigned int m_NumOfBuckets; 122 unsigned int m_NumOfEntries; 123 unsigned int m_NumOfTombstones; 124 hasher m_Hasher; 125 }; 126 127 #include "HashBase.tcc" 128 129 } // namespace mcld 130 131 #endif // MCLD_ADT_HASHBASE_H_ 132