X-Git-Url: https://git.saurik.com/apple/objc4.git/blobdiff_plain/13ba007ef885ec1d079cdb0e881efe5cc776a7d2..1807f628818b6189856744a276064da043a77bac:/runtime/llvm-DenseSet.h

diff --git a/runtime/llvm-DenseSet.h b/runtime/llvm-DenseSet.h
new file mode 100644
index 0000000..45ea107
--- /dev/null
+++ b/runtime/llvm-DenseSet.h
@@ -0,0 +1,293 @@
+//===- llvm/ADT/DenseSet.h - Dense probed hash table ------------*- C++ -*-===//
+//
+//                     The LLVM Compiler Infrastructure
+//
+// This file is distributed under the University of Illinois Open Source
+// License. See LICENSE.TXT for details.
+//
+//===----------------------------------------------------------------------===//
+//
+// This file defines the DenseSet and SmallDenseSet classes.
+//
+//===----------------------------------------------------------------------===//
+
+// Taken from clang-1100.247.11.10.9
+
+#ifndef LLVM_ADT_DENSESET_H
+#define LLVM_ADT_DENSESET_H
+
+#include "llvm-DenseMap.h"
+#include "llvm-DenseMapInfo.h"
+#include "llvm-type_traits.h"
+#include <algorithm>
+#include <cstddef>
+#include <initializer_list>
+#include <iterator>
+#include <utility>
+#include <TargetConditionals.h>
+
+#include "objc-private.h"
+
+namespace objc {
+
+namespace detail {
+
+struct DenseSetEmpty {};
+
+// Use the empty base class trick so we can create a DenseMap where the buckets
+// contain only a single item.
+template <typename KeyT> class DenseSetPair : public DenseSetEmpty {
+  KeyT key;
+
+public:
+  KeyT &getFirst() { return key; }
+  const KeyT &getFirst() const { return key; }
+  DenseSetEmpty &getSecond() { return *this; }
+  const DenseSetEmpty &getSecond() const { return *this; }
+};
+
+/// Base class for DenseSet and DenseSmallSet.
+///
+/// MapTy should be either
+///
+///   DenseMap<ValueT, detail::DenseSetEmpty,
+///            DenseMapValueInfo<detail::DenseSetEmpty>,
+///            ValueInfoT, detail::DenseSetPair<ValueT>>
+///
+/// or the equivalent SmallDenseMap type.  ValueInfoT must implement the
+/// DenseMapInfo "concept".
+template <typename ValueT, typename MapTy, typename ValueInfoT>
+class DenseSetImpl {
+  static_assert(sizeof(typename MapTy::value_type) == sizeof(ValueT),
+                "DenseMap buckets unexpectedly large!");
+  MapTy TheMap;
+
+  template <typename T>
+  using const_arg_type_t = typename const_pointer_or_const_ref<T>::type;
+
+public:
+  using key_type = ValueT;
+  using value_type = ValueT;
+  using size_type = unsigned;
+
+  explicit DenseSetImpl(unsigned InitialReserve = 0) : TheMap(InitialReserve) {}
+
+  DenseSetImpl(std::initializer_list<ValueT> Elems)
+      : DenseSetImpl(PowerOf2Ceil(Elems.size())) {
+    insert(Elems.begin(), Elems.end());
+  }
+
+  bool empty() const { return TheMap.empty(); }
+  size_type size() const { return TheMap.size(); }
+  size_t getMemorySize() const { return TheMap.getMemorySize(); }
+
+  /// Grow the DenseSet so that it has at least Size buckets. Will not shrink
+  /// the Size of the set.
+  void resize(size_t Size) { TheMap.resize(Size); }
+
+  /// Grow the DenseSet so that it can contain at least \p NumEntries items
+  /// before resizing again.
+  void reserve(size_t Size) { TheMap.reserve(Size); }
+
+  void clear() {
+    TheMap.clear();
+  }
+
+  /// Return 1 if the specified key is in the set, 0 otherwise.
+  size_type count(const_arg_type_t<ValueT> V) const {
+    return TheMap.count(V);
+  }
+
+  bool erase(const ValueT &V) {
+    return TheMap.erase(V);
+  }
+
+  void swap(DenseSetImpl &RHS) { TheMap.swap(RHS.TheMap); }
+
+  // Iterators.
+
+  class ConstIterator;
+
+  class Iterator {
+    typename MapTy::iterator I;
+    friend class DenseSetImpl;
+    friend class ConstIterator;
+
+  public:
+    using difference_type = typename MapTy::iterator::difference_type;
+    using value_type = ValueT;
+    using pointer = value_type *;
+    using reference = value_type &;
+    using iterator_category = std::forward_iterator_tag;
+
+    Iterator() = default;
+    Iterator(const typename MapTy::iterator &i) : I(i) {}
+
+    ValueT &operator*() { return I->getFirst(); }
+    const ValueT &operator*() const { return I->getFirst(); }
+    ValueT *operator->() { return &I->getFirst(); }
+    const ValueT *operator->() const { return &I->getFirst(); }
+
+    Iterator& operator++() { ++I; return *this; }
+    Iterator operator++(int) { auto T = *this; ++I; return T; }
+    bool operator==(const ConstIterator& X) const { return I == X.I; }
+    bool operator!=(const ConstIterator& X) const { return I != X.I; }
+  };
+
+  class ConstIterator {
+    typename MapTy::const_iterator I;
+    friend class DenseSet;
+    friend class Iterator;
+
+  public:
+    using difference_type = typename MapTy::const_iterator::difference_type;
+    using value_type = ValueT;
+    using pointer = const value_type *;
+    using reference = const value_type &;
+    using iterator_category = std::forward_iterator_tag;
+
+    ConstIterator() = default;
+    ConstIterator(const Iterator &B) : I(B.I) {}
+    ConstIterator(const typename MapTy::const_iterator &i) : I(i) {}
+
+    const ValueT &operator*() const { return I->getFirst(); }
+    const ValueT *operator->() const { return &I->getFirst(); }
+
+    ConstIterator& operator++() { ++I; return *this; }
+    ConstIterator operator++(int) { auto T = *this; ++I; return T; }
+    bool operator==(const ConstIterator& X) const { return I == X.I; }
+    bool operator!=(const ConstIterator& X) const { return I != X.I; }
+  };
+
+  using iterator = Iterator;
+  using const_iterator = ConstIterator;
+
+  iterator begin() { return Iterator(TheMap.begin()); }
+  iterator end() { return Iterator(TheMap.end()); }
+
+  const_iterator begin() const { return ConstIterator(TheMap.begin()); }
+  const_iterator end() const { return ConstIterator(TheMap.end()); }
+
+  iterator find(const_arg_type_t<ValueT> V) { return Iterator(TheMap.find(V)); }
+  const_iterator find(const_arg_type_t<ValueT> V) const {
+    return ConstIterator(TheMap.find(V));
+  }
+
+  /// Alternative version of find() which allows a different, and possibly less
+  /// expensive, key type.
+  /// The DenseMapInfo is responsible for supplying methods
+  /// getHashValue(LookupKeyT) and isEqual(LookupKeyT, KeyT) for each key type
+  /// used.
+  template <class LookupKeyT>
+  iterator find_as(const LookupKeyT &Val) {
+    return Iterator(TheMap.find_as(Val));
+  }
+  template <class LookupKeyT>
+  const_iterator find_as(const LookupKeyT &Val) const {
+    return ConstIterator(TheMap.find_as(Val));
+  }
+
+  void erase(Iterator I) { return TheMap.erase(I.I); }
+  void erase(ConstIterator CI) { return TheMap.erase(CI.I); }
+
+  std::pair<iterator, bool> insert(const ValueT &V) {
+    detail::DenseSetEmpty Empty;
+    return TheMap.try_emplace(V, Empty);
+  }
+
+  std::pair<iterator, bool> insert(ValueT &&V) {
+    detail::DenseSetEmpty Empty;
+    return TheMap.try_emplace(std::move(V), Empty);
+  }
+
+  /// Alternative version of insert that uses a different (and possibly less
+  /// expensive) key type.
+  template <typename LookupKeyT>
+  std::pair<iterator, bool> insert_as(const ValueT &V,
+                                      const LookupKeyT &LookupKey) {
+    return TheMap.insert_as({V, detail::DenseSetEmpty()}, LookupKey);
+  }
+  template <typename LookupKeyT>
+  std::pair<iterator, bool> insert_as(ValueT &&V, const LookupKeyT &LookupKey) {
+    return TheMap.insert_as({std::move(V), detail::DenseSetEmpty()}, LookupKey);
+  }
+
+  // Range insertion of values.
+  template<typename InputIt>
+  void insert(InputIt I, InputIt E) {
+    for (; I != E; ++I)
+      insert(*I);
+  }
+};
+
+/// Equality comparison for DenseSet.
+///
+/// Iterates over elements of LHS confirming that each element is also a member
+/// of RHS, and that RHS contains no additional values.
+/// Equivalent to N calls to RHS.count. Amortized complexity is linear, worst
+/// case is O(N^2) (if every hash collides).
+template <typename ValueT, typename MapTy, typename ValueInfoT>
+bool operator==(const DenseSetImpl<ValueT, MapTy, ValueInfoT> &LHS,
+                const DenseSetImpl<ValueT, MapTy, ValueInfoT> &RHS) {
+  if (LHS.size() != RHS.size())
+    return false;
+
+  for (auto &E : LHS)
+    if (!RHS.count(E))
+      return false;
+
+  return true;
+}
+
+/// Inequality comparison for DenseSet.
+///
+/// Equivalent to !(LHS == RHS). See operator== for performance notes.
+template <typename ValueT, typename MapTy, typename ValueInfoT>
+bool operator!=(const DenseSetImpl<ValueT, MapTy, ValueInfoT> &LHS,
+                const DenseSetImpl<ValueT, MapTy, ValueInfoT> &RHS) {
+  return !(LHS == RHS);
+}
+
+} // end namespace detail
+
+/// Implements a dense probed hash-table based set.
+template <typename ValueT, typename ValueInfoT = DenseMapInfo<ValueT>>
+class DenseSet : public detail::DenseSetImpl<
+                     ValueT, DenseMap<ValueT, detail::DenseSetEmpty,
+                                      DenseMapValueInfo<detail::DenseSetEmpty>,
+                                      ValueInfoT, detail::DenseSetPair<ValueT>>,
+                     ValueInfoT> {
+  using BaseT =
+      detail::DenseSetImpl<ValueT,
+                           DenseMap<ValueT, detail::DenseSetEmpty,
+                                    DenseMapValueInfo<detail::DenseSetEmpty>,
+                                    ValueInfoT, detail::DenseSetPair<ValueT>>,
+                           ValueInfoT>;
+
+public:
+  using BaseT::BaseT;
+};
+
+/// Implements a dense probed hash-table based set with some number of buckets
+/// stored inline.
+template <typename ValueT, unsigned InlineBuckets = 4,
+          typename ValueInfoT = DenseMapInfo<ValueT>>
+class SmallDenseSet
+    : public detail::DenseSetImpl<
+          ValueT, SmallDenseMap<ValueT, detail::DenseSetEmpty, InlineBuckets,
+                                DenseMapValueInfo<detail::DenseSetEmpty>,
+                                ValueInfoT, detail::DenseSetPair<ValueT>>,
+          ValueInfoT> {
+  using BaseT = detail::DenseSetImpl<
+      ValueT, SmallDenseMap<ValueT, detail::DenseSetEmpty, InlineBuckets,
+                            DenseMapValueInfo<detail::DenseSetEmpty>,
+                            ValueInfoT, detail::DenseSetPair<ValueT>>,
+      ValueInfoT>;
+
+public:
+  using BaseT::BaseT;
+};
+
+} // end namespace objc
+
+#endif // LLVM_ADT_DENSESET_H