Subversion Repositories QNX 8.QNX8 LLVM/Clang compiler suite

//===- llvm/ADT/SmallPtrSet.h - 'Normally small' pointer set ----*- 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 defines the SmallPtrSet class.  See the doxygen comment for

/// SmallPtrSetImplBase for more details on the algorithm used.

//

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

#ifndef LLVM_ADT_SMALLPTRSET_H

#define LLVM_ADT_SMALLPTRSET_H

#include "llvm/ADT/EpochTracker.h"

#include "llvm/Support/Compiler.h"

#include "llvm/Support/ReverseIteration.h"

#include "llvm/Support/type_traits.h"

#include <cassert>

#include <cstddef>

#include <cstdlib>

#include <cstring>

#include <initializer_list>

#include <iterator>

#include <utility>

namespace llvm {

/// SmallPtrSetImplBase - This is the common code shared among all the

/// SmallPtrSet<>'s, which is almost everything.  SmallPtrSet has two modes, one

/// for small and one for large sets.

///

/// Small sets use an array of pointers allocated in the SmallPtrSet object,

/// which is treated as a simple array of pointers.  When a pointer is added to

/// the set, the array is scanned to see if the element already exists, if not

/// the element is 'pushed back' onto the array.  If we run out of space in the

/// array, we grow into the 'large set' case.  SmallSet should be used when the

/// sets are often small.  In this case, no memory allocation is used, and only

/// light-weight and cache-efficient scanning is used.

///

/// Large sets use a classic exponentially-probed hash table.  Empty buckets are

/// represented with an illegal pointer value (-1) to allow null pointers to be

/// inserted.  Tombstones are represented with another illegal pointer value

/// (-2), to allow deletion.  The hash table is resized when the table is 3/4 or

/// more.  When this happens, the table is doubled in size.

///

class SmallPtrSetImplBase : public DebugEpochBase {

  friend class SmallPtrSetIteratorImpl;

protected:

  /// SmallArray - Points to a fixed size set of buckets, used in 'small mode'.

  const void **SmallArray;

  /// CurArray - This is the current set of buckets.  If equal to SmallArray,

  /// then the set is in 'small mode'.

  const void **CurArray;

  /// CurArraySize - The allocated size of CurArray, always a power of two.

  unsigned CurArraySize;

  /// Number of elements in CurArray that contain a value or are a tombstone.

  /// If small, all these elements are at the beginning of CurArray and the rest

  /// is uninitialized.

  unsigned NumNonEmpty;

  /// Number of tombstones in CurArray.

  unsigned NumTombstones;

  // Helpers to copy and move construct a SmallPtrSet.

  SmallPtrSetImplBase(const void **SmallStorage,

                      const SmallPtrSetImplBase &that);

  SmallPtrSetImplBase(const void **SmallStorage, unsigned SmallSize,

                      SmallPtrSetImplBase &&that);

  explicit SmallPtrSetImplBase(const void **SmallStorage, unsigned SmallSize)

      : SmallArray(SmallStorage), CurArray(SmallStorage),

        CurArraySize(SmallSize), NumNonEmpty(0), NumTombstones(0) {

    assert(SmallSize && (SmallSize & (SmallSize-1)) == 0 &&

           "Initial size must be a power of two!");

  }

  ~SmallPtrSetImplBase() {

    if (!isSmall())

      free(CurArray);

  }

public:

  using size_type = unsigned;

  SmallPtrSetImplBase &operator=(const SmallPtrSetImplBase &) = delete;

  [[nodiscard]] bool empty() const { return size() == 0; }

  size_type size() const { return NumNonEmpty - NumTombstones; }

  void clear() {

    incrementEpoch();

    // If the capacity of the array is huge, and the # elements used is small,

    // shrink the array.

    if (!isSmall()) {

      if (size() * 4 < CurArraySize && CurArraySize > 32)

        return shrink_and_clear();

      // Fill the array with empty markers.

      memset(CurArray, -1, CurArraySize * sizeof(void *));

    }

    NumNonEmpty = 0;

    NumTombstones = 0;

  }

protected:

  static void *getTombstoneMarker() { return reinterpret_cast<void*>(-2); }

  static void *getEmptyMarker() {

    // Note that -1 is chosen to make clear() efficiently implementable with

    // memset and because it's not a valid pointer value.

    return reinterpret_cast<void*>(-1);

  }

  const void **EndPointer() const {

    return isSmall() ? CurArray + NumNonEmpty : CurArray + CurArraySize;

  }

  /// insert_imp - This returns true if the pointer was new to the set, false if

  /// it was already in the set.  This is hidden from the client so that the

  /// derived class can check that the right type of pointer is passed in.

  std::pair<const void *const *, bool> insert_imp(const void *Ptr) {

    if (isSmall()) {

      // Check to see if it is already in the set.

      const void **LastTombstone = nullptr;

      for (const void **APtr = SmallArray, **E = SmallArray + NumNonEmpty;

           APtr != E; ++APtr) {

        const void *Value = *APtr;

        if (Value == Ptr)

          return std::make_pair(APtr, false);

        if (Value == getTombstoneMarker())

          LastTombstone = APtr;

      }

      // Did we find any tombstone marker?

      if (LastTombstone != nullptr) {

        *LastTombstone = Ptr;

        --NumTombstones;

        incrementEpoch();

        return std::make_pair(LastTombstone, true);

      }

      // Nope, there isn't.  If we stay small, just 'pushback' now.

      if (NumNonEmpty < CurArraySize) {

        SmallArray[NumNonEmpty++] = Ptr;

        incrementEpoch();

        return std::make_pair(SmallArray + (NumNonEmpty - 1), true);

      }

      // Otherwise, hit the big set case, which will call grow.

    }

    return insert_imp_big(Ptr);

  }

  /// erase_imp - If the set contains the specified pointer, remove it and

  /// return true, otherwise return false.  This is hidden from the client so

  /// that the derived class can check that the right type of pointer is passed

  /// in.

  bool erase_imp(const void * Ptr) {

    const void *const *P = find_imp(Ptr);

    if (P == EndPointer())

      return false;

    const void **Loc = const_cast<const void **>(P);

    assert(*Loc == Ptr && "broken find!");

    *Loc = getTombstoneMarker();

    NumTombstones++;

    return true;

  }

  /// Returns the raw pointer needed to construct an iterator.  If element not

  /// found, this will be EndPointer.  Otherwise, it will be a pointer to the

  /// slot which stores Ptr;

  const void *const * find_imp(const void * Ptr) const {

    if (isSmall()) {

      // Linear search for the item.

      for (const void *const *APtr = SmallArray,

                      *const *E = SmallArray + NumNonEmpty; APtr != E; ++APtr)

        if (*APtr == Ptr)

          return APtr;

      return EndPointer();

    }

    // Big set case.

    auto *Bucket = FindBucketFor(Ptr);

    if (*Bucket == Ptr)

      return Bucket;

    return EndPointer();

  }

private:

  bool isSmall() const { return CurArray == SmallArray; }

  std::pair<const void *const *, bool> insert_imp_big(const void *Ptr);

  const void * const *FindBucketFor(const void *Ptr) const;

  void shrink_and_clear();

  /// Grow - Allocate a larger backing store for the buckets and move it over.

  void Grow(unsigned NewSize);

protected:

  /// swap - Swaps the elements of two sets.

  /// Note: This method assumes that both sets have the same small size.

  void swap(SmallPtrSetImplBase &RHS);

  void CopyFrom(const SmallPtrSetImplBase &RHS);

  void MoveFrom(unsigned SmallSize, SmallPtrSetImplBase &&RHS);

private:

  /// Code shared by MoveFrom() and move constructor.

  void MoveHelper(unsigned SmallSize, SmallPtrSetImplBase &&RHS);

  /// Code shared by CopyFrom() and copy constructor.

  void CopyHelper(const SmallPtrSetImplBase &RHS);

};

/// SmallPtrSetIteratorImpl - This is the common base class shared between all

/// instances of SmallPtrSetIterator.

class SmallPtrSetIteratorImpl {

protected:

  const void *const *Bucket;

  const void *const *End;

public:

  explicit SmallPtrSetIteratorImpl(const void *const *BP, const void*const *E)

    : Bucket(BP), End(E) {

    if (shouldReverseIterate()) {

      RetreatIfNotValid();

      return;

    }

    AdvanceIfNotValid();

  }

  bool operator==(const SmallPtrSetIteratorImpl &RHS) const {

    return Bucket == RHS.Bucket;

  }

  bool operator!=(const SmallPtrSetIteratorImpl &RHS) const {

    return Bucket != RHS.Bucket;

  }

protected:

  /// AdvanceIfNotValid - If the current bucket isn't valid, advance to a bucket

  /// that is.   This is guaranteed to stop because the end() bucket is marked

  /// valid.

  void AdvanceIfNotValid() {

    assert(Bucket <= End);

    while (Bucket != End &&

           (*Bucket == SmallPtrSetImplBase::getEmptyMarker() ||

            *Bucket == SmallPtrSetImplBase::getTombstoneMarker()))

      ++Bucket;

  }

  void RetreatIfNotValid() {

    assert(Bucket >= End);

    while (Bucket != End &&

           (Bucket[-1] == SmallPtrSetImplBase::getEmptyMarker() ||

            Bucket[-1] == SmallPtrSetImplBase::getTombstoneMarker())) {

      --Bucket;

    }

  }

};

/// SmallPtrSetIterator - This implements a const_iterator for SmallPtrSet.

template <typename PtrTy>

class SmallPtrSetIterator : public SmallPtrSetIteratorImpl,

                            DebugEpochBase::HandleBase {

  using PtrTraits = PointerLikeTypeTraits<PtrTy>;

public:

  using value_type = PtrTy;

  using reference = PtrTy;

  using pointer = PtrTy;

  using difference_type = std::ptrdiff_t;

  using iterator_category = std::forward_iterator_tag;

  explicit SmallPtrSetIterator(const void *const *BP, const void *const *E,

                               const DebugEpochBase &Epoch)

      : SmallPtrSetIteratorImpl(BP, E), DebugEpochBase::HandleBase(&Epoch) {}

  // Most methods are provided by the base class.

  const PtrTy operator*() const {

    assert(isHandleInSync() && "invalid iterator access!");

    if (shouldReverseIterate()) {

      assert(Bucket > End);

      return PtrTraits::getFromVoidPointer(const_cast<void *>(Bucket[-1]));

    }

    assert(Bucket < End);

    return PtrTraits::getFromVoidPointer(const_cast<void*>(*Bucket));

  }

  inline SmallPtrSetIterator& operator++() {          // Preincrement

    assert(isHandleInSync() && "invalid iterator access!");

    if (shouldReverseIterate()) {

      --Bucket;

      RetreatIfNotValid();

      return *this;

    }

    ++Bucket;

    AdvanceIfNotValid();

    return *this;

  }

  SmallPtrSetIterator operator++(int) {        // Postincrement

    SmallPtrSetIterator tmp = *this;

    ++*this;

    return tmp;

  }

};

/// RoundUpToPowerOfTwo - This is a helper template that rounds N up to the next

/// power of two (which means N itself if N is already a power of two).

template<unsigned N>

struct RoundUpToPowerOfTwo;

/// RoundUpToPowerOfTwoH - If N is not a power of two, increase it.  This is a

/// helper template used to implement RoundUpToPowerOfTwo.

template<unsigned N, bool isPowerTwo>

struct RoundUpToPowerOfTwoH {

  enum { Val = N };

};

template<unsigned N>

struct RoundUpToPowerOfTwoH<N, false> {

  enum {

    // We could just use NextVal = N+1, but this converges faster.  N|(N-1) sets

    // the right-most zero bits to one all at once, e.g. 0b0011000 -> 0b0011111.

    Val = RoundUpToPowerOfTwo<(N|(N-1)) + 1>::Val

  };

};

template<unsigned N>

struct RoundUpToPowerOfTwo {

  enum { Val = RoundUpToPowerOfTwoH<N, (N&(N-1)) == 0>::Val };

};

/// A templated base class for \c SmallPtrSet which provides the

/// typesafe interface that is common across all small sizes.

///

/// This is particularly useful for passing around between interface boundaries

/// to avoid encoding a particular small size in the interface boundary.

template <typename PtrType>

class SmallPtrSetImpl : public SmallPtrSetImplBase {

  using ConstPtrType = typename add_const_past_pointer<PtrType>::type;

  using PtrTraits = PointerLikeTypeTraits<PtrType>;

  using ConstPtrTraits = PointerLikeTypeTraits<ConstPtrType>;

protected:

  // Forward constructors to the base.

  using SmallPtrSetImplBase::SmallPtrSetImplBase;

public:

  using iterator = SmallPtrSetIterator<PtrType>;

  using const_iterator = SmallPtrSetIterator<PtrType>;

  using key_type = ConstPtrType;

  using value_type = PtrType;

  SmallPtrSetImpl(const SmallPtrSetImpl &) = delete;

  /// Inserts Ptr if and only if there is no element in the container equal to

  /// Ptr. The bool component of the returned pair is true if and only if the

  /// insertion takes place, and the iterator component of the pair points to

  /// the element equal to Ptr.

  std::pair<iterator, bool> insert(PtrType Ptr) {

    auto p = insert_imp(PtrTraits::getAsVoidPointer(Ptr));

    return std::make_pair(makeIterator(p.first), p.second);

  }

  /// Insert the given pointer with an iterator hint that is ignored. This is

  /// identical to calling insert(Ptr), but allows SmallPtrSet to be used by

  /// std::insert_iterator and std::inserter().

  iterator insert(iterator, PtrType Ptr) {

    return insert(Ptr).first;

  }

  /// erase - If the set contains the specified pointer, remove it and return

  /// true, otherwise return false.

  bool erase(PtrType Ptr) {

    return erase_imp(PtrTraits::getAsVoidPointer(Ptr));

  }

  /// count - Return 1 if the specified pointer is in the set, 0 otherwise.

  size_type count(ConstPtrType Ptr) const {

    return find_imp(ConstPtrTraits::getAsVoidPointer(Ptr)) != EndPointer();

  }

  iterator find(ConstPtrType Ptr) const {

    return makeIterator(find_imp(ConstPtrTraits::getAsVoidPointer(Ptr)));

  }

  bool contains(ConstPtrType Ptr) const {

    return find_imp(ConstPtrTraits::getAsVoidPointer(Ptr)) != EndPointer();

  }

  template <typename IterT>

  void insert(IterT I, IterT E) {

    for (; I != E; ++I)

      insert(*I);

  }

  void insert(std::initializer_list<PtrType> IL) {

    insert(IL.begin(), IL.end());

  }

  iterator begin() const {

    if (shouldReverseIterate())

      return makeIterator(EndPointer() - 1);

    return makeIterator(CurArray);

  }

  iterator end() const { return makeIterator(EndPointer()); }

private:

  /// Create an iterator that dereferences to same place as the given pointer.

  iterator makeIterator(const void *const *P) const {

    if (shouldReverseIterate())

      return iterator(P == EndPointer() ? CurArray : P + 1, CurArray, *this);

    return iterator(P, EndPointer(), *this);

  }

};

/// Equality comparison for SmallPtrSet.

///

/// Iterates over elements of LHS confirming that each value from LHS is also in

/// RHS, and that no additional values are in RHS.

template <typename PtrType>

bool operator==(const SmallPtrSetImpl<PtrType> &LHS,

                const SmallPtrSetImpl<PtrType> &RHS) {

  if (LHS.size() != RHS.size())

    return false;

  for (const auto *KV : LHS)

    if (!RHS.count(KV))

      return false;

  return true;

}

/// Inequality comparison for SmallPtrSet.

///

/// Equivalent to !(LHS == RHS).

template <typename PtrType>

bool operator!=(const SmallPtrSetImpl<PtrType> &LHS,

                const SmallPtrSetImpl<PtrType> &RHS) {

  return !(LHS == RHS);

}

/// SmallPtrSet - This class implements a set which is optimized for holding

/// SmallSize or less elements.  This internally rounds up SmallSize to the next

/// power of two if it is not already a power of two.  See the comments above

/// SmallPtrSetImplBase for details of the algorithm.

template<class PtrType, unsigned SmallSize>

class SmallPtrSet : public SmallPtrSetImpl<PtrType> {

  // In small mode SmallPtrSet uses linear search for the elements, so it is

  // not a good idea to choose this value too high. You may consider using a

  // DenseSet<> instead if you expect many elements in the set.

  static_assert(SmallSize <= 32, "SmallSize should be small");

  using BaseT = SmallPtrSetImpl<PtrType>;

  // Make sure that SmallSize is a power of two, round up if not.

  enum { SmallSizePowTwo = RoundUpToPowerOfTwo<SmallSize>::Val };

  /// SmallStorage - Fixed size storage used in 'small mode'.

  const void *SmallStorage[SmallSizePowTwo];

public:

  SmallPtrSet() : BaseT(SmallStorage, SmallSizePowTwo) {}

  SmallPtrSet(const SmallPtrSet &that) : BaseT(SmallStorage, that) {}

  SmallPtrSet(SmallPtrSet &&that)

      : BaseT(SmallStorage, SmallSizePowTwo, std::move(that)) {}

  template<typename It>

  SmallPtrSet(It I, It E) : BaseT(SmallStorage, SmallSizePowTwo) {

    this->insert(I, E);

  }

  SmallPtrSet(std::initializer_list<PtrType> IL)

      : BaseT(SmallStorage, SmallSizePowTwo) {

    this->insert(IL.begin(), IL.end());

  }

  SmallPtrSet<PtrType, SmallSize> &

  operator=(const SmallPtrSet<PtrType, SmallSize> &RHS) {

    if (&RHS != this)

      this->CopyFrom(RHS);

    return *this;

  }

  SmallPtrSet<PtrType, SmallSize> &

  operator=(SmallPtrSet<PtrType, SmallSize> &&RHS) {

    if (&RHS != this)

      this->MoveFrom(SmallSizePowTwo, std::move(RHS));

    return *this;

  }

  SmallPtrSet<PtrType, SmallSize> &

  operator=(std::initializer_list<PtrType> IL) {

    this->clear();

    this->insert(IL.begin(), IL.end());

    return *this;

  }

  /// swap - Swaps the elements of two sets.

  void swap(SmallPtrSet<PtrType, SmallSize> &RHS) {

    SmallPtrSetImplBase::swap(RHS);

  }

};

} // end namespace llvm

namespace std {

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

  template<class T, unsigned N>

  inline void swap(llvm::SmallPtrSet<T, N> &LHS, llvm::SmallPtrSet<T, N> &RHS) {

    LHS.swap(RHS);

  }

} // end namespace std

#endif // LLVM_ADT_SMALLPTRSET_H