I have not received any additional reply/justification for this checkin, together with Matt Austern's comments. I am requesting back out of this checkin. Please do so until there is concensus on what is the right approach Sun
On Tue, Jun 7, 2011 at 11:08 PM, Das, Dibyendu <dibyendu....@amd.com> wrote: > CR by Shin/Sun/Chris. > > TBD: Send patch to gcc with additional information. > > -----Original Message----- > From: s...@open64.net [mailto:s...@open64.net] > Sent: Wednesday, June 08, 2011 11:36 AM > To: open64-devel@lists.sourceforge.net > Subject: [Open64-devel] r3642 - > trunk/osprey-gcc-4.2.0/libstdc++-v3/include/bits > > Author: dibyendu > Date: 2011-06-08 02:06:24 -0400 (Wed, 08 Jun 2011) > New Revision: 3642 > > Modified: > trunk/osprey-gcc-4.2.0/libstdc++-v3/include/bits/stl_tree.h > Log: > Implementation of fast STL set/map which allows iterators to be speedier > when iterators are hot. The underlying Red-Black Tree structure has been > changed for this purpose. Currently the implementation is available > under the -D__OPEN64_FAST_SET. > > > > Modified: trunk/osprey-gcc-4.2.0/libstdc++-v3/include/bits/stl_tree.h > =================================================================== > --- trunk/osprey-gcc-4.2.0/libstdc++-v3/include/bits/stl_tree.h 2011-06-04 > 07:25:15 UTC (rev 3641) > +++ trunk/osprey-gcc-4.2.0/libstdc++-v3/include/bits/stl_tree.h 2011-06-08 > 06:06:24 UTC (rev 3642) > @@ -100,6 +100,11 @@ > _Base_ptr _M_left; > _Base_ptr _M_right; > > +#ifdef __OPEN64_FAST_SET > + _Base_ptr _M_prev; > + _Base_ptr _M_next; > +#endif > + > static _Base_ptr > _S_minimum(_Base_ptr __x) > { > @@ -180,7 +185,11 @@ > _Self& > operator++() > { > +#ifdef __OPEN64_FAST_SET > + _M_node = _M_node->_M_next; > +#else > _M_node = _Rb_tree_increment(_M_node); > +#endif > return *this; > } > > @@ -188,14 +197,23 @@ > operator++(int) > { > _Self __tmp = *this; > + > +#ifdef __OPEN64_FAST_SET > + _M_node = _M_node->_M_next; > +#else > _M_node = _Rb_tree_increment(_M_node); > +#endif > return __tmp; > } > > _Self& > operator--() > { > +#ifdef __OPEN64_FAST_SET > + _M_node = _M_node->_M_prev; > +#else > _M_node = _Rb_tree_decrement(_M_node); > +#endif > return *this; > } > > @@ -203,7 +221,12 @@ > operator--(int) > { > _Self __tmp = *this; > + > +#ifdef __OPEN64_FAST_SET > + _M_node = _M_node->_M_prev; > +#else > _M_node = _Rb_tree_decrement(_M_node); > +#endif > return __tmp; > } > > @@ -255,7 +278,11 @@ > _Self& > operator++() > { > +#ifdef __OPEN64_FAST_SET > + _M_node = _M_node->_M_next; > +#else > _M_node = _Rb_tree_increment(_M_node); > +#endif > return *this; > } > > @@ -263,14 +290,23 @@ > operator++(int) > { > _Self __tmp = *this; > + > +#ifdef __OPEN64_FAST_SET > + _M_node = _M_node->_M_next; > +#else > _M_node = _Rb_tree_increment(_M_node); > +#endif > return __tmp; > } > > _Self& > operator--() > { > +#ifdef __OPEN64_FAST_SET > + _M_node = _M_node->_M_prev; > +#else > _M_node = _Rb_tree_decrement(_M_node); > +#endif > return *this; > } > > @@ -278,7 +314,12 @@ > operator--(int) > { > _Self __tmp = *this; > + > +#ifdef __OPEN64_FAST_SET > + _M_node = _M_node->_M_prev; > +#else > _M_node = _Rb_tree_decrement(_M_node); > +#endif > return __tmp; > } > > @@ -324,6 +365,16 @@ > _Rb_tree_node_base& __header); > > > +#ifdef __OPEN64_FAST_SET > + void > + _Rb_tree_insert_into_sorted_list(const bool __insert_left, > + _Rb_tree_node_base* __x, > + _Rb_tree_node_base* __p, > + _Rb_tree_node_base& __header); > + void > + _Rb_tree_recreate_sorted_list(_Rb_tree_node_base& __header); > +#endif > + > template<typename _Key, typename _Val, typename _KeyOfValue, > typename _Compare, typename _Alloc = allocator<_Val> > > class _Rb_tree > @@ -391,6 +442,12 @@ > __tmp->_M_color = __x->_M_color; > __tmp->_M_left = 0; > __tmp->_M_right = 0; > + > +#ifdef __OPEN64_FAST_SET > + __tmp->_M_prev = __tmp; > + __tmp->_M_next = __tmp; > +#endif > + > return __tmp; > } > > @@ -419,6 +476,11 @@ > this->_M_header._M_parent = 0; > this->_M_header._M_left = &this->_M_header; > this->_M_header._M_right = &this->_M_header; > + > +#ifdef __OPEN64_FAST_SET > + this->_M_header._M_prev = &this->_M_header; > + this->_M_header._M_next = &this->_M_header; > +#endif > } > }; > > @@ -440,6 +502,12 @@ > this->_M_header._M_parent = 0; > this->_M_header._M_left = &this->_M_header; > this->_M_header._M_right = &this->_M_header; > + > +#ifdef __OPEN64_FAST_SET > + this->_M_header._M_prev = &this->_M_header; > + this->_M_header._M_next = &this->_M_header; > +#endif > + > } > }; > > @@ -585,6 +653,10 @@ > _M_leftmost() = _S_minimum(_M_root()); > _M_rightmost() = _S_maximum(_M_root()); > _M_impl._M_node_count = __x._M_impl._M_node_count; > + > +#ifdef __OPEN64_FAST_SET > + _Rb_tree_recreate_sorted_list(this->_M_impl._M_header); > +#endif > } > } > > @@ -713,6 +785,11 @@ > _M_root() = 0; > _M_rightmost() = _M_end(); > _M_impl._M_node_count = 0; > + > +#ifdef __OPEN64_FAST_SET > + _M_end()->_M_next = _M_end(); > + _M_end()->_M_prev = _M_end(); > +#endif > } > > // Set operations. > @@ -820,6 +897,10 @@ > _M_leftmost() = _S_minimum(_M_root()); > _M_rightmost() = _S_maximum(_M_root()); > _M_impl._M_node_count = __x._M_impl._M_node_count; > + > +#ifdef __OPEN64_FAST_SET > + _Rb_tree_recreate_sorted_list(this->_M_impl._M_header); > +#endif > } > } > return *this; > @@ -837,6 +918,10 @@ > > _Link_type __z = _M_create_node(__v); > > +#ifdef __OPEN64_FAST_SET > + _Rb_tree_insert_into_sorted_list(__insert_left, __z, __p, > + this->_M_impl._M_header); > +#endif > _Rb_tree_insert_and_rebalance(__insert_left, __z, __p, > this->_M_impl._M_header); > ++_M_impl._M_node_count; > @@ -855,6 +940,10 @@ > > _Link_type __z = _M_create_node(__v); > > +#ifdef __OPEN64_FAST_SET > + _Rb_tree_insert_into_sorted_list(__insert_left, __z, __p, > + this->_M_impl._M_header); > +#endif > _Rb_tree_insert_and_rebalance(__insert_left, __z, __p, > this->_M_impl._M_header); > ++_M_impl._M_node_count; > @@ -873,6 +962,11 @@ > > _Link_type __z = _M_create_node(__v); > > +#ifdef __OPEN64_FAST_SET > + _Rb_tree_insert_into_sorted_list(__insert_left, __z, > + const_cast<_Base_ptr>(__p), > + this->_M_impl._M_header); > +#endif > _Rb_tree_insert_and_rebalance(__insert_left, __z, > const_cast<_Base_ptr>(__p), > this->_M_impl._M_header); > @@ -928,10 +1022,23 @@ > _M_leftmost() = __t._M_leftmost(); > _M_rightmost() = __t._M_rightmost(); > _M_root()->_M_parent = _M_end(); > + > +#ifdef __OPEN64_FAST_SET > + _M_end()->_M_next = _M_leftmost(); > + _M_leftmost()->_M_prev = _M_end(); > + _M_end()->_M_prev = _M_rightmost(); > + _M_rightmost()->_M_next = _M_end(); > +#endif > > __t._M_root() = 0; > __t._M_leftmost() = __t._M_end(); > __t._M_rightmost() = __t._M_end(); > + > +#ifdef __OPEN64_FAST_SET > + __t._M_end()->_M_prev = __t._M_end(); > + __t._M_end()->_M_next = __t._M_end(); > +#endif > + > } > } > else if (__t._M_root() == 0) > @@ -940,10 +1047,24 @@ > __t._M_leftmost() = _M_leftmost(); > __t._M_rightmost() = _M_rightmost(); > __t._M_root()->_M_parent = __t._M_end(); > + > +#ifdef __OPEN64_FAST_SET > + __t._M_end()->_M_next = __t._M_leftmost(); > + __t._M_leftmost()->_M_prev = __t._M_end(); > + __t._M_end()->_M_prev = __t._M_rightmost(); > + __t._M_rightmost()->_M_next = __t._M_end(); > +#endif > > + > _M_root() = 0; > _M_leftmost() = _M_end(); > _M_rightmost() = _M_end(); > + > +#ifdef __OPEN64_FAST_SET > + _M_end()->_M_prev = _M_end(); > + _M_end()->_M_next = _M_end(); > +#endif > + > } > else > { > @@ -953,6 +1074,19 @@ > > _M_root()->_M_parent = _M_end(); > __t._M_root()->_M_parent = __t._M_end(); > + > +#ifdef __OPEN64_FAST_SET > + _M_end()->_M_next = _M_leftmost(); > + _M_leftmost()->_M_prev = _M_end(); > + _M_end()->_M_prev = _M_rightmost(); > + _M_rightmost()->_M_next = _M_end(); > + __t._M_end()->_M_next = __t._M_leftmost(); > + __t._M_leftmost()->_M_prev = __t._M_end(); > + __t._M_end()->_M_prev = __t._M_rightmost(); > + __t._M_rightmost()->_M_next = __t._M_end(); > +#endif > + > + > } > // No need to swap header's color as it does not change. > std::swap(this->_M_impl._M_node_count, __t._M_impl._M_node_count); > @@ -1245,6 +1379,12 @@ > static_cast<_Link_type>(_Rb_tree_rebalance_for_erase > (__position._M_node, > this->_M_impl._M_header)); > + > +#ifdef __OPEN64_FAST_SET > + __y->_M_prev->_M_next = __y->_M_next; > + __y->_M_next->_M_prev = __y->_M_prev; > +#endif > + > _M_destroy_node(__y); > --_M_impl._M_node_count; > } > @@ -1259,6 +1399,11 @@ > static_cast<_Link_type>(_Rb_tree_rebalance_for_erase > (const_cast<_Base_ptr>(__position._M_node), > this->_M_impl._M_header)); > +#ifdef __OPEN64_FAST_SET > + __y->_M_prev->_M_next = __y->_M_next; > + __y->_M_next->_M_prev = __y->_M_prev; > +#endif > + > _M_destroy_node(__y); > --_M_impl._M_node_count; > } > @@ -1281,7 +1426,7 @@ > _Rb_tree<_Key, _Val, _KoV, _Compare, _Alloc>:: > _M_copy(_Const_Link_type __x, _Link_type __p) > { > - // Structural copy. __x and __p must be non-null. > + > _Link_type __top = _M_clone_node(__x); > __top->_M_parent = __p; > > @@ -1289,9 +1434,11 @@ > { > if (__x->_M_right) > __top->_M_right = _M_copy(_S_right(__x), __top); > + > __p = __top; > __x = _S_left(__x); > > + > while (__x != 0) > { > _Link_type __y = _M_clone_node(__x); > @@ -1299,6 +1446,7 @@ > __y->_M_parent = __p; > if (__x->_M_right) > __y->_M_right = _M_copy(_S_right(__x), __y); > + > __p = __y; > __x = _S_left(__x); > } > @@ -1322,6 +1470,11 @@ > { > _M_erase(_S_right(__x)); > _Link_type __y = _S_left(__x); > + > +#ifdef __OPEN64_FAST_SET > + __x->_M_prev->_M_next = __x->_M_next; > + __x->_M_next->_M_prev = __x->_M_prev; > +#endif > _M_destroy_node(__x); > __x = __y; > } > @@ -1552,6 +1705,49 @@ > return true; > } > > +#ifdef __OPEN64_FAST_SET > +inline void > +_Rb_tree_insert_into_sorted_list(const bool __insert_left, > + _Rb_tree_node_base* __x, > + _Rb_tree_node_base* __p, > + _Rb_tree_node_base& __header ) > +{ > + if ( __insert_left) > + { > + __x->_M_next = __p; > + __x->_M_prev = __p->_M_prev; > + __p->_M_prev->_M_next = __x; > + __p->_M_prev = __x; > + } > + else { > + __x->_M_prev = __p; > + __x->_M_next = __p->_M_next; > + __p->_M_next->_M_prev = __x; > + __p->_M_next = __x; > + } > +} > +inline void > +_Rb_tree_recreate_sorted_list(_Rb_tree_node_base& __header ) > +{ > + _Rb_tree_node_base *__x, *__y, *__rightmost; > + > + __rightmost = __header._M_right; > + __x = __header._M_left; > + __x->_M_prev = &__header; > + __header._M_next = __x; > + > + while ( __x != __rightmost ) > + { > + __y = _Rb_tree_increment(__x); > + __x->_M_next = __y; > + __y->_M_prev = __x; > + __x = __y; > + } > + __rightmost->_M_next = &__header; > + __header._M_prev = __rightmost; > +} > +#endif > + > _GLIBCXX_END_NAMESPACE > > #endif > > > ------------------------------------------------------------------------------ > EditLive Enterprise is the world's most technically advanced content > authoring tool. Experience the power of Track Changes, Inline Image > Editing and ensure content is compliant with Accessibility Checking. > http://p.sf.net/sfu/ephox-dev2dev > _______________________________________________ > Open64-devel mailing list > Open64-devel@lists.sourceforge.net > https://lists.sourceforge.net/lists/listinfo/open64-devel > > > > ------------------------------------------------------------------------------ > EditLive Enterprise is the world's most technically advanced content > authoring tool. Experience the power of Track Changes, Inline Image > Editing and ensure content is compliant with Accessibility Checking. > http://p.sf.net/sfu/ephox-dev2dev > _______________________________________________ > Open64-devel mailing list > Open64-devel@lists.sourceforge.net > https://lists.sourceforge.net/lists/listinfo/open64-devel > ------------------------------------------------------------------------------ EditLive Enterprise is the world's most technically advanced content authoring tool. Experience the power of Track Changes, Inline Image Editing and ensure content is compliant with Accessibility Checking. http://p.sf.net/sfu/ephox-dev2dev _______________________________________________ Open64-devel mailing list Open64-devel@lists.sourceforge.net https://lists.sourceforge.net/lists/listinfo/open64-devel
