Line data Source code
1 : /**
2 : Copyright (c) 2017-2022 Roman Katuntsev <sbkarr@stappler.org>
3 : Copyright (c) 2023 Stappler LLC <admin@stappler.dev>
4 :
5 : Permission is hereby granted, free of charge, to any person obtaining a copy
6 : of this software and associated documentation files (the "Software"), to deal
7 : in the Software without restriction, including without limitation the rights
8 : to use, copy, modify, merge, publish, distribute, sublicense, and/or sell
9 : copies of the Software, and to permit persons to whom the Software is
10 : furnished to do so, subject to the following conditions:
11 :
12 : The above copyright notice and this permission notice shall be included in
13 : all copies or substantial portions of the Software.
14 :
15 : THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
16 : IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
17 : FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE
18 : AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
19 : LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM,
20 : OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN
21 : THE SOFTWARE.
22 : **/
23 :
24 : #include "SPMemRbtree.h"
25 : #include "SPMemStringStream.h"
26 :
27 : namespace STAPPLER_VERSIONIZED stappler::memory::rbtree {
28 :
29 19421264 : NodeBase * NodeBase::increment(NodeBase *c) {
30 19421264 : if (c->right) {
31 8811330 : c = c->right;
32 12148950 : while (c->left) {
33 3337620 : c = c->left;
34 : }
35 : } else {
36 10609934 : if (c->parent) {
37 10679968 : if (c->parent->left == c) {
38 6461793 : c = c->parent;
39 : } else {
40 10951566 : while (c->parent && c->parent->right == c) {
41 6733391 : c = c->parent;
42 : }
43 4218175 : if (!c->parent) {
44 0 : return nullptr;
45 : } else {
46 4218175 : c = c->parent;
47 : }
48 : }
49 : } else {
50 0 : return nullptr;
51 : }
52 : }
53 19491298 : return c;
54 : }
55 :
56 209763891 : const NodeBase * NodeBase::increment(const NodeBase *c) {
57 209763891 : if (c->right) {
58 : // move right one step, then left until end
59 90637166 : c = c->right;
60 137912455 : while (c->left) {
61 47275289 : c = c->left;
62 : }
63 : } else {
64 119126725 : if (c->parent) {
65 121214658 : if (c->parent->left == c) {
66 63813863 : c = c->parent;
67 : } else {
68 147753068 : while (c->parent && c->parent->right == c) {
69 90352273 : c = c->parent;
70 : }
71 57400795 : if (!c->parent) {
72 0 : return nullptr; // end of iteration
73 : } else {
74 57400795 : c = c->parent;
75 : }
76 : }
77 : } else {
78 0 : return nullptr;
79 : }
80 : }
81 211851824 : return c;
82 : }
83 :
84 1387527 : NodeBase * NodeBase::decrement(NodeBase *c) {
85 1387527 : if (c->left) {
86 : // move left one step, then right until end
87 702527 : c = c->left;
88 702527 : while (c->right) {
89 0 : c = c->right;
90 : }
91 : } else {
92 685000 : if (c->parent) {
93 689404 : if (c->parent->right == c) {
94 689389 : c = c->parent;
95 : } else {
96 15 : while (c->parent && c->parent->left == c) {
97 0 : c = c->parent;
98 : }
99 15 : if (!c->parent) {
100 0 : return nullptr; // end of iteration
101 : } else {
102 15 : c = c->parent;
103 : }
104 : }
105 : } else {
106 0 : return nullptr;
107 : }
108 : }
109 1391931 : return c;
110 : }
111 :
112 5211530 : const NodeBase * NodeBase::decrement(const NodeBase *c) {
113 5211530 : if (c->left) {
114 : // move left one step, then right until end
115 3396864 : c = c->left;
116 4243671 : while (c->right) {
117 846807 : c = c->right;
118 : }
119 : } else {
120 1814666 : if (c->parent) {
121 1824830 : if (c->parent->right == c) {
122 1373226 : c = c->parent;
123 : } else {
124 1013297 : while (c->parent && c->parent->left == c) {
125 561693 : c = c->parent;
126 : }
127 451604 : if (!c->parent) {
128 0 : return nullptr; // end of iteration
129 : } else {
130 451604 : c = c->parent;
131 : }
132 : }
133 : } else {
134 0 : return nullptr;
135 : }
136 : }
137 5221694 : return c;
138 : }
139 :
140 3373180 : NodeBase *NodeBase::replace(NodeBase *old, NodeBase *n) {
141 3373180 : n->left = old->left;
142 3373180 : n->right = old->right;
143 3373180 : n->setColor(old->getColor());
144 3374332 : n->parent = old->parent;
145 :
146 : // link new with parent
147 3374332 : if (old->parent) {
148 3375913 : if (old->parent->left == old) {
149 2620369 : old->parent->left = n;
150 : } else {
151 755544 : old->parent->right = n;
152 : }
153 : }
154 :
155 : // link new with childs
156 3374332 : if (old->left && old->left != n) {
157 1917804 : old->left->parent = n;
158 1456528 : } else if (old->left == n) {
159 0 : n->left = nullptr;
160 : }
161 3374332 : if (old->right && old->right != n) {
162 2888076 : old->right->parent = n;
163 486256 : } else if (old->right == n) {
164 0 : n->right = nullptr;
165 : }
166 :
167 3374332 : return old;
168 : }
169 :
170 5603878 : void RotateLeft(NodeBase * head, NodeBase * n, NodeBase * p) {
171 5603878 : NodeBase * tmp = n->left;
172 5603878 : if (p == head->left) {
173 1925125 : head->left = n;
174 : } else {
175 3678753 : if (p->parent->right == p) {
176 2214339 : p->parent->right = n;
177 : } else {
178 1464414 : p->parent->left = n;
179 : }
180 : }
181 5603878 : n->parent = p->parent;
182 5603878 : p->parent = n;
183 5603878 : n->left = p;
184 :
185 5603878 : if (tmp) tmp->parent = p;
186 5603878 : p->right = tmp;
187 5603878 : }
188 :
189 3028737 : void RotateRight(NodeBase * head, NodeBase * n, NodeBase * p) {
190 3028737 : NodeBase * tmp = n->right;
191 3028737 : if (p == head->left) {
192 347157 : head->left = n;
193 : } else {
194 2681580 : if (p->parent->right == p) {
195 2059741 : p->parent->right = n;
196 : } else {
197 621839 : p->parent->left = n;
198 : }
199 : }
200 3028737 : n->parent = p->parent;
201 3028737 : p->parent = n;
202 3028737 : n->right = p;
203 :
204 3028737 : if (tmp) tmp->parent = p;
205 3028737 : p->left = tmp;
206 3028737 : }
207 :
208 15058117 : void NodeBase::insert(NodeBase *head, NodeBase * n) {
209 : /* check Red-Black properties */
210 22818948 : while (n != head->left && n->parent->getColor() == NodeColor::Red) {
211 7762906 : auto p = n->parent;
212 7762906 : auto g = n->parent->parent;
213 7762906 : if (p == g->left) {
214 1630328 : NodeBase * u = g->right;
215 1630328 : if (u && u->getColor() == NodeColor::Red) {
216 831552 : p->setColor(NodeColor::Black);
217 831543 : u->setColor(NodeColor::Black);
218 831594 : g->setColor(NodeColor::Red);
219 831614 : n = g;
220 : } else {
221 798761 : if (n == p->right) {
222 300271 : RotateLeft(head, n, p);
223 300276 : n = n->left;
224 300276 : p = n->parent;
225 : }
226 798766 : p->setColor(NodeColor::Black);
227 799160 : g->setColor(NodeColor::Red);
228 799170 : RotateRight(head, p, g);
229 : }
230 : } else {
231 6132578 : NodeBase * u = g->left;
232 6132578 : if (u && u->getColor() == NodeColor::Red) {
233 2242146 : p->setColor(NodeColor::Black);
234 2242139 : u->setColor(NodeColor::Black);
235 2242178 : g->setColor(NodeColor::Red);
236 2242179 : n = g;
237 : } else {
238 3890438 : if (n == n->parent->left) {
239 1063497 : RotateRight(head, n, p);
240 1063541 : n = n->right;
241 1063541 : p = n->parent;
242 : }
243 3890482 : p->setColor(NodeColor::Black);
244 3890648 : g->setColor(NodeColor::Red);
245 3890650 : RotateLeft(head, p, g);
246 : }
247 : }
248 : }
249 15056353 : head->left->setColor(NodeColor::Black); // root
250 15062370 : }
251 :
252 3110182 : void NodeBase::remove(NodeBase *head, NodeBase * n) {
253 3568545 : while (n != head->left && n->getColor() == NodeColor::Black) {
254 2831723 : if (n == n->parent->left) {
255 1750817 : NodeBase *s = n->parent->right;
256 1750817 : if (s && s->getColor() == NodeColor::Red) {
257 163577 : n->parent->setColor(NodeColor::Red);
258 163572 : s->setColor(NodeColor::Black);
259 163572 : RotateLeft(head, s, n->parent);
260 163655 : s = n->parent->right;
261 : }
262 1750903 : if (s) {
263 1750903 : if (s->getColor() == NodeColor::Black
264 1750873 : && (!s->left || s->left->getColor() == NodeColor::Black)
265 3501812 : && (!s->right || s->right->getColor() == NodeColor::Black)) {
266 714893 : s->setColor(NodeColor::Red);
267 714878 : if (s->parent->getColor() == NodeColor::Red) {
268 405516 : s->parent->setColor(NodeColor::Black);
269 405521 : break;
270 : } else {
271 309500 : n = n->parent;
272 : }
273 : } else {
274 1036056 : if ((!s->right || s->right->getColor() == NodeColor::Black) && (s->left && s->left->getColor() == NodeColor::Red)) {
275 488195 : s->setColor(NodeColor::Red);
276 488158 : s->left->setColor(NodeColor::Black);
277 488181 : RotateRight(head, s->left, s);
278 488192 : s = n->parent->right;
279 : }
280 1036042 : s->setColor(n->parent->getColor());
281 1036943 : n->parent->setColor(NodeColor::Black);
282 1037121 : if (s->right) s->right->setColor(NodeColor::Black);
283 1037501 : RotateLeft(head, s, n->parent);
284 1037487 : break;
285 : }
286 : } else {
287 0 : break;
288 : }
289 : } else {
290 1080906 : NodeBase *s = n->parent->left;
291 1080906 : if (s && s->getColor() == NodeColor::Red) {
292 67777 : n->parent->setColor(NodeColor::Red);
293 67774 : s->setColor(NodeColor::Black);
294 67774 : RotateRight(head, s, n->parent);
295 67749 : s = n->parent->left;
296 : }
297 1080904 : if (s) {
298 1080904 : if (s->getColor() == NodeColor::Black
299 1080895 : && (!s->left || s->left->getColor() == NodeColor::Black)
300 2161792 : && (!s->right || s->right->getColor() == NodeColor::Black)) {
301 468718 : s->setColor(NodeColor::Red);
302 468716 : if (s->parent->getColor() == NodeColor::Red) {
303 319885 : s->parent->setColor(NodeColor::Black);
304 319890 : break;
305 : } else {
306 148863 : n = n->parent;
307 : }
308 : } else {
309 612186 : if ((!s->left || s->left->getColor() == NodeColor::Black) && (s->right && s->right->getColor() == NodeColor::Red)) {
310 214254 : s->setColor(NodeColor::Red);
311 214238 : s->right->setColor(NodeColor::Black);
312 214248 : RotateLeft(head, s->right, s);
313 214249 : s = n->parent->left;
314 : }
315 612183 : s->setColor(n->parent->getColor());
316 612367 : n->parent->setColor(NodeColor::Black);
317 612436 : if (s->left) s->left->setColor(NodeColor::Black);
318 612507 : RotateRight(head, s, n->parent);
319 612432 : break;
320 : }
321 : } else {
322 0 : break;
323 : }
324 : }
325 : }
326 3112610 : n->setColor(NodeColor::Black);
327 3113102 : }
328 :
329 : #if SP_MEM_RBTREE_DEBUG
330 :
331 : bool TreeDebug::make_test(std::ostream &ostream, int size) {
332 : apr::rbtree::Tree<int, int> tree_test;
333 : bool valid = true;
334 :
335 : apr::ostringstream stream;
336 : stream << "{ ";
337 : for (int i = 0; i < size; i ++) {
338 : auto val = rand() % 100000;
339 : tree_test.emplace(val);
340 : stream << val << ", ";
341 :
342 : auto v = validate(tree_test);
343 : switch (v) {
344 : case Validation::Valid:
345 : break;
346 : case Validation::RootIsNotBlack:
347 : stream << "\nInsert: Invalid Tree: RootIsNotBlack\n";
348 : visit(tree_test, stream);
349 : valid = false;
350 : break;
351 : case Validation::RedChildIntoRedNode:
352 : stream << "\nInsert: Invalid Tree: RedChildIntoRedNode\n";
353 : visit(tree_test, stream);
354 : valid = false;
355 : break;
356 : case Validation::DifferentBlackNodeCount:
357 : stream << "\nInsert: Invalid Tree: DifferentBlackNodeCount\n";
358 : visit(tree_test, stream);
359 : valid = false;
360 : break;
361 : }
362 : }
363 : stream << "}\nSize: " << tree_test.size() << "\n";
364 :
365 : apr::array<int> arr;
366 : stream << "Sorted: ";
367 : for (auto it = tree_test.begin(); it != tree_test.end(); it ++) {
368 : stream << *it << " ";
369 : arr.emplace_back(*it);
370 : }
371 : stream << "\n";
372 :
373 : if (valid) {
374 : ostream << stream.str();
375 : stream.clear();
376 : }
377 :
378 : auto val = validate(tree_test);
379 : switch (val) {
380 : case Validation::Valid:
381 : stream << "Valid Tree\n";
382 : break;
383 : case Validation::RootIsNotBlack:
384 : stream << "Invalid Tree: RootIsNotBlack\n";
385 : valid = false;
386 : break;
387 : case Validation::RedChildIntoRedNode:
388 : stream << "Invalid Tree: RedChildIntoRedNode\n";
389 : valid = false;
390 : break;
391 : case Validation::DifferentBlackNodeCount:
392 : stream << "Invalid Tree: DifferentBlackNodeCount\n";
393 : valid = false;
394 : break;
395 : }
396 : visit(tree_test, stream);
397 :
398 : auto max = arr.size();
399 : for (size_t i = 0; i < max; i++) {
400 : auto c = rand() % (max - i);
401 :
402 : stream << "erase " << arr[c] << " at " << c << "\n";
403 : tree_test.erase_unique(arr[c]);
404 : arr.erase(arr.begin() + c);
405 :
406 : for (auto it = tree_test.begin(); it != tree_test.end(); it ++) {
407 : stream << *it << " ";
408 : }
409 : stream << "\n";
410 : auto val = validate(tree_test);
411 : switch (val) {
412 : case Validation::Valid:
413 : break;
414 : case Validation::RootIsNotBlack:
415 : stream << "Erase: Invalid Tree: RootIsNotBlack\n";
416 : visit(tree_test, stream);
417 : valid = false;
418 : break;
419 : case Validation::RedChildIntoRedNode:
420 : stream << "Erase: Invalid Tree: RedChildIntoRedNode\n";
421 : visit(tree_test, stream);
422 : valid = false;
423 : break;
424 : case Validation::DifferentBlackNodeCount:
425 : stream << "Erase: Invalid Tree: DifferentBlackNodeCount\n";
426 : visit(tree_test, stream);
427 : valid = false;
428 : break;
429 : }
430 : }
431 :
432 : if (!valid) {
433 : ostream << stream.str();
434 : }
435 :
436 : return valid;
437 : }
438 :
439 : bool TreeDebug::make_test(std::ostream &ostream, const apr::array<int> &data, const apr::array<int> &erase) {
440 : apr::rbtree::Tree<int, int> tree_test;
441 : apr::ostringstream stream;
442 : bool valid = true;
443 :
444 : for (auto &it : data) {
445 : tree_test.emplace(it);
446 : }
447 :
448 : stream << "Sorted: ";
449 : apr::array<int> arr;
450 : for (auto it = tree_test.begin(); it != tree_test.end(); it ++) {
451 : stream << *it << " ";
452 : arr.emplace_back(*it);
453 : }
454 : stream << "\n";
455 :
456 : auto val = validate(tree_test);
457 : switch (val) {
458 : case Validation::Valid:
459 : stream << "Valid Tree\n";
460 : break;
461 : case Validation::RootIsNotBlack:
462 : stream << "Invalid Tree: RootIsNotBlack\n";
463 : valid = false;
464 : break;
465 : case Validation::RedChildIntoRedNode:
466 : stream << "Invalid Tree: RedChildIntoRedNode\n";
467 : valid = false;
468 : break;
469 : case Validation::DifferentBlackNodeCount:
470 : stream << "Invalid Tree: DifferentBlackNodeCount\n";
471 : valid = false;
472 : break;
473 : }
474 : visit(tree_test, stream);
475 :
476 :
477 : for (auto &it : erase) {
478 : tree_test.erase_unique(it);
479 :
480 : val = validate(tree_test);
481 : switch (val) {
482 : case Validation::Valid:
483 : break;
484 : case Validation::RootIsNotBlack:
485 : stream << "Invalid Tree: RootIsNotBlack\n";
486 : visit(tree_test, stream);
487 : valid = false;
488 : break;
489 : case Validation::RedChildIntoRedNode:
490 : stream << "Invalid Tree: RedChildIntoRedNode\n";
491 : visit(tree_test, stream);
492 : valid = false;
493 : break;
494 : case Validation::DifferentBlackNodeCount:
495 : stream << "Invalid Tree: DifferentBlackNodeCount\n";
496 : visit(tree_test, stream);
497 : valid = false;
498 : break;
499 : }
500 : }
501 :
502 : if (!valid) {
503 : ostream << stream.str();
504 : }
505 :
506 : return valid;
507 : }
508 :
509 : bool TreeDebug::make_hint_test(std::ostream &stream, int size) {
510 : Tree<int, int> tree_test1;
511 : auto time_test1_s = std::chrono::system_clock::now();
512 : for(int i = 0; i < size; ++i) {
513 : tree_test1.emplace(i);
514 : }
515 : auto time_test1 = std::chrono::system_clock::now() - time_test1_s;
516 :
517 :
518 : auto time_test2_s = std::chrono::system_clock::now();
519 : Tree<int, int> tree_test2;
520 : auto it2 = tree_test2.begin();
521 : for(int i = 0; i < size; ++i) {
522 : tree_test2.emplace_hint(it2, i);
523 : it2 = tree_test2.end();
524 : }
525 : auto time_test2 = std::chrono::system_clock::now() - time_test2_s;
526 :
527 :
528 : auto time_test3_s = std::chrono::system_clock::now();
529 : Tree<int, int> tree_test3;
530 : auto it3 = tree_test3.begin();
531 : for(int i = size; i > 0; --i) {
532 : tree_test3.emplace_hint(it3, i);
533 : it3 = tree_test3.end();
534 : }
535 : auto time_test3 = std::chrono::system_clock::now() - time_test3_s;
536 :
537 :
538 : auto time_test4_s = std::chrono::system_clock::now();
539 : Tree<int, int> tree_test4;
540 : auto it4 = tree_test4.begin();
541 : for(int i = size; i > 0; --i) {
542 : tree_test4.emplace_hint(it4, i);
543 : it4 = tree_test4.begin();
544 : }
545 : auto time_test4 = std::chrono::system_clock::now() - time_test4_s;
546 :
547 :
548 : auto time_test5_s = std::chrono::system_clock::now();
549 : Tree<int, int> tree_test5;
550 : auto it5 = tree_test5.begin();
551 : for(int i = 0; i < size; ++i) {
552 : it5 = tree_test5.emplace_hint(it5, i);
553 : }
554 : auto time_test5 = std::chrono::system_clock::now() - time_test5_s;
555 :
556 :
557 : stream << std::fixed << std::setprecision(2)
558 : << " time: " << time_test1.count() << " Emplace test: " << validate(tree_test1) << "\n"
559 : << " time: " << time_test2.count() << " Emplace Hint test: " << validate(tree_test2) << "\n"
560 : << " time: " << time_test3.count() << " Emplace Wrong Hint test: " << validate(tree_test3) << "\n"
561 : << " time: " << time_test4.count() << " Emplace Corrected Hint test: " << validate(tree_test4) << "\n"
562 : << " time: " << time_test5.count() << " Emplace Closest Hint test: " << validate(tree_test5) << "\n";
563 :
564 : return true;
565 : }
566 :
567 : #endif
568 :
569 : }
|
