HashBase.h revision 87f34658dec9097d987d254a990ea7f311bfc95f 
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#ifdef ENABLE_UNITTEST
12#include <gtest.h>
13#endif
14#include <llvm/ADT/StringRef.h>
15#include <cstdlib>
16
17namespace mcld {
18
19/** forward declaration **/
20template<typename HashTableImplTy>
21class ChainIteratorBase;
22
23template<typename HashTableImplTy>
24class EntryIteratorBase;
25
26/** \class HashBucket
27 *  \brief HashBucket is an entry in the hash table.
28 */
29template<typename HashEntryTy>
30class HashBucket
31{
32public:
33  typedef HashEntryTy entry_type;
34
35public:
36  unsigned int FullHashValue;
37  entry_type *Entry;
38
39public:
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 */
66template<typename HashEntryTy,
67         typename HashFunctionTy>
68class HashTableImpl
69{
70private:
71  static const unsigned int NumOfInitBuckets = 16;
72
73public:
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
82public:
83  HashTableImpl();
84  explicit HashTableImpl(unsigned int pInitSize);
85  virtual ~HashTableImpl();
86
87  // -----  observers  ----- //
88  bool empty() const;
89
90  size_t numOfBuckets() const
91  { return m_NumOfBuckets; }
92
93  size_t numOfEntries() const
94  { return m_NumOfEntries; }
95
96  hasher& hash()
97  { return m_Hasher; }
98
99  const hasher& hash() const
100  { return m_Hasher; }
101
102protected:
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
122friend class ChainIteratorBase<Self>;
123friend class ChainIteratorBase<const Self>;
124friend class EntryIteratorBase<Self>;
125friend class EntryIteratorBase<const Self>;
126protected:
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