StringHash.h revision 5460a1f25d9ddecb5c70667267d66d51af177a99 
1//===- StringHash.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
10#ifndef MCLD_STRING_HASH_FUNCTION_H
11#define MCLD_STRING_HASH_FUNCTION_H
12#ifdef ENABLE_UNITTEST
13#include <gtest.h>
14#endif
15#include <llvm/ADT/StringRef.h>
16#include <llvm/Support/ErrorHandling.h>
17#include <functional>
18
19namespace mcld
20{
21
22enum StringHashType
23{
24  RS,
25  JS,
26  PJW,
27  ELF,
28  BKDR,
29  SDBM,
30  DJB,
31  DEK,
32  BP,
33  FNV,
34  AP
35};
36
37/** \class template<size_t TYPE> StringHash
38 *  \brief the template StringHash class, for specification
39 */
40template<size_t TYPE>
41struct StringHash : public std::unary_function<const llvm::StringRef&, size_t>
42{
43  size_t operator()(const llvm::StringRef& pKey) const
44  {
45    llvm::report_fatal_error("Undefined StringHash function.\n");
46  }
47};
48
49/** \class StringHash<RSHash>
50 *  \brief RS StringHash funciton
51 */
52template<>
53struct StringHash<RS> : public std::unary_function<const llvm::StringRef&, size_t>
54{
55  size_t operator()(const llvm::StringRef& pKey) const
56  {
57    const unsigned int b = 378551;
58    size_t a = 63689;
59    size_t hash_val = 0;
60
61    for(unsigned int i = 0; i < pKey.size(); ++i) {
62      hash_val = hash_val * a + pKey[i];
63      a = a * b;
64    }
65    return hash_val;
66  }
67};
68
69/** \class StringHash<JSHash>
70 *  \brief JS hash funciton
71 */
72template<>
73struct StringHash<JS> : public std::unary_function<const llvm::StringRef&, size_t>
74{
75  size_t operator()(const llvm::StringRef& pKey) const
76  {
77    size_t hash_val = 1315423911;
78
79    for(unsigned int i = 0; i < pKey.size(); ++i) {
80       hash_val ^= ((hash_val << 5) + pKey[i] + (hash_val >> 2));
81    }
82    return hash_val;
83  }
84};
85
86/** \class StringHash<PJW>
87 *  \brief P.J. Weinberger hash function
88 */
89template<>
90struct StringHash<PJW> : public std::unary_function<const llvm::StringRef&, size_t>
91{
92  size_t operator()(const llvm::StringRef& pKey) const
93  {
94    const unsigned int BitsInUnsignedInt = (unsigned int)(sizeof(unsigned int) * 8);
95    const unsigned int ThreeQuarters     = (unsigned int)((BitsInUnsignedInt  * 3) / 4);
96    const unsigned int OneEighth         = (unsigned int)(BitsInUnsignedInt / 8);
97    const unsigned int HighBits          = (unsigned int)(0xFFFFFFFF) << (BitsInUnsignedInt - OneEighth);
98    size_t hash_val = 0;
99    size_t test = 0;
100
101    for(unsigned int i = 0; i < pKey.size(); ++i) {
102      hash_val = (hash_val << OneEighth) + pKey[i];
103
104      if((test = hash_val & HighBits) != 0) {
105        hash_val = (( hash_val ^ (test >> ThreeQuarters)) & (~HighBits));
106      }
107    }
108    return hash_val;
109  }
110};
111
112/** \class StringHash<ELF>
113 *  \brief ELF hash function.
114 */
115template<>
116struct StringHash<ELF> : public std::unary_function<const llvm::StringRef&, size_t>
117{
118  size_t operator()(const llvm::StringRef& pKey) const
119  {
120    size_t hash_val = 0;
121    size_t x = 0;
122
123    for (unsigned int i = 0; i < pKey.size(); ++i) {
124      hash_val = (hash_val << 4) + pKey[i];
125      if((x = hash_val & 0xF0000000L) != 0)
126        hash_val ^= (x >> 24);
127      hash_val &= ~x;
128    }
129    return hash_val;
130  }
131};
132
133/** \class StringHash<BKDR>
134 *  \brief BKDR hash function
135 */
136template<>
137struct StringHash<BKDR> : public std::unary_function<const llvm::StringRef&, size_t>
138{
139  size_t operator()(const llvm::StringRef& pKey) const
140  {
141    const size_t seed = 131;
142    size_t hash_val = 0;
143
144    for(size_t i = 0; i < pKey.size(); ++i)
145      hash_val = (hash_val * seed) + pKey[i];
146    return hash_val;
147  }
148};
149
150
151/** \class StringHash<SDBM>
152 *  \brief SDBM hash function
153 *  0.049s in 100000 test
154 */
155template<>
156struct StringHash<SDBM> : public std::unary_function<const llvm::StringRef&, size_t>
157{
158  size_t operator()(const llvm::StringRef& pKey) const
159  {
160    size_t hash_val = 0;
161
162    for(size_t i = 0; i < pKey.size(); ++i)
163      hash_val = pKey[i] + (hash_val << 6) + (hash_val << 16) - hash_val;
164    return hash_val;
165  }
166};
167
168/** \class StringHash<DJB>
169 *  \brief DJB hash function
170 *  0.057s in 100000 test
171 */
172template<>
173struct StringHash<DJB> : public std::unary_function<const llvm::StringRef&, size_t>
174{
175  size_t operator()(const llvm::StringRef& pKey) const
176  {
177    size_t hash_val = 5381;
178
179    for(size_t i = 0; i < pKey.size(); ++i)
180      hash_val = ((hash_val << 5) + hash_val) + pKey[i];
181
182    return hash_val;
183  }
184};
185
186/** \class StringHash<DEK>
187 *  \brief DEK hash function
188 *  0.60s
189 */
190template<>
191struct StringHash<DEK> : public std::unary_function<const llvm::StringRef&, size_t>
192{
193  size_t operator()(const llvm::StringRef& pKey) const
194  {
195    size_t hash_val = pKey.size();
196
197    for(size_t i = 0; i < pKey.size(); ++i)
198      hash_val = ((hash_val << 5) ^ (hash_val >> 27)) ^ pKey[i];
199
200    return hash_val;
201  }
202};
203
204/** \class StringHash<BP>
205 *  \brief BP hash function
206 *  0.057s
207 */
208template<>
209struct StringHash<BP> : public std::unary_function<const llvm::StringRef&, size_t>
210{
211  size_t operator()(const llvm::StringRef& pKey) const
212  {
213    size_t hash_val = 0;
214    for(size_t i = 0; i < pKey.size(); ++i)
215      hash_val = hash_val << 7 ^ pKey[i];
216
217    return hash_val;
218  }
219};
220
221/** \class StringHash<FNV>
222 *  \brief FNV hash function
223 *  0.058s
224 */
225template<>
226struct StringHash<FNV> : public std::unary_function<const llvm::StringRef&, size_t>
227{
228  size_t operator()(const llvm::StringRef& pKey) const
229  {
230    const size_t fnv_prime = 0x811C9DC5;
231    size_t hash_val = 0;
232    for(size_t i = 0; i < pKey.size(); ++i) {
233      hash_val *= fnv_prime;
234      hash_val ^= pKey[i];
235    }
236
237    return hash_val;
238  }
239};
240
241/** \class StringHash<AP>
242 *  \brief AP hash function
243 *  0.060s
244 */
245template<>
246struct StringHash<AP> : public std::unary_function<const llvm::StringRef&, size_t>
247{
248  size_t operator()(const llvm::StringRef& pKey) const
249  {
250    unsigned int hash_val = 0xAAAAAAAA;
251
252    for(size_t i = 0; i < pKey.size(); ++i) {
253      hash_val ^= ((i & 1) == 0)?
254                          ((hash_val <<  7) ^ pKey[i] * (hash_val >> 3)):
255                          (~((hash_val << 11) + (pKey[i] ^ (hash_val >> 5))));
256    }
257
258    return hash_val;
259  }
260};
261
262/** \class template<size_t TYPE> StringCompare
263 *  \brief the template StringCompare class, for specification
264 */
265template<typename STRING_TYPE>
266struct StringCompare : public std::binary_function<const STRING_TYPE&, const STRING_TYPE&, bool>
267{
268  bool operator()(const STRING_TYPE& X, const STRING_TYPE& Y) const
269  { return X == Y; }
270};
271
272template<>
273struct StringCompare<const char*> : public std::binary_function<const char*, const char*, bool>
274{
275  bool operator()(const char* X, const char* Y) const
276  { return (0 == std::strcmp(X, Y)); }
277};
278
279template<>
280struct StringCompare<char*> : public std::binary_function<const char*, const char*, bool>
281{
282  bool operator()(const char* X, const char* Y) const
283  { return (0 == std::strcmp(X, Y)); }
284};
285
286} // namespace of mcld
287
288#endif
289
290