Set.hh revision 12334
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 4211085Snilay@cs.wisc.edu// Change for systems with more than 64 controllers of a particular type. 4311085Snilay@cs.wisc.educonst int NUMBER_BITS_PER_SET = 64; 446145Snate@binkert.org 457089Snate@binkert.orgclass Set 467089Snate@binkert.org{ 477089Snate@binkert.org private: 4811085Snilay@cs.wisc.edu // Number of bits in use in this set. 4911085Snilay@cs.wisc.edu int m_nSize; 5011085Snilay@cs.wisc.edu std::bitset<NUMBER_BITS_PER_SET> bits; 516145Snate@binkert.org 527089Snate@binkert.org public: 5311085Snilay@cs.wisc.edu Set() : m_nSize(0) {} 546145Snate@binkert.org 5511085Snilay@cs.wisc.edu Set(int size) : m_nSize(size) 5611085Snilay@cs.wisc.edu { 5711085Snilay@cs.wisc.edu if (size > NUMBER_BITS_PER_SET) 5811085Snilay@cs.wisc.edu fatal("Number of bits(%d) < size specified(%d). " 5911085Snilay@cs.wisc.edu "Increase the number of bits and recompile.\n", 6011085Snilay@cs.wisc.edu NUMBER_BITS_PER_SET, size); 6111085Snilay@cs.wisc.edu } 6211085Snilay@cs.wisc.edu 6311085Snilay@cs.wisc.edu Set(const Set& obj) : m_nSize(obj.m_nSize), bits(obj.bits) {} 6411085Snilay@cs.wisc.edu ~Set() {} 6511085Snilay@cs.wisc.edu 6611085Snilay@cs.wisc.edu Set& operator=(const Set& obj) 6711085Snilay@cs.wisc.edu { 6811085Snilay@cs.wisc.edu m_nSize = obj.m_nSize; 6911085Snilay@cs.wisc.edu bits = obj.bits; 7011085Snilay@cs.wisc.edu return *this; 7111085Snilay@cs.wisc.edu } 727089Snate@binkert.org 737089Snate@binkert.org void 747089Snate@binkert.org add(NodeID index) 756163Spdudnik@gmail.com { 7611085Snilay@cs.wisc.edu bits.set(index); 776163Spdudnik@gmail.com } 786163Spdudnik@gmail.com 7911085Snilay@cs.wisc.edu /* 8011085Snilay@cs.wisc.edu * This function should set all the bits in the current set that are 8111085Snilay@cs.wisc.edu * already set in the parameter set 8211085Snilay@cs.wisc.edu */ 8311085Snilay@cs.wisc.edu void 8411085Snilay@cs.wisc.edu addSet(const Set& obj) 8511085Snilay@cs.wisc.edu { 8611085Snilay@cs.wisc.edu assert(m_nSize == obj.m_nSize); 8711085Snilay@cs.wisc.edu bits |= obj.bits; 8811085Snilay@cs.wisc.edu } 896163Spdudnik@gmail.com 9011085Snilay@cs.wisc.edu /* 9111085Snilay@cs.wisc.edu * This function clears bits that are =1 in the parameter set 9211085Snilay@cs.wisc.edu */ 937089Snate@binkert.org void 947089Snate@binkert.org remove(NodeID index) 956163Spdudnik@gmail.com { 9611085Snilay@cs.wisc.edu bits.reset(index); 976163Spdudnik@gmail.com } 986163Spdudnik@gmail.com 9911085Snilay@cs.wisc.edu /* 10011085Snilay@cs.wisc.edu * This function clears bits that are =1 in the parameter set 10111085Snilay@cs.wisc.edu */ 1027089Snate@binkert.org void 10311085Snilay@cs.wisc.edu removeSet(const Set& obj) 1046163Spdudnik@gmail.com { 10511085Snilay@cs.wisc.edu assert(m_nSize == obj.m_nSize); 10611085Snilay@cs.wisc.edu bits &= (~obj.bits); 1076163Spdudnik@gmail.com } 1086145Snate@binkert.org 10911085Snilay@cs.wisc.edu void clear() { bits.reset(); } 11011085Snilay@cs.wisc.edu 11111085Snilay@cs.wisc.edu /* 11211085Snilay@cs.wisc.edu * this function sets all bits in the set 11311085Snilay@cs.wisc.edu */ 11411085Snilay@cs.wisc.edu void broadcast() 11511085Snilay@cs.wisc.edu { 11611085Snilay@cs.wisc.edu bits.set(); 11711085Snilay@cs.wisc.edu for (int j = m_nSize; j < NUMBER_BITS_PER_SET; ++j) { 11811085Snilay@cs.wisc.edu bits.reset(j); 11911085Snilay@cs.wisc.edu } 12011085Snilay@cs.wisc.edu } 12111085Snilay@cs.wisc.edu 12211085Snilay@cs.wisc.edu /* 12311085Snilay@cs.wisc.edu * This function returns the population count of 1's in the set 12411085Snilay@cs.wisc.edu */ 12511085Snilay@cs.wisc.edu int count() const { return bits.count(); } 12611085Snilay@cs.wisc.edu 12711085Snilay@cs.wisc.edu /* 12811085Snilay@cs.wisc.edu * This function checks for set equality 12911085Snilay@cs.wisc.edu */ 13011085Snilay@cs.wisc.edu bool 13111085Snilay@cs.wisc.edu isEqual(const Set& obj) const 13211085Snilay@cs.wisc.edu { 13311085Snilay@cs.wisc.edu assert(m_nSize == obj.m_nSize); 13411085Snilay@cs.wisc.edu return bits == obj.bits; 13511085Snilay@cs.wisc.edu } 1367089Snate@binkert.org 1377089Snate@binkert.org // return the logical OR of this set and orSet 13811085Snilay@cs.wisc.edu Set 13911085Snilay@cs.wisc.edu OR(const Set& obj) const 14011085Snilay@cs.wisc.edu { 14111085Snilay@cs.wisc.edu assert(m_nSize == obj.m_nSize); 14211085Snilay@cs.wisc.edu Set r(m_nSize); 14311085Snilay@cs.wisc.edu r.bits = bits | obj.bits; 14411085Snilay@cs.wisc.edu return r; 14511085Snilay@cs.wisc.edu }; 1467089Snate@binkert.org 1477089Snate@binkert.org // return the logical AND of this set and andSet 14811085Snilay@cs.wisc.edu Set 14911085Snilay@cs.wisc.edu AND(const Set& obj) const 15011085Snilay@cs.wisc.edu { 15111085Snilay@cs.wisc.edu assert(m_nSize == obj.m_nSize); 15211085Snilay@cs.wisc.edu Set r(m_nSize); 15311085Snilay@cs.wisc.edu r.bits = bits & obj.bits; 15411085Snilay@cs.wisc.edu return r; 15511085Snilay@cs.wisc.edu } 1567089Snate@binkert.org 1577089Snate@binkert.org // Returns true if the intersection of the two sets is empty 1587089Snate@binkert.org bool 15911085Snilay@cs.wisc.edu intersectionIsEmpty(const Set& obj) const 1606163Spdudnik@gmail.com { 16111085Snilay@cs.wisc.edu std::bitset<NUMBER_BITS_PER_SET> r = bits & obj.bits; 16211085Snilay@cs.wisc.edu return r.none(); 1636163Spdudnik@gmail.com } 1646145Snate@binkert.org 16511085Snilay@cs.wisc.edu /* 16611085Snilay@cs.wisc.edu * Returns false if a bit is set in the parameter set that is NOT set 16711085Snilay@cs.wisc.edu * in this set 16811085Snilay@cs.wisc.edu */ 16911085Snilay@cs.wisc.edu bool 17011085Snilay@cs.wisc.edu isSuperset(const Set& test) const 17111085Snilay@cs.wisc.edu { 17211085Snilay@cs.wisc.edu assert(m_nSize == test.m_nSize); 17311085Snilay@cs.wisc.edu std::bitset<NUMBER_BITS_PER_SET> r = bits | test.bits; 17411085Snilay@cs.wisc.edu return (r == bits); 17511085Snilay@cs.wisc.edu } 17611085Snilay@cs.wisc.edu 1777089Snate@binkert.org bool isSubset(const Set& test) const { return test.isSuperset(*this); } 1786163Spdudnik@gmail.com 17911085Snilay@cs.wisc.edu bool isElement(NodeID element) const { return bits.test(element); } 18011085Snilay@cs.wisc.edu 18111085Snilay@cs.wisc.edu /* 18211085Snilay@cs.wisc.edu * this function returns true iff all bits in use are set 18311085Snilay@cs.wisc.edu */ 1847089Snate@binkert.org bool 18511085Snilay@cs.wisc.edu isBroadcast() const 1866163Spdudnik@gmail.com { 18711085Snilay@cs.wisc.edu return (bits.count() == m_nSize); 1886163Spdudnik@gmail.com } 1896163Spdudnik@gmail.com 19011085Snilay@cs.wisc.edu bool isEmpty() const { return bits.none(); } 1916145Snate@binkert.org 19211085Snilay@cs.wisc.edu NodeID smallestElement() const 19311085Snilay@cs.wisc.edu { 19411085Snilay@cs.wisc.edu for (int i = 0; i < m_nSize; ++i) { 19511085Snilay@cs.wisc.edu if (bits.test(i)) { 19611085Snilay@cs.wisc.edu return i; 19711085Snilay@cs.wisc.edu } 19811085Snilay@cs.wisc.edu } 19911085Snilay@cs.wisc.edu panic("No smallest element of an empty set."); 20011085Snilay@cs.wisc.edu } 2016145Snate@binkert.org 20211085Snilay@cs.wisc.edu bool elementAt(int index) const { return bits[index]; } 2036163Spdudnik@gmail.com 2047089Snate@binkert.org int getSize() const { return m_nSize; } 2056145Snate@binkert.org 20611085Snilay@cs.wisc.edu void 20711085Snilay@cs.wisc.edu setSize(int size) 20811085Snilay@cs.wisc.edu { 20911085Snilay@cs.wisc.edu if (size > NUMBER_BITS_PER_SET) 21011085Snilay@cs.wisc.edu fatal("Number of bits(%d) < size specified(%d). " 21111085Snilay@cs.wisc.edu "Increase the number of bits and recompile.\n", 21211085Snilay@cs.wisc.edu NUMBER_BITS_PER_SET, size); 21311085Snilay@cs.wisc.edu m_nSize = size; 21411085Snilay@cs.wisc.edu bits.reset(); 21511085Snilay@cs.wisc.edu } 21611085Snilay@cs.wisc.edu 21711085Snilay@cs.wisc.edu void print(std::ostream& out) const 21811085Snilay@cs.wisc.edu { 21911085Snilay@cs.wisc.edu out << "[Set (" << m_nSize << "): " << bits << "]"; 22011085Snilay@cs.wisc.edu } 2216145Snate@binkert.org}; 2226145Snate@binkert.org 2237089Snate@binkert.orginline std::ostream& 2247089Snate@binkert.orgoperator<<(std::ostream& out, const Set& obj) 2256145Snate@binkert.org{ 2267089Snate@binkert.org obj.print(out); 2277089Snate@binkert.org out << std::flush; 2287089Snate@binkert.org return out; 2296145Snate@binkert.org} 2306145Snate@binkert.org 2317089Snate@binkert.org#endif // __MEM_RUBY_COMMON_SET_HH__ 232