static APFloat getNaN(const fltSemantics &Sem, bool Negative = false) {
return APFloat(Sem, fcNaN, Negative);
}
-
+
/// Profile - Used to insert APFloat objects, or objects that contain
/// APFloat objects, into FoldingSets.
void Profile(FoldingSetNodeID& NID) const;
-
+
/// @brief Used by the Bitcode serializer to emit APInts to Bitcode.
void Emit(Serializer& S) const;
-
+
/// @brief Used by the Bitcode deserializer to deserialize APInts.
static APFloat ReadVal(Deserializer& D);
class Deserializer;
class FoldingSetNodeID;
class raw_ostream;
-
+
template<typename T>
class SmallVectorImpl;
-
+
/* An unsigned host type used as a single part of a multi-part
bignum. */
typedef uint64_t integerPart;
//===----------------------------------------------------------------------===//
/// APInt - This class represents arbitrary precision constant integral values.
-/// It is a functional replacement for common case unsigned integer type like
-/// "unsigned", "unsigned long" or "uint64_t", but also allows non-byte-width
+/// It is a functional replacement for common case unsigned integer type like
+/// "unsigned", "unsigned long" or "uint64_t", but also allows non-byte-width
/// integer sizes and large integer value types such as 3-bits, 15-bits, or more
-/// than 64-bits of precision. APInt provides a variety of arithmetic operators
+/// than 64-bits of precision. APInt provides a variety of arithmetic operators
/// and methods to manipulate integer values of any bit-width. It supports both
/// the typical integer arithmetic and comparison operations as well as bitwise
/// manipulation.
///
/// The class has several invariants worth noting:
/// * All bit, byte, and word positions are zero-based.
-/// * Once the bit width is set, it doesn't change except by the Truncate,
+/// * Once the bit width is set, it doesn't change except by the Truncate,
/// SignExtend, or ZeroExtend operations.
/// * All binary operators must be on APInt instances of the same bit width.
-/// Attempting to use these operators on instances with different bit
+/// Attempting to use these operators on instances with different bit
/// widths will yield an assertion.
/// * The value is stored canonically as an unsigned value. For operations
/// where it makes a difference, there are both signed and unsigned variants
/// @returns true if the number of bits <= 64, false otherwise.
/// @brief Determine if this APInt just has one word to store value.
- bool isSingleWord() const {
- return BitWidth <= APINT_BITS_PER_WORD;
+ bool isSingleWord() const {
+ return BitWidth <= APINT_BITS_PER_WORD;
}
/// @returns the word position for the specified bit position.
/// @brief Determine which word a bit is in.
- static uint32_t whichWord(uint32_t bitPosition) {
- return bitPosition / APINT_BITS_PER_WORD;
+ static uint32_t whichWord(uint32_t bitPosition) {
+ return bitPosition / APINT_BITS_PER_WORD;
}
- /// @returns the bit position in a word for the specified bit position
+ /// @returns the bit position in a word for the specified bit position
/// in the APInt.
/// @brief Determine which bit in a word a bit is in.
- static uint32_t whichBit(uint32_t bitPosition) {
- return bitPosition % APINT_BITS_PER_WORD;
+ static uint32_t whichBit(uint32_t bitPosition) {
+ return bitPosition % APINT_BITS_PER_WORD;
}
- /// This method generates and returns a uint64_t (word) mask for a single
- /// bit at a specific bit position. This is used to mask the bit in the
+ /// This method generates and returns a uint64_t (word) mask for a single
+ /// bit at a specific bit position. This is used to mask the bit in the
/// corresponding word.
/// @returns a uint64_t with only bit at "whichBit(bitPosition)" set
/// @brief Get a single bit mask.
- static uint64_t maskBit(uint32_t bitPosition) {
- return 1ULL << whichBit(bitPosition);
+ static uint64_t maskBit(uint32_t bitPosition) {
+ return 1ULL << whichBit(bitPosition);
}
/// This method is used internally to clear the to "N" bits in the high order
- /// word that are not used by the APInt. This is needed after the most
- /// significant word is assigned a value to ensure that those bits are
+ /// word that are not used by the APInt. This is needed after the most
+ /// significant word is assigned a value to ensure that those bits are
/// zero'd out.
/// @brief Clear unused high order bits
APInt& clearUnusedBits() {
/// @returns the corresponding word for the specified bit position.
/// @brief Get the word corresponding to a bit position
- uint64_t getWord(uint32_t bitPosition) const {
- return isSingleWord() ? VAL : pVal[whichWord(bitPosition)];
+ uint64_t getWord(uint32_t bitPosition) const {
+ return isSingleWord() ? VAL : pVal[whichWord(bitPosition)];
}
/// This is used by the constructors that take string arguments.
/// @brief Convert a char array into an APInt
- void fromString(uint32_t numBits, const char *strStart, uint32_t slen,
+ void fromString(uint32_t numBits, const char *strStart, uint32_t slen,
uint8_t radix);
/// This is used by the toString method to divide by the radix. It simply
/// has specific constraints on its inputs. If those constraints are not met
/// then it provides a simpler form of divide.
/// @brief An internal division function for dividing APInts.
- static void divide(const APInt LHS, uint32_t lhsWords,
+ static void divide(const APInt LHS, uint32_t lhsWords,
const APInt &RHS, uint32_t rhsWords,
APInt *Quotient, APInt *Remainder);
APInt(uint32_t numBits, uint32_t numWords, const uint64_t bigVal[]);
/// This constructor interprets the slen characters starting at StrStart as
- /// a string in the given radix. The interpretation stops when the first
+ /// a string in the given radix. The interpretation stops when the first
/// character that is not suitable for the radix is encountered. Acceptable
/// radix values are 2, 8, 10 and 16. It is an error for the value implied by
/// the string to require more bits than numBits.
APInt(const APInt& that)
: BitWidth(that.BitWidth), VAL(0) {
assert(BitWidth && "bitwidth too small");
- if (isSingleWord())
+ if (isSingleWord())
VAL = that.VAL;
else
initSlowCase(that);
/// @brief Destructor.
~APInt() {
- if (!isSingleWord())
+ if (!isSingleWord())
delete [] pVal;
}
/// Default constructor that creates an uninitialized APInt. This is useful
/// for object deserialization (pair this with the static method Read).
explicit APInt() : BitWidth(1) {}
-
- /// Profile - Used to insert APInt objects, or objects that contain APInt
+
+ /// Profile - Used to insert APInt objects, or objects that contain APInt
/// objects, into FoldingSets.
void Profile(FoldingSetNodeID& id) const;
-
+
/// @brief Used by the Bitcode serializer to emit APInts to Bitcode.
void Emit(Serializer& S) const;
-
+
/// @brief Used by the Bitcode deserializer to deserialize APInts.
void Read(Deserializer& D);
assert(N && "N == 0 ???");
if (N >= getBitWidth())
return true;
-
+
if (isSingleWord())
return VAL == (VAL & (~0ULL >> (64 - N)));
APInt Tmp(N, getNumWords(), pVal);
}
/// @returns true if the argument APInt value is a power of two > 0.
- bool isPowerOf2() const;
+ bool isPowerOf2() const;
/// isSignBit - Return true if this is the value returned by getSignBit.
bool isSignBit() const { return isMinSignedValue(); }
-
+
/// This converts the APInt to a boolean value as a test against zero.
- /// @brief Boolean conversion function.
+ /// @brief Boolean conversion function.
bool getBoolValue() const {
return *this != 0;
}
/// bits from loBit (inclusive) to hiBit (exclusive) will be set. All other
/// bits will be zero. For example, with parameters(32, 0, 16) you would get
/// 0x0000FFFF. If hiBit is less than loBit then the set bits "wrap". For
- /// example, with parameters (32, 28, 4), you would get 0xF000000F.
+ /// example, with parameters (32, 28, 4), you would get 0xF000000F.
/// @param numBits the intended bit width of the result
/// @param loBit the index of the lowest bit set.
/// @param hiBit the index of the highest bit set.
/// @brief Get a hash value based on this APInt
uint64_t getHashValue() const;
- /// This function returns a pointer to the internal storage of the APInt.
+ /// This function returns a pointer to the internal storage of the APInt.
/// This is useful for writing out the APInt in binary form without any
/// conversions.
const uint64_t* getRawData() const {
APInt& operator++();
/// @returns a new APInt representing *this decremented by one.
- /// @brief Postfix decrement operator.
+ /// @brief Postfix decrement operator.
const APInt operator--(int) {
APInt API(*this);
--(*this);
}
/// @returns *this decremented by one.
- /// @brief Prefix decrement operator.
+ /// @brief Prefix decrement operator.
APInt& operator--();
- /// Performs a bitwise complement operation on this APInt.
+ /// Performs a bitwise complement operation on this APInt.
/// @returns an APInt that is the bitwise complement of *this
- /// @brief Unary bitwise complement operator.
+ /// @brief Unary bitwise complement operator.
APInt operator~() const {
APInt Result(*this);
Result.flip();
/// Performs logical negation operation on this APInt.
/// @returns true if *this is zero, false otherwise.
- /// @brief Logical negation operator.
+ /// @brief Logical negation operator.
bool operator!() const;
/// @}
/// @name Assignment Operators
/// @{
/// @returns *this after assignment of RHS.
- /// @brief Copy assignment operator.
+ /// @brief Copy assignment operator.
APInt& operator=(const APInt& RHS) {
// If the bitwidths are the same, we can avoid mucking with memory
if (isSingleWord() && RHS.isSingleWord()) {
/// the bit width, the excess bits are truncated. If the bit width is larger
/// than 64, the value is zero filled in the unspecified high order bits.
/// @returns *this after assignment of RHS value.
- /// @brief Assignment operator.
+ /// @brief Assignment operator.
APInt& operator=(uint64_t RHS);
/// Performs a bitwise AND operation on this APInt and RHS. The result is
- /// assigned to *this.
+ /// assigned to *this.
/// @returns *this after ANDing with RHS.
- /// @brief Bitwise AND assignment operator.
+ /// @brief Bitwise AND assignment operator.
APInt& operator&=(const APInt& RHS);
- /// Performs a bitwise OR operation on this APInt and RHS. The result is
+ /// Performs a bitwise OR operation on this APInt and RHS. The result is
/// assigned *this;
/// @returns *this after ORing with RHS.
- /// @brief Bitwise OR assignment operator.
+ /// @brief Bitwise OR assignment operator.
APInt& operator|=(const APInt& RHS);
/// Performs a bitwise XOR operation on this APInt and RHS. The result is
/// assigned to *this.
/// @returns *this after XORing with RHS.
- /// @brief Bitwise XOR assignment operator.
+ /// @brief Bitwise XOR assignment operator.
APInt& operator^=(const APInt& RHS);
/// Multiplies this APInt by RHS and assigns the result to *this.
/// @returns *this
- /// @brief Multiplication assignment operator.
+ /// @brief Multiplication assignment operator.
APInt& operator*=(const APInt& RHS);
/// Adds RHS to *this and assigns the result to *this.
/// @returns *this
- /// @brief Addition assignment operator.
+ /// @brief Addition assignment operator.
APInt& operator+=(const APInt& RHS);
/// Subtracts RHS from *this and assigns the result to *this.
/// @returns *this
- /// @brief Subtraction assignment operator.
+ /// @brief Subtraction assignment operator.
APInt& operator-=(const APInt& RHS);
/// Shifts *this left by shiftAmt and assigns the result to *this.
/// @{
/// Performs a bitwise AND operation on *this and RHS.
/// @returns An APInt value representing the bitwise AND of *this and RHS.
- /// @brief Bitwise AND operator.
+ /// @brief Bitwise AND operator.
APInt operator&(const APInt& RHS) const {
assert(BitWidth == RHS.BitWidth && "Bit widths must be the same");
if (isSingleWord())
/// Performs a bitwise OR operation on *this and RHS.
/// @returns An APInt value representing the bitwise OR of *this and RHS.
- /// @brief Bitwise OR operator.
+ /// @brief Bitwise OR operator.
APInt operator|(const APInt& RHS) const {
assert(BitWidth == RHS.BitWidth && "Bit widths must be the same");
if (isSingleWord())
/// Performs a bitwise XOR operation on *this and RHS.
/// @returns An APInt value representing the bitwise XOR of *this and RHS.
- /// @brief Bitwise XOR operator.
+ /// @brief Bitwise XOR operator.
APInt operator^(const APInt& RHS) const {
assert(BitWidth == RHS.BitWidth && "Bit widths must be the same");
if (isSingleWord())
}
/// Multiplies this APInt by RHS and returns the result.
- /// @brief Multiplication operator.
+ /// @brief Multiplication operator.
APInt operator*(const APInt& RHS) const;
/// Adds RHS to this APInt and returns the result.
- /// @brief Addition operator.
+ /// @brief Addition operator.
APInt operator+(const APInt& RHS) const;
APInt operator+(uint64_t RHS) const {
return (*this) + APInt(BitWidth, RHS);
}
/// Subtracts RHS from this APInt and returns the result.
- /// @brief Subtraction operator.
+ /// @brief Subtraction operator.
APInt operator-(const APInt& RHS) const;
APInt operator-(uint64_t RHS) const {
return (*this) - APInt(BitWidth, RHS);
}
-
+
APInt operator<<(unsigned Bits) const {
return shl(Bits);
}
/// may overlap with the pair of output arguments. It is safe to call
/// udivrem(X, Y, X, Y), for example.
/// @brief Dual division/remainder interface.
- static void udivrem(const APInt &LHS, const APInt &RHS,
+ static void udivrem(const APInt &LHS, const APInt &RHS,
APInt &Quotient, APInt &Remainder);
static void sdivrem(const APInt &LHS, const APInt &RHS,
/// @{
/// Compares this APInt with RHS for the validity of the equality
/// relationship.
- /// @brief Equality operator.
+ /// @brief Equality operator.
bool operator==(const APInt& RHS) const {
assert(BitWidth == RHS.BitWidth && "Comparison requires equal bit widths");
if (isSingleWord())
return EqualSlowCase(RHS);
}
- /// Compares this APInt with a uint64_t for the validity of the equality
+ /// Compares this APInt with a uint64_t for the validity of the equality
/// relationship.
/// @returns true if *this == Val
/// @brief Equality operator.
/// @returns true if *this == Val
/// @brief Equality comparison.
bool eq(const APInt &RHS) const {
- return (*this) == RHS;
+ return (*this) == RHS;
}
/// Compares this APInt with RHS for the validity of the inequality
/// relationship.
/// @returns true if *this != Val
- /// @brief Inequality operator.
+ /// @brief Inequality operator.
bool operator!=(const APInt& RHS) const {
return !((*this) == RHS);
}
- /// Compares this APInt with a uint64_t for the validity of the inequality
+ /// Compares this APInt with a uint64_t for the validity of the inequality
/// relationship.
/// @returns true if *this != Val
- /// @brief Inequality operator.
+ /// @brief Inequality operator.
bool operator!=(uint64_t Val) const {
return !((*this) == Val);
}
-
+
/// Compares this APInt with RHS for the validity of the inequality
/// relationship.
/// @returns true if *this != Val
/// @name Resizing Operators
/// @{
/// Truncate the APInt to a specified width. It is an error to specify a width
- /// that is greater than or equal to the current width.
+ /// that is greater than or equal to the current width.
/// @brief Truncate to new width.
APInt &trunc(uint32_t width);
/// This operation sign extends the APInt to a new width. If the high order
/// bit is set, the fill on the left will be done with 1 bits, otherwise zero.
- /// It is an error to specify a width that is less than or equal to the
+ /// It is an error to specify a width that is less than or equal to the
/// current width.
/// @brief Sign extend to a new width.
APInt &sext(uint32_t width);
/// This operation zero extends the APInt to a new width. The high order bits
- /// are filled with 0 bits. It is an error to specify a width that is less
+ /// are filled with 0 bits. It is an error to specify a width that is less
/// than or equal to the current width.
/// @brief Zero extend to a new width.
APInt &zext(uint32_t width);
/// @brief Set every bit to 0.
APInt& clear() {
- if (isSingleWord())
+ if (isSingleWord())
VAL = 0;
- else
+ else
memset(pVal, 0, getNumWords() * APINT_WORD_SIZE);
return *this;
}
return clearUnusedBits();
}
- /// Toggle a given bit to its opposite value whose position is given
+ /// Toggle a given bit to its opposite value whose position is given
/// as "bitPosition".
/// @brief Toggles a given bit to its opposite value.
APInt& flip(uint32_t bitPosition);
/// @{
/// @returns the total number of bits.
- uint32_t getBitWidth() const {
- return BitWidth;
+ uint32_t getBitWidth() const {
+ return BitWidth;
}
/// Here one word's bitwidth equals to that of uint64_t.
}
/// Computes the minimum bit width for this APInt while considering it to be
- /// a signed (and probably negative) value. If the value is not negative,
+ /// a signed (and probably negative) value. If the value is not negative,
/// this function returns the same value as getActiveBits()+1. Otherwise, it
/// returns the smallest bit width that will retain the negative value. For
/// example, -1 can be written as 0b1 or 0xFFFFFFFFFF. 0b1 is shorter and so
/// for -1, this function will always return 1.
- /// @brief Get the minimum bit size for this signed APInt
+ /// @brief Get the minimum bit size for this signed APInt
uint32_t getMinSignedBits() const {
if (isNegative())
return BitWidth - countLeadingOnes() + 1;
/// @brief Get sign extended value
int64_t getSExtValue() const {
if (isSingleWord())
- return int64_t(VAL << (APINT_BITS_PER_WORD - BitWidth)) >>
+ return int64_t(VAL << (APINT_BITS_PER_WORD - BitWidth)) >>
(APINT_BITS_PER_WORD - BitWidth);
assert(getMinSignedBits() <= 64 && "Too many bits for int64_t");
return int64_t(pVal[0]);
/// @brief Count the number of leading one bits.
uint32_t countLeadingOnes() const;
- /// countTrailingZeros - This function is an APInt version of the
- /// countTrailingZeros_{32,64} functions in MathExtras.h. It counts
+ /// countTrailingZeros - This function is an APInt version of the
+ /// countTrailingZeros_{32,64} functions in MathExtras.h. It counts
/// the number of zeros from the least significant bit to the first set bit.
/// @returns BitWidth if the value is zero.
/// @returns the number of zeros from the least significant bit to the first
/// @brief Count the number of trailing zero bits.
uint32_t countTrailingZeros() const;
- /// countTrailingOnes - This function is an APInt version of the
- /// countTrailingOnes_{32,64} functions in MathExtras.h. It counts
+ /// countTrailingOnes - This function is an APInt version of the
+ /// countTrailingOnes_{32,64} functions in MathExtras.h. It counts
/// the number of ones from the least significant bit to the first zero bit.
/// @returns BitWidth if the value is all ones.
/// @returns the number of ones from the least significant bit to the first
/// countPopulation - This function is an APInt version of the
/// countPopulation_{32,64} functions in MathExtras.h. It counts the number
- /// of 1 bits in the APInt value.
+ /// of 1 bits in the APInt value.
/// @returns 0 if the value is zero.
/// @returns the number of set bits.
/// @brief Count the number of bits set.
/// @name Conversion Functions
/// @{
void print(raw_ostream &OS, bool isSigned) const;
-
+
/// toString - Converts an APInt to a string and append it to Str. Str is
/// commonly a SmallString.
void toString(SmallVectorImpl<char> &Str, unsigned Radix, bool Signed) const;
void toStringSigned(SmallVectorImpl<char> &Str, unsigned Radix = 10) const {
return toString(Str, Radix, true);
}
-
+
/// toString - This returns the APInt as a std::string. Note that this is an
/// inefficient method. It is better to pass in a SmallVector/SmallString
/// to the methods above to avoid thrashing the heap for the string.
std::string toString(unsigned Radix, bool Signed) const;
-
+
/// @returns a byte-swapped representation of this APInt Value.
APInt byteSwap() const;
static void tcOr(integerPart *, const integerPart *, unsigned int);
static void tcXor(integerPart *, const integerPart *, unsigned int);
static void tcComplement(integerPart *, unsigned int);
-
+
/// Comparison (unsigned) of two bignums.
static int tcCompare(const integerPart *, const integerPart *,
unsigned int);
I.print(OS, true);
return OS;
}
-
+
namespace APIntOps {
/// @brief Determine the smaller of two APInts considered to be signed.
/// @returns the floor log base 2 of the specified APInt value.
inline uint32_t logBase2(const APInt& APIVal) {
- return APIVal.logBase2();
+ return APIVal.logBase2();
}
/// GreatestCommonDivisor - This function returns the greatest common
return LHS - RHS;
}
-/// Performs bitwise AND operation on APInt LHS and
+/// Performs bitwise AND operation on APInt LHS and
/// APInt RHS.
/// @brief Bitwise AND function for APInt.
inline APInt And(const APInt& LHS, const APInt& RHS) {
}
/// Performs bitwise OR operation on APInt LHS and APInt RHS.
-/// @brief Bitwise OR function for APInt.
+/// @brief Bitwise OR function for APInt.
inline APInt Or(const APInt& LHS, const APInt& RHS) {
return LHS | RHS;
}
/// @brief Bitwise XOR function for APInt.
inline APInt Xor(const APInt& LHS, const APInt& RHS) {
return LHS ^ RHS;
-}
+}
/// Performs a bitwise complement operation on APInt.
-/// @brief Bitwise complement function.
+/// @brief Bitwise complement function.
inline APInt Not(const APInt& APIVal) {
return ~APIVal;
}
#include "llvm/ADT/APInt.h"
namespace llvm {
-
+
class APSInt : public APInt {
bool IsUnsigned;
public:
/// APSInt ctor - Create an APSInt with the specified width, default to
/// unsigned.
- explicit APSInt(uint32_t BitWidth, bool isUnsigned = true)
+ explicit APSInt(uint32_t BitWidth, bool isUnsigned = true)
: APInt(BitWidth, 0), IsUnsigned(isUnsigned) {}
- explicit APSInt(const APInt &I, bool isUnsigned = true)
+ explicit APSInt(const APInt &I, bool isUnsigned = true)
: APInt(I), IsUnsigned(isUnsigned) {}
APSInt &operator=(const APSInt &RHS) {
- APInt::operator=(RHS);
+ APInt::operator=(RHS);
IsUnsigned = RHS.IsUnsigned;
return *this;
}
APSInt &operator=(const APInt &RHS) {
// Retain our current sign.
- APInt::operator=(RHS);
+ APInt::operator=(RHS);
return *this;
}
APSInt &operator=(uint64_t RHS) {
// Retain our current sign.
- APInt::operator=(RHS);
+ APInt::operator=(RHS);
return *this;
}
bool isUnsigned() const { return IsUnsigned; }
void setIsUnsigned(bool Val) { IsUnsigned = Val; }
void setIsSigned(bool Val) { IsUnsigned = !Val; }
-
+
/// toString - Append this APSInt to the specified SmallString.
void toString(SmallVectorImpl<char> &Str, unsigned Radix = 10) const {
return APInt::toString(Str, Radix, isSigned());
return APInt::toString(Radix, isSigned());
}
using APInt::toString;
-
+
APSInt& extend(uint32_t width) {
if (IsUnsigned)
zext(width);
sext(width);
return *this;
}
-
+
APSInt& extOrTrunc(uint32_t width) {
if (IsUnsigned)
zextOrTrunc(width);
sextOrTrunc(width);
return *this;
}
-
+
const APSInt &operator%=(const APSInt &RHS) {
assert(IsUnsigned == RHS.IsUnsigned && "Signedness mismatch!");
if (IsUnsigned)
assert(IsUnsigned == RHS.IsUnsigned && "Signedness mismatch!");
return IsUnsigned ? APSInt(udiv(RHS), true) : APSInt(sdiv(RHS), false);
}
-
+
APSInt operator>>(unsigned Amt) const {
return IsUnsigned ? APSInt(lshr(Amt), true) : APSInt(ashr(Amt), false);
}
*this = *this >> Amt;
return *this;
}
-
+
inline bool operator<(const APSInt& RHS) const {
assert(IsUnsigned == RHS.IsUnsigned && "Signedness mismatch!");
return IsUnsigned ? ult(RHS) : slt(RHS);
assert(IsUnsigned == RHS.IsUnsigned && "Signedness mismatch!");
return IsUnsigned ? uge(RHS) : sge(RHS);
}
-
+
// The remaining operators just wrap the logic of APInt, but retain the
// signedness information.
-
+
APSInt operator<<(unsigned Bits) const {
return APSInt(static_cast<const APInt&>(*this) << Bits, IsUnsigned);
- }
+ }
APSInt& operator<<=(unsigned Amt) {
*this = *this << Amt;
return *this;
}
-
+
APSInt& operator++() {
static_cast<APInt&>(*this)++;
return *this;
}
APSInt operator--(int) {
return APSInt(--static_cast<APInt&>(*this), IsUnsigned);
- }
+ }
APSInt operator-() const {
return APSInt(-static_cast<const APInt&>(*this), IsUnsigned);
- }
+ }
APSInt& operator+=(const APSInt& RHS) {
assert(IsUnsigned == RHS.IsUnsigned && "Signedness mismatch!");
static_cast<APInt&>(*this) += RHS;
return *this;
- }
+ }
APSInt& operator-=(const APSInt& RHS) {
assert(IsUnsigned == RHS.IsUnsigned && "Signedness mismatch!");
static_cast<APInt&>(*this) -= RHS;
return *this;
- }
+ }
APSInt& operator*=(const APSInt& RHS) {
assert(IsUnsigned == RHS.IsUnsigned && "Signedness mismatch!");
static_cast<APInt&>(*this) *= RHS;
return *this;
}
- APSInt operator&(const APSInt& RHS) const {
+ APSInt operator&(const APSInt& RHS) const {
assert(IsUnsigned == RHS.IsUnsigned && "Signedness mismatch!");
return APSInt(static_cast<const APInt&>(*this) & RHS, IsUnsigned);
}
APSInt And(const APSInt& RHS) const {
return this->operator&(RHS);
}
-
- APSInt operator|(const APSInt& RHS) const {
+
+ APSInt operator|(const APSInt& RHS) const {
assert(IsUnsigned == RHS.IsUnsigned && "Signedness mismatch!");
return APSInt(static_cast<const APInt&>(*this) | RHS, IsUnsigned);
}
APSInt Or(const APSInt& RHS) const {
return this->operator|(RHS);
}
-
-
- APSInt operator^(const APSInt& RHS) const {
+
+
+ APSInt operator^(const APSInt& RHS) const {
assert(IsUnsigned == RHS.IsUnsigned && "Signedness mismatch!");
return APSInt(static_cast<const APInt&>(*this) ^ RHS, IsUnsigned);
}
APSInt Xor(const APSInt& RHS) const {
return this->operator^(RHS);
- }
-
+ }
+
APSInt operator*(const APSInt& RHS) const {
assert(IsUnsigned == RHS.IsUnsigned && "Signedness mismatch!");
return APSInt(static_cast<const APInt&>(*this) * RHS, IsUnsigned);
}
- APSInt operator+(const APSInt& RHS) const {
+ APSInt operator+(const APSInt& RHS) const {
assert(IsUnsigned == RHS.IsUnsigned && "Signedness mismatch!");
return APSInt(static_cast<const APInt&>(*this) + RHS, IsUnsigned);
}
assert(IsUnsigned == RHS.IsUnsigned && "Signedness mismatch!");
return APSInt(static_cast<const APInt&>(*this) - RHS, IsUnsigned);
}
- APSInt operator~() const {
+ APSInt operator~() const {
return APSInt(~static_cast<const APInt&>(*this), IsUnsigned);
}
-
+
/// getMaxValue - Return the APSInt representing the maximum integer value
/// with the given bit width and signedness.
static APSInt getMaxValue(uint32_t numBits, bool Signed) {
return APSInt(Signed ? APInt::getSignedMaxValue(numBits)
: APInt::getMaxValue(numBits), Signed);
}
-
+
/// getMinValue - Return the APSInt representing the minimum integer value
/// with the given bit width and signedness.
static APSInt getMinValue(uint32_t numBits, bool Signed) {
return APSInt(Signed ? APInt::getSignedMinValue(numBits)
: APInt::getMinValue(numBits), Signed);
}
-
+
/// Profile - Used to insert APSInt objects, or objects that contain APSInt
/// objects, into FoldingSets.
void Profile(FoldingSetNodeID& ID) const;
};
-
+
inline raw_ostream &operator<<(raw_ostream &OS, const APSInt &I) {
I.print(OS, I.isSigned());
return OS;
}
-
-
+
+
} // end namespace llvm
#endif
enum { BITWORD_SIZE = (unsigned)sizeof(BitWord) * 8 };
- BitWord *Bits; // Actual bits.
+ BitWord *Bits; // Actual bits.
unsigned Size; // Size of bitvector in bits.
unsigned Capacity; // Size of allocated memory in BitWord.
Bits = new BitWord[Capacity];
std::copy(RHS.Bits, &RHS.Bits[Capacity], Bits);
}
-
+
~BitVector() {
delete[] Bits;
}
grow(N);
init_words(&Bits[OldCapacity], (Capacity-OldCapacity), t);
}
-
- // Set any old unused bits that are now included in the BitVector. This
- // may set bits that are not included in the new vector, but we will clear
+
+ // Set any old unused bits that are now included in the BitVector. This
+ // may set bits that are not included in the new vector, but we will clear
// them back out below.
if (N > Size)
set_unused_bits(t);
-
+
// Update the size, and clear out any bits that are now unused
unsigned OldSize = Size;
Size = N;
}
bool operator[](unsigned Idx) const {
- assert (Idx < Size && "Out-of-bounds Bit access.");
+ assert (Idx < Size && "Out-of-bounds Bit access.");
BitWord Mask = 1L << (Idx % BITWORD_SIZE);
return (Bits[Idx / BITWORD_SIZE] & Mask) != 0;
}
for (i = 0; i != std::min(ThisWords, RHSWords); ++i)
if (Bits[i] != RHS.Bits[i])
return false;
-
+
// Verify that any extra words are all zeros.
if (i != ThisWords) {
for (; i != ThisWords; ++i)
unsigned i;
for (i = 0; i != std::min(ThisWords, RHSWords); ++i)
Bits[i] &= RHS.Bits[i];
-
+
// Any bits that are just in this bitvector become zero, because they aren't
// in the RHS bit vector. Any words only in RHS are ignored because they
// are already zero in the LHS.
for (; i != ThisWords; ++i)
Bits[i] = 0;
-
+
return *this;
}
Bits[i] ^= RHS.Bits[i];
return *this;
}
-
+
// Assignment operator.
const BitVector &operator=(const BitVector &RHS) {
if (this == &RHS) return *this;
clear_unused_bits();
return *this;
}
-
+
// Grow the bitvector to have enough elements.
Capacity = RHSWords;
BitWord *NewBits = new BitWord[Capacity];
unsigned NumBitWords(unsigned S) const {
return (S + BITWORD_SIZE-1) / BITWORD_SIZE;
}
-
+
// Set the unused bits in the high words.
void set_unused_bits(bool t = true) {
// Set high words first.
unsigned UsedWords = NumBitWords(Size);
if (Capacity > UsedWords)
init_words(&Bits[UsedWords], (Capacity-UsedWords), t);
-
+
// Then set any stray high bits of the last used word.
unsigned ExtraBits = Size % BITWORD_SIZE;
if (ExtraBits) {
// Destroy the old bits.
delete[] Bits;
Bits = NewBits;
-
+
clear_unused_bits();
}
void init_words(BitWord *B, unsigned NumWords, bool t) {
memset(B, 0 - (int)t, NumWords*sizeof(BitWord));
- }
+ }
};
inline BitVector operator&(const BitVector &LHS, const BitVector &RHS) {
Result ^= RHS;
return Result;
}
-
+
} // End llvm namespace
#endif
#include <utility>
namespace llvm {
-
+
template<typename T>
struct DenseMapInfo {
//static inline T getEmptyKey();
static inline T* getEmptyKey() { return reinterpret_cast<T*>(-1); }
static inline T* getTombstoneKey() { return reinterpret_cast<T*>(-2); }
static unsigned getHashValue(const T *PtrVal) {
- return (unsigned((uintptr_t)PtrVal) >> 4) ^
+ return (unsigned((uintptr_t)PtrVal) >> 4) ^
(unsigned((uintptr_t)PtrVal) >> 9);
}
static bool isEqual(const T *LHS, const T *RHS) { return LHS == RHS; }
typedef DenseMapInfo<T> FirstInfo;
typedef DenseMapInfo<U> SecondInfo;
- static inline Pair getEmptyKey() {
- return std::make_pair(FirstInfo::getEmptyKey(),
- SecondInfo::getEmptyKey());
+ static inline Pair getEmptyKey() {
+ return std::make_pair(FirstInfo::getEmptyKey(),
+ SecondInfo::getEmptyKey());
}
- static inline Pair getTombstoneKey() {
- return std::make_pair(FirstInfo::getTombstoneKey(),
+ static inline Pair getTombstoneKey() {
+ return std::make_pair(FirstInfo::getTombstoneKey(),
SecondInfo::getEmptyKey());
}
static unsigned getHashValue(const Pair& PairVal) {
static bool isPod() { return FirstInfo::isPod() && SecondInfo::isPod(); }
};
-template<typename KeyT, typename ValueT,
+template<typename KeyT, typename ValueT,
typename KeyInfoT = DenseMapInfo<KeyT>,
typename ValueInfoT = DenseMapInfo<ValueT> >
class DenseMapIterator;
typedef std::pair<KeyT, ValueT> BucketT;
unsigned NumBuckets;
BucketT *Buckets;
-
+
unsigned NumEntries;
unsigned NumTombstones;
public:
typedef KeyT key_type;
typedef ValueT mapped_type;
typedef BucketT value_type;
-
+
DenseMap(const DenseMap& other) {
NumBuckets = 0;
CopyFrom(other);
}
-
+
explicit DenseMap(unsigned NumInitBuckets = 64) {
init(NumInitBuckets);
}
-
+
~DenseMap() {
const KeyT EmptyKey = getEmptyKey(), TombstoneKey = getTombstoneKey();
for (BucketT *P = Buckets, *E = Buckets+NumBuckets; P != E; ++P) {
}
operator delete(Buckets);
}
-
+
typedef DenseMapIterator<KeyT, ValueT, KeyInfoT> iterator;
typedef DenseMapConstIterator<KeyT, ValueT, KeyInfoT> const_iterator;
inline iterator begin() {
inline const_iterator end() const {
return const_iterator(Buckets+NumBuckets, Buckets+NumBuckets);
}
-
+
bool empty() const { return NumEntries == 0; }
unsigned size() const { return NumEntries; }
/// Grow the densemap so that it has at least Size buckets. Does not shrink
void resize(size_t Size) { grow(Size); }
-
+
void clear() {
// If the capacity of the array is huge, and the # elements used is small,
// shrink the array.
shrink_and_clear();
return;
}
-
+
const KeyT EmptyKey = getEmptyKey(), TombstoneKey = getTombstoneKey();
for (BucketT *P = Buckets, *E = Buckets+NumBuckets; P != E; ++P) {
if (!KeyInfoT::isEqual(P->first, EmptyKey)) {
BucketT *TheBucket;
return LookupBucketFor(Val, TheBucket);
}
-
+
iterator find(const KeyT &Val) {
BucketT *TheBucket;
if (LookupBucketFor(Val, TheBucket))
return const_iterator(TheBucket, Buckets+NumBuckets);
return end();
}
-
+
/// lookup - Return the entry for the specified key, or a default
/// constructed value if no such entry exists.
ValueT lookup(const KeyT &Val) const {
if (LookupBucketFor(KV.first, TheBucket))
return std::make_pair(iterator(TheBucket, Buckets+NumBuckets),
false); // Already in map.
-
+
// Otherwise, insert the new element.
TheBucket = InsertIntoBucket(KV.first, KV.second, TheBucket);
return std::make_pair(iterator(TheBucket, Buckets+NumBuckets),
true);
}
-
+
/// insert - Range insertion of pairs.
template<typename InputIt>
void insert(InputIt I, InputIt E) {
insert(*I);
}
-
+
bool erase(const KeyT &Val) {
BucketT *TheBucket;
if (!LookupBucketFor(Val, TheBucket))
BucketT *TheBucket;
if (LookupBucketFor(Key, TheBucket))
return *TheBucket;
-
+
return *InsertIntoBucket(Key, ValueT(), TheBucket);
}
-
+
ValueT &operator[](const KeyT &Key) {
return FindAndConstruct(Key).second;
}
-
+
DenseMap& operator=(const DenseMap& other) {
CopyFrom(other);
return *this;
}
-
+
private:
void CopyFrom(const DenseMap& other) {
if (NumBuckets != 0 && (!KeyInfoT::isPod() || !ValueInfoT::isPod())) {
P->first.~KeyT();
}
}
-
+
NumEntries = other.NumEntries;
NumTombstones = other.NumTombstones;
-
+
if (NumBuckets)
operator delete(Buckets);
Buckets = static_cast<BucketT*>(operator new(sizeof(BucketT) *
other.NumBuckets));
-
+
if (KeyInfoT::isPod() && ValueInfoT::isPod())
memcpy(Buckets, other.Buckets, other.NumBuckets * sizeof(BucketT));
else
}
NumBuckets = other.NumBuckets;
}
-
+
BucketT *InsertIntoBucket(const KeyT &Key, const ValueT &Value,
BucketT *TheBucket) {
// If the load of the hash table is more than 3/4, or if fewer than 1/8 of
// table completely filled with tombstones, no lookup would ever succeed,
// causing infinite loops in lookup.
if (NumEntries*4 >= NumBuckets*3 ||
- NumBuckets-(NumEntries+NumTombstones) < NumBuckets/8) {
+ NumBuckets-(NumEntries+NumTombstones) < NumBuckets/8) {
this->grow(NumBuckets * 2);
LookupBucketFor(Key, TheBucket);
}
++NumEntries;
-
+
// If we are writing over a tombstone, remember this.
if (!KeyInfoT::isEqual(TheBucket->first, getEmptyKey()))
--NumTombstones;
-
+
TheBucket->first = Key;
new (&TheBucket->second) ValueT(Value);
return TheBucket;
static const KeyT getTombstoneKey() {
return KeyInfoT::getTombstoneKey();
}
-
+
/// LookupBucketFor - Lookup the appropriate bucket for Val, returning it in
/// FoundBucket. If the bucket contains the key and a value, this returns
/// true, otherwise it returns a bucket with an empty marker or tombstone and
unsigned BucketNo = getHashValue(Val);
unsigned ProbeAmt = 1;
BucketT *BucketsPtr = Buckets;
-
+
// FoundTombstone - Keep track of whether we find a tombstone while probing.
BucketT *FoundTombstone = 0;
const KeyT EmptyKey = getEmptyKey();
assert(!KeyInfoT::isEqual(Val, EmptyKey) &&
!KeyInfoT::isEqual(Val, TombstoneKey) &&
"Empty/Tombstone value shouldn't be inserted into map!");
-
+
while (1) {
BucketT *ThisBucket = BucketsPtr + (BucketNo & (NumBuckets-1));
// Found Val's bucket? If so, return it.
FoundBucket = ThisBucket;
return true;
}
-
+
// If we found an empty bucket, the key doesn't exist in the set.
// Insert it and return the default value.
if (KeyInfoT::isEqual(ThisBucket->first, EmptyKey)) {
FoundBucket = FoundTombstone ? FoundTombstone : ThisBucket;
return false;
}
-
+
// If this is a tombstone, remember it. If Val ends up not in the map, we
// prefer to return it than something that would require more probing.
if (KeyInfoT::isEqual(ThisBucket->first, TombstoneKey) && !FoundTombstone)
FoundTombstone = ThisBucket; // Remember the first tombstone found.
-
+
// Otherwise, it's a hash collision or a tombstone, continue quadratic
// probing.
BucketNo += ProbeAmt++;
for (unsigned i = 0; i != InitBuckets; ++i)
new (&Buckets[i].first) KeyT(EmptyKey);
}
-
+
void grow(unsigned AtLeast) {
unsigned OldNumBuckets = NumBuckets;
BucketT *OldBuckets = Buckets;
-
+
// Double the number of buckets.
while (NumBuckets <= AtLeast)
NumBuckets <<= 1;
assert(!FoundVal && "Key already in new map?");
DestBucket->first = B->first;
new (&DestBucket->second) ValueT(B->second);
-
+
// Free the value.
B->second.~ValueT();
}
B->first.~KeyT();
}
-
+
// Free the old table.
operator delete(OldBuckets);
}
-
+
void shrink_and_clear() {
unsigned OldNumBuckets = NumBuckets;
BucketT *OldBuckets = Buckets;
-
+
// Reduce the number of buckets.
NumBuckets = NumEntries > 32 ? 1 << (Log2_32_Ceil(NumEntries) + 1)
: 64;
}
B->first.~KeyT();
}
-
+
// Free the old table.
operator delete(OldBuckets);
-
+
NumEntries = 0;
}
};
DenseMapIterator(const BucketT *Pos, const BucketT *E) : Ptr(Pos), End(E) {
AdvancePastEmptyBuckets();
}
-
+
std::pair<KeyT, ValueT> &operator*() const {
return *const_cast<BucketT*>(Ptr);
}
std::pair<KeyT, ValueT> *operator->() const {
return const_cast<BucketT*>(Ptr);
}
-
+
bool operator==(const DenseMapIterator &RHS) const {
return Ptr == RHS.Ptr;
}
bool operator!=(const DenseMapIterator &RHS) const {
return Ptr != RHS.Ptr;
}
-
+
inline DenseMapIterator& operator++() { // Preincrement
++Ptr;
AdvancePastEmptyBuckets();
DenseMapIterator operator++(int) { // Postincrement
DenseMapIterator tmp = *this; ++*this; return tmp;
}
-
+
private:
void AdvancePastEmptyBuckets() {
const KeyT Empty = KeyInfoT::getEmptyKey();
const KeyT Tombstone = KeyInfoT::getTombstoneKey();
- while (Ptr != End &&
+ while (Ptr != End &&
(KeyInfoT::isEqual(Ptr->first, Empty) ||
KeyInfoT::isEqual(Ptr->first, Tombstone)))
++Ptr;
public:
DenseSet(const DenseSet &Other) : TheMap(Other.TheMap) {}
explicit DenseSet(unsigned NumInitBuckets = 64) : TheMap(NumInitBuckets) {}
-
+
bool empty() const { return TheMap.empty(); }
- unsigned size() const { return TheMap.size(); }
-
+ unsigned size() const { return TheMap.size(); }
+
void clear() {
TheMap.clear();
}
-
+
bool count(const ValueT &V) const {
return TheMap.count(V);
}
-
+
void erase(const ValueT &V) {
TheMap.erase(V);
}
-
+
DenseSet &operator=(const DenseSet &RHS) {
TheMap = RHS.TheMap;
return *this;
}
-
+
// Iterators.
-
+
class Iterator {
typename MapTy::iterator I;
public:
Iterator(const typename MapTy::iterator &i) : I(i) {}
-
+
ValueT& operator*() { return I->first; }
ValueT* operator->() { return &I->first; }
-
+
Iterator& operator++() { ++I; return *this; };
bool operator==(const Iterator& X) const { return I == X.I; }
bool operator!=(const Iterator& X) const { return I != X.I; }
};
-
+
class ConstIterator {
typename MapTy::const_iterator I;
public:
ConstIterator(const typename MapTy::const_iterator &i) : I(i) {}
-
+
const ValueT& operator*() { return I->first; }
const ValueT* operator->() { return &I->first; }
-
+
ConstIterator& operator++() { ++I; return *this; };
bool operator==(const ConstIterator& X) const { return I == X.I; }
bool operator!=(const ConstIterator& X) const { return I != X.I; }
};
-
+
typedef Iterator iterator;
typedef ConstIterator const_iterator;
-
+
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()); }
/// instance of the node in the set. If the node already exists, return
/// it, otherwise return the bucket it should be inserted into.
/// 2. Given a node that has already been created, remove it from the set.
-///
+///
/// This class is implemented as a single-link chained hash table, where the
/// "buckets" are actually the nodes themselves (the next pointer is in the
/// node). The last node points back to the bucket to simplify node removal.
/// Any node that is to be included in the folding set must be a subclass of
/// FoldingSetNode. The node class must also define a Profile method used to
/// establish the unique bits of data for the node. The Profile method is
-/// passed a FoldingSetNodeID object which is used to gather the bits. Just
+/// passed a FoldingSetNodeID object which is used to gather the bits. Just
/// call one of the Add* functions defined in the FoldingSetImpl::NodeID class.
/// NOTE: That the folding set does not own the nodes and it is the
/// responsibility of the user to dispose of the nodes.
/// Eg.
/// FoldingSet<MyNode> MyFoldingSet;
///
-/// Four public methods are available to manipulate the folding set;
+/// Four public methods are available to manipulate the folding set;
///
/// 1) If you have an existing node that you want add to the set but unsure
/// that the node might already exist then call;
/// bool WasRemoved = RemoveNode(N);
///
/// The result indicates whether the node existed in the folding set.
-
+
class FoldingSetNodeID;
-
+
//===----------------------------------------------------------------------===//
/// FoldingSetImpl - Implements the folding set functionality. The main
/// structure is an array of buckets. Each bucket is indexed by the hash of
/// the nodes it contains. The bucket itself points to the nodes contained
/// in the bucket via a singly linked list. The last node in the list points
/// back to the bucket to facilitate node removal.
-///
+///
class FoldingSetImpl {
protected:
/// Buckets - Array of bucket chains.
///
void **Buckets;
-
+
/// NumBuckets - Length of the Buckets array. Always a power of 2.
///
unsigned NumBuckets;
-
+
/// NumNodes - Number of nodes in the folding set. Growth occurs when NumNodes
/// is greater than twice the number of buckets.
unsigned NumNodes;
-
+
public:
explicit FoldingSetImpl(unsigned Log2InitSize = 6);
virtual ~FoldingSetImpl();
-
+
//===--------------------------------------------------------------------===//
/// Node - This class is used to maintain the singly linked bucket list in
/// a folding set.
private:
// NextInFoldingSetBucket - next link in the bucket list.
void *NextInFoldingSetBucket;
-
+
public:
Node() : NextInFoldingSetBucket(0) {}
-
+
// Accessors
void *getNextInBucket() const { return NextInFoldingSetBucket; }
void SetNextInBucket(void *N) { NextInFoldingSetBucket = N; }
/// RemoveNode - Remove a node from the folding set, returning true if one
/// was removed or false if the node was not in the folding set.
bool RemoveNode(Node *N);
-
+
/// GetOrInsertNode - If there is an existing simple Node exactly
/// equal to the specified node, return it. Otherwise, insert 'N' and return
/// it instead.
Node *GetOrInsertNode(Node *N);
-
+
/// FindNodeOrInsertPos - Look up the node specified by ID. If it exists,
/// return it. If not, return the insertion token that will make insertion
/// faster.
Node *FindNodeOrInsertPos(const FoldingSetNodeID &ID, void *&InsertPos);
-
+
/// InsertNode - Insert the specified node into the folding set, knowing that
- /// it is not already in the folding set. InsertPos must be obtained from
+ /// it is not already in the folding set. InsertPos must be obtained from
/// FindNodeOrInsertPos.
void InsertNode(Node *N, void *InsertPos);
-
+
/// size - Returns the number of nodes in the folding set.
unsigned size() const { return NumNodes; }
/// empty - Returns true if there are no nodes in the folding set.
bool empty() const { return NumNodes == 0; }
-
+
private:
/// GrowHashTable - Double the size of the hash table and rehash everything.
///
void GrowHashTable();
-
+
protected:
/// GetNodeProfile - Instantiations of the FoldingSet template implement
static inline void Profile(const T& X, FoldingSetNodeID& ID) { X.Profile(ID);}
static inline void Profile(T& X, FoldingSetNodeID& ID) { X.Profile(ID); }
};
-
+
//===--------------------------------------------------------------------===//
/// FoldingSetNodeID - This class is used to gather all the unique data bits of
/// a node. When all the bits are gathered this class is used to produce a
-/// hash value for the node.
+/// hash value for the node.
///
class FoldingSetNodeID {
/// Bits - Vector of all the data bits that make the node unique.
/// Use a SmallVector to avoid a heap allocation in the common case.
SmallVector<unsigned, 32> Bits;
-
+
public:
FoldingSetNodeID() {}
-
+
/// getRawData - Return the ith entry in the Bits data.
///
unsigned getRawData(unsigned i) const {
return Bits[i];
}
-
+
/// Add* - Add various data types to Bit data.
///
void AddPointer(const void *Ptr);
void AddDouble(double D);
void AddString(const std::string &String);
void AddString(const char* String);
-
+
template <typename T>
inline void Add(const T& x) { FoldingSetTrait<T>::Profile(x, *this); }
-
+
/// clear - Clear the accumulated profile, allowing this FoldingSetNodeID
/// object to be used to compute a new profile.
inline void clear() { Bits.clear(); }
-
+
/// ComputeHash - Compute a strong hash value for this FoldingSetNodeID, used
/// to lookup the node in the FoldingSetImpl.
unsigned ComputeHash() const;
-
+
/// operator== - Used to compare two nodes to each other.
///
bool operator==(const FoldingSetNodeID &RHS) const;
-};
+};
// Convenience type to hide the implementation of the folding set.
typedef FoldingSetImpl::Node FoldingSetNode;
template<class T> class FoldingSetIterator;
template<class T> class FoldingSetBucketIterator;
-
+
//===----------------------------------------------------------------------===//
/// FoldingSet - This template class is used to instantiate a specialized
-/// implementation of the folding set to the node class T. T must be a
+/// implementation of the folding set to the node class T. T must be a
/// subclass of FoldingSetNode and implement a Profile function.
///
template<class T> class FoldingSet : public FoldingSetImpl {
T *TN = static_cast<T *>(N);
FoldingSetTrait<T>::Profile(*TN,ID);
}
-
+
public:
explicit FoldingSet(unsigned Log2InitSize = 6)
: FoldingSetImpl(Log2InitSize)
{}
-
+
typedef FoldingSetIterator<T> iterator;
iterator begin() { return iterator(Buckets); }
iterator end() { return iterator(Buckets+NumBuckets); }
const_iterator begin() const { return const_iterator(Buckets); }
const_iterator end() const { return const_iterator(Buckets+NumBuckets); }
- typedef FoldingSetBucketIterator<T> bucket_iterator;
+ typedef FoldingSetBucketIterator<T> bucket_iterator;
bucket_iterator bucket_begin(unsigned hash) {
return bucket_iterator(Buckets + (hash & (NumBuckets-1)));
}
-
+
bucket_iterator bucket_end(unsigned hash) {
return bucket_iterator(Buckets + (hash & (NumBuckets-1)), true);
}
-
+
/// GetOrInsertNode - If there is an existing simple Node exactly
/// equal to the specified node, return it. Otherwise, insert 'N' and
/// return it instead.
T *GetOrInsertNode(Node *N) {
return static_cast<T *>(FoldingSetImpl::GetOrInsertNode(N));
}
-
+
/// FindNodeOrInsertPos - Look up the node specified by ID. If it exists,
/// return it. If not, return the insertion token that will make insertion
/// faster.
FoldingSetNode *NodePtr;
FoldingSetIteratorImpl(void **Bucket);
void advance();
-
+
public:
bool operator==(const FoldingSetIteratorImpl &RHS) const {
return NodePtr == RHS.NodePtr;
class FoldingSetIterator : public FoldingSetIteratorImpl {
public:
explicit FoldingSetIterator(void **Bucket) : FoldingSetIteratorImpl(Bucket) {}
-
+
T &operator*() const {
return *static_cast<T*>(NodePtr);
}
-
+
T *operator->() const {
return static_cast<T*>(NodePtr);
}
-
+
inline FoldingSetIterator& operator++() { // Preincrement
advance();
return *this;
FoldingSetIterator tmp = *this; ++*this; return tmp;
}
};
-
+
//===----------------------------------------------------------------------===//
/// FoldingSetBucketIteratorImpl - This is the common bucket iterator support
/// shared by all folding sets, which knows how to walk a particular bucket
/// of a folding set hash table.
-
+
class FoldingSetBucketIteratorImpl {
protected:
void *Ptr;
explicit FoldingSetBucketIteratorImpl(void **Bucket);
-
+
FoldingSetBucketIteratorImpl(void **Bucket, bool)
: Ptr(Bucket) {}
uintptr_t x = reinterpret_cast<uintptr_t>(Probe) & ~0x1;
Ptr = reinterpret_cast<void*>(x);
}
-
+
public:
bool operator==(const FoldingSetBucketIteratorImpl &RHS) const {
return Ptr == RHS.Ptr;
return Ptr != RHS.Ptr;
}
};
-
-
+
+
template<class T>
class FoldingSetBucketIterator : public FoldingSetBucketIteratorImpl {
public:
- explicit FoldingSetBucketIterator(void **Bucket) :
+ explicit FoldingSetBucketIterator(void **Bucket) :
FoldingSetBucketIteratorImpl(Bucket) {}
-
- FoldingSetBucketIterator(void **Bucket, bool) :
+
+ FoldingSetBucketIterator(void **Bucket, bool) :
FoldingSetBucketIteratorImpl(Bucket, true) {}
-
- T& operator*() const { return *static_cast<T*>(Ptr); }
+
+ T& operator*() const { return *static_cast<T*>(Ptr); }
T* operator->() const { return static_cast<T*>(Ptr); }
-
+
inline FoldingSetBucketIterator& operator++() { // Preincrement
advance();
return *this;
- }
+ }
FoldingSetBucketIterator operator++(int) { // Postincrement
FoldingSetBucketIterator tmp = *this; ++*this; return tmp;
}
};
-
+
//===----------------------------------------------------------------------===//
/// FoldingSetNodeWrapper - This template class is used to "wrap" arbitrary
/// types in an enclosing object so that they can be inserted into FoldingSets.
public:
explicit FoldingSetNodeWrapper(const T& x) : data(x) {}
virtual ~FoldingSetNodeWrapper() {}
-
+
template<typename A1>
explicit FoldingSetNodeWrapper(const A1& a1)
: data(a1) {}
-
+
template <typename A1, typename A2>
explicit FoldingSetNodeWrapper(const A1& a1, const A2& a2)
: data(a1,a2) {}
-
+
template <typename A1, typename A2, typename A3>
explicit FoldingSetNodeWrapper(const A1& a1, const A2& a2, const A3& a3)
: data(a1,a2,a3) {}
-
+
template <typename A1, typename A2, typename A3, typename A4>
explicit FoldingSetNodeWrapper(const A1& a1, const A2& a2, const A3& a3,
const A4& a4)
: data(a1,a2,a3,a4) {}
-
+
template <typename A1, typename A2, typename A3, typename A4, typename A5>
explicit FoldingSetNodeWrapper(const A1& a1, const A2& a2, const A3& a3,
const A4& a4, const A5& a5)
: data(a1,a2,a3,a4,a5) {}
-
+
void Profile(FoldingSetNodeID& ID) { FoldingSetTrait<T>::Profile(data, ID); }
T& getValue() { return data; }
operator T&() { return data; }
operator const T&() const { return data; }
-};
-
+};
+
//===----------------------------------------------------------------------===//
// Partial specializations of FoldingSetTrait.
struct GraphTraits<Inverse<Inverse<T> > > {
typedef typename GraphTraits<T>::NodeType NodeType;
typedef typename GraphTraits<T>::ChildIteratorType ChildIteratorType;
-
+
static NodeType *getEntryNode(Inverse<Inverse<T> > *G) {
return GraphTraits<T>::getEntryNode(G->Graph.Graph);
}
-
+
static ChildIteratorType child_begin(NodeType* N) {
return GraphTraits<T>::child_begin(N);
}
-
+
static ChildIteratorType child_end(NodeType* N) {
return GraphTraits<T>::child_end(N);
}
namespace llvm {
template <typename T> class ImmutableListFactory;
-
+
template <typename T>
class ImmutableListImpl : public FoldingSetNode {
T Head;
ImmutableListImpl(const T& head, const ImmutableListImpl* tail = 0)
: Head(head), Tail(tail) {}
-
+
friend class ImmutableListFactory<T>;
-
+
// Do not implement.
void operator=(const ImmutableListImpl&);
ImmutableListImpl(const ImmutableListImpl&);
-
+
public:
const T& getHead() const { return Head; }
const ImmutableListImpl* getTail() const { return Tail; }
-
+
static inline void Profile(FoldingSetNodeID& ID, const T& H,
const ImmutableListImpl* L){
ID.AddPointer(L);
ID.Add(H);
}
-
+
void Profile(FoldingSetNodeID& ID) {
Profile(ID, Head, Tail);
}
};
-
+
/// ImmutableList - This class represents an immutable (functional) list.
/// It is implemented as a smart pointer (wraps ImmutableListImpl), so it
/// it is intended to always be copied by value as if it were a pointer.
const ImmutableListImpl<T>* getInternalPointer() const {
return X;
}
-
+
class iterator {
const ImmutableListImpl<T>* L;
public:
iterator() : L(0) {}
iterator(ImmutableList l) : L(l.getInternalPointer()) {}
-
+
iterator& operator++() { L = L->getTail(); return *this; }
bool operator==(const iterator& I) const { return L == I.L; }
bool operator!=(const iterator& I) const { return L != I.L; }
- const value_type& operator*() const { return L->getHead(); }
- ImmutableList getList() const { return L; }
+ const value_type& operator*() const { return L->getHead(); }
+ ImmutableList getList() const { return L; }
};
/// begin - Returns an iterator referring to the head of the list, or
/// an iterator denoting the end of the list if the list is empty.
iterator begin() const { return iterator(X); }
-
+
/// end - Returns an iterator denoting the end of the list. This iterator
/// does not refer to a valid list element.
iterator end() const { return iterator(); }
/// isEmpty - Returns true if the list is empty.
bool isEmpty() const { return !X; }
-
+
/// isEqual - Returns true if two lists are equal. Because all lists created
/// from the same ImmutableListFactory are uniqued, this has O(1) complexity
/// because it the contents of the list do not need to be compared. Note
/// that you should only compare two lists created from the same
/// ImmutableListFactory.
- bool isEqual(const ImmutableList& L) const { return X == L.X; }
+ bool isEqual(const ImmutableList& L) const { return X == L.X; }
bool operator==(const ImmutableList& L) const { return isEqual(L); }
assert (!isEmpty() && "Cannot get the head of an empty list.");
return X->getHead();
}
-
+
/// getTail - Returns the tail of the list, which is another (possibly empty)
/// ImmutableList.
ImmutableList getTail() {
return X ? X->getTail() : 0;
- }
+ }
void Profile(FoldingSetNodeID& ID) const {
ID.AddPointer(X);
}
};
-
+
template <typename T>
class ImmutableListFactory {
- typedef ImmutableListImpl<T> ListTy;
+ typedef ImmutableListImpl<T> ListTy;
typedef FoldingSet<ListTy> CacheTy;
-
+
CacheTy Cache;
uintptr_t Allocator;
-
+
bool ownsAllocator() const {
return Allocator & 0x1 ? false : true;
}
-
- BumpPtrAllocator& getAllocator() const {
+
+ BumpPtrAllocator& getAllocator() const {
return *reinterpret_cast<BumpPtrAllocator*>(Allocator & ~0x1);
- }
+ }
public:
ImmutableListFactory()
: Allocator(reinterpret_cast<uintptr_t>(new BumpPtrAllocator())) {}
-
+
ImmutableListFactory(BumpPtrAllocator& Alloc)
: Allocator(reinterpret_cast<uintptr_t>(&Alloc) | 0x1) {}
-
+
~ImmutableListFactory() {
if (ownsAllocator()) delete &getAllocator();
}
-
+
ImmutableList<T> Concat(const T& Head, ImmutableList<T> Tail) {
// Profile the new list to see if it already exists in our cache.
FoldingSetNodeID ID;
void* InsertPos;
-
+
const ListTy* TailImpl = Tail.getInternalPointer();
ListTy::Profile(ID, Head, TailImpl);
ListTy* L = Cache.FindNodeOrInsertPos(ID, InsertPos);
-
+
if (!L) {
// The list does not exist in our cache. Create it.
BumpPtrAllocator& A = getAllocator();
L = (ListTy*) A.Allocate<ListTy>();
new (L) ListTy(Head, TailImpl);
-
+
// Insert the new list into the cache.
Cache.InsertNode(L, InsertPos);
}
-
+
return L;
}
-
+
ImmutableList<T> Add(const T& D, ImmutableList<T> L) {
return Concat(D, L);
}
-
+
ImmutableList<T> GetEmptyList() const {
return ImmutableList<T>(0);
}
-
+
ImmutableList<T> Create(const T& X) {
return Concat(X, GetEmptyList());
}
};
-
+
//===----------------------------------------------------------------------===//
// Partially-specialized Traits.
//===----------------------------------------------------------------------===//
}
static unsigned getHashValue(ImmutableList<T> X) {
uintptr_t PtrVal = reinterpret_cast<uintptr_t>(X.getInternalPointer());
- return (unsigned((uintptr_t)PtrVal) >> 4) ^
+ return (unsigned((uintptr_t)PtrVal) >> 4) ^
(unsigned((uintptr_t)PtrVal) >> 9);
}
static bool isEqual(ImmutableList<T> X1, ImmutableList<T> X2) {
}
static bool isPod() { return true; }
};
-
+
} // end llvm namespace
#endif
typedef const T& key_type_ref;
typedef const S data_type;
typedef const S& data_type_ref;
-
+
static inline key_type_ref KeyOfValue(value_type_ref V) {
return V.first;
}
-
+
static inline data_type_ref DataOfValue(value_type_ref V) {
return V.second;
}
-
+
static inline bool isEqual(key_type_ref L, key_type_ref R) {
return ImutContainerInfo<T>::isEqual(L,R);
- }
+ }
static inline bool isLess(key_type_ref L, key_type_ref R) {
return ImutContainerInfo<T>::isLess(L,R);
}
-
+
static inline bool isDataEqual(data_type_ref L, data_type_ref R) {
return ImutContainerInfo<S>::isEqual(L,R);
}
-
+
static inline void Profile(FoldingSetNodeID& ID, value_type_ref V) {
ImutContainerInfo<T>::Profile(ID, V.first);
ImutContainerInfo<S>::Profile(ID, V.second);
}
-};
+};
-
-template <typename KeyT, typename ValT,
+
+template <typename KeyT, typename ValT,
typename ValInfo = ImutKeyValueInfo<KeyT,ValT> >
class ImmutableMap {
public:
typedef typename ValInfo::data_type data_type;
typedef typename ValInfo::data_type_ref data_type_ref;
typedef ImutAVLTree<ValInfo> TreeTy;
-
+
private:
TreeTy* Root;
-
+
public:
/// Constructs a map from a pointer to a tree root. In general one
/// should use a Factory object to create maps instead of directly
/// invoking the constructor, but there are cases where make this
/// constructor public is useful.
explicit ImmutableMap(const TreeTy* R) : Root(const_cast<TreeTy*>(R)) {}
-
+
class Factory {
typename TreeTy::Factory F;
-
+
public:
Factory() {}
-
+
Factory(BumpPtrAllocator& Alloc)
: F(Alloc) {}
-
+
ImmutableMap GetEmptyMap() { return ImmutableMap(F.GetEmptyTree()); }
-
+
ImmutableMap Add(ImmutableMap Old, key_type_ref K, data_type_ref D) {
return ImmutableMap(F.Add(Old.Root,
std::make_pair<key_type,data_type>(K,D)));
}
-
+
ImmutableMap Remove(ImmutableMap Old, key_type_ref K) {
return ImmutableMap(F.Remove(Old.Root,K));
- }
-
+ }
+
private:
Factory(const Factory& RHS) {};
- void operator=(const Factory& RHS) {};
+ void operator=(const Factory& RHS) {};
};
-
- friend class Factory;
-
+
+ friend class Factory;
+
bool contains(key_type_ref K) const {
return Root ? Root->contains(K) : false;
}
-
+
bool operator==(ImmutableMap RHS) const {
return Root && RHS.Root ? Root->isEqual(*RHS.Root) : Root == RHS.Root;
}
-
+
bool operator!=(ImmutableMap RHS) const {
return Root && RHS.Root ? Root->isNotEqual(*RHS.Root) : Root != RHS.Root;
}
-
+
TreeTy* getRoot() const { return Root; }
-
+
bool isEmpty() const { return !Root; }
- //===--------------------------------------------------===//
+ //===--------------------------------------------------===//
// Foreach - A limited form of map iteration.
//===--------------------------------------------------===//
template <typename Callback>
struct CBWrapper {
Callback C;
- void operator()(value_type_ref V) { C(V.first,V.second); }
- };
-
+ void operator()(value_type_ref V) { C(V.first,V.second); }
+ };
+
template <typename Callback>
struct CBWrapperRef {
Callback &C;
CBWrapperRef(Callback& c) : C(c) {}
-
- void operator()(value_type_ref V) { C(V.first,V.second); }
+
+ void operator()(value_type_ref V) { C(V.first,V.second); }
};
-
-public:
+
+public:
template <typename Callback>
- void foreach(Callback& C) {
- if (Root) {
+ void foreach(Callback& C) {
+ if (Root) {
CBWrapperRef<Callback> CB(C);
Root->foreach(CB);
}
}
-
+
template <typename Callback>
- void foreach() {
+ void foreach() {
if (Root) {
CBWrapper<Callback> CB;
Root->foreach(CB);
}
}
-
- //===--------------------------------------------------===//
+
+ //===--------------------------------------------------===//
// For testing.
- //===--------------------------------------------------===//
-
+ //===--------------------------------------------------===//
+
void verify() const { if (Root) Root->verify(); }
-
- //===--------------------------------------------------===//
+
+ //===--------------------------------------------------===//
// Iterators.
- //===--------------------------------------------------===//
-
+ //===--------------------------------------------------===//
+
class iterator {
typename TreeTy::iterator itr;
-
+
iterator() {}
iterator(TreeTy* t) : itr(t) {}
friend class ImmutableMap;
public:
value_type_ref operator*() const { return itr->getValue(); }
value_type* operator->() const { return &itr->getValue(); }
-
+
key_type_ref getKey() const { return itr->getValue().first; }
data_type_ref getData() const { return itr->getValue().second; }
-
-
+
+
iterator& operator++() { ++itr; return *this; }
iterator operator++(int) { iterator tmp(*this); ++itr; return tmp; }
iterator& operator--() { --itr; return *this; }
iterator operator--(int) { iterator tmp(*this); --itr; return tmp; }
bool operator==(const iterator& RHS) const { return RHS.itr == itr; }
- bool operator!=(const iterator& RHS) const { return RHS.itr != itr; }
+ bool operator!=(const iterator& RHS) const { return RHS.itr != itr; }
};
-
+
iterator begin() const { return iterator(Root); }
- iterator end() const { return iterator(); }
-
+ iterator end() const { return iterator(); }
+
data_type* lookup(key_type_ref K) const {
if (Root) {
TreeTy* T = Root->find(K);
if (T) return &T->getValue().second;
}
-
+
return 0;
}
-
- //===--------------------------------------------------===//
+
+ //===--------------------------------------------------===//
// Utility methods.
- //===--------------------------------------------------===//
-
+ //===--------------------------------------------------===//
+
inline unsigned getHeight() const { return Root ? Root->getHeight() : 0; }
static inline void Profile(FoldingSetNodeID& ID, const ImmutableMap& M) {
ID.AddPointer(M.Root);
}
-
+
inline void Profile(FoldingSetNodeID& ID) const {
return Profile(ID,*this);
- }
+ }
};
-
+
} // end namespace llvm
#endif
#include <functional>
namespace llvm {
-
-//===----------------------------------------------------------------------===//
+
+//===----------------------------------------------------------------------===//
// Immutable AVL-Tree Definition.
//===----------------------------------------------------------------------===//
template <typename ImutInfo> class ImutAVLFactory;
template <typename ImutInfo> class ImutAVLTreeInOrderIterator;
template <typename ImutInfo> class ImutAVLTreeGenericIterator;
-
+
template <typename ImutInfo >
class ImutAVLTree : public FoldingSetNode {
public:
typedef ImutAVLFactory<ImutInfo> Factory;
friend class ImutAVLFactory<ImutInfo>;
-
+
friend class ImutAVLTreeGenericIterator<ImutInfo>;
friend class FoldingSet<ImutAVLTree>;
-
+
typedef ImutAVLTreeInOrderIterator<ImutInfo> iterator;
-
- //===----------------------------------------------------===//
+
+ //===----------------------------------------------------===//
// Public Interface.
- //===----------------------------------------------------===//
-
+ //===----------------------------------------------------===//
+
/// getLeft - Returns a pointer to the left subtree. This value
/// is NULL if there is no left subtree.
- ImutAVLTree* getLeft() const {
+ ImutAVLTree* getLeft() const {
assert (!isMutable() && "Node is incorrectly marked mutable.");
-
+
return reinterpret_cast<ImutAVLTree*>(Left);
}
-
+
/// getRight - Returns a pointer to the right subtree. This value is
/// NULL if there is no right subtree.
- ImutAVLTree* getRight() const { return Right; }
-
-
+ ImutAVLTree* getRight() const { return Right; }
+
+
/// getHeight - Returns the height of the tree. A tree with no subtrees
/// has a height of 1.
- unsigned getHeight() const { return Height; }
-
+ unsigned getHeight() const { return Height; }
+
/// getValue - Returns the data value associated with the tree node.
const value_type& getValue() const { return Value; }
-
+
/// find - Finds the subtree associated with the specified key value.
/// This method returns NULL if no matching subtree is found.
ImutAVLTree* find(key_type_ref K) {
ImutAVLTree *T = this;
-
+
while (T) {
key_type_ref CurrentKey = ImutInfo::KeyOfValue(T->getValue());
-
+
if (ImutInfo::isEqual(K,CurrentKey))
return T;
else if (ImutInfo::isLess(K,CurrentKey))
else
T = T->getRight();
}
-
+
return NULL;
}
-
+
/// size - Returns the number of nodes in the tree, which includes
/// both leaves and non-leaf nodes.
unsigned size() const {
unsigned n = 1;
-
+
if (const ImutAVLTree* L = getLeft()) n += L->size();
if (const ImutAVLTree* R = getRight()) n += R->size();
-
+
return n;
}
-
+
/// begin - Returns an iterator that iterates over the nodes of the tree
/// in an inorder traversal. The returned iterator thus refers to the
/// the tree node with the minimum data element.
iterator begin() const { return iterator(this); }
-
+
/// end - Returns an iterator for the tree that denotes the end of an
/// inorder traversal.
iterator end() const { return iterator(); }
-
+
bool ElementEqual(value_type_ref V) const {
// Compare the keys.
if (!ImutInfo::isEqual(ImutInfo::KeyOfValue(getValue()),
ImutInfo::KeyOfValue(V)))
return false;
-
+
// Also compare the data values.
if (!ImutInfo::isDataEqual(ImutInfo::DataOfValue(getValue()),
ImutInfo::DataOfValue(V)))
return false;
-
+
return true;
}
-
+
bool ElementEqual(const ImutAVLTree* RHS) const {
return ElementEqual(RHS->getValue());
}
-
+
/// isEqual - Compares two trees for structural equality and returns true
/// if they are equal. This worst case performance of this operation is
// linear in the sizes of the trees.
bool isEqual(const ImutAVLTree& RHS) const {
if (&RHS == this)
return true;
-
+
iterator LItr = begin(), LEnd = end();
iterator RItr = RHS.begin(), REnd = RHS.end();
-
+
while (LItr != LEnd && RItr != REnd) {
if (*LItr == *RItr) {
LItr.SkipSubTree();
RItr.SkipSubTree();
continue;
}
-
+
if (!LItr->ElementEqual(*RItr))
return false;
-
+
++LItr;
++RItr;
}
-
+
return LItr == LEnd && RItr == REnd;
}
/// isNotEqual - Compares two trees for structural inequality. Performance
/// is the same is isEqual.
bool isNotEqual(const ImutAVLTree& RHS) const { return !isEqual(RHS); }
-
+
/// contains - Returns true if this tree contains a subtree (node) that
/// has an data element that matches the specified key. Complexity
/// is logarithmic in the size of the tree.
bool contains(const key_type_ref K) { return (bool) find(K); }
-
+
/// foreach - A member template the accepts invokes operator() on a functor
/// object (specifed by Callback) for every node/subtree in the tree.
/// Nodes are visited using an inorder traversal.
template <typename Callback>
void foreach(Callback& C) {
if (ImutAVLTree* L = getLeft()) L->foreach(C);
-
- C(Value);
-
+
+ C(Value);
+
if (ImutAVLTree* R = getRight()) R->foreach(C);
}
-
+
/// verify - A utility method that checks that the balancing and
/// ordering invariants of the tree are satisifed. It is a recursive
/// method that returns the height of the tree, which is then consumed
unsigned verify() const {
unsigned HL = getLeft() ? getLeft()->verify() : 0;
unsigned HR = getRight() ? getRight()->verify() : 0;
-
- assert (getHeight() == ( HL > HR ? HL : HR ) + 1
+
+ assert (getHeight() == ( HL > HR ? HL : HR ) + 1
&& "Height calculation wrong.");
-
+
assert ((HL > HR ? HL-HR : HR-HL) <= 2
&& "Balancing invariant violated.");
-
-
+
+
assert (!getLeft()
|| ImutInfo::isLess(ImutInfo::KeyOfValue(getLeft()->getValue()),
ImutInfo::KeyOfValue(getValue()))
&& "Value in left child is not less that current value.");
-
-
+
+
assert (!getRight()
|| ImutInfo::isLess(ImutInfo::KeyOfValue(getValue()),
ImutInfo::KeyOfValue(getRight()->getValue()))
&& "Current value is not less that value of right child.");
-
+
return getHeight();
}
-
+
/// Profile - Profiling for ImutAVLTree.
void Profile(llvm::FoldingSetNodeID& ID) {
ID.AddInteger(ComputeDigest());
}
-
- //===----------------------------------------------------===//
+
+ //===----------------------------------------------------===//
// Internal Values.
//===----------------------------------------------------===//
-
+
private:
uintptr_t Left;
ImutAVLTree* Right;
unsigned Height;
value_type Value;
unsigned Digest;
-
- //===----------------------------------------------------===//
+
+ //===----------------------------------------------------===//
// Internal methods (node manipulation; used by Factory).
//===----------------------------------------------------===//
private:
-
+
enum { Mutable = 0x1 };
/// ImutAVLTree - Internal constructor that is only called by
ImutAVLTree(ImutAVLTree* l, ImutAVLTree* r, value_type_ref v, unsigned height)
: Left(reinterpret_cast<uintptr_t>(l) | Mutable),
Right(r), Height(height), Value(v), Digest(0) {}
-
-
+
+
/// isMutable - Returns true if the left and right subtree references
/// (as well as height) can be changed. If this method returns false,
/// the tree is truly immutable. Trees returned from an ImutAVLFactory
/// method returns false for an instance of ImutAVLTree, all subtrees
/// will also have this method return false. The converse is not true.
bool isMutable() const { return Left & Mutable; }
-
+
/// getSafeLeft - Returns the pointer to the left tree by always masking
/// out the mutable bit. This is used internally by ImutAVLFactory,
/// as no trees returned to the client should have the mutable flag set.
- ImutAVLTree* getSafeLeft() const {
+ ImutAVLTree* getSafeLeft() const {
return reinterpret_cast<ImutAVLTree*>(Left & ~Mutable);
}
-
- //===----------------------------------------------------===//
+
+ //===----------------------------------------------------===//
// Mutating operations. A tree root can be manipulated as
- // long as its reference has not "escaped" from internal
+ // long as its reference has not "escaped" from internal
// methods of a factory object (see below). When a tree
- // pointer is externally viewable by client code, the
- // internal "mutable bit" is cleared to mark the tree
+ // pointer is externally viewable by client code, the
+ // internal "mutable bit" is cleared to mark the tree
// immutable. Note that a tree that still has its mutable
// bit set may have children (subtrees) that are themselves
// immutable.
//===----------------------------------------------------===//
-
-
+
+
/// MarkImmutable - Clears the mutable flag for a tree. After this happens,
/// it is an error to call setLeft(), setRight(), and setHeight(). It
- /// is also then safe to call getLeft() instead of getSafeLeft().
+ /// is also then safe to call getLeft() instead of getSafeLeft().
void MarkImmutable() {
assert (isMutable() && "Mutable flag already removed.");
Left &= ~Mutable;
}
-
+
/// setLeft - Changes the reference of the left subtree. Used internally
/// by ImutAVLFactory.
void setLeft(ImutAVLTree* NewLeft) {
- assert (isMutable() &&
+ assert (isMutable() &&
"Only a mutable tree can have its left subtree changed.");
-
+
Left = reinterpret_cast<uintptr_t>(NewLeft) | Mutable;
}
-
+
/// setRight - Changes the reference of the right subtree. Used internally
/// by ImutAVLFactory.
void setRight(ImutAVLTree* NewRight) {
assert (isMutable() &&
"Only a mutable tree can have its right subtree changed.");
-
+
Right = NewRight;
}
-
+
/// setHeight - Changes the height of the tree. Used internally by
/// ImutAVLFactory.
void setHeight(unsigned h) {
assert (isMutable() && "Only a mutable tree can have its height changed.");
Height = h;
}
-
-
+
+
static inline
unsigned ComputeDigest(ImutAVLTree* L, ImutAVLTree* R, value_type_ref V) {
unsigned digest = 0;
-
+
if (L) digest += L->ComputeDigest();
-
+
{ // Compute digest of stored data.
FoldingSetNodeID ID;
ImutInfo::Profile(ID,V);
digest += ID.ComputeHash();
}
-
+
if (R) digest += R->ComputeDigest();
-
+
return digest;
}
-
+
inline unsigned ComputeDigest() {
if (Digest) return Digest;
-
+
unsigned X = ComputeDigest(getSafeLeft(), getRight(), getValue());
if (!isMutable()) Digest = X;
-
+
return X;
}
};
-//===----------------------------------------------------------------------===//
+//===----------------------------------------------------------------------===//
// Immutable AVL-Tree Factory class.
//===----------------------------------------------------------------------===//
-template <typename ImutInfo >
+template <typename ImutInfo >
class ImutAVLFactory {
typedef ImutAVLTree<ImutInfo> TreeTy;
typedef typename TreeTy::value_type_ref value_type_ref;
typedef typename TreeTy::key_type_ref key_type_ref;
-
+
typedef FoldingSet<TreeTy> CacheTy;
-
+
CacheTy Cache;
uintptr_t Allocator;
-
+
bool ownsAllocator() const {
return Allocator & 0x1 ? false : true;
}
- BumpPtrAllocator& getAllocator() const {
+ BumpPtrAllocator& getAllocator() const {
return *reinterpret_cast<BumpPtrAllocator*>(Allocator & ~0x1);
}
-
- //===--------------------------------------------------===//
+
+ //===--------------------------------------------------===//
// Public interface.
//===--------------------------------------------------===//
-
+
public:
ImutAVLFactory()
: Allocator(reinterpret_cast<uintptr_t>(new BumpPtrAllocator())) {}
-
+
ImutAVLFactory(BumpPtrAllocator& Alloc)
: Allocator(reinterpret_cast<uintptr_t>(&Alloc) | 0x1) {}
-
+
~ImutAVLFactory() {
if (ownsAllocator()) delete &getAllocator();
}
-
+
TreeTy* Add(TreeTy* T, value_type_ref V) {
T = Add_internal(V,T);
MarkImmutable(T);
return T;
}
-
+
TreeTy* Remove(TreeTy* T, key_type_ref V) {
T = Remove_internal(V,T);
MarkImmutable(T);
return T;
}
-
+
TreeTy* GetEmptyTree() const { return NULL; }
-
- //===--------------------------------------------------===//
+
+ //===--------------------------------------------------===//
// A bunch of quick helper functions used for reasoning
// about the properties of trees and their children.
// These have succinct names so that the balancing code
// is as terse (and readable) as possible.
//===--------------------------------------------------===//
private:
-
+
bool isEmpty(TreeTy* T) const { return !T; }
- unsigned Height(TreeTy* T) const { return T ? T->getHeight() : 0; }
+ unsigned Height(TreeTy* T) const { return T ? T->getHeight() : 0; }
TreeTy* Left(TreeTy* T) const { return T->getSafeLeft(); }
- TreeTy* Right(TreeTy* T) const { return T->getRight(); }
+ TreeTy* Right(TreeTy* T) const { return T->getRight(); }
value_type_ref Value(TreeTy* T) const { return T->Value; }
-
+
unsigned IncrementHeight(TreeTy* L, TreeTy* R) const {
unsigned hl = Height(L);
unsigned hr = Height(R);
return ( hl > hr ? hl : hr ) + 1;
}
-
-
+
+
static bool CompareTreeWithSection(TreeTy* T,
typename TreeTy::iterator& TI,
typename TreeTy::iterator& TE) {
-
+
typename TreeTy::iterator I = T->begin(), E = T->end();
-
+
for ( ; I!=E ; ++I, ++TI)
if (TI == TE || !I->ElementEqual(*TI))
return false;
return true;
- }
-
- //===--------------------------------------------------===//
+ }
+
+ //===--------------------------------------------------===//
// "CreateNode" is used to generate new tree roots that link
// to other trees. The functon may also simply move links
// in an existing root if that root is still marked mutable.
// then discarded later before the finished tree is
// returned to the caller.
//===--------------------------------------------------===//
-
+
TreeTy* CreateNode(TreeTy* L, value_type_ref V, TreeTy* R) {
// Search the FoldingSet bucket for a Tree with the same digest.
FoldingSetNodeID ID;
unsigned digest = TreeTy::ComputeDigest(L, R, V);
ID.AddInteger(digest);
unsigned hash = ID.ComputeHash();
-
+
typename CacheTy::bucket_iterator I = Cache.bucket_begin(hash);
typename CacheTy::bucket_iterator E = Cache.bucket_end(hash);
-
+
for (; I != E; ++I) {
TreeTy* T = &*I;
if (T->ComputeDigest() != digest)
continue;
-
+
// We found a collision. Perform a comparison of Contents('T')
// with Contents('L')+'V'+Contents('R').
-
+
typename TreeTy::iterator TI = T->begin(), TE = T->end();
-
+
// First compare Contents('L') with the (initial) contents of T.
if (!CompareTreeWithSection(L, TI, TE))
continue;
-
+
// Now compare the new data element.
if (TI == TE || !TI->ElementEqual(V))
continue;
-
+
++TI;
// Now compare the remainder of 'T' with 'R'.
if (!CompareTreeWithSection(R, TI, TE))
continue;
-
+
if (TI != TE) // Contents('R') did not match suffix of 'T'.
continue;
-
+
// Trees did match! Return 'T'.
return T;
}
-
+
// No tree with the contents: Contents('L')+'V'+Contents('R').
// Create it.
return T;
}
-
- TreeTy* CreateNode(TreeTy* L, TreeTy* OldTree, TreeTy* R) {
+
+ TreeTy* CreateNode(TreeTy* L, TreeTy* OldTree, TreeTy* R) {
assert (!isEmpty(OldTree));
-
+
if (OldTree->isMutable()) {
OldTree->setLeft(L);
OldTree->setRight(R);
}
else return CreateNode(L, Value(OldTree), R);
}
-
+
/// Balance - Used by Add_internal and Remove_internal to
/// balance a newly created tree.
TreeTy* Balance(TreeTy* L, value_type_ref V, TreeTy* R) {
-
+
unsigned hl = Height(L);
unsigned hr = Height(R);
-
+
if (hl > hr + 2) {
assert (!isEmpty(L) &&
"Left tree cannot be empty to have a height >= 2.");
-
+
TreeTy* LL = Left(L);
TreeTy* LR = Right(L);
-
+
if (Height(LL) >= Height(LR))
return CreateNode(LL, L, CreateNode(LR,V,R));
-
+
assert (!isEmpty(LR) &&
"LR cannot be empty because it has a height >= 1.");
-
+
TreeTy* LRL = Left(LR);
TreeTy* LRR = Right(LR);
-
- return CreateNode(CreateNode(LL,L,LRL), LR, CreateNode(LRR,V,R));
+
+ return CreateNode(CreateNode(LL,L,LRL), LR, CreateNode(LRR,V,R));
}
else if (hr > hl + 2) {
assert (!isEmpty(R) &&
"Right tree cannot be empty to have a height >= 2.");
-
+
TreeTy* RL = Left(R);
TreeTy* RR = Right(R);
-
+
if (Height(RR) >= Height(RL))
return CreateNode(CreateNode(L,V,RL), R, RR);
-
+
assert (!isEmpty(RL) &&
"RL cannot be empty because it has a height >= 1.");
-
+
TreeTy* RLL = Left(RL);
TreeTy* RLR = Right(RL);
-
+
return CreateNode(CreateNode(L,V,RLL), RL, CreateNode(RLR,R,RR));
}
else
return CreateNode(L,V,R);
}
-
+
/// Add_internal - Creates a new tree that includes the specified
/// data and the data from the original tree. If the original tree
/// already contained the data item, the original tree is returned.
TreeTy* Add_internal(value_type_ref V, TreeTy* T) {
if (isEmpty(T))
return CreateNode(T, V, T);
-
+
assert (!T->isMutable());
-
+
key_type_ref K = ImutInfo::KeyOfValue(V);
key_type_ref KCurrent = ImutInfo::KeyOfValue(Value(T));
-
+
if (ImutInfo::isEqual(K,KCurrent))
return CreateNode(Left(T), V, Right(T));
else if (ImutInfo::isLess(K,KCurrent))
else
return Balance(Left(T), Value(T), Add_internal(V,Right(T)));
}
-
+
/// Remove_internal - Creates a new tree that includes all the data
/// from the original tree except the specified data. If the
/// specified data did not exist in the original tree, the original
TreeTy* Remove_internal(key_type_ref K, TreeTy* T) {
if (isEmpty(T))
return T;
-
+
assert (!T->isMutable());
-
+
key_type_ref KCurrent = ImutInfo::KeyOfValue(Value(T));
-
+
if (ImutInfo::isEqual(K,KCurrent))
return CombineLeftRightTrees(Left(T),Right(T));
else if (ImutInfo::isLess(K,KCurrent))
else
return Balance(Left(T), Value(T), Remove_internal(K,Right(T)));
}
-
+
TreeTy* CombineLeftRightTrees(TreeTy* L, TreeTy* R) {
- if (isEmpty(L)) return R;
+ if (isEmpty(L)) return R;
if (isEmpty(R)) return L;
-
- TreeTy* OldNode;
+
+ TreeTy* OldNode;
TreeTy* NewRight = RemoveMinBinding(R,OldNode);
return Balance(L,Value(OldNode),NewRight);
}
-
+
TreeTy* RemoveMinBinding(TreeTy* T, TreeTy*& NodeRemoved) {
assert (!isEmpty(T));
-
+
if (isEmpty(Left(T))) {
NodeRemoved = T;
return Right(T);
}
-
+
return Balance(RemoveMinBinding(Left(T),NodeRemoved),Value(T),Right(T));
- }
-
+ }
+
/// MarkImmutable - Clears the mutable bits of a root and all of its
/// descendants.
void MarkImmutable(TreeTy* T) {
if (!T || !T->isMutable())
return;
-
+
T->MarkImmutable();
MarkImmutable(Left(T));
MarkImmutable(Right(T));
-
+
// Now that the node is immutable it can safely be inserted
// into the node cache.
llvm::FoldingSetNodeID ID;
Cache.InsertNode(T, (void*) &*Cache.bucket_end(ID.ComputeHash()));
}
};
-
-
-//===----------------------------------------------------------------------===//
+
+
+//===----------------------------------------------------------------------===//
// Immutable AVL-Tree Iterators.
-//===----------------------------------------------------------------------===//
+//===----------------------------------------------------------------------===//
template <typename ImutInfo>
class ImutAVLTreeGenericIterator {
SmallVector<uintptr_t,20> stack;
public:
- enum VisitFlag { VisitedNone=0x0, VisitedLeft=0x1, VisitedRight=0x3,
+ enum VisitFlag { VisitedNone=0x0, VisitedLeft=0x1, VisitedRight=0x3,
Flags=0x3 };
-
- typedef ImutAVLTree<ImutInfo> TreeTy;
+
+ typedef ImutAVLTree<ImutInfo> TreeTy;
typedef ImutAVLTreeGenericIterator<ImutInfo> _Self;
inline ImutAVLTreeGenericIterator() {}
inline ImutAVLTreeGenericIterator(const TreeTy* Root) {
if (Root) stack.push_back(reinterpret_cast<uintptr_t>(Root));
- }
-
+ }
+
TreeTy* operator*() const {
- assert (!stack.empty());
+ assert (!stack.empty());
return reinterpret_cast<TreeTy*>(stack.back() & ~Flags);
}
-
+
uintptr_t getVisitState() {
assert (!stack.empty());
return stack.back() & Flags;
}
-
-
+
+
bool AtEnd() const { return stack.empty(); }
- bool AtBeginning() const {
+ bool AtBeginning() const {
return stack.size() == 1 && getVisitState() == VisitedNone;
}
-
+
void SkipToParent() {
assert (!stack.empty());
stack.pop_back();
-
+
if (stack.empty())
return;
-
+
switch (getVisitState()) {
case VisitedNone:
stack.back() |= VisitedLeft;
stack.back() |= VisitedRight;
break;
default:
- assert (false && "Unreachable.");
+ assert (false && "Unreachable.");
}
}
-
+
inline bool operator==(const _Self& x) const {
if (stack.size() != x.stack.size())
return false;
-
+
for (unsigned i = 0 ; i < stack.size(); i++)
if (stack[i] != x.stack[i])
return false;
-
+
return true;
}
-
- inline bool operator!=(const _Self& x) const { return !operator==(x); }
-
+
+ inline bool operator!=(const _Self& x) const { return !operator==(x); }
+
_Self& operator++() {
assert (!stack.empty());
-
+
TreeTy* Current = reinterpret_cast<TreeTy*>(stack.back() & ~Flags);
assert (Current);
-
+
switch (getVisitState()) {
case VisitedNone:
if (TreeTy* L = Current->getSafeLeft())
stack.push_back(reinterpret_cast<uintptr_t>(L));
else
stack.back() |= VisitedLeft;
-
+
break;
-
+
case VisitedLeft:
if (TreeTy* R = Current->getRight())
stack.push_back(reinterpret_cast<uintptr_t>(R));
else
stack.back() |= VisitedRight;
-
+
break;
-
+
case VisitedRight:
- SkipToParent();
+ SkipToParent();
break;
-
+
default:
assert (false && "Unreachable.");
}
-
+
return *this;
}
-
+
_Self& operator--() {
assert (!stack.empty());
-
+
TreeTy* Current = reinterpret_cast<TreeTy*>(stack.back() & ~Flags);
assert (Current);
-
+
switch (getVisitState()) {
case VisitedNone:
stack.pop_back();
break;
-
- case VisitedLeft:
+
+ case VisitedLeft:
stack.back() &= ~Flags; // Set state to "VisitedNone."
-
+
if (TreeTy* L = Current->getLeft())
stack.push_back(reinterpret_cast<uintptr_t>(L) | VisitedRight);
-
+
break;
-
- case VisitedRight:
+
+ case VisitedRight:
stack.back() &= ~Flags;
stack.back() |= VisitedLeft;
-
+
if (TreeTy* R = Current->getRight())
stack.push_back(reinterpret_cast<uintptr_t>(R) | VisitedRight);
-
+
break;
-
+
default:
assert (false && "Unreachable.");
}
-
+
return *this;
}
};
-
+
template <typename ImutInfo>
class ImutAVLTreeInOrderIterator {
typedef ImutAVLTreeGenericIterator<ImutInfo> InternalIteratorTy;
typedef ImutAVLTree<ImutInfo> TreeTy;
typedef ImutAVLTreeInOrderIterator<ImutInfo> _Self;
- ImutAVLTreeInOrderIterator(const TreeTy* Root) : InternalItr(Root) {
+ ImutAVLTreeInOrderIterator(const TreeTy* Root) : InternalItr(Root) {
if (Root) operator++(); // Advance to first element.
}
-
+
ImutAVLTreeInOrderIterator() : InternalItr() {}
inline bool operator==(const _Self& x) const {
return InternalItr == x.InternalItr;
}
-
- inline bool operator!=(const _Self& x) const { return !operator==(x); }
-
+
+ inline bool operator!=(const _Self& x) const { return !operator==(x); }
+
inline TreeTy* operator*() const { return *InternalItr; }
inline TreeTy* operator->() const { return *InternalItr; }
-
- inline _Self& operator++() {
+
+ inline _Self& operator++() {
do ++InternalItr;
- while (!InternalItr.AtEnd() &&
+ while (!InternalItr.AtEnd() &&
InternalItr.getVisitState() != InternalIteratorTy::VisitedLeft);
return *this;
}
-
- inline _Self& operator--() {
+
+ inline _Self& operator--() {
do --InternalItr;
- while (!InternalItr.AtBeginning() &&
+ while (!InternalItr.AtBeginning() &&
InternalItr.getVisitState() != InternalIteratorTy::VisitedLeft);
-
+
return *this;
}
-
+
inline void SkipSubTree() {
InternalItr.SkipToParent();
-
+
while (!InternalItr.AtEnd() &&
InternalItr.getVisitState() != InternalIteratorTy::VisitedLeft)
- ++InternalItr;
+ ++InternalItr;
}
};
-
-//===----------------------------------------------------------------------===//
+
+//===----------------------------------------------------------------------===//
// Trait classes for Profile information.
//===----------------------------------------------------------------------===//
struct ImutProfileInfo {
typedef const T value_type;
typedef const T& value_type_ref;
-
+
static inline void Profile(FoldingSetNodeID& ID, value_type_ref X) {
FoldingSetTrait<T>::Profile(X,ID);
}
/// Profile traits for integers.
template <typename T>
-struct ImutProfileInteger {
+struct ImutProfileInteger {
typedef const T value_type;
typedef const T& value_type_ref;
-
+
static inline void Profile(FoldingSetNodeID& ID, value_type_ref X) {
ID.AddInteger(X);
- }
+ }
};
#define PROFILE_INTEGER_INFO(X)\
struct ImutProfileInfo<T*> {
typedef const T* value_type;
typedef value_type value_type_ref;
-
+
static inline void Profile(FoldingSetNodeID &ID, value_type_ref X) {
ID.AddPointer(X);
}
};
-//===----------------------------------------------------------------------===//
+//===----------------------------------------------------------------------===//
// Trait classes that contain element comparison operators and type
// definitions used by ImutAVLTree, ImmutableSet, and ImmutableMap. These
// inherit from the profile traits (ImutProfileInfo) to include operations
typedef value_type_ref key_type_ref;
typedef bool data_type;
typedef bool data_type_ref;
-
+
static inline key_type_ref KeyOfValue(value_type_ref D) { return D; }
static inline data_type_ref DataOfValue(value_type_ref) { return true; }
-
- static inline bool isEqual(key_type_ref LHS, key_type_ref RHS) {
+
+ static inline bool isEqual(key_type_ref LHS, key_type_ref RHS) {
return std::equal_to<key_type>()(LHS,RHS);
}
-
+
static inline bool isLess(key_type_ref LHS, key_type_ref RHS) {
return std::less<key_type>()(LHS,RHS);
}
-
+
static inline bool isDataEqual(data_type_ref,data_type_ref) { return true; }
};
typedef value_type_ref key_type_ref;
typedef bool data_type;
typedef bool data_type_ref;
-
+
static inline key_type_ref KeyOfValue(value_type_ref D) { return D; }
static inline data_type_ref DataOfValue(value_type_ref) { return true; }
-
+
static inline bool isEqual(key_type_ref LHS, key_type_ref RHS) {
return LHS == RHS;
}
-
+
static inline bool isLess(key_type_ref LHS, key_type_ref RHS) {
return LHS < RHS;
}
-
+
static inline bool isDataEqual(data_type_ref,data_type_ref) { return true; }
};
-//===----------------------------------------------------------------------===//
+//===----------------------------------------------------------------------===//
// Immutable Set
//===----------------------------------------------------------------------===//
typedef typename ValInfo::value_type_ref value_type_ref;
typedef ImutAVLTree<ValInfo> TreeTy;
-private:
+private:
TreeTy* Root;
public:
/// invoking the constructor, but there are cases where make this
/// constructor public is useful.
explicit ImmutableSet(TreeTy* R) : Root(R) {}
-
+
class Factory {
typename TreeTy::Factory F;
-
+
public:
Factory() {}
-
+
Factory(BumpPtrAllocator& Alloc)
: F(Alloc) {}
-
+
/// GetEmptySet - Returns an immutable set that contains no elements.
ImmutableSet GetEmptySet() { return ImmutableSet(F.GetEmptyTree()); }
-
+
/// Add - Creates a new immutable set that contains all of the values
/// of the original set with the addition of the specified value. If
/// the original set already included the value, then the original set is
ImmutableSet Add(ImmutableSet Old, value_type_ref V) {
return ImmutableSet(F.Add(Old.Root,V));
}
-
+
/// Remove - Creates a new immutable set that contains all of the values
/// of the original set with the exception of the specified value. If
/// the original set did not contain the value, the original set is
ImmutableSet Remove(ImmutableSet Old, value_type_ref V) {
return ImmutableSet(F.Remove(Old.Root,V));
}
-
+
BumpPtrAllocator& getAllocator() { return F.getAllocator(); }
private:
Factory(const Factory& RHS) {};
- void operator=(const Factory& RHS) {};
+ void operator=(const Factory& RHS) {};
};
-
- friend class Factory;
+
+ friend class Factory;
/// contains - Returns true if the set contains the specified value.
bool contains(const value_type_ref V) const {
return Root ? Root->contains(V) : false;
}
-
+
bool operator==(ImmutableSet RHS) const {
return Root && RHS.Root ? Root->isEqual(*RHS.Root) : Root == RHS.Root;
}
-
+
bool operator!=(ImmutableSet RHS) const {
return Root && RHS.Root ? Root->isNotEqual(*RHS.Root) : Root != RHS.Root;
}
-
+
TreeTy* getRoot() const { return Root; }
-
+
/// isEmpty - Return true if the set contains no elements.
bool isEmpty() const { return !Root; }
-
+
template <typename Callback>
void foreach(Callback& C) { if (Root) Root->foreach(C); }
-
+
template <typename Callback>
void foreach() { if (Root) { Callback C; Root->foreach(C); } }
-
- //===--------------------------------------------------===//
+
+ //===--------------------------------------------------===//
// Iterators.
- //===--------------------------------------------------===//
+ //===--------------------------------------------------===//
class iterator {
typename TreeTy::iterator itr;
-
+
iterator() {}
iterator(TreeTy* t) : itr(t) {}
friend class ImmutableSet<ValT,ValInfo>;
inline iterator& operator--() { --itr; return *this; }
inline iterator operator--(int) { iterator tmp(*this); --itr; return tmp; }
inline bool operator==(const iterator& RHS) const { return RHS.itr == itr; }
- inline bool operator!=(const iterator& RHS) const { return RHS.itr != itr; }
+ inline bool operator!=(const iterator& RHS) const { return RHS.itr != itr; }
};
-
+
iterator begin() const { return iterator(Root); }
- iterator end() const { return iterator(); }
-
- //===--------------------------------------------------===//
+ iterator end() const { return iterator(); }
+
+ //===--------------------------------------------------===//
// Utility methods.
- //===--------------------------------------------------===//
-
+ //===--------------------------------------------------===//
+
inline unsigned getHeight() const { return Root ? Root->getHeight() : 0; }
-
+
static inline void Profile(FoldingSetNodeID& ID, const ImmutableSet& S) {
ID.AddPointer(S.Root);
}
-
+
inline void Profile(FoldingSetNodeID& ID) const {
return Profile(ID,*this);
}
-
- //===--------------------------------------------------===//
+
+ //===--------------------------------------------------===//
// For testing.
- //===--------------------------------------------------===//
-
+ //===--------------------------------------------------===//
+
void verify() const { if (Root) Root->verify(); }
};
/// guarantees deletion of the object pointed to, either on destruction of the
/// OwningPtr or via an explicit reset(). Once created, ownership of the
/// pointee object can be taken away from OwningPtr by using the take method.
-template<class T>
+template<class T>
class OwningPtr {
OwningPtr(OwningPtr const &); // DO NOT IMPLEMENT
OwningPtr &operator=(OwningPtr const &); // DO NOT IMPLEMENT
/// reset - Change the current pointee to the specified pointer. Note that
/// calling this with any pointer (including a null pointer) deletes the
/// current pointer.
- void reset(T *P = 0) {
+ void reset(T *P = 0) {
if (P == Ptr) return;
T *Tmp = Ptr;
Ptr = P;
/// take - Reset the owning pointer to null and return its pointer. This does
/// not delete the pointer before returning it.
- T *take() {
+ T *take() {
T *Tmp = Ptr;
Ptr = 0;
return Tmp;
}
-
+
T &operator*() const {
assert(Ptr && "Cannot dereference null pointer");
return *Ptr;
/// OwningArrayPtr smart pointer - OwningArrayPtr provides the same
/// functionality as OwningPtr, except that it works for array types.
-template<class T>
+template<class T>
class OwningArrayPtr {
OwningArrayPtr(OwningArrayPtr const &); // DO NOT IMPLEMENT
OwningArrayPtr &operator=(OwningArrayPtr const &); // DO NOT IMPLEMENT
/// reset - Change the current pointee to the specified pointer. Note that
/// calling this with any pointer (including a null pointer) deletes the
/// current pointer.
- void reset(T *P = 0) {
+ void reset(T *P = 0) {
if (P == Ptr) return;
T *Tmp = Ptr;
Ptr = P;
/// take - Reset the owning pointer to null and return its pointer. This does
/// not delete the pointer before returning it.
- T *take() {
+ T *take() {
T *Tmp = Ptr;
Ptr = 0;
return Tmp;
}
-
+
T &operator[](std::ptrdiff_t i) const {
assert(Ptr && "Cannot dereference null pointer");
return Ptr[i];
}
-
+
T *get() const { return Ptr; }
operator bool() const { return Ptr != 0; }
bool operator!() const { return Ptr == 0; }
#include <cassert>
namespace llvm {
-
+
template<typename T>
struct DenseMapInfo;
-
+
/// PointerIntPair - This class implements a pair of a pointer and small
/// integer. It is designed to represent this in the space required by one
/// pointer by bitmangling the integer into the low part of the pointer. This
PointerTy getPointer() const {
return reinterpret_cast<PointerTy>(Value & ~((1 << IntBits)-1));
}
-
+
IntType getInt() const {
return (IntType)(Value & ((1 << IntBits)-1));
}
-
+
void setPointer(PointerTy Ptr) {
intptr_t PtrVal = reinterpret_cast<intptr_t>(Ptr);
assert((PtrVal & ((1 << IntBits)-1)) == 0 &&
"Pointer is not sufficiently aligned");
Value = PtrVal | (intptr_t)getInt();
}
-
+
void setInt(IntType Int) {
intptr_t IntVal = Int;
assert(IntVal < (1 << IntBits) && "Integer too large for field");
Value = reinterpret_cast<intptr_t>(getPointer()) | IntVal;
}
-
+
void *getOpaqueValue() const { return reinterpret_cast<void*>(Value); }
void setFromOpaqueValue(void *Val) { Value = reinterpret_cast<intptr_t>(Val);}
-
+
bool operator==(const PointerIntPair &RHS) const {return Value == RHS.Value;}
bool operator!=(const PointerIntPair &RHS) const {return Value != RHS.Value;}
bool operator<(const PointerIntPair &RHS) const {return Value < RHS.Value;}
namespace llvm {
-template<class SetType, bool External> // Non-external set
-class po_iterator_storage {
-public:
- SetType Visited;
-};
-
-template<class SetType>
-class po_iterator_storage<SetType, true> {
-public:
- po_iterator_storage(SetType &VSet) : Visited(VSet) {}
- po_iterator_storage(const po_iterator_storage &S) : Visited(S.Visited) {}
- SetType &Visited;
-};
-
-template<class GraphT,
- class SetType = std::set<typename GraphTraits<GraphT>::NodeType*>,
- bool ExtStorage = false,
- class GT = GraphTraits<GraphT> >
-class po_iterator : public forward_iterator<typename GT::NodeType, ptrdiff_t>,
- public po_iterator_storage<SetType, ExtStorage> {
+template<class SetType, bool External> // Non-external set
+class po_iterator_storage {
+public:
+ SetType Visited;
+};
+
+template<class SetType>
+class po_iterator_storage<SetType, true> {
+public:
+ po_iterator_storage(SetType &VSet) : Visited(VSet) {}
+ po_iterator_storage(const po_iterator_storage &S) : Visited(S.Visited) {}
+ SetType &Visited;
+};
+
+template<class GraphT,
+ class SetType = std::set<typename GraphTraits<GraphT>::NodeType*>,
+ bool ExtStorage = false,
+ class GT = GraphTraits<GraphT> >
+class po_iterator : public forward_iterator<typename GT::NodeType, ptrdiff_t>,
+ public po_iterator_storage<SetType, ExtStorage> {
typedef forward_iterator<typename GT::NodeType, ptrdiff_t> super;
typedef typename GT::NodeType NodeType;
typedef typename GT::ChildIteratorType ChildItTy;
-
+
// VisitStack - Used to maintain the ordering. Top = current block
// First element is basic block pointer, second is the 'next child' to visit
std::stack<std::pair<NodeType *, ChildItTy> > VisitStack;
VisitStack.push(std::make_pair(BB, GT::child_begin(BB)));
traverseChild();
}
- inline po_iterator() {} // End is when stack is empty.
-
- inline po_iterator(NodeType *BB, SetType &S) :
- po_iterator_storage<SetType, ExtStorage>(&S) {
- if(!S.count(BB)) {
- this->Visited.insert(BB);
- VisitStack.push(std::make_pair(BB, GT::child_begin(BB)));
- traverseChild();
- }
- }
-
- inline po_iterator(SetType &S) :
+ inline po_iterator() {} // End is when stack is empty.
+
+ inline po_iterator(NodeType *BB, SetType &S) :
+ po_iterator_storage<SetType, ExtStorage>(&S) {
+ if(!S.count(BB)) {
+ this->Visited.insert(BB);
+ VisitStack.push(std::make_pair(BB, GT::child_begin(BB)));
+ traverseChild();
+ }
+ }
+
+ inline po_iterator(SetType &S) :
po_iterator_storage<SetType, ExtStorage>(&S) {
- } // End is when stack is empty.
+ } // End is when stack is empty.
public:
typedef typename super::pointer pointer;
- typedef po_iterator<GraphT, SetType, ExtStorage, GT> _Self;
+ typedef po_iterator<GraphT, SetType, ExtStorage, GT> _Self;
// Provide static "constructors"...
static inline _Self begin(GraphT G) { return _Self(GT::getEntryNode(G)); }
static inline _Self end (GraphT G) { return _Self(); }
- static inline _Self begin(GraphT G, SetType &S) {
- return _Self(GT::getEntryNode(G), S);
- }
- static inline _Self end (GraphT G, SetType &S) { return _Self(S); }
-
+ static inline _Self begin(GraphT G, SetType &S) {
+ return _Self(GT::getEntryNode(G), S);
+ }
+ static inline _Self end (GraphT G, SetType &S) { return _Self(S); }
+
inline bool operator==(const _Self& x) const {
return VisitStack == x.VisitStack;
}
template <class T>
po_iterator<T> po_end (T G) { return po_iterator<T>::end(G); }
-// Provide global definitions of external postorder iterators...
-template<class T, class SetType=std::set<typename GraphTraits<T>::NodeType*> >
-struct po_ext_iterator : public po_iterator<T, SetType, true> {
- po_ext_iterator(const po_iterator<T, SetType, true> &V) :
- po_iterator<T, SetType, true>(V) {}
-};
-
-template<class T, class SetType>
-po_ext_iterator<T, SetType> po_ext_begin(T G, SetType &S) {
- return po_ext_iterator<T, SetType>::begin(G, S);
-}
-
-template<class T, class SetType>
-po_ext_iterator<T, SetType> po_ext_end(T G, SetType &S) {
- return po_ext_iterator<T, SetType>::end(G, S);
-}
+// Provide global definitions of external postorder iterators...
+template<class T, class SetType=std::set<typename GraphTraits<T>::NodeType*> >
+struct po_ext_iterator : public po_iterator<T, SetType, true> {
+ po_ext_iterator(const po_iterator<T, SetType, true> &V) :
+ po_iterator<T, SetType, true>(V) {}
+};
+
+template<class T, class SetType>
+po_ext_iterator<T, SetType> po_ext_begin(T G, SetType &S) {
+ return po_ext_iterator<T, SetType>::begin(G, S);
+}
+
+template<class T, class SetType>
+po_ext_iterator<T, SetType> po_ext_end(T G, SetType &S) {
+ return po_ext_iterator<T, SetType>::end(G, S);
+}
// Provide global definitions of inverse post order iterators...
-template <class T,
- class SetType = std::set<typename GraphTraits<T>::NodeType*>,
- bool External = false>
-struct ipo_iterator : public po_iterator<Inverse<T>, SetType, External > {
- ipo_iterator(const po_iterator<Inverse<T>, SetType, External> &V) :
- po_iterator<Inverse<T>, SetType, External> (V) {}
+template <class T,
+ class SetType = std::set<typename GraphTraits<T>::NodeType*>,
+ bool External = false>
+struct ipo_iterator : public po_iterator<Inverse<T>, SetType, External > {
+ ipo_iterator(const po_iterator<Inverse<T>, SetType, External> &V) :
+ po_iterator<Inverse<T>, SetType, External> (V) {}
};
template <class T>
return ipo_iterator<T>::end(G);
}
-//Provide global definitions of external inverse postorder iterators...
-template <class T, class SetType = std::set<typename GraphTraits<T>::NodeType*> >
-struct ipo_ext_iterator : public ipo_iterator<T, SetType, true> {
- ipo_ext_iterator(const ipo_iterator<T, SetType, true> &V) :
- ipo_iterator<T, SetType, true>(&V) {}
- ipo_ext_iterator(const po_iterator<Inverse<T>, SetType, true> &V) :
- ipo_iterator<T, SetType, true>(&V) {}
-};
-
-template <class T, class SetType>
-ipo_ext_iterator<T, SetType> ipo_ext_begin(T G, SetType &S) {
- return ipo_ext_iterator<T, SetType>::begin(G, S);
-}
-
-template <class T, class SetType>
-ipo_ext_iterator<T, SetType> ipo_ext_end(T G, SetType &S) {
- return ipo_ext_iterator<T, SetType>::end(G, S);
-}
+//Provide global definitions of external inverse postorder iterators...
+template <class T, class SetType = std::set<typename GraphTraits<T>::NodeType*> >
+struct ipo_ext_iterator : public ipo_iterator<T, SetType, true> {
+ ipo_ext_iterator(const ipo_iterator<T, SetType, true> &V) :
+ ipo_iterator<T, SetType, true>(&V) {}
+ ipo_ext_iterator(const po_iterator<Inverse<T>, SetType, true> &V) :
+ ipo_iterator<T, SetType, true>(&V) {}
+};
+
+template <class T, class SetType>
+ipo_ext_iterator<T, SetType> ipo_ext_begin(T G, SetType &S) {
+ return ipo_ext_iterator<T, SetType>::begin(G, S);
+}
+
+template <class T, class SetType>
+ipo_ext_iterator<T, SetType> ipo_ext_end(T G, SetType &S) {
+ return ipo_ext_iterator<T, SetType>::end(G, S);
+}
//===--------------------------------------------------------------------===//
// Reverse Post Order CFG iterator code
/// PriorityQueue - This class behaves like std::priority_queue and
/// provides a few additional convenience functions.
-///
+///
template<class T,
class Sequence = std::vector<T>,
class Compare = std::less<typename Sequence::value_type> >
return 1;
return 0;
}
-
+
/// get_array_pad_sort_comparator - This is an internal helper function used to
/// get type deduction of T right.
template<typename T>
-static int (*get_array_pad_sort_comparator(const T &X))
+static int (*get_array_pad_sort_comparator(const T &X))
(const void*, const void*) {
return array_pod_sort_comparator<T>;
}
qsort(&*Start, End-Start, sizeof(*Start),
get_array_pad_sort_comparator(*Start));
}
-
+
} // End llvm namespace
#endif
K Key;
V Val;
public:
- ScopedHashTableVal(ScopedHashTableVal *nextInScope,
+ ScopedHashTableVal(ScopedHashTableVal *nextInScope,
ScopedHashTableVal *nextForKey, const K &key, const V &val)
: NextInScope(nextInScope), NextForKey(nextForKey), Key(key), Val(val) {
}
-
+
const K &getKey() const { return Key; }
const V &getValue() const { return Val; }
V &getValue() { return Val; }
-
+
ScopedHashTableVal *getNextForKey() { return NextForKey; }
const ScopedHashTableVal *getNextForKey() const { return NextForKey; }
public:
class ScopedHashTableScope {
/// HT - The hashtable that we are active for.
ScopedHashTable<K, V> &HT;
-
+
/// PrevScope - This is the scope that we are shadowing in HT.
ScopedHashTableScope *PrevScope;
public:
ScopedHashTableScope(ScopedHashTable<K, V> &HT);
~ScopedHashTableScope();
-
+
private:
friend class ScopedHashTable<K, V>;
ScopedHashTableVal<K, V> *getLastValInScope() { return LastValInScope; }
ScopedHashTableVal<K,V> *Node;
public:
ScopedHashTableIterator(ScopedHashTableVal<K,V> *node) : Node(node){}
-
+
V &operator*() const {
assert(Node && "Dereference end()");
return Node->getValue();
V *operator->() const {
return &Node->getValue();
}
-
+
bool operator==(const ScopedHashTableIterator &RHS) const {
return Node == RHS.Node;
}
bool operator!=(const ScopedHashTableIterator &RHS) const {
return Node != RHS.Node;
}
-
+
inline ScopedHashTableIterator& operator++() { // Preincrement
assert(Node && "incrementing past end()");
Node = Node->getNextForKey();
~ScopedHashTable() {
assert(CurScope == 0 && TopLevelMap.empty() && "Scope imbalance!");
}
-
+
void insert(const K &Key, const V &Val) {
assert(CurScope && "No scope active!");
-
+
ScopedHashTableVal<K,V> *&KeyEntry = TopLevelMap[Key];
-
+
KeyEntry = new ScopedHashTableVal<K,V>(CurScope->getLastValInScope(),
KeyEntry, Key, Val);
CurScope->setLastValInScope(KeyEntry);
}
-
+
typedef ScopedHashTableIterator<K, V> iterator;
iterator end() { return iterator(0); }
iterator begin(const K &Key) {
- typename DenseMap<K, ScopedHashTableVal<K,V>*>::iterator I =
+ typename DenseMap<K, ScopedHashTableVal<K,V>*>::iterator I =
TopLevelMap.find(Key);
if (I == TopLevelMap.end()) return end();
return iterator(I->second);
ScopedHashTableScope<K, V>::~ScopedHashTableScope() {
assert(HT.CurScope == this && "Scope imbalance!");
HT.CurScope = PrevScope;
-
+
// Pop and delete all values corresponding to this scope.
while (ScopedHashTableVal<K, V> *ThisEntry = LastValInScope) {
// Pop this value out of the TopLevelMap.
assert(HT.TopLevelMap[ThisEntry->getKey()] == ThisEntry &&
"Scope imbalance!");
HT.TopLevelMap.erase(ThisEntry->getKey());
- } else {
+ } else {
ScopedHashTableVal<K,V> *&KeyEntry = HT.TopLevelMap[ThisEntry->getKey()];
assert(KeyEntry == ThisEntry && "Scope imbalance!");
KeyEntry = ThisEntry->getNextForKey();
}
-
+
// Pop this value out of the scope.
LastValInScope = ThisEntry->getNextInScope();
-
+
// Delete this entry.
delete ThisEntry;
}
class SmallSetVector : public SetVector<T, SmallVector<T, N>, SmallSet<T, N> > {
public:
SmallSetVector() {}
-
+
/// @brief Initialize a SmallSetVector with a range of elements
template<typename It>
SmallSetVector(It Start, It End) {
/// Note that CurArray points to an array that has CurArraySize+1 elements in
/// it, so that the end iterator actually points to valid memory.
unsigned CurArraySize;
-
+
// If small, this is # elts allocated consequtively
unsigned NumElements;
unsigned NumTombstones;
clear();
}
~SmallPtrSetImpl();
-
+
bool empty() const { return size() == 0; }
unsigned size() const { return NumElements; }
-
+
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);
}
-
+
void clear() {
// If the capacity of the array is huge, and the # elements used is small,
// shrink the array.
if (!isSmall() && NumElements*4 < CurArraySize && CurArraySize > 32)
return shrink_and_clear();
-
+
// Fill the array with empty markers.
memset(CurArray, -1, CurArraySize*sizeof(void*));
NumElements = 0;
NumTombstones = 0;
}
-
+
protected:
/// 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.
bool insert_imp(const void * 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);
-
+
bool count_imp(const void * Ptr) const {
if (isSmall()) {
// Linear search for the item.
return true;
return false;
}
-
+
// Big set case.
return *FindBucketFor(Ptr) == Ptr;
}
-
+
private:
bool isSmall() const { return CurArray == &SmallArray[0]; }
}
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();
-
+
void operator=(const SmallPtrSetImpl &RHS); // DO NOT IMPLEMENT.
protected:
void CopyFrom(const SmallPtrSetImpl &RHS);
explicit SmallPtrSetIteratorImpl(const void *const *BP) : Bucket(BP) {
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
: SmallPtrSetIteratorImpl(BP) {}
// Most methods provided by baseclass.
-
+
const PtrTy operator*() const {
return static_cast<const PtrTy>(const_cast<void*>(*Bucket));
}
-
+
inline SmallPtrSetIterator& operator++() { // Preincrement
++Bucket;
AdvanceIfNotValid();
return *this;
}
-
+
SmallPtrSetIterator operator++(int) { // Postincrement
SmallPtrSetIterator tmp = *this; ++*this; return tmp;
}
public:
SmallPtrSet() : SmallPtrSetImpl(NextPowerOfTwo<SmallSizePowTwo>::Val) {}
SmallPtrSet(const SmallPtrSet &that) : SmallPtrSetImpl(that) {}
-
+
template<typename It>
SmallPtrSet(It I, It E)
: SmallPtrSetImpl(NextPowerOfTwo<SmallSizePowTwo>::Val) {
insert(I, E);
}
-
+
/// insert - This returns true if the pointer was new to the set, false if it
/// was already in the set.
bool insert(PtrType Ptr) { return insert_imp(Ptr); }
-
+
/// erase - If the set contains the specified pointer, remove it and return
/// true, otherwise return false.
bool erase(PtrType Ptr) { return erase_imp(Ptr); }
-
+
/// count - Return true if the specified pointer is in the set.
bool count(PtrType Ptr) const { return count_imp(Ptr); }
-
+
template <typename IterT>
void insert(IterT I, IterT E) {
for (; I != E; ++I)
insert(*I);
}
-
+
typedef SmallPtrSetIterator<PtrType> iterator;
typedef SmallPtrSetIterator<PtrType> const_iterator;
inline iterator begin() const {
inline iterator end() const {
return iterator(CurArray+CurArraySize);
}
-
+
// Allow assignment from any smallptrset with the same element type even if it
// doesn't have the same smallsize.
const SmallPtrSet<PtrType, SmallSize>&
unsigned size() const {
return isSmall() ? Vector.size() : Set.size();
}
-
+
/// count - Return true if the element is in the set.
bool count(const T &V) const {
if (isSmall()) {
return Set.count(V);
}
}
-
+
/// insert - Insert an element into the set if it isn't already there.
bool insert(const T &V) {
if (!isSmall())
return Set.insert(V).second;
-
+
VIterator I = vfind(V);
if (I != Vector.end()) // Don't reinsert if it already exists.
return false;
Set.insert(V);
return true;
}
-
+
bool erase(const T &V) {
if (!isSmall())
return Set.erase(V);
}
return false;
}
-
+
void clear() {
Vector.clear();
Set.clear();
}
private:
bool isSmall() const { return Set.empty(); }
-
+
VIterator vfind(const T &V) const {
for (VIterator I = Vector.begin(), E = Vector.end(); I != E; ++I)
if (*I == V)
// Initialize with a range.
template<typename ItTy>
SmallString(ItTy S, ItTy E) : SmallVector<char, InternalLen>(S, E) {}
-
+
// Copy ctor.
SmallString(const SmallString &RHS) : SmallVector<char, InternalLen>(RHS) {}
-
+
// Extra methods.
const char *c_str() const {
SmallString *This = const_cast<SmallString*>(this);
This->End[0] = 0;
return this->begin();
}
-
+
// Extra operators.
const SmallString &operator=(const char *RHS) {
this->clear();
return *this += RHS;
}
-
+
SmallString &operator+=(const char *RHS) {
this->append(RHS, RHS+strlen(RHS));
return *this;
SmallString &append_uint_32(uint32_t N) {
char Buffer[20];
char *BufPtr = Buffer+20;
-
+
if (N == 0) *--BufPtr = '0'; // Handle special case.
-
+
while (N) {
*--BufPtr = '0' + char(N % 10);
N /= 10;
this->append(BufPtr, Buffer+20);
return *this;
}
-
+
SmallString &append_uint(uint64_t N) {
if (N == uint32_t(N))
return append_uint_32(uint32_t(N));
-
+
char Buffer[40];
char *BufPtr = Buffer+40;
-
+
if (N == 0) *--BufPtr = '0'; // Handle special case...
-
+
while (N) {
*--BufPtr = '0' + char(N % 10);
N /= 10;
this->append(BufPtr, Buffer+40);
return *this;
}
-
+
SmallString &append_sint(int64_t N) {
// TODO, wrong for minint64.
if (N < 0) {
}
return append_uint(N);
}
-
+
};
-
-
+
+
}
#endif
class SmallVectorImpl {
protected:
T *Begin, *End, *Capacity;
-
+
// Allocate raw space for N elements of type T. If T has a ctor or dtor, we
// don't want it to be automatically run, so we need to represent the space as
// something else. An array of char would work great, but might not be
public:
// Default ctor - Initialize to empty.
SmallVectorImpl(unsigned N)
- : Begin(reinterpret_cast<T*>(&FirstEl)),
- End(reinterpret_cast<T*>(&FirstEl)),
+ : Begin(reinterpret_cast<T*>(&FirstEl)),
+ End(reinterpret_cast<T*>(&FirstEl)),
Capacity(reinterpret_cast<T*>(&FirstEl)+N) {
}
-
+
~SmallVectorImpl() {
// Destroy the constructed elements in the vector.
destroy_range(Begin, End);
if (!isSmall())
operator delete(Begin);
}
-
+
typedef size_t size_type;
typedef ptrdiff_t difference_type;
typedef T value_type;
typedef T* iterator;
typedef const T* const_iterator;
-
+
typedef std::reverse_iterator<const_iterator> const_reverse_iterator;
typedef std::reverse_iterator<iterator> reverse_iterator;
-
+
typedef T& reference;
typedef const T& const_reference;
typedef T* pointer;
const_iterator begin() const { return Begin; }
iterator end() { return End; }
const_iterator end() const { return End; }
-
+
// reverse iterator creation methods.
reverse_iterator rbegin() { return reverse_iterator(end()); }
const_reverse_iterator rbegin() const{ return const_reverse_iterator(end()); }
reverse_iterator rend() { return reverse_iterator(begin()); }
const_reverse_iterator rend() const { return const_reverse_iterator(begin());}
-
-
+
+
/* These asserts could be "Begin + idx < End", but there are lots of places
in llvm where we use &v[v.size()] instead of v.end(). */
reference operator[](unsigned idx) {
assert (Begin + idx <= End);
return Begin[idx];
}
-
+
reference front() {
return begin()[0];
}
const_reference front() const {
return begin()[0];
}
-
+
reference back() {
return end()[-1];
}
const_reference back() const {
return end()[-1];
}
-
+
void push_back(const_reference Elt) {
if (End < Capacity) {
Retry:
grow();
goto Retry;
}
-
+
void pop_back() {
--End;
End->~T();
}
-
+
T pop_back_val() {
T Result = back();
pop_back();
return Result;
}
-
+
void clear() {
destroy_range(Begin, End);
End = Begin;
}
-
+
void resize(unsigned N) {
if (N < size()) {
destroy_range(Begin+N, End);
End = Begin+N;
}
}
-
+
void resize(unsigned N, const T &NV) {
if (N < size()) {
destroy_range(Begin+N, End);
End = Begin+N;
}
}
-
+
void reserve(unsigned N) {
if (unsigned(Capacity-Begin) < N)
grow(N);
}
-
+
void swap(SmallVectorImpl &RHS);
-
+
/// append - Add the specified range to the end of the SmallVector.
///
template<typename in_iter>
std::uninitialized_copy(in_start, in_end, End);
End += NumInputs;
}
-
+
/// append - Add the specified range to the end of the SmallVector.
///
void append(size_type NumInputs, const T &Elt) {
std::uninitialized_fill_n(End, NumInputs, Elt);
End += NumInputs;
}
-
+
void assign(unsigned NumElts, const T &Elt) {
clear();
if (unsigned(Capacity-Begin) < NumElts)
End = Begin+NumElts;
construct_range(Begin, End, Elt);
}
-
+
iterator erase(iterator I) {
iterator N = I;
// Shift all elts down one.
pop_back();
return(N);
}
-
+
iterator erase(iterator S, iterator E) {
iterator N = S;
// Shift all elts down.
End = I;
return(N);
}
-
+
iterator insert(iterator I, const T &Elt) {
if (I == End) { // Important special case for empty vector.
push_back(Elt);
return end()-1;
}
-
+
if (End < Capacity) {
Retry:
new (End) T(back());
append(NumToInsert, Elt);
return end()-1;
}
-
+
// Convert iterator to elt# to avoid invalidating iterator when we reserve()
size_t InsertElt = I-begin();
-
+
// Ensure there is enough space.
reserve(static_cast<unsigned>(size() + NumToInsert));
-
+
// Uninvalidate the iterator.
I = begin()+InsertElt;
-
+
// If we already have this many elements in the collection, append the
// dest elements at the end, then copy over the appropriate elements. Since
// we already reserved space, we know that this won't reallocate the vector.
if (size() >= NumToInsert) {
T *OldEnd = End;
append(End-NumToInsert, End);
-
+
// Copy the existing elements that get replaced.
std::copy(I, OldEnd-NumToInsert, I+NumToInsert);
-
+
std::fill_n(I, NumToInsert, Elt);
return I;
}
// Otherwise, we're inserting more elements than exist already, and we're
// not inserting at the end.
-
+
// Copy over the elements that we're about to overwrite.
T *OldEnd = End;
End += NumToInsert;
size_t NumOverwritten = OldEnd-I;
std::uninitialized_copy(I, OldEnd, End-NumOverwritten);
-
+
// Replace the overwritten part.
std::fill_n(I, NumOverwritten, Elt);
-
+
// Insert the non-overwritten middle part.
std::uninitialized_fill_n(OldEnd, NumToInsert-NumOverwritten, Elt);
return I;
}
-
+
template<typename ItTy>
iterator insert(iterator I, ItTy From, ItTy To) {
if (I == End) { // Important special case for empty vector.
append(From, To);
return end()-1;
}
-
+
size_t NumToInsert = std::distance(From, To);
// Convert iterator to elt# to avoid invalidating iterator when we reserve()
size_t InsertElt = I-begin();
-
+
// Ensure there is enough space.
reserve(static_cast<unsigned>(size() + NumToInsert));
-
+
// Uninvalidate the iterator.
I = begin()+InsertElt;
-
+
// If we already have this many elements in the collection, append the
// dest elements at the end, then copy over the appropriate elements. Since
// we already reserved space, we know that this won't reallocate the vector.
if (size() >= NumToInsert) {
T *OldEnd = End;
append(End-NumToInsert, End);
-
+
// Copy the existing elements that get replaced.
std::copy(I, OldEnd-NumToInsert, I+NumToInsert);
-
+
std::copy(From, To, I);
return I;
}
// Otherwise, we're inserting more elements than exist already, and we're
// not inserting at the end.
-
+
// Copy over the elements that we're about to overwrite.
T *OldEnd = End;
End += NumToInsert;
size_t NumOverwritten = OldEnd-I;
std::uninitialized_copy(I, OldEnd, End-NumOverwritten);
-
+
// Replace the overwritten part.
std::copy(From, From+NumOverwritten, I);
-
+
// Insert the non-overwritten middle part.
std::uninitialized_copy(From+NumOverwritten, To, OldEnd);
return I;
}
-
+
const SmallVectorImpl &operator=(const SmallVectorImpl &RHS);
-
+
bool operator==(const SmallVectorImpl &RHS) const {
if (size() != RHS.size()) return false;
- for (T *This = Begin, *That = RHS.Begin, *E = Begin+size();
+ for (T *This = Begin, *That = RHS.Begin, *E = Begin+size();
This != E; ++This, ++That)
if (*This != *That)
return false;
return std::lexicographical_compare(begin(), end(),
RHS.begin(), RHS.end());
}
-
+
private:
/// isSmall - Return true if this is a smallvector which has not had dynamic
/// memory allocated for it.
bool isSmall() const {
- return static_cast<const void*>(Begin) ==
+ return static_cast<const void*>(Begin) ==
static_cast<const void*>(&FirstEl);
}
for (; S != E; ++S)
new (S) T(Elt);
}
-
+
void destroy_range(T *S, T *E) {
while (S != E) {
--E;
if (NewCapacity < MinSize)
NewCapacity = MinSize;
T *NewElts = static_cast<T*>(operator new(NewCapacity*sizeof(T)));
-
+
// Copy the elements over.
if (is_class<T>::value)
std::uninitialized_copy(Begin, End, NewElts);
else
// Use memcpy for PODs (std::uninitialized_copy optimizes to memmove).
memcpy(NewElts, Begin, CurSize * sizeof(T));
-
+
// Destroy the original elements.
destroy_range(Begin, End);
-
+
// If this wasn't grown from the inline copy, deallocate the old space.
if (!isSmall())
operator delete(Begin);
-
+
Begin = NewElts;
End = NewElts+CurSize;
Capacity = Begin+NewCapacity;
template <typename T>
void SmallVectorImpl<T>::swap(SmallVectorImpl<T> &RHS) {
if (this == &RHS) return;
-
+
// We can only avoid copying elements if neither vector is small.
if (!isSmall() && !RHS.isSmall()) {
std::swap(Begin, RHS.Begin);
grow(RHS.size());
if (RHS.begin()+size() > RHS.Capacity)
RHS.grow(size());
-
+
// Swap the shared elements.
size_t NumShared = size();
if (NumShared > RHS.size()) NumShared = RHS.size();
for (unsigned i = 0; i != static_cast<unsigned>(NumShared); ++i)
std::swap(Begin[i], RHS[i]);
-
+
// Copy over the extra elts.
if (size() > RHS.size()) {
size_t EltDiff = size() - RHS.size();
RHS.End = RHS.Begin+NumShared;
}
}
-
+
template <typename T>
const SmallVectorImpl<T> &
SmallVectorImpl<T>::operator=(const SmallVectorImpl<T> &RHS) {
// Avoid self-assignment.
if (this == &RHS) return *this;
-
+
// If we already have sufficient space, assign the common elements, then
// destroy any excess.
unsigned RHSSize = unsigned(RHS.size());
NewEnd = std::copy(RHS.Begin, RHS.Begin+RHSSize, Begin);
else
NewEnd = Begin;
-
+
// Destroy excess elements.
destroy_range(NewEnd, End);
-
+
// Trim.
End = NewEnd;
return *this;
}
-
+
// If we have to grow to have enough elements, destroy the current elements.
// This allows us to avoid copying them during the grow.
if (unsigned(Capacity-Begin) < RHSSize) {
// Otherwise, use assignment for the already-constructed elements.
std::copy(RHS.Begin, RHS.Begin+CurSize, Begin);
}
-
+
// Copy construct the new elements in place.
std::uninitialized_copy(RHS.Begin+CurSize, RHS.End, Begin+CurSize);
-
+
// Set end.
End = Begin+RHSSize;
return *this;
}
-
+
/// SmallVector - This is a 'vector' (really, a variable-sized array), optimized
/// for the case when the array is small. It contains some number of elements
/// in-place, which allows it to avoid heap allocation when the actual number of
enum {
// MinUs - The number of U's require to cover N T's.
MinUs = (static_cast<unsigned int>(sizeof(T))*N +
- static_cast<unsigned int>(sizeof(U)) - 1) /
+ static_cast<unsigned int>(sizeof(U)) - 1) /
static_cast<unsigned int>(sizeof(U)),
-
+
// NumInlineEltsElts - The number of elements actually in this array. There
// is already one in the parent class, and we have to round up to avoid
// having a zero-element array.
NumInlineEltsElts = MinUs > 1 ? (MinUs - 1) : 1,
-
+
// NumTsAvailable - The number of T's we actually have space for, which may
// be more than N due to rounding.
NumTsAvailable = (NumInlineEltsElts+1)*static_cast<unsigned int>(sizeof(U))/
static_cast<unsigned int>(sizeof(T))
};
U InlineElts[NumInlineEltsElts];
-public:
+public:
SmallVector() : SmallVectorImpl<T>(NumTsAvailable) {
}
-
+
explicit SmallVector(unsigned Size, const T &Value = T())
: SmallVectorImpl<T>(NumTsAvailable) {
this->reserve(Size);
while (Size--)
this->push_back(Value);
}
-
+
template<typename ItTy>
SmallVector(ItTy S, ItTy E) : SmallVectorImpl<T>(NumTsAvailable) {
this->append(S, E);
}
-
+
SmallVector(const SmallVector &RHS) : SmallVectorImpl<T>(NumTsAvailable) {
if (!RHS.empty())
SmallVectorImpl<T>::operator=(RHS);
SmallVectorImpl<T>::operator=(RHS);
return *this;
}
-
+
};
} // End llvm namespace
swap(llvm::SmallVectorImpl<T> &LHS, llvm::SmallVectorImpl<T> &RHS) {
LHS.swap(RHS);
}
-
+
/// Implement std::swap in terms of SmallVector swap.
template<typename T, unsigned N>
inline void
CurrElementIter = Elements.begin ();
}
-
+
// Assignment
SparseBitVector& operator=(const SparseBitVector& RHS) {
Elements.clear();
-
+
ElementListConstIter ElementIter = RHS.Elements.begin();
while (ElementIter != RHS.Elements.end()) {
Elements.push_back(SparseBitVectorElement<ElementSize>(*ElementIter));
}
CurrElementIter = Elements.begin ();
-
+
return *this;
}
const Statistic &operator-=(const unsigned &V) { Value -= V; return init(); }
const Statistic &operator*=(const unsigned &V) { Value *= V; return init(); }
const Statistic &operator/=(const unsigned &V) { Value /= V; return init(); }
-
+
protected:
Statistic &init() {
if (!Initialized) RegisterStatistic();
}
void RegisterStatistic();
};
-
+
// STATISTIC - A macro to make definition of statistics really simple. This
// automatically passes the DEBUG_TYPE of the file into the statistic.
#define STATISTIC(VARNAME, DESC) \
}
return BufPtr;
}
-
+
static inline std::string utohexstr(uint64_t X) {
char Buffer[40];
return utohex_buffer(X, Buffer+40);
static inline std::string utostr(uint64_t X, bool isNeg = false) {
if (X == uint32_t(X))
return utostr_32(uint32_t(X), isNeg);
-
+
char Buffer[40];
char *BufPtr = Buffer+39;
-
+
*BufPtr = 0; // Null terminate buffer...
if (X == 0) *--BufPtr = '0'; // Handle special case...
-
+
while (X) {
*--BufPtr = '0' + char(X % 10);
X /= 10;
}
-
+
if (isNeg) *--BufPtr = '-'; // Add negative sign...
return std::string(BufPtr);
}
/// StringsEqualNoCase - Return true if the two strings are equal, ignoring
/// case.
-static inline bool StringsEqualNoCase(const std::string &LHS,
+static inline bool StringsEqualNoCase(const std::string &LHS,
const std::string &RHS) {
if (LHS.size() != RHS.size()) return false;
for (unsigned i = 0, e = static_cast<unsigned>(LHS.size()); i != e; ++i)
/// StringsEqualNoCase - Return true if the two strings are equal, ignoring
/// case.
-static inline bool StringsEqualNoCase(const std::string &LHS,
+static inline bool StringsEqualNoCase(const std::string &LHS,
const char *RHS) {
for (unsigned i = 0, e = static_cast<unsigned>(LHS.size()); i != e; ++i) {
if (RHS[i] == 0) return false; // RHS too short.
}
return RHS[LHS.size()] == 0; // Not too long?
}
-
+
/// CStrInCStrNoCase - Portable version of strcasestr. Locates the first
/// occurance of c-string 's2' in string 's1', ignoring case. Returns
/// NULL if 's2' cannot be found.
// Are either strings NULL or empty?
if (!s1 || !s2 || s1[0] == '\0' || s2[0] == '\0')
return 0;
-
+
if (s1 == s2)
return s1;
-
+
const char *I1=s1, *I2=s2;
-
+
while (*I1 != '\0' && *I2 != '\0' )
if (tolower(*I1) != tolower(*I2)) { // No match. Start over.
++s1; I1 = s1; I2 = s2;
/// UniqueVector - This class produces a sequential ID number (base 1) for each
/// unique entry that is added. T is the type of entries in the vector. This
/// class should have an implementation of operator== and of operator<.
-/// Entries can be fetched using operator[] with the entry ID.
+/// Entries can be fetched using operator[] with the entry ID.
template<class T> class UniqueVector {
private:
// Map - Used to handle the correspondence of entry to ID.
// Vector - ID ordered vector of entries. Entries can be indexed by ID - 1.
//
std::vector<T> Vector;
-
+
public:
/// insert - Append entry to the vector if it doesn't already exist. Returns
/// the entry's index + 1 to be used as a unique ID.
unsigned insert(const T &Entry) {
// Check if the entry is already in the map.
unsigned &Val = Map[Entry];
-
+
// See if entry exists, if so return prior ID.
if (Val) return Val;
// Compute ID for entry.
Val = static_cast<unsigned>(Vector.size()) + 1;
-
+
// Insert in vector.
Vector.push_back(Entry);
return Val;
}
-
+
/// idFor - return the ID for an existing entry. Returns 0 if the entry is
/// not found.
unsigned idFor(const T &Entry) const {
// Search for entry in the map.
typename std::map<T, unsigned>::const_iterator MI = Map.find(Entry);
-
+
// See if entry exists, if so return ID.
if (MI != Map.end()) return MI->second;
-
+
// No luck.
return 0;
}
assert(ID-1 < size() && "ID is 0 or out of range!");
return Vector[ID - 1];
}
-
+
/// size - Returns the number of entries in the vector.
///
size_t size() const { return Vector.size(); }
-
+
/// empty - Returns true if the vector is empty.
///
bool empty() const { return Vector.empty(); }
-
+
/// reset - Clears all the entries.
///
void reset() {
//==-- llvm/ADT/hash_map.h - "Portable" wrapper around hash_map --*- C++ -*-==//
-//
+//
// The LLVM Compiler Infrastructure
//
// This file is distributed under the University of Illinois Open Source
// License. See LICENSE.TXT for details.
-//
+//
//===----------------------------------------------------------------------===//
-//
+//
// This file provides a wrapper around the mysterious <hash_map> header file
// that seems to move around between GCC releases into and out of namespaces at
// will. #including this header will cause hash_map to be available in the
class _HashFcn = hash<KeyType>,
class _EqualKey = equal_to<KeyType>,
class _A = allocator <ValueType> >
-class hash_map : public rw_hashmap<KeyType, ValueType, class _HashFcn,
+class hash_map : public rw_hashmap<KeyType, ValueType, class _HashFcn,
class _EqualKey, class _A> {
};
// hash_map to use GCC's hash classes.
namespace stdext {
template<class Key> struct hash;
-
+
// Provide a hash function for unsigned ints...
template<> struct hash<unsigned int> {
inline size_t operator()(unsigned int Val) const {
//==-- llvm/ADT/hash_set.h - "Portable" wrapper around hash_set --*- C++ -*-==//
-//
+//
// The LLVM Compiler Infrastructure
//
// This file is distributed under the University of Illinois Open Source
// License. See LICENSE.TXT for details.
-//
+//
//===----------------------------------------------------------------------===//
// vim:ft=cpp
//
class _HashFcn = hash<ValueType>,
class _EqualKey = equal_to<ValueType>,
class _A = allocator <ValueType> >
-class hash_set :
+class hash_set :
public rw_hashset<ValueType, class _HashFcn, class _EqualKey, class _A> {
};
//==-- llvm/ADT/ilist_node.h - Intrusive Linked List Helper ------*- 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 ilist_node class template, which is a convenient
//==-- llvm/ADT/iterator.h - Portable wrapper around <iterator> --*- C++ -*-==//
-//
+//
// The LLVM Compiler Infrastructure
//
// This file is distributed under the University of Illinois Open Source
// License. See LICENSE.TXT for details.
-//
+//
//===----------------------------------------------------------------------===//
//
// This file provides a wrapper around the mysterious <iterator> header file.
projects / oota-llvm.git / commitdiff