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.cc651
1 files changed, 218 insertions, 433 deletions
diff --git a/src/mem/ruby/common/Set.cc b/src/mem/ruby/common/Set.cc
index a9ced0078..c946fec16 100644
--- a/src/mem/ruby/common/Set.cc
+++ b/src/mem/ruby/common/Set.cc
@@ -1,4 +1,3 @@
-
/*
* Copyright (c) 1999-2008 Mark D. Hill and David A. Wood
* All rights reserved.
@@ -27,554 +26,340 @@
* OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
*/
-/*
- * Set.cc
- *
- * Description: See Set.hh
- *
- * $Id: BigSet.cc 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
+// modified (rewritten) 05/20/05 by Dan Gibson to accomimdate FASTER
+// >32 bit set sizes
#include "mem/ruby/common/Set.hh"
#include "mem/ruby/system/System.hh"
-#if __amd64__ || __LP64__
-#define __64BITS__
-#else
-#define __32BITS__
-#endif
-
Set::Set()
{
- m_p_nArray = NULL;
- m_nArrayLen = 0;
- m_nSize = 0;
+ m_p_nArray = NULL;
+ m_nArrayLen = 0;
+ m_nSize = 0;
}
-// 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(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;
- m_nArrayLen = 0;
- m_nSize = 0;
- if(size > 0) {
- setSize(size);
- }
+ m_p_nArray = NULL;
+ m_nArrayLen = 0;
+ m_nSize = 0;
+ if (size > 0)
+ setSize(size);
}
-Set::~Set() {
- if( (m_p_nArray != (&m_p_nArray_Static[0])) && (m_p_nArray != NULL))
- delete [] m_p_nArray;
- m_p_nArray = NULL;
+Set::~Set()
+{
+ if (m_p_nArray && m_p_nArray != &m_p_nArray_Static[0])
+ delete [] m_p_nArray;
+ m_p_nArray = NULL;
}
+void
+Set::clearExcess()
+{
+ // now just ensure that no bits over the maximum size were set
+#ifdef _LP64
+ long mask = 0x7FFFFFFFFFFFFFFF;
+#else
+ long mask = 0x7FFFFFFF;
+#endif
-// /*
-// * 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__
+ // the number of populated spaces in the higest-order array slot
+ // is: m_nSize % LONG_BITS, so the uppermost LONG_BITS -
+ // m_nSize%64 bits should be cleared
+ if ((m_nSize % LONG_BITS) != 0) {
+ for (int j = 0; j < 64 - (m_nSize & INDEX_MASK); j++) {
+ m_p_nArray[m_nArrayLen - 1] &= mask;
+ mask = mask >> 1;
+ }
+ }
+}
-// }
/*
- * This function should set all the bits in the current set
- * that are already set in the parameter set
+ * 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)
+void
+Set::addSet(const Set& set)
{
- assert(getSize()==set.getSize());
- for(int i=0; i<m_nArrayLen; i++) {
- m_p_nArray[i] |= set.m_p_nArray[i];
- }
-
+ 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?
+ * This function should randomly assign 1 to the bits in the set--it
+ * should not clear the bits bits first, though?
*/
-void Set::addRandom()
+void
+Set::addRandom()
{
- 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;
+ for (int i = 0; i < m_nArrayLen; i++) {
+ // this ensures that all 32 bits are subject to random effects,
+ // as RAND_MAX typically = 0x7FFFFFFF
+ m_p_nArray[i] |= random() ^ (random() << 4);
}
- }
-#endif // __32BITS__
-
+ clearExcess();
}
-// /*
-// * 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)
+void
+Set::removeSet(const Set& set)
{
-
- assert(m_nSize==set.m_nSize);
- for(int i=0; i<m_nArrayLen; i++) {
- m_p_nArray[i] &= ~(set.m_p_nArray[i]);
- }
-
+ 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()
+void
+Set::broadcast()
{
+ 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.
- 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__
-
+ clearExcess();
}
/*
* This function returns the population count of 1's in the set
*/
-int Set::count() const
+int
+Set::count() const
{
- int counter = 0;
- 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;
+ int counter = 0;
+ long mask;
+
+ for (int i = 0; i < m_nArrayLen; i++) {
+ mask = (long)0x01;
+
+ for (int j = 0; j < LONG_BITS; j++) {
+ // FIXME - significant performance loss when array
+ // population << LONG_BITS
+ if ((m_p_nArray[i] & mask) != 0) {
+ counter++;
+ }
+ mask = mask << 1;
+ }
}
-#endif // __32BITS__
-
- }
-
- return counter;
+ return counter;
}
/*
* This function checks for set equality
*/
-
-bool Set::isEqual(const Set& set) const
+bool
+Set::isEqual(const Set& set) const
{
- assert(m_nSize==set.m_nSize);
+ 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;
- }
- }
+ for (int i = 0; i < m_nArrayLen; i++)
+ if (m_p_nArray[i] != set.m_p_nArray[i])
+ return false;
- return true;
+ return true;
}
/*
- * This function returns the NodeID (int) of the
- * least set bit
+ * This function returns the NodeID (int) of the least set bit
*/
-NodeID Set::smallestElement() const
+NodeID
+Set::smallestElement() const
{
- assert(count() > 0);
- 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;
+ assert(count() > 0);
+ 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];
+
+ for (int j = 0; j < LONG_BITS; j++) {
+ if (x & (unsigned long)1) {
+ return LONG_BITS * i + j;
+ }
+
+ x = x >> 1;
+ }
+
+ ERROR_MSG("No smallest element of an empty set.");
}
-
- 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.");
+ ERROR_MSG("No smallest element of an empty set.");
- return 0;
+ return 0;
}
/*
* this function returns true iff all bits are set
*/
-bool Set::isBroadcast() const
+bool
+Set::isBroadcast() const
{
- // 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;
+ // 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
+
+ int max = (m_nSize % LONG_BITS) == 0 ? m_nArrayLen : m_nArrayLen - 1;
+ for (int i = 0; i < max; 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;
+ // now check the last word, which may not be fully loaded
+ long mask = 1;
+ for (int j = 0; j < (m_nSize % LONG_BITS); j++) {
+ if ((mask & m_p_nArray[m_nArrayLen-1]) == 0) {
+ return false;
+ }
+ mask = mask << 1;
}
- mask = mask << 1;
- }
-#endif // __32BITS__
-
- return true;
+ return true;
}
/*
* this function returns true iff no bits are set
*/
-bool Set::isEmpty() const
+bool
+Set::isEmpty() const
{
-
- // 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) {
+ // 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])
return false;
- }
- }
- return true;
+ return true;
}
// returns the logical OR of "this" set and orSet
-Set Set::OR(const Set& orSet) const
+Set
+Set::OR(const Set& orSet) const
{
- 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;
+ 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
+Set
+Set::AND(const Set& andSet) const
{
- Set result(m_nSize);
- assert(m_nSize == andSet.m_nSize);
+ 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];
- }
+ for (int i = 0; i < m_nArrayLen; i++) {
+ result.m_p_nArray[i] = m_p_nArray[i] & andSet.m_p_nArray[i];
+ }
- return result;
+ return result;
}
-// // 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;
-// }
-// }
-
-// 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
+ * 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
+bool
+Set::isSuperset(const Set& test) const
{
- assert(m_nSize == test.m_nSize);
+ assert(m_nSize == test.m_nSize);
- 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;
- }
- }
+ 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;
+ 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.cc 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)
+void
+Set::setSize(int size)
{
- 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 RubySystem.hh
- // 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];
- }
+ m_nSize = size;
+
+ m_nArrayLen = m_nSize / LONG_BITS + ((m_nSize % LONG_BITS == 0) ? 0 : 1 );
+
+ // decide whether to use dynamic or static alloction
+ if (m_nArrayLen <= NUMBER_WORDS_PER_SET) {
+ // constant defined in RubySystem.hh
+ // 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 && 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 && m_p_nArray != &m_p_nArray_Static[0])
+ delete [] m_p_nArray;
+
+ m_p_nArray = new long[m_nArrayLen];
+ }
- clear();
+ clear();
}
-Set& Set::operator=(const Set& obj) {
- if(this == &obj) {
- // do nothing
- } else {
-
- // resize this item
- setSize(obj.getSize());
+Set&
+Set::operator=(const Set& obj)
+{
+ if (this != &obj) {
+ // resize this item
+ setSize(obj.getSize());
- // copy the elements from obj to this
- for(int i=0; i<m_nArrayLen; i++) {
- m_p_nArray[i] = obj.m_p_nArray[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];
}
- }
- return *this;
+ return *this;
}
-void Set::print(std::ostream& out) const
+void
+Set::print(std::ostream& out) const
{
- if(m_p_nArray==NULL) {
- out << "[Set {Empty}]";
- return;
- }
- char buff[24];
- out << "[Set (" << m_nSize << ") 0x ";
- for (int i=m_nArrayLen-1; i>=0; i--) {
-#ifdef __32BITS__
- sprintf(buff,"%08X ",m_p_nArray[i]);
+ if (!m_p_nArray) {
+ out << "[Set {Empty}]";
+ return;
+ }
+
+ char buff[24];
+ out << "[Set (" << m_nSize << ") 0x ";
+ for (int i = m_nArrayLen - 1; i >= 0; i--) {
+#ifdef _LP64
+ sprintf(buff,"0x %016llX ", (long long)m_p_nArray[i]);
#else
- sprintf(buff,"0x %016llX ", (long long)m_p_nArray[i]);
+ sprintf(buff,"%08X ", m_p_nArray[i]);
#endif // __32BITS__
- out << buff;
- }
- out << " ]";
-
+ out << buff;
+ }
+ out << " ]";
}
-
-