This is the mail archive of the
libstdc++@gcc.gnu.org
mailing list for the libstdc++ project.
Re: [RFC] libstdc++/31440
- From: Paolo Carlini <pcarlini at suse dot de>
- To: Gabriel Dos Reis <gdr at cs dot tamu dot edu>
- Cc: libstdc++ <libstdc++ at gcc dot gnu dot org>
- Date: Tue, 03 Apr 2007 02:15:59 +0200
- Subject: Re: [RFC] libstdc++/31440
- References: <46117E6E.6050307@suse.de> <87hcryiamm.fsf@soliton.cs.tamu.edu>
Hi Gaby.
I have had a very hard day, so I'm slow at puzzles :-( You seem to
understand where the issue is, so plesse could elaborate a bit on what
the problem is what solution you're proposing?
basically, it's just one of those cost-correctness issues. I'm coming to
the conclusion it's a real regression vs the behavior we always had,
it's just that by chance another implementation is affected by the same
problems. I would fix it by adding (back) a bit of redundancy (and
removing a few casts), like the below, tested x86-linux. Sounds good?
Paolo.
////////////////
2007-04-03 Paolo Carlini <pcarlini@suse.de>
PR libstdc++/31440
* include/bits/stl_tree.h (_M_lower_bound(_Link_type, _Link_type,
const _Key&), _M_upper_bound(_Link_type, _Link_type, const _Key&)):
Add.
(_M_equal_range(const _Key&) const): Remove.
(lower_bound(const key_type&), lower_bound(const key_type&) const,
upper_bound(const key_type&), upper_bound(const key_type&) const,
equal_range(const key_type&), equal_range(const key_type&) const):
Adjust.
(find(const _Key&), find(const _Key&) const): Tweak.
* testsuite/23_containers/map/operations/31440.cc: New.
Index: include/bits/stl_tree.h
===================================================================
--- include/bits/stl_tree.h (revision 123420)
+++ include/bits/stl_tree.h (working copy)
@@ -554,16 +554,21 @@
_M_erase(_Link_type __x);
iterator
+ _M_lower_bound(_Link_type __x, _Link_type __y,
+ const _Key& __k);
+
+ const_iterator
_M_lower_bound(_Const_Link_type __x, _Const_Link_type __y,
const _Key& __k) const;
iterator
+ _M_upper_bound(_Link_type __x, _Link_type __y,
+ const _Key& __k);
+
+ const_iterator
_M_upper_bound(_Const_Link_type __x, _Const_Link_type __y,
const _Key& __k) const;
- pair<iterator, iterator>
- _M_equal_range(const _Key& __k) const;
-
public:
// allocation/deallocation
_Rb_tree()
@@ -717,27 +722,25 @@
iterator
lower_bound(const key_type& __k)
- { return iterator(_M_lower_bound(_M_begin(), _M_end(), __k)); }
+ { return _M_lower_bound(_M_begin(), _M_end(), __k); }
const_iterator
lower_bound(const key_type& __k) const
- { return const_iterator(_M_lower_bound(_M_begin(), _M_end(), __k)); }
+ { return _M_lower_bound(_M_begin(), _M_end(), __k); }
iterator
upper_bound(const key_type& __k)
- { return iterator(_M_upper_bound(_M_begin(), _M_end(), __k)); }
+ { return _M_upper_bound(_M_begin(), _M_end(), __k); }
const_iterator
upper_bound(const key_type& __k) const
- { return const_iterator(_M_upper_bound(_M_begin(), _M_end(), __k)); }
+ { return _M_upper_bound(_M_begin(), _M_end(), __k); }
pair<iterator, iterator>
- equal_range(const key_type& __k)
- { return pair<iterator, iterator>(_M_equal_range(__k)); }
+ equal_range(const key_type& __k);
pair<const_iterator, const_iterator>
- equal_range(const key_type& __k) const
- { return pair<const_iterator, const_iterator>(_M_equal_range(__k)); }
+ equal_range(const key_type& __k) const;
// Debugging.
bool
@@ -929,8 +932,25 @@
template<typename _Key, typename _Val, typename _KeyOfValue,
typename _Compare, typename _Alloc>
- typename _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::iterator
+ typename _Rb_tree<_Key, _Val, _KeyOfValue,
+ _Compare, _Alloc>::iterator
_Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
+ _M_lower_bound(_Link_type __x, _Link_type __y,
+ const _Key& __k)
+ {
+ while (__x != 0)
+ if (!_M_impl._M_key_compare(_S_key(__x), __k))
+ __y = __x, __x = _S_left(__x);
+ else
+ __x = _S_right(__x);
+ return iterator(__y);
+ }
+
+ template<typename _Key, typename _Val, typename _KeyOfValue,
+ typename _Compare, typename _Alloc>
+ typename _Rb_tree<_Key, _Val, _KeyOfValue,
+ _Compare, _Alloc>::const_iterator
+ _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
_M_lower_bound(_Const_Link_type __x, _Const_Link_type __y,
const _Key& __k) const
{
@@ -939,13 +959,30 @@
__y = __x, __x = _S_left(__x);
else
__x = _S_right(__x);
- return iterator(const_cast<_Link_type>(__y));
+ return const_iterator(__y);
}
template<typename _Key, typename _Val, typename _KeyOfValue,
typename _Compare, typename _Alloc>
- typename _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::iterator
+ typename _Rb_tree<_Key, _Val, _KeyOfValue,
+ _Compare, _Alloc>::iterator
_Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
+ _M_upper_bound(_Link_type __x, _Link_type __y,
+ const _Key& __k)
+ {
+ while (__x != 0)
+ if (_M_impl._M_key_compare(__k, _S_key(__x)))
+ __y = __x, __x = _S_left(__x);
+ else
+ __x = _S_right(__x);
+ return iterator(__y);
+ }
+
+ template<typename _Key, typename _Val, typename _KeyOfValue,
+ typename _Compare, typename _Alloc>
+ typename _Rb_tree<_Key, _Val, _KeyOfValue,
+ _Compare, _Alloc>::const_iterator
+ _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
_M_upper_bound(_Const_Link_type __x, _Const_Link_type __y,
const _Key& __k) const
{
@@ -954,17 +991,49 @@
__y = __x, __x = _S_left(__x);
else
__x = _S_right(__x);
- return iterator(const_cast<_Link_type>(__y));
+ return const_iterator(__y);
}
template<typename _Key, typename _Val, typename _KeyOfValue,
typename _Compare, typename _Alloc>
pair<typename _Rb_tree<_Key, _Val, _KeyOfValue,
_Compare, _Alloc>::iterator,
- typename _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::iterator>
+ typename _Rb_tree<_Key, _Val, _KeyOfValue,
+ _Compare, _Alloc>::iterator>
_Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
- _M_equal_range(const _Key& __k) const
+ equal_range(const _Key& __k)
{
+ _Link_type __x = _M_begin();
+ _Link_type __y = _M_end();
+ while (__x != 0)
+ {
+ if (_M_impl._M_key_compare(_S_key(__x), __k))
+ __x = _S_right(__x);
+ else if (_M_impl._M_key_compare(__k, _S_key(__x)))
+ __y = __x, __x = _S_left(__x);
+ else
+ {
+ _Link_type __xu(__x), __yu(__y);
+ __y = __x, __x = _S_left(__x);
+ __xu = _S_right(__xu);
+ return pair<iterator,
+ iterator>(_M_lower_bound(__x, __y, __k),
+ _M_upper_bound(__xu, __yu, __k));
+ }
+ }
+ return pair<iterator, iterator>(iterator(__y),
+ iterator(__y));
+ }
+
+ template<typename _Key, typename _Val, typename _KeyOfValue,
+ typename _Compare, typename _Alloc>
+ pair<typename _Rb_tree<_Key, _Val, _KeyOfValue,
+ _Compare, _Alloc>::const_iterator,
+ typename _Rb_tree<_Key, _Val, _KeyOfValue,
+ _Compare, _Alloc>::const_iterator>
+ _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
+ equal_range(const _Key& __k) const
+ {
_Const_Link_type __x = _M_begin();
_Const_Link_type __y = _M_end();
while (__x != 0)
@@ -978,12 +1047,13 @@
_Const_Link_type __xu(__x), __yu(__y);
__y = __x, __x = _S_left(__x);
__xu = _S_right(__xu);
- return pair<iterator, iterator>(_M_lower_bound(__x, __y, __k),
- _M_upper_bound(__xu, __yu, __k));
+ return pair<const_iterator,
+ const_iterator>(_M_lower_bound(__x, __y, __k),
+ _M_upper_bound(__xu, __yu, __k));
}
}
- return pair<iterator, iterator>(iterator(const_cast<_Link_type>(__y)),
- iterator(const_cast<_Link_type>(__y)));
+ return pair<const_iterator, const_iterator>(const_iterator(__y),
+ const_iterator(__y));
}
template<typename _Key, typename _Val, typename _KeyOfValue,
@@ -1295,11 +1365,12 @@
template<typename _Key, typename _Val, typename _KeyOfValue,
typename _Compare, typename _Alloc>
- typename _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::iterator
+ typename _Rb_tree<_Key, _Val, _KeyOfValue,
+ _Compare, _Alloc>::iterator
_Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
find(const _Key& __k)
{
- iterator __j = iterator(_M_lower_bound(_M_begin(), _M_end(), __k));
+ iterator __j = _M_lower_bound(_M_begin(), _M_end(), __k);
return (__j == end()
|| _M_impl._M_key_compare(__k,
_S_key(__j._M_node))) ? end() : __j;
@@ -1307,12 +1378,12 @@
template<typename _Key, typename _Val, typename _KeyOfValue,
typename _Compare, typename _Alloc>
- typename _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::const_iterator
+ typename _Rb_tree<_Key, _Val, _KeyOfValue,
+ _Compare, _Alloc>::const_iterator
_Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
find(const _Key& __k) const
{
- const_iterator __j = const_iterator(_M_lower_bound(_M_begin(),
- _M_end(), __k));
+ const_iterator __j = _M_lower_bound(_M_begin(), _M_end(), __k);
return (__j == end()
|| _M_impl._M_key_compare(__k,
_S_key(__j._M_node))) ? end() : __j;
Index: testsuite/23_containers/map/operations/31440.cc
===================================================================
--- testsuite/23_containers/map/operations/31440.cc (revision 0)
+++ testsuite/23_containers/map/operations/31440.cc (revision 0)
@@ -0,0 +1,61 @@
+// { dg-do compile }
+
+// Copyright (C) 2007 Free Software Foundation, Inc.
+//
+// This file is part of the GNU ISO C++ Library. This library is free
+// software; you can redistribute it and/or modify it under the
+// terms of the GNU General Public License as published by the
+// Free Software Foundation; either version 2, or (at your option)
+// any later version.
+//
+// This library is distributed in the hope that it will be useful,
+// but WITHOUT ANY WARRANTY; without even the implied warranty of
+// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
+// GNU General Public License for more details.
+//
+// You should have received a copy of the GNU General Public License along
+// with this library; see the file COPYING. If not, write to the Free
+// Software Foundation, 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301,
+// USA.
+//
+// As a special exception, you may use this file as part of a free software
+// library without restriction. Specifically, if other files instantiate
+// templates or use macros or inline functions from this file, or you compile
+// this file and link it with other files to produce an executable, this
+// file does not by itself cause the resulting executable to be covered by
+// the GNU General Public License. This exception does not however
+// invalidate any other reasons why the executable file might be covered by
+// the GNU General Public License.
+
+#include <map>
+
+// libstdc++/31440
+struct DagNode
+{ };
+
+class MemoTable
+{
+public:
+ void memoRewrite();
+
+private:
+ struct dagNodeLt;
+ class MemoMap;
+
+ MemoMap* memoMap;
+};
+
+struct MemoTable::dagNodeLt
+{
+ bool operator()(const DagNode*, const DagNode*);
+};
+
+class MemoTable::MemoMap
+: public std::map<DagNode*, DagNode*, MemoTable::dagNodeLt>
+{ };
+
+void
+MemoTable::memoRewrite()
+{
+ memoMap->find(0);
+}