StringHash.h revision f7ac0f19a1c8d0ad14bcf6456ce368b830fea886
1f7ac0f19a1c8d0ad14bcf6456ce368b830fea886Stephen Hines//===- StringHash.h -------------------------------------------------------===// 25460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao// 35460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao// The MCLinker Project 45460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao// 55460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao// This file is distributed under the University of Illinois Open Source 65460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao// License. See LICENSE.TXT for details. 75460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao// 85460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao//===----------------------------------------------------------------------===// 95460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao#ifndef MCLD_STRING_HASH_FUNCTION_H 105460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao#define MCLD_STRING_HASH_FUNCTION_H 115460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao#ifdef ENABLE_UNITTEST 125460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao#include <gtest.h> 135460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao#endif 145460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao#include <llvm/ADT/StringRef.h> 1522add6ff3426df1a85089fe6a6e1597ee3b6f300Shih-wei Liao#include <llvm/Support/DataTypes.h> 165460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao#include <llvm/Support/ErrorHandling.h> 1722add6ff3426df1a85089fe6a6e1597ee3b6f300Shih-wei Liao#include <cctype> 185460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao#include <functional> 195460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao 20f7ac0f19a1c8d0ad14bcf6456ce368b830fea886Stephen Hinesnamespace mcld { 21f7ac0f19a1c8d0ad14bcf6456ce368b830fea886Stephen Hinesnamespace hash { 225460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao 23f7ac0f19a1c8d0ad14bcf6456ce368b830fea886Stephen Hinesenum Type { 245460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao RS, 255460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao JS, 265460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao PJW, 275460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao ELF, 285460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao BKDR, 295460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao SDBM, 305460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao DJB, 315460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao DEK, 325460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao BP, 335460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao FNV, 3422add6ff3426df1a85089fe6a6e1597ee3b6f300Shih-wei Liao AP, 3522add6ff3426df1a85089fe6a6e1597ee3b6f300Shih-wei Liao ES 365460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao}; 375460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao 3822add6ff3426df1a85089fe6a6e1597ee3b6f300Shih-wei Liao/** \class template<uint32_t TYPE> StringHash 395460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao * \brief the template StringHash class, for specification 405460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao */ 4122add6ff3426df1a85089fe6a6e1597ee3b6f300Shih-wei Liaotemplate<uint32_t TYPE> 4222add6ff3426df1a85089fe6a6e1597ee3b6f300Shih-wei Liaostruct StringHash : public std::unary_function<const llvm::StringRef&, uint32_t> 435460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao{ 4422add6ff3426df1a85089fe6a6e1597ee3b6f300Shih-wei Liao uint32_t operator()(const llvm::StringRef& pKey) const 455460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao { 465460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao llvm::report_fatal_error("Undefined StringHash function.\n"); 475460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao } 485460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao}; 495460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao 505460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao/** \class StringHash<RSHash> 515460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao * \brief RS StringHash funciton 525460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao */ 535460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liaotemplate<> 5422add6ff3426df1a85089fe6a6e1597ee3b6f300Shih-wei Liaostruct StringHash<RS> : public std::unary_function<const llvm::StringRef&, uint32_t> 555460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao{ 5622add6ff3426df1a85089fe6a6e1597ee3b6f300Shih-wei Liao uint32_t operator()(const llvm::StringRef& pKey) const 575460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao { 585460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao const unsigned int b = 378551; 5922add6ff3426df1a85089fe6a6e1597ee3b6f300Shih-wei Liao uint32_t a = 63689; 6022add6ff3426df1a85089fe6a6e1597ee3b6f300Shih-wei Liao uint32_t hash_val = 0; 615460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao 625460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao for(unsigned int i = 0; i < pKey.size(); ++i) { 635460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao hash_val = hash_val * a + pKey[i]; 645460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao a = a * b; 655460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao } 665460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao return hash_val; 675460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao } 685460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao}; 695460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao 705460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao/** \class StringHash<JSHash> 715460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao * \brief JS hash funciton 725460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao */ 735460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liaotemplate<> 7422add6ff3426df1a85089fe6a6e1597ee3b6f300Shih-wei Liaostruct StringHash<JS> : public std::unary_function<const llvm::StringRef&, uint32_t> 755460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao{ 7622add6ff3426df1a85089fe6a6e1597ee3b6f300Shih-wei Liao uint32_t operator()(const llvm::StringRef& pKey) const 775460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao { 7822add6ff3426df1a85089fe6a6e1597ee3b6f300Shih-wei Liao uint32_t hash_val = 1315423911; 795460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao 805460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao for(unsigned int i = 0; i < pKey.size(); ++i) { 815460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao hash_val ^= ((hash_val << 5) + pKey[i] + (hash_val >> 2)); 82affc150dc44fab1911775a49636d0ce85333b634Zonr Chang } 835460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao return hash_val; 845460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao } 855460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao}; 865460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao 875460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao/** \class StringHash<PJW> 885460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao * \brief P.J. Weinberger hash function 895460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao */ 905460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liaotemplate<> 9122add6ff3426df1a85089fe6a6e1597ee3b6f300Shih-wei Liaostruct StringHash<PJW> : public std::unary_function<const llvm::StringRef&, uint32_t> 925460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao{ 9322add6ff3426df1a85089fe6a6e1597ee3b6f300Shih-wei Liao uint32_t operator()(const llvm::StringRef& pKey) const 945460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao { 955460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao const unsigned int BitsInUnsignedInt = (unsigned int)(sizeof(unsigned int) * 8); 965460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao const unsigned int ThreeQuarters = (unsigned int)((BitsInUnsignedInt * 3) / 4); 975460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao const unsigned int OneEighth = (unsigned int)(BitsInUnsignedInt / 8); 985460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao const unsigned int HighBits = (unsigned int)(0xFFFFFFFF) << (BitsInUnsignedInt - OneEighth); 9922add6ff3426df1a85089fe6a6e1597ee3b6f300Shih-wei Liao uint32_t hash_val = 0; 10022add6ff3426df1a85089fe6a6e1597ee3b6f300Shih-wei Liao uint32_t test = 0; 1015460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao 1025460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao for(unsigned int i = 0; i < pKey.size(); ++i) { 1035460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao hash_val = (hash_val << OneEighth) + pKey[i]; 1045460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao 1055460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao if((test = hash_val & HighBits) != 0) { 1065460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao hash_val = (( hash_val ^ (test >> ThreeQuarters)) & (~HighBits)); 1075460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao } 1085460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao } 1095460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao return hash_val; 1105460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao } 1115460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao}; 1125460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao 1135460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao/** \class StringHash<ELF> 1145460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao * \brief ELF hash function. 1155460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao */ 1165460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liaotemplate<> 11722add6ff3426df1a85089fe6a6e1597ee3b6f300Shih-wei Liaostruct StringHash<ELF> : public std::unary_function<const llvm::StringRef&, uint32_t> 1185460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao{ 11922add6ff3426df1a85089fe6a6e1597ee3b6f300Shih-wei Liao uint32_t operator()(const llvm::StringRef& pKey) const 1205460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao { 12122add6ff3426df1a85089fe6a6e1597ee3b6f300Shih-wei Liao uint32_t hash_val = 0; 12222add6ff3426df1a85089fe6a6e1597ee3b6f300Shih-wei Liao uint32_t x = 0; 1235460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao 1245460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao for (unsigned int i = 0; i < pKey.size(); ++i) { 1255460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao hash_val = (hash_val << 4) + pKey[i]; 1265460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao if((x = hash_val & 0xF0000000L) != 0) 127affc150dc44fab1911775a49636d0ce85333b634Zonr Chang hash_val ^= (x >> 24); 1285460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao hash_val &= ~x; 1295460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao } 1305460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao return hash_val; 1315460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao } 1325460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao}; 1335460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao 1345460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao/** \class StringHash<BKDR> 1355460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao * \brief BKDR hash function 1365460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao */ 1375460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liaotemplate<> 13822add6ff3426df1a85089fe6a6e1597ee3b6f300Shih-wei Liaostruct StringHash<BKDR> : public std::unary_function<const llvm::StringRef&, uint32_t> 1395460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao{ 14022add6ff3426df1a85089fe6a6e1597ee3b6f300Shih-wei Liao uint32_t operator()(const llvm::StringRef& pKey) const 1415460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao { 14222add6ff3426df1a85089fe6a6e1597ee3b6f300Shih-wei Liao const uint32_t seed = 131; 14322add6ff3426df1a85089fe6a6e1597ee3b6f300Shih-wei Liao uint32_t hash_val = 0; 144affc150dc44fab1911775a49636d0ce85333b634Zonr Chang 14522add6ff3426df1a85089fe6a6e1597ee3b6f300Shih-wei Liao for(uint32_t i = 0; i < pKey.size(); ++i) 1465460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao hash_val = (hash_val * seed) + pKey[i]; 1475460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao return hash_val; 1485460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao } 1495460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao}; 1505460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao 1515460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao 1525460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao/** \class StringHash<SDBM> 1535460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao * \brief SDBM hash function 1545460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao * 0.049s in 100000 test 1555460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao */ 1565460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liaotemplate<> 15722add6ff3426df1a85089fe6a6e1597ee3b6f300Shih-wei Liaostruct StringHash<SDBM> : public std::unary_function<const llvm::StringRef&, uint32_t> 1585460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao{ 15922add6ff3426df1a85089fe6a6e1597ee3b6f300Shih-wei Liao uint32_t operator()(const llvm::StringRef& pKey) const 1605460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao { 16122add6ff3426df1a85089fe6a6e1597ee3b6f300Shih-wei Liao uint32_t hash_val = 0; 1625460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao 16322add6ff3426df1a85089fe6a6e1597ee3b6f300Shih-wei Liao for(uint32_t i = 0; i < pKey.size(); ++i) 1645460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao hash_val = pKey[i] + (hash_val << 6) + (hash_val << 16) - hash_val; 1655460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao return hash_val; 1665460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao } 1675460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao}; 1685460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao 1695460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao/** \class StringHash<DJB> 1705460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao * \brief DJB hash function 1715460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao * 0.057s in 100000 test 1725460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao */ 1735460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liaotemplate<> 17422add6ff3426df1a85089fe6a6e1597ee3b6f300Shih-wei Liaostruct StringHash<DJB> : public std::unary_function<const llvm::StringRef&, uint32_t> 1755460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao{ 17622add6ff3426df1a85089fe6a6e1597ee3b6f300Shih-wei Liao uint32_t operator()(const llvm::StringRef& pKey) const 1775460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao { 17822add6ff3426df1a85089fe6a6e1597ee3b6f300Shih-wei Liao uint32_t hash_val = 5381; 1795460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao 18022add6ff3426df1a85089fe6a6e1597ee3b6f300Shih-wei Liao for(uint32_t i = 0; i < pKey.size(); ++i) 1815460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao hash_val = ((hash_val << 5) + hash_val) + pKey[i]; 1825460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao 1835460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao return hash_val; 1845460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao } 1855460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao}; 1865460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao 1875460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao/** \class StringHash<DEK> 1885460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao * \brief DEK hash function 1895460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao * 0.60s 1905460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao */ 1915460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liaotemplate<> 19222add6ff3426df1a85089fe6a6e1597ee3b6f300Shih-wei Liaostruct StringHash<DEK> : public std::unary_function<const llvm::StringRef&, uint32_t> 1935460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao{ 19422add6ff3426df1a85089fe6a6e1597ee3b6f300Shih-wei Liao uint32_t operator()(const llvm::StringRef& pKey) const 1955460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao { 19622add6ff3426df1a85089fe6a6e1597ee3b6f300Shih-wei Liao uint32_t hash_val = pKey.size(); 1975460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao 19822add6ff3426df1a85089fe6a6e1597ee3b6f300Shih-wei Liao for(uint32_t i = 0; i < pKey.size(); ++i) 1995460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao hash_val = ((hash_val << 5) ^ (hash_val >> 27)) ^ pKey[i]; 2005460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao 2015460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao return hash_val; 2025460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao } 2035460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao}; 2045460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao 2055460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao/** \class StringHash<BP> 2065460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao * \brief BP hash function 2075460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao * 0.057s 2085460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao */ 2095460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liaotemplate<> 21022add6ff3426df1a85089fe6a6e1597ee3b6f300Shih-wei Liaostruct StringHash<BP> : public std::unary_function<const llvm::StringRef&, uint32_t> 2115460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao{ 21222add6ff3426df1a85089fe6a6e1597ee3b6f300Shih-wei Liao uint32_t operator()(const llvm::StringRef& pKey) const 2135460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao { 21422add6ff3426df1a85089fe6a6e1597ee3b6f300Shih-wei Liao uint32_t hash_val = 0; 21522add6ff3426df1a85089fe6a6e1597ee3b6f300Shih-wei Liao for(uint32_t i = 0; i < pKey.size(); ++i) 2165460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao hash_val = hash_val << 7 ^ pKey[i]; 2175460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao 2185460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao return hash_val; 2195460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao } 2205460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao}; 2215460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao 2225460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao/** \class StringHash<FNV> 2235460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao * \brief FNV hash function 2245460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao * 0.058s 2255460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao */ 2265460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liaotemplate<> 22722add6ff3426df1a85089fe6a6e1597ee3b6f300Shih-wei Liaostruct StringHash<FNV> : public std::unary_function<const llvm::StringRef&, uint32_t> 2285460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao{ 22922add6ff3426df1a85089fe6a6e1597ee3b6f300Shih-wei Liao uint32_t operator()(const llvm::StringRef& pKey) const 2305460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao { 23122add6ff3426df1a85089fe6a6e1597ee3b6f300Shih-wei Liao const uint32_t fnv_prime = 0x811C9DC5; 23222add6ff3426df1a85089fe6a6e1597ee3b6f300Shih-wei Liao uint32_t hash_val = 0; 23322add6ff3426df1a85089fe6a6e1597ee3b6f300Shih-wei Liao for(uint32_t i = 0; i < pKey.size(); ++i) { 2345460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao hash_val *= fnv_prime; 2355460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao hash_val ^= pKey[i]; 2365460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao } 2375460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao 2385460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao return hash_val; 2395460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao } 2405460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao}; 2415460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao 2425460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao/** \class StringHash<AP> 2435460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao * \brief AP hash function 2445460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao * 0.060s 2455460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao */ 2465460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liaotemplate<> 24722add6ff3426df1a85089fe6a6e1597ee3b6f300Shih-wei Liaostruct StringHash<AP> : public std::unary_function<const llvm::StringRef&, uint32_t> 2485460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao{ 24922add6ff3426df1a85089fe6a6e1597ee3b6f300Shih-wei Liao uint32_t operator()(const llvm::StringRef& pKey) const 2505460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao { 2515460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao unsigned int hash_val = 0xAAAAAAAA; 252affc150dc44fab1911775a49636d0ce85333b634Zonr Chang 25322add6ff3426df1a85089fe6a6e1597ee3b6f300Shih-wei Liao for(uint32_t i = 0; i < pKey.size(); ++i) { 2545460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao hash_val ^= ((i & 1) == 0)? 2555460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao ((hash_val << 7) ^ pKey[i] * (hash_val >> 3)): 2565460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao (~((hash_val << 11) + (pKey[i] ^ (hash_val >> 5)))); 2575460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao } 258affc150dc44fab1911775a49636d0ce85333b634Zonr Chang 2595460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao return hash_val; 2605460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao } 2615460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao}; 2625460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao 26322add6ff3426df1a85089fe6a6e1597ee3b6f300Shih-wei Liao/** \class StringHash<ES> 26422add6ff3426df1a85089fe6a6e1597ee3b6f300Shih-wei Liao * \brief This is a revision of Edward Sayers' string characteristic function. 26522add6ff3426df1a85089fe6a6e1597ee3b6f300Shih-wei Liao * 26622add6ff3426df1a85089fe6a6e1597ee3b6f300Shih-wei Liao * 31-28 27 26 25 - 0 26722add6ff3426df1a85089fe6a6e1597ee3b6f300Shih-wei Liao * +----+---+---+------------+ 26822add6ff3426df1a85089fe6a6e1597ee3b6f300Shih-wei Liao * | . | N | - | a/A ~ z/Z | 26922add6ff3426df1a85089fe6a6e1597ee3b6f300Shih-wei Liao * +----+---+---+------------+ 27022add6ff3426df1a85089fe6a6e1597ee3b6f300Shih-wei Liao * 27122add6ff3426df1a85089fe6a6e1597ee3b6f300Shih-wei Liao * . (bit 31~28) - The number of '.' characters 27222add6ff3426df1a85089fe6a6e1597ee3b6f300Shih-wei Liao * N (bit 27) - Are there any numbers in the string 27322add6ff3426df1a85089fe6a6e1597ee3b6f300Shih-wei Liao * - (bit 26) - Does the string have '-' character 27422add6ff3426df1a85089fe6a6e1597ee3b6f300Shih-wei Liao * bit 25~0 - Bit 25 is set only if the string contains a 'a' or 'A', and 27522add6ff3426df1a85089fe6a6e1597ee3b6f300Shih-wei Liao * Bit 24 is set only if ... 'b' or 'B', ... 27622add6ff3426df1a85089fe6a6e1597ee3b6f300Shih-wei Liao */ 27722add6ff3426df1a85089fe6a6e1597ee3b6f300Shih-wei Liaotemplate<> 27822add6ff3426df1a85089fe6a6e1597ee3b6f300Shih-wei Liaostruct StringHash<ES> : public std::unary_function<const llvm::StringRef&, uint32_t> 27922add6ff3426df1a85089fe6a6e1597ee3b6f300Shih-wei Liao{ 28022add6ff3426df1a85089fe6a6e1597ee3b6f300Shih-wei Liao uint32_t operator()(const llvm::StringRef& pString) const 28122add6ff3426df1a85089fe6a6e1597ee3b6f300Shih-wei Liao { 28222add6ff3426df1a85089fe6a6e1597ee3b6f300Shih-wei Liao uint32_t result = 0x0; 28322add6ff3426df1a85089fe6a6e1597ee3b6f300Shih-wei Liao unsigned int dot = 0; 28422add6ff3426df1a85089fe6a6e1597ee3b6f300Shih-wei Liao std::string::size_type idx; 28522add6ff3426df1a85089fe6a6e1597ee3b6f300Shih-wei Liao for (idx = 0; idx < pString.size(); ++idx) { 28622add6ff3426df1a85089fe6a6e1597ee3b6f300Shih-wei Liao int cur_char = pString[idx]; 28722add6ff3426df1a85089fe6a6e1597ee3b6f300Shih-wei Liao 28822add6ff3426df1a85089fe6a6e1597ee3b6f300Shih-wei Liao if ('.' == cur_char) { 28922add6ff3426df1a85089fe6a6e1597ee3b6f300Shih-wei Liao ++dot; 29022add6ff3426df1a85089fe6a6e1597ee3b6f300Shih-wei Liao continue; 29122add6ff3426df1a85089fe6a6e1597ee3b6f300Shih-wei Liao } 29222add6ff3426df1a85089fe6a6e1597ee3b6f300Shih-wei Liao 29322add6ff3426df1a85089fe6a6e1597ee3b6f300Shih-wei Liao if (isdigit(cur_char)) { 29422add6ff3426df1a85089fe6a6e1597ee3b6f300Shih-wei Liao result |= (1 << 27); 29522add6ff3426df1a85089fe6a6e1597ee3b6f300Shih-wei Liao continue; 29622add6ff3426df1a85089fe6a6e1597ee3b6f300Shih-wei Liao } 29722add6ff3426df1a85089fe6a6e1597ee3b6f300Shih-wei Liao 29822add6ff3426df1a85089fe6a6e1597ee3b6f300Shih-wei Liao if ('_' == cur_char) { 29922add6ff3426df1a85089fe6a6e1597ee3b6f300Shih-wei Liao result |= (1 << 26); 30022add6ff3426df1a85089fe6a6e1597ee3b6f300Shih-wei Liao continue; 30122add6ff3426df1a85089fe6a6e1597ee3b6f300Shih-wei Liao } 30222add6ff3426df1a85089fe6a6e1597ee3b6f300Shih-wei Liao 30322add6ff3426df1a85089fe6a6e1597ee3b6f300Shih-wei Liao if (isupper(cur_char)) { 30422add6ff3426df1a85089fe6a6e1597ee3b6f300Shih-wei Liao result |= (1 << (cur_char - 'A')); 30522add6ff3426df1a85089fe6a6e1597ee3b6f300Shih-wei Liao continue; 30622add6ff3426df1a85089fe6a6e1597ee3b6f300Shih-wei Liao } 30722add6ff3426df1a85089fe6a6e1597ee3b6f300Shih-wei Liao 30822add6ff3426df1a85089fe6a6e1597ee3b6f300Shih-wei Liao if (islower(cur_char)) { 30922add6ff3426df1a85089fe6a6e1597ee3b6f300Shih-wei Liao result |= (1 << (cur_char - 'a')); 31022add6ff3426df1a85089fe6a6e1597ee3b6f300Shih-wei Liao continue; 31122add6ff3426df1a85089fe6a6e1597ee3b6f300Shih-wei Liao } 31222add6ff3426df1a85089fe6a6e1597ee3b6f300Shih-wei Liao } 31322add6ff3426df1a85089fe6a6e1597ee3b6f300Shih-wei Liao result |= (dot << 28); 31422add6ff3426df1a85089fe6a6e1597ee3b6f300Shih-wei Liao return result; 31522add6ff3426df1a85089fe6a6e1597ee3b6f300Shih-wei Liao } 31622add6ff3426df1a85089fe6a6e1597ee3b6f300Shih-wei Liao 31722add6ff3426df1a85089fe6a6e1597ee3b6f300Shih-wei Liao 31822add6ff3426df1a85089fe6a6e1597ee3b6f300Shih-wei Liao /** \func may_include 31922add6ff3426df1a85089fe6a6e1597ee3b6f300Shih-wei Liao * \brief is it possible that pRule is a sub-string of pInString 32022add6ff3426df1a85089fe6a6e1597ee3b6f300Shih-wei Liao */ 32122add6ff3426df1a85089fe6a6e1597ee3b6f300Shih-wei Liao static bool may_include(uint32_t pRule, uint32_t pInString) 32222add6ff3426df1a85089fe6a6e1597ee3b6f300Shih-wei Liao { 32322add6ff3426df1a85089fe6a6e1597ee3b6f300Shih-wei Liao uint32_t in_c = pInString << 4; 32422add6ff3426df1a85089fe6a6e1597ee3b6f300Shih-wei Liao uint32_t r_c = pRule << 4; 32522add6ff3426df1a85089fe6a6e1597ee3b6f300Shih-wei Liao 32622add6ff3426df1a85089fe6a6e1597ee3b6f300Shih-wei Liao uint32_t res = (in_c ^ r_c) & r_c; 32722add6ff3426df1a85089fe6a6e1597ee3b6f300Shih-wei Liao if (0 != res) 32822add6ff3426df1a85089fe6a6e1597ee3b6f300Shih-wei Liao return false; 32922add6ff3426df1a85089fe6a6e1597ee3b6f300Shih-wei Liao 33022add6ff3426df1a85089fe6a6e1597ee3b6f300Shih-wei Liao uint32_t in_dot = pInString >> 28; 33122add6ff3426df1a85089fe6a6e1597ee3b6f300Shih-wei Liao uint32_t r_dot = pRule >> 28; 33222add6ff3426df1a85089fe6a6e1597ee3b6f300Shih-wei Liao if (r_dot > in_dot) 33322add6ff3426df1a85089fe6a6e1597ee3b6f300Shih-wei Liao return false; 33422add6ff3426df1a85089fe6a6e1597ee3b6f300Shih-wei Liao 33522add6ff3426df1a85089fe6a6e1597ee3b6f300Shih-wei Liao return true; 33622add6ff3426df1a85089fe6a6e1597ee3b6f300Shih-wei Liao } 33722add6ff3426df1a85089fe6a6e1597ee3b6f300Shih-wei Liao}; 33822add6ff3426df1a85089fe6a6e1597ee3b6f300Shih-wei Liao 33922add6ff3426df1a85089fe6a6e1597ee3b6f300Shih-wei Liao/** \class template<uint32_t TYPE> StringCompare 3405460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao * \brief the template StringCompare class, for specification 3415460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao */ 3425460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liaotemplate<typename STRING_TYPE> 3435460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liaostruct StringCompare : public std::binary_function<const STRING_TYPE&, const STRING_TYPE&, bool> 3445460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao{ 3455460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao bool operator()(const STRING_TYPE& X, const STRING_TYPE& Y) const 3465460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao { return X == Y; } 3475460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao}; 3485460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao 3495460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liaotemplate<> 3505460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liaostruct StringCompare<const char*> : public std::binary_function<const char*, const char*, bool> 3515460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao{ 3525460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao bool operator()(const char* X, const char* Y) const 3535460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao { return (0 == std::strcmp(X, Y)); } 3545460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao}; 3555460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao 3565460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liaotemplate<> 3575460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liaostruct StringCompare<char*> : public std::binary_function<const char*, const char*, bool> 3585460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao{ 3595460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao bool operator()(const char* X, const char* Y) const 3605460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao { return (0 == std::strcmp(X, Y)); } 3615460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao}; 3625460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao 363f7ac0f19a1c8d0ad14bcf6456ce368b830fea886Stephen Hines} // namespace of hash 3645460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao} // namespace of mcld 3655460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao 3665460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao#endif 367affc150dc44fab1911775a49636d0ce85333b634Zonr Chang 368