StringHash.h revision 22add6ff3426df1a85089fe6a6e1597ee3b6f300
15460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao//===- 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 105460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao#ifndef MCLD_STRING_HASH_FUNCTION_H 115460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao#define MCLD_STRING_HASH_FUNCTION_H 125460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao#ifdef ENABLE_UNITTEST 135460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao#include <gtest.h> 145460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao#endif 155460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao#include <llvm/ADT/StringRef.h> 1622add6ff3426df1a85089fe6a6e1597ee3b6f300Shih-wei Liao#include <llvm/Support/DataTypes.h> 175460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao#include <llvm/Support/ErrorHandling.h> 1822add6ff3426df1a85089fe6a6e1597ee3b6f300Shih-wei Liao#include <cctype> 195460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao#include <functional> 205460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao 215460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liaonamespace mcld 225460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao{ 235460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao 245460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liaoenum StringHashType 255460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao{ 265460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao RS, 275460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao JS, 285460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao PJW, 295460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao ELF, 305460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao BKDR, 315460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao SDBM, 325460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao DJB, 335460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao DEK, 345460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao BP, 355460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao FNV, 3622add6ff3426df1a85089fe6a6e1597ee3b6f300Shih-wei Liao AP, 3722add6ff3426df1a85089fe6a6e1597ee3b6f300Shih-wei Liao ES 385460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao}; 395460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao 4022add6ff3426df1a85089fe6a6e1597ee3b6f300Shih-wei Liao/** \class template<uint32_t TYPE> StringHash 415460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao * \brief the template StringHash class, for specification 425460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao */ 4322add6ff3426df1a85089fe6a6e1597ee3b6f300Shih-wei Liaotemplate<uint32_t TYPE> 4422add6ff3426df1a85089fe6a6e1597ee3b6f300Shih-wei Liaostruct StringHash : public std::unary_function<const llvm::StringRef&, uint32_t> 455460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao{ 4622add6ff3426df1a85089fe6a6e1597ee3b6f300Shih-wei Liao uint32_t operator()(const llvm::StringRef& pKey) const 475460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao { 485460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao llvm::report_fatal_error("Undefined StringHash function.\n"); 495460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao } 505460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao}; 515460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao 525460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao/** \class StringHash<RSHash> 535460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao * \brief RS StringHash funciton 545460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao */ 555460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liaotemplate<> 5622add6ff3426df1a85089fe6a6e1597ee3b6f300Shih-wei Liaostruct StringHash<RS> : public std::unary_function<const llvm::StringRef&, uint32_t> 575460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao{ 5822add6ff3426df1a85089fe6a6e1597ee3b6f300Shih-wei Liao uint32_t operator()(const llvm::StringRef& pKey) const 595460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao { 605460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao const unsigned int b = 378551; 6122add6ff3426df1a85089fe6a6e1597ee3b6f300Shih-wei Liao uint32_t a = 63689; 6222add6ff3426df1a85089fe6a6e1597ee3b6f300Shih-wei Liao uint32_t hash_val = 0; 635460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao 645460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao for(unsigned int i = 0; i < pKey.size(); ++i) { 655460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao hash_val = hash_val * a + pKey[i]; 665460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao a = a * b; 675460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao } 685460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao return hash_val; 695460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao } 705460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao}; 715460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao 725460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao/** \class StringHash<JSHash> 735460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao * \brief JS hash funciton 745460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao */ 755460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liaotemplate<> 7622add6ff3426df1a85089fe6a6e1597ee3b6f300Shih-wei Liaostruct StringHash<JS> : public std::unary_function<const llvm::StringRef&, uint32_t> 775460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao{ 7822add6ff3426df1a85089fe6a6e1597ee3b6f300Shih-wei Liao uint32_t operator()(const llvm::StringRef& pKey) const 795460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao { 8022add6ff3426df1a85089fe6a6e1597ee3b6f300Shih-wei Liao uint32_t hash_val = 1315423911; 815460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao 825460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao for(unsigned int i = 0; i < pKey.size(); ++i) { 835460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao hash_val ^= ((hash_val << 5) + pKey[i] + (hash_val >> 2)); 84affc150dc44fab1911775a49636d0ce85333b634Zonr Chang } 855460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao return hash_val; 865460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao } 875460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao}; 885460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao 895460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao/** \class StringHash<PJW> 905460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao * \brief P.J. Weinberger hash function 915460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao */ 925460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liaotemplate<> 9322add6ff3426df1a85089fe6a6e1597ee3b6f300Shih-wei Liaostruct StringHash<PJW> : public std::unary_function<const llvm::StringRef&, uint32_t> 945460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao{ 9522add6ff3426df1a85089fe6a6e1597ee3b6f300Shih-wei Liao uint32_t operator()(const llvm::StringRef& pKey) const 965460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao { 975460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao const unsigned int BitsInUnsignedInt = (unsigned int)(sizeof(unsigned int) * 8); 985460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao const unsigned int ThreeQuarters = (unsigned int)((BitsInUnsignedInt * 3) / 4); 995460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao const unsigned int OneEighth = (unsigned int)(BitsInUnsignedInt / 8); 1005460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao const unsigned int HighBits = (unsigned int)(0xFFFFFFFF) << (BitsInUnsignedInt - OneEighth); 10122add6ff3426df1a85089fe6a6e1597ee3b6f300Shih-wei Liao uint32_t hash_val = 0; 10222add6ff3426df1a85089fe6a6e1597ee3b6f300Shih-wei Liao uint32_t test = 0; 1035460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao 1045460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao for(unsigned int i = 0; i < pKey.size(); ++i) { 1055460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao hash_val = (hash_val << OneEighth) + pKey[i]; 1065460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao 1075460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao if((test = hash_val & HighBits) != 0) { 1085460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao hash_val = (( hash_val ^ (test >> ThreeQuarters)) & (~HighBits)); 1095460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao } 1105460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao } 1115460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao return hash_val; 1125460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao } 1135460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao}; 1145460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao 1155460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao/** \class StringHash<ELF> 1165460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao * \brief ELF hash function. 1175460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao */ 1185460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liaotemplate<> 11922add6ff3426df1a85089fe6a6e1597ee3b6f300Shih-wei Liaostruct StringHash<ELF> : public std::unary_function<const llvm::StringRef&, uint32_t> 1205460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao{ 12122add6ff3426df1a85089fe6a6e1597ee3b6f300Shih-wei Liao uint32_t operator()(const llvm::StringRef& pKey) const 1225460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao { 12322add6ff3426df1a85089fe6a6e1597ee3b6f300Shih-wei Liao uint32_t hash_val = 0; 12422add6ff3426df1a85089fe6a6e1597ee3b6f300Shih-wei Liao uint32_t x = 0; 1255460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao 1265460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao for (unsigned int i = 0; i < pKey.size(); ++i) { 1275460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao hash_val = (hash_val << 4) + pKey[i]; 1285460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao if((x = hash_val & 0xF0000000L) != 0) 129affc150dc44fab1911775a49636d0ce85333b634Zonr Chang hash_val ^= (x >> 24); 1305460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao hash_val &= ~x; 1315460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao } 1325460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao return hash_val; 1335460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao } 1345460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao}; 1355460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao 1365460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao/** \class StringHash<BKDR> 1375460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao * \brief BKDR hash function 1385460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao */ 1395460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liaotemplate<> 14022add6ff3426df1a85089fe6a6e1597ee3b6f300Shih-wei Liaostruct StringHash<BKDR> : public std::unary_function<const llvm::StringRef&, uint32_t> 1415460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao{ 14222add6ff3426df1a85089fe6a6e1597ee3b6f300Shih-wei Liao uint32_t operator()(const llvm::StringRef& pKey) const 1435460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao { 14422add6ff3426df1a85089fe6a6e1597ee3b6f300Shih-wei Liao const uint32_t seed = 131; 14522add6ff3426df1a85089fe6a6e1597ee3b6f300Shih-wei Liao uint32_t hash_val = 0; 146affc150dc44fab1911775a49636d0ce85333b634Zonr Chang 14722add6ff3426df1a85089fe6a6e1597ee3b6f300Shih-wei Liao for(uint32_t i = 0; i < pKey.size(); ++i) 1485460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao hash_val = (hash_val * seed) + pKey[i]; 1495460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao return hash_val; 1505460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao } 1515460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao}; 1525460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao 1535460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao 1545460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao/** \class StringHash<SDBM> 1555460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao * \brief SDBM hash function 1565460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao * 0.049s in 100000 test 1575460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao */ 1585460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liaotemplate<> 15922add6ff3426df1a85089fe6a6e1597ee3b6f300Shih-wei Liaostruct StringHash<SDBM> : public std::unary_function<const llvm::StringRef&, uint32_t> 1605460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao{ 16122add6ff3426df1a85089fe6a6e1597ee3b6f300Shih-wei Liao uint32_t operator()(const llvm::StringRef& pKey) const 1625460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao { 16322add6ff3426df1a85089fe6a6e1597ee3b6f300Shih-wei Liao uint32_t hash_val = 0; 1645460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao 16522add6ff3426df1a85089fe6a6e1597ee3b6f300Shih-wei Liao for(uint32_t i = 0; i < pKey.size(); ++i) 1665460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao hash_val = pKey[i] + (hash_val << 6) + (hash_val << 16) - hash_val; 1675460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao return hash_val; 1685460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao } 1695460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao}; 1705460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao 1715460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao/** \class StringHash<DJB> 1725460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao * \brief DJB hash function 1735460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao * 0.057s in 100000 test 1745460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao */ 1755460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liaotemplate<> 17622add6ff3426df1a85089fe6a6e1597ee3b6f300Shih-wei Liaostruct StringHash<DJB> : public std::unary_function<const llvm::StringRef&, uint32_t> 1775460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao{ 17822add6ff3426df1a85089fe6a6e1597ee3b6f300Shih-wei Liao uint32_t operator()(const llvm::StringRef& pKey) const 1795460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao { 18022add6ff3426df1a85089fe6a6e1597ee3b6f300Shih-wei Liao uint32_t hash_val = 5381; 1815460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao 18222add6ff3426df1a85089fe6a6e1597ee3b6f300Shih-wei Liao for(uint32_t i = 0; i < pKey.size(); ++i) 1835460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao hash_val = ((hash_val << 5) + hash_val) + pKey[i]; 1845460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao 1855460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao return hash_val; 1865460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao } 1875460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao}; 1885460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao 1895460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao/** \class StringHash<DEK> 1905460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao * \brief DEK hash function 1915460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao * 0.60s 1925460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao */ 1935460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liaotemplate<> 19422add6ff3426df1a85089fe6a6e1597ee3b6f300Shih-wei Liaostruct StringHash<DEK> : public std::unary_function<const llvm::StringRef&, uint32_t> 1955460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao{ 19622add6ff3426df1a85089fe6a6e1597ee3b6f300Shih-wei Liao uint32_t operator()(const llvm::StringRef& pKey) const 1975460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao { 19822add6ff3426df1a85089fe6a6e1597ee3b6f300Shih-wei Liao uint32_t hash_val = pKey.size(); 1995460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao 20022add6ff3426df1a85089fe6a6e1597ee3b6f300Shih-wei Liao for(uint32_t i = 0; i < pKey.size(); ++i) 2015460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao hash_val = ((hash_val << 5) ^ (hash_val >> 27)) ^ pKey[i]; 2025460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao 2035460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao return hash_val; 2045460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao } 2055460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao}; 2065460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao 2075460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao/** \class StringHash<BP> 2085460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao * \brief BP hash function 2095460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao * 0.057s 2105460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao */ 2115460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liaotemplate<> 21222add6ff3426df1a85089fe6a6e1597ee3b6f300Shih-wei Liaostruct StringHash<BP> : public std::unary_function<const llvm::StringRef&, uint32_t> 2135460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao{ 21422add6ff3426df1a85089fe6a6e1597ee3b6f300Shih-wei Liao uint32_t operator()(const llvm::StringRef& pKey) const 2155460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao { 21622add6ff3426df1a85089fe6a6e1597ee3b6f300Shih-wei Liao uint32_t hash_val = 0; 21722add6ff3426df1a85089fe6a6e1597ee3b6f300Shih-wei Liao for(uint32_t i = 0; i < pKey.size(); ++i) 2185460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao hash_val = hash_val << 7 ^ pKey[i]; 2195460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao 2205460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao return hash_val; 2215460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao } 2225460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao}; 2235460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao 2245460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao/** \class StringHash<FNV> 2255460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao * \brief FNV hash function 2265460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao * 0.058s 2275460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao */ 2285460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liaotemplate<> 22922add6ff3426df1a85089fe6a6e1597ee3b6f300Shih-wei Liaostruct StringHash<FNV> : public std::unary_function<const llvm::StringRef&, uint32_t> 2305460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao{ 23122add6ff3426df1a85089fe6a6e1597ee3b6f300Shih-wei Liao uint32_t operator()(const llvm::StringRef& pKey) const 2325460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao { 23322add6ff3426df1a85089fe6a6e1597ee3b6f300Shih-wei Liao const uint32_t fnv_prime = 0x811C9DC5; 23422add6ff3426df1a85089fe6a6e1597ee3b6f300Shih-wei Liao uint32_t hash_val = 0; 23522add6ff3426df1a85089fe6a6e1597ee3b6f300Shih-wei Liao for(uint32_t i = 0; i < pKey.size(); ++i) { 2365460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao hash_val *= fnv_prime; 2375460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao hash_val ^= pKey[i]; 2385460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao } 2395460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao 2405460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao return hash_val; 2415460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao } 2425460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao}; 2435460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao 2445460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao/** \class StringHash<AP> 2455460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao * \brief AP hash function 2465460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao * 0.060s 2475460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao */ 2485460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liaotemplate<> 24922add6ff3426df1a85089fe6a6e1597ee3b6f300Shih-wei Liaostruct StringHash<AP> : public std::unary_function<const llvm::StringRef&, uint32_t> 2505460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao{ 25122add6ff3426df1a85089fe6a6e1597ee3b6f300Shih-wei Liao uint32_t operator()(const llvm::StringRef& pKey) const 2525460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao { 2535460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao unsigned int hash_val = 0xAAAAAAAA; 254affc150dc44fab1911775a49636d0ce85333b634Zonr Chang 25522add6ff3426df1a85089fe6a6e1597ee3b6f300Shih-wei Liao for(uint32_t i = 0; i < pKey.size(); ++i) { 2565460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao hash_val ^= ((i & 1) == 0)? 2575460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao ((hash_val << 7) ^ pKey[i] * (hash_val >> 3)): 2585460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao (~((hash_val << 11) + (pKey[i] ^ (hash_val >> 5)))); 2595460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao } 260affc150dc44fab1911775a49636d0ce85333b634Zonr Chang 2615460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao return hash_val; 2625460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao } 2635460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao}; 2645460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao 26522add6ff3426df1a85089fe6a6e1597ee3b6f300Shih-wei Liao/** \class StringHash<ES> 26622add6ff3426df1a85089fe6a6e1597ee3b6f300Shih-wei Liao * \brief This is a revision of Edward Sayers' string characteristic function. 26722add6ff3426df1a85089fe6a6e1597ee3b6f300Shih-wei Liao * 26822add6ff3426df1a85089fe6a6e1597ee3b6f300Shih-wei Liao * 31-28 27 26 25 - 0 26922add6ff3426df1a85089fe6a6e1597ee3b6f300Shih-wei Liao * +----+---+---+------------+ 27022add6ff3426df1a85089fe6a6e1597ee3b6f300Shih-wei Liao * | . | N | - | a/A ~ z/Z | 27122add6ff3426df1a85089fe6a6e1597ee3b6f300Shih-wei Liao * +----+---+---+------------+ 27222add6ff3426df1a85089fe6a6e1597ee3b6f300Shih-wei Liao * 27322add6ff3426df1a85089fe6a6e1597ee3b6f300Shih-wei Liao * . (bit 31~28) - The number of '.' characters 27422add6ff3426df1a85089fe6a6e1597ee3b6f300Shih-wei Liao * N (bit 27) - Are there any numbers in the string 27522add6ff3426df1a85089fe6a6e1597ee3b6f300Shih-wei Liao * - (bit 26) - Does the string have '-' character 27622add6ff3426df1a85089fe6a6e1597ee3b6f300Shih-wei Liao * bit 25~0 - Bit 25 is set only if the string contains a 'a' or 'A', and 27722add6ff3426df1a85089fe6a6e1597ee3b6f300Shih-wei Liao * Bit 24 is set only if ... 'b' or 'B', ... 27822add6ff3426df1a85089fe6a6e1597ee3b6f300Shih-wei Liao */ 27922add6ff3426df1a85089fe6a6e1597ee3b6f300Shih-wei Liaotemplate<> 28022add6ff3426df1a85089fe6a6e1597ee3b6f300Shih-wei Liaostruct StringHash<ES> : public std::unary_function<const llvm::StringRef&, uint32_t> 28122add6ff3426df1a85089fe6a6e1597ee3b6f300Shih-wei Liao{ 28222add6ff3426df1a85089fe6a6e1597ee3b6f300Shih-wei Liao uint32_t operator()(const llvm::StringRef& pString) const 28322add6ff3426df1a85089fe6a6e1597ee3b6f300Shih-wei Liao { 28422add6ff3426df1a85089fe6a6e1597ee3b6f300Shih-wei Liao uint32_t result = 0x0; 28522add6ff3426df1a85089fe6a6e1597ee3b6f300Shih-wei Liao unsigned int dot = 0; 28622add6ff3426df1a85089fe6a6e1597ee3b6f300Shih-wei Liao std::string::size_type idx; 28722add6ff3426df1a85089fe6a6e1597ee3b6f300Shih-wei Liao for (idx = 0; idx < pString.size(); ++idx) { 28822add6ff3426df1a85089fe6a6e1597ee3b6f300Shih-wei Liao int cur_char = pString[idx]; 28922add6ff3426df1a85089fe6a6e1597ee3b6f300Shih-wei Liao 29022add6ff3426df1a85089fe6a6e1597ee3b6f300Shih-wei Liao if ('.' == cur_char) { 29122add6ff3426df1a85089fe6a6e1597ee3b6f300Shih-wei Liao ++dot; 29222add6ff3426df1a85089fe6a6e1597ee3b6f300Shih-wei Liao continue; 29322add6ff3426df1a85089fe6a6e1597ee3b6f300Shih-wei Liao } 29422add6ff3426df1a85089fe6a6e1597ee3b6f300Shih-wei Liao 29522add6ff3426df1a85089fe6a6e1597ee3b6f300Shih-wei Liao if (isdigit(cur_char)) { 29622add6ff3426df1a85089fe6a6e1597ee3b6f300Shih-wei Liao result |= (1 << 27); 29722add6ff3426df1a85089fe6a6e1597ee3b6f300Shih-wei Liao continue; 29822add6ff3426df1a85089fe6a6e1597ee3b6f300Shih-wei Liao } 29922add6ff3426df1a85089fe6a6e1597ee3b6f300Shih-wei Liao 30022add6ff3426df1a85089fe6a6e1597ee3b6f300Shih-wei Liao if ('_' == cur_char) { 30122add6ff3426df1a85089fe6a6e1597ee3b6f300Shih-wei Liao result |= (1 << 26); 30222add6ff3426df1a85089fe6a6e1597ee3b6f300Shih-wei Liao continue; 30322add6ff3426df1a85089fe6a6e1597ee3b6f300Shih-wei Liao } 30422add6ff3426df1a85089fe6a6e1597ee3b6f300Shih-wei Liao 30522add6ff3426df1a85089fe6a6e1597ee3b6f300Shih-wei Liao if (isupper(cur_char)) { 30622add6ff3426df1a85089fe6a6e1597ee3b6f300Shih-wei Liao result |= (1 << (cur_char - 'A')); 30722add6ff3426df1a85089fe6a6e1597ee3b6f300Shih-wei Liao continue; 30822add6ff3426df1a85089fe6a6e1597ee3b6f300Shih-wei Liao } 30922add6ff3426df1a85089fe6a6e1597ee3b6f300Shih-wei Liao 31022add6ff3426df1a85089fe6a6e1597ee3b6f300Shih-wei Liao if (islower(cur_char)) { 31122add6ff3426df1a85089fe6a6e1597ee3b6f300Shih-wei Liao result |= (1 << (cur_char - 'a')); 31222add6ff3426df1a85089fe6a6e1597ee3b6f300Shih-wei Liao continue; 31322add6ff3426df1a85089fe6a6e1597ee3b6f300Shih-wei Liao } 31422add6ff3426df1a85089fe6a6e1597ee3b6f300Shih-wei Liao } 31522add6ff3426df1a85089fe6a6e1597ee3b6f300Shih-wei Liao result |= (dot << 28); 31622add6ff3426df1a85089fe6a6e1597ee3b6f300Shih-wei Liao return result; 31722add6ff3426df1a85089fe6a6e1597ee3b6f300Shih-wei Liao } 31822add6ff3426df1a85089fe6a6e1597ee3b6f300Shih-wei Liao 31922add6ff3426df1a85089fe6a6e1597ee3b6f300Shih-wei Liao 32022add6ff3426df1a85089fe6a6e1597ee3b6f300Shih-wei Liao /** \func may_include 32122add6ff3426df1a85089fe6a6e1597ee3b6f300Shih-wei Liao * \brief is it possible that pRule is a sub-string of pInString 32222add6ff3426df1a85089fe6a6e1597ee3b6f300Shih-wei Liao */ 32322add6ff3426df1a85089fe6a6e1597ee3b6f300Shih-wei Liao static bool may_include(uint32_t pRule, uint32_t pInString) 32422add6ff3426df1a85089fe6a6e1597ee3b6f300Shih-wei Liao { 32522add6ff3426df1a85089fe6a6e1597ee3b6f300Shih-wei Liao uint32_t in_c = pInString << 4; 32622add6ff3426df1a85089fe6a6e1597ee3b6f300Shih-wei Liao uint32_t r_c = pRule << 4; 32722add6ff3426df1a85089fe6a6e1597ee3b6f300Shih-wei Liao 32822add6ff3426df1a85089fe6a6e1597ee3b6f300Shih-wei Liao uint32_t res = (in_c ^ r_c) & r_c; 32922add6ff3426df1a85089fe6a6e1597ee3b6f300Shih-wei Liao if (0 != res) 33022add6ff3426df1a85089fe6a6e1597ee3b6f300Shih-wei Liao return false; 33122add6ff3426df1a85089fe6a6e1597ee3b6f300Shih-wei Liao 33222add6ff3426df1a85089fe6a6e1597ee3b6f300Shih-wei Liao uint32_t in_dot = pInString >> 28; 33322add6ff3426df1a85089fe6a6e1597ee3b6f300Shih-wei Liao uint32_t r_dot = pRule >> 28; 33422add6ff3426df1a85089fe6a6e1597ee3b6f300Shih-wei Liao if (r_dot > in_dot) 33522add6ff3426df1a85089fe6a6e1597ee3b6f300Shih-wei Liao return false; 33622add6ff3426df1a85089fe6a6e1597ee3b6f300Shih-wei Liao 33722add6ff3426df1a85089fe6a6e1597ee3b6f300Shih-wei Liao return true; 33822add6ff3426df1a85089fe6a6e1597ee3b6f300Shih-wei Liao } 33922add6ff3426df1a85089fe6a6e1597ee3b6f300Shih-wei Liao}; 34022add6ff3426df1a85089fe6a6e1597ee3b6f300Shih-wei Liao 34122add6ff3426df1a85089fe6a6e1597ee3b6f300Shih-wei Liao/** \class template<uint32_t TYPE> StringCompare 3425460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao * \brief the template StringCompare class, for specification 3435460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao */ 3445460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liaotemplate<typename STRING_TYPE> 3455460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liaostruct StringCompare : public std::binary_function<const STRING_TYPE&, const STRING_TYPE&, bool> 3465460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao{ 3475460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao bool operator()(const STRING_TYPE& X, const STRING_TYPE& Y) const 3485460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao { return X == Y; } 3495460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao}; 3505460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao 3515460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liaotemplate<> 3525460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liaostruct StringCompare<const char*> : public std::binary_function<const char*, const char*, bool> 3535460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao{ 3545460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao bool operator()(const char* X, const char* Y) const 3555460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao { return (0 == std::strcmp(X, Y)); } 3565460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao}; 3575460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao 3585460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liaotemplate<> 3595460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liaostruct StringCompare<char*> : public std::binary_function<const char*, const char*, bool> 3605460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao{ 3615460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao bool operator()(const char* X, const char* Y) const 3625460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao { return (0 == std::strcmp(X, Y)); } 3635460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao}; 3645460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao 3655460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao} // namespace of mcld 3665460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao 3675460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao#endif 368affc150dc44fab1911775a49636d0ce85333b634Zonr Chang 369