1 /* CO_Tree class implementation.
2 Copyright (C) 2001-2010 Roberto Bagnara <bagnara@cs.unipr.it>
3 Copyright (C) 2010-2016 BUGSENG srl (http://bugseng.com)
4
5 This file is part of the Parma Polyhedra Library (PPL).
6
7 The PPL is free software; you can redistribute it and/or modify it
8 under the terms of the GNU General Public License as published by the
9 Free Software Foundation; either version 3 of the License, or (at your
10 option) any later version.
11
12 The PPL is distributed in the hope that it will be useful, but WITHOUT
13 ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
14 FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License
15 for more details.
16
17 You should have received a copy of the GNU General Public License
18 along with this program; if not, write to the Free Software Foundation,
19 Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02111-1307, USA.
20
21 For the most up-to-date information see the Parma Polyhedra Library
22 site: http://bugseng.com/products/ppl/ . */
23
24 #include "ppl-config.h"
25 #include "CO_Tree_defs.hh"
26
27 namespace PPL = Parma_Polyhedra_Library;
28
29 PPL::dimension_type
external_memory_in_bytes() const30 PPL::CO_Tree::external_memory_in_bytes() const {
31 dimension_type memory_size = 0;
32 if (reserved_size != 0) {
33 // Add the size of data[]
34 memory_size += (reserved_size + 1)*sizeof(data[0]);
35 // Add the size of indexes[]
36 memory_size += (reserved_size + 2)*sizeof(indexes[0]);
37 for (const_iterator itr = begin(), itr_end = end();
38 itr != itr_end; ++itr) {
39 memory_size += PPL::external_memory_in_bytes(*itr);
40 }
41 }
42 return memory_size;
43 }
44
45 PPL::CO_Tree::iterator
insert(iterator itr,dimension_type key1)46 PPL::CO_Tree::insert(iterator itr, dimension_type key1) {
47 PPL_ASSERT(key1 != unused_index);
48
49 if (empty()) {
50 insert_in_empty_tree(key1, Coefficient_zero());
51 return iterator(*this);
52 }
53
54 if (itr == end()) {
55 return insert(key1);
56 }
57
58 iterator candidate1 = bisect_near(itr, key1);
59
60 if (key1 == candidate1.index()) {
61 return candidate1;
62 }
63
64 dimension_type candidate2_index = dfs_index(candidate1);
65
66 if (key1 < candidate1.index()) {
67 --candidate2_index;
68 while (indexes[candidate2_index] == unused_index) {
69 --candidate2_index;
70 }
71 }
72 else {
73 ++candidate2_index;
74 while (indexes[candidate2_index] == unused_index) {
75 ++candidate2_index;
76 }
77 }
78
79 tree_iterator candidate1_node(candidate1, *this);
80
81 PPL_ASSERT(candidate2_index <= reserved_size + 1);
82
83 if (candidate2_index == 0 || candidate2_index > reserved_size) {
84 // Use candidate1
85 return iterator(insert_precise(key1, Coefficient_zero(),
86 candidate1_node));
87 }
88
89 tree_iterator candidate2_node(*this, candidate2_index);
90
91 // Adjacent nodes in an in-order visit of a tree always have different
92 // heights. This fact can be easily proven by induction on the tree's
93 // height, using the definition of the in-order layout.
94 PPL_ASSERT(candidate1_node.get_offset() != candidate2_node.get_offset());
95
96 if (candidate1_node.get_offset() < candidate2_node.get_offset()) {
97 PPL_ASSERT(candidate1_node.depth() > candidate2_node.depth());
98 // candidate1_node is deeper in the tree than candidate2_node, so use
99 // candidate1_node.
100 return iterator(insert_precise(key1, Coefficient_zero(),
101 candidate1_node));
102 }
103 else {
104 PPL_ASSERT(candidate1_node.depth() < candidate2_node.depth());
105 // candidate2_node is deeper in the tree than candidate1_node, so use
106 // candidate2_node.
107 return iterator(insert_precise(key1, Coefficient_zero(),
108 candidate2_node));
109 }
110 }
111
112 PPL::CO_Tree::iterator
insert(iterator itr,dimension_type key1,data_type_const_reference data1)113 PPL::CO_Tree::insert(iterator itr, dimension_type key1,
114 data_type_const_reference data1) {
115 PPL_ASSERT(key1 != unused_index);
116
117 if (empty()) {
118 insert_in_empty_tree(key1, data1);
119 return iterator(*this);
120 }
121
122 if (itr == end()) {
123 return insert(key1, data1);
124 }
125
126 iterator candidate1 = bisect_near(itr, key1);
127
128 if (key1 == candidate1.index()) {
129 *candidate1 = data1;
130 return candidate1;
131 }
132
133 dimension_type candidate2_index = dfs_index(candidate1);
134
135 if (key1 < candidate1.index()) {
136 --candidate2_index;
137 while (indexes[candidate2_index] == unused_index) {
138 --candidate2_index;
139 }
140
141 }
142 else {
143 ++candidate2_index;
144 while (indexes[candidate2_index] == unused_index) {
145 ++candidate2_index;
146 }
147
148 }
149
150 tree_iterator candidate1_node(candidate1, *this);
151
152 if (candidate2_index == 0 || candidate2_index > reserved_size) {
153 // Use candidate1
154 return iterator(insert_precise(key1, data1, candidate1_node));
155 }
156
157 tree_iterator candidate2_node(*this, candidate2_index);
158
159 // Adjacent nodes in an in-order visit of a tree always have different
160 // heights. This fact can be easily proven by induction on the tree's
161 // height, using the definition of the in-order layout.
162 PPL_ASSERT(candidate1_node.get_offset() != candidate2_node.get_offset());
163
164 if (candidate1_node.get_offset() < candidate2_node.get_offset()) {
165 PPL_ASSERT(candidate1_node.depth() > candidate2_node.depth());
166 // candidate1_node is deeper in the tree than candidate2_node, so
167 // use candidate1_node.
168 return iterator(insert_precise(key1, data1, candidate1_node));
169 }
170 else {
171 PPL_ASSERT(candidate1_node.depth() < candidate2_node.depth());
172 // candidate2_node is deeper in the tree than candidate1_node, so
173 // use candidate2_node.
174 return iterator(insert_precise(key1, data1, candidate2_node));
175 }
176 }
177
178 void
erase_element_and_shift_left(dimension_type key)179 PPL::CO_Tree::erase_element_and_shift_left(dimension_type key) {
180 iterator itr = erase(key);
181 if (itr == end()) {
182 return;
183 }
184 const dimension_type i = dfs_index(itr);
185 dimension_type* p = indexes + i;
186 const dimension_type* const p_end = indexes + (reserved_size + 1);
187 for ( ; p != p_end; ++p) {
188 if (*p != unused_index) {
189 --(*p);
190 }
191 }
192 PPL_ASSERT(OK());
193 }
194
195 void
increase_keys_from(dimension_type key,dimension_type n)196 PPL::CO_Tree::increase_keys_from(dimension_type key, dimension_type n) {
197 if (empty()) {
198 return;
199 }
200 dimension_type* p = indexes + reserved_size;
201 while (*p == unused_index) {
202 --p;
203 }
204 while (p != indexes && *p >= key) {
205 *p += n;
206 --p;
207 while (*p == unused_index) {
208 --p;
209 }
210 }
211 PPL_ASSERT(OK());
212 }
213
214 PPL::dimension_type
bisect_in(dimension_type first,dimension_type last,dimension_type key) const215 PPL::CO_Tree::bisect_in(dimension_type first, dimension_type last,
216 dimension_type key) const {
217 PPL_ASSERT(first != 0);
218 PPL_ASSERT(last <= reserved_size);
219 PPL_ASSERT(first <= last);
220 PPL_ASSERT(indexes[first] != unused_index);
221 PPL_ASSERT(indexes[last] != unused_index);
222
223 while (first < last) {
224 dimension_type half = (first + last) / 2;
225 dimension_type new_half = half;
226
227 while (indexes[new_half] == unused_index) {
228 ++new_half;
229 }
230
231 if (indexes[new_half] == key) {
232 return new_half;
233 }
234
235 if (indexes[new_half] > key) {
236
237 while (indexes[half] == unused_index) {
238 --half;
239 }
240
241 last = half;
242
243 }
244 else {
245
246 ++new_half;
247 while (indexes[new_half] == unused_index) {
248 ++new_half;
249 }
250
251 first = new_half;
252 }
253 }
254
255 // It is important that last is returned instead of first, because first
256 // may have increased beyond last, even beyond the original value of last
257 // at the beginning of this method.
258 return last;
259 }
260
261 PPL::dimension_type
bisect_near(dimension_type hint,dimension_type key) const262 PPL::CO_Tree::bisect_near(dimension_type hint, dimension_type key) const {
263 PPL_ASSERT(hint != 0);
264 PPL_ASSERT(hint <= reserved_size);
265 PPL_ASSERT(indexes[hint] != unused_index);
266
267 if (indexes[hint] == key) {
268 return hint;
269 }
270
271 dimension_type new_hint;
272 dimension_type offset = 1;
273
274 if (indexes[hint] > key) {
275 // The searched element is before `hint'.
276
277 while (true) {
278
279 if (hint <= offset) {
280 // The searched element is in (0,hint).
281 new_hint = hint;
282 hint = 1;
283 // The searched element is in [hint,new_hint).
284 while (indexes[hint] == unused_index) {
285 ++hint;
286 }
287
288 if (indexes[hint] >= key) {
289 return hint;
290 }
291 // The searched element is in (hint,new_hint) and both indexes point
292 // to valid elements.
293 break;
294 }
295 else {
296 new_hint = hint - offset;
297 }
298
299 PPL_ASSERT(new_hint > 0);
300 PPL_ASSERT(new_hint <= reserved_size);
301
302 // Find the element at `new_hint' (or the first after it).
303 while (indexes[new_hint] == unused_index) {
304 ++new_hint;
305 }
306
307 PPL_ASSERT(new_hint <= hint);
308
309 if (indexes[new_hint] == key) {
310 return new_hint;
311 }
312 else
313 if (indexes[new_hint] < key) {
314 // The searched element is in (new_hint,hint)
315 using std::swap;
316 swap(hint, new_hint);
317 // The searched element is now in (hint,new_hint).
318 break;
319 }
320
321 hint = new_hint;
322 offset *= 2;
323 }
324
325 }
326 else {
327 // The searched element is after `hint'.
328 while (true) {
329
330 if (hint + offset > reserved_size) {
331 // The searched element is in (hint,reserved_size+1).
332 new_hint = reserved_size;
333 // The searched element is in (hint,new_hint].
334 while (indexes[new_hint] == unused_index) {
335 --new_hint;
336 }
337 if (indexes[new_hint] <= key) {
338 return new_hint;
339 }
340 // The searched element is in (hint,new_hint) and both indexes point
341 // to valid elements.
342 break;
343 }
344 else {
345 new_hint = hint + offset;
346 }
347
348 PPL_ASSERT(new_hint > 0);
349 PPL_ASSERT(new_hint <= reserved_size);
350
351 // Find the element at `new_hint' (or the first after it).
352 while (indexes[new_hint] == unused_index) {
353 --new_hint;
354 }
355
356 PPL_ASSERT(hint <= new_hint);
357
358 if (indexes[new_hint] == key) {
359 return new_hint;
360 }
361 else {
362 if (indexes[new_hint] > key) {
363 // The searched element is in (hint,new_hint).
364 break;
365 }
366 }
367 hint = new_hint;
368 offset *= 2;
369 }
370 }
371 // The searched element is in (hint,new_hint).
372 PPL_ASSERT(hint > 0);
373 PPL_ASSERT(hint < new_hint);
374 PPL_ASSERT(new_hint <= reserved_size);
375 PPL_ASSERT(indexes[hint] != unused_index);
376 PPL_ASSERT(indexes[new_hint] != unused_index);
377
378 ++hint;
379 while (indexes[hint] == unused_index) {
380 ++hint;
381 }
382
383 if (hint == new_hint) {
384 return hint;
385 }
386
387 --new_hint;
388
389 while (indexes[new_hint] == unused_index) {
390 --new_hint;
391 }
392
393 PPL_ASSERT(hint <= new_hint);
394 PPL_ASSERT(indexes[hint] != unused_index);
395 PPL_ASSERT(indexes[new_hint] != unused_index);
396
397 return bisect_in(hint, new_hint, key);
398 }
399
400 PPL::CO_Tree::tree_iterator
insert_precise(dimension_type key1,data_type_const_reference data1,tree_iterator itr)401 PPL::CO_Tree::insert_precise(dimension_type key1,
402 data_type_const_reference data1,
403 tree_iterator itr) {
404 PPL_ASSERT(key1 != unused_index);
405 PPL_ASSERT(!empty());
406
407 #ifndef NDEBUG
408 // Check that `itr' is a correct hint.
409 tree_iterator itr2(*this);
410 itr2.go_down_searching_key(key1);
411 PPL_ASSERT(itr == itr2);
412 #endif
413
414 if (itr.index() == key1) {
415 // Replacement, rather than insertion.
416 *itr = data1;
417 PPL_ASSERT(OK());
418 return itr;
419 }
420
421 // Proper insertion: check if it would invalidate `data1'.
422 const bool invalidating
423 = (data <= &data1) && (&data1 < data + (reserved_size + 1));
424
425 if (!invalidating) {
426 return insert_precise_aux(key1, data1, itr);
427 }
428 // `data1' could be invalidated by the insert, because it is
429 // a coefficient of this row. Avoid the issue by copying it.
430 data_type data1_copy = data1;
431
432 #ifndef NDEBUG
433 dimension_type i = &data1 - data;
434 dimension_type key2 = indexes[i];
435 PPL_ASSERT(key2 != unused_index);
436 // This is true since `key1' is not in the tree.
437 PPL_ASSERT(key2 != key1);
438 #endif
439
440 // Insert a dummy coefficient.
441 // NOTE: this may invalidate `data1', because it may reallocate the tree
442 // and/or move coefficients during rebalancing.
443 itr = insert_precise_aux(key1, Coefficient_zero(), itr);
444
445 PPL_ASSERT(itr.index() == key1);
446
447 // Swap the correct coefficient in place.
448 using std::swap;
449 swap(*itr, data1_copy);
450
451 PPL_ASSERT(OK());
452 return itr;
453 }
454
455 PPL::CO_Tree::tree_iterator
insert_precise_aux(dimension_type key1,data_type_const_reference data1,tree_iterator itr)456 PPL::CO_Tree::insert_precise_aux(dimension_type key1,
457 data_type_const_reference data1,
458 tree_iterator itr) {
459 PPL_ASSERT(key1 != unused_index);
460 PPL_ASSERT(!empty());
461 // This is a proper insert.
462 PPL_ASSERT(itr.index() != key1);
463 // `data1' is not going to be invalidated.
464 PPL_ASSERT(!(data <= &data1 && &data1 < data + (reserved_size + 1)));
465
466 if (is_greater_than_ratio(size_ + 1, reserved_size, max_density_percent)) {
467 rebuild_bigger_tree();
468 // `itr' was invalidated by the rebuild operation
469 itr.get_root();
470 itr.go_down_searching_key(key1);
471 PPL_ASSERT(itr.index() != key1);
472 }
473
474 PPL_ASSERT(!is_greater_than_ratio(size_ + 1, reserved_size,
475 max_density_percent));
476
477 ++size_;
478
479 if (!itr.is_leaf()) {
480 if (key1 < itr.index()) {
481 itr.get_left_child();
482 }
483 else {
484 itr.get_right_child();
485 }
486 PPL_ASSERT(itr.index() == unused_index);
487
488 new(&(*itr)) data_type(data1);
489 // Set the index only if the construction was successful.
490 itr.index() = key1;
491 }
492 else {
493 itr = rebalance(itr, key1, data1);
494 itr.go_down_searching_key(key1);
495 PPL_ASSERT(itr.index() == key1);
496 }
497 PPL_ASSERT(OK());
498
499 return itr;
500 }
501
502 PPL::CO_Tree::iterator
erase(tree_iterator itr)503 PPL::CO_Tree::erase(tree_iterator itr) {
504 PPL_ASSERT(itr.index() != unused_index);
505
506 PPL_ASSERT(size_ != 0);
507
508 if (size_ == 1) {
509 // Deleting the only element of this tree, now it is empty.
510 clear();
511 return end();
512 }
513
514 if (is_less_than_ratio(size_ - 1, reserved_size, min_density_percent)
515 && !is_greater_than_ratio(size_ - 1, reserved_size/2,
516 max_density_percent)) {
517
518 const dimension_type key = itr.index();
519
520 PPL_ASSERT(!is_greater_than_ratio(size_, reserved_size,
521 max_density_percent));
522
523 rebuild_smaller_tree();
524 itr.get_root();
525 itr.go_down_searching_key(key);
526
527 PPL_ASSERT(itr.index() == key);
528 }
529
530 #ifndef NDEBUG
531 if (size_ > 1) {
532 PPL_ASSERT(!is_less_than_ratio(size_ - 1, reserved_size,
533 min_density_percent)
534 || is_greater_than_ratio(size_ - 1, reserved_size/2,
535 max_density_percent));
536 }
537 #endif
538
539 const dimension_type deleted_key = itr.index();
540 tree_iterator deleted_node = itr;
541 (*itr).~data_type();
542 while (true) {
543 dimension_type& current_key = itr.index();
544 data_type& current_data = *itr;
545 if (itr.is_leaf()) {
546 break;
547 }
548 itr.get_left_child();
549 if (itr.index() != unused_index) {
550 // The left child has a value.
551 itr.follow_right_children_with_value();
552 }
553 else {
554 // The left child has not a value, try the right child.
555 itr.get_parent();
556 itr.get_right_child();
557 if (itr.index() != unused_index) {
558 // The right child has a value.
559 itr.follow_left_children_with_value();
560 }
561 else {
562 // The right child has not a value, too.
563 itr.get_parent();
564 break;
565 }
566 }
567 using std::swap;
568 swap(current_key, itr.index());
569 move_data_element(current_data, *itr);
570 }
571
572 PPL_ASSERT(itr.index() != unused_index);
573 itr.index() = unused_index;
574 --size_;
575
576 PPL_ASSERT(OK());
577
578 itr = rebalance(itr, 0, Coefficient_zero());
579
580 if (itr.get_offset() < deleted_node.get_offset()) {
581 // deleted_node is an ancestor of itr
582 itr = deleted_node;
583 }
584
585 itr.go_down_searching_key(deleted_key);
586
587 iterator result(itr);
588
589 if (result.index() < deleted_key) {
590 ++result;
591 }
592
593 PPL_ASSERT(OK());
594 PPL_ASSERT(result == end() || result.index() > deleted_key);
595 #ifndef NDEBUG
596 if (!empty()) {
597 iterator last = end();
598 --last;
599 PPL_ASSERT((result == end()) == (last.index() < deleted_key));
600 }
601 #endif
602
603 return result;
604 }
605
606 void
init(dimension_type n)607 PPL::CO_Tree::init(dimension_type n) {
608 indexes = NULL;
609 data = NULL;
610 size_ = 0;
611 reserved_size = 0;
612 max_depth = 0;
613
614 if (n > 0) {
615 const dimension_type max_d = integer_log2(n) + 1;
616 const height_t new_max_depth = static_cast<height_t>(max_d);
617 const dimension_type new_reserved_size
618 = (static_cast<dimension_type>(1) << new_max_depth) - 1;
619 // If this throws, *this will be the empty tree.
620 indexes = new dimension_type[new_reserved_size + 2];
621 try {
622 data = data_allocator.allocate(new_reserved_size + 1);
623 }
624 catch (...) {
625 delete[] indexes;
626 indexes = 0;
627 PPL_ASSERT(OK());
628 throw;
629 }
630 max_depth = new_max_depth;
631 reserved_size = new_reserved_size;
632
633 // Mark all pairs as unused.
634 for (dimension_type i = 1; i <= reserved_size; ++i) {
635 indexes[i] = unused_index;
636 }
637
638 // These are used as markers by iterators.
639 indexes[0] = 0;
640 indexes[reserved_size + 1] = 0;
641 }
642
643 refresh_cached_iterators();
644
645 PPL_ASSERT(structure_OK());
646 }
647
648 void
destroy()649 PPL::CO_Tree::destroy() {
650
651 if (reserved_size != 0) {
652 for (dimension_type i = 1; i <= reserved_size; ++i) {
653 if (indexes[i] != unused_index) {
654 data[i].~data_type();
655 }
656 }
657
658 delete[] indexes;
659 data_allocator.deallocate(data, reserved_size + 1);
660 }
661 }
662
663 bool
structure_OK() const664 PPL::CO_Tree::structure_OK() const {
665
666 if (size_ > reserved_size) {
667 return false;
668 }
669
670 if (reserved_size == 0) {
671 if (indexes != NULL) {
672 return false;
673 }
674 if (data != NULL) {
675 return false;
676 }
677 if (max_depth != 0) {
678 return false;
679 }
680
681 return true;
682 }
683
684 if (reserved_size < 3) {
685 return false;
686 }
687 if (reserved_size != (static_cast<dimension_type>(1) << max_depth) - 1) {
688 return false;
689 }
690
691 if (data == NULL) {
692 return false;
693 }
694
695 if (indexes == NULL) {
696 return false;
697 }
698
699 if (max_depth == 0) {
700 return false;
701 }
702
703 if (size_ == 0) {
704
705 // This const_cast could be removed by adding a const_tree_iterator,
706 // but it would add much code duplication without a real need.
707 tree_iterator itr(*const_cast<CO_Tree*>(this));
708 if (itr.index() != unused_index) {
709 return false;
710 }
711
712 }
713 else {
714 // This const_cast could be removed by adding a const_tree_iterator,
715 // but it would add much code duplication without a real need.
716 tree_iterator itr(*const_cast<CO_Tree*>(this));
717 const dimension_type real_size = count_used_in_subtree(itr);
718 if (real_size != size_) {
719 // There are \p real_size elements in the tree that are reachable by the
720 // root, but size is \p size.
721 return false;
722 }
723 }
724
725 if (size_ != 0) {
726 const_iterator itr = begin();
727 const_iterator itr_end = end();
728
729 if (itr != itr_end) {
730 dimension_type last_index = itr.index();
731 for (++itr; itr != itr_end; ++itr) {
732 if (last_index >= itr.index()) {
733 // Found index \p itr->first after index \p last_index.
734 return false;
735 }
736 last_index = itr.index();
737 }
738 }
739 }
740
741 if (const_iterator(cached_end) != const_iterator(*this, reserved_size + 1)) {
742 return false;
743 }
744 if (cached_const_end != const_iterator(*this, reserved_size + 1)) {
745 return false;
746 }
747
748 return true;
749 }
750
751 bool
OK() const752 PPL::CO_Tree::OK() const {
753
754 if (!structure_OK()) {
755 return false;
756 }
757 {
758 dimension_type real_size = 0;
759
760 for (const_iterator itr = begin(), itr_end = end(); itr != itr_end; ++itr) {
761 ++real_size;
762 }
763
764 if (real_size != size_) {
765 // There are \p real_size elements in the tree, but size is \p size.
766 return false;
767 }
768 }
769
770 if (reserved_size > 0) {
771 if (is_greater_than_ratio(size_, reserved_size, max_density_percent)
772 && reserved_size != 3) {
773 // Found too high density.
774 return false;
775 }
776 if (is_less_than_ratio(size_, reserved_size, min_density_percent)
777 && !is_greater_than_ratio(size_, reserved_size/2, max_density_percent)) {
778 // Found too low density
779 return false;
780 }
781 }
782
783 return true;
784 }
785
786 unsigned
integer_log2(dimension_type n)787 PPL::CO_Tree::integer_log2(dimension_type n) {
788 PPL_ASSERT(n != 0);
789 unsigned result = 0;
790 while (n != 1) {
791 n /= 2;
792 ++result;
793 }
794 return result;
795 }
796
797 void
dump_subtree(tree_iterator itr)798 PPL::CO_Tree::dump_subtree(tree_iterator itr) {
799 if (!itr.is_leaf()) {
800 itr.get_left_child();
801 dump_subtree(itr);
802 itr.get_parent();
803 }
804 std::cout << "At depth: " << itr.depth();
805 if (itr.index() == unused_index) {
806 std::cout << " (no data)" << std::endl;
807 }
808 else {
809 std::cout << " pair (" << itr.index() << "," << *itr << ")" << std::endl;
810 }
811 if (!itr.is_leaf()) {
812 itr.get_right_child();
813 dump_subtree(itr);
814 itr.get_parent();
815 }
816 }
817
818 void
rebuild_bigger_tree()819 PPL::CO_Tree::rebuild_bigger_tree() {
820 if (reserved_size == 0) {
821 init(3);
822 PPL_ASSERT(structure_OK());
823 return;
824 }
825
826 const dimension_type new_reserved_size = reserved_size*2 + 1;
827
828 dimension_type* const new_indexes = new dimension_type[new_reserved_size + 2];
829
830 data_type* new_data;
831
832 try {
833 new_data = data_allocator.allocate(new_reserved_size + 1);
834 } catch (...) {
835 delete[] new_indexes;
836 throw;
837 }
838
839 new_indexes[1] = unused_index;
840
841 for (dimension_type i = 1, j = 2; i <= reserved_size; ++i, ++j) {
842 new_indexes[j] = indexes[i];
843 if (indexes[i] != unused_index) {
844 move_data_element(new_data[j], data[i]);
845 }
846 ++j;
847 new_indexes[j] = unused_index;
848 }
849
850 // These are used as markers by iterators.
851 new_indexes[0] = 0;
852 new_indexes[new_reserved_size + 1] = 0;
853
854 delete[] indexes;
855 data_allocator.deallocate(data, reserved_size + 1);
856
857 indexes = new_indexes;
858 data = new_data;
859 reserved_size = new_reserved_size;
860 ++max_depth;
861
862 refresh_cached_iterators();
863
864 PPL_ASSERT(structure_OK());
865 }
866
867 PPL::CO_Tree::tree_iterator
rebalance(tree_iterator itr,dimension_type key,data_type_const_reference value)868 PPL::CO_Tree::rebalance(tree_iterator itr, dimension_type key,
869 data_type_const_reference value) {
870 // Trees with reserved size 3 need not to be rebalanced.
871 // This check is needed because they can't be shrunk, so they may violate
872 // the density thresholds, and this would prevent the following while from
873 // working correctly.
874 if (reserved_size == 3) {
875 PPL_ASSERT(OK());
876 return tree_iterator(*this);
877 }
878 PPL_ASSERT(itr.index() == unused_index || itr.is_leaf());
879 height_t itr_depth_minus_1 = itr.depth() - 1;
880 const height_t height = max_depth - itr_depth_minus_1;
881 dimension_type subtree_size;
882 dimension_type subtree_reserved_size = (static_cast<dimension_type>(1)
883 << height) - 1;
884 const bool deleting = itr.index() == unused_index;
885 PPL_ASSERT(deleting || key != unused_index);
886 if (deleting) {
887 subtree_size = 0;
888 }
889 else {
890 // The existing element and the element with index key we want to add.
891 subtree_size = 2;
892 }
893
894 while (is_greater_than_ratio(subtree_size, subtree_reserved_size,
895 max_density_percent
896 + ((itr_depth_minus_1
897 * (100 - max_density_percent))
898 / (max_depth - 1)))
899 || is_less_than_ratio(subtree_size, subtree_reserved_size,
900 min_density_percent
901 - ((itr_depth_minus_1
902 * (min_density_percent
903 - min_leaf_density_percent))
904 / (max_depth - 1)))) {
905 // The density in the tree is correct, so the while condition is always
906 // false for the root.
907 PPL_ASSERT(itr_depth_minus_1 != 0);
908 const bool is_right_brother = itr.is_right_child();
909 itr.get_parent();
910 if (is_right_brother) {
911 itr.get_left_child();
912 }
913 else {
914 itr.get_right_child();
915 }
916 subtree_size += count_used_in_subtree(itr);
917 itr.get_parent();
918 PPL_ASSERT(itr.index() != unused_index);
919 ++subtree_size;
920 subtree_reserved_size = 2*subtree_reserved_size + 1;
921 --itr_depth_minus_1;
922 PPL_ASSERT(itr.depth() - 1 == itr_depth_minus_1);
923 }
924
925 // Now the subtree rooted at itr has been chosen as the subtree to be
926 // rebalanced.
927
928 // Step 1: compact elements of this subtree in the rightmost end, from right
929 // to left.
930 const dimension_type last_index_in_subtree
931 = itr.dfs_index() + itr.get_offset() - 1;
932
933 const dimension_type first_unused
934 = compact_elements_in_the_rightmost_end(last_index_in_subtree,
935 subtree_size, key, value,
936 !deleting);
937
938 // Step 2: redistribute the elements, from left to right.
939 redistribute_elements_in_subtree(itr.dfs_index(), subtree_size,
940 first_unused + 1, key, value,
941 first_unused != last_index_in_subtree
942 - subtree_size);
943
944 PPL_ASSERT(OK());
945
946 return itr;
947 }
948
949 PPL::dimension_type
950 PPL::CO_Tree
compact_elements_in_the_rightmost_end(dimension_type last_in_subtree,dimension_type subtree_size,dimension_type key,data_type_const_reference value,bool add_element)951 ::compact_elements_in_the_rightmost_end(dimension_type last_in_subtree,
952 dimension_type subtree_size,
953 dimension_type key,
954 data_type_const_reference value,
955 bool add_element) {
956
957 PPL_ASSERT(subtree_size != 0);
958
959 PPL_ASSERT(subtree_size != 1 || !add_element);
960
961 dimension_type* last_index_in_subtree = &(indexes[last_in_subtree]);
962 data_type* last_data_in_subtree = &(data[last_in_subtree]);
963
964 dimension_type* first_unused_index = last_index_in_subtree;
965 data_type* first_unused_data = last_data_in_subtree;
966
967 while (*last_index_in_subtree == unused_index) {
968 --last_index_in_subtree;
969 --last_data_in_subtree;
970 }
971
972 // From now on, last_index_in_subtree and last_data_in_subtree point to the
973 // rightmost node with a value in the subtree. first_unused_index and
974 // first_unused_data point to the rightmost unused node in the subtree.
975
976 if (add_element) {
977 while (subtree_size != 0) {
978 --subtree_size;
979 if (last_index_in_subtree == indexes || key > *last_index_in_subtree) {
980 if (last_index_in_subtree == indexes
981 || last_index_in_subtree != first_unused_index) {
982 PPL_ASSERT(first_unused_index != indexes);
983 PPL_ASSERT(*first_unused_index == unused_index);
984 new(first_unused_data) data_type(value);
985 // Set the index only if the construction was successful.
986 *first_unused_index = key;
987 --first_unused_index;
988 --first_unused_data;
989 }
990 break;
991 }
992 else {
993 if (last_index_in_subtree != first_unused_index) {
994 PPL_ASSERT(first_unused_index != indexes);
995 PPL_ASSERT(last_index_in_subtree != indexes);
996 PPL_ASSERT(*first_unused_index == unused_index);
997 *first_unused_index = *last_index_in_subtree;
998 *last_index_in_subtree = unused_index;
999 move_data_element(*first_unused_data, *last_data_in_subtree);
1000 }
1001 --last_index_in_subtree;
1002 --last_data_in_subtree;
1003 while (*last_index_in_subtree == unused_index) {
1004 --last_index_in_subtree;
1005 --last_data_in_subtree;
1006 }
1007 --first_unused_index;
1008 --first_unused_data;
1009 }
1010 }
1011 }
1012 while (subtree_size != 0) {
1013 if (last_index_in_subtree != first_unused_index) {
1014 PPL_ASSERT(first_unused_index != indexes);
1015 PPL_ASSERT(last_index_in_subtree != indexes);
1016 PPL_ASSERT(*first_unused_index == unused_index);
1017 *first_unused_index = *last_index_in_subtree;
1018 *last_index_in_subtree = unused_index;
1019 move_data_element(*first_unused_data, *last_data_in_subtree);
1020 }
1021 --last_index_in_subtree;
1022 --last_data_in_subtree;
1023 while (*last_index_in_subtree == unused_index) {
1024 --last_index_in_subtree;
1025 --last_data_in_subtree;
1026 }
1027 --first_unused_index;
1028 --first_unused_data;
1029 --subtree_size;
1030 }
1031
1032 const std::ptrdiff_t distance = first_unused_index - indexes;
1033 PPL_ASSERT(distance >= 0);
1034 return static_cast<dimension_type>(distance);
1035 }
1036
1037 void
redistribute_elements_in_subtree(dimension_type root_index,dimension_type subtree_size,dimension_type last_used,dimension_type key,data_type_const_reference value,bool add_element)1038 PPL::CO_Tree::redistribute_elements_in_subtree(
1039 dimension_type root_index,
1040 dimension_type subtree_size,
1041 dimension_type last_used,
1042 dimension_type key,
1043 data_type_const_reference value,
1044 bool add_element) {
1045
1046 // This is static and with static allocation, to improve performance.
1047 // sizeof_to_bits(sizeof(dimension_type)) is the maximum k such that
1048 // 2^k-1 is a dimension_type, so it is the maximum tree height.
1049 // For each node level, the stack may contain up to two element (one for the
1050 // subtree rooted at the right son of a node of that level, and one for the
1051 // node itself). An additional element can be at the top of the tree.
1052 static std::pair<dimension_type,dimension_type>
1053 stack[2U * sizeof_to_bits(sizeof(dimension_type)) + 1U];
1054
1055 std::pair<dimension_type,dimension_type>* stack_first_empty = stack;
1056
1057 // A pair (n, i) in the stack means to visit the subtree with root index i
1058 // and size n.
1059
1060 PPL_ASSERT(subtree_size != 0);
1061
1062 stack_first_empty->first = subtree_size;
1063 stack_first_empty->second = root_index;
1064 ++stack_first_empty;
1065
1066 while (stack_first_empty != stack) {
1067
1068 --stack_first_empty;
1069
1070 // Implement
1071 //
1072 // <CODE>
1073 // top_n = stack.top().first;
1074 // top_i = stack.top().second;
1075 // </CODE>
1076 const dimension_type top_n = stack_first_empty->first;
1077 const dimension_type top_i = stack_first_empty->second;
1078
1079 PPL_ASSERT(top_n != 0);
1080 if (top_n == 1) {
1081 if (add_element
1082 && (last_used > reserved_size || indexes[last_used] > key)) {
1083 PPL_ASSERT(last_used != top_i);
1084 PPL_ASSERT(indexes[top_i] == unused_index);
1085 add_element = false;
1086 new(&(data[top_i])) data_type(value);
1087 // Set the index only if the construction was successful.
1088 indexes[top_i] = key;
1089 }
1090 else {
1091 if (last_used != top_i) {
1092 PPL_ASSERT(indexes[top_i] == unused_index);
1093 indexes[top_i] = indexes[last_used];
1094 indexes[last_used] = unused_index;
1095 move_data_element(data[top_i], data[last_used]);
1096 }
1097 ++last_used;
1098 }
1099 }
1100 else {
1101 PPL_ASSERT(stack_first_empty + 2
1102 < stack + sizeof(stack)/sizeof(stack[0]));
1103
1104 const dimension_type offset = (top_i & -top_i) / 2;
1105 const dimension_type half = (top_n + 1) / 2;
1106
1107 PPL_ASSERT(half > 0);
1108
1109 // Right subtree
1110 PPL_ASSERT(top_n - half > 0);
1111 stack_first_empty->first = top_n - half;
1112 stack_first_empty->second = top_i + offset;
1113 ++stack_first_empty;
1114
1115 // Root of the current subtree
1116 stack_first_empty->first = 1;
1117 stack_first_empty->second = top_i;
1118 ++stack_first_empty;
1119
1120 // Left subtree
1121 if (half - 1 != 0) {
1122 stack_first_empty->first = half - 1;
1123 stack_first_empty->second = top_i - offset;
1124 ++stack_first_empty;
1125 }
1126 }
1127 }
1128
1129 PPL_ASSERT(!add_element);
1130 }
1131
1132 void
move_data_from(CO_Tree & tree)1133 PPL::CO_Tree::move_data_from(CO_Tree& tree) {
1134 PPL_ASSERT(size_ == 0);
1135 if (tree.size_ == 0) {
1136 return;
1137 }
1138
1139 tree_iterator root(*this);
1140
1141 dimension_type source_index = 1;
1142 while (tree.indexes[source_index] == unused_index) {
1143 ++source_index;
1144 }
1145
1146 // This is static and with static allocation, to improve performance.
1147 // sizeof_to_bits(sizeof(dimension_type)) is the maximum k such that 2^k-1 is a
1148 // dimension_type, so it is the maximum tree height.
1149 // For each node level, the stack may contain up to 4 elements: two elements
1150 // with operation 0, one element with operation 2 and one element
1151 // with operation 3. An additional element with operation 1 can be at the
1152 // top of the tree.
1153 static std::pair<dimension_type, signed char>
1154 stack[5U * sizeof_to_bits(sizeof(dimension_type))];
1155
1156 dimension_type stack_first_empty = 0;
1157
1158 // A pair (n, operation) in the stack means:
1159 //
1160 // * Go to the parent, if operation is 0.
1161 // * Go to the left child, then visit the current tree (with size n), if
1162 // operation is 1.
1163 // * Go to the right child, then visit the current tree (with size n), if
1164 // operation is 2.
1165 // * Visit the current tree (with size n), if operation is 3.
1166
1167 stack[0].first = tree.size_;
1168 stack[0].second = 3;
1169 ++stack_first_empty;
1170
1171 while (stack_first_empty != 0) {
1172
1173 // Implement
1174 //
1175 // <CODE>
1176 // top_n = stack.top().first;
1177 // top_operation = stack.top().second;
1178 // </CODE>
1179 const dimension_type top_n = stack[stack_first_empty - 1].first;
1180 const signed char top_operation = stack[stack_first_empty - 1].second;
1181
1182 switch (top_operation) {
1183
1184 case 0:
1185 root.get_parent();
1186 --stack_first_empty;
1187 continue;
1188
1189 case 1:
1190 root.get_left_child();
1191 break;
1192
1193 case 2:
1194 root.get_right_child();
1195 break;
1196
1197 #ifndef NDEBUG
1198 case 3:
1199 break;
1200
1201 default:
1202 PPL_UNREACHABLE;
1203 break;
1204 #endif
1205 }
1206
1207 // We now visit the current tree
1208
1209 if (top_n == 0) {
1210 --stack_first_empty;
1211 }
1212 else {
1213 if (top_n == 1) {
1214 PPL_ASSERT(root.index() == unused_index);
1215 PPL_ASSERT(tree.indexes[source_index] != unused_index);
1216 root.index() = tree.indexes[source_index];
1217 tree.indexes[source_index] = unused_index;
1218 move_data_element(*root, tree.data[source_index]);
1219 PPL_ASSERT(source_index <= tree.reserved_size);
1220 ++source_index;
1221 while (tree.indexes[source_index] == unused_index) {
1222 ++source_index;
1223 }
1224 --stack_first_empty;
1225 }
1226 else {
1227 PPL_ASSERT(stack_first_empty + 3 < sizeof(stack)/sizeof(stack[0]));
1228
1229 const dimension_type half = (top_n + 1) / 2;
1230 stack[stack_first_empty - 1].second = 0;
1231 stack[stack_first_empty ] = std::make_pair(top_n - half, 2);
1232 stack[stack_first_empty + 1] = std::make_pair(1, 3);
1233 stack[stack_first_empty + 2].second = 0;
1234 stack[stack_first_empty + 3] = std::make_pair(half - 1, 1);
1235 stack_first_empty += 4;
1236 }
1237 }
1238 }
1239 size_ = tree.size_;
1240 tree.size_ = 0;
1241 PPL_ASSERT(tree.structure_OK());
1242 PPL_ASSERT(structure_OK());
1243 }
1244
1245 void
copy_data_from(const CO_Tree & x)1246 PPL::CO_Tree::copy_data_from(const CO_Tree& x) {
1247 PPL_ASSERT(size_ == 0);
1248 PPL_ASSERT(reserved_size == x.reserved_size);
1249 PPL_ASSERT(structure_OK());
1250
1251 if (x.size_ == 0) {
1252 PPL_ASSERT(OK());
1253 return;
1254 }
1255
1256 dimension_type i;
1257 try {
1258 for (i = x.reserved_size; i > 0; --i) {
1259 if (x.indexes[i] != unused_index) {
1260 indexes[i] = x.indexes[i];
1261 new(&(data[i])) data_type(x.data[i]);
1262 }
1263 else {
1264 PPL_ASSERT(indexes[i] == unused_index);
1265 }
1266 }
1267 } catch (...) {
1268 // The (used) data elements in (i,x.reserved_size] have been constructed
1269 // successfully.
1270 // The constructor of data[i] has thrown an exception, so data[i] has not
1271 // been constructed.
1272
1273 // 1. Destroy the data elements that have been constructed successfully.
1274 for (dimension_type j = x.reserved_size; j > i; --j) {
1275 if (indexes[j] != unused_index) {
1276 data[j].~data_type();
1277 }
1278 }
1279
1280 // 2. Deallocate index[] and data[]
1281 delete[] indexes;
1282 data_allocator.deallocate(data, reserved_size + 1);
1283
1284 // 3. Set the tree to an empty tree and rethrow exception.
1285 init(0);
1286 throw;
1287 }
1288
1289 size_ = x.size_;
1290 PPL_ASSERT(OK());
1291 }
1292
1293 PPL::dimension_type
count_used_in_subtree(tree_iterator itr)1294 PPL::CO_Tree::count_used_in_subtree(tree_iterator itr) {
1295 dimension_type n = 0;
1296
1297 const dimension_type k = itr.get_offset();
1298 const dimension_type root_index = itr.dfs_index();
1299
1300 // The complete subtree rooted at itr has 2*k - 1 nodes.
1301
1302 PPL_ASSERT(root_index > (k - 1));
1303
1304 const dimension_type* current_index
1305 = &(itr.tree.indexes[root_index - (k - 1)]);
1306
1307 for (dimension_type j = 2*k - 1; j > 0; --j, ++current_index) {
1308 if (*current_index != unused_index) {
1309 ++n;
1310 }
1311 }
1312
1313 return n;
1314 }
1315
1316 bool
OK() const1317 PPL::CO_Tree::const_iterator::OK() const {
1318 #if PPL_CO_TREE_EXTRA_DEBUG
1319 if (tree == 0) {
1320 if (current_index != 0) {
1321 return false;
1322 }
1323 if (current_data != 0) {
1324 return false;
1325 }
1326 }
1327 else
1328 if (tree->reserved_size == 0) {
1329 if (current_index != 1 + static_cast<dimension_type*>(0)
1330 || current_data != 1 + static_cast<data_type*>(0)) {
1331 return false;
1332 }
1333 }
1334 else {
1335 if (current_index <= &(tree->indexes[0])) {
1336 return false;
1337 }
1338 if (current_index > &(tree->indexes[tree->reserved_size + 1])) {
1339 return false;
1340 }
1341 if (current_data <= &(tree->data[0])) {
1342 return false;
1343 }
1344 if (current_data > &(tree->data[tree->reserved_size + 1])) {
1345 return false;
1346 }
1347 if (*current_index == unused_index) {
1348 return false;
1349 }
1350 if (current_index - tree->indexes != current_data - tree->data) {
1351 return false;
1352 }
1353 }
1354 #endif
1355 return true;
1356 }
1357
1358 bool
OK() const1359 PPL::CO_Tree::iterator::OK() const {
1360 #if PPL_CO_TREE_EXTRA_DEBUG
1361 if (tree == 0) {
1362 if (current_index != 0) {
1363 return false;
1364 }
1365 if (current_data != 0) {
1366 return false;
1367 }
1368 }
1369 else
1370 if (tree->reserved_size == 0) {
1371 if (current_index != 1 + static_cast<dimension_type*>(0)
1372 || current_data != 1 + static_cast<data_type*>(0)) {
1373 return false;
1374 }
1375 }
1376 else {
1377 if (current_index <= &(tree->indexes[0])) {
1378 return false;
1379 }
1380 if (current_index > &(tree->indexes[tree->reserved_size + 1])) {
1381 return false;
1382 }
1383 if (current_data <= &(tree->data[0])) {
1384 return false;
1385 }
1386 if (current_data > &(tree->data[tree->reserved_size + 1])) {
1387 return false;
1388 }
1389 if (*current_index == unused_index) {
1390 return false;
1391 }
1392 if (current_index - tree->indexes != current_data - tree->data) {
1393 return false;
1394 }
1395 }
1396 #endif
1397 return true;
1398 }
1399
1400 bool
OK() const1401 PPL::CO_Tree::tree_iterator::OK() const {
1402 if (i == 0 || i > tree.reserved_size) {
1403 return false;
1404 }
1405
1406 // This assumes two's complement encoding.
1407 const dimension_type correct_offset = i & -i;
1408
1409 if (offset != correct_offset) {
1410 return false;
1411 }
1412
1413 return true;
1414 }
1415
1416 void
go_down_searching_key(dimension_type key)1417 PPL::CO_Tree::tree_iterator::go_down_searching_key(dimension_type key) {
1418 // *this points to a node, so the tree is not empty.
1419 PPL_ASSERT(!tree.empty());
1420 PPL_ASSERT(key != unused_index);
1421 PPL_ASSERT(index() != unused_index);
1422 while (!is_leaf()) {
1423 if (key == index()) {
1424 break;
1425 }
1426 if (key < index()) {
1427 get_left_child();
1428 if (index() == unused_index) {
1429 get_parent();
1430 break;
1431 }
1432 }
1433 else {
1434 get_right_child();
1435 if (index() == unused_index) {
1436 get_parent();
1437 break;
1438 }
1439 }
1440 }
1441 }
1442