diff options
Diffstat (limited to 'src/mem/ruby/common/BigSet.cc')
-rw-r--r-- | src/mem/ruby/common/BigSet.cc | 249 |
1 files changed, 249 insertions, 0 deletions
diff --git a/src/mem/ruby/common/BigSet.cc b/src/mem/ruby/common/BigSet.cc new file mode 100644 index 000000000..e16284f15 --- /dev/null +++ b/src/mem/ruby/common/BigSet.cc @@ -0,0 +1,249 @@ + +/* + * 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. + */ + +#include "Set.hh" +#include "RubyConfig.hh" + +Set::Set() +{ + setSize(RubyConfig::numberOfProcessors()); +} + +Set::Set(int size) +{ + setSize(size); +} + +void Set::add(NodeID index) +{ + m_bits[index] = Present; +} + +void Set::addSet(const Set& set) +{ + assert(m_bits.size() == set.getSize()); + for (int i=0; i<m_bits.size(); i++) { + if(set.isElement(i)){ + add(i); + } + } +} + +void Set::addRandom() +{ + int rand = random(); + for (int i=0; i<m_bits.size(); i++) { + if(rand & 0x1 == 0) { // Look at the low order bit + add(i); + } + rand = (rand >> 1); // Shift the random number to look at the next bit + } +} + +void Set::remove(NodeID index) +{ + m_bits[index] = NotPresent; +} + +void Set::removeSet(const Set& set) +{ + assert(m_bits.size() == set.getSize()); + for (int i=0; i<m_bits.size(); i++) { + if(set.isElement(i)){ + remove(i); + } + } +} + +void Set::clear() +{ + for (int i=0; i<m_bits.size(); i++) { + m_bits[i] = NotPresent; + } +} + +void Set::broadcast() +{ + for (int i=0; i<m_bits.size(); i++) { + m_bits[i] = Present; + } +} + +int Set::count() const +{ + int counter = 0; + for (int i=0; i<m_bits.size(); i++) { + if (m_bits[i] == Present) { + counter++; + } + } + return counter; +} + +bool Set::isEqual(const Set& set) const +{ + assert(m_bits.size() == set.getSize()); + for (int i=0; i<m_bits.size(); i++) { + if (m_bits[i] != set.isElement(i)) { + return false; + } + } + return true; +} + +NodeID Set::smallestElement() const +{ + assert(count() > 0); + for (int i=0; i<m_bits.size(); i++) { + if (isElement(i)) { + return i; + } + } + ERROR_MSG("No smallest element of an empty set."); +} + +// Returns true iff all bits are set +bool Set::isBroadcast() const +{ + for (int i=0; i<m_bits.size(); i++) { + if (m_bits[i] == NotPresent) { + return false; + } + } + return true; +} + +// Returns true iff no bits are set +bool Set::isEmpty() const +{ + for (int i=0; i<m_bits.size(); i++) { + if (m_bits[i] == Present) { + return false; + } + } + return true; +} + +// returns the logical OR of "this" set and orSet +Set Set::OR(const Set& orSet) const +{ + Set result; + assert(m_bits.size() == orSet.getSize()); + result.setSize(m_bits.size()); + for (int i=0; i<m_bits.size(); i++) { + if(m_bits[i] == Present || orSet.isElement(i)){ + result.add(i); + }else{ + result.remove(i); + } + } + + return result; + +} + +// returns the logical AND of "this" set and andSet +Set Set::AND(const Set& andSet) const +{ + Set result; + assert(m_bits.size() == andSet.getSize()); + result.setSize(m_bits.size()); + for (int i=0; i<m_bits.size(); i++) { + if(m_bits[i] == Present && andSet.isElement(i)){ + result.add(i); + }else{ + result.remove(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_bits.size() == other_set.getSize()); + for(int index=0; index < m_bits.size(); index++){ + if(other_set.isElement(index) && isElement(index)) { + return true; + } + } + return false; +} + +// Returns true if the intersection of the two sets is non-empty +bool Set::intersectionIsEmpty(const Set& other_set) const +{ + assert(m_bits.size() == other_set.getSize()); + for(int index=0; index < m_bits.size(); index++){ + if(other_set.isElement(index) && isElement(index)) { + return false; + } + } + return true; +} + +bool Set::isSuperset(const Set& test) const +{ + assert(m_bits.size() == test.getSize()); + for(int index=0; index < m_bits.size(); index++){ + if(test.isElement(index) && !isElement(index)) { + return false; + } + } + return true; +} + +bool Set::isElement(NodeID element) const +{ + return (m_bits[element] == Present); +} + +NodeID Set::elementAt(int index) const +{ + if (m_bits[index] == Present) { + return m_bits[index] == Present; + } else { + return 0; + } +} + +void Set::setSize(int size) +{ + m_bits.setSize(size); + clear(); +} + +void Set::print(ostream& out) const +{ + out << "[Set "; + for (int i=0; i<m_bits.size(); i++) { + out << (bool)m_bits[i] << " "; + } + out << "]"; +} |