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//===----------------------------------------------------------------------===// 937b74a387bb3993387029859c2d9d051c41c724eStephen Hines#ifndef MCLD_ADT_STRINGHASH_H_ 1037b74a387bb3993387029859c2d9d051c41c724eStephen Hines#define MCLD_ADT_STRINGHASH_H_ 1137b74a387bb3993387029859c2d9d051c41c724eStephen Hines 125460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao#include <llvm/ADT/StringRef.h> 1322add6ff3426df1a85089fe6a6e1597ee3b6f300Shih-wei Liao#include <llvm/Support/DataTypes.h> 1437b74a387bb3993387029859c2d9d051c41c724eStephen Hines 1587f34658dec9097d987d254a990ea7f311bfc95fStephen Hines#include <cassert> 1637b74a387bb3993387029859c2d9d051c41c724eStephen Hines#include <cctype> 175460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao#include <functional> 185460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao 19f7ac0f19a1c8d0ad14bcf6456ce368b830fea886Stephen Hinesnamespace mcld { 20f7ac0f19a1c8d0ad14bcf6456ce368b830fea886Stephen Hinesnamespace hash { 215460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao 2237b74a387bb3993387029859c2d9d051c41c724eStephen Hinesenum Type { RS, JS, PJW, ELF, BKDR, SDBM, DJB, DEK, BP, FNV, AP, ES }; 235460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao 2422add6ff3426df1a85089fe6a6e1597ee3b6f300Shih-wei Liao/** \class template<uint32_t TYPE> StringHash 255460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao * \brief the template StringHash class, for specification 265460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao */ 2737b74a387bb3993387029859c2d9d051c41c724eStephen Hinestemplate <uint32_t TYPE> 2837b74a387bb3993387029859c2d9d051c41c724eStephen Hinesstruct StringHash 2937b74a387bb3993387029859c2d9d051c41c724eStephen Hines : public std::unary_function<const llvm::StringRef, uint32_t> { 3037b74a387bb3993387029859c2d9d051c41c724eStephen Hines uint32_t operator()(const llvm::StringRef pKey) const { 3187f34658dec9097d987d254a990ea7f311bfc95fStephen Hines assert(false && "Undefined StringHash function.\n"); 3287f34658dec9097d987d254a990ea7f311bfc95fStephen Hines return 0; 335460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao } 345460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao}; 355460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao 365460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao/** \class StringHash<RSHash> 375460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao * \brief RS StringHash funciton 385460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao */ 3937b74a387bb3993387029859c2d9d051c41c724eStephen Hinestemplate <> 4037b74a387bb3993387029859c2d9d051c41c724eStephen Hinesstruct StringHash<RS> 4137b74a387bb3993387029859c2d9d051c41c724eStephen Hines : public std::unary_function<const llvm::StringRef, uint32_t> { 4237b74a387bb3993387029859c2d9d051c41c724eStephen Hines uint32_t operator()(const llvm::StringRef pKey) const { 435460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao const unsigned int b = 378551; 4422add6ff3426df1a85089fe6a6e1597ee3b6f300Shih-wei Liao uint32_t a = 63689; 4522add6ff3426df1a85089fe6a6e1597ee3b6f300Shih-wei Liao uint32_t hash_val = 0; 465460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao 4737b74a387bb3993387029859c2d9d051c41c724eStephen Hines for (unsigned int i = 0; i < pKey.size(); ++i) { 485460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao hash_val = hash_val * a + pKey[i]; 495460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao a = a * b; 505460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao } 515460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao return hash_val; 525460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao } 535460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao}; 545460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao 555460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao/** \class StringHash<JSHash> 565460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao * \brief JS hash funciton 575460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao */ 5837b74a387bb3993387029859c2d9d051c41c724eStephen Hinestemplate <> 5937b74a387bb3993387029859c2d9d051c41c724eStephen Hinesstruct StringHash<JS> 6037b74a387bb3993387029859c2d9d051c41c724eStephen Hines : public std::unary_function<const llvm::StringRef, uint32_t> { 6137b74a387bb3993387029859c2d9d051c41c724eStephen Hines uint32_t operator()(const llvm::StringRef pKey) const { 6222add6ff3426df1a85089fe6a6e1597ee3b6f300Shih-wei Liao uint32_t hash_val = 1315423911; 635460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao 6437b74a387bb3993387029859c2d9d051c41c724eStephen Hines for (unsigned int i = 0; i < pKey.size(); ++i) { 6537b74a387bb3993387029859c2d9d051c41c724eStephen Hines hash_val ^= ((hash_val << 5) + pKey[i] + (hash_val >> 2)); 66551ae4ebd3e9d137ea668fb83ae4a55b8cfba451Stephen Hines } 675460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao return hash_val; 685460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao } 695460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao}; 705460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao 715460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao/** \class StringHash<PJW> 725460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao * \brief P.J. Weinberger hash function 735460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao */ 7437b74a387bb3993387029859c2d9d051c41c724eStephen Hinestemplate <> 7537b74a387bb3993387029859c2d9d051c41c724eStephen Hinesstruct StringHash<PJW> 7637b74a387bb3993387029859c2d9d051c41c724eStephen Hines : public std::unary_function<const llvm::StringRef, uint32_t> { 7737b74a387bb3993387029859c2d9d051c41c724eStephen Hines uint32_t operator()(const llvm::StringRef pKey) const { 7837b74a387bb3993387029859c2d9d051c41c724eStephen Hines const unsigned int BitsInUnsignedInt = 7937b74a387bb3993387029859c2d9d051c41c724eStephen Hines (unsigned int)(sizeof(unsigned int) * 8); 8037b74a387bb3993387029859c2d9d051c41c724eStephen Hines const unsigned int ThreeQuarters = 8137b74a387bb3993387029859c2d9d051c41c724eStephen Hines (unsigned int)((BitsInUnsignedInt * 3) / 4); 8237b74a387bb3993387029859c2d9d051c41c724eStephen Hines const unsigned int OneEighth = (unsigned int)(BitsInUnsignedInt / 8); 8337b74a387bb3993387029859c2d9d051c41c724eStephen Hines const unsigned int HighBits = (unsigned int)(0xFFFFFFFF) 8437b74a387bb3993387029859c2d9d051c41c724eStephen Hines << (BitsInUnsignedInt - OneEighth); 8522add6ff3426df1a85089fe6a6e1597ee3b6f300Shih-wei Liao uint32_t hash_val = 0; 8622add6ff3426df1a85089fe6a6e1597ee3b6f300Shih-wei Liao uint32_t test = 0; 875460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao 8837b74a387bb3993387029859c2d9d051c41c724eStephen Hines for (unsigned int i = 0; i < pKey.size(); ++i) { 895460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao hash_val = (hash_val << OneEighth) + pKey[i]; 905460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao 9137b74a387bb3993387029859c2d9d051c41c724eStephen Hines if ((test = hash_val & HighBits) != 0) { 9237b74a387bb3993387029859c2d9d051c41c724eStephen Hines hash_val = ((hash_val ^ (test >> ThreeQuarters)) & (~HighBits)); 935460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao } 945460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao } 955460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao return hash_val; 965460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao } 975460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao}; 985460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao 995460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao/** \class StringHash<ELF> 1005460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao * \brief ELF hash function. 1015460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao */ 10237b74a387bb3993387029859c2d9d051c41c724eStephen Hinestemplate <> 10337b74a387bb3993387029859c2d9d051c41c724eStephen Hinesstruct StringHash<ELF> 10437b74a387bb3993387029859c2d9d051c41c724eStephen Hines : public std::unary_function<const llvm::StringRef, uint32_t> { 10537b74a387bb3993387029859c2d9d051c41c724eStephen Hines uint32_t operator()(const llvm::StringRef pKey) const { 10622add6ff3426df1a85089fe6a6e1597ee3b6f300Shih-wei Liao uint32_t hash_val = 0; 10722add6ff3426df1a85089fe6a6e1597ee3b6f300Shih-wei Liao uint32_t x = 0; 1085460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao 1095460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao for (unsigned int i = 0; i < pKey.size(); ++i) { 1105460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao hash_val = (hash_val << 4) + pKey[i]; 11137b74a387bb3993387029859c2d9d051c41c724eStephen Hines if ((x = hash_val & 0xF0000000L) != 0) 112551ae4ebd3e9d137ea668fb83ae4a55b8cfba451Stephen Hines hash_val ^= (x >> 24); 1135460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao hash_val &= ~x; 1145460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao } 1155460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao return hash_val; 1165460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao } 1175460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao}; 1185460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao 1195460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao/** \class StringHash<BKDR> 1205460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao * \brief BKDR hash function 1215460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao */ 12237b74a387bb3993387029859c2d9d051c41c724eStephen Hinestemplate <> 12337b74a387bb3993387029859c2d9d051c41c724eStephen Hinesstruct StringHash<BKDR> 12437b74a387bb3993387029859c2d9d051c41c724eStephen Hines : public std::unary_function<const llvm::StringRef, uint32_t> { 12537b74a387bb3993387029859c2d9d051c41c724eStephen Hines uint32_t operator()(const llvm::StringRef pKey) const { 12622add6ff3426df1a85089fe6a6e1597ee3b6f300Shih-wei Liao const uint32_t seed = 131; 12722add6ff3426df1a85089fe6a6e1597ee3b6f300Shih-wei Liao uint32_t hash_val = 0; 128551ae4ebd3e9d137ea668fb83ae4a55b8cfba451Stephen Hines 12937b74a387bb3993387029859c2d9d051c41c724eStephen Hines for (uint32_t i = 0; i < pKey.size(); ++i) 1305460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao hash_val = (hash_val * seed) + pKey[i]; 1315460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao return hash_val; 1325460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao } 1335460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao}; 1345460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao 1355460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao/** \class StringHash<SDBM> 1365460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao * \brief SDBM hash function 1375460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao * 0.049s in 100000 test 1385460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao */ 13937b74a387bb3993387029859c2d9d051c41c724eStephen Hinestemplate <> 14037b74a387bb3993387029859c2d9d051c41c724eStephen Hinesstruct StringHash<SDBM> 14137b74a387bb3993387029859c2d9d051c41c724eStephen Hines : public std::unary_function<const llvm::StringRef, uint32_t> { 14237b74a387bb3993387029859c2d9d051c41c724eStephen Hines uint32_t operator()(const llvm::StringRef pKey) const { 14322add6ff3426df1a85089fe6a6e1597ee3b6f300Shih-wei Liao uint32_t hash_val = 0; 1445460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao 14537b74a387bb3993387029859c2d9d051c41c724eStephen Hines for (uint32_t i = 0; i < pKey.size(); ++i) 1465460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao hash_val = pKey[i] + (hash_val << 6) + (hash_val << 16) - hash_val; 1475460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao return hash_val; 1485460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao } 1495460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao}; 1505460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao 1515460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao/** \class StringHash<DJB> 1525460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao * \brief DJB hash function 1535460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao * 0.057s in 100000 test 1545460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao */ 15537b74a387bb3993387029859c2d9d051c41c724eStephen Hinestemplate <> 15637b74a387bb3993387029859c2d9d051c41c724eStephen Hinesstruct StringHash<DJB> 15737b74a387bb3993387029859c2d9d051c41c724eStephen Hines : public std::unary_function<const llvm::StringRef, uint32_t> { 15837b74a387bb3993387029859c2d9d051c41c724eStephen Hines uint32_t operator()(const llvm::StringRef pKey) const { 15922add6ff3426df1a85089fe6a6e1597ee3b6f300Shih-wei Liao uint32_t hash_val = 5381; 1605460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao 16137b74a387bb3993387029859c2d9d051c41c724eStephen Hines for (uint32_t i = 0; i < pKey.size(); ++i) 1625460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao hash_val = ((hash_val << 5) + hash_val) + pKey[i]; 1635460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao 1645460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao return hash_val; 1655460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao } 1665460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao}; 1675460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao 1685460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao/** \class StringHash<DEK> 1695460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao * \brief DEK hash function 1705460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao * 0.60s 1715460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao */ 17237b74a387bb3993387029859c2d9d051c41c724eStephen Hinestemplate <> 17337b74a387bb3993387029859c2d9d051c41c724eStephen Hinesstruct StringHash<DEK> 17437b74a387bb3993387029859c2d9d051c41c724eStephen Hines : public std::unary_function<const llvm::StringRef, uint32_t> { 17537b74a387bb3993387029859c2d9d051c41c724eStephen Hines uint32_t operator()(const llvm::StringRef pKey) const { 17622add6ff3426df1a85089fe6a6e1597ee3b6f300Shih-wei Liao uint32_t hash_val = pKey.size(); 1775460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao 17837b74a387bb3993387029859c2d9d051c41c724eStephen Hines for (uint32_t i = 0; i < pKey.size(); ++i) 1795460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao hash_val = ((hash_val << 5) ^ (hash_val >> 27)) ^ 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<BP> 1865460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao * \brief BP hash function 1875460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao * 0.057s 1885460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao */ 18937b74a387bb3993387029859c2d9d051c41c724eStephen Hinestemplate <> 19037b74a387bb3993387029859c2d9d051c41c724eStephen Hinesstruct StringHash<BP> 19137b74a387bb3993387029859c2d9d051c41c724eStephen Hines : public std::unary_function<const llvm::StringRef, uint32_t> { 19237b74a387bb3993387029859c2d9d051c41c724eStephen Hines uint32_t operator()(const llvm::StringRef pKey) const { 19322add6ff3426df1a85089fe6a6e1597ee3b6f300Shih-wei Liao uint32_t hash_val = 0; 19437b74a387bb3993387029859c2d9d051c41c724eStephen Hines for (uint32_t i = 0; i < pKey.size(); ++i) 1955460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao hash_val = hash_val << 7 ^ pKey[i]; 1965460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao 1975460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao return hash_val; 1985460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao } 1995460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao}; 2005460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao 2015460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao/** \class StringHash<FNV> 2025460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao * \brief FNV hash function 2035460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao * 0.058s 2045460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao */ 20537b74a387bb3993387029859c2d9d051c41c724eStephen Hinestemplate <> 20637b74a387bb3993387029859c2d9d051c41c724eStephen Hinesstruct StringHash<FNV> 20737b74a387bb3993387029859c2d9d051c41c724eStephen Hines : public std::unary_function<const llvm::StringRef, uint32_t> { 20837b74a387bb3993387029859c2d9d051c41c724eStephen Hines uint32_t operator()(const llvm::StringRef pKey) const { 20922add6ff3426df1a85089fe6a6e1597ee3b6f300Shih-wei Liao const uint32_t fnv_prime = 0x811C9DC5; 21022add6ff3426df1a85089fe6a6e1597ee3b6f300Shih-wei Liao uint32_t hash_val = 0; 21137b74a387bb3993387029859c2d9d051c41c724eStephen Hines for (uint32_t i = 0; i < pKey.size(); ++i) { 2125460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao hash_val *= fnv_prime; 2135460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao hash_val ^= pKey[i]; 2145460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao } 2155460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao 2165460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao return hash_val; 2175460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao } 2185460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao}; 2195460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao 2205460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao/** \class StringHash<AP> 2215460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao * \brief AP hash function 2225460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao * 0.060s 2235460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao */ 22437b74a387bb3993387029859c2d9d051c41c724eStephen Hinestemplate <> 22537b74a387bb3993387029859c2d9d051c41c724eStephen Hinesstruct StringHash<AP> 22637b74a387bb3993387029859c2d9d051c41c724eStephen Hines : public std::unary_function<const llvm::StringRef, uint32_t> { 22737b74a387bb3993387029859c2d9d051c41c724eStephen Hines uint32_t operator()(const llvm::StringRef pKey) const { 2285460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao unsigned int hash_val = 0xAAAAAAAA; 229551ae4ebd3e9d137ea668fb83ae4a55b8cfba451Stephen Hines 23037b74a387bb3993387029859c2d9d051c41c724eStephen Hines for (uint32_t i = 0; i < pKey.size(); ++i) { 23137b74a387bb3993387029859c2d9d051c41c724eStephen Hines hash_val ^= ((i & 1) == 0) 23237b74a387bb3993387029859c2d9d051c41c724eStephen Hines ? ((hash_val << 7) ^ pKey[i] * (hash_val >> 3)) 23337b74a387bb3993387029859c2d9d051c41c724eStephen Hines : (~((hash_val << 11) + (pKey[i] ^ (hash_val >> 5)))); 2345460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao } 235551ae4ebd3e9d137ea668fb83ae4a55b8cfba451Stephen Hines 2365460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao return hash_val; 2375460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao } 2385460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao}; 2395460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao 24022add6ff3426df1a85089fe6a6e1597ee3b6f300Shih-wei Liao/** \class StringHash<ES> 24122add6ff3426df1a85089fe6a6e1597ee3b6f300Shih-wei Liao * \brief This is a revision of Edward Sayers' string characteristic function. 24222add6ff3426df1a85089fe6a6e1597ee3b6f300Shih-wei Liao * 24322add6ff3426df1a85089fe6a6e1597ee3b6f300Shih-wei Liao * 31-28 27 26 25 - 0 24422add6ff3426df1a85089fe6a6e1597ee3b6f300Shih-wei Liao * +----+---+---+------------+ 24522add6ff3426df1a85089fe6a6e1597ee3b6f300Shih-wei Liao * | . | N | - | a/A ~ z/Z | 24622add6ff3426df1a85089fe6a6e1597ee3b6f300Shih-wei Liao * +----+---+---+------------+ 24722add6ff3426df1a85089fe6a6e1597ee3b6f300Shih-wei Liao * 24822add6ff3426df1a85089fe6a6e1597ee3b6f300Shih-wei Liao * . (bit 31~28) - The number of '.' characters 24922add6ff3426df1a85089fe6a6e1597ee3b6f300Shih-wei Liao * N (bit 27) - Are there any numbers in the string 25022add6ff3426df1a85089fe6a6e1597ee3b6f300Shih-wei Liao * - (bit 26) - Does the string have '-' character 25122add6ff3426df1a85089fe6a6e1597ee3b6f300Shih-wei Liao * bit 25~0 - Bit 25 is set only if the string contains a 'a' or 'A', and 25222add6ff3426df1a85089fe6a6e1597ee3b6f300Shih-wei Liao * Bit 24 is set only if ... 'b' or 'B', ... 25322add6ff3426df1a85089fe6a6e1597ee3b6f300Shih-wei Liao */ 25437b74a387bb3993387029859c2d9d051c41c724eStephen Hinestemplate <> 25537b74a387bb3993387029859c2d9d051c41c724eStephen Hinesstruct StringHash<ES> 25637b74a387bb3993387029859c2d9d051c41c724eStephen Hines : public std::unary_function<const llvm::StringRef, uint32_t> { 25737b74a387bb3993387029859c2d9d051c41c724eStephen Hines uint32_t operator()(const llvm::StringRef pString) const { 25822add6ff3426df1a85089fe6a6e1597ee3b6f300Shih-wei Liao uint32_t result = 0x0; 25922add6ff3426df1a85089fe6a6e1597ee3b6f300Shih-wei Liao unsigned int dot = 0; 26022add6ff3426df1a85089fe6a6e1597ee3b6f300Shih-wei Liao std::string::size_type idx; 26122add6ff3426df1a85089fe6a6e1597ee3b6f300Shih-wei Liao for (idx = 0; idx < pString.size(); ++idx) { 26222add6ff3426df1a85089fe6a6e1597ee3b6f300Shih-wei Liao int cur_char = pString[idx]; 26322add6ff3426df1a85089fe6a6e1597ee3b6f300Shih-wei Liao 26422add6ff3426df1a85089fe6a6e1597ee3b6f300Shih-wei Liao if ('.' == cur_char) { 26522add6ff3426df1a85089fe6a6e1597ee3b6f300Shih-wei Liao ++dot; 26622add6ff3426df1a85089fe6a6e1597ee3b6f300Shih-wei Liao continue; 26722add6ff3426df1a85089fe6a6e1597ee3b6f300Shih-wei Liao } 26822add6ff3426df1a85089fe6a6e1597ee3b6f300Shih-wei Liao 26922add6ff3426df1a85089fe6a6e1597ee3b6f300Shih-wei Liao if (isdigit(cur_char)) { 27022add6ff3426df1a85089fe6a6e1597ee3b6f300Shih-wei Liao result |= (1 << 27); 27122add6ff3426df1a85089fe6a6e1597ee3b6f300Shih-wei Liao continue; 27222add6ff3426df1a85089fe6a6e1597ee3b6f300Shih-wei Liao } 27322add6ff3426df1a85089fe6a6e1597ee3b6f300Shih-wei Liao 27422add6ff3426df1a85089fe6a6e1597ee3b6f300Shih-wei Liao if ('_' == cur_char) { 27522add6ff3426df1a85089fe6a6e1597ee3b6f300Shih-wei Liao result |= (1 << 26); 27622add6ff3426df1a85089fe6a6e1597ee3b6f300Shih-wei Liao continue; 27722add6ff3426df1a85089fe6a6e1597ee3b6f300Shih-wei Liao } 27822add6ff3426df1a85089fe6a6e1597ee3b6f300Shih-wei Liao 27922add6ff3426df1a85089fe6a6e1597ee3b6f300Shih-wei Liao if (isupper(cur_char)) { 28022add6ff3426df1a85089fe6a6e1597ee3b6f300Shih-wei Liao result |= (1 << (cur_char - 'A')); 28122add6ff3426df1a85089fe6a6e1597ee3b6f300Shih-wei Liao continue; 28222add6ff3426df1a85089fe6a6e1597ee3b6f300Shih-wei Liao } 28322add6ff3426df1a85089fe6a6e1597ee3b6f300Shih-wei Liao 28422add6ff3426df1a85089fe6a6e1597ee3b6f300Shih-wei Liao if (islower(cur_char)) { 28522add6ff3426df1a85089fe6a6e1597ee3b6f300Shih-wei Liao result |= (1 << (cur_char - 'a')); 28622add6ff3426df1a85089fe6a6e1597ee3b6f300Shih-wei Liao continue; 28722add6ff3426df1a85089fe6a6e1597ee3b6f300Shih-wei Liao } 28822add6ff3426df1a85089fe6a6e1597ee3b6f300Shih-wei Liao } 28922add6ff3426df1a85089fe6a6e1597ee3b6f300Shih-wei Liao result |= (dot << 28); 29022add6ff3426df1a85089fe6a6e1597ee3b6f300Shih-wei Liao return result; 29122add6ff3426df1a85089fe6a6e1597ee3b6f300Shih-wei Liao } 29222add6ff3426df1a85089fe6a6e1597ee3b6f300Shih-wei Liao 29322add6ff3426df1a85089fe6a6e1597ee3b6f300Shih-wei Liao /** \func may_include 29422add6ff3426df1a85089fe6a6e1597ee3b6f300Shih-wei Liao * \brief is it possible that pRule is a sub-string of pInString 29522add6ff3426df1a85089fe6a6e1597ee3b6f300Shih-wei Liao */ 29637b74a387bb3993387029859c2d9d051c41c724eStephen Hines static bool may_include(uint32_t pRule, uint32_t pInString) { 29722add6ff3426df1a85089fe6a6e1597ee3b6f300Shih-wei Liao uint32_t in_c = pInString << 4; 29837b74a387bb3993387029859c2d9d051c41c724eStephen Hines uint32_t r_c = pRule << 4; 29922add6ff3426df1a85089fe6a6e1597ee3b6f300Shih-wei Liao 30022add6ff3426df1a85089fe6a6e1597ee3b6f300Shih-wei Liao uint32_t res = (in_c ^ r_c) & r_c; 30122add6ff3426df1a85089fe6a6e1597ee3b6f300Shih-wei Liao if (0 != res) 30222add6ff3426df1a85089fe6a6e1597ee3b6f300Shih-wei Liao return false; 30322add6ff3426df1a85089fe6a6e1597ee3b6f300Shih-wei Liao 30422add6ff3426df1a85089fe6a6e1597ee3b6f300Shih-wei Liao uint32_t in_dot = pInString >> 28; 30537b74a387bb3993387029859c2d9d051c41c724eStephen Hines uint32_t r_dot = pRule >> 28; 30622add6ff3426df1a85089fe6a6e1597ee3b6f300Shih-wei Liao if (r_dot > in_dot) 30722add6ff3426df1a85089fe6a6e1597ee3b6f300Shih-wei Liao return false; 30822add6ff3426df1a85089fe6a6e1597ee3b6f300Shih-wei Liao 30922add6ff3426df1a85089fe6a6e1597ee3b6f300Shih-wei Liao return true; 31022add6ff3426df1a85089fe6a6e1597ee3b6f300Shih-wei Liao } 31122add6ff3426df1a85089fe6a6e1597ee3b6f300Shih-wei Liao}; 31222add6ff3426df1a85089fe6a6e1597ee3b6f300Shih-wei Liao 31322add6ff3426df1a85089fe6a6e1597ee3b6f300Shih-wei Liao/** \class template<uint32_t TYPE> StringCompare 3145460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao * \brief the template StringCompare class, for specification 3155460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao */ 31637b74a387bb3993387029859c2d9d051c41c724eStephen Hinestemplate <typename STRING_TYPE> 31737b74a387bb3993387029859c2d9d051c41c724eStephen Hinesstruct StringCompare : public std::binary_function<const STRING_TYPE&, 31837b74a387bb3993387029859c2d9d051c41c724eStephen Hines const STRING_TYPE&, 31937b74a387bb3993387029859c2d9d051c41c724eStephen Hines bool> { 32037b74a387bb3993387029859c2d9d051c41c724eStephen Hines bool operator()(const STRING_TYPE& X, const STRING_TYPE& Y) const { 32137b74a387bb3993387029859c2d9d051c41c724eStephen Hines return X == Y; 32237b74a387bb3993387029859c2d9d051c41c724eStephen Hines } 3235460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao}; 3245460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao 32537b74a387bb3993387029859c2d9d051c41c724eStephen Hinestemplate <> 32637b74a387bb3993387029859c2d9d051c41c724eStephen Hinesstruct StringCompare<const char*> 32737b74a387bb3993387029859c2d9d051c41c724eStephen Hines : public std::binary_function<const char*, const char*, bool> { 32837b74a387bb3993387029859c2d9d051c41c724eStephen Hines bool operator()(const char* X, const char* Y) const { 32937b74a387bb3993387029859c2d9d051c41c724eStephen Hines return (std::strcmp(X, Y) == 0); 33037b74a387bb3993387029859c2d9d051c41c724eStephen Hines } 3315460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao}; 3325460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao 33337b74a387bb3993387029859c2d9d051c41c724eStephen Hinestemplate <> 33437b74a387bb3993387029859c2d9d051c41c724eStephen Hinesstruct StringCompare<char*> 33537b74a387bb3993387029859c2d9d051c41c724eStephen Hines : public std::binary_function<const char*, const char*, bool> { 33637b74a387bb3993387029859c2d9d051c41c724eStephen Hines bool operator()(const char* X, const char* Y) const { 33737b74a387bb3993387029859c2d9d051c41c724eStephen Hines return (std::strcmp(X, Y) == 0); 33837b74a387bb3993387029859c2d9d051c41c724eStephen Hines } 3395460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao}; 3405460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao 34137b74a387bb3993387029859c2d9d051c41c724eStephen Hines} // namespace hash 34237b74a387bb3993387029859c2d9d051c41c724eStephen Hines} // namespace mcld 343affc150dc44fab1911775a49636d0ce85333b634Zonr Chang 34437b74a387bb3993387029859c2d9d051c41c724eStephen Hines#endif // MCLD_ADT_STRINGHASH_H_ 345