Set.hh revision 7055
16145Snate@binkert.org 26145Snate@binkert.org/* 36145Snate@binkert.org * Copyright (c) 1999-2008 Mark D. Hill and David A. Wood 46145Snate@binkert.org * All rights reserved. 56145Snate@binkert.org * 66145Snate@binkert.org * Redistribution and use in source and binary forms, with or without 76145Snate@binkert.org * modification, are permitted provided that the following conditions are 86145Snate@binkert.org * met: redistributions of source code must retain the above copyright 96145Snate@binkert.org * notice, this list of conditions and the following disclaimer; 106145Snate@binkert.org * redistributions in binary form must reproduce the above copyright 116145Snate@binkert.org * notice, this list of conditions and the following disclaimer in the 126145Snate@binkert.org * documentation and/or other materials provided with the distribution; 136145Snate@binkert.org * neither the name of the copyright holders nor the names of its 146145Snate@binkert.org * contributors may be used to endorse or promote products derived from 156145Snate@binkert.org * this software without specific prior written permission. 166145Snate@binkert.org * 176145Snate@binkert.org * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS 186145Snate@binkert.org * "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT 196145Snate@binkert.org * LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR 206145Snate@binkert.org * A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT 216145Snate@binkert.org * OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, 226145Snate@binkert.org * SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT 236145Snate@binkert.org * LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, 246145Snate@binkert.org * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY 256145Snate@binkert.org * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT 266145Snate@binkert.org * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE 276145Snate@binkert.org * OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. 286145Snate@binkert.org */ 296145Snate@binkert.org 306145Snate@binkert.org/* 316284Snate@binkert.org * Set.hh 326145Snate@binkert.org * 336145Snate@binkert.org * Description: 346145Snate@binkert.org * 356284Snate@binkert.org * $Id: BigSet.hh 1.6 05/01/19 13:12:25-06:00 mikem@maya.cs.wisc.edu $ 366145Snate@binkert.org * 376145Snate@binkert.org */ 386145Snate@binkert.org 396163Spdudnik@gmail.com// modified by Dan Gibson on 05/20/05 to accomidate FASTER 406163Spdudnik@gmail.com// >32 set lengths, using an array of ints w/ 32 bits/int 416145Snate@binkert.org 426163Spdudnik@gmail.com// NOTE: Never include this file directly, this should only be 436284Snate@binkert.org// included from Set.hh 446145Snate@binkert.org 456145Snate@binkert.org#ifndef SET_H 466145Snate@binkert.org#define SET_H 476145Snate@binkert.org 487055Snate@binkert.org#include <iostream> 497055Snate@binkert.org 506372Sdrh5@cs.wisc.edu#include "mem/ruby/system/System.hh" 516154Snate@binkert.org#include "mem/ruby/common/Global.hh" 526154Snate@binkert.org#include "mem/gems_common/Vector.hh" 536154Snate@binkert.org#include "mem/ruby/system/NodeID.hh" 546145Snate@binkert.org 556163Spdudnik@gmail.com// gibson 05/20/05 566163Spdudnik@gmail.com// enum PresenceBit {NotPresent, Present}; 576163Spdudnik@gmail.com 586145Snate@binkert.orgclass Set { 596145Snate@binkert.orgpublic: 606145Snate@binkert.org // Constructors 616145Snate@binkert.org // creates and empty set 626145Snate@binkert.org Set(); 636163Spdudnik@gmail.com Set (int size); 646145Snate@binkert.org 656145Snate@binkert.org // used during the replay mechanism 666145Snate@binkert.org // Set(const char *str); 676145Snate@binkert.org 686163Spdudnik@gmail.com Set(const Set& obj); 696163Spdudnik@gmail.com Set& operator=(const Set& obj); 706145Snate@binkert.org 716145Snate@binkert.org // Destructor 726163Spdudnik@gmail.com ~Set(); 736145Snate@binkert.org 746145Snate@binkert.org // Public Methods 756145Snate@binkert.org 766163Spdudnik@gmail.com inline void add(NodeID index) 776163Spdudnik@gmail.com { 786163Spdudnik@gmail.com#ifdef __32BITS__ 796163Spdudnik@gmail.com m_p_nArray[index>>5] |= (1 << (index & 0x01F)); 806163Spdudnik@gmail.com#else 816163Spdudnik@gmail.com m_p_nArray[index>>6] |= (((unsigned long) 1) << (index & 0x03F)); 826163Spdudnik@gmail.com#endif // __32BITS__ 836163Spdudnik@gmail.com } 846163Spdudnik@gmail.com 856145Snate@binkert.org void addSet(const Set& set); 866145Snate@binkert.org void addRandom(); 876163Spdudnik@gmail.com 886163Spdudnik@gmail.com inline void remove(NodeID index) 896163Spdudnik@gmail.com { 906163Spdudnik@gmail.com#ifdef __32BITS__ 916163Spdudnik@gmail.com m_p_nArray[index>>5] &= ~(0x00000001 << (index & 0x01F)); 926163Spdudnik@gmail.com#else 936163Spdudnik@gmail.com m_p_nArray[index>>6] &= ~(((unsigned long) 0x0000000000000001) << (index & 0x03F)); 946163Spdudnik@gmail.com#endif // __32BITS__ 956163Spdudnik@gmail.com } 966163Spdudnik@gmail.com 976163Spdudnik@gmail.com 986145Snate@binkert.org void removeSet(const Set& set); 996163Spdudnik@gmail.com 1006163Spdudnik@gmail.com inline void clear() { for(int i=0; i<m_nArrayLen; i++) m_p_nArray[i] = 0; } 1016163Spdudnik@gmail.com 1026145Snate@binkert.org void broadcast(); 1036145Snate@binkert.org int count() const; 1046163Spdudnik@gmail.com bool isEqual(const Set& set) const; 1056145Snate@binkert.org 1066145Snate@binkert.org Set OR(const Set& orSet) const; // return the logical OR of this set and orSet 1076145Snate@binkert.org Set AND(const Set& andSet) const; // return the logical AND of this set and andSet 1086145Snate@binkert.org 1096145Snate@binkert.org // Returns true if the intersection of the two sets is non-empty 1106163Spdudnik@gmail.com inline bool intersectionIsNotEmpty(const Set& other_set) const 1116163Spdudnik@gmail.com { 1126163Spdudnik@gmail.com for(int i=0; i< m_nArrayLen; i++) { 1136163Spdudnik@gmail.com if(m_p_nArray[i] & other_set.m_p_nArray[i]) { 1146163Spdudnik@gmail.com return true; 1156163Spdudnik@gmail.com } 1166163Spdudnik@gmail.com } 1176163Spdudnik@gmail.com return false; 1186163Spdudnik@gmail.com } 1196145Snate@binkert.org 1206145Snate@binkert.org // Returns true if the intersection of the two sets is empty 1216163Spdudnik@gmail.com inline bool intersectionIsEmpty(const Set& other_set) const 1226163Spdudnik@gmail.com { 1236163Spdudnik@gmail.com for(int i=0; i< m_nArrayLen; i++) { 1246163Spdudnik@gmail.com if(m_p_nArray[i] & other_set.m_p_nArray[i]) { 1256163Spdudnik@gmail.com return false; 1266163Spdudnik@gmail.com } 1276163Spdudnik@gmail.com } 1286163Spdudnik@gmail.com return true; 1296163Spdudnik@gmail.com } 1306145Snate@binkert.org 1316145Snate@binkert.org bool isSuperset(const Set& test) const; 1326145Snate@binkert.org bool isSubset(const Set& test) const { return test.isSuperset(*this); } 1336163Spdudnik@gmail.com 1346163Spdudnik@gmail.com inline bool isElement(NodeID element) const 1356163Spdudnik@gmail.com { 1366163Spdudnik@gmail.com#ifdef __32BITS__ 1376163Spdudnik@gmail.com return ((m_p_nArray[element>>5] & (0x00000001 << (element & 0x01F)))!=0); 1386163Spdudnik@gmail.com#else 1396163Spdudnik@gmail.com return ((m_p_nArray[element>>6] & (((unsigned long) 0x0000000000000001) << (element & 0x03F)))!=0); 1406163Spdudnik@gmail.com#endif // __32BITS__ 1416163Spdudnik@gmail.com 1426163Spdudnik@gmail.com } 1436163Spdudnik@gmail.com 1446145Snate@binkert.org bool isBroadcast() const; 1456145Snate@binkert.org bool isEmpty() const; 1466145Snate@binkert.org 1476145Snate@binkert.org NodeID smallestElement() const; 1486145Snate@binkert.org 1496145Snate@binkert.org // int size() const; 1506145Snate@binkert.org void setSize (int size); 1516145Snate@binkert.org 1526145Snate@binkert.org // get element for a index 1536163Spdudnik@gmail.com inline NodeID elementAt(int index) const 1546163Spdudnik@gmail.com { 1556163Spdudnik@gmail.com if(isElement(index)) return (NodeID) true; 1566163Spdudnik@gmail.com else return 0; 1576163Spdudnik@gmail.com } 1586163Spdudnik@gmail.com 1596163Spdudnik@gmail.com // gibson 05/20/05 1606163Spdudnik@gmail.com int getSize() const { return m_nSize; } 1616145Snate@binkert.org 1626145Snate@binkert.org // DEPRECATED METHODS 1636145Snate@binkert.org void addToSet(NodeID newElement) { add(newElement); } // Deprecated 1646145Snate@binkert.org void removeFromSet(NodeID newElement) { remove(newElement); } // Deprecated 1656145Snate@binkert.org void clearSet() { clear(); } // Deprecated 1666145Snate@binkert.org void setBroadcast() { broadcast(); } // Deprecated 1676145Snate@binkert.org bool presentInSet(NodeID element) const { return isElement(element); } // Deprecated 1686145Snate@binkert.org 1697055Snate@binkert.org void print(std::ostream& out) const; 1706145Snate@binkert.orgprivate: 1716145Snate@binkert.org // Private Methods 1726145Snate@binkert.org 1736145Snate@binkert.org // Data Members (m_ prefix) 1746163Spdudnik@gmail.com // gibson 05/20/05 1756163Spdudnik@gmail.com // Vector<uint8> m_bits; // This is an vector of uint8 to reduce the size of the set 1766145Snate@binkert.org 1776163Spdudnik@gmail.com int m_nSize; // the number of bits in this set 1786163Spdudnik@gmail.com int m_nArrayLen; // the number of 32-bit words that are held in the array 1796163Spdudnik@gmail.com 1806163Spdudnik@gmail.com // Changed 5/24/05 for static allocation of array 1816163Spdudnik@gmail.com // note that "long" corresponds to 32 bits on a 32-bit machine, 1826163Spdudnik@gmail.com // 64 bits if the -m64 parameter is passed to g++, which it is 1836163Spdudnik@gmail.com // for an AMD opteron under our configuration 1846163Spdudnik@gmail.com 1856163Spdudnik@gmail.com long * m_p_nArray; // an word array to hold the bits in the set 1866163Spdudnik@gmail.com long m_p_nArray_Static[NUMBER_WORDS_PER_SET]; 1876145Snate@binkert.org}; 1886145Snate@binkert.org 1896145Snate@binkert.org// Output operator declaration 1907055Snate@binkert.orgstd::ostream& operator<<(std::ostream& out, const Set& obj); 1916145Snate@binkert.org 1926145Snate@binkert.org// ******************* Definitions ******************* 1936145Snate@binkert.org 1946145Snate@binkert.org// Output operator definition 1956145Snate@binkert.orgextern inline 1967055Snate@binkert.orgstd::ostream& operator<<(std::ostream& out, const Set& obj) 1976145Snate@binkert.org{ 1986145Snate@binkert.org obj.print(out); 1997055Snate@binkert.org out << std::flush; 2006145Snate@binkert.org return out; 2016145Snate@binkert.org} 2026145Snate@binkert.org 2036145Snate@binkert.org#endif //SET_H 2046145Snate@binkert.org 205