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