Set.hh revision 7089
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 386372Sdrh5@cs.wisc.edu#include "mem/ruby/system/System.hh" 396154Snate@binkert.org#include "mem/ruby/common/Global.hh" 406154Snate@binkert.org#include "mem/ruby/system/NodeID.hh" 416145Snate@binkert.org 427089Snate@binkert.orgclass Set 437089Snate@binkert.org{ 447089Snate@binkert.org private: 457089Snate@binkert.org int m_nSize; // the number of bits in this set 467089Snate@binkert.org int m_nArrayLen; // the number of 32-bit words that are 477089Snate@binkert.org // held in the array 486163Spdudnik@gmail.com 497089Snate@binkert.org // Changed 5/24/05 for static allocation of array 507089Snate@binkert.org // note that "long" corresponds to 32 bits on a 32-bit machine, 517089Snate@binkert.org // 64 bits if the -m64 parameter is passed to g++, which it is 527089Snate@binkert.org // for an AMD opteron under our configuration 536145Snate@binkert.org 547089Snate@binkert.org long *m_p_nArray; // an word array to hold the bits in the set 557089Snate@binkert.org long m_p_nArray_Static[NUMBER_WORDS_PER_SET]; 566145Snate@binkert.org 577089Snate@binkert.org static const int LONG_BITS = std::numeric_limits<long>::digits; 587089Snate@binkert.org static const int INDEX_SHIFT = LONG_BITS == 64 ? 6 : 5; 597089Snate@binkert.org static const int INDEX_MASK = (1 << INDEX_SHIFT) - 1; 606145Snate@binkert.org 617089Snate@binkert.org void clearExcess(); 626145Snate@binkert.org 637089Snate@binkert.org public: 647089Snate@binkert.org Set(); 657089Snate@binkert.org Set(int size); 667089Snate@binkert.org Set(const Set& obj); 677089Snate@binkert.org ~Set(); 686145Snate@binkert.org 697089Snate@binkert.org Set& operator=(const Set& obj); 707089Snate@binkert.org 717089Snate@binkert.org void 727089Snate@binkert.org add(NodeID index) 736163Spdudnik@gmail.com { 747089Snate@binkert.org m_p_nArray[index >> INDEX_SHIFT] |= 757089Snate@binkert.org (((unsigned long) 1) << (index & INDEX_MASK)); 766163Spdudnik@gmail.com } 776163Spdudnik@gmail.com 787089Snate@binkert.org void addSet(const Set& set); 797089Snate@binkert.org void addRandom(); 806163Spdudnik@gmail.com 817089Snate@binkert.org void 827089Snate@binkert.org remove(NodeID index) 836163Spdudnik@gmail.com { 847089Snate@binkert.org m_p_nArray[index >> INDEX_SHIFT] &= 857089Snate@binkert.org ~(((unsigned long)1) << (index & INDEX_MASK)); 866163Spdudnik@gmail.com } 876163Spdudnik@gmail.com 887089Snate@binkert.org void removeSet(const Set& set); 896163Spdudnik@gmail.com 907089Snate@binkert.org void 917089Snate@binkert.org clear() 926163Spdudnik@gmail.com { 937089Snate@binkert.org for (int i = 0; i < m_nArrayLen; i++) 947089Snate@binkert.org m_p_nArray[i] = 0; 956163Spdudnik@gmail.com } 966145Snate@binkert.org 977089Snate@binkert.org void broadcast(); 987089Snate@binkert.org int count() const; 997089Snate@binkert.org bool isEqual(const Set& set) const; 1007089Snate@binkert.org 1017089Snate@binkert.org // return the logical OR of this set and orSet 1027089Snate@binkert.org Set OR(const Set& orSet) const; 1037089Snate@binkert.org 1047089Snate@binkert.org // return the logical AND of this set and andSet 1057089Snate@binkert.org Set AND(const Set& andSet) const; 1067089Snate@binkert.org 1077089Snate@binkert.org // Returns true if the intersection of the two sets is empty 1087089Snate@binkert.org bool 1097089Snate@binkert.org intersectionIsEmpty(const Set& other_set) const 1106163Spdudnik@gmail.com { 1117089Snate@binkert.org for (int i = 0; i < m_nArrayLen; i++) 1127089Snate@binkert.org if (m_p_nArray[i] & other_set.m_p_nArray[i]) 1137089Snate@binkert.org return false; 1147089Snate@binkert.org return true; 1156163Spdudnik@gmail.com } 1166145Snate@binkert.org 1177089Snate@binkert.org bool isSuperset(const Set& test) const; 1187089Snate@binkert.org bool isSubset(const Set& test) const { return test.isSuperset(*this); } 1196163Spdudnik@gmail.com 1207089Snate@binkert.org bool 1217089Snate@binkert.org isElement(NodeID element) const 1226163Spdudnik@gmail.com { 1237089Snate@binkert.org return (m_p_nArray[element>>INDEX_SHIFT] & 1247089Snate@binkert.org (((unsigned long)1) << (element & INDEX_MASK))) != 0; 1256163Spdudnik@gmail.com } 1266163Spdudnik@gmail.com 1277089Snate@binkert.org bool isBroadcast() const; 1287089Snate@binkert.org bool isEmpty() const; 1296145Snate@binkert.org 1307089Snate@binkert.org NodeID smallestElement() const; 1316145Snate@binkert.org 1327089Snate@binkert.org void setSize(int size); 1336145Snate@binkert.org 1347089Snate@binkert.org NodeID 1357089Snate@binkert.org elementAt(int index) const 1366163Spdudnik@gmail.com { 1377089Snate@binkert.org if (isElement(index)) 1387089Snate@binkert.org return (NodeID)true; 1397089Snate@binkert.org else 1407089Snate@binkert.org return 0; 1416163Spdudnik@gmail.com } 1426163Spdudnik@gmail.com 1437089Snate@binkert.org int getSize() const { return m_nSize; } 1446145Snate@binkert.org 1457089Snate@binkert.org void print(std::ostream& out) const; 1466145Snate@binkert.org}; 1476145Snate@binkert.org 1487089Snate@binkert.orginline std::ostream& 1497089Snate@binkert.orgoperator<<(std::ostream& out, const Set& obj) 1506145Snate@binkert.org{ 1517089Snate@binkert.org obj.print(out); 1527089Snate@binkert.org out << std::flush; 1537089Snate@binkert.org return out; 1546145Snate@binkert.org} 1556145Snate@binkert.org 1567089Snate@binkert.org#endif // __MEM_RUBY_COMMON_SET_HH__ 157