Set.hh revision 8650
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 357055Snate@binkert.org#include <iostream> 367089Snate@binkert.org#include <limits> 377055Snate@binkert.org 388650Snilay@cs.wisc.edu#include "mem/ruby/common/TypeDefines.hh" 398650Snilay@cs.wisc.edu 408650Snilay@cs.wisc.edu/* 418650Snilay@cs.wisc.edu * This defines the number of longs (32-bits on 32 bit machines, 428650Snilay@cs.wisc.edu * 64-bit on 64-bit AMD machines) to use to hold the set... 438650Snilay@cs.wisc.edu * the default is 4, allowing 128 or 256 different members 448650Snilay@cs.wisc.edu * of the set. 458650Snilay@cs.wisc.edu * 468650Snilay@cs.wisc.edu * This should never need to be changed for correctness reasons, 478650Snilay@cs.wisc.edu * though increasing it will increase performance for larger 488650Snilay@cs.wisc.edu * set sizes at the cost of a (much) larger memory footprint 498650Snilay@cs.wisc.edu * 508650Snilay@cs.wisc.edu */ 518650Snilay@cs.wisc.educonst int NUMBER_WORDS_PER_SET = 1; 526145Snate@binkert.org 537089Snate@binkert.orgclass Set 547089Snate@binkert.org{ 557089Snate@binkert.org private: 567089Snate@binkert.org int m_nSize; // the number of bits in this set 577089Snate@binkert.org int m_nArrayLen; // the number of 32-bit words that are 587089Snate@binkert.org // held in the array 596163Spdudnik@gmail.com 607089Snate@binkert.org // Changed 5/24/05 for static allocation of array 617089Snate@binkert.org // note that "long" corresponds to 32 bits on a 32-bit machine, 627089Snate@binkert.org // 64 bits if the -m64 parameter is passed to g++, which it is 637089Snate@binkert.org // for an AMD opteron under our configuration 646145Snate@binkert.org 657089Snate@binkert.org long *m_p_nArray; // an word array to hold the bits in the set 667089Snate@binkert.org long m_p_nArray_Static[NUMBER_WORDS_PER_SET]; 676145Snate@binkert.org 688351Snilay@cs.wisc.edu static const int LONG_BITS = std::numeric_limits<long>::digits + 1; 697089Snate@binkert.org static const int INDEX_SHIFT = LONG_BITS == 64 ? 6 : 5; 707089Snate@binkert.org static const int INDEX_MASK = (1 << INDEX_SHIFT) - 1; 716145Snate@binkert.org 727089Snate@binkert.org void clearExcess(); 736145Snate@binkert.org 747089Snate@binkert.org public: 757089Snate@binkert.org Set(); 767089Snate@binkert.org Set(int size); 777089Snate@binkert.org Set(const Set& obj); 787089Snate@binkert.org ~Set(); 796145Snate@binkert.org 807089Snate@binkert.org Set& operator=(const Set& obj); 817089Snate@binkert.org 827089Snate@binkert.org void 837089Snate@binkert.org add(NodeID index) 846163Spdudnik@gmail.com { 857089Snate@binkert.org m_p_nArray[index >> INDEX_SHIFT] |= 867089Snate@binkert.org (((unsigned long) 1) << (index & INDEX_MASK)); 876163Spdudnik@gmail.com } 886163Spdudnik@gmail.com 897089Snate@binkert.org void addSet(const Set& set); 907089Snate@binkert.org void addRandom(); 916163Spdudnik@gmail.com 927089Snate@binkert.org void 937089Snate@binkert.org remove(NodeID index) 946163Spdudnik@gmail.com { 957089Snate@binkert.org m_p_nArray[index >> INDEX_SHIFT] &= 967089Snate@binkert.org ~(((unsigned long)1) << (index & INDEX_MASK)); 976163Spdudnik@gmail.com } 986163Spdudnik@gmail.com 997089Snate@binkert.org void removeSet(const Set& set); 1006163Spdudnik@gmail.com 1017089Snate@binkert.org void 1027089Snate@binkert.org clear() 1036163Spdudnik@gmail.com { 1047089Snate@binkert.org for (int i = 0; i < m_nArrayLen; i++) 1057089Snate@binkert.org m_p_nArray[i] = 0; 1066163Spdudnik@gmail.com } 1076145Snate@binkert.org 1087089Snate@binkert.org void broadcast(); 1097089Snate@binkert.org int count() const; 1107089Snate@binkert.org bool isEqual(const Set& set) const; 1117089Snate@binkert.org 1127089Snate@binkert.org // return the logical OR of this set and orSet 1137089Snate@binkert.org Set OR(const Set& orSet) const; 1147089Snate@binkert.org 1157089Snate@binkert.org // return the logical AND of this set and andSet 1167089Snate@binkert.org Set AND(const Set& andSet) const; 1177089Snate@binkert.org 1187089Snate@binkert.org // Returns true if the intersection of the two sets is empty 1197089Snate@binkert.org bool 1207089Snate@binkert.org intersectionIsEmpty(const Set& other_set) const 1216163Spdudnik@gmail.com { 1227089Snate@binkert.org for (int i = 0; i < m_nArrayLen; i++) 1237089Snate@binkert.org if (m_p_nArray[i] & other_set.m_p_nArray[i]) 1247089Snate@binkert.org return false; 1257089Snate@binkert.org return true; 1266163Spdudnik@gmail.com } 1276145Snate@binkert.org 1287089Snate@binkert.org bool isSuperset(const Set& test) const; 1297089Snate@binkert.org bool isSubset(const Set& test) const { return test.isSuperset(*this); } 1306163Spdudnik@gmail.com 1317089Snate@binkert.org bool 1327089Snate@binkert.org isElement(NodeID element) const 1336163Spdudnik@gmail.com { 1347089Snate@binkert.org return (m_p_nArray[element>>INDEX_SHIFT] & 1357089Snate@binkert.org (((unsigned long)1) << (element & INDEX_MASK))) != 0; 1366163Spdudnik@gmail.com } 1376163Spdudnik@gmail.com 1387089Snate@binkert.org bool isBroadcast() const; 1397089Snate@binkert.org bool isEmpty() const; 1406145Snate@binkert.org 1417089Snate@binkert.org NodeID smallestElement() const; 1426145Snate@binkert.org 1437089Snate@binkert.org void setSize(int size); 1446145Snate@binkert.org 1457089Snate@binkert.org NodeID 1467089Snate@binkert.org elementAt(int index) const 1476163Spdudnik@gmail.com { 1487089Snate@binkert.org if (isElement(index)) 1497089Snate@binkert.org return (NodeID)true; 1507089Snate@binkert.org else 1517089Snate@binkert.org return 0; 1526163Spdudnik@gmail.com } 1536163Spdudnik@gmail.com 1547089Snate@binkert.org int getSize() const { return m_nSize; } 1556145Snate@binkert.org 1567089Snate@binkert.org void print(std::ostream& out) const; 1576145Snate@binkert.org}; 1586145Snate@binkert.org 1597089Snate@binkert.orginline std::ostream& 1607089Snate@binkert.orgoperator<<(std::ostream& out, const Set& obj) 1616145Snate@binkert.org{ 1627089Snate@binkert.org obj.print(out); 1637089Snate@binkert.org out << std::flush; 1647089Snate@binkert.org return out; 1656145Snate@binkert.org} 1666145Snate@binkert.org 1677089Snate@binkert.org#endif // __MEM_RUBY_COMMON_SET_HH__ 168