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
[email protected]
https://lists.sourceforge.net/lists/listinfo/open64-devel
