From 30eee05f3f809e3950c8d8463ecdd9807c943692 Mon Sep 17 00:00:00 2001 From: jsmall-nvidia Date: Thu, 9 May 2019 14:08:30 -0400 Subject: IntSet -> UIntSet (#961) * * Fix warning in vk-swap-chain around use of Index. Rename _indexOf to _indexOfFormat. * Rename IntSet to UIntSet and put in own files slang-uint-set.h.cpp. Use UInt as the held type. * On UintSet setMax -> resizeAndClear. Doing so revealed bug in add. * Closer following of conventions - use kPrefix for constants (even though held in 'enum') * Small fixes/improvements * * Add some documentation to UIntSet methods * Use memset to set/reset bits * Fix some tabbing. Rename oldBufferSize -> oldCount * Fix tabs. --- source/core/core.vcxproj | 3 +- source/core/core.vcxproj.filters | 9 +- source/core/dictionary.h | 6 +- source/core/int-set.h | 209 --------------------------------------- source/core/slang-uint-set.cpp | 151 ++++++++++++++++++++++++++++ source/core/slang-uint-set.h | 118 ++++++++++++++++++++++ 6 files changed, 280 insertions(+), 216 deletions(-) delete mode 100644 source/core/int-set.h create mode 100644 source/core/slang-uint-set.cpp create mode 100644 source/core/slang-uint-set.h (limited to 'source/core') diff --git a/source/core/core.vcxproj b/source/core/core.vcxproj index 4b730f028..0416eaed6 100644 --- a/source/core/core.vcxproj +++ b/source/core/core.vcxproj @@ -178,7 +178,6 @@ - @@ -196,6 +195,7 @@ + @@ -218,6 +218,7 @@ + diff --git a/source/core/core.vcxproj.filters b/source/core/core.vcxproj.filters index e0341df7a..0a0ea93fa 100644 --- a/source/core/core.vcxproj.filters +++ b/source/core/core.vcxproj.filters @@ -33,9 +33,6 @@ Header Files - - Header Files - Header Files @@ -87,6 +84,9 @@ Header Files + + Header Files + Header Files @@ -149,6 +149,9 @@ Source Files + + Source Files + Source Files diff --git a/source/core/dictionary.h b/source/core/dictionary.h index a38699368..1b3525756 100644 --- a/source/core/dictionary.h +++ b/source/core/dictionary.h @@ -2,7 +2,7 @@ #define CORE_LIB_DICTIONARY_H #include "list.h" #include "common.h" -#include "int-set.h" +#include "slang-uint-set.h" #include "exception.h" #include "slang-math.h" #include "hash.h" @@ -81,7 +81,7 @@ namespace Slang private: int bucketSizeMinusOne; int _count; - IntSet marks; + UIntSet marks; KeyValuePair* hashMap; void Free() { @@ -180,7 +180,7 @@ namespace Slang Dictionary newDict; newDict.bucketSizeMinusOne = newSize - 1; newDict.hashMap = new KeyValuePair[newSize]; - newDict.marks.setMax(newSize * 2); + newDict.marks.resizeAndClear(newSize * 2); if (hashMap) { for (auto & kvPair : *this) diff --git a/source/core/int-set.h b/source/core/int-set.h deleted file mode 100644 index 6b6243552..000000000 --- a/source/core/int-set.h +++ /dev/null @@ -1,209 +0,0 @@ -#ifndef BIT_VECTOR_INT_SET_H -#define BIT_VECTOR_INT_SET_H - -#include "list.h" -#include "slang-math.h" -#include "common.h" -#include "exception.h" - -#include - -namespace Slang -{ - /* The set works by storing as a bit per integer */ - class IntSet - { - private: - typedef uint32_t Element; ///< Type that holds the bits - enum - { - ELEMENT_SHIFT = 5, ///< How many bits to shift to get Element index from an index - ELEMENT_SIZE = sizeof(Element) * 8, ///< The number of bits in an element - ELEMENT_MASK = ELEMENT_SIZE - 1, ///< Mask to get shift from an index - }; - - // Make sure they are correct for the Element type - SLANG_COMPILE_TIME_ASSERT( (1 << ELEMENT_SHIFT) == ELEMENT_SIZE); - - List m_buffer; - - public: - IntSet() - {} - IntSet(const IntSet& other) - { - m_buffer = other.m_buffer; - } - IntSet(IntSet && other) - { - *this = (_Move(other)); - } - IntSet& operator=(IntSet&& other) - { - m_buffer = _Move(other.m_buffer); - return *this; - } - IntSet& operator=(const IntSet& other) - { - m_buffer = other.m_buffer; - return *this; - } - int GetHashCode() - { - int rs = 0; - for (auto val : m_buffer) - rs ^= val; - return rs; - } - IntSet(Int maxVal) - { - setMax(maxVal); - } - Int getCount() const - { - return Int(m_buffer.getCount()) * ELEMENT_SIZE; - } - void setMax(Int val) - { - resize(val); - clear(); - } - void setAll() - { - for (Index i = 0; i < m_buffer.getCount(); i++) - m_buffer[i] = ~Element(0); - } - void resize(Int size) - { - const Index oldBufferSize = m_buffer.getCount(); - const Index newCount = Index((size + ELEMENT_MASK) >> ELEMENT_SHIFT); - m_buffer.setCount(newCount); - - if (newCount > oldBufferSize) - memset(m_buffer.getBuffer() + oldBufferSize, 0, (newCount - oldBufferSize) * sizeof(Element)); - } - void clear() - { - for (Index i = 0; i < m_buffer.getCount(); i++) - m_buffer[i] = 0; - } - void clearAndDeallocate() - { - m_buffer.clearAndDeallocate(); - } - void add(Int val) - { - Index id = Index(val >> 5); - if (id < m_buffer.getCount()) - m_buffer[id] |= Element(1) << (val & ELEMENT_MASK); - else - { - Index oldCount = m_buffer.getCount(); - m_buffer.setCount(id + 1); - memset(m_buffer.getBuffer() + oldCount, 0, (m_buffer.getCount() - oldCount) * sizeof(Element)); - m_buffer[id] |= Element(1) << (val & ELEMENT_MASK); - } - } - void remove(Int val) - { - const Index idx = Index(val >> ELEMENT_SHIFT); - if (idx < m_buffer.getCount()) - m_buffer[idx] &= ~(Element(1) << (val & ELEMENT_MASK)); - } - bool contains(Int val) const - { - const Index idx = Index(val >> ELEMENT_SHIFT); - if (idx >= m_buffer.getCount()) - return false; - return (m_buffer[idx] & (Element(1) << (val & ELEMENT_MASK))) != 0; - } - void unionWith(const IntSet& set) - { - const Index minCount = Math::Min(set.m_buffer.getCount(), m_buffer.getCount()); - for (Index i = 0; i < minCount; i++) - { - m_buffer[i] |= set.m_buffer[i]; - } - if (set.m_buffer.getCount() > m_buffer.getCount()) - m_buffer.addRange(set.m_buffer.getBuffer()+m_buffer.getCount(), set.m_buffer.getCount()-m_buffer.getCount()); - } - bool operator==(const IntSet& set) const - { - Index minCount = Math::Min(set.m_buffer.getCount(), m_buffer.getCount()); - if (::memcmp(m_buffer.getBuffer(), set.m_buffer.getBuffer(), minCount * sizeof(Element)) != 0) - { - return false; - } - return m_buffer.getCount() == set.m_buffer.getCount() || (_areRemainingZeros(m_buffer, minCount) && _areRemainingZeros(set.m_buffer, minCount)); - } - bool operator!=(const IntSet& set) const - { - return !(*this == set); - } - void intersectWith(const IntSet& set) - { - if (set.m_buffer.getCount() < m_buffer.getCount()) - memset(m_buffer.getBuffer() + set.m_buffer.getCount(), 0, (m_buffer.getCount() - set.m_buffer.getCount()) * sizeof(Element)); - - const Index minCount = Math::Min(set.m_buffer.getCount(), m_buffer.getCount()); - for (Index i = 0; i < minCount; i++) - { - m_buffer[i] &= set.m_buffer[i]; - } - } - static void calcUnion(IntSet& outRs, const IntSet& set1, const IntSet& set2) - { - outRs.m_buffer.setCount(Math::Max(set1.m_buffer.getCount(), set2.m_buffer.getCount())); - outRs.clear(); - for (Index i = 0; i < set1.m_buffer.getCount(); i++) - outRs.m_buffer[i] |= set1.m_buffer[i]; - for (Index i = 0; i < set2.m_buffer.getCount(); i++) - outRs.m_buffer[i] |= set2.m_buffer[i]; - } - static void calcIntersection(IntSet& outRs, const IntSet& set1, const IntSet& set2) - { - const Index minCount = Math::Min(set1.m_buffer.getCount(), set2.m_buffer.getCount()); - outRs.m_buffer.setCount(minCount); - - for (Index i = 0; i < minCount; i++) - outRs.m_buffer[i] = set1.m_buffer[i] & set2.m_buffer[i]; - } - static void calcSubtract(IntSet& outRs, const IntSet& set1, const IntSet& set2) - { - outRs.m_buffer.setCount(set1.m_buffer.getCount()); - - const Index minCount = Math::Min(set1.m_buffer.getCount(), set2.m_buffer.getCount()); - for (Index i = 0; i < minCount; i++) - outRs.m_buffer[i] = set1.m_buffer[i] & (~set2.m_buffer[i]); - } - static bool hasIntersection(const IntSet& set1, const IntSet& set2) - { - const Index minCount = Math::Min(set1.m_buffer.getCount(), set2.m_buffer.getCount()); - for (Index i = 0; i < minCount; i++) - { - if (set1.m_buffer[i] & set2.m_buffer[i]) - return true; - } - return false; - } - - private: - static bool _areRemainingZeros(const List& elems, Index minCount) - { - const Index count = elems.getCount(); - const Element* base = elems.getBuffer(); - - for (Index i = minCount; i < count; ++i) - { - if (base[i]) - { - return false; - } - } - return true; - } - - }; -} - -#endif diff --git a/source/core/slang-uint-set.cpp b/source/core/slang-uint-set.cpp new file mode 100644 index 000000000..656bd8ba8 --- /dev/null +++ b/source/core/slang-uint-set.cpp @@ -0,0 +1,151 @@ +#include "slang-uint-set.h" + +namespace Slang +{ + +static bool _areAllZero(const UIntSet::Element* elems, Index count) +{ + for (Index i = 0; count; ++i) + { + if (elems[i]) + { + return false; + } + } + return true; +} + +UIntSet& UIntSet::operator=(UIntSet&& other) +{ + m_buffer = _Move(other.m_buffer); + return *this; +} + +UIntSet& UIntSet::operator=(const UIntSet& other) +{ + m_buffer = other.m_buffer; + return *this; +} + +int UIntSet::GetHashCode() +{ + int rs = 0; + for (auto val : m_buffer) + rs ^= val; + return rs; +} + +void UIntSet::resizeAndClear(UInt val) +{ + // TODO(JS): This could be faster in that if the resize is larger the additional area is cleared twice + resize(val); + clear(); +} + +void UIntSet::setAll() +{ + ::memset(m_buffer.getBuffer(), -1, m_buffer.getCount() * sizeof(Element)); +} + +void UIntSet::resize(UInt size) +{ + const Index oldCount = m_buffer.getCount(); + const Index newCount = Index((size + kElementMask) >> kElementShift); + m_buffer.setCount(newCount); + + if (newCount > oldCount) + { + ::memset(m_buffer.getBuffer() + oldCount, 0, (newCount - oldCount) * sizeof(Element)); + } +} + +void UIntSet::clear() +{ + ::memset(m_buffer.getBuffer(), 0, m_buffer.getCount() * sizeof(Element)); +} + +void UIntSet::clearAndDeallocate() +{ + m_buffer.clearAndDeallocate(); +} + +void UIntSet::unionWith(const UIntSet& set) +{ + const Index minCount = Math::Min(set.m_buffer.getCount(), m_buffer.getCount()); + for (Index i = 0; i < minCount; i++) + { + m_buffer[i] |= set.m_buffer[i]; + } + + if (set.m_buffer.getCount() > m_buffer.getCount()) + m_buffer.addRange(set.m_buffer.getBuffer() + m_buffer.getCount(), set.m_buffer.getCount() - m_buffer.getCount()); +} + +bool UIntSet::operator==(const UIntSet& set) const +{ + const Index aCount = m_buffer.getCount(); + const auto aElems = m_buffer.getBuffer(); + + const Index bCount = set.m_buffer.getCount(); + const auto bElems = set.m_buffer.getBuffer(); + + const Index minCount = Math::Min(aCount, bCount); + + return ::memcmp(aElems, bElems, minCount) == 0 && + _areAllZero(aElems + minCount, aCount - minCount) && + _areAllZero(bElems + minCount, bCount - minCount); +} + +void UIntSet::intersectWith(const UIntSet& set) +{ + if (set.m_buffer.getCount() < m_buffer.getCount()) + ::memset(m_buffer.getBuffer() + set.m_buffer.getCount(), 0, (m_buffer.getCount() - set.m_buffer.getCount()) * sizeof(Element)); + + const Index minCount = Math::Min(set.m_buffer.getCount(), m_buffer.getCount()); + for (Index i = 0; i < minCount; i++) + { + m_buffer[i] &= set.m_buffer[i]; + } +} + +/* static */void UIntSet::calcUnion(UIntSet& outRs, const UIntSet& set1, const UIntSet& set2) +{ + outRs.m_buffer.setCount(Math::Max(set1.m_buffer.getCount(), set2.m_buffer.getCount())); + outRs.clear(); + for (Index i = 0; i < set1.m_buffer.getCount(); i++) + outRs.m_buffer[i] |= set1.m_buffer[i]; + for (Index i = 0; i < set2.m_buffer.getCount(); i++) + outRs.m_buffer[i] |= set2.m_buffer[i]; +} + +/* static */void UIntSet::calcIntersection(UIntSet& outRs, const UIntSet& set1, const UIntSet& set2) +{ + const Index minCount = Math::Min(set1.m_buffer.getCount(), set2.m_buffer.getCount()); + outRs.m_buffer.setCount(minCount); + + for (Index i = 0; i < minCount; i++) + outRs.m_buffer[i] = set1.m_buffer[i] & set2.m_buffer[i]; +} + +/* static */void UIntSet::calcSubtract(UIntSet& outRs, const UIntSet& set1, const UIntSet& set2) +{ + outRs.m_buffer.setCount(set1.m_buffer.getCount()); + + const Index minCount = Math::Min(set1.m_buffer.getCount(), set2.m_buffer.getCount()); + for (Index i = 0; i < minCount; i++) + outRs.m_buffer[i] = set1.m_buffer[i] & (~set2.m_buffer[i]); +} + +/* static */bool UIntSet::hasIntersection(const UIntSet& set1, const UIntSet& set2) +{ + const Index minCount = Math::Min(set1.m_buffer.getCount(), set2.m_buffer.getCount()); + for (Index i = 0; i < minCount; i++) + { + if (set1.m_buffer[i] & set2.m_buffer[i]) + return true; + } + return false; +} + +} + diff --git a/source/core/slang-uint-set.h b/source/core/slang-uint-set.h new file mode 100644 index 000000000..25f0c9269 --- /dev/null +++ b/source/core/slang-uint-set.h @@ -0,0 +1,118 @@ +#ifndef SLANG_UINT_SET_H +#define SLANG_UINT_SET_H + +#include "list.h" +#include "slang-math.h" +#include "common.h" + +#include + +namespace Slang +{ + +/* Hold a set of UInt values. Implementation works by storing as a bit per value */ +class UIntSet +{ +public: + typedef uint32_t Element; ///< Type that holds the bits to say if value is present + + UIntSet() {} + UIntSet(const UIntSet& other) { m_buffer = other.m_buffer; } + UIntSet(UIntSet && other) { *this = (_Move(other)); } + UIntSet(UInt maxVal) { resizeAndClear(maxVal); } + + UIntSet& operator=(UIntSet&& other); + UIntSet& operator=(const UIntSet& other); + + int GetHashCode(); + + /// Return the count of all bits directly represented + Int getCount() const { return Int(m_buffer.getCount()) * kElementSize; } + + /// Resize such that val can be stored and clear contents + void resizeAndClear(UInt val); + /// Set all of the values up to count, as set + void setAll(); + /// Resize (but maintain contents) up to bit size. + /// NOTE! That since storage is in Element blocks, it may mean some values after size are set (up to the Element boundary) + void resize(UInt size); + + /// Clear all of the contents (by clearing the bits) + void clear(); + + /// Clear all the contents and free memory + void clearAndDeallocate(); + + /// Add a value + inline void add(UInt val); + /// Remove a value + inline void remove(UInt val); + /// Returns true if the value is present + inline bool contains(UInt val) const; + + /// == + bool operator==(const UIntSet& set) const; + /// != + bool operator!=(const UIntSet& set) const { return !(*this == set); } + + /// Store the union between this and set in this + void unionWith(const UIntSet& set); + /// Store the intersection between this and set in this + void intersectWith(const UIntSet& set); + + /// Store the union of set1 and set2 in outRs + static void calcUnion(UIntSet& outRs, const UIntSet& set1, const UIntSet& set2); + /// Store the intersection of set1 and set2 in outRs + static void calcIntersection(UIntSet& outRs, const UIntSet& set1, const UIntSet& set2); + /// Store the subtraction of set2 from set1 in outRs + static void calcSubtract(UIntSet& outRs, const UIntSet& set1, const UIntSet& set2); + + /// Returns true if set1 and set2 have a same value set (ie there is an intersection) + static bool hasIntersection(const UIntSet& set1, const UIntSet& set2); + +private: + enum + { + kElementShift = 5, ///< How many bits to shift to get Element index from an index + kElementSize = sizeof(Element) * 8, ///< The number of bits in an element + kElementMask = kElementSize - 1, ///< Mask to get shift from an index + }; + + // Make sure they are correct for the Element type + SLANG_COMPILE_TIME_ASSERT((1 << kElementShift) == kElementSize); + + List m_buffer; +}; + +// -------------------------------------------------------------------------- +inline void UIntSet::remove(UInt val) +{ + const Index idx = Index(val >> kElementShift); + if (idx < m_buffer.getCount()) + { + m_buffer[idx] &= ~(Element(1) << (val & kElementMask)); + } +} + +// -------------------------------------------------------------------------- +inline bool UIntSet::contains(UInt val) const +{ + const Index idx = Index(val >> kElementShift); + return idx <= m_buffer.getCount() && + ((m_buffer[idx] & (Element(1) << (val & kElementMask))) != 0); +} + +// -------------------------------------------------------------------------- +inline void UIntSet::add(UInt val) +{ + const Index idx = Index(val >> kElementShift); + if (idx >= m_buffer.getCount()) + { + resize(val); + } + m_buffer[idx] |= Element(1) << (val & kElementMask); +} + +} + +#endif -- cgit v1.2.3