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