StringHash.h revision 87f34658dec9097d987d254a990ea7f311bfc95f
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//===----------------------------------------------------------------------===// 987f34658dec9097d987d254a990ea7f311bfc95fStephen Hines#ifndef MCLD_ADT_STRINGHASH_H 1087f34658dec9097d987d254a990ea7f311bfc95fStephen Hines#define MCLD_ADT_STRINGHASH_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> 1622add6ff3426df1a85089fe6a6e1597ee3b6f300Shih-wei Liao#include <cctype> 1787f34658dec9097d987d254a990ea7f311bfc95fStephen Hines#include <cassert> 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 { 4687f34658dec9097d987d254a990ea7f311bfc95fStephen Hines assert(false && "Undefined StringHash function.\n"); 4787f34658dec9097d987d254a990ea7f311bfc95fStephen Hines return 0; 485460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao } 495460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao}; 505460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao 515460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao/** \class StringHash<RSHash> 525460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao * \brief RS StringHash funciton 535460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao */ 545460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liaotemplate<> 5522add6ff3426df1a85089fe6a6e1597ee3b6f300Shih-wei Liaostruct StringHash<RS> : public std::unary_function<const llvm::StringRef&, uint32_t> 565460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao{ 5722add6ff3426df1a85089fe6a6e1597ee3b6f300Shih-wei Liao uint32_t operator()(const llvm::StringRef& pKey) const 585460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao { 595460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao const unsigned int b = 378551; 6022add6ff3426df1a85089fe6a6e1597ee3b6f300Shih-wei Liao uint32_t a = 63689; 6122add6ff3426df1a85089fe6a6e1597ee3b6f300Shih-wei Liao uint32_t hash_val = 0; 625460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao 635460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao for(unsigned int i = 0; i < pKey.size(); ++i) { 645460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao hash_val = hash_val * a + pKey[i]; 655460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao a = a * b; 665460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao } 675460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao return hash_val; 685460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao } 695460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao}; 705460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao 715460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao/** \class StringHash<JSHash> 725460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao * \brief JS hash funciton 735460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao */ 745460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liaotemplate<> 7522add6ff3426df1a85089fe6a6e1597ee3b6f300Shih-wei Liaostruct StringHash<JS> : public std::unary_function<const llvm::StringRef&, uint32_t> 765460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao{ 7722add6ff3426df1a85089fe6a6e1597ee3b6f300Shih-wei Liao uint32_t operator()(const llvm::StringRef& pKey) const 785460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao { 7922add6ff3426df1a85089fe6a6e1597ee3b6f300Shih-wei Liao uint32_t hash_val = 1315423911; 805460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao 815460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao for(unsigned int i = 0; i < pKey.size(); ++i) { 825460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao hash_val ^= ((hash_val << 5) + pKey[i] + (hash_val >> 2)); 83affc150dc44fab1911775a49636d0ce85333b634Zonr Chang } 845460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao return hash_val; 855460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao } 865460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao}; 875460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao 885460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao/** \class StringHash<PJW> 895460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao * \brief P.J. Weinberger hash function 905460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao */ 915460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liaotemplate<> 9222add6ff3426df1a85089fe6a6e1597ee3b6f300Shih-wei Liaostruct StringHash<PJW> : public std::unary_function<const llvm::StringRef&, uint32_t> 935460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao{ 9422add6ff3426df1a85089fe6a6e1597ee3b6f300Shih-wei Liao uint32_t operator()(const llvm::StringRef& pKey) const 955460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao { 965460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao const unsigned int BitsInUnsignedInt = (unsigned int)(sizeof(unsigned int) * 8); 975460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao const unsigned int ThreeQuarters = (unsigned int)((BitsInUnsignedInt * 3) / 4); 985460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao const unsigned int OneEighth = (unsigned int)(BitsInUnsignedInt / 8); 995460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao const unsigned int HighBits = (unsigned int)(0xFFFFFFFF) << (BitsInUnsignedInt - OneEighth); 10022add6ff3426df1a85089fe6a6e1597ee3b6f300Shih-wei Liao uint32_t hash_val = 0; 10122add6ff3426df1a85089fe6a6e1597ee3b6f300Shih-wei Liao uint32_t test = 0; 1025460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao 1035460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao for(unsigned int i = 0; i < pKey.size(); ++i) { 1045460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao hash_val = (hash_val << OneEighth) + pKey[i]; 1055460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao 1065460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao if((test = hash_val & HighBits) != 0) { 1075460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao hash_val = (( hash_val ^ (test >> ThreeQuarters)) & (~HighBits)); 1085460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao } 1095460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao } 1105460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao return hash_val; 1115460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao } 1125460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao}; 1135460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao 1145460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao/** \class StringHash<ELF> 1155460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao * \brief ELF hash function. 1165460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao */ 1175460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liaotemplate<> 11822add6ff3426df1a85089fe6a6e1597ee3b6f300Shih-wei Liaostruct StringHash<ELF> : public std::unary_function<const llvm::StringRef&, uint32_t> 1195460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao{ 12022add6ff3426df1a85089fe6a6e1597ee3b6f300Shih-wei Liao uint32_t operator()(const llvm::StringRef& pKey) const 1215460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao { 12222add6ff3426df1a85089fe6a6e1597ee3b6f300Shih-wei Liao uint32_t hash_val = 0; 12322add6ff3426df1a85089fe6a6e1597ee3b6f300Shih-wei Liao uint32_t x = 0; 1245460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao 1255460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao for (unsigned int i = 0; i < pKey.size(); ++i) { 1265460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao hash_val = (hash_val << 4) + pKey[i]; 1275460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao if((x = hash_val & 0xF0000000L) != 0) 128affc150dc44fab1911775a49636d0ce85333b634Zonr Chang hash_val ^= (x >> 24); 1295460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao hash_val &= ~x; 1305460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao } 1315460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao return hash_val; 1325460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao } 1335460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao}; 1345460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao 1355460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao/** \class StringHash<BKDR> 1365460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao * \brief BKDR hash function 1375460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao */ 1385460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liaotemplate<> 13922add6ff3426df1a85089fe6a6e1597ee3b6f300Shih-wei Liaostruct StringHash<BKDR> : public std::unary_function<const llvm::StringRef&, uint32_t> 1405460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao{ 14122add6ff3426df1a85089fe6a6e1597ee3b6f300Shih-wei Liao uint32_t operator()(const llvm::StringRef& pKey) const 1425460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao { 14322add6ff3426df1a85089fe6a6e1597ee3b6f300Shih-wei Liao const uint32_t seed = 131; 14422add6ff3426df1a85089fe6a6e1597ee3b6f300Shih-wei Liao uint32_t hash_val = 0; 145affc150dc44fab1911775a49636d0ce85333b634Zonr Chang 14622add6ff3426df1a85089fe6a6e1597ee3b6f300Shih-wei Liao for(uint32_t i = 0; i < pKey.size(); ++i) 1475460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao hash_val = (hash_val * seed) + pKey[i]; 1485460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao return hash_val; 1495460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao } 1505460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao}; 1515460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao 1525460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao 1535460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao/** \class StringHash<SDBM> 1545460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao * \brief SDBM hash function 1555460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao * 0.049s in 100000 test 1565460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao */ 1575460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liaotemplate<> 15822add6ff3426df1a85089fe6a6e1597ee3b6f300Shih-wei Liaostruct StringHash<SDBM> : public std::unary_function<const llvm::StringRef&, uint32_t> 1595460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao{ 16022add6ff3426df1a85089fe6a6e1597ee3b6f300Shih-wei Liao uint32_t operator()(const llvm::StringRef& pKey) const 1615460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao { 16222add6ff3426df1a85089fe6a6e1597ee3b6f300Shih-wei Liao uint32_t hash_val = 0; 1635460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao 16422add6ff3426df1a85089fe6a6e1597ee3b6f300Shih-wei Liao for(uint32_t i = 0; i < pKey.size(); ++i) 1655460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao hash_val = pKey[i] + (hash_val << 6) + (hash_val << 16) - hash_val; 1665460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao return hash_val; 1675460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao } 1685460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao}; 1695460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao 1705460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao/** \class StringHash<DJB> 1715460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao * \brief DJB hash function 1725460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao * 0.057s in 100000 test 1735460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao */ 1745460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liaotemplate<> 17522add6ff3426df1a85089fe6a6e1597ee3b6f300Shih-wei Liaostruct StringHash<DJB> : public std::unary_function<const llvm::StringRef&, uint32_t> 1765460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao{ 17722add6ff3426df1a85089fe6a6e1597ee3b6f300Shih-wei Liao uint32_t operator()(const llvm::StringRef& pKey) const 1785460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao { 17922add6ff3426df1a85089fe6a6e1597ee3b6f300Shih-wei Liao uint32_t hash_val = 5381; 1805460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao 18122add6ff3426df1a85089fe6a6e1597ee3b6f300Shih-wei Liao for(uint32_t i = 0; i < pKey.size(); ++i) 1825460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao hash_val = ((hash_val << 5) + hash_val) + pKey[i]; 1835460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao 1845460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao return hash_val; 1855460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao } 1865460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao}; 1875460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao 1885460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao/** \class StringHash<DEK> 1895460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao * \brief DEK hash function 1905460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao * 0.60s 1915460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao */ 1925460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liaotemplate<> 19322add6ff3426df1a85089fe6a6e1597ee3b6f300Shih-wei Liaostruct StringHash<DEK> : public std::unary_function<const llvm::StringRef&, uint32_t> 1945460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao{ 19522add6ff3426df1a85089fe6a6e1597ee3b6f300Shih-wei Liao uint32_t operator()(const llvm::StringRef& pKey) const 1965460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao { 19722add6ff3426df1a85089fe6a6e1597ee3b6f300Shih-wei Liao uint32_t hash_val = pKey.size(); 1985460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao 19922add6ff3426df1a85089fe6a6e1597ee3b6f300Shih-wei Liao for(uint32_t i = 0; i < pKey.size(); ++i) 2005460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao hash_val = ((hash_val << 5) ^ (hash_val >> 27)) ^ pKey[i]; 2015460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao 2025460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao return hash_val; 2035460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao } 2045460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao}; 2055460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao 2065460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao/** \class StringHash<BP> 2075460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao * \brief BP hash function 2085460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao * 0.057s 2095460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao */ 2105460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liaotemplate<> 21122add6ff3426df1a85089fe6a6e1597ee3b6f300Shih-wei Liaostruct StringHash<BP> : public std::unary_function<const llvm::StringRef&, uint32_t> 2125460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao{ 21322add6ff3426df1a85089fe6a6e1597ee3b6f300Shih-wei Liao uint32_t operator()(const llvm::StringRef& pKey) const 2145460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao { 21522add6ff3426df1a85089fe6a6e1597ee3b6f300Shih-wei Liao uint32_t hash_val = 0; 21622add6ff3426df1a85089fe6a6e1597ee3b6f300Shih-wei Liao for(uint32_t i = 0; i < pKey.size(); ++i) 2175460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao hash_val = hash_val << 7 ^ pKey[i]; 2185460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao 2195460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao return hash_val; 2205460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao } 2215460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao}; 2225460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao 2235460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao/** \class StringHash<FNV> 2245460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao * \brief FNV hash function 2255460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao * 0.058s 2265460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao */ 2275460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liaotemplate<> 22822add6ff3426df1a85089fe6a6e1597ee3b6f300Shih-wei Liaostruct StringHash<FNV> : public std::unary_function<const llvm::StringRef&, uint32_t> 2295460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao{ 23022add6ff3426df1a85089fe6a6e1597ee3b6f300Shih-wei Liao uint32_t operator()(const llvm::StringRef& pKey) const 2315460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao { 23222add6ff3426df1a85089fe6a6e1597ee3b6f300Shih-wei Liao const uint32_t fnv_prime = 0x811C9DC5; 23322add6ff3426df1a85089fe6a6e1597ee3b6f300Shih-wei Liao uint32_t hash_val = 0; 23422add6ff3426df1a85089fe6a6e1597ee3b6f300Shih-wei Liao for(uint32_t i = 0; i < pKey.size(); ++i) { 2355460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao hash_val *= fnv_prime; 2365460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao hash_val ^= pKey[i]; 2375460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao } 2385460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao 2395460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao return hash_val; 2405460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao } 2415460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao}; 2425460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao 2435460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao/** \class StringHash<AP> 2445460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao * \brief AP hash function 2455460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao * 0.060s 2465460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao */ 2475460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liaotemplate<> 24822add6ff3426df1a85089fe6a6e1597ee3b6f300Shih-wei Liaostruct StringHash<AP> : public std::unary_function<const llvm::StringRef&, uint32_t> 2495460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao{ 25022add6ff3426df1a85089fe6a6e1597ee3b6f300Shih-wei Liao uint32_t operator()(const llvm::StringRef& pKey) const 2515460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao { 2525460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao unsigned int hash_val = 0xAAAAAAAA; 253affc150dc44fab1911775a49636d0ce85333b634Zonr Chang 25422add6ff3426df1a85089fe6a6e1597ee3b6f300Shih-wei Liao for(uint32_t i = 0; i < pKey.size(); ++i) { 2555460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao hash_val ^= ((i & 1) == 0)? 2565460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao ((hash_val << 7) ^ pKey[i] * (hash_val >> 3)): 2575460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao (~((hash_val << 11) + (pKey[i] ^ (hash_val >> 5)))); 2585460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao } 259affc150dc44fab1911775a49636d0ce85333b634Zonr Chang 2605460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao return hash_val; 2615460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao } 2625460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao}; 2635460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao 26422add6ff3426df1a85089fe6a6e1597ee3b6f300Shih-wei Liao/** \class StringHash<ES> 26522add6ff3426df1a85089fe6a6e1597ee3b6f300Shih-wei Liao * \brief This is a revision of Edward Sayers' string characteristic function. 26622add6ff3426df1a85089fe6a6e1597ee3b6f300Shih-wei Liao * 26722add6ff3426df1a85089fe6a6e1597ee3b6f300Shih-wei Liao * 31-28 27 26 25 - 0 26822add6ff3426df1a85089fe6a6e1597ee3b6f300Shih-wei Liao * +----+---+---+------------+ 26922add6ff3426df1a85089fe6a6e1597ee3b6f300Shih-wei Liao * | . | N | - | a/A ~ z/Z | 27022add6ff3426df1a85089fe6a6e1597ee3b6f300Shih-wei Liao * +----+---+---+------------+ 27122add6ff3426df1a85089fe6a6e1597ee3b6f300Shih-wei Liao * 27222add6ff3426df1a85089fe6a6e1597ee3b6f300Shih-wei Liao * . (bit 31~28) - The number of '.' characters 27322add6ff3426df1a85089fe6a6e1597ee3b6f300Shih-wei Liao * N (bit 27) - Are there any numbers in the string 27422add6ff3426df1a85089fe6a6e1597ee3b6f300Shih-wei Liao * - (bit 26) - Does the string have '-' character 27522add6ff3426df1a85089fe6a6e1597ee3b6f300Shih-wei Liao * bit 25~0 - Bit 25 is set only if the string contains a 'a' or 'A', and 27622add6ff3426df1a85089fe6a6e1597ee3b6f300Shih-wei Liao * Bit 24 is set only if ... 'b' or 'B', ... 27722add6ff3426df1a85089fe6a6e1597ee3b6f300Shih-wei Liao */ 27822add6ff3426df1a85089fe6a6e1597ee3b6f300Shih-wei Liaotemplate<> 27922add6ff3426df1a85089fe6a6e1597ee3b6f300Shih-wei Liaostruct StringHash<ES> : public std::unary_function<const llvm::StringRef&, uint32_t> 28022add6ff3426df1a85089fe6a6e1597ee3b6f300Shih-wei Liao{ 28122add6ff3426df1a85089fe6a6e1597ee3b6f300Shih-wei Liao uint32_t operator()(const llvm::StringRef& pString) const 28222add6ff3426df1a85089fe6a6e1597ee3b6f300Shih-wei Liao { 28322add6ff3426df1a85089fe6a6e1597ee3b6f300Shih-wei Liao uint32_t result = 0x0; 28422add6ff3426df1a85089fe6a6e1597ee3b6f300Shih-wei Liao unsigned int dot = 0; 28522add6ff3426df1a85089fe6a6e1597ee3b6f300Shih-wei Liao std::string::size_type idx; 28622add6ff3426df1a85089fe6a6e1597ee3b6f300Shih-wei Liao for (idx = 0; idx < pString.size(); ++idx) { 28722add6ff3426df1a85089fe6a6e1597ee3b6f300Shih-wei Liao int cur_char = pString[idx]; 28822add6ff3426df1a85089fe6a6e1597ee3b6f300Shih-wei Liao 28922add6ff3426df1a85089fe6a6e1597ee3b6f300Shih-wei Liao if ('.' == cur_char) { 29022add6ff3426df1a85089fe6a6e1597ee3b6f300Shih-wei Liao ++dot; 29122add6ff3426df1a85089fe6a6e1597ee3b6f300Shih-wei Liao continue; 29222add6ff3426df1a85089fe6a6e1597ee3b6f300Shih-wei Liao } 29322add6ff3426df1a85089fe6a6e1597ee3b6f300Shih-wei Liao 29422add6ff3426df1a85089fe6a6e1597ee3b6f300Shih-wei Liao if (isdigit(cur_char)) { 29522add6ff3426df1a85089fe6a6e1597ee3b6f300Shih-wei Liao result |= (1 << 27); 29622add6ff3426df1a85089fe6a6e1597ee3b6f300Shih-wei Liao continue; 29722add6ff3426df1a85089fe6a6e1597ee3b6f300Shih-wei Liao } 29822add6ff3426df1a85089fe6a6e1597ee3b6f300Shih-wei Liao 29922add6ff3426df1a85089fe6a6e1597ee3b6f300Shih-wei Liao if ('_' == cur_char) { 30022add6ff3426df1a85089fe6a6e1597ee3b6f300Shih-wei Liao result |= (1 << 26); 30122add6ff3426df1a85089fe6a6e1597ee3b6f300Shih-wei Liao continue; 30222add6ff3426df1a85089fe6a6e1597ee3b6f300Shih-wei Liao } 30322add6ff3426df1a85089fe6a6e1597ee3b6f300Shih-wei Liao 30422add6ff3426df1a85089fe6a6e1597ee3b6f300Shih-wei Liao if (isupper(cur_char)) { 30522add6ff3426df1a85089fe6a6e1597ee3b6f300Shih-wei Liao result |= (1 << (cur_char - 'A')); 30622add6ff3426df1a85089fe6a6e1597ee3b6f300Shih-wei Liao continue; 30722add6ff3426df1a85089fe6a6e1597ee3b6f300Shih-wei Liao } 30822add6ff3426df1a85089fe6a6e1597ee3b6f300Shih-wei Liao 30922add6ff3426df1a85089fe6a6e1597ee3b6f300Shih-wei Liao if (islower(cur_char)) { 31022add6ff3426df1a85089fe6a6e1597ee3b6f300Shih-wei Liao result |= (1 << (cur_char - 'a')); 31122add6ff3426df1a85089fe6a6e1597ee3b6f300Shih-wei Liao continue; 31222add6ff3426df1a85089fe6a6e1597ee3b6f300Shih-wei Liao } 31322add6ff3426df1a85089fe6a6e1597ee3b6f300Shih-wei Liao } 31422add6ff3426df1a85089fe6a6e1597ee3b6f300Shih-wei Liao result |= (dot << 28); 31522add6ff3426df1a85089fe6a6e1597ee3b6f300Shih-wei Liao return result; 31622add6ff3426df1a85089fe6a6e1597ee3b6f300Shih-wei Liao } 31722add6ff3426df1a85089fe6a6e1597ee3b6f300Shih-wei Liao 31822add6ff3426df1a85089fe6a6e1597ee3b6f300Shih-wei Liao 31922add6ff3426df1a85089fe6a6e1597ee3b6f300Shih-wei Liao /** \func may_include 32022add6ff3426df1a85089fe6a6e1597ee3b6f300Shih-wei Liao * \brief is it possible that pRule is a sub-string of pInString 32122add6ff3426df1a85089fe6a6e1597ee3b6f300Shih-wei Liao */ 32222add6ff3426df1a85089fe6a6e1597ee3b6f300Shih-wei Liao static bool may_include(uint32_t pRule, uint32_t pInString) 32322add6ff3426df1a85089fe6a6e1597ee3b6f300Shih-wei Liao { 32422add6ff3426df1a85089fe6a6e1597ee3b6f300Shih-wei Liao uint32_t in_c = pInString << 4; 32522add6ff3426df1a85089fe6a6e1597ee3b6f300Shih-wei Liao uint32_t r_c = pRule << 4; 32622add6ff3426df1a85089fe6a6e1597ee3b6f300Shih-wei Liao 32722add6ff3426df1a85089fe6a6e1597ee3b6f300Shih-wei Liao uint32_t res = (in_c ^ r_c) & r_c; 32822add6ff3426df1a85089fe6a6e1597ee3b6f300Shih-wei Liao if (0 != res) 32922add6ff3426df1a85089fe6a6e1597ee3b6f300Shih-wei Liao return false; 33022add6ff3426df1a85089fe6a6e1597ee3b6f300Shih-wei Liao 33122add6ff3426df1a85089fe6a6e1597ee3b6f300Shih-wei Liao uint32_t in_dot = pInString >> 28; 33222add6ff3426df1a85089fe6a6e1597ee3b6f300Shih-wei Liao uint32_t r_dot = pRule >> 28; 33322add6ff3426df1a85089fe6a6e1597ee3b6f300Shih-wei Liao if (r_dot > in_dot) 33422add6ff3426df1a85089fe6a6e1597ee3b6f300Shih-wei Liao return false; 33522add6ff3426df1a85089fe6a6e1597ee3b6f300Shih-wei Liao 33622add6ff3426df1a85089fe6a6e1597ee3b6f300Shih-wei Liao return true; 33722add6ff3426df1a85089fe6a6e1597ee3b6f300Shih-wei Liao } 33822add6ff3426df1a85089fe6a6e1597ee3b6f300Shih-wei Liao}; 33922add6ff3426df1a85089fe6a6e1597ee3b6f300Shih-wei Liao 34022add6ff3426df1a85089fe6a6e1597ee3b6f300Shih-wei Liao/** \class template<uint32_t TYPE> StringCompare 3415460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao * \brief the template StringCompare class, for specification 3425460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao */ 3435460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liaotemplate<typename STRING_TYPE> 3445460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liaostruct StringCompare : public std::binary_function<const STRING_TYPE&, const STRING_TYPE&, bool> 3455460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao{ 3465460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao bool operator()(const STRING_TYPE& X, const STRING_TYPE& Y) const 3475460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao { return X == Y; } 3485460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao}; 3495460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao 3505460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liaotemplate<> 3515460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liaostruct StringCompare<const char*> : public std::binary_function<const char*, const char*, bool> 3525460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao{ 3535460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao bool operator()(const char* X, const char* Y) const 3545460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao { return (0 == std::strcmp(X, Y)); } 3555460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao}; 3565460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao 3575460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liaotemplate<> 3585460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liaostruct StringCompare<char*> : public std::binary_function<const char*, const char*, bool> 3595460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao{ 3605460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao bool operator()(const char* X, const char* Y) const 3615460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao { return (0 == std::strcmp(X, Y)); } 3625460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao}; 3635460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao 364f7ac0f19a1c8d0ad14bcf6456ce368b830fea886Stephen Hines} // namespace of hash 3655460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao} // namespace of mcld 3665460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao 3675460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao#endif 368affc150dc44fab1911775a49636d0ce85333b634Zonr Chang 369