hashtable_policy.h (__lower_bound): Add.

2007-12-25  Paolo Carlini  <pcarlini@suse.de>

	* include/tr1_impl/hashtable_policy.h (__lower_bound): Add.
	(_Prime_rehash_policy::_M_next_bkt, _M_bkt_for_elements,
	_M_need_rehash): Use __lower_bound.
	* include/std/unordered_map: Do not include the whole <algorithm>,
	include <bits/stl_algobase.h>.
	* include/std/unordered_set: Likewise.
	* include/tr1/unordered_map: Likewise.
	* include/tr1/unordered_set: Likewise.

From-SVN: r131170

6 files changed, 43 insertions, 10 deletions

diff --git a/libstdc++-v3/ChangeLog b/libstdc++-v3/ChangeLog
index f88476a..b870e82 100644
--- a/libstdc++-v3/ChangeLog
+++ b/libstdc++-v3/ChangeLog
@@ -1,3 +1,14 @@
+2007-12-25  Paolo Carlini  <pcarlini@suse.de>
+
+	* include/tr1_impl/hashtable_policy.h (__lower_bound): Add.
+	(_Prime_rehash_policy::_M_next_bkt, _M_bkt_for_elements,
+	_M_need_rehash): Use __lower_bound.
+	* include/std/unordered_map: Do not include the whole <algorithm>,
+	include <bits/stl_algobase.h>.
+	* include/std/unordered_set: Likewise.
+	* include/tr1/unordered_map: Likewise.
+	* include/tr1/unordered_set: Likewise.
+
 2007-12-24  Paolo Carlini  <pcarlini@suse.de>
 
 	* testsuite/20_util/tuple/cons/big_tuples.cc: New.
diff --git a/libstdc++-v3/include/std/unordered_map b/libstdc++-v3/include/std/unordered_map
index 4ce8051..5fb714d 100644
--- a/libstdc++-v3/include/std/unordered_map
+++ b/libstdc++-v3/include/std/unordered_map
@@ -45,8 +45,8 @@
 #endif
 
 #include <utility>
-#include <algorithm> // lower_bound
 #include <type_traits>
+#include <bits/stl_algobase.h>
 #include <bits/allocator.h>
 #include <bits/stl_function.h> // equal_to, _Identity, _Select1st
 #include <bits/stringfwd.h>
diff --git a/libstdc++-v3/include/std/unordered_set b/libstdc++-v3/include/std/unordered_set
index 3cc6937..1e59984 100644
--- a/libstdc++-v3/include/std/unordered_set
+++ b/libstdc++-v3/include/std/unordered_set
@@ -45,8 +45,8 @@
 #endif
 
 #include <utility>
-#include <algorithm> // lower_bound
 #include <type_traits>
+#include <bits/stl_algobase.h>
 #include <bits/allocator.h>
 #include <bits/stl_function.h> // equal_to, _Identity, _Select1st
 #include <bits/stringfwd.h>
diff --git a/libstdc++-v3/include/tr1/unordered_map b/libstdc++-v3/include/tr1/unordered_map
index 041eb94..5ab2940 100644
--- a/libstdc++-v3/include/tr1/unordered_map
+++ b/libstdc++-v3/include/tr1/unordered_map
@@ -41,7 +41,7 @@
 #endif
 
 #include <utility>
-#include <algorithm> // lower_bound
+#include <bits/stl_algobase.h>
 #include <bits/allocator.h>
 #include <bits/stl_function.h> // equal_to, _Identity, _Select1st
 #include <bits/stringfwd.h>
diff --git a/libstdc++-v3/include/tr1/unordered_set b/libstdc++-v3/include/tr1/unordered_set
index 1618168..8811d4a 100644
--- a/libstdc++-v3/include/tr1/unordered_set
+++ b/libstdc++-v3/include/tr1/unordered_set
@@ -41,7 +41,7 @@
 #endif
 
 #include <utility>
-#include <algorithm> // lower_bound
+#include <bits/stl_algobase.h>
 #include <bits/allocator.h>
 #include <bits/stl_function.h> // equal_to, _Identity, _Select1st
 #include <bits/stringfwd.h>
diff --git a/libstdc++-v3/include/tr1_impl/hashtable_policy.h b/libstdc++-v3/include/tr1_impl/hashtable_policy.h
index b74531c..f23f8c6 100644
--- a/libstdc++-v3/include/tr1_impl/hashtable_policy.h
+++ b/libstdc++-v3/include/tr1_impl/hashtable_policy.h
@@ -60,6 +60,28 @@ namespace __detail
       return __distance_fw(__first, __last, _Tag());
     }
 
+  template<typename _RAIter, typename _Tp>
+    _RAIter
+    __lower_bound(_RAIter __first, _RAIter __last, const _Tp& __val)
+    {
+      typedef typename std::iterator_traits<_RAIter>::difference_type _DType;
+
+      _DType __len = __last - __first;
+      while (__len > 0)
+	{
+	  _DType __half = __len >> 1;
+	  _RAIter __middle = __first + __half;
+	  if (*__middle < __val)
+	    {
+	      __first = __middle;
+	      ++__first;
+	      __len = __len - __half - 1;
+	    }
+	  else
+	    __len = __half;
+	}
+      return __first;
+    }
 
   // Auxiliary types used for all instantiations of _Hashtable: nodes
   // and iterators.
@@ -423,8 +445,8 @@ namespace __detail
   _Prime_rehash_policy::
   _M_next_bkt(std::size_t __n) const
   {
-    const unsigned long* __p = std::lower_bound(__prime_list, __prime_list
-						+ _S_n_primes, __n);
+    const unsigned long* __p = __lower_bound(__prime_list, __prime_list
+					     + _S_n_primes, __n);
     _M_next_resize = 
       static_cast<std::size_t>(__builtin_ceil(*__p * _M_max_load_factor));
     return *__p;
@@ -437,8 +459,8 @@ namespace __detail
   _M_bkt_for_elements(std::size_t __n) const
   {
     const float __min_bkts = __n / _M_max_load_factor;
-    const unsigned long* __p = std::lower_bound(__prime_list, __prime_list
-						+ _S_n_primes, __min_bkts);
+    const unsigned long* __p = __lower_bound(__prime_list, __prime_list
+					     + _S_n_primes, __min_bkts);
     _M_next_resize =
       static_cast<std::size_t>(__builtin_ceil(*__p * _M_max_load_factor));
     return *__p;
@@ -466,8 +488,8 @@ namespace __detail
 	  {
 	    __min_bkts = std::max(__min_bkts, _M_growth_factor * __n_bkt);
 	    const unsigned long* __p =
-	      std::lower_bound(__prime_list, __prime_list + _S_n_primes,
-			       __min_bkts);
+	      __lower_bound(__prime_list, __prime_list + _S_n_primes,
+			    __min_bkts);
 	    _M_next_resize = static_cast<std::size_t>
 	      (__builtin_ceil(*__p * _M_max_load_factor));
 	    return std::make_pair(true, *__p);