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