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
16namespace mcld {
17
18/** forward declaration **/
19template <typename HashTableImplTy>
20class ChainIteratorBase;
21
22template <typename HashTableImplTy>
23class EntryIteratorBase;
24
25/** \class HashBucket
26 *  \brief HashBucket is an entry in the hash table.
27 */
28template <typename HashEntryTy>
29class 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 */
63template <typename HashEntryTy, typename HashFunctionTy>
64class 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
84  size_t numOfBuckets() const { return m_NumOfBuckets; }
85
86  size_t numOfEntries() const { return m_NumOfEntries; }
87
88  hasher& hash() { return m_Hasher; }
89
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