HashBase.h revision 533eae20118036f425f27bf0536ef0ccbb090b65
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 14namespace mcld { 15 16/** forward declaration **/ 17template<typename HashTableImplTy> 18class ChainIteratorBase; 19 20template<typename HashTableImplTy> 21class EntryIteratorBase; 22 23/** \class HashBucket 24 * \brief HashBucket is an entry in the hash table. 25 */ 26template<typename HashEntryTy> 27class HashBucket 28{ 29public: 30 typedef HashEntryTy entry_type; 31 32public: 33 unsigned int FullHashValue; 34 entry_type *Entry; 35 36public: 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 */ 63template<typename HashEntryTy, 64 typename HashFunctionTy> 65class HashTableImpl 66{ 67private: 68 static const unsigned int NumOfInitBuckets = 16; 69 70public: 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 79public: 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 99protected: 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 119friend class ChainIteratorBase<Self>; 120friend class ChainIteratorBase<const Self>; 121friend class EntryIteratorBase<Self>; 122friend class EntryIteratorBase<const Self>; 123protected: 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