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 #include <string>
17 #include "ecmascript/base/builtins_base.h"
18 #include "ecmascript/ecma_runtime_call_info.h"
19 #include "ecmascript/global_env.h"
20 #include "ecmascript/js_handle.h"
21 #include "ecmascript/js_object-inl.h"
22 #include "ecmascript/js_tagged_value.h"
23 #include "ecmascript/object_factory.h"
24 #include "ecmascript/tagged_tree.h"
25 #include "ecmascript/tests/ecma_test_common.h"
26
27 using namespace panda;
28
29 using namespace panda::ecmascript;
30
31 namespace panda::test {
32 class TaggedTreeTest : public BaseTestWithScope<false> {
33 public:
GetGlobalEnv()34 JSHandle<GlobalEnv> GetGlobalEnv()
35 {
36 EcmaVM *ecma = thread->GetEcmaVM();
37 return ecma->GetGlobalEnv();
38 }
39 class TestClass : public base::BuiltinsBase {
40 public:
TestCompareFunction(EcmaRuntimeCallInfo * argv)41 static JSTaggedValue TestCompareFunction(EcmaRuntimeCallInfo *argv)
42 {
43 return TestCommon::TestCompareFunction(argv);
44 }
45 };
46 };
47
48 template <typename T>
CheckRBTreeOfAllPaths(JSHandle<T> & tree,int numsOfBlack,int index,int count)49 bool CheckRBTreeOfAllPaths(JSHandle<T> &tree, int numsOfBlack, int index, int count)
50 {
51 if (index < 0) {
52 return count == numsOfBlack;
53 }
54 if (tree->GetColor(index) == TreeColor::BLACK) {
55 count++;
56 }
57 if (CheckRBTreeOfAllPaths(tree, numsOfBlack, tree->GetLeftChildIndex(index), count) &&
58 CheckRBTreeOfAllPaths(tree, numsOfBlack, tree->GetRightChildIndex(index), count)) {
59 return true;
60 }
61 return false;
62 }
63
64 template <typename T>
CheckBlackNodeNumbers(JSHandle<T> & tree,int index)65 bool CheckBlackNodeNumbers(JSHandle<T> &tree, int index)
66 {
67 int numsOfBlack = 0;
68 int child = index;
69 while (child >= 0) {
70 if (tree->GetColor(child) == TreeColor::BLACK) {
71 numsOfBlack++;
72 }
73 child = tree->GetLeftChildIndex(child);
74 }
75 return CheckRBTreeOfAllPaths(tree, numsOfBlack, index, 0);
76 }
77
78 template <typename T>
IsVaildRBTree(JSThread * thread,JSHandle<T> & tree,int nodeIndex)79 bool IsVaildRBTree(JSThread *thread, JSHandle<T> &tree, int nodeIndex)
80 {
81 CQueue<int> nodes;
82 nodes.emplace(nodeIndex);
83 while (!nodes.empty()) {
84 int index = nodes.front();
85 int parent = tree->GetParent(index);
86 int pleft = tree->GetLeftChildIndex(parent);
87 int pright = tree->GetRightChildIndex(parent);
88 if (parent >= 0 && index != pleft && index != pright) {
89 return false;
90 }
91
92 int ileft = tree->GetLeftChildIndex(index);
93 JSHandle<JSTaggedValue> indexKey(thread, tree->GetKey(index));
94 if (ileft >= 0) {
95 JSHandle<JSTaggedValue> leftKey(thread, tree->GetKey(ileft));
96 ComparisonResult result = TaggedTree<T>::EntryCompare(thread, leftKey, indexKey, tree);
97 if (tree->GetParent(ileft) != index || result != ComparisonResult::LESS) {
98 return false;
99 }
100 nodes.emplace(ileft);
101 }
102 int iright = tree->GetRightChildIndex(index);
103 if (iright >= 0) {
104 JSHandle<JSTaggedValue> rightKey(thread, tree->GetKey(iright));
105 ComparisonResult result = TaggedTree<T>::EntryCompare(thread, rightKey, indexKey, tree);
106 if (tree->GetParent(iright) != index || result != ComparisonResult::GREAT) {
107 return false;
108 }
109 nodes.emplace(iright);
110 }
111
112 // check red node
113 TreeColor indexColor = tree->GetColor(index);
114 if (indexColor == TreeColor::RED) {
115 if (ileft >= 0 && tree->GetColor(ileft) == TreeColor::RED) {
116 return false;
117 }
118 if (iright >= 0 && tree->GetColor(iright) == TreeColor::RED) {
119 return false;
120 }
121 }
122 // check black node
123 if (!CheckBlackNodeNumbers(tree, index)) {
124 return false;
125 }
126 nodes.pop();
127 }
128 return true;
129 }
130
HWTEST_F_L0(TaggedTreeTest,TreeMapCreate)131 HWTEST_F_L0(TaggedTreeTest, TreeMapCreate)
132 {
133 constexpr int NODE_NUMBERS = 64;
134 JSHandle<TaggedTreeMap> tmap(thread, TaggedTreeMap::Create(thread, NODE_NUMBERS));
135 EXPECT_EQ(tmap->Capacity(), NODE_NUMBERS);
136 EXPECT_EQ(tmap->GetRootEntries(), -1);
137 EXPECT_EQ(tmap->NumberOfElements(), 0);
138 EXPECT_EQ(tmap->NumberOfDeletedElements(), 0);
139 }
140
HWTEST_F_L0(TaggedTreeTest,TreeSetCreate)141 HWTEST_F_L0(TaggedTreeTest, TreeSetCreate)
142 {
143 constexpr int NODE_NUMBERS = 64;
144 JSHandle<TaggedTreeSet> tset(thread, TaggedTreeSet::Create(thread, NODE_NUMBERS));
145 EXPECT_EQ(tset->Capacity(), NODE_NUMBERS);
146 EXPECT_EQ(tset->GetRootEntries(), -1);
147 EXPECT_EQ(tset->NumberOfElements(), 0);
148 EXPECT_EQ(tset->NumberOfDeletedElements(), 0);
149 }
150
HWTEST_F_L0(TaggedTreeTest,TestTreeMapAddKeyAndValue)151 HWTEST_F_L0(TaggedTreeTest, TestTreeMapAddKeyAndValue)
152 {
153 ObjectFactory *factory = thread->GetEcmaVM()->GetFactory();
154 constexpr int NODE_NUMBERS = 64;
155 JSMutableHandle<TaggedTreeMap> tmap(thread, TaggedTreeMap::Create(thread, NODE_NUMBERS));
156 JSHandle<JSTaggedValue> objFun = GetGlobalEnv()->GetObjectFunction();
157
158 char keyArray[] = "mykey1";
159 JSHandle<EcmaString> stringKey1 = factory->NewFromStdString(keyArray);
160 JSHandle<JSTaggedValue> key1(stringKey1);
161 JSHandle<JSTaggedValue> value1(factory->NewJSObjectByConstructor(JSHandle<JSFunction>(objFun), objFun));
162 char key2Array[] = "mykey2";
163 JSHandle<EcmaString> stringKey2 = factory->NewFromStdString(key2Array);
164 JSHandle<JSTaggedValue> key2(stringKey2);
165 JSHandle<JSTaggedValue> value2(factory->NewJSObjectByConstructor(JSHandle<JSFunction>(objFun), objFun));
166
167 // test set()
168 tmap.Update(TaggedTreeMap::Set(thread, tmap, key1, value1));
169 EXPECT_EQ(tmap->NumberOfElements(), 1);
170 tmap.Update(TaggedTreeMap::Set(thread, tmap, key2, value2));
171 EXPECT_EQ(tmap->NumberOfElements(), 2);
172
173 // test find()
174 JSTaggedValue res = TaggedTreeMap::Get(thread, tmap, key1);
175 EXPECT_EQ(value1.GetTaggedValue(), res);
176
177 // test remove()
178 int entry = TaggedTreeMap::FindEntry(thread, tmap, key1);
179 res = TaggedTreeMap::Delete(thread, tmap, entry);
180 EXPECT_EQ(TaggedTreeMap::Cast(res.GetTaggedObject())->NumberOfElements(), 1);
181 tmap.Update(res);
182 EXPECT_EQ(tmap->NumberOfElements(), 1);
183 res = TaggedTreeMap::Get(thread, tmap, key1);
184 EXPECT_EQ(res, JSTaggedValue::Undefined());
185 }
186
HWTEST_F_L0(TaggedTreeTest,TestTreeSetAddValue)187 HWTEST_F_L0(TaggedTreeTest, TestTreeSetAddValue)
188 {
189 ObjectFactory *factory = thread->GetEcmaVM()->GetFactory();
190 constexpr int NODE_NUMBERS = 64;
191 JSMutableHandle<TaggedTreeSet> tset(thread, TaggedTreeSet::Create(thread, NODE_NUMBERS));
192
193 char keyArray[] = "mykey1";
194 JSHandle<EcmaString> stringKey1 = factory->NewFromStdString(keyArray);
195 JSHandle<JSTaggedValue> key1(stringKey1);
196 char key2Array[] = "mykey2";
197 JSHandle<EcmaString> stringKey2 = factory->NewFromStdString(key2Array);
198 JSHandle<JSTaggedValue> key2(stringKey2);
199
200 // test set()
201 tset.Update(TaggedTreeSet::Add(thread, tset, key1));
202 EXPECT_EQ(tset->NumberOfElements(), 1);
203 tset.Update(TaggedTreeSet::Add(thread, tset, key2));
204 EXPECT_EQ(tset->NumberOfElements(), 2);
205
206 // test find()
207 int entry = TaggedTreeSet::FindEntry(thread, tset, key1);
208 EXPECT_TRUE(entry >= 0);
209
210 // test remove()
211 JSTaggedValue res = TaggedTreeSet::Delete(thread, tset, entry);
212 EXPECT_EQ(TaggedTreeSet::Cast(res.GetTaggedObject())->NumberOfElements(), 1);
213 EXPECT_EQ(-1, TaggedTreeSet::FindEntry(thread, tset, key1));
214 EXPECT_EQ(tset->NumberOfElements(), 1);
215 }
216
HWTEST_F_L0(TaggedTreeTest,TestTreeMapGrowCapacity)217 HWTEST_F_L0(TaggedTreeTest, TestTreeMapGrowCapacity)
218 {
219 constexpr int NODE_NUMBERS = 32;
220 ObjectFactory *factory = thread->GetEcmaVM()->GetFactory();
221 JSMutableHandle<TaggedTreeMap> tmap(thread, TaggedTreeMap::Create(thread));
222 JSHandle<JSFunction> objFun(GetGlobalEnv()->GetObjectFunction());
223 char keyArray[7] = "mykey"; // 7 means array length
224 for (int i = 0; i < NODE_NUMBERS; i++) {
225 keyArray[5] = '1' + static_cast<uint32_t>(i); // 5 means index of keyArray
226 keyArray[6] = 0; // 6 means index of keyArray
227 JSHandle<JSTaggedValue> key(factory->NewFromStdString(keyArray));
228 JSHandle<JSTaggedValue> value(thread, JSTaggedValue(i));
229 // test set()
230 tmap.Update(TaggedTreeMap::Set(thread, tmap, key, value));
231 EXPECT_TRUE(TaggedTreeMap::FindEntry(thread, tmap, key) >= 0);
232 }
233
234 for (int i = 0; i < NODE_NUMBERS; i++) {
235 keyArray[5] = '1' + static_cast<uint32_t>(i); // 5 means index of keyArray
236 keyArray[6] = 0; // 6 means index of keyArray
237 JSHandle<JSTaggedValue> stringKey(factory->NewFromStdString(keyArray));
238 // test get()
239 JSTaggedValue res = TaggedTreeMap::Get(thread, tmap, stringKey);
240 EXPECT_EQ(JSTaggedValue(i), res);
241 }
242 EXPECT_EQ(tmap->NumberOfElements(), NODE_NUMBERS);
243 EXPECT_EQ(tmap->Capacity(), 63); // 63 means capacity after Grow
244 }
245
HWTEST_F_L0(TaggedTreeTest,TestTreeSetGrowCapacity)246 HWTEST_F_L0(TaggedTreeTest, TestTreeSetGrowCapacity)
247 {
248 constexpr int NODE_NUMBERS = 32;
249 ObjectFactory *factory = thread->GetEcmaVM()->GetFactory();
250 JSMutableHandle<TaggedTreeSet> tset(thread, TaggedTreeSet::Create(thread));
251 // create key
252 char keyArray[7] = "mykey"; // 7 means array length
253 for (int i = 0; i < NODE_NUMBERS; i++) {
254 keyArray[5] = '1' + static_cast<uint32_t>(i); // 5 means index of keyArray
255 keyArray[6] = 0; // 6 means index of keyArray
256 JSHandle<EcmaString> stringKey = factory->NewFromStdString(keyArray);
257 JSHandle<JSTaggedValue> key(stringKey);
258
259 // test set()
260 tset.Update(TaggedTreeSet::Add(thread, tset, key));
261 EXPECT_TRUE(TaggedTreeSet::FindEntry(thread, tset, key) >= 0);
262 }
263
264 for (int i = 0; i < NODE_NUMBERS; i++) {
265 keyArray[5] = '1' + static_cast<uint32_t>(i); // 5 means index of keyArray
266 keyArray[6] = 0; // 6 means index of keyArray
267 JSHandle<JSTaggedValue> stringKey(factory->NewFromStdString(keyArray));
268 // test get()#
269 EXPECT_TRUE(TaggedTreeSet::FindEntry(thread, tset, stringKey) >= 0);
270 }
271 EXPECT_EQ(tset->NumberOfElements(), NODE_NUMBERS);
272 EXPECT_EQ(tset->Capacity(), 63); // 63 means capacity after Grow
273 }
274
KeyValueUpdate(JSThread * thread,JSMutableHandle<TaggedTreeMap> & tmap,std::vector<std::string> & strKeyValue,std::vector<JSMutableHandle<JSTaggedValue>> & keyValue,int32_t nums)275 void KeyValueUpdate(JSThread *thread, JSMutableHandle<TaggedTreeMap>& tmap, std::vector<std::string>& strKeyValue,
276 std::vector<JSMutableHandle<JSTaggedValue>>& keyValue, int32_t nums)
277 {
278 ObjectFactory *factory = thread->GetEcmaVM()->GetFactory();
279 for (int32_t i = 0; i < nums; i++) {
280 std::string ikey = strKeyValue[0] + std::to_string(i);
281 std::string ivalue = strKeyValue[1] + std::to_string(i); // 1 : value index
282 keyValue[0].Update(factory->NewFromStdString(ikey).GetTaggedValue());
283 keyValue[1].Update(factory->NewFromStdString(ivalue).GetTaggedValue()); // 1 : value index
284 tmap.Update(TaggedTreeMap::Set(thread, tmap, keyValue[0], keyValue[1])); // 1 : value index
285 }
286 }
287
KeyValueCommon(JSThread * thread,std::string & myKey,std::string & myValue,std::vector<JSMutableHandle<JSTaggedValue>> & keyValue,int32_t nums)288 JSMutableHandle<TaggedTreeMap> KeyValueCommon(JSThread *thread, std::string& myKey, std::string& myValue,
289 std::vector<JSMutableHandle<JSTaggedValue>>& keyValue, int32_t nums)
290 {
291 JSMutableHandle<JSTaggedValue> key(thread, JSTaggedValue::Undefined());
292 JSMutableHandle<JSTaggedValue> value(thread, JSTaggedValue::Undefined());
293 keyValue.push_back(key);
294 keyValue.push_back(value);
295 JSMutableHandle<TaggedTreeMap> tmap(thread, TaggedTreeMap::Create(thread));
296 std::vector<std::string> strKeyValue{myKey, myValue};
297 KeyValueUpdate(thread, tmap, strKeyValue, keyValue, nums);
298 return tmap;
299 }
300
KeyValueCommon(JSThread * thread,std::vector<JSMutableHandle<JSTaggedValue>> & keyValue,int32_t nums)301 JSMutableHandle<TaggedTreeMap> KeyValueCommon(JSThread *thread, std::vector<JSMutableHandle<JSTaggedValue>>& keyValue,
302 int32_t nums)
303 {
304 JSMutableHandle<JSTaggedValue> key(thread, JSTaggedValue::Undefined());
305 JSMutableHandle<JSTaggedValue> value(thread, JSTaggedValue::Undefined());
306
307 // test TaggedTreeMap
308 JSMutableHandle<TaggedTreeMap> tmap(thread, TaggedTreeMap::Create(thread));
309 for (int i = 0; i < nums; i++) {
310 key.Update(JSTaggedValue(i));
311 value.Update(JSTaggedValue(i));
312 tmap.Update(TaggedTreeMap::Set(thread, tmap, key, value));
313 }
314 keyValue.push_back(key);
315 keyValue.push_back(value);
316 return tmap;
317 }
318
HWTEST_F_L0(TaggedTreeTest,TestTreeMapHasValue)319 HWTEST_F_L0(TaggedTreeTest, TestTreeMapHasValue)
320 {
321 constexpr int NODE_NUMBERS = 8;
322 std::string myKey("mykey");
323 std::string myValue("myvalue");
324 std::vector<JSMutableHandle<JSTaggedValue>> keyValue;
325 // test TaggedTreeMap HasValue
326 auto tmap = KeyValueCommon(thread, myKey, myValue, keyValue, static_cast<int32_t>(NODE_NUMBERS));
327 EXPECT_EQ(tmap->NumberOfElements(), NODE_NUMBERS);
328 EXPECT_EQ(tmap->Capacity(), 15); // 15 means capacity after Grow
329 ObjectFactory *factory = thread->GetEcmaVM()->GetFactory();
330 for (int i = 0; i < NODE_NUMBERS; i++) {
331 std::string ivalue = myValue + std::to_string(i);
332 keyValue[1].Update(factory->NewFromStdString(ivalue).GetTaggedValue()); // 1 : value index
333 bool success = tmap->HasValue(thread, keyValue[1].GetTaggedValue()); // 1 : value index
334 EXPECT_TRUE(success);
335 }
336 }
337
HWTEST_F_L0(TaggedTreeTest,TestTreeMapGetLowerKey)338 HWTEST_F_L0(TaggedTreeTest, TestTreeMapGetLowerKey)
339 {
340 constexpr int NODE_NUMBERS = 8;
341 ObjectFactory *factory = thread->GetEcmaVM()->GetFactory();
342 std::string myKey("mykey");
343 std::string myValue("myvalue");
344
345 // test TaggedTreeMap
346 std::vector<JSMutableHandle<JSTaggedValue>> keyValue;
347 auto tmap = KeyValueCommon(thread, myKey, myValue, keyValue, static_cast<int32_t>(NODE_NUMBERS));
348
349 std::string minKey = myKey + std::to_string(0);
350 keyValue[0].Update(factory->NewFromStdString(minKey).GetTaggedValue());
351 JSTaggedValue lowerKey = TaggedTreeMap::GetLowerKey(thread, tmap, keyValue[0]);
352 EXPECT_TRUE(lowerKey.IsUndefined());
353
354 // add [1, 1]
355 keyValue[0].Update(JSTaggedValue(1));
356 keyValue[1].Update(JSTaggedValue(1));
357 tmap.Update(TaggedTreeMap::Set(thread, tmap, keyValue[0], keyValue[1]));
358
359 keyValue[0].Update(factory->NewFromStdString(minKey).GetTaggedValue());
360 lowerKey = TaggedTreeMap::GetLowerKey(thread, tmap, keyValue[0]);
361 EXPECT_EQ(lowerKey, JSTaggedValue(1));
362
363 // check mykey1 ...mykeyn
364 JSMutableHandle<JSTaggedValue> keyToCompare(thread, JSTaggedValue::Undefined());
365 for (uint32_t i = 1; i < NODE_NUMBERS; i++) {
366 std::string ikey = myKey + std::to_string(i);
367 keyValue[0].Update(factory->NewFromStdString(ikey).GetTaggedValue());
368 std::string tmp = myKey + std::to_string(i - 1);
369 keyToCompare.Update(factory->NewFromStdString(tmp).GetTaggedValue());
370 lowerKey = TaggedTreeMap::GetLowerKey(thread, tmap, keyValue[0]);
371 EXPECT_EQ(lowerKey, keyToCompare.GetTaggedValue());
372 }
373 }
374
HWTEST_F_L0(TaggedTreeTest,TestTreeMapGetHigherKey)375 HWTEST_F_L0(TaggedTreeTest, TestTreeMapGetHigherKey)
376 {
377 constexpr int NODE_NUMBERS = 8;
378 ObjectFactory *factory = thread->GetEcmaVM()->GetFactory();
379 std::vector<JSMutableHandle<JSTaggedValue>> keyValue;
380 auto tmap = KeyValueCommon(thread, keyValue, static_cast<int32_t>(NODE_NUMBERS));
381 JSMutableHandle<JSTaggedValue> maxKey(thread, JSTaggedValue(NODE_NUMBERS - 1));
382 JSTaggedValue higherKey = TaggedTreeMap::GetHigherKey(thread, tmap, maxKey);
383 EXPECT_TRUE(higherKey.IsUndefined());
384
385 // add [mykey, mykey]
386 std::string myKey("mykey");
387 keyValue[0].Update(factory->NewFromStdString(myKey).GetTaggedValue());
388 tmap.Update(TaggedTreeMap::Set(thread, tmap, keyValue[0], keyValue[1]));
389
390 higherKey = TaggedTreeMap::GetHigherKey(thread, tmap, maxKey);
391 EXPECT_EQ(higherKey, keyValue[0].GetTaggedValue());
392
393 // check 1 ...n
394 JSMutableHandle<JSTaggedValue> keyToCompare(thread, JSTaggedValue::Undefined());
395 for (int i = 0; i < NODE_NUMBERS - 1; i++) {
396 keyValue[0].Update(JSTaggedValue(i));
397 keyToCompare.Update(JSTaggedValue(i + 1));
398 higherKey = TaggedTreeMap::GetHigherKey(thread, tmap, keyValue[0]);
399 EXPECT_EQ(higherKey, keyToCompare.GetTaggedValue());
400 }
401 }
402
HWTEST_F_L0(TaggedTreeTest,TestTreeMapGetFirsKey)403 HWTEST_F_L0(TaggedTreeTest, TestTreeMapGetFirsKey)
404 {
405 constexpr int NODE_NUMBERS = 8;
406 ObjectFactory *factory = thread->GetEcmaVM()->GetFactory();
407 std::string myKey("mykey");
408 std::string myValue("myvalue");
409
410 std::vector<JSMutableHandle<JSTaggedValue>> keyValue;
411 auto tmap = KeyValueCommon(thread, myKey, myValue, keyValue, static_cast<int32_t>(NODE_NUMBERS));
412 std::string ckey = myKey + std::to_string(0);
413 keyValue[0].Update(factory->NewFromStdString(ckey).GetTaggedValue());
414 JSTaggedValue firstKey = tmap->GetFirstKey();
415 EXPECT_EQ(firstKey, keyValue[0].GetTaggedValue());
416
417 for (int i = 0; i < NODE_NUMBERS; i++) {
418 keyValue[0].Update(JSTaggedValue(i));
419 keyValue[1].Update(JSTaggedValue(i));
420 tmap.Update(TaggedTreeMap::Set(thread, tmap, keyValue[0], keyValue[1]));
421 }
422 firstKey = tmap->GetFirstKey();
423 EXPECT_EQ(firstKey, JSTaggedValue(0));
424 }
425
HWTEST_F_L0(TaggedTreeTest,TestTreeMapGetLastKey)426 HWTEST_F_L0(TaggedTreeTest, TestTreeMapGetLastKey)
427 {
428 constexpr int32_t NODE_NUMBERS = 8;
429 ObjectFactory *factory = thread->GetEcmaVM()->GetFactory();
430 std::vector<JSMutableHandle<JSTaggedValue>> keyValue;
431 auto tmap = KeyValueCommon(thread, keyValue, NODE_NUMBERS);
432
433 JSTaggedValue lastKey = tmap->GetLastKey();
434 EXPECT_EQ(lastKey, JSTaggedValue(NODE_NUMBERS - 1));
435
436 std::string myKey("mykey");
437 std::string myValue("myvalue");
438 std::vector<std::string> strKeyValue{myKey, myValue};
439 KeyValueUpdate(thread, tmap, strKeyValue, keyValue, NODE_NUMBERS);
440 std::string ckey = myKey + std::to_string(NODE_NUMBERS - 1);
441 keyValue[0].Update(factory->NewFromStdString(ckey).GetTaggedValue());
442 lastKey = tmap->GetLastKey();
443 EXPECT_EQ(lastKey, keyValue[0].GetTaggedValue());
444 }
445
HWTEST_F_L0(TaggedTreeTest,TestTreeMapSetAll)446 HWTEST_F_L0(TaggedTreeTest, TestTreeMapSetAll)
447 {
448 constexpr int NODE_NUMBERS = 8;
449 ObjectFactory *factory = thread->GetEcmaVM()->GetFactory();
450 JSMutableHandle<JSTaggedValue> key(thread, JSTaggedValue::Undefined());
451 JSMutableHandle<JSTaggedValue> value(thread, JSTaggedValue::Undefined());
452
453 // test TaggedTreeMap
454 JSMutableHandle<TaggedTreeMap> smap(thread, TaggedTreeMap::Create(thread));
455 for (int i = 0; i < NODE_NUMBERS; i++) {
456 key.Update(JSTaggedValue(i));
457 value.Update(JSTaggedValue(i));
458 smap.Update(TaggedTreeMap::Set(thread, smap, key, value));
459 }
460
461 JSMutableHandle<TaggedTreeMap> dmap(thread, TaggedTreeMap::Create(thread));
462 std::string myKey("mykey");
463 std::string myValue("myvalue");
464 for (int i = 0; i < NODE_NUMBERS; i++) {
465 std::string ikey = myKey + std::to_string(i);
466 std::string ivalue = myValue + std::to_string(i);
467 key.Update(factory->NewFromStdString(ikey).GetTaggedValue());
468 value.Update(factory->NewFromStdString(ivalue).GetTaggedValue());
469 dmap.Update(TaggedTreeMap::Set(thread, dmap, key, value));
470 }
471 dmap.Update(TaggedTreeMap::SetAll(thread, dmap, smap));
472
473 for (int i = 0; i < NODE_NUMBERS; i++) {
474 key.Update(JSTaggedValue(i));
475 value.Update(JSTaggedValue(i));
476 JSTaggedValue res = TaggedTreeMap::Get(thread, dmap, key);
477 EXPECT_EQ(res, value.GetTaggedValue());
478
479 std::string ikey = myKey + std::to_string(i);
480 std::string ivalue = myValue + std::to_string(i);
481 key.Update(factory->NewFromStdString(ikey).GetTaggedValue());
482 value.Update(factory->NewFromStdString(ivalue).GetTaggedValue());
483 res = TaggedTreeMap::Get(thread, dmap, key);
484 EXPECT_EQ(res, value.GetTaggedValue());
485 }
486 }
487
HWTEST_F_L0(TaggedTreeTest,TestTreeMapGetArrayFromMap)488 HWTEST_F_L0(TaggedTreeTest, TestTreeMapGetArrayFromMap)
489 {
490 constexpr int NODE_NUMBERS = 8;
491 ObjectFactory *factory = thread->GetEcmaVM()->GetFactory();
492
493 std::vector<JSMutableHandle<JSTaggedValue>> keyValue;
494 auto tmap = KeyValueCommon(thread, keyValue, static_cast<int32_t>(NODE_NUMBERS));
495
496 std::string myKey("mykey");
497 std::string myValue("myvalue");
498 std::vector<std::string> keyValueStr{myKey, myValue};
499 KeyValueUpdate(thread, tmap, keyValueStr, keyValue, static_cast<int32_t>(NODE_NUMBERS));
500 JSHandle<TaggedArray> arr = TaggedTreeMap::GetArrayFromMap(thread, tmap);
501 EXPECT_EQ(static_cast<int>(arr->GetLength()), NODE_NUMBERS * 2);
502
503 for (int i = 0; i < NODE_NUMBERS; i++) {
504 EXPECT_EQ(tmap->GetKey(arr->Get(i).GetInt()), JSTaggedValue(i));
505 }
506 for (int i = 0; i < NODE_NUMBERS; i++) {
507 std::string ikey = myKey + std::to_string(i);
508 keyValue[0].Update(factory->NewFromStdString(ikey).GetTaggedValue());
509 EXPECT_EQ(tmap->GetKey(arr->Get(NODE_NUMBERS + i).GetInt()), keyValue[0].GetTaggedValue());
510 }
511 }
512
SetKeyCommon(JSThread * thread,JSMutableHandle<TaggedTreeSet> & tset,JSMutableHandle<JSTaggedValue> & key,std::string & myKey,int nums)513 void SetKeyCommon(JSThread* thread, JSMutableHandle<TaggedTreeSet>& tset, JSMutableHandle<JSTaggedValue>& key,
514 std::string& myKey, int nums)
515 {
516 ObjectFactory *factory = thread->GetEcmaVM()->GetFactory();
517 // test TaggedTreeSet
518 for (int i = 0; i < nums; i++) {
519 std::string ikey = myKey + std::to_string(i);
520 key.Update(factory->NewFromStdString(ikey).GetTaggedValue());
521 tset.Update(TaggedTreeSet::Add(thread, tset, key));
522 }
523 }
524
525 // TaggedTreeSet
HWTEST_F_L0(TaggedTreeTest,TestTreeSetGetLowerKey)526 HWTEST_F_L0(TaggedTreeTest, TestTreeSetGetLowerKey)
527 {
528 constexpr int NODE_NUMBERS = 8;
529 ObjectFactory *factory = thread->GetEcmaVM()->GetFactory();
530 JSMutableHandle<JSTaggedValue> key(thread, JSTaggedValue::Undefined());
531 std::string myKey("mykey");
532 // test TaggedTreeSet
533 JSMutableHandle<TaggedTreeSet> tset(thread, TaggedTreeSet::Create(thread));
534 SetKeyCommon(thread, tset, key, myKey, NODE_NUMBERS);
535
536 std::string minKey = myKey + std::to_string(0);
537 key.Update(factory->NewFromStdString(minKey).GetTaggedValue());
538 JSTaggedValue lowerKey = TaggedTreeSet::GetLowerKey(thread, tset, key);
539 EXPECT_TRUE(lowerKey.IsUndefined());
540
541 // add [1, 1]
542 key.Update(JSTaggedValue(1));
543 tset.Update(TaggedTreeSet::Add(thread, tset, key));
544
545 key.Update(factory->NewFromStdString(minKey).GetTaggedValue());
546 lowerKey = TaggedTreeSet::GetLowerKey(thread, tset, key);
547 EXPECT_EQ(lowerKey, JSTaggedValue(1));
548
549 // check mykey1 ...mykeyn
550 JSMutableHandle<JSTaggedValue> keyToCompare(thread, JSTaggedValue::Undefined());
551 for (uint32_t i = 1; i < NODE_NUMBERS; i++) {
552 std::string ikey = myKey + std::to_string(i);
553 key.Update(factory->NewFromStdString(ikey).GetTaggedValue());
554 std::string tmp = myKey + std::to_string(i - 1);
555 keyToCompare.Update(factory->NewFromStdString(tmp).GetTaggedValue());
556 lowerKey = TaggedTreeSet::GetLowerKey(thread, tset, key);
557 EXPECT_EQ(lowerKey, keyToCompare.GetTaggedValue());
558 }
559 }
560
HWTEST_F_L0(TaggedTreeTest,TestTreeSetGetHigherKey)561 HWTEST_F_L0(TaggedTreeTest, TestTreeSetGetHigherKey)
562 {
563 constexpr int NODE_NUMBERS = 8;
564 ObjectFactory *factory = thread->GetEcmaVM()->GetFactory();
565 JSMutableHandle<JSTaggedValue> key(thread, JSTaggedValue::Undefined());
566
567 // test TaggedTreeSet
568 JSMutableHandle<TaggedTreeSet> tset(thread, TaggedTreeSet::Create(thread));
569 for (int i = 0; i < NODE_NUMBERS; i++) {
570 key.Update(JSTaggedValue(i));
571 tset.Update(TaggedTreeSet::Add(thread, tset, key));
572 }
573
574 JSMutableHandle<JSTaggedValue> maxKey(thread, JSTaggedValue(NODE_NUMBERS - 1));
575 JSTaggedValue higherKey = TaggedTreeSet::GetHigherKey(thread, tset, maxKey);
576 EXPECT_TRUE(higherKey.IsUndefined());
577
578 // add [mykey, mykey]
579 std::string myKey("mykey");
580 key.Update(factory->NewFromStdString(myKey).GetTaggedValue());
581 tset.Update(TaggedTreeSet::Add(thread, tset, key));
582
583 higherKey = TaggedTreeSet::GetHigherKey(thread, tset, maxKey);
584 EXPECT_EQ(higherKey, key.GetTaggedValue());
585
586 // check 1 ...n
587 JSMutableHandle<JSTaggedValue> keyToCompare(thread, JSTaggedValue::Undefined());
588 for (int i = 0; i < NODE_NUMBERS - 1; i++) {
589 key.Update(JSTaggedValue(i));
590 keyToCompare.Update(JSTaggedValue(i + 1));
591 higherKey = TaggedTreeSet::GetHigherKey(thread, tset, key);
592 EXPECT_EQ(higherKey, keyToCompare.GetTaggedValue());
593 }
594 }
595
HWTEST_F_L0(TaggedTreeTest,TestTreeSetGetFirsKey)596 HWTEST_F_L0(TaggedTreeTest, TestTreeSetGetFirsKey)
597 {
598 constexpr int NODE_NUMBERS = 8;
599 ObjectFactory *factory = thread->GetEcmaVM()->GetFactory();
600 JSMutableHandle<JSTaggedValue> key(thread, JSTaggedValue::Undefined());
601 std::string myKey("mykey");
602
603 // test TaggedTreeSet
604 JSMutableHandle<TaggedTreeSet> tset(thread, TaggedTreeSet::Create(thread));
605 SetKeyCommon(thread, tset, key, myKey, NODE_NUMBERS);
606 std::string ckey = myKey + std::to_string(0);
607 key.Update(factory->NewFromStdString(ckey).GetTaggedValue());
608 JSTaggedValue firstKey = tset->GetFirstKey();
609 EXPECT_EQ(firstKey, key.GetTaggedValue());
610
611 for (int i = 0; i < NODE_NUMBERS; i++) {
612 key.Update(JSTaggedValue(i));
613 tset.Update(TaggedTreeSet::Add(thread, tset, key));
614 }
615 firstKey = tset->GetFirstKey();
616 EXPECT_EQ(firstKey, JSTaggedValue(0));
617 }
618
HWTEST_F_L0(TaggedTreeTest,TestTreeSetGetLastKey)619 HWTEST_F_L0(TaggedTreeTest, TestTreeSetGetLastKey)
620 {
621 constexpr int NODE_NUMBERS = 8;
622 ObjectFactory *factory = thread->GetEcmaVM()->GetFactory();
623 JSMutableHandle<JSTaggedValue> key(thread, JSTaggedValue::Undefined());
624
625 // test TaggedTreeSet
626 JSMutableHandle<TaggedTreeSet> tset(thread, TaggedTreeSet::Create(thread));
627 for (int i = 0; i < NODE_NUMBERS; i++) {
628 key.Update(JSTaggedValue(i));
629 tset.Update(TaggedTreeSet::Add(thread, tset, key));
630 }
631 JSTaggedValue lastKey = tset->GetLastKey();
632 EXPECT_EQ(lastKey, JSTaggedValue(NODE_NUMBERS - 1));
633
634 std::string myKey("mykey");
635 for (int i = 0; i < NODE_NUMBERS; i++) {
636 std::string ikey = myKey + std::to_string(i);
637 key.Update(factory->NewFromStdString(ikey).GetTaggedValue());
638 tset.Update(TaggedTreeSet::Add(thread, tset, key));
639 }
640 std::string ckey = myKey + std::to_string(NODE_NUMBERS - 1);
641 key.Update(factory->NewFromStdString(ckey).GetTaggedValue());
642 lastKey = tset->GetLastKey();
643 EXPECT_EQ(lastKey, key.GetTaggedValue());
644 }
645
HWTEST_F_L0(TaggedTreeTest,TestTreeSetGetArrayFromSet)646 HWTEST_F_L0(TaggedTreeTest, TestTreeSetGetArrayFromSet)
647 {
648 constexpr int NODE_NUMBERS = 8;
649 ObjectFactory *factory = thread->GetEcmaVM()->GetFactory();
650 JSMutableHandle<JSTaggedValue> key(thread, JSTaggedValue::Undefined());
651
652 // test TaggedTreeSet
653 JSMutableHandle<TaggedTreeSet> tset(thread, TaggedTreeSet::Create(thread));
654 for (int i = 0; i < NODE_NUMBERS; i++) {
655 key.Update(JSTaggedValue(i));
656 tset.Update(TaggedTreeSet::Add(thread, tset, key));
657 }
658
659 std::string myKey("mykey");
660 for (int i = 0; i < NODE_NUMBERS; i++) {
661 std::string ikey = myKey + std::to_string(i);
662 key.Update(factory->NewFromStdString(ikey).GetTaggedValue());
663 tset.Update(TaggedTreeSet::Add(thread, tset, key));
664 }
665 JSHandle<TaggedArray> arr = TaggedTreeSet::GetArrayFromSet(thread, tset);
666 EXPECT_EQ(static_cast<int>(arr->GetLength()), NODE_NUMBERS * 2);
667
668 for (int i = 0; i < NODE_NUMBERS; i++) {
669 EXPECT_EQ(tset->GetKey(arr->Get(i).GetInt()), JSTaggedValue(i));
670 }
671 for (int i = 0; i < NODE_NUMBERS; i++) {
672 std::string ikey = myKey + std::to_string(i);
673 key.Update(factory->NewFromStdString(ikey).GetTaggedValue());
674 EXPECT_EQ(tset->GetKey(arr->Get(NODE_NUMBERS + i).GetInt()), key.GetTaggedValue());
675 }
676 }
677
TestSetAfterDeleteCheckOther(JSThread * thread,std::vector<JSMutableHandle<JSTaggedValue>> & keyValue,std::string & myKey,int NODE_NUMBERS)678 void TestSetAfterDeleteCheckOther(JSThread* thread, std::vector<JSMutableHandle<JSTaggedValue>>& keyValue,
679 std::string& myKey, int NODE_NUMBERS)
680 {
681 ObjectFactory *factory = thread->GetEcmaVM()->GetFactory();
682 // TaggedTreeSet
683 JSMutableHandle<TaggedTreeSet> tset(thread, TaggedTreeSet::Create(thread));
684 for (int i = 0; i < NODE_NUMBERS; i++) {
685 keyValue[0].Update(JSTaggedValue(i));
686 tset.Update(TaggedTreeSet::Add(thread, tset, keyValue[0]));
687 }
688 EXPECT_EQ(tset->NumberOfElements(), NODE_NUMBERS);
689 EXPECT_EQ(tset->NumberOfDeletedElements(), 0);
690
691 for (int i = 0; i < NODE_NUMBERS / 2; i++) { // 2 : half
692 keyValue[0].Update(JSTaggedValue(i));
693 JSTaggedValue dvalue = TaggedTreeSet::Delete(thread, tset, TaggedTreeSet::FindEntry(thread, tset, keyValue[0]));
694 EXPECT_EQ(dvalue, tset.GetTaggedValue());
695 }
696 EXPECT_EQ(tset->NumberOfElements(), NODE_NUMBERS / 2); // 2 : half
697 EXPECT_EQ(tset->NumberOfDeletedElements(), NODE_NUMBERS / 2); // 2 : half
698
699 for (int i = 0; i < NODE_NUMBERS; i++) {
700 std::string ikey = myKey + std::to_string(i);
701 keyValue[0].Update(factory->NewFromStdString(ikey).GetTaggedValue());
702 tset.Update(TaggedTreeSet::Add(thread, tset, keyValue[0]));
703 }
704 EXPECT_EQ(tset->NumberOfElements(), NODE_NUMBERS + NODE_NUMBERS / 2); // 2 : half
705 EXPECT_EQ(tset->NumberOfDeletedElements(), 0);
706
707 for (uint32_t i = NODE_NUMBERS / 2; i < NODE_NUMBERS; i++) {
708 keyValue[0].Update(JSTaggedValue(i));
709 int entry = TaggedTreeSet::FindEntry(thread, tset, keyValue[0]);
710 EXPECT_TRUE(entry >= 0);
711 }
712
713 for (int i = 0; i < NODE_NUMBERS; i++) {
714 std::string ikey = myKey + std::to_string(i);
715 keyValue[0].Update(factory->NewFromStdString(ikey).GetTaggedValue());
716 int entry = TaggedTreeSet::FindEntry(thread, tset, keyValue[0]);
717 EXPECT_TRUE(entry >= 0);
718 }
719 EXPECT_EQ(tset->NumberOfElements(), NODE_NUMBERS + NODE_NUMBERS / 2); // 2 : half
720 EXPECT_EQ(tset->Capacity(), 31); // 31 means capacity after grow
721 }
722
HWTEST_F_L0(TaggedTreeTest,TestSetAfterDelete)723 HWTEST_F_L0(TaggedTreeTest, TestSetAfterDelete)
724 {
725 constexpr int NODE_NUMBERS = 8;
726 ObjectFactory *factory = thread->GetEcmaVM()->GetFactory();
727 std::vector<JSMutableHandle<JSTaggedValue>> keyValue;
728 auto tmap = KeyValueCommon(thread, keyValue, static_cast<int32_t>(NODE_NUMBERS));
729 EXPECT_EQ(tmap->NumberOfElements(), NODE_NUMBERS);
730 EXPECT_EQ(tmap->NumberOfDeletedElements(), 0);
731
732 for (int i = 0; i < NODE_NUMBERS / 2; i++) {
733 keyValue[0].Update(JSTaggedValue(i));
734 keyValue[1].Update(JSTaggedValue(i));
735 JSTaggedValue dvalue = TaggedTreeMap::Delete(thread, tmap, TaggedTreeMap::FindEntry(thread, tmap, keyValue[0]));
736 EXPECT_EQ(dvalue, tmap.GetTaggedValue());
737 }
738 EXPECT_EQ(tmap->NumberOfElements(), NODE_NUMBERS / 2);
739 EXPECT_EQ(tmap->NumberOfDeletedElements(), NODE_NUMBERS / 2);
740
741 std::string myKey("mykey");
742 std::string myValue("myvalue");
743 std::vector<std::string> myKeyValue{myKey, myValue};
744 KeyValueUpdate(thread, tmap, myKeyValue, keyValue, static_cast<int32_t>(NODE_NUMBERS));
745 EXPECT_EQ(tmap->NumberOfElements(), NODE_NUMBERS + NODE_NUMBERS / 2);
746 EXPECT_EQ(tmap->NumberOfDeletedElements(), 0);
747
748 for (uint32_t i = NODE_NUMBERS / 2; i < NODE_NUMBERS; i++) {
749 keyValue[0].Update(JSTaggedValue(i));
750 keyValue[1].Update(JSTaggedValue(i));
751 JSTaggedValue gvalue = TaggedTreeMap::Get(thread, tmap, keyValue[0]);
752 EXPECT_EQ(gvalue, keyValue[1].GetTaggedValue());
753 }
754
755 for (int i = 0; i < NODE_NUMBERS; i++) {
756 std::string ikey = myKey + std::to_string(i);
757 std::string ivalue = myValue + std::to_string(i);
758 keyValue[0].Update(factory->NewFromStdString(ikey).GetTaggedValue());
759 keyValue[1].Update(factory->NewFromStdString(ivalue).GetTaggedValue());
760 JSTaggedValue gvalue = TaggedTreeMap::Get(thread, tmap, keyValue[0]);
761 EXPECT_EQ(gvalue, keyValue[1].GetTaggedValue());
762 }
763 EXPECT_EQ(tmap->NumberOfElements(), NODE_NUMBERS + NODE_NUMBERS / 2);
764 EXPECT_EQ(tmap->Capacity(), 31); // 31 means capacity after grow
765 TestSetAfterDeleteCheckOther(thread, keyValue, myKey, NODE_NUMBERS);
766 }
767
RTCommon(JSThread * thread,std::vector<JSMutableHandle<JSTaggedValue>> & keyValue,std::string & myKey,std::string & myValue,int nums)768 JSMutableHandle<TaggedTreeMap> RTCommon(JSThread *thread, std::vector<JSMutableHandle<JSTaggedValue>>& keyValue,
769 std::string& myKey, std::string& myValue, int nums)
770 {
771 ObjectFactory *factory = thread->GetEcmaVM()->GetFactory();
772 JSMutableHandle<JSTaggedValue> key(thread, JSTaggedValue::Undefined());
773 JSMutableHandle<JSTaggedValue> value(thread, JSTaggedValue::Undefined());
774
775 // test TaggedTreeMap
776 JSMutableHandle<TaggedTreeMap> tmap(thread, TaggedTreeMap::Create(thread));
777 for (int i = 0; i < nums; i++) {
778 key.Update(JSTaggedValue(i));
779 value.Update(JSTaggedValue(i));
780 tmap.Update(TaggedTreeMap::Set(thread, tmap, key, value));
781 bool success = IsVaildRBTree<TaggedTreeMap>(thread, tmap, tmap->GetRootEntries());
782 EXPECT_TRUE(success);
783 }
784 for (int i = 0; i < nums; i++) {
785 std::string ikey = myKey + std::to_string(i);
786 std::string ivalue = myValue + std::to_string(i);
787 key.Update(factory->NewFromStdString(ikey).GetTaggedValue());
788 value.Update(factory->NewFromStdString(ivalue).GetTaggedValue());
789 tmap.Update(TaggedTreeMap::Set(thread, tmap, key, value));
790 bool success = IsVaildRBTree<TaggedTreeMap>(thread, tmap, tmap->GetRootEntries());
791 EXPECT_TRUE(success);
792 }
793 keyValue.push_back(key);
794 keyValue.push_back(value);
795 return tmap;
796 }
797
SetCommon(JSThread * thread,JSMutableHandle<TaggedTreeSet> & tset,JSMutableHandle<JSTaggedValue> & key,std::string & myKey,int nums)798 void SetCommon(JSThread *thread, JSMutableHandle<TaggedTreeSet>& tset, JSMutableHandle<JSTaggedValue>& key,
799 std::string& myKey, int nums)
800 {
801 ObjectFactory *factory = thread->GetEcmaVM()->GetFactory();
802 for (int i = 0; i < nums; i++) {
803 key.Update(JSTaggedValue(i));
804 tset.Update(TaggedTreeSet::Add(thread, tset, key));
805 bool success = IsVaildRBTree<TaggedTreeSet>(thread, tset, tset->GetRootEntries());
806 EXPECT_TRUE(success);
807 }
808 for (int i = 0; i < nums; i++) {
809 std::string ikey = myKey + std::to_string(i);
810 key.Update(factory->NewFromStdString(ikey).GetTaggedValue());
811 tset.Update(TaggedTreeSet::Add(thread, tset, key));
812 bool success = IsVaildRBTree<TaggedTreeSet>(thread, tset, tset->GetRootEntries());
813 EXPECT_TRUE(success);
814 }
815 }
816
HWTEST_F_L0(TaggedTreeTest,RBTreeAddCheck)817 HWTEST_F_L0(TaggedTreeTest, RBTreeAddCheck)
818 {
819 constexpr int NODE_NUMBERS = 16;
820 std::vector<JSMutableHandle<JSTaggedValue>> keyValue;
821 std::string myKey("mykey");
822 std::string myValue("myvalue");
823 auto tmap = RTCommon(thread, keyValue, myKey, myValue, NODE_NUMBERS);
824 EXPECT_TRUE(tmap->NumberOfElements() == NODE_NUMBERS * 2);
825
826 // test TaggedTreeSet
827 JSMutableHandle<TaggedTreeSet> tset(thread, TaggedTreeSet::Create(thread));
828 SetCommon(thread, tset, keyValue[0], myKey, NODE_NUMBERS);
829 EXPECT_TRUE(tset->NumberOfElements() == NODE_NUMBERS * 2);
830 }
831
HWTEST_F_L0(TaggedTreeTest,RBTreeDeleteCheck)832 HWTEST_F_L0(TaggedTreeTest, RBTreeDeleteCheck)
833 {
834 constexpr int NODE_NUMBERS = 16;
835 std::vector<JSMutableHandle<JSTaggedValue>> keyValue;
836 std::string myKey("mykey");
837 std::string myValue("myvalue");
838
839 // test TaggedTreeMap
840 auto tmap = RTCommon(thread, keyValue, myKey, myValue, NODE_NUMBERS);
841
842 JSMutableHandle<JSTaggedValue> resOfDelete(thread, JSTaggedValue::Undefined());
843 for (int i = 0; i < NODE_NUMBERS; i++) {
844 keyValue[0].Update(JSTaggedValue(i));
845 resOfDelete.Update(TaggedTreeMap::Delete(thread, tmap, TaggedTreeMap::FindEntry(thread, tmap, keyValue[0])));
846 bool success = IsVaildRBTree<TaggedTreeMap>(thread, tmap, tmap->GetRootEntries());
847 EXPECT_TRUE(success);
848 EXPECT_EQ(resOfDelete.GetTaggedValue(), tmap.GetTaggedValue());
849 }
850 EXPECT_TRUE(tmap->NumberOfElements() == NODE_NUMBERS);
851
852 // test TaggedTreeSet
853 JSMutableHandle<TaggedTreeSet> tset(thread, TaggedTreeSet::Create(thread));
854 SetCommon(thread, tset, keyValue[0], myKey, NODE_NUMBERS);
855
856 for (int i = 0; i < NODE_NUMBERS; i++) {
857 keyValue[0].Update(JSTaggedValue(i));
858 resOfDelete.Update(TaggedTreeSet::Delete(thread, tset, TaggedTreeSet::FindEntry(thread, tset, keyValue[0])));
859 bool success = IsVaildRBTree<TaggedTreeSet>(thread, tset, tset->GetRootEntries());
860 EXPECT_TRUE(success);
861 EXPECT_EQ(resOfDelete.GetTaggedValue(), tset.GetTaggedValue());
862 }
863 EXPECT_TRUE(tset->NumberOfElements() == NODE_NUMBERS);
864 }
865
HWTEST_F_L0(TaggedTreeTest,CustomCompareFunctionTest)866 HWTEST_F_L0(TaggedTreeTest, CustomCompareFunctionTest)
867 {
868 ObjectFactory *factory = thread->GetEcmaVM()->GetFactory();
869 constexpr int NODE_NUMBERS = 9;
870 JSMutableHandle<JSTaggedValue> key(thread, JSTaggedValue::Undefined());
871 JSMutableHandle<JSTaggedValue> value(thread, JSTaggedValue::Undefined());
872 std::string myKey("mykey");
873 std::string myValue("myvalue");
874
875 // test TaggedTreeMap
876 JSMutableHandle<TaggedTreeMap> tmap(thread, TaggedTreeMap::Create(thread));
877 JSHandle<GlobalEnv> env = thread->GetEcmaVM()->GetGlobalEnv();
878 JSHandle<JSFunction> func = factory->NewJSFunction(env, reinterpret_cast<void *>(TestClass::TestCompareFunction));
879 tmap->SetCompare(thread, func.GetTaggedValue());
880 for (int i = 0; i < NODE_NUMBERS; i++) {
881 key.Update(JSTaggedValue(i));
882 value.Update(JSTaggedValue(i));
883 tmap.Update(TaggedTreeMap::Set(thread, tmap, key, value));
884 bool success = IsVaildRBTree<TaggedTreeMap>(thread, tmap, tmap->GetRootEntries());
885 EXPECT_TRUE(success);
886 }
887 for (int i = 0; i < NODE_NUMBERS; i++) {
888 std::string ikey = myKey + std::to_string(i);
889 std::string ivalue = myValue + std::to_string(i);
890 key.Update(factory->NewFromStdString(ikey).GetTaggedValue());
891 value.Update(factory->NewFromStdString(ivalue).GetTaggedValue());
892 tmap.Update(TaggedTreeMap::Set(thread, tmap, key, value));
893 bool success = IsVaildRBTree<TaggedTreeMap>(thread, tmap, tmap->GetRootEntries());
894 EXPECT_TRUE(success);
895 }
896 EXPECT_TRUE(tmap->NumberOfElements() == NODE_NUMBERS * 2);
897
898 JSHandle<TaggedArray> arr = TaggedTreeMap::GetArrayFromMap(thread, tmap);
899 EXPECT_EQ(static_cast<int>(arr->GetLength()), NODE_NUMBERS * 2);
900 for (int i = NODE_NUMBERS; i < NODE_NUMBERS * 2; i++) {
901 EXPECT_EQ(tmap->GetKey(arr->Get(i).GetInt()).GetInt(), (NODE_NUMBERS * 2 - 1 - i));
902 }
903 for (int i = 0; i < NODE_NUMBERS; i++) {
904 std::string ikey = myKey + std::to_string(NODE_NUMBERS - 1 - i);
905 key.Update(factory->NewFromStdString(ikey).GetTaggedValue());
906 EXPECT_EQ(tmap->GetKey(arr->Get(i).GetInt()), key.GetTaggedValue());
907 }
908
909 // test TaggedTreeSet
910 JSMutableHandle<TaggedTreeSet> tset(thread, TaggedTreeSet::Create(thread));
911 tset->SetCompare(thread, func.GetTaggedValue());
912 for (int i = 0; i < NODE_NUMBERS; i++) {
913 key.Update(JSTaggedValue(i));
914 tset.Update(TaggedTreeSet::Add(thread, tset, key));
915 bool success = IsVaildRBTree<TaggedTreeSet>(thread, tset, tset->GetRootEntries());
916 EXPECT_TRUE(success);
917 }
918 for (int i = 0; i < NODE_NUMBERS; i++) {
919 std::string ikey = myKey + std::to_string(i);
920 key.Update(factory->NewFromStdString(ikey).GetTaggedValue());
921 tset.Update(TaggedTreeSet::Add(thread, tset, key));
922 bool success = IsVaildRBTree<TaggedTreeSet>(thread, tset, tset->GetRootEntries());
923 EXPECT_TRUE(success);
924 }
925 EXPECT_TRUE(tset->NumberOfElements() == NODE_NUMBERS * 2);
926
927 JSHandle<TaggedArray> sarr = TaggedTreeSet::GetArrayFromSet(thread, tset);
928 EXPECT_EQ(static_cast<int>(arr->GetLength()), NODE_NUMBERS * 2);
929 for (int i = NODE_NUMBERS; i < NODE_NUMBERS * 2; i++) {
930 EXPECT_EQ(tset->GetKey(sarr->Get(i).GetInt()), JSTaggedValue(NODE_NUMBERS * 2 - 1 - i));
931 }
932 for (int i = 0; i < NODE_NUMBERS; i++) {
933 std::string ikey = myKey + std::to_string(NODE_NUMBERS - 1 - i);
934 key.Update(factory->NewFromStdString(ikey).GetTaggedValue());
935 EXPECT_EQ(tset->GetKey(sarr->Get(i).GetInt()), key.GetTaggedValue());
936 }
937 }
938
HWTEST_F_L0(TaggedTreeTest,RBTreeDeleteShrink)939 HWTEST_F_L0(TaggedTreeTest, RBTreeDeleteShrink)
940 {
941 ObjectFactory *factory = thread->GetEcmaVM()->GetFactory();
942 constexpr int NODE_NUMBERS = 32;
943 JSMutableHandle<JSTaggedValue> key(thread, JSTaggedValue::Undefined());
944 JSMutableHandle<JSTaggedValue> value(thread, JSTaggedValue::Undefined());
945 std::string myKey("mykey");
946 std::string myValue("myvalue");
947
948 // test TaggedTreeMap
949 JSMutableHandle<TaggedTreeMap> tmap(thread, TaggedTreeMap::Create(thread));
950 for (int i = 0; i < NODE_NUMBERS; i++) {
951 key.Update(JSTaggedValue(i));
952 value.Update(JSTaggedValue(i));
953 tmap.Update(TaggedTreeMap::Set(thread, tmap, key, value));
954 bool success = IsVaildRBTree<TaggedTreeMap>(thread, tmap, tmap->GetRootEntries());
955 EXPECT_TRUE(success);
956 }
957
958 JSMutableHandle<JSTaggedValue> resOfDelete(thread, JSTaggedValue::Undefined());
959 for (int i = 0; i < NODE_NUMBERS / 2; i++) {
960 key.Update(JSTaggedValue(i));
961 resOfDelete.Update(TaggedTreeMap::Delete(thread, tmap, TaggedTreeMap::FindEntry(thread, tmap, key)));
962 bool success = IsVaildRBTree<TaggedTreeMap>(thread, tmap, tmap->GetRootEntries());
963 EXPECT_TRUE(success);
964 EXPECT_EQ(resOfDelete.GetTaggedValue(), tmap.GetTaggedValue());
965 }
966
967 {
968 EXPECT_EQ(tmap->Capacity(), NODE_NUMBERS * 2 - 1);
969 key.Update(JSTaggedValue(NODE_NUMBERS / 2));
970 resOfDelete.Update(TaggedTreeMap::Delete(thread, tmap, TaggedTreeMap::FindEntry(thread, tmap, key)));
971 EXPECT_NE(resOfDelete.GetTaggedValue(), tmap.GetTaggedValue());
972
973 key.Update(JSTaggedValue(NODE_NUMBERS / 2 + 1));
974 JSHandle<TaggedTreeMap> newMap = JSHandle<TaggedTreeMap>::Cast(resOfDelete);
975 resOfDelete.Update(TaggedTreeMap::Delete(thread, newMap, TaggedTreeMap::FindEntry(thread, newMap, key)));
976 EXPECT_EQ(tmap->NumberOfElements(), NODE_NUMBERS / 2 - 1);
977 EXPECT_EQ(newMap->NumberOfElements(), NODE_NUMBERS / 2 - 2); // 2 means two elements
978 bool success = IsVaildRBTree<TaggedTreeMap>(thread, newMap, newMap->GetRootEntries());
979 EXPECT_TRUE(success);
980 EXPECT_EQ(newMap->Capacity(), NODE_NUMBERS - 1);
981 }
982
983 // test TaggedTreeSet
984 JSMutableHandle<TaggedTreeSet> tset(thread, TaggedTreeSet::Create(thread));
985 for (int i = 0; i < NODE_NUMBERS; i++) {
986 std::string ikey = myKey + std::to_string(i);
987 key.Update(factory->NewFromStdString(ikey).GetTaggedValue());
988 tset.Update(TaggedTreeSet::Add(thread, tset, key));
989 bool success = IsVaildRBTree<TaggedTreeSet>(thread, tset, tset->GetRootEntries());
990 EXPECT_TRUE(success);
991 }
992
993 for (int i = 0; i < NODE_NUMBERS / 2; i++) {
994 std::string ikey = myKey + std::to_string(i);
995 key.Update(factory->NewFromStdString(ikey).GetTaggedValue());
996 resOfDelete.Update(TaggedTreeSet::Delete(thread, tset, TaggedTreeSet::FindEntry(thread, tset, key)));
997 bool success = IsVaildRBTree<TaggedTreeSet>(thread, tset, tset->GetRootEntries());
998 EXPECT_TRUE(success);
999 EXPECT_EQ(resOfDelete.GetTaggedValue(), tset.GetTaggedValue());
1000 }
1001
1002 {
1003 EXPECT_EQ(tset->Capacity(), NODE_NUMBERS * 2 - 1);
1004 std::string ikey = myKey + std::to_string(NODE_NUMBERS / 2);
1005 key.Update(factory->NewFromStdString(ikey).GetTaggedValue());
1006 resOfDelete.Update(TaggedTreeSet::Delete(thread, tset, TaggedTreeSet::FindEntry(thread, tset, key)));
1007 EXPECT_NE(resOfDelete.GetTaggedValue(), tset.GetTaggedValue());
1008
1009 ikey = myKey + std::to_string(NODE_NUMBERS / 2 + 1);
1010 key.Update(factory->NewFromStdString(ikey).GetTaggedValue());
1011 JSHandle<TaggedTreeSet> newSet = JSHandle<TaggedTreeSet>::Cast(resOfDelete);
1012 resOfDelete.Update(TaggedTreeSet::Delete(thread, newSet, TaggedTreeSet::FindEntry(thread, newSet, key)));
1013 EXPECT_EQ(tset->NumberOfElements(), NODE_NUMBERS / 2 - 1);
1014 EXPECT_EQ(newSet->NumberOfElements(), NODE_NUMBERS / 2 - 2);
1015 bool success = IsVaildRBTree<TaggedTreeSet>(thread, newSet, newSet->GetRootEntries());
1016 EXPECT_TRUE(success);
1017 EXPECT_EQ(newSet->Capacity(), NODE_NUMBERS - 1);
1018 }
1019 }
1020 } // namespace panda::test
1021