Changeset 21d97e8 in mainline for uspace/lib/cpp/include/internal
- Timestamp:
- 2018-07-05T21:41:23Z (7 years ago)
- Branches:
- lfn, master, serial, ticket/834-toolchain-update, topic/msim-upgrade, topic/simplify-dev-export
- Children:
- 0fe0f32
- Parents:
- 5608106c
- git-author:
- Dzejrou <dzejrou@…> (2018-05-14 17:03:57)
- git-committer:
- Dzejrou <dzejrou@…> (2018-07-05 21:41:23)
- Location:
- uspace/lib/cpp/include/internal
- Files:
-
- 4 edited
Legend:
- Unmodified
- Added
- Removed
-
uspace/lib/cpp/include/internal/rbtree.hpp
r5608106c r21d97e8 353 353 if (!node) 354 354 return nullptr; 355 356 --size_; 357 358 auto succ = node->successor(); 355 359 if (auto tmp = node->get_node_for_deletion(); tmp != nullptr) 356 360 { … … 359 363 * we popped one node from a list of nodes 360 364 * with equivalent keys and we can delete it 361 * and return the original as it is still362 * in place.365 * and return the successor which was the next 366 * in the list. 363 367 */ 364 368 delete tmp; 365 369 366 return node; 367 } 368 369 --size_; 370 371 if (node == root_) 372 { 370 update_root_(succ); // Incase the first in list was root. 371 return succ; 372 } 373 else if (node == root_) 374 { // Only executed if root_ is unique. 375 root_ = nullptr; 373 376 delete node; 374 root_ = nullptr;375 377 376 378 return nullptr; 377 379 } 378 380 379 auto succ = node->successor();380 381 if (node->left() && node->right()) 381 382 { … … 407 408 else if (node->is_right_child()) 408 409 child->parent()->right(child); 410 node->parent(nullptr); 411 node->left(nullptr); 412 node->right(nullptr); 409 413 410 414 // Repair if needed. -
uspace/lib/cpp/include/internal/rbtree_iterators.hpp
r5608106c r21d97e8 78 78 rbtree_iterator& operator++() 79 79 { 80 if (end_) 81 return *this; 82 80 83 if (current_) 81 84 { … … 102 105 if (end_) 103 106 { 104 try_undo_end_();107 end_ = false; 105 108 106 109 return *this; … … 145 148 node_type* current_; 146 149 bool end_; 147 148 void try_undo_end_()149 {150 if (!current_)151 return;152 153 /**154 * We can do this if we are past end().155 * This means we are the largest.156 */157 if (current_->find_largest() == current_)158 end_ = false;159 }160 150 }; 161 151 … … 224 214 rbtree_const_iterator& operator++() 225 215 { 216 if (end_) 217 return *this; 218 226 219 if (current_) 227 220 { … … 248 241 if (end_) 249 242 { 250 try_undo_end_();243 end_ = false; 251 244 252 245 return *this; … … 286 279 const node_type* current_; 287 280 bool end_; 288 289 void try_undo_end_()290 {291 if (!current_)292 return;293 294 /**295 * We can do this if we are past end().296 * This means we are the largest.297 */298 if (current_->find_largest() == current_)299 end_ = false;300 }301 281 }; 302 282 -
uspace/lib/cpp/include/internal/rbtree_node.hpp
r5608106c r21d97e8 46 46 { 47 47 if (node && node->parent()) 48 return node->parent ->parent();48 return node->parent()->parent(); 49 49 else 50 50 return nullptr; … … 55 55 if (node && node->parent()) 56 56 { 57 if (node == node->parent ->left())58 return node->parent ->right();59 else 60 return node->parent ->left();57 if (node == node->parent()->left()) 58 return node->parent()->right(); 59 else 60 return node->parent()->left(); 61 61 } 62 62 else … … 573 573 const rbtree_multi_node* predecessor() const 574 574 { 575 return utils::predecessor(this); 575 if (this != first_) 576 { 577 auto tmp = first_; 578 while (tmp->next_ != this) 579 tmp = tmp->next_; 580 581 return tmp; 582 } 583 else 584 { 585 auto tmp = utils::predecessor(this); 586 587 /** 588 * If tmp was duplicate, we got a pointer 589 * to the first node in the list. So we need 590 * to move to the end. 591 */ 592 while (tmp->next_ != nullptr) 593 tmp = tmp->next_; 594 595 return tmp; 596 } 576 597 } 577 598 … … 591 612 } 592 613 593 rbtree_multi_node<T>* get_node_for_deletion() 594 { 614 rbtree_multi_node* get_node_for_deletion() 615 { 616 /** 617 * To make sure we delete nodes in 618 * the order of their insertion 619 * (not required, but sensical), we 620 * update then list and return this 621 * for deletion. 622 */ 595 623 if (next_) 596 624 { 597 auto tmp = next_; 598 while (tmp && tmp->next_ != this) 625 // Make next the new this. 626 next_->first_ = next_; 627 if (is_left_child()) 628 parent_->left_ = next_; 629 else if (is_right_child()) 630 parent_->right_ = next_; 631 632 if (left_) 633 left_->parent_ = next_; 634 if (right_) 635 right_->parent_ = next_; 636 637 /** 638 * Update the first_ pointer 639 * of the rest of the list. 640 */ 641 auto tmp = next_->next_; 642 while (tmp) 643 { 644 tmp->first_ = next_; 599 645 tmp = tmp->next_; 600 601 return tmp; // This will get deleted. 646 } 647 648 /** 649 * Otherwise destructor could 650 * destroy them. 651 */ 652 parent_ = nullptr; 653 left_ = nullptr; 654 right_ = nullptr; 655 next_ = nullptr; 656 first_ = nullptr; 657 658 return this; // This will get deleted. 602 659 } 603 660 else … … 608 665 { 609 666 if (is_left_child()) 610 parent ->left_ = nullptr;667 parent_->left_ = nullptr; 611 668 else if (is_right_child()) 612 parent ->right_ = nullptr;669 parent_->right_ = nullptr; 613 670 } 614 671 -
uspace/lib/cpp/include/internal/rbtree_policies.hpp
r5608106c r21d97e8 277 277 278 278 size_type res{}; 279 while ( tree.keys_equal(tree.get_key(*it), key))279 while (it != tree.end() && tree.keys_equal(tree.get_key(*it), key)) 280 280 { 281 281 ++res; … … 291 291 auto it = lower_bound_const(tree, key); 292 292 293 return typename Tree::iterator{it.node(), it.end()}; 293 return typename Tree::iterator{ 294 const_cast<typename Tree::node_type*>(it.node()), it.end() 295 }; 294 296 } 295 297 … … 328 330 auto it = upper_bound_const(tree, key); 329 331 330 return typename Tree::iterator{it.node(), it.end()}; 332 return typename Tree::iterator{ 333 const_cast<typename Tree::node_type*>(it.node()), it.end() 334 }; 331 335 } 332 336
Note:
See TracChangeset
for help on using the changeset viewer.