diff options
Diffstat (limited to 'src/mem/ruby/common/OptBigSet.cc')
| -rw-r--r-- | src/mem/ruby/common/OptBigSet.cc | 576 |
1 files changed, 576 insertions, 0 deletions
diff --git a/src/mem/ruby/common/OptBigSet.cc b/src/mem/ruby/common/OptBigSet.cc new file mode 100644 index 000000000..51214e936 --- /dev/null +++ b/src/mem/ruby/common/OptBigSet.cc @@ -0,0 +1,576 @@ + +/* + * Copyright (c) 1999-2008 Mark D. Hill and David A. Wood + * All rights reserved. + * + * Redistribution and use in source and binary forms, with or without + * modification, are permitted provided that the following conditions are + * met: redistributions of source code must retain the above copyright + * notice, this list of conditions and the following disclaimer; + * redistributions in binary form must reproduce the above copyright + * notice, this list of conditions and the following disclaimer in the + * documentation and/or other materials provided with the distribution; + * neither the name of the copyright holders nor the names of its + * contributors may be used to endorse or promote products derived from + * this software without specific prior written permission. + * + * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS + * "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT + * LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR + * A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT + * OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, + * SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT + * LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, + * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY + * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT + * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE + * OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. + */ + +/* + * Set.C + * + * Description: See Set.h + * + * $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 "Set.hh" +#include "RubyConfig.hh" + +#if __amd64__ || __LP64__ +#define __64BITS__ +#else +#define __32BITS__ +#endif + +Set::Set() +{ + 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); +} + +Set::~Set() { + if( (m_p_nArray != (&m_p_nArray_Static[0])) && (m_p_nArray != NULL)) + delete [] m_p_nArray; + m_p_nArray = NULL; +} + + +// /* +// * 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(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() +{ + + 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_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() +{ + + 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; + 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; +} + +/* + * 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; + } + } + + return true; +} + +/* + * This function returns the NodeID (int) of the + * least set bit + */ +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; + } + + 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; +} + +/* + * this function returns true iff all bits are set + */ +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; + } + } + + // 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; +} + +/* + * this function returns true iff no bits are set + */ +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) { + return false; + } + } + + return true; +} + +// returns the logical OR of "this" set and orSet +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; + +} + +// returns the logical AND of "this" set and andSet +Set Set::AND(const Set& andSet) const +{ + 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_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 + */ +bool Set::isSuperset(const Set& test) const +{ + 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; + } + } + + 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) +{ + 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(); +} + +Set& Set::operator=(const Set& obj) { + if(this == &obj) { + // do nothing + } else { + + // 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]; + } + } + + return *this; +} + +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 << " ]"; + +} + + |