summaryrefslogtreecommitdiffstats
path: root/source
diff options
context:
space:
mode:
Diffstat (limited to 'source')
-rw-r--r--source/core/core.vcxproj3
-rw-r--r--source/core/core.vcxproj.filters9
-rw-r--r--source/core/dictionary.h6
-rw-r--r--source/core/int-set.h209
-rw-r--r--source/core/slang-uint-set.cpp151
-rw-r--r--source/core/slang-uint-set.h118
6 files changed, 280 insertions, 216 deletions
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 @@
<ClInclude Include="dictionary.h" />
<ClInclude Include="exception.h" />
<ClInclude Include="hash.h" />
- <ClInclude Include="int-set.h" />
<ClInclude Include="list.h" />
<ClInclude Include="platform.h" />
<ClInclude Include="secure-crt.h" />
@@ -196,6 +195,7 @@
<ClInclude Include="slang-string-util.h" />
<ClInclude Include="slang-string.h" />
<ClInclude Include="slang-test-tool-util.h" />
+ <ClInclude Include="slang-uint-set.h" />
<ClInclude Include="slang-writer.h" />
<ClInclude Include="smart-pointer.h" />
<ClInclude Include="stream.h" />
@@ -218,6 +218,7 @@
<ClCompile Include="slang-string-util.cpp" />
<ClCompile Include="slang-string.cpp" />
<ClCompile Include="slang-test-tool-util.cpp" />
+ <ClCompile Include="slang-uint-set.cpp" />
<ClCompile Include="slang-writer.cpp" />
<ClCompile Include="stream.cpp" />
<ClCompile Include="text-io.cpp" />
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 @@
<ClInclude Include="hash.h">
<Filter>Header Files</Filter>
</ClInclude>
- <ClInclude Include="int-set.h">
- <Filter>Header Files</Filter>
- </ClInclude>
<ClInclude Include="list.h">
<Filter>Header Files</Filter>
</ClInclude>
@@ -87,6 +84,9 @@
<ClInclude Include="slang-test-tool-util.h">
<Filter>Header Files</Filter>
</ClInclude>
+ <ClInclude Include="slang-uint-set.h">
+ <Filter>Header Files</Filter>
+ </ClInclude>
<ClInclude Include="slang-writer.h">
<Filter>Header Files</Filter>
</ClInclude>
@@ -149,6 +149,9 @@
<ClCompile Include="slang-test-tool-util.cpp">
<Filter>Source Files</Filter>
</ClCompile>
+ <ClCompile Include="slang-uint-set.cpp">
+ <Filter>Source Files</Filter>
+ </ClCompile>
<ClCompile Include="slang-writer.cpp">
<Filter>Source Files</Filter>
</ClCompile>
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<TKey, TValue>* hashMap;
void Free()
{
@@ -180,7 +180,7 @@ namespace Slang
Dictionary<TKey, TValue> newDict;
newDict.bucketSizeMinusOne = newSize - 1;
newDict.hashMap = new KeyValuePair<TKey, TValue>[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 <memory.h>
-
-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<Element> 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<Element>& 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 <memory.h>
+
+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<Element> 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
generated by cgit v1.2.3 (git 2.39.1) at 2026-06-01 15:25:52 +0000