Set.hh revision 6163
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/* 316145Snate@binkert.org * Set.h 326145Snate@binkert.org * 336145Snate@binkert.org * Description: 346145Snate@binkert.org * 356163Spdudnik@gmail.com * $Id: BigSet.h 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 436163Spdudnik@gmail.com// included from Set.h 446145Snate@binkert.org 456145Snate@binkert.org#ifndef SET_H 466145Snate@binkert.org#define SET_H 476145Snate@binkert.org 486154Snate@binkert.org#include "mem/ruby/common/Global.hh" 496154Snate@binkert.org#include "mem/gems_common/Vector.hh" 506154Snate@binkert.org#include "mem/ruby/system/NodeID.hh" 516154Snate@binkert.org#include "mem/ruby/config/RubyConfig.hh" 526145Snate@binkert.org 536163Spdudnik@gmail.com// gibson 05/20/05 546163Spdudnik@gmail.com// enum PresenceBit {NotPresent, Present}; 556163Spdudnik@gmail.com 566145Snate@binkert.orgclass Set { 576145Snate@binkert.orgpublic: 586145Snate@binkert.org // Constructors 596145Snate@binkert.org // creates and empty set 606145Snate@binkert.org Set(); 616163Spdudnik@gmail.com Set (int size); 626145Snate@binkert.org 636145Snate@binkert.org // used during the replay mechanism 646145Snate@binkert.org // Set(const char *str); 656145Snate@binkert.org 666163Spdudnik@gmail.com Set(const Set& obj); 676163Spdudnik@gmail.com Set& operator=(const Set& obj); 686145Snate@binkert.org 696145Snate@binkert.org // Destructor 706163Spdudnik@gmail.com ~Set(); 716145Snate@binkert.org 726145Snate@binkert.org // Public Methods 736145Snate@binkert.org 746163Spdudnik@gmail.com inline void add(NodeID index) 756163Spdudnik@gmail.com { 766163Spdudnik@gmail.com#ifdef __32BITS__ 776163Spdudnik@gmail.com m_p_nArray[index>>5] |= (1 << (index & 0x01F)); 786163Spdudnik@gmail.com#else 796163Spdudnik@gmail.com m_p_nArray[index>>6] |= (((unsigned long) 1) << (index & 0x03F)); 806163Spdudnik@gmail.com#endif // __32BITS__ 816163Spdudnik@gmail.com } 826163Spdudnik@gmail.com 836145Snate@binkert.org void addSet(const Set& set); 846145Snate@binkert.org void addRandom(); 856163Spdudnik@gmail.com 866163Spdudnik@gmail.com inline void remove(NodeID index) 876163Spdudnik@gmail.com { 886163Spdudnik@gmail.com#ifdef __32BITS__ 896163Spdudnik@gmail.com m_p_nArray[index>>5] &= ~(0x00000001 << (index & 0x01F)); 906163Spdudnik@gmail.com#else 916163Spdudnik@gmail.com m_p_nArray[index>>6] &= ~(((unsigned long) 0x0000000000000001) << (index & 0x03F)); 926163Spdudnik@gmail.com#endif // __32BITS__ 936163Spdudnik@gmail.com } 946163Spdudnik@gmail.com 956163Spdudnik@gmail.com 966145Snate@binkert.org void removeSet(const Set& set); 976163Spdudnik@gmail.com 986163Spdudnik@gmail.com inline void clear() { for(int i=0; i<m_nArrayLen; i++) m_p_nArray[i] = 0; } 996163Spdudnik@gmail.com 1006145Snate@binkert.org void broadcast(); 1016145Snate@binkert.org int count() const; 1026163Spdudnik@gmail.com bool isEqual(const Set& set) const; 1036145Snate@binkert.org 1046145Snate@binkert.org Set OR(const Set& orSet) const; // return the logical OR of this set and orSet 1056145Snate@binkert.org Set AND(const Set& andSet) const; // return the logical AND of this set and andSet 1066145Snate@binkert.org 1076145Snate@binkert.org // Returns true if the intersection of the two sets is non-empty 1086163Spdudnik@gmail.com inline bool intersectionIsNotEmpty(const Set& other_set) const 1096163Spdudnik@gmail.com { 1106163Spdudnik@gmail.com for(int i=0; i< m_nArrayLen; i++) { 1116163Spdudnik@gmail.com if(m_p_nArray[i] & other_set.m_p_nArray[i]) { 1126163Spdudnik@gmail.com return true; 1136163Spdudnik@gmail.com } 1146163Spdudnik@gmail.com } 1156163Spdudnik@gmail.com return false; 1166163Spdudnik@gmail.com } 1176145Snate@binkert.org 1186145Snate@binkert.org // Returns true if the intersection of the two sets is empty 1196163Spdudnik@gmail.com inline bool intersectionIsEmpty(const Set& other_set) const 1206163Spdudnik@gmail.com { 1216163Spdudnik@gmail.com for(int i=0; i< m_nArrayLen; i++) { 1226163Spdudnik@gmail.com if(m_p_nArray[i] & other_set.m_p_nArray[i]) { 1236163Spdudnik@gmail.com return false; 1246163Spdudnik@gmail.com } 1256163Spdudnik@gmail.com } 1266163Spdudnik@gmail.com return true; 1276163Spdudnik@gmail.com } 1286145Snate@binkert.org 1296145Snate@binkert.org bool isSuperset(const Set& test) const; 1306145Snate@binkert.org bool isSubset(const Set& test) const { return test.isSuperset(*this); } 1316163Spdudnik@gmail.com 1326163Spdudnik@gmail.com inline bool isElement(NodeID element) const 1336163Spdudnik@gmail.com { 1346163Spdudnik@gmail.com#ifdef __32BITS__ 1356163Spdudnik@gmail.com return ((m_p_nArray[element>>5] & (0x00000001 << (element & 0x01F)))!=0); 1366163Spdudnik@gmail.com#else 1376163Spdudnik@gmail.com return ((m_p_nArray[element>>6] & (((unsigned long) 0x0000000000000001) << (element & 0x03F)))!=0); 1386163Spdudnik@gmail.com#endif // __32BITS__ 1396163Spdudnik@gmail.com 1406163Spdudnik@gmail.com } 1416163Spdudnik@gmail.com 1426145Snate@binkert.org bool isBroadcast() const; 1436145Snate@binkert.org bool isEmpty() const; 1446145Snate@binkert.org 1456145Snate@binkert.org NodeID smallestElement() const; 1466145Snate@binkert.org 1476145Snate@binkert.org // int size() const; 1486145Snate@binkert.org void setSize (int size); 1496145Snate@binkert.org 1506145Snate@binkert.org // get element for a index 1516163Spdudnik@gmail.com inline NodeID elementAt(int index) const 1526163Spdudnik@gmail.com { 1536163Spdudnik@gmail.com if(isElement(index)) return (NodeID) true; 1546163Spdudnik@gmail.com else return 0; 1556163Spdudnik@gmail.com } 1566163Spdudnik@gmail.com 1576163Spdudnik@gmail.com // gibson 05/20/05 1586163Spdudnik@gmail.com int getSize() const { return m_nSize; } 1596145Snate@binkert.org 1606145Snate@binkert.org // DEPRECATED METHODS 1616145Snate@binkert.org void addToSet(NodeID newElement) { add(newElement); } // Deprecated 1626145Snate@binkert.org void removeFromSet(NodeID newElement) { remove(newElement); } // Deprecated 1636145Snate@binkert.org void clearSet() { clear(); } // Deprecated 1646145Snate@binkert.org void setBroadcast() { broadcast(); } // Deprecated 1656145Snate@binkert.org bool presentInSet(NodeID element) const { return isElement(element); } // Deprecated 1666145Snate@binkert.org 1676145Snate@binkert.org void print(ostream& out) const; 1686145Snate@binkert.orgprivate: 1696145Snate@binkert.org // Private Methods 1706145Snate@binkert.org 1716145Snate@binkert.org // Data Members (m_ prefix) 1726163Spdudnik@gmail.com // gibson 05/20/05 1736163Spdudnik@gmail.com // Vector<uint8> m_bits; // This is an vector of uint8 to reduce the size of the set 1746145Snate@binkert.org 1756163Spdudnik@gmail.com int m_nSize; // the number of bits in this set 1766163Spdudnik@gmail.com int m_nArrayLen; // the number of 32-bit words that are held in the array 1776163Spdudnik@gmail.com 1786163Spdudnik@gmail.com // Changed 5/24/05 for static allocation of array 1796163Spdudnik@gmail.com // note that "long" corresponds to 32 bits on a 32-bit machine, 1806163Spdudnik@gmail.com // 64 bits if the -m64 parameter is passed to g++, which it is 1816163Spdudnik@gmail.com // for an AMD opteron under our configuration 1826163Spdudnik@gmail.com 1836163Spdudnik@gmail.com long * m_p_nArray; // an word array to hold the bits in the set 1846163Spdudnik@gmail.com long m_p_nArray_Static[NUMBER_WORDS_PER_SET]; 1856145Snate@binkert.org}; 1866145Snate@binkert.org 1876145Snate@binkert.org// Output operator declaration 1886145Snate@binkert.orgostream& operator<<(ostream& out, const Set& obj); 1896145Snate@binkert.org 1906145Snate@binkert.org// ******************* Definitions ******************* 1916145Snate@binkert.org 1926145Snate@binkert.org// Output operator definition 1936145Snate@binkert.orgextern inline 1946145Snate@binkert.orgostream& operator<<(ostream& out, const Set& obj) 1956145Snate@binkert.org{ 1966145Snate@binkert.org obj.print(out); 1976145Snate@binkert.org out << flush; 1986145Snate@binkert.org return out; 1996145Snate@binkert.org} 2006145Snate@binkert.org 2016145Snate@binkert.org#endif //SET_H 2026145Snate@binkert.org 203