Subversion Repositories QNX 8.QNX8 LLVM/Clang compiler suite

//===- llvm/ADT/SetVector.h - Set with insert order iteration ---*- C++ -*-===//

//

// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.

// See https://llvm.org/LICENSE.txt for license information.

// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception

//

//===----------------------------------------------------------------------===//

///

/// \file

/// This file implements a set that has insertion order iteration

/// characteristics. This is useful for keeping a set of things that need to be

/// visited later but in a deterministic order (insertion order). The interface

/// is purposefully minimal.

///

/// This file defines SetVector and SmallSetVector, which performs no

/// allocations if the SetVector has less than a certain number of elements.

///

//===----------------------------------------------------------------------===//

#ifndef LLVM_ADT_SETVECTOR_H

#define LLVM_ADT_SETVECTOR_H

#include "llvm/ADT/ArrayRef.h"

#include "llvm/ADT/DenseSet.h"

#include "llvm/ADT/STLExtras.h"

#include "llvm/Support/Compiler.h"

#include <cassert>

#include <iterator>

#include <vector>

namespace llvm {

/// A vector that has set insertion semantics.

///

/// This adapter class provides a way to keep a set of things that also has the

/// property of a deterministic iteration order. The order of iteration is the

/// order of insertion.

template <typename T, typename Vector = std::vector<T>,

          typename Set = DenseSet<T>>

class SetVector {

public:

  using value_type = T;

  using key_type = T;

  using reference = T&;

  using const_reference = const T&;

  using set_type = Set;

  using vector_type = Vector;

  using iterator = typename vector_type::const_iterator;

  using const_iterator = typename vector_type::const_iterator;

  using reverse_iterator = typename vector_type::const_reverse_iterator;

  using const_reverse_iterator = typename vector_type::const_reverse_iterator;

  using size_type = typename vector_type::size_type;

  /// Construct an empty SetVector

  SetVector() = default;

  /// Initialize a SetVector with a range of elements

  template<typename It>

  SetVector(It Start, It End) {

    insert(Start, End);

  }

  ArrayRef<T> getArrayRef() const { return vector_; }

  /// Clear the SetVector and return the underlying vector.

  Vector takeVector() {

    set_.clear();

    return std::move(vector_);

  }

  /// Determine if the SetVector is empty or not.

  bool empty() const {

    return vector_.empty();

  }

  /// Determine the number of elements in the SetVector.

  size_type size() const {

    return vector_.size();

  }

  /// Get an iterator to the beginning of the SetVector.

  iterator begin() {

    return vector_.begin();

  }

  /// Get a const_iterator to the beginning of the SetVector.

  const_iterator begin() const {

    return vector_.begin();

  }

  /// Get an iterator to the end of the SetVector.

  iterator end() {

    return vector_.end();

  }

  /// Get a const_iterator to the end of the SetVector.

  const_iterator end() const {

    return vector_.end();

  }

  /// Get an reverse_iterator to the end of the SetVector.

  reverse_iterator rbegin() {

    return vector_.rbegin();

  }

  /// Get a const_reverse_iterator to the end of the SetVector.

  const_reverse_iterator rbegin() const {

    return vector_.rbegin();

  }

  /// Get a reverse_iterator to the beginning of the SetVector.

  reverse_iterator rend() {

    return vector_.rend();

  }

  /// Get a const_reverse_iterator to the beginning of the SetVector.

  const_reverse_iterator rend() const {

    return vector_.rend();

  }

  /// Return the first element of the SetVector.

  const T &front() const {

    assert(!empty() && "Cannot call front() on empty SetVector!");

    return vector_.front();

  }

  /// Return the last element of the SetVector.

  const T &back() const {

    assert(!empty() && "Cannot call back() on empty SetVector!");

    return vector_.back();

  }

  /// Index into the SetVector.

  const_reference operator[](size_type n) const {

    assert(n < vector_.size() && "SetVector access out of range!");

    return vector_[n];

  }

  /// Insert a new element into the SetVector.

  /// \returns true if the element was inserted into the SetVector.

  bool insert(const value_type &X) {

    bool result = set_.insert(X).second;

    if (result)

      vector_.push_back(X);

    return result;

  }

  /// Insert a range of elements into the SetVector.

  template<typename It>

  void insert(It Start, It End) {

    for (; Start != End; ++Start)

      if (set_.insert(*Start).second)

        vector_.push_back(*Start);

  }

  /// Remove an item from the set vector.

  bool remove(const value_type& X) {

    if (set_.erase(X)) {

      typename vector_type::iterator I = find(vector_, X);

      assert(I != vector_.end() && "Corrupted SetVector instances!");

      vector_.erase(I);

      return true;

    }

    return false;

  }

  /// Erase a single element from the set vector.

  /// \returns an iterator pointing to the next element that followed the

  /// element erased. This is the end of the SetVector if the last element is

  /// erased.

  iterator erase(const_iterator I) {

    const key_type &V = *I;

    assert(set_.count(V) && "Corrupted SetVector instances!");

    set_.erase(V);

    return vector_.erase(I);

  }

  /// Remove items from the set vector based on a predicate function.

  ///

  /// This is intended to be equivalent to the following code, if we could

  /// write it:

  ///

  /// \code

  ///   V.erase(remove_if(V, P), V.end());

  /// \endcode

  ///

  /// However, SetVector doesn't expose non-const iterators, making any

  /// algorithm like remove_if impossible to use.

  ///

  /// \returns true if any element is removed.

  template <typename UnaryPredicate>

  bool remove_if(UnaryPredicate P) {

    typename vector_type::iterator I =

        llvm::remove_if(vector_, TestAndEraseFromSet<UnaryPredicate>(P, set_));

    if (I == vector_.end())

      return false;

    vector_.erase(I, vector_.end());

    return true;

  }

  /// Check if the SetVector contains the given key.

  bool contains(const key_type &key) const {

    return set_.find(key) != set_.end();

  }

  /// Count the number of elements of a given key in the SetVector.

  /// \returns 0 if the element is not in the SetVector, 1 if it is.

  size_type count(const key_type &key) const {

    return set_.count(key);

  }

  /// Completely clear the SetVector

  void clear() {

    set_.clear();

    vector_.clear();

  }

  /// Remove the last element of the SetVector.

  void pop_back() {

    assert(!empty() && "Cannot remove an element from an empty SetVector!");

    set_.erase(back());

    vector_.pop_back();

  }

  [[nodiscard]] T pop_back_val() {

    T Ret = back();

    pop_back();

    return Ret;

  }

  bool operator==(const SetVector &that) const {

    return vector_ == that.vector_;

  }

  bool operator!=(const SetVector &that) const {

    return vector_ != that.vector_;

  }

  /// Compute This := This u S, return whether 'This' changed.

  /// TODO: We should be able to use set_union from SetOperations.h, but

  ///       SetVector interface is inconsistent with DenseSet.

  template <class STy>

  bool set_union(const STy &S) {

    bool Changed = false;

    for (typename STy::const_iterator SI = S.begin(), SE = S.end(); SI != SE;

         ++SI)

      if (insert(*SI))

        Changed = true;

    return Changed;

  }

  /// Compute This := This - B

  /// TODO: We should be able to use set_subtract from SetOperations.h, but

  ///       SetVector interface is inconsistent with DenseSet.

  template <class STy>

  void set_subtract(const STy &S) {

    for (typename STy::const_iterator SI = S.begin(), SE = S.end(); SI != SE;

         ++SI)

      remove(*SI);

  }

  void swap(SetVector<T, Vector, Set> &RHS) {

    set_.swap(RHS.set_);

    vector_.swap(RHS.vector_);

  }

private:

  /// A wrapper predicate designed for use with std::remove_if.

  ///

  /// This predicate wraps a predicate suitable for use with std::remove_if to

  /// call set_.erase(x) on each element which is slated for removal.

  template <typename UnaryPredicate>

  class TestAndEraseFromSet {

    UnaryPredicate P;

    set_type &set_;

  public:

    TestAndEraseFromSet(UnaryPredicate P, set_type &set_)

        : P(std::move(P)), set_(set_) {}

    template <typename ArgumentT>

    bool operator()(const ArgumentT &Arg) {

      if (P(Arg)) {

        set_.erase(Arg);

        return true;

      }

      return false;

    }

  };

  set_type set_;         ///< The set.

  vector_type vector_;   ///< The vector.

};

/// A SetVector that performs no allocations if smaller than

/// a certain size.

template <typename T, unsigned N>

class SmallSetVector

    : public SetVector<T, SmallVector<T, N>, SmallDenseSet<T, N>> {

public:

  SmallSetVector() = default;

  /// Initialize a SmallSetVector with a range of elements

  template<typename It>

  SmallSetVector(It Start, It End) {

    this->insert(Start, End);

  }

};

} // end namespace llvm

namespace std {

/// Implement std::swap in terms of SetVector swap.

template<typename T, typename V, typename S>

inline void

swap(llvm::SetVector<T, V, S> &LHS, llvm::SetVector<T, V, S> &RHS) {

  LHS.swap(RHS);

}

/// Implement std::swap in terms of SmallSetVector swap.

template<typename T, unsigned N>

inline void

swap(llvm::SmallSetVector<T, N> &LHS, llvm::SmallSetVector<T, N> &RHS) {

  LHS.swap(RHS);

}

} // end namespace std

#endif // LLVM_ADT_SETVECTOR_H