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
10namespace v8 {
11namespace internal {
12
13class ConsString;
14class String;
15
16template <typename T>
17class Vector;
18
19class 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
72class 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.
85struct 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.
93struct StringEquals {
94 bool operator()(const char* name1, const char* name2) const {
95 return strcmp(name1, name2) == 0;
96 }
97};
98
99} // namespace internal
100} // namespace v8
101
102#endif // V8_STRING_HASHER_H_
103