16145Snate@binkert.org/* 26145Snate@binkert.org * Copyright (c) 1999-2008 Mark D. Hill and David A. Wood 36145Snate@binkert.org * All rights reserved. 46145Snate@binkert.org * 56145Snate@binkert.org * Redistribution and use in source and binary forms, with or without 66145Snate@binkert.org * modification, are permitted provided that the following conditions are 76145Snate@binkert.org * met: redistributions of source code must retain the above copyright 86145Snate@binkert.org * notice, this list of conditions and the following disclaimer; 96145Snate@binkert.org * redistributions in binary form must reproduce the above copyright 106145Snate@binkert.org * notice, this list of conditions and the following disclaimer in the 116145Snate@binkert.org * documentation and/or other materials provided with the distribution; 126145Snate@binkert.org * neither the name of the copyright holders nor the names of its 136145Snate@binkert.org * contributors may be used to endorse or promote products derived from 146145Snate@binkert.org * this software without specific prior written permission. 156145Snate@binkert.org * 166145Snate@binkert.org * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS 176145Snate@binkert.org * "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT 186145Snate@binkert.org * LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR 196145Snate@binkert.org * A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT 206145Snate@binkert.org * OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, 216145Snate@binkert.org * SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT 226145Snate@binkert.org * LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, 236145Snate@binkert.org * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY 246145Snate@binkert.org * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT 256145Snate@binkert.org * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE 266145Snate@binkert.org * OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. 276145Snate@binkert.org */ 286145Snate@binkert.org 296163Spdudnik@gmail.com// modified by Dan Gibson on 05/20/05 to accomidate FASTER 306163Spdudnik@gmail.com// >32 set lengths, using an array of ints w/ 32 bits/int 316145Snate@binkert.org 327089Snate@binkert.org#ifndef __MEM_RUBY_COMMON_SET_HH__ 337089Snate@binkert.org#define __MEM_RUBY_COMMON_SET_HH__ 346145Snate@binkert.org 3511085Snilay@cs.wisc.edu#include <bitset> 3611085Snilay@cs.wisc.edu#include <cassert> 377055Snate@binkert.org#include <iostream> 387055Snate@binkert.org 3912334Sgabeblack@google.com#include "base/logging.hh" 408650Snilay@cs.wisc.edu#include "mem/ruby/common/TypeDefines.hh" 418650Snilay@cs.wisc.edu 427089Snate@binkert.orgclass Set 437089Snate@binkert.org{ 447089Snate@binkert.org private: 4511085Snilay@cs.wisc.edu // Number of bits in use in this set. 4614037Sjohnathan.alsop@amd.com // can be defined in build_opts file (default=64). 4711085Snilay@cs.wisc.edu int m_nSize; 4811085Snilay@cs.wisc.edu std::bitset<NUMBER_BITS_PER_SET> bits; 496145Snate@binkert.org 507089Snate@binkert.org public: 5111085Snilay@cs.wisc.edu Set() : m_nSize(0) {} 526145Snate@binkert.org 5311085Snilay@cs.wisc.edu Set(int size) : m_nSize(size) 5411085Snilay@cs.wisc.edu { 5511085Snilay@cs.wisc.edu if (size > NUMBER_BITS_PER_SET) 5611085Snilay@cs.wisc.edu fatal("Number of bits(%d) < size specified(%d). " 5711085Snilay@cs.wisc.edu "Increase the number of bits and recompile.\n", 5811085Snilay@cs.wisc.edu NUMBER_BITS_PER_SET, size); 5911085Snilay@cs.wisc.edu } 6011085Snilay@cs.wisc.edu 6111085Snilay@cs.wisc.edu Set(const Set& obj) : m_nSize(obj.m_nSize), bits(obj.bits) {} 6211085Snilay@cs.wisc.edu ~Set() {} 6311085Snilay@cs.wisc.edu 6411085Snilay@cs.wisc.edu Set& operator=(const Set& obj) 6511085Snilay@cs.wisc.edu { 6611085Snilay@cs.wisc.edu m_nSize = obj.m_nSize; 6711085Snilay@cs.wisc.edu bits = obj.bits; 6811085Snilay@cs.wisc.edu return *this; 6911085Snilay@cs.wisc.edu } 707089Snate@binkert.org 717089Snate@binkert.org void 727089Snate@binkert.org add(NodeID index) 736163Spdudnik@gmail.com { 7411085Snilay@cs.wisc.edu bits.set(index); 756163Spdudnik@gmail.com } 766163Spdudnik@gmail.com 7711085Snilay@cs.wisc.edu /* 7811085Snilay@cs.wisc.edu * This function should set all the bits in the current set that are 7911085Snilay@cs.wisc.edu * already set in the parameter set 8011085Snilay@cs.wisc.edu */ 8111085Snilay@cs.wisc.edu void 8211085Snilay@cs.wisc.edu addSet(const Set& obj) 8311085Snilay@cs.wisc.edu { 8411085Snilay@cs.wisc.edu assert(m_nSize == obj.m_nSize); 8511085Snilay@cs.wisc.edu bits |= obj.bits; 8611085Snilay@cs.wisc.edu } 876163Spdudnik@gmail.com 8811085Snilay@cs.wisc.edu /* 8911085Snilay@cs.wisc.edu * This function clears bits that are =1 in the parameter set 9011085Snilay@cs.wisc.edu */ 917089Snate@binkert.org void 927089Snate@binkert.org remove(NodeID index) 936163Spdudnik@gmail.com { 9411085Snilay@cs.wisc.edu bits.reset(index); 956163Spdudnik@gmail.com } 966163Spdudnik@gmail.com 9711085Snilay@cs.wisc.edu /* 9811085Snilay@cs.wisc.edu * This function clears bits that are =1 in the parameter set 9911085Snilay@cs.wisc.edu */ 1007089Snate@binkert.org void 10111085Snilay@cs.wisc.edu removeSet(const Set& obj) 1026163Spdudnik@gmail.com { 10311085Snilay@cs.wisc.edu assert(m_nSize == obj.m_nSize); 10411085Snilay@cs.wisc.edu bits &= (~obj.bits); 1056163Spdudnik@gmail.com } 1066145Snate@binkert.org 10711085Snilay@cs.wisc.edu void clear() { bits.reset(); } 10811085Snilay@cs.wisc.edu 10911085Snilay@cs.wisc.edu /* 11011085Snilay@cs.wisc.edu * this function sets all bits in the set 11111085Snilay@cs.wisc.edu */ 11211085Snilay@cs.wisc.edu void broadcast() 11311085Snilay@cs.wisc.edu { 11411085Snilay@cs.wisc.edu bits.set(); 11511085Snilay@cs.wisc.edu for (int j = m_nSize; j < NUMBER_BITS_PER_SET; ++j) { 11611085Snilay@cs.wisc.edu bits.reset(j); 11711085Snilay@cs.wisc.edu } 11811085Snilay@cs.wisc.edu } 11911085Snilay@cs.wisc.edu 12011085Snilay@cs.wisc.edu /* 12111085Snilay@cs.wisc.edu * This function returns the population count of 1's in the set 12211085Snilay@cs.wisc.edu */ 12311085Snilay@cs.wisc.edu int count() const { return bits.count(); } 12411085Snilay@cs.wisc.edu 12511085Snilay@cs.wisc.edu /* 12611085Snilay@cs.wisc.edu * This function checks for set equality 12711085Snilay@cs.wisc.edu */ 12811085Snilay@cs.wisc.edu bool 12911085Snilay@cs.wisc.edu isEqual(const Set& obj) const 13011085Snilay@cs.wisc.edu { 13111085Snilay@cs.wisc.edu assert(m_nSize == obj.m_nSize); 13211085Snilay@cs.wisc.edu return bits == obj.bits; 13311085Snilay@cs.wisc.edu } 1347089Snate@binkert.org 1357089Snate@binkert.org // return the logical OR of this set and orSet 13611085Snilay@cs.wisc.edu Set 13711085Snilay@cs.wisc.edu OR(const Set& obj) const 13811085Snilay@cs.wisc.edu { 13911085Snilay@cs.wisc.edu assert(m_nSize == obj.m_nSize); 14011085Snilay@cs.wisc.edu Set r(m_nSize); 14111085Snilay@cs.wisc.edu r.bits = bits | obj.bits; 14211085Snilay@cs.wisc.edu return r; 14311085Snilay@cs.wisc.edu }; 1447089Snate@binkert.org 1457089Snate@binkert.org // return the logical AND of this set and andSet 14611085Snilay@cs.wisc.edu Set 14711085Snilay@cs.wisc.edu AND(const Set& obj) const 14811085Snilay@cs.wisc.edu { 14911085Snilay@cs.wisc.edu assert(m_nSize == obj.m_nSize); 15011085Snilay@cs.wisc.edu Set r(m_nSize); 15111085Snilay@cs.wisc.edu r.bits = bits & obj.bits; 15211085Snilay@cs.wisc.edu return r; 15311085Snilay@cs.wisc.edu } 1547089Snate@binkert.org 1557089Snate@binkert.org // Returns true if the intersection of the two sets is empty 1567089Snate@binkert.org bool 15711085Snilay@cs.wisc.edu intersectionIsEmpty(const Set& obj) const 1586163Spdudnik@gmail.com { 15911085Snilay@cs.wisc.edu std::bitset<NUMBER_BITS_PER_SET> r = bits & obj.bits; 16011085Snilay@cs.wisc.edu return r.none(); 1616163Spdudnik@gmail.com } 1626145Snate@binkert.org 16311085Snilay@cs.wisc.edu /* 16411085Snilay@cs.wisc.edu * Returns false if a bit is set in the parameter set that is NOT set 16511085Snilay@cs.wisc.edu * in this set 16611085Snilay@cs.wisc.edu */ 16711085Snilay@cs.wisc.edu bool 16811085Snilay@cs.wisc.edu isSuperset(const Set& test) const 16911085Snilay@cs.wisc.edu { 17011085Snilay@cs.wisc.edu assert(m_nSize == test.m_nSize); 17111085Snilay@cs.wisc.edu std::bitset<NUMBER_BITS_PER_SET> r = bits | test.bits; 17211085Snilay@cs.wisc.edu return (r == bits); 17311085Snilay@cs.wisc.edu } 17411085Snilay@cs.wisc.edu 1757089Snate@binkert.org bool isSubset(const Set& test) const { return test.isSuperset(*this); } 1766163Spdudnik@gmail.com 17711085Snilay@cs.wisc.edu bool isElement(NodeID element) const { return bits.test(element); } 17811085Snilay@cs.wisc.edu 17911085Snilay@cs.wisc.edu /* 18011085Snilay@cs.wisc.edu * this function returns true iff all bits in use are set 18111085Snilay@cs.wisc.edu */ 1827089Snate@binkert.org bool 18311085Snilay@cs.wisc.edu isBroadcast() const 1846163Spdudnik@gmail.com { 18511085Snilay@cs.wisc.edu return (bits.count() == m_nSize); 1866163Spdudnik@gmail.com } 1876163Spdudnik@gmail.com 18811085Snilay@cs.wisc.edu bool isEmpty() const { return bits.none(); } 1896145Snate@binkert.org 19011085Snilay@cs.wisc.edu NodeID smallestElement() const 19111085Snilay@cs.wisc.edu { 19211085Snilay@cs.wisc.edu for (int i = 0; i < m_nSize; ++i) { 19311085Snilay@cs.wisc.edu if (bits.test(i)) { 19411085Snilay@cs.wisc.edu return i; 19511085Snilay@cs.wisc.edu } 19611085Snilay@cs.wisc.edu } 19711085Snilay@cs.wisc.edu panic("No smallest element of an empty set."); 19811085Snilay@cs.wisc.edu } 1996145Snate@binkert.org 20011085Snilay@cs.wisc.edu bool elementAt(int index) const { return bits[index]; } 2016163Spdudnik@gmail.com 2027089Snate@binkert.org int getSize() const { return m_nSize; } 2036145Snate@binkert.org 20411085Snilay@cs.wisc.edu void 20511085Snilay@cs.wisc.edu setSize(int size) 20611085Snilay@cs.wisc.edu { 20711085Snilay@cs.wisc.edu if (size > NUMBER_BITS_PER_SET) 20811085Snilay@cs.wisc.edu fatal("Number of bits(%d) < size specified(%d). " 20911085Snilay@cs.wisc.edu "Increase the number of bits and recompile.\n", 21011085Snilay@cs.wisc.edu NUMBER_BITS_PER_SET, size); 21111085Snilay@cs.wisc.edu m_nSize = size; 21211085Snilay@cs.wisc.edu bits.reset(); 21311085Snilay@cs.wisc.edu } 21411085Snilay@cs.wisc.edu 21511085Snilay@cs.wisc.edu void print(std::ostream& out) const 21611085Snilay@cs.wisc.edu { 21711085Snilay@cs.wisc.edu out << "[Set (" << m_nSize << "): " << bits << "]"; 21811085Snilay@cs.wisc.edu } 2196145Snate@binkert.org}; 2206145Snate@binkert.org 2217089Snate@binkert.orginline std::ostream& 2227089Snate@binkert.orgoperator<<(std::ostream& out, const Set& obj) 2236145Snate@binkert.org{ 2247089Snate@binkert.org obj.print(out); 2257089Snate@binkert.org out << std::flush; 2267089Snate@binkert.org return out; 2276145Snate@binkert.org} 2286145Snate@binkert.org 2297089Snate@binkert.org#endif // __MEM_RUBY_COMMON_SET_HH__ 230