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#include <llvm/ADT/StringRef.h> 1222add6ff3426df1a85089fe6a6e1597ee3b6f300Shih-wei Liao#include <llvm/Support/DataTypes.h> 1322add6ff3426df1a85089fe6a6e1597ee3b6f300Shih-wei Liao#include <cctype> 1487f34658dec9097d987d254a990ea7f311bfc95fStephen Hines#include <cassert> 155460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao#include <functional> 165460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao 17f7ac0f19a1c8d0ad14bcf6456ce368b830fea886Stephen Hinesnamespace mcld { 18f7ac0f19a1c8d0ad14bcf6456ce368b830fea886Stephen Hinesnamespace hash { 195460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao 20f7ac0f19a1c8d0ad14bcf6456ce368b830fea886Stephen Hinesenum Type { 215460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao RS, 225460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao JS, 235460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao PJW, 245460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao ELF, 255460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao BKDR, 265460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao SDBM, 275460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao DJB, 285460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao DEK, 295460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao BP, 305460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao FNV, 3122add6ff3426df1a85089fe6a6e1597ee3b6f300Shih-wei Liao AP, 3222add6ff3426df1a85089fe6a6e1597ee3b6f300Shih-wei Liao ES 335460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao}; 345460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao 3522add6ff3426df1a85089fe6a6e1597ee3b6f300Shih-wei Liao/** \class template<uint32_t TYPE> StringHash 365460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao * \brief the template StringHash class, for specification 375460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao */ 3822add6ff3426df1a85089fe6a6e1597ee3b6f300Shih-wei Liaotemplate<uint32_t TYPE> 3922add6ff3426df1a85089fe6a6e1597ee3b6f300Shih-wei Liaostruct StringHash : public std::unary_function<const llvm::StringRef&, uint32_t> 405460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao{ 4122add6ff3426df1a85089fe6a6e1597ee3b6f300Shih-wei Liao uint32_t operator()(const llvm::StringRef& pKey) const 425460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao { 4387f34658dec9097d987d254a990ea7f311bfc95fStephen Hines assert(false && "Undefined StringHash function.\n"); 4487f34658dec9097d987d254a990ea7f311bfc95fStephen Hines return 0; 455460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao } 465460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao}; 475460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao 485460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao/** \class StringHash<RSHash> 495460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao * \brief RS StringHash funciton 505460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao */ 515460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liaotemplate<> 5222add6ff3426df1a85089fe6a6e1597ee3b6f300Shih-wei Liaostruct StringHash<RS> : public std::unary_function<const llvm::StringRef&, uint32_t> 535460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao{ 5422add6ff3426df1a85089fe6a6e1597ee3b6f300Shih-wei Liao uint32_t operator()(const llvm::StringRef& pKey) const 555460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao { 565460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao const unsigned int b = 378551; 5722add6ff3426df1a85089fe6a6e1597ee3b6f300Shih-wei Liao uint32_t a = 63689; 5822add6ff3426df1a85089fe6a6e1597ee3b6f300Shih-wei Liao uint32_t hash_val = 0; 595460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao 605460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao for(unsigned int i = 0; i < pKey.size(); ++i) { 615460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao hash_val = hash_val * a + pKey[i]; 625460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao a = a * b; 635460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao } 645460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao return hash_val; 655460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao } 665460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao}; 675460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao 685460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao/** \class StringHash<JSHash> 695460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao * \brief JS hash funciton 705460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao */ 715460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liaotemplate<> 7222add6ff3426df1a85089fe6a6e1597ee3b6f300Shih-wei Liaostruct StringHash<JS> : public std::unary_function<const llvm::StringRef&, uint32_t> 735460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao{ 7422add6ff3426df1a85089fe6a6e1597ee3b6f300Shih-wei Liao uint32_t operator()(const llvm::StringRef& pKey) const 755460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao { 7622add6ff3426df1a85089fe6a6e1597ee3b6f300Shih-wei Liao uint32_t hash_val = 1315423911; 775460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao 785460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao for(unsigned int i = 0; i < pKey.size(); ++i) { 795460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao hash_val ^= ((hash_val << 5) + pKey[i] + (hash_val >> 2)); 80551ae4ebd3e9d137ea668fb83ae4a55b8cfba451Stephen Hines } 815460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao return hash_val; 825460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao } 835460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao}; 845460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao 855460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao/** \class StringHash<PJW> 865460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao * \brief P.J. Weinberger hash function 875460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao */ 885460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liaotemplate<> 8922add6ff3426df1a85089fe6a6e1597ee3b6f300Shih-wei Liaostruct StringHash<PJW> : public std::unary_function<const llvm::StringRef&, uint32_t> 905460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao{ 9122add6ff3426df1a85089fe6a6e1597ee3b6f300Shih-wei Liao uint32_t operator()(const llvm::StringRef& pKey) const 925460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao { 935460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao const unsigned int BitsInUnsignedInt = (unsigned int)(sizeof(unsigned int) * 8); 945460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao const unsigned int ThreeQuarters = (unsigned int)((BitsInUnsignedInt * 3) / 4); 955460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao const unsigned int OneEighth = (unsigned int)(BitsInUnsignedInt / 8); 965460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao const unsigned int HighBits = (unsigned int)(0xFFFFFFFF) << (BitsInUnsignedInt - OneEighth); 9722add6ff3426df1a85089fe6a6e1597ee3b6f300Shih-wei Liao uint32_t hash_val = 0; 9822add6ff3426df1a85089fe6a6e1597ee3b6f300Shih-wei Liao uint32_t test = 0; 995460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao 1005460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao for(unsigned int i = 0; i < pKey.size(); ++i) { 1015460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao hash_val = (hash_val << OneEighth) + pKey[i]; 1025460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao 1035460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao if((test = hash_val & HighBits) != 0) { 1045460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao hash_val = (( hash_val ^ (test >> ThreeQuarters)) & (~HighBits)); 1055460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao } 1065460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao } 1075460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao return hash_val; 1085460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao } 1095460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao}; 1105460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao 1115460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao/** \class StringHash<ELF> 1125460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao * \brief ELF hash function. 1135460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao */ 1145460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liaotemplate<> 11522add6ff3426df1a85089fe6a6e1597ee3b6f300Shih-wei Liaostruct StringHash<ELF> : public std::unary_function<const llvm::StringRef&, uint32_t> 1165460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao{ 11722add6ff3426df1a85089fe6a6e1597ee3b6f300Shih-wei Liao uint32_t operator()(const llvm::StringRef& pKey) const 1185460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao { 11922add6ff3426df1a85089fe6a6e1597ee3b6f300Shih-wei Liao uint32_t hash_val = 0; 12022add6ff3426df1a85089fe6a6e1597ee3b6f300Shih-wei Liao uint32_t x = 0; 1215460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao 1225460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao for (unsigned int i = 0; i < pKey.size(); ++i) { 1235460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao hash_val = (hash_val << 4) + pKey[i]; 1245460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao if((x = hash_val & 0xF0000000L) != 0) 125551ae4ebd3e9d137ea668fb83ae4a55b8cfba451Stephen Hines hash_val ^= (x >> 24); 1265460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao hash_val &= ~x; 1275460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao } 1285460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao return hash_val; 1295460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao } 1305460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao}; 1315460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao 1325460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao/** \class StringHash<BKDR> 1335460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao * \brief BKDR hash function 1345460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao */ 1355460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liaotemplate<> 13622add6ff3426df1a85089fe6a6e1597ee3b6f300Shih-wei Liaostruct StringHash<BKDR> : public std::unary_function<const llvm::StringRef&, uint32_t> 1375460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao{ 13822add6ff3426df1a85089fe6a6e1597ee3b6f300Shih-wei Liao uint32_t operator()(const llvm::StringRef& pKey) const 1395460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao { 14022add6ff3426df1a85089fe6a6e1597ee3b6f300Shih-wei Liao const uint32_t seed = 131; 14122add6ff3426df1a85089fe6a6e1597ee3b6f300Shih-wei Liao uint32_t hash_val = 0; 142551ae4ebd3e9d137ea668fb83ae4a55b8cfba451Stephen Hines 14322add6ff3426df1a85089fe6a6e1597ee3b6f300Shih-wei Liao for(uint32_t i = 0; i < pKey.size(); ++i) 1445460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao hash_val = (hash_val * seed) + pKey[i]; 1455460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao return hash_val; 1465460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao } 1475460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao}; 1485460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao 1495460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao 1505460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao/** \class StringHash<SDBM> 1515460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao * \brief SDBM hash function 1525460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao * 0.049s in 100000 test 1535460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao */ 1545460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liaotemplate<> 15522add6ff3426df1a85089fe6a6e1597ee3b6f300Shih-wei Liaostruct StringHash<SDBM> : public std::unary_function<const llvm::StringRef&, uint32_t> 1565460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao{ 15722add6ff3426df1a85089fe6a6e1597ee3b6f300Shih-wei Liao uint32_t operator()(const llvm::StringRef& pKey) const 1585460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao { 15922add6ff3426df1a85089fe6a6e1597ee3b6f300Shih-wei Liao uint32_t hash_val = 0; 1605460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao 16122add6ff3426df1a85089fe6a6e1597ee3b6f300Shih-wei Liao for(uint32_t i = 0; i < pKey.size(); ++i) 1625460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao hash_val = pKey[i] + (hash_val << 6) + (hash_val << 16) - hash_val; 1635460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao return hash_val; 1645460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao } 1655460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao}; 1665460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao 1675460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao/** \class StringHash<DJB> 1685460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao * \brief DJB hash function 1695460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao * 0.057s in 100000 test 1705460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao */ 1715460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liaotemplate<> 17222add6ff3426df1a85089fe6a6e1597ee3b6f300Shih-wei Liaostruct StringHash<DJB> : public std::unary_function<const llvm::StringRef&, uint32_t> 1735460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao{ 17422add6ff3426df1a85089fe6a6e1597ee3b6f300Shih-wei Liao uint32_t operator()(const llvm::StringRef& pKey) const 1755460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao { 17622add6ff3426df1a85089fe6a6e1597ee3b6f300Shih-wei Liao uint32_t hash_val = 5381; 1775460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao 17822add6ff3426df1a85089fe6a6e1597ee3b6f300Shih-wei Liao for(uint32_t i = 0; i < pKey.size(); ++i) 1795460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao hash_val = ((hash_val << 5) + hash_val) + pKey[i]; 1805460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao 1815460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao return hash_val; 1825460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao } 1835460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao}; 1845460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao 1855460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao/** \class StringHash<DEK> 1865460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao * \brief DEK hash function 1875460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao * 0.60s 1885460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao */ 1895460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liaotemplate<> 19022add6ff3426df1a85089fe6a6e1597ee3b6f300Shih-wei Liaostruct StringHash<DEK> : public std::unary_function<const llvm::StringRef&, uint32_t> 1915460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao{ 19222add6ff3426df1a85089fe6a6e1597ee3b6f300Shih-wei Liao uint32_t operator()(const llvm::StringRef& pKey) const 1935460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao { 19422add6ff3426df1a85089fe6a6e1597ee3b6f300Shih-wei Liao uint32_t hash_val = pKey.size(); 1955460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao 19622add6ff3426df1a85089fe6a6e1597ee3b6f300Shih-wei Liao for(uint32_t i = 0; i < pKey.size(); ++i) 1975460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao hash_val = ((hash_val << 5) ^ (hash_val >> 27)) ^ pKey[i]; 1985460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao 1995460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao return hash_val; 2005460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao } 2015460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao}; 2025460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao 2035460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao/** \class StringHash<BP> 2045460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao * \brief BP hash function 2055460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao * 0.057s 2065460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao */ 2075460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liaotemplate<> 20822add6ff3426df1a85089fe6a6e1597ee3b6f300Shih-wei Liaostruct StringHash<BP> : public std::unary_function<const llvm::StringRef&, uint32_t> 2095460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao{ 21022add6ff3426df1a85089fe6a6e1597ee3b6f300Shih-wei Liao uint32_t operator()(const llvm::StringRef& pKey) const 2115460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao { 21222add6ff3426df1a85089fe6a6e1597ee3b6f300Shih-wei Liao uint32_t hash_val = 0; 21322add6ff3426df1a85089fe6a6e1597ee3b6f300Shih-wei Liao for(uint32_t i = 0; i < pKey.size(); ++i) 2145460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao hash_val = hash_val << 7 ^ pKey[i]; 2155460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao 2165460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao return hash_val; 2175460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao } 2185460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao}; 2195460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao 2205460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao/** \class StringHash<FNV> 2215460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao * \brief FNV hash function 2225460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao * 0.058s 2235460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao */ 2245460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liaotemplate<> 22522add6ff3426df1a85089fe6a6e1597ee3b6f300Shih-wei Liaostruct StringHash<FNV> : public std::unary_function<const llvm::StringRef&, uint32_t> 2265460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao{ 22722add6ff3426df1a85089fe6a6e1597ee3b6f300Shih-wei Liao uint32_t operator()(const llvm::StringRef& pKey) const 2285460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao { 22922add6ff3426df1a85089fe6a6e1597ee3b6f300Shih-wei Liao const uint32_t fnv_prime = 0x811C9DC5; 23022add6ff3426df1a85089fe6a6e1597ee3b6f300Shih-wei Liao uint32_t hash_val = 0; 23122add6ff3426df1a85089fe6a6e1597ee3b6f300Shih-wei Liao for(uint32_t i = 0; i < pKey.size(); ++i) { 2325460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao hash_val *= fnv_prime; 2335460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao hash_val ^= pKey[i]; 2345460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao } 2355460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao 2365460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao return hash_val; 2375460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao } 2385460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao}; 2395460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao 2405460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao/** \class StringHash<AP> 2415460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao * \brief AP hash function 2425460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao * 0.060s 2435460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao */ 2445460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liaotemplate<> 24522add6ff3426df1a85089fe6a6e1597ee3b6f300Shih-wei Liaostruct StringHash<AP> : public std::unary_function<const llvm::StringRef&, uint32_t> 2465460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao{ 24722add6ff3426df1a85089fe6a6e1597ee3b6f300Shih-wei Liao uint32_t operator()(const llvm::StringRef& pKey) const 2485460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao { 2495460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao unsigned int hash_val = 0xAAAAAAAA; 250551ae4ebd3e9d137ea668fb83ae4a55b8cfba451Stephen Hines 251551ae4ebd3e9d137ea668fb83ae4a55b8cfba451Stephen Hines for(uint32_t i = 0; i < pKey.size(); ++i) { 2525460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao hash_val ^= ((i & 1) == 0)? 2535460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao ((hash_val << 7) ^ pKey[i] * (hash_val >> 3)): 2545460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao (~((hash_val << 11) + (pKey[i] ^ (hash_val >> 5)))); 2555460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao } 256551ae4ebd3e9d137ea668fb83ae4a55b8cfba451Stephen Hines 2575460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao return hash_val; 2585460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao } 2595460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao}; 2605460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao 26122add6ff3426df1a85089fe6a6e1597ee3b6f300Shih-wei Liao/** \class StringHash<ES> 26222add6ff3426df1a85089fe6a6e1597ee3b6f300Shih-wei Liao * \brief This is a revision of Edward Sayers' string characteristic function. 26322add6ff3426df1a85089fe6a6e1597ee3b6f300Shih-wei Liao * 26422add6ff3426df1a85089fe6a6e1597ee3b6f300Shih-wei Liao * 31-28 27 26 25 - 0 26522add6ff3426df1a85089fe6a6e1597ee3b6f300Shih-wei Liao * +----+---+---+------------+ 26622add6ff3426df1a85089fe6a6e1597ee3b6f300Shih-wei Liao * | . | N | - | a/A ~ z/Z | 26722add6ff3426df1a85089fe6a6e1597ee3b6f300Shih-wei Liao * +----+---+---+------------+ 26822add6ff3426df1a85089fe6a6e1597ee3b6f300Shih-wei Liao * 26922add6ff3426df1a85089fe6a6e1597ee3b6f300Shih-wei Liao * . (bit 31~28) - The number of '.' characters 27022add6ff3426df1a85089fe6a6e1597ee3b6f300Shih-wei Liao * N (bit 27) - Are there any numbers in the string 27122add6ff3426df1a85089fe6a6e1597ee3b6f300Shih-wei Liao * - (bit 26) - Does the string have '-' character 27222add6ff3426df1a85089fe6a6e1597ee3b6f300Shih-wei Liao * bit 25~0 - Bit 25 is set only if the string contains a 'a' or 'A', and 27322add6ff3426df1a85089fe6a6e1597ee3b6f300Shih-wei Liao * Bit 24 is set only if ... 'b' or 'B', ... 27422add6ff3426df1a85089fe6a6e1597ee3b6f300Shih-wei Liao */ 27522add6ff3426df1a85089fe6a6e1597ee3b6f300Shih-wei Liaotemplate<> 27622add6ff3426df1a85089fe6a6e1597ee3b6f300Shih-wei Liaostruct StringHash<ES> : public std::unary_function<const llvm::StringRef&, uint32_t> 27722add6ff3426df1a85089fe6a6e1597ee3b6f300Shih-wei Liao{ 27822add6ff3426df1a85089fe6a6e1597ee3b6f300Shih-wei Liao uint32_t operator()(const llvm::StringRef& pString) const 27922add6ff3426df1a85089fe6a6e1597ee3b6f300Shih-wei Liao { 28022add6ff3426df1a85089fe6a6e1597ee3b6f300Shih-wei Liao uint32_t result = 0x0; 28122add6ff3426df1a85089fe6a6e1597ee3b6f300Shih-wei Liao unsigned int dot = 0; 28222add6ff3426df1a85089fe6a6e1597ee3b6f300Shih-wei Liao std::string::size_type idx; 28322add6ff3426df1a85089fe6a6e1597ee3b6f300Shih-wei Liao for (idx = 0; idx < pString.size(); ++idx) { 28422add6ff3426df1a85089fe6a6e1597ee3b6f300Shih-wei Liao int cur_char = pString[idx]; 28522add6ff3426df1a85089fe6a6e1597ee3b6f300Shih-wei Liao 28622add6ff3426df1a85089fe6a6e1597ee3b6f300Shih-wei Liao if ('.' == cur_char) { 28722add6ff3426df1a85089fe6a6e1597ee3b6f300Shih-wei Liao ++dot; 28822add6ff3426df1a85089fe6a6e1597ee3b6f300Shih-wei Liao continue; 28922add6ff3426df1a85089fe6a6e1597ee3b6f300Shih-wei Liao } 29022add6ff3426df1a85089fe6a6e1597ee3b6f300Shih-wei Liao 29122add6ff3426df1a85089fe6a6e1597ee3b6f300Shih-wei Liao if (isdigit(cur_char)) { 29222add6ff3426df1a85089fe6a6e1597ee3b6f300Shih-wei Liao result |= (1 << 27); 29322add6ff3426df1a85089fe6a6e1597ee3b6f300Shih-wei Liao continue; 29422add6ff3426df1a85089fe6a6e1597ee3b6f300Shih-wei Liao } 29522add6ff3426df1a85089fe6a6e1597ee3b6f300Shih-wei Liao 29622add6ff3426df1a85089fe6a6e1597ee3b6f300Shih-wei Liao if ('_' == cur_char) { 29722add6ff3426df1a85089fe6a6e1597ee3b6f300Shih-wei Liao result |= (1 << 26); 29822add6ff3426df1a85089fe6a6e1597ee3b6f300Shih-wei Liao continue; 29922add6ff3426df1a85089fe6a6e1597ee3b6f300Shih-wei Liao } 30022add6ff3426df1a85089fe6a6e1597ee3b6f300Shih-wei Liao 30122add6ff3426df1a85089fe6a6e1597ee3b6f300Shih-wei Liao if (isupper(cur_char)) { 30222add6ff3426df1a85089fe6a6e1597ee3b6f300Shih-wei Liao result |= (1 << (cur_char - 'A')); 30322add6ff3426df1a85089fe6a6e1597ee3b6f300Shih-wei Liao continue; 30422add6ff3426df1a85089fe6a6e1597ee3b6f300Shih-wei Liao } 30522add6ff3426df1a85089fe6a6e1597ee3b6f300Shih-wei Liao 30622add6ff3426df1a85089fe6a6e1597ee3b6f300Shih-wei Liao if (islower(cur_char)) { 30722add6ff3426df1a85089fe6a6e1597ee3b6f300Shih-wei Liao result |= (1 << (cur_char - 'a')); 30822add6ff3426df1a85089fe6a6e1597ee3b6f300Shih-wei Liao continue; 30922add6ff3426df1a85089fe6a6e1597ee3b6f300Shih-wei Liao } 31022add6ff3426df1a85089fe6a6e1597ee3b6f300Shih-wei Liao } 31122add6ff3426df1a85089fe6a6e1597ee3b6f300Shih-wei Liao result |= (dot << 28); 31222add6ff3426df1a85089fe6a6e1597ee3b6f300Shih-wei Liao return result; 31322add6ff3426df1a85089fe6a6e1597ee3b6f300Shih-wei Liao } 31422add6ff3426df1a85089fe6a6e1597ee3b6f300Shih-wei Liao 31522add6ff3426df1a85089fe6a6e1597ee3b6f300Shih-wei Liao 31622add6ff3426df1a85089fe6a6e1597ee3b6f300Shih-wei Liao /** \func may_include 31722add6ff3426df1a85089fe6a6e1597ee3b6f300Shih-wei Liao * \brief is it possible that pRule is a sub-string of pInString 31822add6ff3426df1a85089fe6a6e1597ee3b6f300Shih-wei Liao */ 31922add6ff3426df1a85089fe6a6e1597ee3b6f300Shih-wei Liao static bool may_include(uint32_t pRule, uint32_t pInString) 32022add6ff3426df1a85089fe6a6e1597ee3b6f300Shih-wei Liao { 32122add6ff3426df1a85089fe6a6e1597ee3b6f300Shih-wei Liao uint32_t in_c = pInString << 4; 32222add6ff3426df1a85089fe6a6e1597ee3b6f300Shih-wei Liao uint32_t r_c = pRule << 4; 32322add6ff3426df1a85089fe6a6e1597ee3b6f300Shih-wei Liao 32422add6ff3426df1a85089fe6a6e1597ee3b6f300Shih-wei Liao uint32_t res = (in_c ^ r_c) & r_c; 32522add6ff3426df1a85089fe6a6e1597ee3b6f300Shih-wei Liao if (0 != res) 32622add6ff3426df1a85089fe6a6e1597ee3b6f300Shih-wei Liao return false; 32722add6ff3426df1a85089fe6a6e1597ee3b6f300Shih-wei Liao 32822add6ff3426df1a85089fe6a6e1597ee3b6f300Shih-wei Liao uint32_t in_dot = pInString >> 28; 32922add6ff3426df1a85089fe6a6e1597ee3b6f300Shih-wei Liao uint32_t r_dot = pRule >> 28; 33022add6ff3426df1a85089fe6a6e1597ee3b6f300Shih-wei Liao if (r_dot > in_dot) 33122add6ff3426df1a85089fe6a6e1597ee3b6f300Shih-wei Liao return false; 33222add6ff3426df1a85089fe6a6e1597ee3b6f300Shih-wei Liao 33322add6ff3426df1a85089fe6a6e1597ee3b6f300Shih-wei Liao return true; 33422add6ff3426df1a85089fe6a6e1597ee3b6f300Shih-wei Liao } 33522add6ff3426df1a85089fe6a6e1597ee3b6f300Shih-wei Liao}; 33622add6ff3426df1a85089fe6a6e1597ee3b6f300Shih-wei Liao 33722add6ff3426df1a85089fe6a6e1597ee3b6f300Shih-wei Liao/** \class template<uint32_t TYPE> StringCompare 3385460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao * \brief the template StringCompare class, for specification 3395460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao */ 3405460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liaotemplate<typename STRING_TYPE> 3415460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liaostruct StringCompare : public std::binary_function<const STRING_TYPE&, const STRING_TYPE&, bool> 3425460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao{ 3435460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao bool operator()(const STRING_TYPE& X, const STRING_TYPE& Y) const 3445460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao { return X == Y; } 3455460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao}; 3465460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao 3475460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liaotemplate<> 3485460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liaostruct StringCompare<const char*> : public std::binary_function<const char*, const char*, bool> 3495460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao{ 3505460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao bool operator()(const char* X, const char* Y) const 3515460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao { return (0 == std::strcmp(X, Y)); } 3525460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao}; 3535460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao 3545460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liaotemplate<> 3555460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liaostruct StringCompare<char*> : public std::binary_function<const char*, const char*, bool> 3565460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao{ 3575460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao bool operator()(const char* X, const char* Y) const 3585460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao { return (0 == std::strcmp(X, Y)); } 3595460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao}; 3605460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao 361f7ac0f19a1c8d0ad14bcf6456ce368b830fea886Stephen Hines} // namespace of hash 3625460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao} // namespace of mcld 3635460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao 3645460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao#endif 365affc150dc44fab1911775a49636d0ce85333b634Zonr Chang 366