Drop the dependency on <algorithm>, add placement new inline

We haven't eliminated C++ library dependency altogether in D57251,
UnwindCursor.hpp had an unused dependency on <algorithm> which was
pulling in other C++ headers. Removing that dependency also revealed
(correctly) that we need our own global placement new declaration. Now
libunwind should be independent of the C++ library.

Differential Revision: https://reviews.llvm.org/D57262

llvm-svn: 352553

1 files changed, 25 insertions, 6 deletions

diff --git a/libunwind/src/UnwindCursor.hpp b/libunwind/src/UnwindCursor.hpp
index 497ff84552de..a830d5840af8 100644
--- a/libunwind/src/UnwindCursor.hpp
+++ b/libunwind/src/UnwindCursor.hpp
@@ -11,7 +11,6 @@
 #ifndef __UNWINDCURSOR_HPP__
 #define __UNWINDCURSOR_HPP__
 
-#include <algorithm>
 #include <stdint.h>
 #include <stdio.h>
 #include <stdlib.h>
@@ -105,7 +104,6 @@ private:
   static void dyldUnloadHook(const struct mach_header *mh, intptr_t slide);
   static bool _registeredForDyldUnloads;
 #endif
-  // Can't use std::vector<> here because this code is below libc++.
   static entry *_buffer;
   static entry *_bufferUsed;
   static entry *_bufferEnd;
@@ -1225,7 +1223,6 @@ template<typename A>
 struct EHABISectionIterator {
   typedef EHABISectionIterator _Self;
 
-  typedef std::random_access_iterator_tag iterator_category;
   typedef typename A::pint_t value_type;
   typedef typename A::pint_t* pointer;
   typedef typename A::pint_t& reference;
@@ -1279,6 +1276,29 @@ struct EHABISectionIterator {
   const UnwindInfoSections* _sects;
 };
 
+namespace {
+
+template <typename A>
+EHABISectionIterator<A> EHABISectionUpperBound(
+    EHABISectionIterator<A> first,
+    EHABISectionIterator<A> last,
+    typename A::pint_t value) {
+  size_t len = last - first;
+  while (len > 0) {
+    size_t l2 = len / 2;
+    EHABISectionIterator<A> m = first + l2;
+    if (value < *m) {
+        len = l2;
+    } else {
+        first = ++m;
+        len -= l2 + 1;
+    }
+  }
+  return first;
+}
+
+}
+
 template <typename A, typename R>
 bool UnwindCursor<A, R>::getInfoFromEHABISection(
     pint_t pc,
@@ -1290,7 +1310,7 @@ bool UnwindCursor<A, R>::getInfoFromEHABISection(
   if (begin == end)
     return false;
 
-  EHABISectionIterator<A> itNextPC = std::upper_bound(begin, end, pc);
+  EHABISectionIterator<A> itNextPC = EHABISectionUpperBound(begin, end, pc);
   if (itNextPC == begin)
     return false;
   EHABISectionIterator<A> itThisPC = itNextPC - 1;
@@ -1300,8 +1320,7 @@ bool UnwindCursor<A, R>::getInfoFromEHABISection(
   // in the table, we don't really know the function extent and have to choose a
   // value for nextPC. Choosing max() will allow the range check during trace to
   // succeed.
-  pint_t nextPC = (itNextPC == end) ? std::numeric_limits<pint_t>::max()
-                                    : itNextPC.functionAddress();
+  pint_t nextPC = (itNextPC == end) ? UINTPTR_MAX : itNextPC.functionAddress();
   pint_t indexDataAddr = itThisPC.dataAddress();
 
   if (indexDataAddr == 0)