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.IsBoolean()) { 154 if (callResult.IsTrue()) { 155 compareResult = -1; 156 } else { 157 info = EcmaInterpreter::NewRuntimeCallInfo(thread, compareFn, thisArgHandle, undefined, argsLength); 158 info->SetCallArg(valueY.GetTaggedValue(), valueX.GetTaggedValue()); 159 callResult = JSFunction::Call(info); 160 RETURN_VALUE_IF_ABRUPT_COMPLETION(thread, ComparisonResult::UNDEFINED); 161 compareResult = callResult.IsTrue() ? 1 : 0; 162 } 163 } else if (callResult.IsInt()) { 164 compareResult = callResult.GetInt(); 165 } else { 166 JSHandle<JSTaggedValue> resultHandle(thread, callResult); 167 JSTaggedNumber v = JSTaggedValue::ToNumber(thread, resultHandle); 168 RETURN_VALUE_IF_ABRUPT_COMPLETION(thread, ComparisonResult::UNDEFINED); 169 double value = v.GetNumber(); 170 if (std::isnan(value)) { 171 THROW_TYPE_ERROR_AND_RETURN(thread, "CompareFn has illegal return value", 172 ComparisonResult::UNDEFINED); 173 } 174 compareResult = static_cast<int>(value); 175 } 176 return compareResult > 0 ? ComparisonResult::GREAT : 177 (compareResult < 0 ? ComparisonResult::LESS : ComparisonResult::EQUAL); 178 } 179 SetKey(const JSThread * thread,uint32_t entry,JSTaggedValue key)180 inline void SetKey(const JSThread *thread, uint32_t entry, JSTaggedValue key) 181 { 182 int index = EntryToIndex(entry); 183 SetElement(thread, index, key); 184 } 185 SetValue(const JSThread * thread,uint32_t entry,JSTaggedValue value)186 inline void SetValue(const JSThread *thread, uint32_t entry, JSTaggedValue value) 187 { 188 int index = static_cast<int>(EntryToIndex(entry) + Derived::ENTRY_VALUE_INDEX); 189 SetElement(thread, index, value); 190 } 191 SetCompare(const JSThread * thread,JSTaggedValue fn)192 inline void SetCompare(const JSThread *thread, JSTaggedValue fn) 193 { 194 Set(thread, COMPARE_FUNCTION_INDEX, fn); 195 } 196 GetCompare()197 inline JSTaggedValue GetCompare() const 198 { 199 return Get(COMPARE_FUNCTION_INDEX); 200 } 201 GetMinimum(int entry)202 inline int GetMinimum(int entry) const 203 { 204 JSTaggedValue child = GetLeftChild(entry); 205 while (!child.IsHole()) { 206 entry = child.GetInt(); 207 child = GetLeftChild(entry); 208 } 209 return entry; 210 } 211 GetMaximum(int entry)212 inline int GetMaximum(int entry) const 213 { 214 JSTaggedValue child = GetRightChild(entry); 215 while (!child.IsHole()) { 216 entry = child.GetInt(); 217 child = GetRightChild(entry); 218 } 219 return entry; 220 } 221 GetParent(int entry)222 inline int GetParent(int entry) const 223 { 224 int index = static_cast<int>(EntryToIndex(entry) + Derived::ENTRY_PARENT_INDEX); 225 JSTaggedValue parent = GetElement(index); 226 return parent.GetInt(); 227 } 228 GetLeftChild(int parent)229 inline JSTaggedValue GetLeftChild(int parent) const 230 { 231 if (parent < 0) { 232 return JSTaggedValue::Hole(); 233 } 234 int index = static_cast<int>(EntryToIndex(parent) + Derived::ENTRY_LEFT_CHILD_INDEX); 235 return Get(index); 236 } 237 GetRightChild(int parent)238 inline JSTaggedValue GetRightChild(int parent) const 239 { 240 if (parent < 0) { 241 return JSTaggedValue::Hole(); 242 } 243 int index = static_cast<int>(EntryToIndex(parent) + Derived::ENTRY_RIGHT_CHILD_INDEX); 244 return Get(index); 245 } 246 GetLeftChildIndex(int parent)247 inline int GetLeftChildIndex(int parent) const 248 { 249 if (parent < 0) { 250 return -1; 251 } 252 int index = static_cast<int>(EntryToIndex(parent) + Derived::ENTRY_LEFT_CHILD_INDEX); 253 JSTaggedValue child = Get(index); 254 return child.IsHole() ? -1 : child.GetInt(); 255 } 256 GetRightChildIndex(int parent)257 inline int GetRightChildIndex(int parent) const 258 { 259 if (parent < 0) { 260 return -1; 261 } 262 int index = static_cast<int>(EntryToIndex(parent) + Derived::ENTRY_RIGHT_CHILD_INDEX); 263 JSTaggedValue child = Get(index); 264 return child.IsHole() ? -1 : child.GetInt(); 265 } 266 267 protected: GetElement(int index)268 inline JSTaggedValue GetElement(int index) const 269 { 270 ASSERT(index >= 0 && index < static_cast<int>(GetLength())); 271 return Get(index); 272 } 273 274 // get root GetRootKey()275 inline JSTaggedValue GetRootKey() const 276 { 277 return GetKey(GetRootEntries()); 278 } 279 EntryToIndex(uint32_t entry)280 inline int EntryToIndex(uint32_t entry) const 281 { 282 return ELEMENTS_START_INDEX + entry * (Derived::ENTRY_SIZE); 283 } 284 SetElement(const JSThread * thread,uint32_t index,JSTaggedValue element)285 inline void SetElement(const JSThread *thread, uint32_t index, JSTaggedValue element) 286 { 287 ASSERT(index >= 0 && index < GetLength()); 288 Set(thread, index, element); 289 } 290 SetParent(const JSThread * thread,int entry,JSTaggedValue value)291 inline void SetParent(const JSThread *thread, int entry, JSTaggedValue value) 292 { 293 if (entry < 0) { 294 return; 295 } 296 int index = static_cast<int>(EntryToIndex(entry) + Derived::ENTRY_PARENT_INDEX); 297 SetElement(thread, index, value); 298 } 299 SetRoot(JSThread * thread,int index,JSTaggedValue key,JSTaggedValue value)300 inline void SetRoot(JSThread *thread, int index, JSTaggedValue key, JSTaggedValue value) 301 { 302 SetKey(thread, 0, key); 303 SetValue(thread, 0, value); 304 SetParent(thread, 0, JSTaggedValue(-1)); 305 SetColor(thread, 0, TreeColor::BLACK); 306 SetRootEntries(thread, index); 307 } 308 SetColor(const JSThread * thread,int entry,TreeColor color)309 inline void SetColor(const JSThread *thread, int entry, TreeColor color) 310 { 311 if (entry >= 0) { 312 int index = static_cast<int>(EntryToIndex(entry) + Derived::ENTRY_COLOR_INDEX); 313 SetElement(thread, index, JSTaggedValue(static_cast<int>(color))); 314 } 315 } 316 InsertLeftEntry(const JSThread * thread,uint32_t parentIndex,uint32_t entry,JSTaggedValue key,JSTaggedValue value)317 inline void InsertLeftEntry(const JSThread *thread, uint32_t parentIndex, uint32_t entry, JSTaggedValue key, 318 JSTaggedValue value) 319 { 320 SetKey(thread, entry, key); 321 SetValue(thread, entry, value); 322 SetColor(thread, entry, TreeColor::RED); 323 SetParent(thread, entry, JSTaggedValue(parentIndex)); 324 SetLeftChild(thread, parentIndex, JSTaggedValue(entry)); 325 } 326 InsertRightEntry(const JSThread * thread,uint32_t parentIndex,uint32_t entry,JSTaggedValue key,JSTaggedValue value)327 inline void InsertRightEntry(const JSThread *thread, uint32_t parentIndex, uint32_t entry, JSTaggedValue key, 328 JSTaggedValue value) 329 { 330 SetKey(thread, entry, key); 331 SetValue(thread, entry, value); 332 SetColor(thread, entry, TreeColor::RED); 333 SetParent(thread, entry, JSTaggedValue(parentIndex)); 334 SetRightChild(thread, parentIndex, JSTaggedValue(entry)); 335 } 336 337 void InsertRebalance(const JSThread *thread, int index); 338 void DeleteRebalance(const JSThread *thread, int index); 339 IsValidIndex(int entry)340 inline bool IsValidIndex(int entry) const 341 { 342 return entry != GetRootEntries() && !GetKey(entry).IsHole(); 343 } 344 GetLeftBrother(int entry)345 inline int GetLeftBrother(int entry) const 346 { 347 JSTaggedValue child = GetRightChild(GetParent(entry)); 348 return child.IsHole() ? -1 : child.GetInt(); 349 } 350 GetRightBrother(int entry)351 inline int GetRightBrother(int entry) const 352 { 353 JSTaggedValue child = GetLeftChild(GetParent(entry)); 354 return child.IsHole() ? -1 : child.GetInt(); 355 } 356 IsLeft(int entry)357 inline bool IsLeft(int entry) const 358 { 359 JSTaggedValue child = GetLeftChild(GetParent(entry)); 360 return child.IsHole() ? false : (child.GetInt() == entry); 361 } 362 IsRight(int entry)363 inline bool IsRight(int entry) const 364 { 365 JSTaggedValue child = GetRightChild(GetParent(entry)); 366 return child.IsHole() ? false : (child.GetInt() == entry); 367 } 368 369 int GetPreDecessor(int entry) const; 370 int GetSuccessor(int entry) const; 371 SetLeftChild(const JSThread * thread,uint32_t entry,JSTaggedValue value)372 inline void SetLeftChild(const JSThread *thread, uint32_t entry, JSTaggedValue value) 373 { 374 int index = static_cast<int>(EntryToIndex(entry) + Derived::ENTRY_LEFT_CHILD_INDEX); 375 SetElement(thread, index, value); 376 } SetRightChild(const JSThread * thread,uint32_t entry,JSTaggedValue value)377 inline void SetRightChild(const JSThread *thread, uint32_t entry, JSTaggedValue value) 378 { 379 int index = static_cast<int>(EntryToIndex(entry) + Derived::ENTRY_RIGHT_CHILD_INDEX); 380 SetElement(thread, index, value); 381 } 382 383 void LeftRotate(const JSThread *thread, int index); 384 void RightRotate(const JSThread *thread, int index); 385 386 static JSHandle<Derived> AdjustTaggedTree(const JSThread *thread, const JSHandle<Derived> &tree, int len); OrdinayEntryCompare(JSThread * thread,const JSHandle<JSTaggedValue> valueX,const JSHandle<JSTaggedValue> valueY)387 inline static ComparisonResult OrdinayEntryCompare(JSThread *thread, const JSHandle<JSTaggedValue> valueX, 388 const JSHandle<JSTaggedValue> valueY) 389 { 390 if (valueX->IsString() && valueY->IsString()) { 391 auto xHandle = JSHandle<EcmaString>(valueX); 392 auto yHandle = JSHandle<EcmaString>(valueY); 393 int result = EcmaStringAccessor::Compare(thread->GetEcmaVM(), xHandle, yHandle); 394 if (result < 0) { 395 return ComparisonResult::LESS; 396 } 397 if (result == 0) { 398 return ComparisonResult::EQUAL; 399 } 400 return ComparisonResult::GREAT; 401 } 402 403 if (valueX->IsNumber() && valueY->IsNumber()) { 404 return JSTaggedValue::StrictNumberCompare(valueX->GetNumber(), valueY->GetNumber()); 405 } 406 407 if (valueX->IsNumber() && valueY->IsString()) { 408 return ComparisonResult::LESS; 409 } 410 if (valueX->IsString() && valueY->IsNumber()) { 411 return ComparisonResult::GREAT; 412 } 413 414 JSHandle<JSTaggedValue> xValueHandle(JSTaggedValue::ToString(thread, valueX)); 415 JSHandle<JSTaggedValue> yValueHandle(JSTaggedValue::ToString(thread, valueY)); 416 ASSERT_NO_ABRUPT_COMPLETION(thread); 417 return JSTaggedValue::Compare(thread, xValueHandle, yValueHandle); 418 } 419 CopyEntry(const JSThread * thread,int parent,const JSHandle<Derived> & newTree,int index)420 inline void CopyEntry(const JSThread *thread, int parent, const JSHandle<Derived> &newTree, int index) 421 { 422 newTree->SetKey(thread, index, GetKey(parent)); 423 newTree->SetColor(thread, index, GetColor(parent)); 424 } 425 CopyData(const JSThread * thread,int dst,int src)426 inline void CopyData(const JSThread *thread, int dst, int src) 427 { 428 SetKey(thread, dst, GetKey(src)); 429 } CopyAllData(const JSThread * thread,int parent,const JSHandle<Derived> & newTree,int index)430 inline void CopyAllData(const JSThread *thread, int parent, const JSHandle<Derived> &newTree, int index) 431 { 432 newTree->SetKey(thread, index, GetKey(parent)); 433 newTree->SetValue(thread, index, GetValue(parent)); 434 newTree->SetColor(thread, index, GetColor(parent)); 435 newTree->SetParent(thread, index, JSTaggedValue(GetParent(parent))); 436 newTree->SetRightChild(thread, index, GetRightChild(parent)); 437 newTree->SetLeftChild(thread, index, GetLeftChild(parent)); 438 } 439 RemoveEntry(const JSThread * thread,int index)440 inline void RemoveEntry(const JSThread *thread, int index) 441 { 442 SetKey(thread, index, JSTaggedValue::Hole()); 443 SetParent(thread, index, JSTaggedValue::Hole()); 444 SetLeftChild(thread, index, JSTaggedValue::Hole()); 445 SetRightChild(thread, index, JSTaggedValue::Hole()); 446 } 447 Transform(JSTaggedValue v)448 inline JSTaggedValue Transform(JSTaggedValue v) const 449 { 450 return v.IsHole() ? JSTaggedValue::Undefined() : v; 451 } 452 453 void Transplant(const JSThread *thread, int dst, int src); 454 455 static JSTaggedValue GetLowerKey(JSThread *thread, const JSHandle<Derived> &tree, 456 const JSHandle<JSTaggedValue> &key); 457 static JSTaggedValue GetHigherKey(JSThread *thread, const JSHandle<Derived> &tree, 458 const JSHandle<JSTaggedValue> &key); 459 static JSHandle<TaggedArray> GetSortArray(const JSThread *thread, const JSHandle<Derived> &tree); 460 static JSHandle<Derived> Shrink(const JSThread *thread, const JSHandle<Derived> &tree); 461 }; 462 463 464 class TaggedTreeMap : public TaggedTree<TaggedTreeMap> { 465 public: 466 using RBTree = TaggedTree<TaggedTreeMap>; Cast(TaggedObject * obj)467 static TaggedTreeMap *Cast(TaggedObject *obj) 468 { 469 return static_cast<TaggedTreeMap *>(obj); 470 } 471 472 static JSTaggedValue Create(const JSThread *thread, int numberOfElements = MIN_CAPACITY); 473 static JSTaggedValue Set(JSThread *thread, JSHandle<TaggedTreeMap> &obj, 474 const JSHandle<JSTaggedValue> &key, const JSHandle<JSTaggedValue> &value); Get(JSThread * thread,const JSHandle<TaggedTreeMap> & map,const JSHandle<JSTaggedValue> & key)475 inline static JSTaggedValue Get(JSThread *thread, const JSHandle<TaggedTreeMap> &map, 476 const JSHandle<JSTaggedValue> &key) 477 { 478 int index = RBTree::FindEntry(thread, map, key); 479 return index == -1 ? JSTaggedValue::Undefined() : map->GetValue(index); 480 } 481 482 static JSTaggedValue Delete(JSThread *thread, const JSHandle<TaggedTreeMap> &map, int entry); 483 bool HasValue(const JSThread *thread, JSTaggedValue value) const; 484 485 static JSTaggedValue GetLowerKey(JSThread *thread, const JSHandle<TaggedTreeMap> &map, 486 const JSHandle<JSTaggedValue> &key); 487 static JSTaggedValue GetHigherKey(JSThread *thread, const JSHandle<TaggedTreeMap> &map, 488 const JSHandle<JSTaggedValue> &key); 489 GetFirstKey()490 inline JSTaggedValue GetFirstKey() const 491 { 492 JSTaggedValue key = GetKey(GetMinimum(GetRootEntries())); 493 return Transform(key); 494 } 495 GetLastKey()496 inline JSTaggedValue GetLastKey() const 497 { 498 JSTaggedValue key = GetKey(GetMaximum(GetRootEntries())); 499 return Transform(key); 500 } 501 502 static JSTaggedValue SetAll(JSThread *thread, JSHandle<TaggedTreeMap> &dst, const JSHandle<TaggedTreeMap> &src); 503 static JSHandle<TaggedArray> GetArrayFromMap(const JSThread *thread, const JSHandle<TaggedTreeMap> &map); 504 static int FindEntry(JSThread *thread, const JSHandle<TaggedTreeMap> &map, const JSHandle<JSTaggedValue> &key); 505 506 static const int ENTRY_SIZE = 6; 507 static const int ENTRY_VALUE_INDEX = 1; 508 static const int ENTRY_COLOR_INDEX = 2; 509 static const int ENTRY_PARENT_INDEX = 3; 510 static const int ENTRY_LEFT_CHILD_INDEX = 4; 511 static const int ENTRY_RIGHT_CHILD_INDEX = 5; DECL_DUMP()512 DECL_DUMP() 513 514 inline void CopyEntry(const JSThread *thread, int parent, const JSHandle<TaggedTreeMap> &newMap, int index) 515 { 516 RBTree::CopyEntry(thread, parent, newMap, index); 517 newMap->SetValue(thread, index, GetValue(parent)); 518 } CopyData(const JSThread * thread,int dst,int src)519 inline void CopyData(const JSThread *thread, int dst, int src) 520 { 521 RBTree::CopyData(thread, dst, src); 522 SetValue(thread, dst, GetValue(src)); 523 } 524 RemoveEntry(const JSThread * thread,int index)525 inline void RemoveEntry(const JSThread *thread, int index) 526 { 527 RBTree::RemoveEntry(thread, index); 528 SetValue(thread, index, JSTaggedValue::Hole()); 529 } 530 }; 531 532 class TaggedTreeSet : public TaggedTree<TaggedTreeSet> { 533 public: 534 using RBTree = TaggedTree<TaggedTreeSet>; Cast(TaggedObject * obj)535 static TaggedTreeSet *Cast(TaggedObject *obj) 536 { 537 return static_cast<TaggedTreeSet *>(obj); 538 } 539 540 static JSTaggedValue Create(const JSThread *thread, int numberOfElements = MIN_CAPACITY); 541 static JSTaggedValue Add(JSThread *thread, JSHandle<TaggedTreeSet> &obj, const JSHandle<JSTaggedValue> &value); 542 static JSTaggedValue Delete(JSThread *thread, const JSHandle<TaggedTreeSet> &set, int entry); 543 544 static JSTaggedValue GetLowerKey(JSThread *thread, const JSHandle<TaggedTreeSet> &set, 545 const JSHandle<JSTaggedValue> &key); 546 static JSTaggedValue GetHigherKey(JSThread *thread, const JSHandle<TaggedTreeSet> &set, 547 const JSHandle<JSTaggedValue> &key); 548 GetFirstKey()549 inline JSTaggedValue GetFirstKey() const 550 { 551 JSTaggedValue key = GetKey(GetMinimum(GetRootEntries())); 552 return Transform(key); 553 } 554 GetLastKey()555 inline JSTaggedValue GetLastKey() const 556 { 557 JSTaggedValue key = GetKey(GetMaximum(GetRootEntries())); 558 return Transform(key); 559 } 560 561 static JSHandle<TaggedArray> GetArrayFromSet(const JSThread *thread, const JSHandle<TaggedTreeSet> &set); 562 static int FindEntry(JSThread *thread, const JSHandle<TaggedTreeSet> &set, const JSHandle<JSTaggedValue> &key); 563 564 static const int ENTRY_SIZE = 5; 565 static const int ENTRY_VALUE_INDEX = 0; 566 static const int ENTRY_COLOR_INDEX = 1; 567 static const int ENTRY_PARENT_INDEX = 2; 568 static const int ENTRY_LEFT_CHILD_INDEX = 3; 569 static const int ENTRY_RIGHT_CHILD_INDEX = 4; 570 DECL_DUMP()571 DECL_DUMP() 572 573 inline void CopyEntry(const JSThread *thread, int parent, const JSHandle<TaggedTreeSet> &newMap, int index) 574 { 575 RBTree::CopyEntry(thread, parent, newMap, index); 576 newMap->SetValue(thread, index, GetValue(parent)); 577 } 578 CopyData(const JSThread * thread,int dst,int src)579 inline void CopyData(const JSThread *thread, int dst, int src) 580 { 581 RBTree::CopyData(thread, dst, src); 582 SetValue(thread, dst, GetValue(src)); 583 } 584 RemoveEntry(const JSThread * thread,int index)585 inline void RemoveEntry(const JSThread *thread, int index) 586 { 587 RBTree::RemoveEntry(thread, index); 588 SetValue(thread, index, JSTaggedValue::Hole()); 589 } 590 }; 591 } // namespace panda::ecmascript 592 #endif // ECMASCRIPT_TAGGED_TREE_H 593