LCOV - code coverage report
Current view: top level - src - string-hasher-inl.h (source / functions) Hit Total Coverage
Test: app.info Lines: 52 54 96.3 %
Date: 2019-01-20 Functions: 7 8 87.5 %

          Line data    Source code
       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   157270332 :       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  2641307250 :   running_hash += c;
      32  2641307250 :   running_hash += (running_hash << 10);
      33  2641307250 :   running_hash ^= (running_hash >> 6);
      34             :   return running_hash;
      35             : }
      36             : 
      37             : uint32_t StringHasher::GetHashCore(uint32_t running_hash) {
      38   204302636 :   running_hash += (running_hash << 3);
      39   204302636 :   running_hash ^= (running_hash >> 11);
      40   204302636 :   running_hash += (running_hash << 15);
      41   204302636 :   int32_t hash = static_cast<int32_t>(running_hash & String::kHashBitMask);
      42   204302636 :   int32_t mask = (hash - 1) >> 31;
      43   204302636 :   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   167174410 :   const Char* end = &chars[length];
      52  2388441686 :   while (chars != end) {
      53  2221267276 :     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   296140938 :   raw_running_hash_ = AddCharacterCore(raw_running_hash_, c);
      62             : }
      63             : 
      64    57205725 : bool StringHasher::UpdateIndex(uint16_t c) {
      65             :   DCHECK(is_array_index_);
      66    57205725 :   if (!TryAddIndexChar(&array_index_, c)) {
      67    53872724 :     is_array_index_ = false;
      68    53872724 :     return false;
      69             :   }
      70     3333001 :   is_array_index_ = array_index_ != 0 || length_ == 1;
      71     3333001 :   return is_array_index_;
      72             : }
      73             : 
      74             : template <typename Char>
      75    71352045 : inline void StringHasher::AddCharacters(const Char* chars, int length) {
      76             :   DCHECK(sizeof(Char) == 1 || sizeof(Char) == 2);
      77             :   int i = 0;
      78    71352045 :   if (is_array_index_) {
      79     3320110 :     for (; i < length; i++) {
      80    42669557 :       AddCharacter(chars[i]);
      81    42669557 :       if (!UpdateIndex(chars[i])) {
      82    39349440 :         i++;
      83    39349440 :         break;
      84             :       }
      85             :     }
      86             :   }
      87    71352038 :   raw_running_hash_ =
      88    71352038 :       ComputeRunningHash(raw_running_hash_, &chars[i], length - i);
      89    71352038 : }
      90             : 
      91             : template <typename schar>
      92   100705280 : 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   100705280 :   if (IsInRange(length, 1, String::kMaxArrayIndexSize)) {
     104   152394732 :     if (IsDecimalDigit(chars[0]) && (length == 1 || chars[0] != '0')) {
     105     4924359 :       uint32_t index = chars[0] - '0';
     106             :       int i = 1;
     107    12729124 :       do {
     108    17611899 :         if (i == length) {
     109     4882168 :           uint32_t result = MakeArrayIndexHash(index, length);
     110             :           DCHECK_EQ(expected, result);
     111             :           return result;
     112             :         }
     113    12729124 :       } while (TryAddIndexChar(&index, chars[i++]));
     114             :     }
     115    24507914 :   } else if (length > String::kMaxHashCalcLength) {
     116             :     // String hash of a large string is simply the length.
     117             :     uint32_t result =
     118         133 :         (length << String::kHashShift) | String::kIsNotArrayIndexMask;
     119             :     DCHECK_EQ(result, expected);
     120         133 :     return result;
     121             :   }
     122             : 
     123             :   // Non-array-index hash.
     124             :   uint32_t hash =
     125    95822372 :       ComputeRunningHash(static_cast<uint32_t>(seed), chars, length);
     126             : 
     127             :   uint32_t result =
     128    95822372 :       (GetHashCore(hash) << String::kHashShift) | String::kIsNotArrayIndexMask;
     129             :   DCHECK_EQ(result, expected);
     130    95822372 :   return result;
     131             : }
     132             : 
     133             : IteratingStringHasher::IteratingStringHasher(int len, uint64_t seed)
     134             :     : StringHasher(len, seed) {}
     135             : 
     136    71369271 : uint32_t IteratingStringHasher::Hash(String string, uint64_t seed) {
     137             :   IteratingStringHasher hasher(string->length(), seed);
     138             :   // Nothing to do.
     139    71369271 :   if (hasher.has_trivial_hash()) return hasher.GetHashField();
     140    71302659 :   ConsString cons_string = String::VisitFlat(&hasher, string);
     141    71303079 :   if (cons_string.is_null()) return hasher.GetHashField();
     142      124582 :   hasher.VisitConsString(cons_string);
     143      124582 :   return hasher.GetHashField();
     144             : }
     145             : 
     146             : void IteratingStringHasher::VisitOneByteString(const uint8_t* chars,
     147             :                                                int length) {
     148    69255057 :   AddCharacters(chars, length);
     149             : }
     150             : 
     151             : void IteratingStringHasher::VisitTwoByteString(const uint16_t* chars,
     152             :                                                int length) {
     153     2051710 :   AddCharacters(chars, length);
     154             : }
     155             : 
     156           0 : std::size_t SeededStringHasher::operator()(const char* name) const {
     157             :   return StringHasher::HashSequentialString(
     158           0 :       name, static_cast<int>(strlen(name)), hashseed_);
     159             : }
     160             : 
     161             : }  // namespace internal
     162             : }  // namespace v8
     163             : 
     164             : #endif  // V8_STRING_HASHER_INL_H_

Generated by: LCOV version 1.10