include/swift/Basic/ClusteredBitVector.h

//===--- ClusteredBitVector.h - A size-optimized bit vector -----*- C++ -*-===//
//
// This source file is part of the Swift.org open source project
//
// Copyright (c) 2014 - 2017 Apple Inc. and the Swift project authors
// Licensed under Apache License v2.0 with Runtime Library Exception
//
// See https://swift.org/LICENSE.txt for license information
// See https://swift.org/CONTRIBUTORS.txt for the list of Swift project authors
//
//===----------------------------------------------------------------------===//
//
// This file defines the ClusteredBitVector class, a bitset data
// structure appropriate for situations meeting two criteria:
//
//   - Many vectors are no larger than a particular constant size, and
//     such vectors should be stored as compactly as possible.  This
//     constant size should be at least as large as any reasonable
//     target's pointer size in bits (i.e. at least 64).
//
//   - Most vectors have no bits set, and those that do tend to have
//     them set in coherent ranges.
//
// For example, this would be reasonable to use to describe the
// unoccupied bits in a memory layout.
//
// Primary mutators:
//   - appending another vector to this vector
//   - appending a constant vector (<0,0,...,0> or <1,1,...,1>) to this vector
//
// Primary observers:
//   - testing a specific bit
//   - searching for set bits from the start
//
//===----------------------------------------------------------------------===//

#ifndef SWIFT_BASIC_CLUSTEREDBITVECTOR_H
#define SWIFT_BASIC_CLUSTEREDBITVECTOR_H

#include "swift/Basic/LLVM.h"
#include "llvm/ADT/ArrayRef.h"
#include "llvm/ADT/Optional.h"
#include "llvm/ADT/STLExtras.h"
#include "llvm/Support/Compiler.h"
#include "llvm/Support/ErrorHandling.h"
#include "llvm/Support/MathExtras.h"
#include <algorithm>
#include <cassert>
#include <climits>
#include <cstdlib>
#include <type_traits>

namespace llvm {
  class APInt;
}

namespace swift {

/// A vector of bits.  This data structure is optimized to store an
/// empty vector of any size without doing any allocation.
class ClusteredBitVector {
  using ChunkType = uint64_t;
  static_assert(std::is_unsigned<ChunkType>::value, "ChunkType must be unsigned");
  enum {
    ChunkSizeInBits = sizeof(ChunkType) * CHAR_BIT
  };
  static_assert(sizeof(ChunkType) >= sizeof(ChunkType*),
                "ChunkType must be large enough to store a pointer");

  /// Return the number of chunks required to store a vector of the
  /// given number of bits.
  static size_t getNumChunksForBits(size_t value) { 
    return (value + ChunkSizeInBits - 1) / ChunkSizeInBits;
  }

  /// Either:
  ///   - a uint64_t * with at least enough storage for
  ///     getNumChunksForBits(LengthInBits) or
  ///   - inline storage for a single chunk
  /// as determined by HasOutOfLineData.
  ///
  /// 1) When using out-of-line storage:
  ///
  /// Suppose chunk size = 8, length = 13, capacity = 24.
  ///
  ///   11010101 00011010 101010010
  ///   ~~~~~~~~  ^ ~~~~~        ^
  ///     data    |  data        |
  ///             |              +---- bits in other chunks
  ///    high bits in last chunk         are uninitialized
  ///      are guaranteed zero
  /// 
  /// The capacity (in bits) is stored at index -1.
  ///
  /// 2) When using inline storage:
  ///
  ///  a) LengthInBits >= ChunkSizeInBits.  In this case, Data must be 0.
  ///     All bits are considered to be zero in this case.
  ///
  ///  b) 0 == LengthInBits.  In this case, Data must be 0.
  ///
  ///  c) 0 < LengthInBits < ChunkSizeInBits.  In this case, Data contains
  ///     a single chunk, with its unused high bits zeroed like in the
  ///     out-of-line case.
  ///
  /// Therefore, an efficient way to test whether all bits are zero:
  /// Data != 0.  (isInlineAndAllClear())  Not *guaranteed* to find
  /// something, but still efficient.
  ChunkType Data;
  
  size_t LengthInBits : sizeof(size_t) * CHAR_BIT - 1;
  size_t HasOutOfLineData : 1;

  /// Is this vector using out-of-line storage?
  bool hasOutOfLineData() const { return HasOutOfLineData; }

  /// Return true if this vector is not using out-of-line storage and
  /// does not have any bits set.  This is a special-case representation
  /// where the capacity can be smaller than the length.
  ///
  /// This is a necessary condition for hasSufficientChunkStorage(),
  /// and it's quicker to test, so a lot of routines in this class
  /// that need to work on chunk data in the general case test this
  /// first.
  bool isInlineAndAllClear() const {
    assert(!hasOutOfLineData() || Data != 0);
    return Data == 0;
  }

  /// Return true if this vector is not in the special case where the
  /// capacity is smaller than the length.  If this is true, then
  /// it's safe to call routines like getChunks().
  bool hasSufficientChunkStorage() const {
    return !(isInlineAndAllClear() && LengthInBits > ChunkSizeInBits);
  }

  /// Return the number of chunks required in order to store the full
  /// length (not capacity) of this bit vector.  This may be greater
  /// than the capacity in exactly one case, (2a), i.e.
  /// !hasSufficientChunkStorage().
  size_t getLengthInChunks() const {
    return getNumChunksForBits(LengthInBits);
  }

  /// Return the current capacity of this bit vector, in bits.  This
  /// is a relatively important operation because it's needed on every
  /// append.
  size_t getCapacityInBits() const {
    return hasOutOfLineData() ? getOutOfLineCapacityInBits() : ChunkSizeInBits;
  }

  /// Return the current capacity of this bit vector, in chunks.
  size_t getCapacityInChunks() const {
    return getCapacityInBits() / ChunkSizeInBits;
  }

  /// Return the current capacity of this bit vector, in bits, given
  /// that it's using out-of-line storage.
  size_t getOutOfLineCapacityInBits() const {
    assert(hasOutOfLineData());
    return (size_t) getOutOfLineChunksPtr()[-1];
  }

  /// Return the current capacity of this bit vector, in chunks, given
  /// that it's using out-of-line storage.
  size_t getOutOfLineCapacityInChunks() const {
    return getOutOfLineCapacityInBits() / ChunkSizeInBits;
  }

  /// Return a pointer to the data storage of this bit vector.
  ChunkType *getChunksPtr() {
    assert(hasSufficientChunkStorage());
    return hasOutOfLineData() ? getOutOfLineChunksPtr() : &Data;
  }
  const ChunkType *getChunksPtr() const {
    assert(hasSufficientChunkStorage());
    return hasOutOfLineData() ? getOutOfLineChunksPtr() : &Data;
  }

  MutableArrayRef<ChunkType> getChunks() {
    assert(hasSufficientChunkStorage());
    return { getChunksPtr(), getLengthInChunks() };
  }
  ArrayRef<ChunkType> getChunks() const {
    assert(hasSufficientChunkStorage());
    return { getChunksPtr(), getLengthInChunks() };
  }

  MutableArrayRef<ChunkType> getOutOfLineChunks() {
    return { getOutOfLineChunksPtr(), getLengthInChunks() };
  }
  ArrayRef<ChunkType> getOutOfLineChunks() const {
    return { getOutOfLineChunksPtr(), getLengthInChunks() };
  }

  /// Return a pointer to the data storage of this bit vector, given
  /// that it's using out-of-line storage.
  ChunkType *getOutOfLineChunksPtr() {
    assert(hasOutOfLineData());
    return reinterpret_cast<ChunkType*>(Data);
  }
  const ChunkType *getOutOfLineChunksPtr() const {
    assert(hasOutOfLineData());
    return reinterpret_cast<const ChunkType*>(Data);
  }

public:
  /// Create a new bit vector of zero length.  This does not perform
  /// any allocations.
  ClusteredBitVector() : Data(0), LengthInBits(0), HasOutOfLineData(0) {}

  /// Return a constant bit-vector of the given size.
  static ClusteredBitVector getConstant(size_t numBits, bool value) {
    ClusteredBitVector result;
    if (value) {
      result.reserve(numBits);
      result.appendSetBits(numBits);
    } else {
      result.appendClearBits(numBits);
    }
    return result;
  }

  ClusteredBitVector(const ClusteredBitVector &other)
    : Data(other.Data),
      LengthInBits(other.LengthInBits),
      HasOutOfLineData(other.HasOutOfLineData) {
    if (hasOutOfLineData()) {
      makeIndependentCopy();
    }
  }

  ClusteredBitVector(ClusteredBitVector &&other)
    : Data(other.Data),
      LengthInBits(other.LengthInBits),
      HasOutOfLineData(other.HasOutOfLineData) {
    other.dropData();
  }

  ClusteredBitVector &operator=(const ClusteredBitVector &other) {
    // Do something with our current out-of-line storage.
    if (hasOutOfLineData()) {
      // Copy into our current storage if its capacity is adequate.
      auto otherLengthInChunks = other.getLengthInChunks();
      if (otherLengthInChunks <= getOutOfLineCapacityInChunks()) {
        LengthInBits = other.LengthInBits;
        if (other.isInlineAndAllClear()) {
          memset(getOutOfLineChunksPtr(), 0,
                 otherLengthInChunks * sizeof(ChunkType));
        } else {
          memcpy(getOutOfLineChunksPtr(), other.getChunksPtr(),
                 otherLengthInChunks * sizeof(ChunkType));
        }
        return *this;
      }

      // Otherwise, destroy our current storage.
      destroy();
    }

    Data = other.Data;
    LengthInBits = other.LengthInBits;
    HasOutOfLineData = other.HasOutOfLineData;
    if (HasOutOfLineData) {
      makeIndependentCopy();
    }

    return *this;
  }

  ClusteredBitVector &operator=(ClusteredBitVector &&other) {
    // Just drop our current out-of-line storage.
    if (hasOutOfLineData()) {
      destroy();
    }

    Data = other.Data;
    LengthInBits = other.LengthInBits;
    HasOutOfLineData = other.HasOutOfLineData;
    other.dropData();
    return *this;
  }

  ~ClusteredBitVector() {
    if (hasOutOfLineData()) {
      destroy();
    }
  }

  /// Return true if this vector is zero-length (*not* if it does not
  /// contain any set bits).
  bool empty() const {
    return LengthInBits == 0;
  }

  /// Return the length of this bit-vector.
  size_t size() const {
    return LengthInBits;
  }

  /// Reserve space for an extra N bits.  This may unnecessarily force
  /// the vector to use an out-of-line representation.
  void reserveExtra(size_t numBits) {
    auto requiredBits = LengthInBits + numBits;
    if (requiredBits > getCapacityInBits()) {
      auto requiredChunks = getNumChunksForBits(requiredBits);
      auto chunkCount = getCapacityInChunks();
      assert(requiredChunks > chunkCount);
      do {
        // Growth curve: 1 (inline) -> 3 -> 7 -> 15 -> 31 -> ...
        // This is a particularly nice sequence because we store the
        // capacity in the chunk at index -1, so the actual allocation
        // size is a power of 2.
        chunkCount = chunkCount * 2 + 1;
      } while (requiredChunks > chunkCount);

      reallocate(chunkCount);
    }
    // Postcondition: hasSufficientChunkStorage().
  }

  /// Reserve space for a total of N bits.  This may unnecessarily
  /// force the vector to use an out-of-line representation.
  void reserve(size_t requiredSize) {
    if (requiredSize > getCapacityInBits()) {
      reallocate(getNumChunksForBits(requiredSize));
    }
    // Postcondition: hasSufficientChunkStorage().
  }

  /// Append the bits from the given vector to this one.
  void append(const ClusteredBitVector &other) {
    // Nothing to do if the other vector is empty.
    if (other.empty()) return;

    // Special case: don't allocate space for zero bits.
    if (isInlineAndAllClear() && other.isInlineAndAllClear()) {
      LengthInBits += other.LengthInBits;
      return;
    }

    // Okay, one or the other of these is using out-of-line storage.
    // Assume that bits might be set.
    reserveExtra(other.size());

    if (other.isInlineAndAllClear()) {
      appendConstantBitsReserved(other.size(), 0);
    } else {
      appendReserved(other.size(), other.getChunksPtr());
    }
  }

  /// Append the bits from the given vector to this one.
  void append(ClusteredBitVector &&other) {
    // If this vector is empty, just move the other.
    if (empty()) {
      *this = std::move(other);
      return;
    }

    // Otherwise, use copy-append.
    append(other);
  }

  /// Add the low N bits from the given value to the vector.
  void add(size_t numBits, uint64_t value) {
    assert(numBits <= 64);
    if (numBits == 0) return;

    if (value == 0 && isInlineAndAllClear()) {
      LengthInBits += numBits;
      return;
    }

    reserveExtra(numBits);
    static_assert(sizeof(value) <= sizeof(ChunkType),
                  "chunk too small for this, break 'value' up into "
                  "multiple parts");
    const ChunkType chunks[] = { value };
    appendReserved(numBits, chunks);
  }

  /// Append a number of clear bits to this vector.
  void appendClearBits(size_t numBits) {
    if (numBits == 0) return;

    if (isInlineAndAllClear()) {
      LengthInBits += numBits;
      return;
    }

    reserveExtra(numBits);
    appendConstantBitsReserved(numBits, 0);
  }

  /// Extend the vector out to the given length with clear bits.
  void extendWithClearBits(size_t newSize) {
    assert(newSize >= size());
    appendClearBits(newSize - size());
  }


  /// Append a number of set bits to this vector.
  void appendSetBits(size_t numBits) {
    if (numBits == 0) return;
    reserveExtra(numBits);
    appendConstantBitsReserved(numBits, 1);
  }

  /// Extend the vector out to the given length with set bits.
  void extendWithSetBits(size_t newSize) {
    assert(newSize >= size());
    appendSetBits(newSize - size());
  }

  /// Test whether a particular bit is set.
  bool operator[](size_t i) const {
    assert(i < size());
    if (isInlineAndAllClear()) return false;
    return getChunks()[i / ChunkSizeInBits]
             & (ChunkType(1) << (i % ChunkSizeInBits));
  }

  /// Intersect a bit-vector of the same size into this vector.
  ClusteredBitVector &operator&=(const ClusteredBitVector &other) {
    assert(size() == other.size());

    // If this vector is all-clear, this is a no-op.
    if (isInlineAndAllClear())
      return *this;

    // If the other vector is all-clear, we need to wipe this one.
    if (other.isInlineAndAllClear()) {
      for (auto &chunk : getChunks())
        chunk = 0;
      return *this;
    }

    // Otherwise, &= the chunks pairwise.
    auto chunks = getChunks();
    auto oi = other.getChunksPtr();
    for (auto i = chunks.begin(), e = chunks.end(); i != e; ++i, ++oi) {
      *i &= *oi;
    }
    return *this;
  }

  /// Union a bit-vector of the same size into this vector.
  ClusteredBitVector &operator|=(const ClusteredBitVector &other) {
    assert(size() == other.size());

    // If the other vector is all-clear, this is a no-op.
    if (other.isInlineAndAllClear())
      return *this;

    // If this vector is all-clear, we just copy the other.
    if (isInlineAndAllClear()) {
      return (*this = other);
    }

    // Otherwise, |= the chunks pairwise.
    auto chunks = getChunks();
    auto oi = other.getChunksPtr();
    for (auto i = chunks.begin(), e = chunks.end(); i != e; ++i, ++oi) {
      *i |= *oi;
    }
    return *this;
  }

  /// Set bit i.
  void setBit(size_t i) {
    assert(i < size());
    if (isInlineAndAllClear()) {
      reserve(LengthInBits);
    }
    getChunks()[i / ChunkSizeInBits] |= (ChunkType(1) << (i % ChunkSizeInBits));
  }

  /// Clear bit i.
  void clearBit(size_t i) {
    assert(i < size());
    if (isInlineAndAllClear()) return;
    getChunksPtr()[i / ChunkSizeInBits] &= ~(ChunkType(1) << (i % ChunkSizeInBits));
  }

  /// Toggle bit i.
  void flipBit(size_t i) {
    assert(i < size());
    if (isInlineAndAllClear()) {
      reserve(LengthInBits);
    }
    getChunksPtr()[i / ChunkSizeInBits] ^= (ChunkType(1) << (i % ChunkSizeInBits));
  }

  /// Toggle all the bits in this vector.
  void flipAll() {
    if (empty()) return;
    if (isInlineAndAllClear()) {
      reserve(LengthInBits);
    }
    for (auto &chunk : getChunks()) {
      chunk = ~chunk;
    }
    if (auto tailBits = size() % ChunkSizeInBits) {
      getChunks().back() &= ((ChunkType(1) << tailBits) - 1);
    }
  }

  /// Set the length of this vector to zero, but do not release any capacity.
  void clear() {
    LengthInBits = 0;
    if (!hasOutOfLineData())
      Data = 0;
  }

  /// Count the number of set bits in this vector.
  size_t count() const {
    if (isInlineAndAllClear()) return 0;
    size_t count = 0;
    for (ChunkType chunk : getChunks()) {
      count += llvm::countPopulation(chunk);
    }
    return count;
  }

  /// Determine if there are any bits set in this vector.
  bool any() const {
    if (isInlineAndAllClear()) return false;
    for (ChunkType chunk : getChunks()) {
      if (chunk) return true;
    }
    return false;
  }

  /// Determine if there are no bits set in this vector.
  ///
  /// \return \c !any()
  bool none() const {
    return !any();
  }

  /// A class for scanning for set bits, from low indices to high ones.
  class SetBitEnumerator {
    ChunkType CurChunk;
    const ChunkType *Chunks;
    unsigned CurChunkIndex;
    unsigned NumChunks;
  public:
    explicit SetBitEnumerator(const ClusteredBitVector &vector) {
      if (vector.isInlineAndAllClear()) {
        CurChunkIndex = 0;
        NumChunks = 0;
      } else {
        Chunks = vector.getChunksPtr();
        CurChunk = Chunks[0];
        CurChunkIndex = 0;
        NumChunks = vector.getLengthInChunks();
      }
    }

    /// Search for another bit.  Returns false if it can't find one.
    Optional<size_t> findNext() {
      if (CurChunkIndex == NumChunks) return None;
      auto cur = CurChunk;
      while (!cur) {
        if (++CurChunkIndex == NumChunks) return None;
        cur = Chunks[CurChunkIndex];
      }

      // Find the index of the lowest set bit.
      size_t bitIndex = llvm::countTrailingZeros(cur, llvm::ZB_Undefined);

      // Clear that bit in the current chunk.
      CurChunk = cur ^ (ChunkType(1) << bitIndex);
      assert(!(CurChunk & (ChunkType(1) << bitIndex)));

      return (CurChunkIndex * ChunkSizeInBits + bitIndex);
    }
  };
  SetBitEnumerator enumerateSetBits() const {
    return SetBitEnumerator(*this);
  }

  friend bool operator==(const ClusteredBitVector &lhs,
                         const ClusteredBitVector &rhs) {
    if (lhs.size() != rhs.size())
      return false;
    if (lhs.empty())
      return true;

    if (!lhs.hasOutOfLineData() && !rhs.hasOutOfLineData()) {
      return lhs.Data == rhs.Data;
    } else {
      return equalsSlowCase(lhs, rhs);
    }
  }
  friend bool operator!=(const ClusteredBitVector &lhs,
                         const ClusteredBitVector &rhs) {
    return !(lhs == rhs);
  }

  /// Return this bit-vector as an APInt, with low indices becoming
  /// the least significant bits of the number.
  llvm::APInt asAPInt() const;

  /// Construct a bit-vector from an APInt.
  static ClusteredBitVector fromAPInt(const llvm::APInt &value);

  /// Pretty-print the vector.
  void print(llvm::raw_ostream &out) const;
  void dump() const;

private:
  /// Make this object store an independent copy of the out of line
  /// data it currently stores, simply overwriting the current pointer
  /// without deleting it.
  void makeIndependentCopy() {
    assert(hasOutOfLineData());
    auto lengthToCopy = getLengthInChunks();
    allocateAndCopyFrom(getOutOfLineChunksPtr(), lengthToCopy, lengthToCopy);
  }

  /// Reallocate this vector, copying the current data into the new space.
  void reallocate(size_t newCapacityInChunks);

  ChunkType *allocate(size_t newCapacityInChunks) {
    assert(HasOutOfLineData && "bit should already be set");
    ChunkType *newData = new ChunkType[newCapacityInChunks + 1] + 1;
    newData[-1] = newCapacityInChunks * ChunkSizeInBits;
    Data = reinterpret_cast<ChunkType>(newData);
    assert(!isInlineAndAllClear());
    assert(getCapacityInChunks() == newCapacityInChunks);
    return newData;
  }

  void allocateAndCopyFrom(const ChunkType *oldData,
                           size_t newCapacityInChunks,
                           size_t numChunksToCopy) {
    auto newData = allocate(newCapacityInChunks);
    memcpy(newData, oldData, numChunksToCopy * sizeof(ChunkType));
  }

  /// Drop references to the current data.
  void dropData() {
    LengthInBits = 0;
    HasOutOfLineData = false;
    Data = 0;
  }

  /// Destroy the out of line data currently stored in this object.
  void destroy() {
    assert(hasOutOfLineData());
    delete[] (getOutOfLineChunksPtr() - 1);
  }

  /// Append a certain number of constant bits to this vector, given
  /// that it's known to contain enough capacity for them.
  void appendConstantBitsReserved(size_t numBits, bool addOnes);

  /// Append bits from the given array to this vector.
  void appendReserved(size_t numBits, const ChunkType *nextChunk);

  /// Append bits to this vector, given that it's known to contain
  /// enough capacity for them all.
  void appendReserved(size_t numBits,
                llvm::function_ref<ChunkType(size_t numBitsWanted)> generator);

  /// The slow case of equality-checking.
  static bool equalsSlowCase(const ClusteredBitVector &lhs,
                             const ClusteredBitVector &rhs);
};

} // end namespace swift

#endif // SWIFT_BASIC_CLUSTEREDBITVECTOR_H