summaryrefslogtreecommitdiff
path: root/src/mem/ruby/common/Set.cc
diff options
context:
space:
mode:
Diffstat (limited to 'src/mem/ruby/common/Set.cc')
-rw-r--r--src/mem/ruby/common/Set.cc549
1 files changed, 447 insertions, 102 deletions
diff --git a/src/mem/ruby/common/Set.cc b/src/mem/ruby/common/Set.cc
index ce4b4af04..b4c4e4789 100644
--- a/src/mem/ruby/common/Set.cc
+++ b/src/mem/ruby/common/Set.cc
@@ -32,200 +32,545 @@
*
* Description: See Set.h
*
- * $Id$
+ * $Id: BigSet.C 1.9 05/01/19 13:12:25-06:00 mikem@maya.cs.wisc.edu $
*
*/
+// modified (rewritten) 05/20/05 by Dan Gibson to accomimdate FASTER >32 bit
+// set sizes
+
#include "mem/ruby/common/Set.hh"
#include "mem/ruby/config/RubyConfig.hh"
-#ifdef OPTBIGSET
-#include "OptBigSet.cc"
-#else
-
-#ifdef BIGSET
-#include "BigSet.cc" // code to supports sets larger than 32
+#if __amd64__ || __LP64__
+#define __64BITS__
#else
+#define __32BITS__
+#endif
Set::Set()
{
- setSize(RubyConfig::numberOfChips());
+ m_p_nArray = NULL;
+ setSize(RubyConfig::numberOfProcessors());
+}
+
+// copy constructor
+Set::Set(const Set& obj) {
+ m_p_nArray = NULL;
+ setSize(obj.m_nSize);
+
+ // copy from the host to this array
+ for(int i=0; i<m_nArrayLen; i++) {
+ m_p_nArray[i] = obj.m_p_nArray[i];
+ }
+
}
Set::Set(int size)
{
+ m_p_nArray = NULL;
+ assert(size>0);
setSize(size);
}
-bool Set::isEqual(const Set& set)
-{
- return (m_bits == set.m_bits);
+Set::~Set() {
+ if( (m_p_nArray != (&m_p_nArray_Static[0])) && (m_p_nArray != NULL))
+ delete [] m_p_nArray;
+ m_p_nArray = NULL;
}
-void Set::add(NodeID index)
-{
- assert((m_bits & m_mask) == m_bits); // check for any bits outside the range
- assert(index < m_size);
- m_bits |= (1 << index);
- assert((m_bits & m_mask) == m_bits); // check for any bits outside the range
-}
+// /*
+// * This function should set the bit corresponding to index
+// * to 1.
+// */
+
+// void Set::add(NodeID index)
+// {
+// assert(index<m_nSize && index >= 0);
+
+// #ifdef __32BITS__
+// m_p_nArray[index>>5] |= (1 << (index & 0x01F));
+// #else
+// m_p_nArray[index>>6] |= (((unsigned long) 1) << (index & 0x03F));
+// #endif // __32BITS__
+
+// }
+
+/*
+ * This function should set all the bits in the current set
+ * that are already set in the parameter set
+ */
void Set::addSet(const Set& set)
{
- assert(m_size == set.m_size);
- m_bits |= set.m_bits;
- assert((m_bits & m_mask) == m_bits); // check for any bits outside the range
+ assert(getSize()==set.getSize());
+ for(int i=0; i<m_nArrayLen; i++) {
+ m_p_nArray[i] |= set.m_p_nArray[i];
+ }
+
}
+/*
+ * This function should randomly assign 1 to the bits in the set--
+ * it should not clear the bits bits first, though?
+ */
void Set::addRandom()
{
- m_bits |= random();
- m_bits &= m_mask;
- assert((m_bits & m_mask) == m_bits); // check for any bits outside the range
-}
-void Set::remove(NodeID index)
-{
- assert(index < m_size);
- m_bits &= ~(1 << index);
- assert((m_bits & m_mask) == m_bits); // check for any bits outside the range
+ for(int i=0; i<m_nArrayLen; i++) {
+ m_p_nArray[i] |= random() ^ (random() << 4); // this ensures that all 32 bits are subject to random effects,
+ // as RAND_MAX typically = 0x7FFFFFFF
+ }
+
+ // now just ensure that no bits over the maximum size were set
+#ifdef __32BITS__
+ long mask = 0x7FFFFFFF;
+
+ // the number of populated spaces in the higest-order array slot is:
+ // m_nSize % 32, so the uppermost 32 - m_nSize%32 bits should be
+ // cleared
+
+ if((m_nSize % 32) != 0) {
+ for(int j=0; j<32-(m_nSize&0x01F); j++) {
+ m_p_nArray[m_nArrayLen-1] &= mask;
+ mask = mask >> 1;
+ }
+ }
+#else
+ long mask = 0x7FFFFFFFFFFFFFFF;
+
+ // the number of populated spaces in the higest-order array slot is:
+ // m_nSize % 64, so the uppermost 64 - m_nSize%64 bits should be
+ // cleared
+
+ if((m_nSize % 64) != 0) {
+ for(int j=0; j<64-(m_nSize&0x03F); j++) {
+ m_p_nArray[m_nArrayLen-1] &= mask;
+ mask = mask >> 1;
+ }
+ }
+#endif // __32BITS__
+
}
+// /*
+// * This function unsets the bit associated with index
+// */
+// void Set::remove(NodeID index)
+// {
+// assert(index<m_nSize && index>=0);
+
+// #ifdef __32BITS__
+// m_p_nArray[index>>5] &= ~(0x00000001 << (index & 0x01F));
+// #else
+// m_p_nArray[index>>6] &= ~(((unsigned long) 0x0000000000000001) << (index & 0x03F));
+// #endif // __32BITS__
+
+// }
+
+
+/*
+ * This function clears bits that are =1 in the parameter set
+ */
void Set::removeSet(const Set& set)
{
- assert(m_size == set.m_size);
- m_bits &= ~(set.m_bits);
- assert((m_bits & m_mask) == m_bits); // check for any bits outside the range
-}
-void Set::clear()
-{
- m_bits = 0;
+ assert(m_nSize==set.m_nSize);
+ for(int i=0; i<m_nArrayLen; i++) {
+ m_p_nArray[i] &= ~(set.m_p_nArray[i]);
+ }
+
}
+// /*
+// * This function clears all bits in the set
+// */
+// void Set::clear()
+// {
+// for(int i=0; i<m_nArrayLen; i++) {
+// m_p_nArray[i] = 0;
+// }
+// }
+
+/*
+ * this function sets all bits in the set
+ */
void Set::broadcast()
{
- m_bits = m_mask;
+
+ for(int i=0; i<m_nArrayLen; i++) {
+ m_p_nArray[i] = -1; // note that -1 corresponds to all 1's in 2's comp.
+ }
+
+ // now just ensure that no bits over the maximum size were set
+#ifdef __32BITS__
+ long mask = 0x7FFFFFFF;
+
+ // the number of populated spaces in the higest-order array slot is:
+ // m_nSize % 32, so the uppermost 32 - m_nSize%32 bits should be
+ // cleared
+
+ if((m_nSize % 32) != 0) {
+ for(int j=0; j<32-(m_nSize&0x01F); j++) {
+ m_p_nArray[m_nArrayLen-1] &= mask;
+ mask = mask >> 1;
+ }
+ }
+#else
+ long mask = 0x7FFFFFFFFFFFFFFF;
+
+ // the number of populated spaces in the higest-order array slot is:
+ // m_nSize % 64, so the uppermost 64 - m_nSize%64 bits should be
+ // cleared
+
+ if((m_nSize % 64) != 0) {
+ for(int j=0; j<64-(m_nSize&0x03F); j++) {
+ m_p_nArray[m_nArrayLen-1] &= mask;
+ mask = mask >> 1;
+ }
+ }
+#endif // __32BITS__
+
}
+/*
+ * This function returns the population count of 1's in the set
+ */
int Set::count() const
{
int counter = 0;
- for (int i=0; i<m_size; i++) {
- if ((m_bits & (1 << i)) != 0) {
- counter++;
+ long mask;
+ for( int i=0; i<m_nArrayLen; i++) {
+ mask = (long) 0x01;
+
+#ifdef __32BITS__
+ for( int j=0; j<32; j++) {
+ if(m_p_nArray[i] & mask) counter++;
+ mask = mask << 1;
}
+
+#else
+
+ for( int j=0; j<64; j++) { // FIXME - significant performance loss when array population << 64
+ if((m_p_nArray[i] & mask) != 0) {
+ counter++;
+ }
+ mask = mask << 1;
+ }
+
+#endif // __32BITS__
+
}
+
return counter;
}
-NodeID Set::elementAt(int index) {
- // count from right to left, index starts from 0
- for (int i=0; i<m_size; i++) {
- if ((m_bits & (1 << i)) != 0) {
- if (index == 0) return i;
- index --;
+/*
+ * This function checks for set equality
+ */
+
+bool Set::isEqual(const Set& set) const
+{
+ assert(m_nSize==set.m_nSize);
+
+ for(int i=0;i<m_nArrayLen;i++) {
+ if(m_p_nArray[i] != set.m_p_nArray[i]) {
+ return false;
}
}
- assert(0); // index out of range
- return 0;
+
+ return true;
}
+/*
+ * This function returns the NodeID (int) of the
+ * least set bit
+ */
NodeID Set::smallestElement() const
{
assert(count() > 0);
- int counter = 0;
- for (int i=0; i<m_size; i++) {
- if (isElement(i)) {
- return i;
+ long x;
+ for( int i=0; i<m_nArrayLen; i++) {
+ if(m_p_nArray[i]!=0) {
+ // the least-set bit must be in here
+ x = m_p_nArray[i];
+
+#ifdef __32BITS__
+ for( int j=0; j<32; j++) {
+ if(x & 0x00000001) {
+ return 32*i+j;
+ }
+
+ x = x >> 1;
+ }
+#else
+ for( int j=0; j<64; j++) {
+ if(x & 0x0000000000000001) {
+ return 64*i+j;
+ }
+
+ x = x >> 1;
+ }
+#endif // __32BITS__
+
+ ERROR_MSG("No smallest element of an empty set.");
}
}
+
ERROR_MSG("No smallest element of an empty set.");
+
+ return 0;
}
-// Returns true iff all bits are set
+/*
+ * this function returns true iff all bits are set
+ */
bool Set::isBroadcast() const
{
- assert((m_bits & m_mask) == m_bits); // check for any bits outside the range
- return (m_mask == m_bits);
+ // check the fully-loaded words by equal to 0xffffffff
+ // only the last word may not be fully loaded, it is not
+ // fully loaded iff m_nSize % 32 or 64 !=0 => fully loaded iff
+ // m_nSize % 32 or 64 == 0
+
+#ifdef __32BITS__
+ for(int i=0; i< (((m_nSize % 32)==0) ? m_nArrayLen : m_nArrayLen-1); i++) {
+ if(m_p_nArray[i]!=-1) {
+ return false;
+ }
+ }
+
+ // now check the last word, which may not be fully loaded
+ long mask = 1;
+ for(int j=0; j< (m_nSize % 32); j++) {
+ if((mask & m_p_nArray[m_nArrayLen-1])==0) {
+ return false;
+ }
+ mask = mask << 1;
+ }
+#else
+ for(int i=0; i< (((m_nSize % 64)==0) ? m_nArrayLen : m_nArrayLen-1); i++) {
+ if(m_p_nArray[i]!=-1) {
+ return false;
+ }
+ }
+
+ // now check the last word, which may not be fully loaded
+ long mask = 1;
+ for(int j=0; j< (m_nSize % 64); j++) {
+ if((mask & m_p_nArray[m_nArrayLen-1])==0) {
+ return false;
+ }
+ mask = mask << 1;
+ }
+
+#endif // __32BITS__
+
+ return true;
}
-// Returns true iff no bits are set
+/*
+ * this function returns true iff no bits are set
+ */
bool Set::isEmpty() const
{
- assert((m_bits & m_mask) == m_bits); // check for any bits outside the range
- return (m_bits == 0);
+
+ // here we can simply check if all = 0, since we ensure
+ // that "extra slots" are all zero
+ for(int i=0; i< m_nArrayLen ; i++) {
+ if(m_p_nArray[i]!=0) {
+ return false;
+ }
+ }
+
+ return true;
}
// returns the logical OR of "this" set and orSet
Set Set::OR(const Set& orSet) const
{
- assert(m_size == orSet.m_size);
- Set result(m_size);
- result.m_bits = (m_bits | orSet.m_bits);
- assert((result.m_bits & result.m_mask) == result.m_bits); // check for any bits outside the range
+ Set result(m_nSize);
+ assert(m_nSize == orSet.m_nSize);
+ for(int i=0; i< m_nArrayLen; i++) {
+ result.m_p_nArray[i] = m_p_nArray[i] | orSet.m_p_nArray[i];
+ }
+
return result;
+
}
// returns the logical AND of "this" set and andSet
Set Set::AND(const Set& andSet) const
{
- assert(m_size == andSet.m_size);
- Set result(m_size);
- result.m_bits = (m_bits & andSet.m_bits);
- assert((result.m_bits & result.m_mask) == result.m_bits); // check for any bits outside the range
+ Set result(m_nSize);
+ assert(m_nSize == andSet.m_nSize);
+
+ for(int i=0; i< m_nArrayLen; i++) {
+ result.m_p_nArray[i] = m_p_nArray[i] & andSet.m_p_nArray[i];
+ }
+
return result;
}
-// Returns true if the intersection of the two sets is non-empty
-bool Set::intersectionIsNotEmpty(const Set& other_set) const
-{
- assert(m_size == other_set.m_size);
- return ((m_bits & other_set.m_bits) != 0);
-}
+// // Returns true if the intersection of the two sets is non-empty
+// bool Set::intersectionIsNotEmpty(const Set& other_set) const
+// {
+// assert(m_nSize == other_set.m_nSize);
+// for(int i=0; i< m_nArrayLen; i++) {
+// if(m_p_nArray[i] & other_set.m_p_nArray[i]) {
+// return true;
+// }
+// }
-// Returns true if the intersection of the two sets is empty
-bool Set::intersectionIsEmpty(const Set& other_set) const
-{
- assert(m_size == other_set.m_size);
- return ((m_bits & other_set.m_bits) == 0);
-}
+// return false;
+
+// }
+
+// // Returns true if the intersection of the two sets is empty
+// bool Set::intersectionIsEmpty(const Set& other_set) const
+// {
+// assert(m_nSize == other_set.m_nSize);
+// for(int i=0; i< m_nArrayLen; i++) {
+// if(m_p_nArray[i] & other_set.m_p_nArray[i]) {
+// return false;
+// }
+// }
+
+// return true;
+
+// }
+/*
+ * Returns false if a bit is set in the parameter set that is
+ * NOT set in this set
+ */
bool Set::isSuperset(const Set& test) const
{
- assert(m_size == test.m_size);
- uint32 temp = (test.m_bits & (~m_bits));
- return (temp == 0);
-}
+ assert(m_nSize == test.m_nSize);
-bool Set::isElement(NodeID element) const
-{
- return ((m_bits & (1 << element)) != 0);
+ for(int i=0;i<m_nArrayLen;i++) {
+ if(((test.m_p_nArray[i] & m_p_nArray[i]) | ~test.m_p_nArray[i]) != -1) {
+ return false;
+ }
+ }
+
+ return true;
}
+// /*
+// * Returns true iff this bit is set
+// */
+// bool Set::isElement(NodeID element) const
+// {
+// bool result;
+
+// #ifdef __32BITS__
+// result = ((m_p_nArray[element>>5] & (0x00000001 << (element & 0x01F)))!=0);
+// #else
+// result = ((m_p_nArray[element>>6] & (((unsigned long) 0x0000000000000001) << (element & 0x03F)))!=0);
+// #endif // __32BITS__
+
+// return result;
+// }
+
+/*
+ * "Supposed" to return the node id of the (n+1)th set
+ * bit, IE n=0 => returns nodeid of first set bit, BUT
+ * since BigSet.C behaves strangely, this implementation
+ * will behave strangely just for reverse compatability.
+ *
+ * Was originally implemented for the flight data recorder
+ * FDR
+ */
+
+// NodeID Set::elementAt(int n) const
+// {
+// if(isElement(n)) return (NodeID) true;
+// else return 0;
+
+// /*
+// int match = -1;
+// for(int i=0;i<m_nSize;i++) {
+// if(isElement(i)) match++;
+// if(match==n) {
+// return i;
+// }
+// }
+
+// return -1;
+// */
+// }
+
void Set::setSize(int size)
{
- // We're using 32 bit ints, and the 32nd bit acts strangely due to
- // signed/unsigned, so restrict the set size to 31 bits.
- assert(size < 32);
- m_size = size;
- m_bits = 0;
- m_mask = ~((~0) << m_size);
- assert(m_mask != 0);
- assert((m_bits & m_mask) == m_bits); // check for any bits outside the range
+ m_nSize = size;
+
+#ifdef __32BITS__
+ m_nArrayLen = m_nSize/32 + ((m_nSize%32==0) ? 0 : 1 );
+#else
+ m_nArrayLen = m_nSize/64 + ((m_nSize%64==0) ? 0 : 1 );
+#endif // __32BITS__
+
+ // decide whether to use dynamic or static alloction
+ if(m_nArrayLen<=NUMBER_WORDS_PER_SET) { // constant defined in RubyConfig.h
+ // its OK to use the static allocation, and it will
+ // probably be faster (as m_nArrayLen is already in the
+ // cache and they will probably share the same cache line)
+
+ // if switching from dyanamic to static allocation (which
+ // is probably rare, but why not be complete?), must delete
+ // the dynamically allocated space
+ if((m_p_nArray != NULL) && (m_p_nArray != &m_p_nArray_Static[0]))
+ delete [] m_p_nArray;
+
+ m_p_nArray = & m_p_nArray_Static[0];
+ } else {
+
+ // can't use static allocation...simply not enough room
+ // so dynamically allocate some space
+ if((m_p_nArray != NULL) && (m_p_nArray != &m_p_nArray_Static[0]))
+ delete [] m_p_nArray;
+
+ m_p_nArray = new long[m_nArrayLen];
+ }
+
+ clear();
}
-void Set::print(ostream& out) const
-{
- out << "[Set (" << m_size << ") ";
+Set& Set::operator=(const Set& obj) {
+ if(this == &obj) {
+ // do nothing
+ } else {
+
+ // resize this item
+ setSize(obj.getSize());
- for (int i=0; i<m_size; i++) {
- out << (bool) isElement(i) << " ";
+ // copy the elements from obj to this
+ for(int i=0; i<m_nArrayLen; i++) {
+ m_p_nArray[i] = obj.m_p_nArray[i];
+ }
}
- out << "]";
+
+ return *this;
}
-#endif // BIGSET
+void Set::print(ostream& out) const
+{
+ if(m_p_nArray==NULL) {
+ out << "[Set {Empty}]";
+ return;
+ }
+ char buff[24];
+ out << "[Set 0x ";
+ for (int i=m_nArrayLen-1; i>=0; i--) {
+#ifdef __32BITS__
+ sprintf(buff,"%08X ",m_p_nArray[i]);
+#else
+ sprintf(buff,"0x %016llX ",m_p_nArray[i]);
+#endif // __32BITS__
+ out << buff;
+ }
+ out << " ]";
+
+}
-#endif // OPTBIGSET
generated by cgit v1.2.3 (git 2.25.1) at 2025-01-26 17:39:54 +0000