svn commit: r616673 - /stdcxx/trunk/include/rw/_tree.cc

[vitek]

Author: vitek
Date: Tue Jan 29 23:50:05 2008
New Revision: 616673

URL: http://svn.apache.org/viewvc?rev=616673&view=rev
Log:

2008-01-30  Travis Vitek  <[EMAIL PROTECTED]>

        STDCXX-216
        * include/rw/_tree.cc (insert): Optimize insertion when hint iterator
        is not begin() or end(). Add some much needed documentation.


Modified:
    stdcxx/trunk/include/rw/_tree.cc

Modified: stdcxx/trunk/include/rw/_tree.cc
URL: 
http://svn.apache.org/viewvc/stdcxx/trunk/include/rw/_tree.cc?rev=616673&r1=616672&r2=616673&view=diff
==============================================================================
--- stdcxx/trunk/include/rw/_tree.cc (original)
+++ stdcxx/trunk/include/rw/_tree.cc Tue Jan 29 23:50:05 2008
@@ -348,28 +348,48 @@
 
 #endif   // _RWSTDDEBUG
 
-    if (__it == begin ()) {
-        if (size () && _C_cmp (_KeyOf ()(__v), _ITER_NODE (__it)->_C_key ()))
-            return _C_insert (_ITER_NODE (__it), _ITER_NODE (__it), __v);
+    const _C_link_t __hint = _ITER_NODE (__it);
+
+    // if __hint is the right most child and __key is greater,
+    // then insert on the right
+    if (__hint == _C_end->_C_child [1]) {
+        if (_C_cmp (__hint->_C_key (), _KeyOf ()(__v)))
+            return _C_insert (0, __hint, __v);
         return insert (__v, __dup).first;
     }
 
-    if (__it == end ()) {
-        if (_C_cmp (_C_end->_C_child [1]->_C_key(), _KeyOf ()(__v)))
-            return _C_insert (0, _C_end->_C_child [1], __v);
+    // if __hint is past the end and __key is greater,
+    // then insert on the right
+    if (__hint == _C_end) {
+        if (_C_cmp (__hint->_C_child [1]->_C_key(), _KeyOf ()(__v)))
+            return _C_insert (0, __hint->_C_child [1], __v);
+        return insert (__v, __dup).first;
+    }
 
+    // if __hint is the leftmost child and __key is less
+    // then insert on the left
+    if (__hint == _C_end->_C_child [0]) {
+        if (size () && _C_cmp (_KeyOf ()(__v), __hint->_C_key ()))
+            return _C_insert (__hint, __hint, __v);
         return insert (__v, __dup).first;
     }
 
-    const iterator __prev = --__it;
+    const iterator __prev = __it++;
 
+    // if __v falls between __prev and __it, then insert it there
     if (   _C_cmp (_ITER_NODE (__prev)->_C_key (), _KeyOf ()(__v))
         && _C_cmp (_KeyOf ()(__v), _ITER_NODE (__it)->_C_key ())) {
+
+        // if there is no right child of __prev, then __prev is the
+        // left child of __it and we insert to right of __prev
         if (_C_link_t () == _ITER_NODE (__prev)->_C_child [1])
             return _C_insert (0, _ITER_NODE (__prev), __v); 
+
+        // otherwise we insert on the left of __it
         return _C_insert (_ITER_NODE (__it), _ITER_NODE (__it), __v);
     }
 
+    // otherwise, do a full traversal
     return insert (__v, __dup).first;
 }