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 19 namespace mcld 20 { 21 22 enum 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 */ 40 template<size_t TYPE> 41 struct StringHash : public std::unary_function<const llvm::StringRef&, size_t> 42 { operatorStringHash43 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 */ 52 template<> 53 struct 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 */ 72 template<> 73 struct 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 */ 89 template<> 90 struct 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 */ 115 template<> 116 struct 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 */ 136 template<> 137 struct 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 */ 155 template<> 156 struct 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 */ 172 template<> 173 struct 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 */ 190 template<> 191 struct 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 */ 208 template<> 209 struct 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 */ 225 template<> 226 struct 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 */ 245 template<> 246 struct 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 */ 265 template<typename STRING_TYPE> 266 struct 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 272 template<> 273 struct 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 279 template<> 280 struct 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