blob: 36d825b197b6726e351e9d8c0ab6babb7bac6d4e (
plain)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
|
//===- HashBase.h ---------------------------------------------------------===//
//
// The MCLinker Project
//
// This file is distributed under the University of Illinois Open Source
// License. See LICENSE.TXT for details.
//
//===----------------------------------------------------------------------===//
#ifndef MCLD_HASH_BASE_H
#define MCLD_HASH_BASE_H
#ifdef ENABLE_UNITTEST
#include <gtest.h>
#endif
#include <llvm/ADT/StringRef.h>
#include <cstdlib>
namespace mcld {
/** forward declaration **/
template<typename HashTableImplTy>
class ChainIteratorBase;
template<typename HashTableImplTy>
class EntryIteratorBase;
/** \class HashBucket
* \brief HashBucket is an entry in the hash table.
*/
template<typename HashEntryTy>
class HashBucket
{
public:
typedef HashEntryTy entry_type;
public:
unsigned int FullHashValue;
entry_type *Entry;
public:
static entry_type* getEmptyBucket();
static entry_type* getTombstone();
};
/** \class HashTableImpl
* \brief HashTableImpl is the base class of HashTable.
*
* HashTableImpl uses open-addressing, linear probing hash table.
* linear probing hash table obviously has high performance when the
* load factor is less than 0.7.
* The drawback is that the number of the stored items can notbe more
* than the size of the hash table.
*
* MCLinker tries to merge every things in the same HashEntry. It can
* keep every thing in the same cache line and improve the locality
* efficiently. HashTableImpl provides a template argument to change the
* definition of HashEntries.
*
* HashEntryTy must provide getKey() and getKenLength() functions.
*
* Different environments have different demands of HashFunctions. For
* example, on-device linkers needs a more light-weight hash function
* than static linkers. HashTableImpl also provides a template argument to
* change the hash functions.
*/
template<typename HashEntryTy,
typename HashFunctionTy>
class HashTableImpl
{
private:
static const unsigned int NumOfInitBuckets = 16;
public:
typedef size_t size_type;
typedef HashFunctionTy hasher;
typedef HashEntryTy entry_type;
typedef typename HashEntryTy::key_type key_type;
typedef HashBucket<HashEntryTy> bucket_type;
typedef HashTableImpl<HashEntryTy, HashFunctionTy> Self;
public:
HashTableImpl();
explicit HashTableImpl(unsigned int pInitSize);
virtual ~HashTableImpl();
// ----- observers ----- //
bool empty() const;
size_t numOfBuckets() const
{ return m_NumOfBuckets; }
size_t numOfEntries() const
{ return m_NumOfEntries; }
hasher& hash()
{ return m_Hasher; }
const hasher& hash() const
{ return m_Hasher; }
protected:
/// initialize the hash table.
void init(unsigned int pInitSize);
/// lookUpBucketFor - search the index of bucket whose key is p>ey
// @return the index of the found bucket
unsigned int lookUpBucketFor(const key_type& pKey);
/// findKey - finds an element with key pKey
// return the index of the element, or -1 when the element does not exist.
int findKey(const key_type& pKey) const;
/// mayRehash - check the load_factor, compute the new size, and then doRehash
void mayRehash();
/// doRehash - re-new the hash table, and rehash all elements into the new buckets
void doRehash(unsigned int pNewSize);
friend class ChainIteratorBase<Self>;
friend class ChainIteratorBase<const Self>;
friend class EntryIteratorBase<Self>;
friend class EntryIteratorBase<const Self>;
protected:
// Array of Buckets
bucket_type* m_Buckets;
unsigned int m_NumOfBuckets;
unsigned int m_NumOfEntries;
unsigned int m_NumOfTombstones;
hasher m_Hasher;
};
#include "HashBase.tcc"
} // namespace of mcld
#endif
|
