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_H_
       6             : #define V8_STRING_HASHER_H_
       7             : 
       8             : #include "src/globals.h"
       9             : 
      10             : namespace v8 {
      11             : namespace internal {
      12             : 
      13             : class ConsString;
      14             : class String;
      15             : 
      16             : template <typename T>
      17             : class Vector;
      18             : 
      19             : class V8_EXPORT_PRIVATE StringHasher {
      20             :  public:
      21             :   explicit inline StringHasher(int length, uint64_t seed);
      22             : 
      23             :   template <typename schar>
      24             :   static inline uint32_t HashSequentialString(const schar* chars, int length,
      25             :                                               uint64_t seed);
      26             : 
      27             :   // Reads all the data, even for long strings and computes the utf16 length.
      28             :   static uint32_t ComputeUtf8Hash(Vector<const char> chars, uint64_t seed,
      29             :                                   int* utf16_length_out);
      30             : 
      31             :   // Calculated hash value for a string consisting of 1 to
      32             :   // String::kMaxArrayIndexSize digits with no leading zeros (except "0").
      33             :   // value is represented decimal value.
      34             :   static uint32_t MakeArrayIndexHash(uint32_t value, int length);
      35             : 
      36             :   // No string is allowed to have a hash of zero.  That value is reserved
      37             :   // for internal properties.  If the hash calculation yields zero then we
      38             :   // use 27 instead.
      39             :   static const int kZeroHash = 27;
      40             : 
      41             :   // Reusable parts of the hashing algorithm.
      42             :   V8_INLINE static uint32_t AddCharacterCore(uint32_t running_hash, uint16_t c);
      43             :   V8_INLINE static uint32_t GetHashCore(uint32_t running_hash);
      44             :   template <typename Char>
      45             :   V8_INLINE static uint32_t ComputeRunningHash(uint32_t running_hash,
      46             :                                                const Char* chars, int length);
      47             : 
      48             :  protected:
      49             :   // Returns the value to store in the hash field of a string with
      50             :   // the given length and contents.
      51             :   uint32_t GetHashField();
      52             :   // Returns true if the hash of this string can be computed without
      53             :   // looking at the contents.
      54             :   inline bool has_trivial_hash();
      55             :   // Adds a block of characters to the hash.
      56             :   template <typename Char>
      57             :   inline void AddCharacters(const Char* chars, int len);
      58             : 
      59             :  private:
      60             :   // Add a character to the hash.
      61             :   inline void AddCharacter(uint16_t c);
      62             :   // Update index. Returns true if string is still an index.
      63             :   inline bool UpdateIndex(uint16_t c);
      64             : 
      65             :   int length_;
      66             :   uint32_t raw_running_hash_;
      67             :   uint32_t array_index_;
      68             :   bool is_array_index_;
      69             :   DISALLOW_COPY_AND_ASSIGN(StringHasher);
      70             : };
      71             : 
      72             : class IteratingStringHasher : public StringHasher {
      73             :  public:
      74             :   static inline uint32_t Hash(String string, uint64_t seed);
      75             :   inline void VisitOneByteString(const uint8_t* chars, int length);
      76             :   inline void VisitTwoByteString(const uint16_t* chars, int length);
      77             : 
      78             :  private:
      79             :   inline IteratingStringHasher(int len, uint64_t seed);
      80             :   void VisitConsString(ConsString cons_string);
      81             :   DISALLOW_COPY_AND_ASSIGN(IteratingStringHasher);
      82             : };
      83             : 
      84             : // Useful for std containers that require something ()'able.
      85             : struct SeededStringHasher {
      86             :   explicit SeededStringHasher(uint64_t hashseed) : hashseed_(hashseed) {}
      87             :   inline std::size_t operator()(const char* name) const;
      88             : 
      89             :   uint64_t hashseed_;
      90             : };
      91             : 
      92             : // Useful for std containers that require something ()'able.
      93             : struct StringEquals {
      94             :   bool operator()(const char* name1, const char* name2) const {
      95           0 :     return strcmp(name1, name2) == 0;
      96             :   }
      97             : };
      98             : 
      99             : }  // namespace internal
     100             : }  // namespace v8
     101             : 
     102             : #endif  // V8_STRING_HASHER_H_