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

git-svn-id: https://llvm.org/svn/llvm-project/libunwind/trunk@352553 91177308-0d34-0410-b5e6-96231b3b80d8

5 files changed, 36 insertions, 34 deletions

diff --git a/CMakeLists.txt b/CMakeLists.txt
index b03adaa..46e7ce1 100644
--- a/CMakeLists.txt
+++ b/CMakeLists.txt
@@ -287,6 +287,9 @@ unwind_append_if(LIBUNWIND_CXX_FLAGS LIBUNWIND_HAS_EHSC_FLAG -EHsc)
 
 unwind_append_if(LIBUNWIND_C_FLAGS LIBUNWIND_HAS_FUNWIND_TABLES -funwind-tables)
 
+# Ensure that we don't depend on C++ standard library.
+unwind_append_if(LIBUNWIND_CXX_FLAGS LIBUNWIND_HAS_NOSTDINCXX_FLAG -nostdinc++)
+
 # Assert
 string(TOUPPER "${CMAKE_BUILD_TYPE}" uppercase_CMAKE_BUILD_TYPE)
 if (LIBUNWIND_ENABLE_ASSERTIONS)
@@ -341,28 +344,6 @@ endif()
 
 include_directories(include)
 
-find_path(
-  LIBUNWIND_LIBCXX_INCLUDES_INTERNAL
-  __libcpp_version
-  PATHS ${LLVM_MAIN_SRC_DIR}/projects/libcxx/include
-        ${LLVM_MAIN_SRC_DIR}/runtimes/libcxx/include
-        ${LLVM_MAIN_SRC_DIR}/../libcxx/include
-  NO_DEFAULT_PATH
-  NO_CMAKE_FIND_ROOT_PATH
-  )
-if ((NOT LIBUNWIND_STANDALONE_BUILD OR HAVE_LIBCXX) AND
-    IS_DIRECTORY "${LIBUNWIND_LIBCXX_INCLUDES_INTERNAL}")
-  set(LIBUNWIND_CXX_INCLUDE_PATHS_DEFAULT "${LIBUNWIND_LIBCXX_INCLUDES_INTERNAL}")
-endif()
-
-set(LIBUNWIND_CXX_INCLUDE_PATHS "${LIBUNWIND_CXX_INCLUDE_PATHS_DEFAULT}" CACHE PATH
-    "Paths to C++ header directories separated by ';'.")
-
-if (NOT LIBUNWIND_CXX_INCLUDE_PATHS STREQUAL "")
-  list(APPEND LIBUNWIND_CXX_FLAGS -nostdinc++)
-  include_directories("${LIBUNWIND_CXX_INCLUDE_PATHS}")
-endif()
-
 add_subdirectory(src)
 
 if (LIBUNWIND_INCLUDE_DOCS)
diff --git a/src/Unwind-EHABI.cpp b/src/Unwind-EHABI.cpp
index 38c7049..c64ca12 100644
--- a/src/Unwind-EHABI.cpp
+++ b/src/Unwind-EHABI.cpp
@@ -20,8 +20,6 @@
 #include <stdlib.h>
 #include <string.h>
 
-#include <type_traits>
-
 #include "config.h"
 #include "libunwind.h"
 #include "libunwind_ext.h"
diff --git a/src/Unwind-seh.cpp b/src/Unwind-seh.cpp
index f55d624..26eb0ef 100644
--- a/src/Unwind-seh.cpp
+++ b/src/Unwind-seh.cpp
@@ -49,6 +49,10 @@ using namespace libunwind;
 /// Class of foreign exceptions based on unrecognized SEH exceptions.
 static const uint64_t kSEHExceptionClass = 0x434C4E4753454800; // CLNGSEH\0
 
+// libunwind does not and should not depend on C++ library which means that we
+// need our own declaration of global placement new.
+void *operator new(size_t, void*);
+
 /// Exception cleanup routine used by \c _GCC_specific_handler to
 /// free foreign exceptions.
 static void seh_exc_cleanup(_Unwind_Reason_Code urc, _Unwind_Exception *exc) {
diff --git a/src/UnwindCursor.hpp b/src/UnwindCursor.hpp
index 497ff84..a830d58 100644
--- a/src/UnwindCursor.hpp
+++ b/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)
diff --git a/src/libunwind.cpp b/src/libunwind.cpp
index a2496a0..cfa9112 100644
--- a/src/libunwind.cpp
+++ b/src/libunwind.cpp
@@ -11,10 +11,6 @@
 
 #include <libunwind.h>
 
-#ifndef NDEBUG
-#include <cstdlib> // getenv
-#endif
-
 #include "libunwind_ext.h"
 #include "config.h"
 
@@ -27,6 +23,10 @@
 
 using namespace libunwind;
 
+// libunwind does not and should not depend on C++ library which means that we
+// need our own declaration of global placement new.
+void *operator new(size_t, void*);
+
 /// internal object to represent this processes address space
 LocalAddressSpace LocalAddressSpace::sThisAddressSpace;