• Home
  • Line#
  • Scopes#
  • Navigate#
  • Raw
  • Download
1 /*
2  * Copyright (c) 2022 Huawei Device Co., Ltd.
3  * Licensed under the Apache License, Version 2.0 (the "License");
4  * you may not use this file except in compliance with the License.
5  * You may obtain a copy of the License at
6  *
7  *     http://www.apache.org/licenses/LICENSE-2.0
8  *
9  * Unless required by applicable law or agreed to in writing, software
10  * distributed under the License is distributed on an "AS IS" BASIS,
11  * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
12  * See the License for the specific language governing permissions and
13  * limitations under the License.
14  */
15 
16 #ifndef ECMASCRIPT_TAGGED_TREE_H
17 #define ECMASCRIPT_TAGGED_TREE_H
18 
19 #include "ecmascript/global_env.h"
20 #include "ecmascript/interpreter/interpreter.h"
21 #include "ecmascript/js_tagged_value.h"
22 #include "ecmascript/js_handle.h"
23 #include "ecmascript/tagged_array.h"
24 
25 namespace panda::ecmascript {
26 enum TreeColor : uint8_t { BLACK = 0, RED };
27 /**
28  * The tree layout is as follows:
29  * 1.array[0-4] is used to store common information, such as:
30  * +------------------------+-----------------------------+------------------------+------------+------------------+
31  * | the number of elements | the number of hole elements | the number of capacity | root index | compare function |
32  * +------------------------+-----------------------------+------------------------+------------+------------------+
33  * 2.array[5,5+capacity] is used to store node of tree, map and set store nodes in different formats respectively.
34  * */
35 template<typename Derived>
36 class TaggedTree : public TaggedArray {
37 public:
38     static constexpr int MIN_CAPACITY = 7;
39     static constexpr int NUMBER_OF_ELEMENTS_INDEX = 0;
40     static constexpr int NUMBER_OF_HOLE_ENTRIES_INDEX = 1;
41     static constexpr int CAPACITY_INDEX = 2;
42     static constexpr int ROOT_INDEX = 3;
43     static constexpr int COMPARE_FUNCTION_INDEX = 4;
44     static constexpr int ELEMENTS_START_INDEX = 5;
45     static constexpr int MIN_SHRINK_CAPACITY = 15;
46 
47     static JSHandle<Derived> Create(const JSThread *thread, int numberOfElements);
48 
49     static JSHandle<Derived> Insert(JSThread *thread, JSHandle<Derived> &tree, const JSHandle<JSTaggedValue> &key,
50                                     const JSHandle<JSTaggedValue> &value);
51 
52     static JSHandle<Derived> GrowCapacity(const JSThread *thread, JSHandle<Derived> &tree);
53 
ComputeCapacity(int oldCapacity)54     inline static int ComputeCapacity(int oldCapacity)
55     {
56         int capacity = (static_cast<uint32_t>(oldCapacity) << 1) + 1;
57         return (capacity > MIN_CAPACITY) ? capacity : MIN_CAPACITY;
58     }
59 
60     static void Remove(const JSThread *thread, const JSHandle<Derived> &tree, int entry);
61 
NumberOfElements()62     inline uint32_t NumberOfElements() const
63     {
64         return Get(NUMBER_OF_ELEMENTS_INDEX).GetInt();
65     }
66 
NumberOfDeletedElements()67     inline uint32_t NumberOfDeletedElements() const
68     {
69         return Get(NUMBER_OF_HOLE_ENTRIES_INDEX).GetInt();
70     }
71 
Capacity()72     inline int Capacity() const
73     {
74         return Get(CAPACITY_INDEX).GetInt();
75     }
76 
GetKey(int entry)77     inline JSTaggedValue GetKey(int entry) const
78     {
79         if (entry < 0) {
80             return JSTaggedValue::Hole();
81         }
82         int index = EntryToIndex(entry);
83         return GetElement(index);
84     }
85 
GetValue(int entry)86     inline JSTaggedValue GetValue(int entry) const
87     {
88         int index = static_cast<int>(EntryToIndex(entry) + Derived::ENTRY_VALUE_INDEX);
89         return GetElement(index);
90     }
91 
GetColor(int entry)92     inline TreeColor GetColor(int entry) const
93     {
94         if (entry < 0) {
95             return TreeColor::BLACK;
96         }
97         int index = static_cast<int>(EntryToIndex(entry) + Derived::ENTRY_COLOR_INDEX);
98         JSTaggedValue color = GetElement(index);
99         return color.GetInt() == TreeColor::RED ? TreeColor::RED : TreeColor::BLACK;
100     }
101 
SetCapacity(const JSThread * thread,int capacity)102     inline void SetCapacity(const JSThread *thread, int capacity)
103     {
104         Set(thread, CAPACITY_INDEX, JSTaggedValue(capacity));
105     }
106 
IsKey(JSTaggedValue key)107     inline static bool IsKey(JSTaggedValue key)
108     {
109         return !key.IsHole();
110     }
111 
SetNumberOfElements(const JSThread * thread,uint32_t num)112     inline void SetNumberOfElements(const JSThread *thread, uint32_t num)
113     {
114         Set(thread, NUMBER_OF_ELEMENTS_INDEX, JSTaggedValue(num));
115     }
116 
SetNumberOfDeletedElements(const JSThread * thread,int num)117     inline void SetNumberOfDeletedElements(const JSThread *thread, int num)
118     {
119         Set(thread, NUMBER_OF_HOLE_ENTRIES_INDEX, JSTaggedValue(num));
120     }
121 
SetRootEntries(const JSThread * thread,int num)122     inline void SetRootEntries(const JSThread *thread, int num)
123     {
124         Set(thread, ROOT_INDEX, JSTaggedValue(num));
125     }
126 
GetRootEntries()127     inline int GetRootEntries() const
128     {
129         return Get(ROOT_INDEX).GetInt();
130     }
131 
132     static int FindEntry(JSThread *thread, const JSHandle<Derived> &tree, const JSHandle<JSTaggedValue> &key);
133 
EntryCompare(JSThread * thread,const JSHandle<JSTaggedValue> valueX,const JSHandle<JSTaggedValue> valueY,JSHandle<Derived> tree)134     inline static ComparisonResult EntryCompare(JSThread *thread, const JSHandle<JSTaggedValue> valueX,
135                                                 const JSHandle<JSTaggedValue> valueY, JSHandle<Derived> tree)
136     {
137         JSTaggedValue fn = tree->GetCompare();
138         if (fn.IsHole()) {
139             return OrdinayEntryCompare(thread, valueX, valueY);
140         }
141 
142         JSHandle<JSTaggedValue> compareFn(thread, fn);
143         JSHandle<JSTaggedValue> thisArgHandle = thread->GlobalConstants()->GetHandledUndefined();
144         const uint32_t argsLength = 2;
145         JSHandle<JSTaggedValue> undefined = thread->GlobalConstants()->GetHandledUndefined();
146         EcmaRuntimeCallInfo *info =
147             EcmaInterpreter::NewRuntimeCallInfo(thread, compareFn, thisArgHandle, undefined, argsLength);
148         RETURN_VALUE_IF_ABRUPT_COMPLETION(thread, ComparisonResult::UNDEFINED);
149         info->SetCallArg(valueX.GetTaggedValue(), valueY.GetTaggedValue());
150         JSTaggedValue callResult = JSFunction::Call(info);
151         RETURN_VALUE_IF_ABRUPT_COMPLETION(thread, ComparisonResult::UNDEFINED);
152         int compareResult = 0;
153         if (callResult.IsInt()) {
154             compareResult = callResult.GetInt();
155         } else {
156             JSHandle<JSTaggedValue> resultHandle(thread, callResult);
157             JSTaggedNumber v = JSTaggedValue::ToNumber(thread, resultHandle);
158             RETURN_VALUE_IF_ABRUPT_COMPLETION(thread, ComparisonResult::UNDEFINED);
159             double value = v.GetNumber();
160             if (std::isnan(value)) {
161                 THROW_TYPE_ERROR_AND_RETURN(thread, "CompareFn has illegal return value", ComparisonResult::UNDEFINED);
162             }
163             compareResult = static_cast<int>(value);
164         }
165         return compareResult > 0 ? ComparisonResult::GREAT :
166                                 (compareResult < 0 ? ComparisonResult::LESS : ComparisonResult::EQUAL);
167     }
168 
SetKey(const JSThread * thread,uint32_t entry,JSTaggedValue key)169     inline void SetKey(const JSThread *thread, uint32_t entry, JSTaggedValue key)
170     {
171         int index = EntryToIndex(entry);
172         SetElement(thread, index, key);
173     }
174 
SetValue(const JSThread * thread,uint32_t entry,JSTaggedValue value)175     inline void SetValue(const JSThread *thread, uint32_t entry, JSTaggedValue value)
176     {
177         int index = static_cast<int>(EntryToIndex(entry) + Derived::ENTRY_VALUE_INDEX);
178         SetElement(thread, index, value);
179     }
180 
SetCompare(const JSThread * thread,JSTaggedValue fn)181     inline void SetCompare(const JSThread *thread, JSTaggedValue fn)
182     {
183         Set(thread, COMPARE_FUNCTION_INDEX, fn);
184     }
185 
GetCompare()186     inline JSTaggedValue GetCompare() const
187     {
188         return Get(COMPARE_FUNCTION_INDEX);
189     }
190 
GetMinimum(int entry)191     inline int GetMinimum(int entry) const
192     {
193         JSTaggedValue child = GetLeftChild(entry);
194         while (!child.IsHole()) {
195             entry = child.GetInt();
196             child = GetLeftChild(entry);
197         }
198         return entry;
199     }
200 
GetMaximum(int entry)201     inline int GetMaximum(int entry) const
202     {
203         JSTaggedValue child = GetRightChild(entry);
204         while (!child.IsHole()) {
205             entry = child.GetInt();
206             child = GetRightChild(entry);
207         }
208         return entry;
209     }
210 
GetParent(int entry)211     inline int GetParent(int entry) const
212     {
213         int index = static_cast<int>(EntryToIndex(entry) + Derived::ENTRY_PARENT_INDEX);
214         JSTaggedValue parent = GetElement(index);
215         return parent.GetInt();
216     }
217 
GetLeftChild(int parent)218     inline JSTaggedValue GetLeftChild(int parent) const
219     {
220         if (parent < 0) {
221             return JSTaggedValue::Hole();
222         }
223         int index = static_cast<int>(EntryToIndex(parent) + Derived::ENTRY_LEFT_CHILD_INDEX);
224         return Get(index);
225     }
226 
GetRightChild(int parent)227     inline JSTaggedValue GetRightChild(int parent) const
228     {
229         if (parent < 0) {
230             return JSTaggedValue::Hole();
231         }
232         int index = static_cast<int>(EntryToIndex(parent) + Derived::ENTRY_RIGHT_CHILD_INDEX);
233         return Get(index);
234     }
235 
GetLeftChildIndex(int parent)236     inline int GetLeftChildIndex(int parent) const
237     {
238         if (parent < 0) {
239             return -1;
240         }
241         int index = static_cast<int>(EntryToIndex(parent) + Derived::ENTRY_LEFT_CHILD_INDEX);
242         JSTaggedValue child = Get(index);
243         return child.IsHole() ? -1 : child.GetInt();
244     }
245 
GetRightChildIndex(int parent)246     inline int GetRightChildIndex(int parent) const
247     {
248         if (parent < 0) {
249             return -1;
250         }
251         int index = static_cast<int>(EntryToIndex(parent) + Derived::ENTRY_RIGHT_CHILD_INDEX);
252         JSTaggedValue child = Get(index);
253         return child.IsHole() ? -1 : child.GetInt();
254     }
255 
256 protected:
GetElement(int index)257     inline JSTaggedValue GetElement(int index) const
258     {
259         ASSERT(index >= 0 && index < static_cast<int>(GetLength()));
260         return Get(index);
261     }
262 
263     // get root
GetRootKey()264     inline JSTaggedValue GetRootKey() const
265     {
266         return GetKey(GetRootEntries());
267     }
268 
EntryToIndex(uint32_t entry)269     inline int EntryToIndex(uint32_t entry) const
270     {
271         return ELEMENTS_START_INDEX + entry * (Derived::ENTRY_SIZE);
272     }
273 
SetElement(const JSThread * thread,uint32_t index,JSTaggedValue element)274     inline void SetElement(const JSThread *thread, uint32_t index, JSTaggedValue element)
275     {
276         ASSERT(index >= 0 && index < GetLength());
277         Set(thread, index, element);
278     }
279 
SetParent(const JSThread * thread,int entry,JSTaggedValue value)280     inline void SetParent(const JSThread *thread, int entry, JSTaggedValue value)
281     {
282         if (entry < 0) {
283             return;
284         }
285         int index = static_cast<int>(EntryToIndex(entry) + Derived::ENTRY_PARENT_INDEX);
286         SetElement(thread, index, value);
287     }
288 
SetRoot(JSThread * thread,int index,JSTaggedValue key,JSTaggedValue value)289     inline void SetRoot(JSThread *thread, int index, JSTaggedValue key, JSTaggedValue value)
290     {
291         SetKey(thread, 0, key);
292         SetValue(thread, 0, value);
293         SetParent(thread, 0, JSTaggedValue(-1));
294         SetColor(thread, 0, TreeColor::BLACK);
295         SetRootEntries(thread, index);
296     }
297 
SetColor(const JSThread * thread,int entry,TreeColor color)298     inline void SetColor(const JSThread *thread, int entry, TreeColor color)
299     {
300         if (entry >= 0) {
301             int index = static_cast<int>(EntryToIndex(entry) + Derived::ENTRY_COLOR_INDEX);
302             SetElement(thread, index, JSTaggedValue(static_cast<int>(color)));
303         }
304     }
305 
InsertLeftEntry(const JSThread * thread,uint32_t parentIndex,uint32_t entry,JSTaggedValue key,JSTaggedValue value)306     inline void InsertLeftEntry(const JSThread *thread, uint32_t parentIndex, uint32_t entry, JSTaggedValue key,
307                                 JSTaggedValue value)
308     {
309         SetKey(thread, entry, key);
310         SetValue(thread, entry, value);
311         SetColor(thread, entry, TreeColor::RED);
312         SetParent(thread, entry, JSTaggedValue(parentIndex));
313         SetLeftChild(thread, parentIndex, JSTaggedValue(entry));
314     }
315 
InsertRightEntry(const JSThread * thread,uint32_t parentIndex,uint32_t entry,JSTaggedValue key,JSTaggedValue value)316     inline void InsertRightEntry(const JSThread *thread, uint32_t parentIndex, uint32_t entry, JSTaggedValue key,
317                                  JSTaggedValue value)
318     {
319         SetKey(thread, entry, key);
320         SetValue(thread, entry, value);
321         SetColor(thread, entry, TreeColor::RED);
322         SetParent(thread, entry, JSTaggedValue(parentIndex));
323         SetRightChild(thread, parentIndex, JSTaggedValue(entry));
324     }
325 
326     void InsertRebalance(const JSThread *thread, int index);
327     void DeleteRebalance(const JSThread *thread, int index);
328 
IsValidIndex(int entry)329     inline bool IsValidIndex(int entry) const
330     {
331         return entry != GetRootEntries() && !GetKey(entry).IsHole();
332     }
333 
GetLeftBrother(int entry)334     inline int GetLeftBrother(int entry) const
335     {
336         JSTaggedValue child = GetRightChild(GetParent(entry));
337         return child.IsHole() ? -1 : child.GetInt();
338     }
339 
GetRightBrother(int entry)340     inline int GetRightBrother(int entry) const
341     {
342         JSTaggedValue child = GetLeftChild(GetParent(entry));
343         return child.IsHole() ? -1 : child.GetInt();
344     }
345 
IsLeft(int entry)346     inline bool IsLeft(int entry) const
347     {
348         JSTaggedValue child = GetLeftChild(GetParent(entry));
349         return child.IsHole() ? false : (child.GetInt() == entry);
350     }
351 
IsRight(int entry)352     inline bool IsRight(int entry) const
353     {
354         JSTaggedValue child = GetRightChild(GetParent(entry));
355         return child.IsHole() ? false : (child.GetInt() == entry);
356     }
357 
358     int GetPreDecessor(int entry) const;
359     int GetSuccessor(int entry) const;
360 
SetLeftChild(const JSThread * thread,uint32_t entry,JSTaggedValue value)361     inline void SetLeftChild(const JSThread *thread, uint32_t entry, JSTaggedValue value)
362     {
363         int index = static_cast<int>(EntryToIndex(entry) + Derived::ENTRY_LEFT_CHILD_INDEX);
364         SetElement(thread, index, value);
365     }
SetRightChild(const JSThread * thread,uint32_t entry,JSTaggedValue value)366     inline void SetRightChild(const JSThread *thread, uint32_t entry, JSTaggedValue value)
367     {
368         int index = static_cast<int>(EntryToIndex(entry) + Derived::ENTRY_RIGHT_CHILD_INDEX);
369         SetElement(thread, index, value);
370     }
371 
372     void LeftRotate(const JSThread *thread, int index);
373     void RightRotate(const JSThread *thread, int index);
374 
375     static JSHandle<Derived> AdjustTaggedTree(const JSThread *thread, const JSHandle<Derived> &tree, int len);
OrdinayEntryCompare(JSThread * thread,const JSHandle<JSTaggedValue> valueX,const JSHandle<JSTaggedValue> valueY)376     inline static ComparisonResult OrdinayEntryCompare(JSThread *thread, const JSHandle<JSTaggedValue> valueX,
377                                                        const JSHandle<JSTaggedValue> valueY)
378     {
379         if (valueX->IsString() && valueY->IsString()) {
380             auto xHandle = JSHandle<EcmaString>(valueX);
381             auto yHandle = JSHandle<EcmaString>(valueY);
382             int result = EcmaStringAccessor::Compare(thread->GetEcmaVM(), xHandle, yHandle);
383             if (result < 0) {
384                 return ComparisonResult::LESS;
385             }
386             if (result == 0) {
387                 return ComparisonResult::EQUAL;
388             }
389             return ComparisonResult::GREAT;
390         }
391 
392         if (valueX->IsNumber() && valueY->IsNumber()) {
393             return JSTaggedValue::StrictNumberCompare(valueX->GetNumber(), valueY->GetNumber());
394         }
395 
396         if (valueX->IsNumber() && valueY->IsString()) {
397             return ComparisonResult::LESS;
398         }
399         if (valueX->IsString() && valueY->IsNumber()) {
400             return ComparisonResult::GREAT;
401         }
402 
403         JSHandle<JSTaggedValue> xValueHandle(JSTaggedValue::ToString(thread, valueX));
404         JSHandle<JSTaggedValue> yValueHandle(JSTaggedValue::ToString(thread, valueY));
405         ASSERT_NO_ABRUPT_COMPLETION(thread);
406         return JSTaggedValue::Compare(thread, xValueHandle, yValueHandle);
407     }
408 
CopyEntry(const JSThread * thread,int parent,const JSHandle<Derived> & newTree,int index)409     inline void CopyEntry(const JSThread *thread, int parent, const JSHandle<Derived> &newTree, int index)
410     {
411         newTree->SetKey(thread, index, GetKey(parent));
412         newTree->SetColor(thread, index, GetColor(parent));
413     }
414 
CopyData(const JSThread * thread,int dst,int src)415     inline void CopyData(const JSThread *thread, int dst, int src)
416     {
417         SetKey(thread, dst, GetKey(src));
418     }
CopyAllData(const JSThread * thread,int parent,const JSHandle<Derived> & newTree,int index)419     inline void CopyAllData(const JSThread *thread, int parent, const JSHandle<Derived> &newTree, int index)
420     {
421         newTree->SetKey(thread, index, GetKey(parent));
422         newTree->SetValue(thread, index, GetValue(parent));
423         newTree->SetColor(thread, index, GetColor(parent));
424         newTree->SetParent(thread, index, JSTaggedValue(GetParent(parent)));
425         newTree->SetRightChild(thread, index, GetRightChild(parent));
426         newTree->SetLeftChild(thread, index, GetLeftChild(parent));
427     }
428 
RemoveEntry(const JSThread * thread,int index)429     inline void RemoveEntry(const JSThread *thread, int index)
430     {
431         SetKey(thread, index, JSTaggedValue::Hole());
432         SetParent(thread, index, JSTaggedValue::Hole());
433         SetLeftChild(thread, index, JSTaggedValue::Hole());
434         SetRightChild(thread, index, JSTaggedValue::Hole());
435     }
436 
Transform(JSTaggedValue v)437     inline JSTaggedValue Transform(JSTaggedValue v) const
438     {
439         return v.IsHole() ? JSTaggedValue::Undefined() : v;
440     }
441 
442     void Transplant(const JSThread *thread, int dst, int src);
443 
444     static JSTaggedValue GetLowerKey(JSThread *thread, const JSHandle<Derived> &tree,
445                                      const JSHandle<JSTaggedValue> &key);
446     static JSTaggedValue GetHigherKey(JSThread *thread, const JSHandle<Derived> &tree,
447                                       const JSHandle<JSTaggedValue> &key);
448     static JSHandle<TaggedArray> GetSortArray(const JSThread *thread, const JSHandle<Derived> &tree);
449     static JSHandle<Derived> Shrink(const JSThread *thread, const JSHandle<Derived> &tree);
450 };
451 
452 
453 class TaggedTreeMap : public TaggedTree<TaggedTreeMap> {
454 public:
455     using RBTree = TaggedTree<TaggedTreeMap>;
Cast(TaggedObject * obj)456     static TaggedTreeMap *Cast(TaggedObject *obj)
457     {
458         return static_cast<TaggedTreeMap *>(obj);
459     }
460 
461     static JSTaggedValue Create(const JSThread *thread, int numberOfElements = MIN_CAPACITY);
462     static JSTaggedValue Set(JSThread *thread, JSHandle<TaggedTreeMap> &obj,
463                                     const JSHandle<JSTaggedValue> &key, const JSHandle<JSTaggedValue> &value);
Get(JSThread * thread,const JSHandle<TaggedTreeMap> & map,const JSHandle<JSTaggedValue> & key)464     inline static JSTaggedValue Get(JSThread *thread, const JSHandle<TaggedTreeMap> &map,
465                                     const JSHandle<JSTaggedValue> &key)
466     {
467         int index = RBTree::FindEntry(thread, map, key);
468         return index == -1 ? JSTaggedValue::Undefined() : map->GetValue(index);
469     }
470 
471     static JSTaggedValue Delete(JSThread *thread, const JSHandle<TaggedTreeMap> &map, int entry);
472     bool HasValue(const JSThread *thread, JSTaggedValue value) const;
473 
474     static JSTaggedValue GetLowerKey(JSThread *thread, const JSHandle<TaggedTreeMap> &map,
475                                      const JSHandle<JSTaggedValue> &key);
476     static JSTaggedValue GetHigherKey(JSThread *thread, const JSHandle<TaggedTreeMap> &map,
477                                       const JSHandle<JSTaggedValue> &key);
478 
GetFirstKey()479     inline JSTaggedValue GetFirstKey() const
480     {
481         JSTaggedValue key = GetKey(GetMinimum(GetRootEntries()));
482         return Transform(key);
483     }
484 
GetLastKey()485     inline JSTaggedValue GetLastKey() const
486     {
487         JSTaggedValue key = GetKey(GetMaximum(GetRootEntries()));
488         return Transform(key);
489     }
490 
491     static JSTaggedValue SetAll(JSThread *thread, JSHandle<TaggedTreeMap> &dst, const JSHandle<TaggedTreeMap> &src);
492     static JSHandle<TaggedArray> GetArrayFromMap(const JSThread *thread, const JSHandle<TaggedTreeMap> &map);
493     static int FindEntry(JSThread *thread, const JSHandle<TaggedTreeMap> &map, const JSHandle<JSTaggedValue> &key);
494 
495     static const int ENTRY_SIZE = 6;
496     static const int ENTRY_VALUE_INDEX = 1;
497     static const int ENTRY_COLOR_INDEX = 2;
498     static const int ENTRY_PARENT_INDEX = 3;
499     static const int ENTRY_LEFT_CHILD_INDEX = 4;
500     static const int ENTRY_RIGHT_CHILD_INDEX = 5;
DECL_DUMP()501     DECL_DUMP()
502 
503     inline void CopyEntry(const JSThread *thread, int parent, const JSHandle<TaggedTreeMap> &newMap, int index)
504     {
505         RBTree::CopyEntry(thread, parent, newMap, index);
506         newMap->SetValue(thread, index, GetValue(parent));
507     }
CopyData(const JSThread * thread,int dst,int src)508     inline void CopyData(const JSThread *thread, int dst, int src)
509     {
510         RBTree::CopyData(thread, dst, src);
511         SetValue(thread, dst, GetValue(src));
512     }
513 
RemoveEntry(const JSThread * thread,int index)514     inline void RemoveEntry(const JSThread *thread, int index)
515     {
516         RBTree::RemoveEntry(thread, index);
517         SetValue(thread, index, JSTaggedValue::Hole());
518     }
519 };
520 
521 class TaggedTreeSet : public TaggedTree<TaggedTreeSet> {
522 public:
523     using RBTree = TaggedTree<TaggedTreeSet>;
Cast(TaggedObject * obj)524     static TaggedTreeSet *Cast(TaggedObject *obj)
525     {
526         return static_cast<TaggedTreeSet *>(obj);
527     }
528 
529     static JSTaggedValue Create(const JSThread *thread, int numberOfElements = MIN_CAPACITY);
530     static JSTaggedValue Add(JSThread *thread, JSHandle<TaggedTreeSet> &obj, const JSHandle<JSTaggedValue> &value);
531     static JSTaggedValue Delete(JSThread *thread, const JSHandle<TaggedTreeSet> &set, int entry);
532 
533     static JSTaggedValue GetLowerKey(JSThread *thread, const JSHandle<TaggedTreeSet> &set,
534                                      const JSHandle<JSTaggedValue> &key);
535     static JSTaggedValue GetHigherKey(JSThread *thread, const JSHandle<TaggedTreeSet> &set,
536                                       const JSHandle<JSTaggedValue> &key);
537 
GetFirstKey()538     inline JSTaggedValue GetFirstKey() const
539     {
540         JSTaggedValue key = GetKey(GetMinimum(GetRootEntries()));
541         return Transform(key);
542     }
543 
GetLastKey()544     inline JSTaggedValue GetLastKey() const
545     {
546         JSTaggedValue key = GetKey(GetMaximum(GetRootEntries()));
547         return Transform(key);
548     }
549 
550     static JSHandle<TaggedArray> GetArrayFromSet(const JSThread *thread, const JSHandle<TaggedTreeSet> &set);
551     static int FindEntry(JSThread *thread, const JSHandle<TaggedTreeSet> &set, const JSHandle<JSTaggedValue> &key);
552 
553     static const int ENTRY_SIZE = 5;
554     static const int ENTRY_VALUE_INDEX = 0;
555     static const int ENTRY_COLOR_INDEX = 1;
556     static const int ENTRY_PARENT_INDEX = 2;
557     static const int ENTRY_LEFT_CHILD_INDEX = 3;
558     static const int ENTRY_RIGHT_CHILD_INDEX = 4;
559 
DECL_DUMP()560     DECL_DUMP()
561 
562     inline void CopyEntry(const JSThread *thread, int parent, const JSHandle<TaggedTreeSet> &newMap, int index)
563     {
564         RBTree::CopyEntry(thread, parent, newMap, index);
565         newMap->SetValue(thread, index, GetValue(parent));
566     }
567 
CopyData(const JSThread * thread,int dst,int src)568     inline void CopyData(const JSThread *thread, int dst, int src)
569     {
570         RBTree::CopyData(thread, dst, src);
571         SetValue(thread, dst, GetValue(src));
572     }
573 
RemoveEntry(const JSThread * thread,int index)574     inline void RemoveEntry(const JSThread *thread, int index)
575     {
576         RBTree::RemoveEntry(thread, index);
577         SetValue(thread, index, JSTaggedValue::Hole());
578     }
579 };
580 }  // namespace panda::ecmascript
581 #endif  // ECMASCRIPT_TAGGED_TREE_H
582