34a35,36
> #include <bitset>
> #include <cassert>
36d37
< #include <limits>
37a39
> #include "base/misc.hh"
40,51c42,43
< /*
< * This defines the number of longs (32-bits on 32 bit machines,
< * 64-bit on 64-bit AMD machines) to use to hold the set...
< * the default is 4, allowing 128 or 256 different members
< * of the set.
< *
< * This should never need to be changed for correctness reasons,
< * though increasing it will increase performance for larger
< * set sizes at the cost of a (much) larger memory footprint
< *
< */
< const int NUMBER_WORDS_PER_SET = 1;
---
> // Change for systems with more than 64 controllers of a particular type.
> const int NUMBER_BITS_PER_SET = 64;
56,58c48,50
< int m_nSize; // the number of bits in this set
< int m_nArrayLen; // the number of 32-bit words that are
< // held in the array
---
> // Number of bits in use in this set.
> int m_nSize;
> std::bitset<NUMBER_BITS_PER_SET> bits;
60,63c52,53
< // Changed 5/24/05 for static allocation of array
< // note that "long" corresponds to 32 bits on a 32-bit machine,
< // 64 bits if the -m64 parameter is passed to g++, which it is
< // for an AMD opteron under our configuration
---
> public:
> Set() : m_nSize(0) {}
65,67c55,61
< // an word array to hold the bits in the set
< unsigned long *m_p_nArray;
< unsigned long m_p_nArray_Static[NUMBER_WORDS_PER_SET];
---
> Set(int size) : m_nSize(size)
> {
> if (size > NUMBER_BITS_PER_SET)
> fatal("Number of bits(%d) < size specified(%d). "
> "Increase the number of bits and recompile.\n",
> NUMBER_BITS_PER_SET, size);
> }
69,72c63,64
< static const int LONG_BITS =
< std::numeric_limits<unsigned long>::digits + 1;
< static const int INDEX_SHIFT = LONG_BITS == 64 ? 6 : 5;
< static const int INDEX_MASK = (1 << INDEX_SHIFT) - 1;
---
> Set(const Set& obj) : m_nSize(obj.m_nSize), bits(obj.bits) {}
> ~Set() {}
74c66,71
< void clearExcess();
---
> Set& operator=(const Set& obj)
> {
> m_nSize = obj.m_nSize;
> bits = obj.bits;
> return *this;
> }
76,83d72
< public:
< Set();
< Set(int size);
< Set(const Set& obj);
< ~Set();
<
< Set& operator=(const Set& obj);
<
87,88c76
< m_p_nArray[index >> INDEX_SHIFT] |=
< (((unsigned long) 1) << (index & INDEX_MASK));
---
> bits.set(index);
91c79,88
< void addSet(const Set& set);
---
> /*
> * This function should set all the bits in the current set that are
> * already set in the parameter set
> */
> void
> addSet(const Set& obj)
> {
> assert(m_nSize == obj.m_nSize);
> bits |= obj.bits;
> }
92a90,92
> /*
> * This function clears bits that are =1 in the parameter set
> */
96,97c96
< m_p_nArray[index >> INDEX_SHIFT] &=
< ~(((unsigned long)1) << (index & INDEX_MASK));
---
> bits.reset(index);
100,101c99,101
< void removeSet(const Set& set);
<
---
> /*
> * This function clears bits that are =1 in the parameter set
> */
103c103
< clear()
---
> removeSet(const Set& obj)
105,106c105,106
< for (int i = 0; i < m_nArrayLen; i++)
< m_p_nArray[i] = 0;
---
> assert(m_nSize == obj.m_nSize);
> bits &= (~obj.bits);
109,111c109
< void broadcast();
< int count() const;
< bool isEqual(const Set& set) const;
---
> void clear() { bits.reset(); }
112a111,136
> /*
> * this function sets all bits in the set
> */
> void broadcast()
> {
> bits.set();
> for (int j = m_nSize; j < NUMBER_BITS_PER_SET; ++j) {
> bits.reset(j);
> }
> }
>
> /*
> * This function returns the population count of 1's in the set
> */
> int count() const { return bits.count(); }
>
> /*
> * This function checks for set equality
> */
> bool
> isEqual(const Set& obj) const
> {
> assert(m_nSize == obj.m_nSize);
> return bits == obj.bits;
> }
>
114c138,145
< Set OR(const Set& orSet) const;
---
> Set
> OR(const Set& obj) const
> {
> assert(m_nSize == obj.m_nSize);
> Set r(m_nSize);
> r.bits = bits | obj.bits;
> return r;
> };
117c148,155
< Set AND(const Set& andSet) const;
---
> Set
> AND(const Set& obj) const
> {
> assert(m_nSize == obj.m_nSize);
> Set r(m_nSize);
> r.bits = bits & obj.bits;
> return r;
> }
121c159
< intersectionIsEmpty(const Set& other_set) const
---
> intersectionIsEmpty(const Set& obj) const
123,126c161,162
< for (int i = 0; i < m_nArrayLen; i++)
< if (m_p_nArray[i] & other_set.m_p_nArray[i])
< return false;
< return true;
---
> std::bitset<NUMBER_BITS_PER_SET> r = bits & obj.bits;
> return r.none();
129,131c165,168
< bool isSuperset(const Set& test) const;
< bool isSubset(const Set& test) const { return test.isSuperset(*this); }
<
---
> /*
> * Returns false if a bit is set in the parameter set that is NOT set
> * in this set
> */
133c170
< isElement(NodeID element) const
---
> isSuperset(const Set& test) const
135,136c172,174
< return (m_p_nArray[element>>INDEX_SHIFT] &
< (((unsigned long)1) << (element & INDEX_MASK))) != 0;
---
> assert(m_nSize == test.m_nSize);
> std::bitset<NUMBER_BITS_PER_SET> r = bits | test.bits;
> return (r == bits);
139,140c177
< bool isBroadcast() const;
< bool isEmpty() const;
---
> bool isSubset(const Set& test) const { return test.isSuperset(*this); }
142c179
< NodeID smallestElement() const;
---
> bool isElement(NodeID element) const { return bits.test(element); }
144c181,188
< void setSize(int size);
---
> /*
> * this function returns true iff all bits in use are set
> */
> bool
> isBroadcast() const
> {
> return (bits.count() == m_nSize);
> }
146,147c190,192
< NodeID
< elementAt(int index) const
---
> bool isEmpty() const { return bits.none(); }
>
> NodeID smallestElement() const
149,152c194,199
< if (isElement(index))
< return (NodeID)true;
< else
< return 0;
---
> for (int i = 0; i < m_nSize; ++i) {
> if (bits.test(i)) {
> return i;
> }
> }
> panic("No smallest element of an empty set.");
154a202,203
> bool elementAt(int index) const { return bits[index]; }
>
157c206,220
< void print(std::ostream& out) const;
---
> void
> setSize(int size)
> {
> if (size > NUMBER_BITS_PER_SET)
> fatal("Number of bits(%d) < size specified(%d). "
> "Increase the number of bits and recompile.\n",
> NUMBER_BITS_PER_SET, size);
> m_nSize = size;
> bits.reset();
> }
>
> void print(std::ostream& out) const
> {
> out << "[Set (" << m_nSize << "): " << bits << "]";
> }