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 V8_INLINE static uint32_t ComputeRunningHash(uint32_t running_hash, 45 const uc16* chars, int length); 46 V8_INLINE static uint32_t ComputeRunningHashOneByte(uint32_t running_hash, 47 const char* chars, 48 int length); 49 50 protected: 51 // Returns the value to store in the hash field of a string with 52 // the given length and contents. 53 uint32_t GetHashField(); 54 // Returns true if the hash of this string can be computed without 55 // looking at the contents. 56 inline bool has_trivial_hash(); 57 // Adds a block of characters to the hash. 58 template <typename Char> 59 inline void AddCharacters(const Char* chars, int len); 60 61 private: 62 // Add a character to the hash. 63 inline void AddCharacter(uint16_t c); 64 // Update index. Returns true if string is still an index. 65 inline bool UpdateIndex(uint16_t c); 66 67 int length_; 68 uint32_t raw_running_hash_; 69 uint32_t array_index_; 70 bool is_array_index_; 71 bool is_first_char_; 72 DISALLOW_COPY_AND_ASSIGN(StringHasher); 73 }; 74 75 class IteratingStringHasher : public StringHasher { 76 public: 77 static inline uint32_t Hash(String* string, uint64_t seed); 78 inline void VisitOneByteString(const uint8_t* chars, int length); 79 inline void VisitTwoByteString(const uint16_t* chars, int length); 80 81 private: 82 inline IteratingStringHasher(int len, uint64_t seed); 83 void VisitConsString(ConsString* cons_string); 84 DISALLOW_COPY_AND_ASSIGN(IteratingStringHasher); 85 }; 86 87 // Useful for std containers that require something ()'able. 88 struct SeededStringHasher { SeededStringHasherSeededStringHasher89 explicit SeededStringHasher(uint64_t hashseed) : hashseed_(hashseed) {} 90 inline std::size_t operator()(const char* name) const; 91 92 uint64_t hashseed_; 93 }; 94 95 // Useful for std containers that require something ()'able. 96 struct StringEquals { operatorStringEquals97 bool operator()(const char* name1, const char* name2) const { 98 return strcmp(name1, name2) == 0; 99 } 100 }; 101 102 } // namespace internal 103 } // namespace v8 104 105 #endif // V8_STRING_HASHER_H_ 106