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#include <llvm/ADT/StringRef.h>
12#include <cstdlib>
13
14namespace mcld {
15
16/** forward declaration **/
17template<typename HashTableImplTy>
18class ChainIteratorBase;
19
20template<typename HashTableImplTy>
21class EntryIteratorBase;
22
23/** \class HashBucket
24 *  \brief HashBucket is an entry in the hash table.
25 */
26template<typename HashEntryTy>
27class HashBucket
28{
29public:
30  typedef HashEntryTy entry_type;
31
32public:
33  unsigned int FullHashValue;
34  entry_type *Entry;
35
36public:
37  static entry_type* getEmptyBucket();
38  static entry_type* getTombstone();
39
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,
64         typename HashFunctionTy>
65class HashTableImpl
66{
67private:
68  static const unsigned int NumOfInitBuckets = 16;
69
70public:
71  typedef size_t size_type;
72  typedef HashFunctionTy hasher;
73  typedef HashEntryTy entry_type;
74  typedef typename HashEntryTy::key_type key_type;
75  typedef HashBucket<HashEntryTy> bucket_type;
76  typedef HashTableImpl<HashEntryTy, HashFunctionTy> Self;
77
78
79public:
80  HashTableImpl();
81  explicit HashTableImpl(unsigned int pInitSize);
82  virtual ~HashTableImpl();
83
84  // -----  observers  ----- //
85  bool empty() const;
86
87  size_t numOfBuckets() const
88  { return m_NumOfBuckets; }
89
90  size_t numOfEntries() const
91  { return m_NumOfEntries; }
92
93  hasher& hash()
94  { return m_Hasher; }
95
96  const hasher& hash() const
97  { return m_Hasher; }
98
99protected:
100  /// initialize the hash table.
101  void init(unsigned int pInitSize);
102
103  void clear();
104
105  /// lookUpBucketFor - search the index of bucket whose key is p>ey
106  //  @return the index of the found bucket
107  unsigned int lookUpBucketFor(const key_type& pKey);
108
109  /// findKey - finds an element with key pKey
110  //  return the index of the element, or -1 when the element does not exist.
111  int findKey(const key_type& pKey) const;
112
113  /// mayRehash - check the load_factor, compute the new size, and then doRehash
114  void mayRehash();
115
116  /// doRehash - re-new the hash table, and rehash all elements into the new buckets
117  void doRehash(unsigned int pNewSize);
118
119friend class ChainIteratorBase<Self>;
120friend class ChainIteratorBase<const Self>;
121friend class EntryIteratorBase<Self>;
122friend class EntryIteratorBase<const Self>;
123protected:
124  // Array of Buckets
125  bucket_type* m_Buckets;
126  unsigned int m_NumOfBuckets;
127  unsigned int m_NumOfEntries;
128  unsigned int m_NumOfTombstones;
129  hasher m_Hasher;
130
131};
132
133#include "HashBase.tcc"
134
135} // namespace of mcld
136
137#endif
138
139