V8 API Reference, 7.2.502.16 (for Deno 0.2.4)
string-hasher-inl.h
1 // Copyright 2017 the V8 project authors. All rights reserved.
2 // Use of this source code is governed by a BSD-style license that can be
3 // found in the LICENSE file.
4 
5 #ifndef V8_STRING_HASHER_INL_H_
6 #define V8_STRING_HASHER_INL_H_
7 
8 #include "src/string-hasher.h"
9 
10 #include "src/char-predicates-inl.h"
11 #include "src/objects.h"
12 #include "src/objects/string-inl.h"
13 #include "src/utils-inl.h"
14 
15 namespace v8 {
16 namespace internal {
17 
18 StringHasher::StringHasher(int length, uint64_t seed)
19  : length_(length),
20  raw_running_hash_(static_cast<uint32_t>(seed)),
21  array_index_(0),
22  is_array_index_(IsInRange(length, 1, String::kMaxArrayIndexSize)) {
23  DCHECK(FLAG_randomize_hashes || raw_running_hash_ == 0);
24 }
25 
26 bool StringHasher::has_trivial_hash() {
27  return length_ > String::kMaxHashCalcLength;
28 }
29 
30 uint32_t StringHasher::AddCharacterCore(uint32_t running_hash, uint16_t c) {
31  running_hash += c;
32  running_hash += (running_hash << 10);
33  running_hash ^= (running_hash >> 6);
34  return running_hash;
35 }
36 
37 uint32_t StringHasher::GetHashCore(uint32_t running_hash) {
38  running_hash += (running_hash << 3);
39  running_hash ^= (running_hash >> 11);
40  running_hash += (running_hash << 15);
41  int32_t hash = static_cast<int32_t>(running_hash & String::kHashBitMask);
42  int32_t mask = (hash - 1) >> 31;
43  return running_hash | (kZeroHash & mask);
44 }
45 
46 template <typename Char>
47 uint32_t StringHasher::ComputeRunningHash(uint32_t running_hash,
48  const Char* chars, int length) {
49  DCHECK_LE(0, length);
50  DCHECK_IMPLIES(0 < length, chars != nullptr);
51  const Char* end = &chars[length];
52  while (chars != end) {
53  running_hash = AddCharacterCore(running_hash, *chars++);
54  }
55  return running_hash;
56 }
57 
58 void StringHasher::AddCharacter(uint16_t c) {
59  // Use the Jenkins one-at-a-time hash function to update the hash
60  // for the given character.
61  raw_running_hash_ = AddCharacterCore(raw_running_hash_, c);
62 }
63 
64 bool StringHasher::UpdateIndex(uint16_t c) {
65  DCHECK(is_array_index_);
66  if (!TryAddIndexChar(&array_index_, c)) {
67  is_array_index_ = false;
68  return false;
69  }
70  is_array_index_ = array_index_ != 0 || length_ == 1;
71  return is_array_index_;
72 }
73 
74 template <typename Char>
75 inline void StringHasher::AddCharacters(const Char* chars, int length) {
76  DCHECK(sizeof(Char) == 1 || sizeof(Char) == 2);
77  int i = 0;
78  if (is_array_index_) {
79  for (; i < length; i++) {
80  AddCharacter(chars[i]);
81  if (!UpdateIndex(chars[i])) {
82  i++;
83  break;
84  }
85  }
86  }
87  raw_running_hash_ =
88  ComputeRunningHash(raw_running_hash_, &chars[i], length - i);
89 }
90 
91 template <typename schar>
92 uint32_t StringHasher::HashSequentialString(const schar* chars, int length,
93  uint64_t seed) {
94 #ifdef DEBUG
95  StringHasher hasher(length, seed);
96  if (!hasher.has_trivial_hash()) hasher.AddCharacters(chars, length);
97  uint32_t expected = hasher.GetHashField();
98 #endif
99 
100  // Check whether the string is a valid array index. In that case, compute the
101  // array index hash. It'll fall through to compute a regular string hash from
102  // the start if it turns out that the string isn't a valid array index.
103  if (IsInRange(length, 1, String::kMaxArrayIndexSize)) {
104  if (IsDecimalDigit(chars[0]) && (length == 1 || chars[0] != '0')) {
105  uint32_t index = chars[0] - '0';
106  int i = 1;
107  do {
108  if (i == length) {
109  uint32_t result = MakeArrayIndexHash(index, length);
110  DCHECK_EQ(expected, result);
111  return result;
112  }
113  } while (TryAddIndexChar(&index, chars[i++]));
114  }
115  } else if (length > String::kMaxHashCalcLength) {
116  // String hash of a large string is simply the length.
117  uint32_t result =
118  (length << String::kHashShift) | String::kIsNotArrayIndexMask;
119  DCHECK_EQ(result, expected);
120  return result;
121  }
122 
123  // Non-array-index hash.
124  uint32_t hash =
125  ComputeRunningHash(static_cast<uint32_t>(seed), chars, length);
126 
127  uint32_t result =
128  (GetHashCore(hash) << String::kHashShift) | String::kIsNotArrayIndexMask;
129  DCHECK_EQ(result, expected);
130  return result;
131 }
132 
133 IteratingStringHasher::IteratingStringHasher(int len, uint64_t seed)
134  : StringHasher(len, seed) {}
135 
136 uint32_t IteratingStringHasher::Hash(String string, uint64_t seed) {
137  IteratingStringHasher hasher(string->length(), seed);
138  // Nothing to do.
139  if (hasher.has_trivial_hash()) return hasher.GetHashField();
140  ConsString cons_string = String::VisitFlat(&hasher, string);
141  if (cons_string.is_null()) return hasher.GetHashField();
142  hasher.VisitConsString(cons_string);
143  return hasher.GetHashField();
144 }
145 
146 void IteratingStringHasher::VisitOneByteString(const uint8_t* chars,
147  int length) {
148  AddCharacters(chars, length);
149 }
150 
151 void IteratingStringHasher::VisitTwoByteString(const uint16_t* chars,
152  int length) {
153  AddCharacters(chars, length);
154 }
155 
156 std::size_t SeededStringHasher::operator()(const char* name) const {
157  return StringHasher::HashSequentialString(
158  name, static_cast<int>(strlen(name)), hashseed_);
159 }
160 
161 } // namespace internal
162 } // namespace v8
163 
164 #endif // V8_STRING_HASHER_INL_H_
Definition: libplatform.h:13