← Back to branch summary

~alinuxninja/nginx-edge/trunk

« back to all changes in this revision

Viewing changes to debian/modules/ngx_pagespeed/psol/include/pagespeed/kernel/base/string_hash.h

  • Committer: Vivian
  • Date: 2015-12-04 18:20:11 UTC
  • Revision ID: git-v1:a36f2bc32e884f7473b3a47040e5411306144d7d
* Do not extract psol.tar.gz

Show diffs side-by-side

added added

removed removed

Lines of Context:
debian/modules/ngx_pagespeed/psol/include/pagespeed/kernel/base/string_hash.h
1
 
/*
2
 
 * Copyright 2010 Google Inc.
3
 
 *
4
 
 * Licensed under the Apache License, Version 2.0 (the "License");
5
 
 * you may not use this file except in compliance with the License.
6
 
 * You may obtain a copy of the License at
7
 
 *
8
 
 *      http://www.apache.org/licenses/LICENSE-2.0
9
 
 *
10
 
 * Unless required by applicable law or agreed to in writing, software
11
 
 * distributed under the License is distributed on an "AS IS" BASIS,
12
 
 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
13
 
 * See the License for the specific language governing permissions and
14
 
 * limitations under the License.
15
 
 */
16
 
 
17
 
// Author: jmarantz@google.com (Joshua Marantz)
18
 
 
19
 
#ifndef PAGESPEED_KERNEL_BASE_STRING_HASH_H_
20
 
#define PAGESPEED_KERNEL_BASE_STRING_HASH_H_
21
 
 
22
 
#include <cstddef>
23
 
 
24
 
#include "pagespeed/kernel/base/string.h"
25
 
#include "pagespeed/kernel/base/string_util.h"
26
 
 
27
 
namespace net_instaweb {
28
 
 
29
 
// A hash function for strings that can be used both in a case-sensitive
30
 
// and case-insensitive way
31
 
template<class CharTransform, typename IntType>
32
 
inline IntType HashString(const char* s, size_t len) {
33
 
  // This implemention is based on code in
34
 
  // third_party/chromium/src/base/hash_tables.h.
35
 
  IntType result = 0;
36
 
  for (const char* end = s + len; s != end; ++s) {
37
 
    result = (result * 131) + CharTransform::Normalize(*s);
38
 
  }
39
 
  return result;
40
 
}
41
 
 
42
 
// Combine two hash values in a reasonable way.  Here to avoid
43
 
// excessive mysticism in the remainder of the code.
44
 
inline size_t JoinHash(size_t a, size_t b) {
45
 
  return (a + 56) * 137 + b * 151;  // Uses different prime multipliers.
46
 
}
47
 
 
48
 
// A helper for case-sensitive hashing
49
 
struct CasePreserve {
50
 
  // We want to use unsigned characters for the return value of Normalize
51
 
  // here and in CaseFold::Normalize.  This is so that we get the same
52
 
  // hash-value arithmetic regardless of whether the c++ compiler treats
53
 
  // chars as signed or unsigned by default.  We want to get the same
54
 
  // hash-values independent of machine so that we get consistent domain
55
 
  // sharding and therefore better caching behavior in a multi-server setup
56
 
  // that contains heterogeneous machines.
57
 
  static unsigned char Normalize(char c) {
58
 
    return c;
59
 
  }
60
 
 
61
 
  static bool Compare(const StringPiece& a, const StringPiece& b) {
62
 
    return a < b;
63
 
  }
64
 
};
65
 
 
66
 
// A helper for case-insensitive hashing, which folds to lowercase
67
 
struct CaseFold {
68
 
  static unsigned char Normalize(char c) {
69
 
    return LowerChar(c);
70
 
  }
71
 
 
72
 
  static bool Compare(const StringPiece& a, const StringPiece& b) {
73
 
    return StringCaseCompare(a, b) < 0;
74
 
  }
75
 
};
76
 
 
77
 
// Functors for constructing case-insensitive and case-sensitive hash-tables.
78
 
struct CasePreserveStringHash {
79
 
  size_t operator()(const GoogleString& str) const {
80
 
    return HashString<CasePreserve, size_t>(str.data(), str.size());
81
 
  }
82
 
};
83
 
 
84
 
struct CaseFoldStringHash {
85
 
  size_t operator()(const GoogleString& str) const {
86
 
    return HashString<CaseFold, size_t>(str.data(), str.size());
87
 
  }
88
 
};
89
 
 
90
 
struct CaseFoldStringEqual {
91
 
  bool operator()(const GoogleString& a, const GoogleString& b) const {
92
 
    return MemCaseEqual(a.data(), a.size(), b.data(), b.size());
93
 
  }
94
 
};
95
 
 
96
 
struct CasePreserveStringPieceHash {
97
 
  size_t operator()(StringPiece str) const {
98
 
    return HashString<CasePreserve, size_t>(str.data(), str.size());
99
 
  }
100
 
};
101
 
 
102
 
struct CaseFoldStringPieceHash {
103
 
  size_t operator()(StringPiece str) const {
104
 
    return HashString<CaseFold, size_t>(str.data(), str.size());
105
 
  }
106
 
};
107
 
struct CaseFoldStringPieceEqual {
108
 
  bool operator()(StringPiece a, StringPiece b) const {
109
 
    return MemCaseEqual(a.data(), a.size(), b.data(), b.size());
110
 
  }
111
 
};
112
 
 
113
 
}  // namespace net_instaweb
114
 
 
115
 
#endif  // PAGESPEED_KERNEL_BASE_STRING_HASH_H_