HashBase.h revision d8a752331fe7a30ce41835f139aa8a4c675ad07a 
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
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  /// lookUpBucketFor - search the index of bucket whose key is p>ey
107  //  @return the index of the found bucket
108  unsigned int lookUpBucketFor(const key_type& pKey);
109
110  /// findKey - finds an element with key pKey
111  //  return the index of the element, or -1 when the element does not exist.
112  int findKey(const key_type& pKey) const;
113
114  /// mayRehash - check the load_factor, compute the new size, and then doRehash
115  void mayRehash();
116
117  /// doRehash - re-new the hash table, and rehash all elements into the new buckets
118  void doRehash(unsigned int pNewSize);
119
120friend class ChainIteratorBase<Self>;
121friend class ChainIteratorBase<const Self>;
122friend class EntryIteratorBase<Self>;
123friend class EntryIteratorBase<const Self>;
124protected:
125  // Array of Buckets
126  bucket_type* m_Buckets;
127  unsigned int m_NumOfBuckets;
128  unsigned int m_NumOfEntries;
129  unsigned int m_NumOfTombstones;
130  hasher m_Hasher;
131
132};
133
134#include "HashBase.tcc"
135
136} // namespace of mcld
137
138#endif
139