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_OBJECTS_STRING_TABLE_H_
6 #define V8_OBJECTS_STRING_TABLE_H_
7 
8 #include "src/common/assert-scope.h"
9 #include "src/objects/string.h"
10 #include "src/roots/roots.h"
11 
12 // Has to be the last include (doesn't have include guards):
13 #include "src/objects/object-macros.h"
14 
15 namespace v8 {
16 namespace internal {
17 
18 // A generic key for lookups into the string table, which allows heteromorphic
19 // lookup and on-demand creation of new strings.
20 class StringTableKey {
21  public:
22   virtual ~StringTableKey() = default;
23   inline StringTableKey(uint32_t raw_hash_field, int length);
24 
raw_hash_field()25   uint32_t raw_hash_field() const {
26     DCHECK_NE(0, raw_hash_field_);
27     return raw_hash_field_;
28   }
29 
30   inline uint32_t hash() const;
length()31   int length() const { return length_; }
32 
33  protected:
34   inline void set_raw_hash_field(uint32_t raw_hash_field);
35 
36  private:
37   uint32_t raw_hash_field_ = 0;
38   int length_;
39 };
40 
41 class SeqOneByteString;
42 
43 // StringTable, for internalizing strings. The Lookup methods are designed to be
44 // thread-safe, in combination with GC safepoints.
45 //
46 // The string table layout is defined by its Data implementation class, see
47 // StringTable::Data for details.
48 class V8_EXPORT_PRIVATE StringTable {
49  public:
empty_element()50   static constexpr Smi empty_element() { return Smi::FromInt(0); }
deleted_element()51   static constexpr Smi deleted_element() { return Smi::FromInt(1); }
52 
53   explicit StringTable(Isolate* isolate);
54   ~StringTable();
55 
56   int Capacity() const;
57   int NumberOfElements() const;
58 
59   // Find string in the string table. If it is not there yet, it is
60   // added. The return value is the string found.
61   Handle<String> LookupString(Isolate* isolate, Handle<String> key);
62 
63   // Find string in the string table, using the given key. If the string is not
64   // there yet, it is created (by the key) and added. The return value is the
65   // string found.
66   template <typename StringTableKey, typename IsolateT>
67   Handle<String> LookupKey(IsolateT* isolate, StringTableKey* key);
68 
69   // {raw_string} must be a tagged String pointer.
70   // Returns a tagged pointer: either a Smi if the string is an array index, an
71   // internalized string, or a Smi sentinel.
72   static Address TryStringToIndexOrLookupExisting(Isolate* isolate,
73                                                   Address raw_string);
74 
75   void Print(PtrComprCageBase cage_base) const;
76   size_t GetCurrentMemoryUsage() const;
77 
78   // The following methods must be called either while holding the write lock,
79   // or while in a Heap safepoint.
80   void IterateElements(RootVisitor* visitor);
81   void DropOldData();
82   void NotifyElementsRemoved(int count);
83 
84  private:
85   class Data;
86 
87   Data* EnsureCapacity(PtrComprCageBase cage_base, int additional_elements);
88 
89   std::atomic<Data*> data_;
90   // Write mutex is mutable so that readers of concurrently mutated values (e.g.
91   // NumberOfElements) are allowed to lock it while staying const.
92   mutable base::Mutex write_mutex_;
93 #ifdef DEBUG
94   Isolate* isolate_;
95 #endif
96 };
97 
98 }  // namespace internal
99 }  // namespace v8
100 
101 #include "src/objects/object-macros-undef.h"
102 
103 #endif  // V8_OBJECTS_STRING_TABLE_H_
104