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