Set.hh revision 8351:f897d0483b06
110497Ssteve.reinhardt@amd.com/* 210497Ssteve.reinhardt@amd.com * Copyright (c) 1999-2008 Mark D. Hill and David A. Wood 310497Ssteve.reinhardt@amd.com * All rights reserved. 410497Ssteve.reinhardt@amd.com * 510497Ssteve.reinhardt@amd.com * Redistribution and use in source and binary forms, with or without 610497Ssteve.reinhardt@amd.com * modification, are permitted provided that the following conditions are 710497Ssteve.reinhardt@amd.com * met: redistributions of source code must retain the above copyright 810497Ssteve.reinhardt@amd.com * notice, this list of conditions and the following disclaimer; 910497Ssteve.reinhardt@amd.com * redistributions in binary form must reproduce the above copyright 1010497Ssteve.reinhardt@amd.com * notice, this list of conditions and the following disclaimer in the 1110497Ssteve.reinhardt@amd.com * documentation and/or other materials provided with the distribution; 1210497Ssteve.reinhardt@amd.com * neither the name of the copyright holders nor the names of its 1310497Ssteve.reinhardt@amd.com * contributors may be used to endorse or promote products derived from 1410497Ssteve.reinhardt@amd.com * this software without specific prior written permission. 1510497Ssteve.reinhardt@amd.com * 1610497Ssteve.reinhardt@amd.com * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS 1710497Ssteve.reinhardt@amd.com * "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT 1810497Ssteve.reinhardt@amd.com * LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR 1910497Ssteve.reinhardt@amd.com * A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT 2010497Ssteve.reinhardt@amd.com * OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, 2110497Ssteve.reinhardt@amd.com * SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT 2210497Ssteve.reinhardt@amd.com * LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, 2310497Ssteve.reinhardt@amd.com * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY 2410497Ssteve.reinhardt@amd.com * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT 2510497Ssteve.reinhardt@amd.com * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE 2610497Ssteve.reinhardt@amd.com * OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. 2710497Ssteve.reinhardt@amd.com */ 2810497Ssteve.reinhardt@amd.com 2910497Ssteve.reinhardt@amd.com// modified by Dan Gibson on 05/20/05 to accomidate FASTER 3010497Ssteve.reinhardt@amd.com// >32 set lengths, using an array of ints w/ 32 bits/int 3110497Ssteve.reinhardt@amd.com 3210497Ssteve.reinhardt@amd.com#ifndef __MEM_RUBY_COMMON_SET_HH__ 3310497Ssteve.reinhardt@amd.com#define __MEM_RUBY_COMMON_SET_HH__ 3410497Ssteve.reinhardt@amd.com 3510497Ssteve.reinhardt@amd.com#include <iostream> 3610497Ssteve.reinhardt@amd.com#include <limits> 3710497Ssteve.reinhardt@amd.com 3810497Ssteve.reinhardt@amd.com#include "mem/ruby/common/Global.hh" 3910497Ssteve.reinhardt@amd.com#include "mem/ruby/system/NodeID.hh" 4010497Ssteve.reinhardt@amd.com#include "mem/ruby/system/System.hh" 4110497Ssteve.reinhardt@amd.com 4210497Ssteve.reinhardt@amd.comclass Set 4310497Ssteve.reinhardt@amd.com{ 4410497Ssteve.reinhardt@amd.com private: 4510497Ssteve.reinhardt@amd.com int m_nSize; // the number of bits in this set 4610497Ssteve.reinhardt@amd.com int m_nArrayLen; // the number of 32-bit words that are 4710497Ssteve.reinhardt@amd.com // held in the array 4810497Ssteve.reinhardt@amd.com 4910497Ssteve.reinhardt@amd.com // Changed 5/24/05 for static allocation of array 5010497Ssteve.reinhardt@amd.com // note that "long" corresponds to 32 bits on a 32-bit machine, 5110497Ssteve.reinhardt@amd.com // 64 bits if the -m64 parameter is passed to g++, which it is 5210497Ssteve.reinhardt@amd.com // for an AMD opteron under our configuration 5310497Ssteve.reinhardt@amd.com 5410497Ssteve.reinhardt@amd.com long *m_p_nArray; // an word array to hold the bits in the set 5510497Ssteve.reinhardt@amd.com long m_p_nArray_Static[NUMBER_WORDS_PER_SET]; 5610497Ssteve.reinhardt@amd.com 5710497Ssteve.reinhardt@amd.com static const int LONG_BITS = std::numeric_limits<long>::digits + 1; 5810497Ssteve.reinhardt@amd.com static const int INDEX_SHIFT = LONG_BITS == 64 ? 6 : 5; 5910497Ssteve.reinhardt@amd.com static const int INDEX_MASK = (1 << INDEX_SHIFT) - 1; 6010497Ssteve.reinhardt@amd.com 6110497Ssteve.reinhardt@amd.com void clearExcess(); 6210497Ssteve.reinhardt@amd.com 6310497Ssteve.reinhardt@amd.com public: 6410497Ssteve.reinhardt@amd.com Set(); 6510497Ssteve.reinhardt@amd.com Set(int size); 6610497Ssteve.reinhardt@amd.com Set(const Set& obj); 6710497Ssteve.reinhardt@amd.com ~Set(); 6810497Ssteve.reinhardt@amd.com 6910497Ssteve.reinhardt@amd.com Set& operator=(const Set& obj); 7010497Ssteve.reinhardt@amd.com 7110497Ssteve.reinhardt@amd.com void 7210497Ssteve.reinhardt@amd.com add(NodeID index) 7310497Ssteve.reinhardt@amd.com { 7410497Ssteve.reinhardt@amd.com m_p_nArray[index >> INDEX_SHIFT] |= 7510497Ssteve.reinhardt@amd.com (((unsigned long) 1) << (index & INDEX_MASK)); 7610497Ssteve.reinhardt@amd.com } 7710497Ssteve.reinhardt@amd.com 7810497Ssteve.reinhardt@amd.com void addSet(const Set& set); 7910497Ssteve.reinhardt@amd.com void addRandom(); 8010497Ssteve.reinhardt@amd.com 8110497Ssteve.reinhardt@amd.com void 8210497Ssteve.reinhardt@amd.com remove(NodeID index) 8310497Ssteve.reinhardt@amd.com { 8410497Ssteve.reinhardt@amd.com m_p_nArray[index >> INDEX_SHIFT] &= 8510497Ssteve.reinhardt@amd.com ~(((unsigned long)1) << (index & INDEX_MASK)); 8610497Ssteve.reinhardt@amd.com } 8710497Ssteve.reinhardt@amd.com 8810497Ssteve.reinhardt@amd.com void removeSet(const Set& set); 8910497Ssteve.reinhardt@amd.com 9010497Ssteve.reinhardt@amd.com void 9110497Ssteve.reinhardt@amd.com clear() 9210497Ssteve.reinhardt@amd.com { 9310497Ssteve.reinhardt@amd.com for (int i = 0; i < m_nArrayLen; i++) 9410497Ssteve.reinhardt@amd.com m_p_nArray[i] = 0; 9510497Ssteve.reinhardt@amd.com } 9610497Ssteve.reinhardt@amd.com 9710497Ssteve.reinhardt@amd.com void broadcast(); 9810497Ssteve.reinhardt@amd.com int count() const; 9910497Ssteve.reinhardt@amd.com bool isEqual(const Set& set) const; 10010497Ssteve.reinhardt@amd.com 10110497Ssteve.reinhardt@amd.com // return the logical OR of this set and orSet 10210497Ssteve.reinhardt@amd.com Set OR(const Set& orSet) const; 10310497Ssteve.reinhardt@amd.com 10410497Ssteve.reinhardt@amd.com // return the logical AND of this set and andSet 10510497Ssteve.reinhardt@amd.com Set AND(const Set& andSet) const; 10610497Ssteve.reinhardt@amd.com 10710497Ssteve.reinhardt@amd.com // Returns true if the intersection of the two sets is empty 10810497Ssteve.reinhardt@amd.com bool 10910497Ssteve.reinhardt@amd.com intersectionIsEmpty(const Set& other_set) const 11010497Ssteve.reinhardt@amd.com { 11110497Ssteve.reinhardt@amd.com for (int i = 0; i < m_nArrayLen; i++) 11210497Ssteve.reinhardt@amd.com if (m_p_nArray[i] & other_set.m_p_nArray[i]) 11310497Ssteve.reinhardt@amd.com return false; 11410497Ssteve.reinhardt@amd.com return true; 11510497Ssteve.reinhardt@amd.com } 11610497Ssteve.reinhardt@amd.com 11710497Ssteve.reinhardt@amd.com bool isSuperset(const Set& test) const; 11810497Ssteve.reinhardt@amd.com bool isSubset(const Set& test) const { return test.isSuperset(*this); } 11910497Ssteve.reinhardt@amd.com 12010497Ssteve.reinhardt@amd.com bool 12110497Ssteve.reinhardt@amd.com isElement(NodeID element) const 12210497Ssteve.reinhardt@amd.com { 12310497Ssteve.reinhardt@amd.com return (m_p_nArray[element>>INDEX_SHIFT] & 12410497Ssteve.reinhardt@amd.com (((unsigned long)1) << (element & INDEX_MASK))) != 0; 12510497Ssteve.reinhardt@amd.com } 12610497Ssteve.reinhardt@amd.com 12710497Ssteve.reinhardt@amd.com bool isBroadcast() const; 12810497Ssteve.reinhardt@amd.com bool isEmpty() const; 12910497Ssteve.reinhardt@amd.com 13010497Ssteve.reinhardt@amd.com NodeID smallestElement() const; 13110497Ssteve.reinhardt@amd.com 13210497Ssteve.reinhardt@amd.com void setSize(int size); 13310497Ssteve.reinhardt@amd.com 13410497Ssteve.reinhardt@amd.com NodeID 13510497Ssteve.reinhardt@amd.com elementAt(int index) const 13610497Ssteve.reinhardt@amd.com { 13710497Ssteve.reinhardt@amd.com if (isElement(index)) 13810497Ssteve.reinhardt@amd.com return (NodeID)true; 13910497Ssteve.reinhardt@amd.com else 14010497Ssteve.reinhardt@amd.com return 0; 14110497Ssteve.reinhardt@amd.com } 14210497Ssteve.reinhardt@amd.com 14310497Ssteve.reinhardt@amd.com int getSize() const { return m_nSize; } 14410497Ssteve.reinhardt@amd.com 14510497Ssteve.reinhardt@amd.com void print(std::ostream& out) const; 14610497Ssteve.reinhardt@amd.com}; 14710497Ssteve.reinhardt@amd.com 14810497Ssteve.reinhardt@amd.cominline std::ostream& 14910497Ssteve.reinhardt@amd.comoperator<<(std::ostream& out, const Set& obj) 15010497Ssteve.reinhardt@amd.com{ 15110497Ssteve.reinhardt@amd.com obj.print(out); 15210497Ssteve.reinhardt@amd.com out << std::flush; 15310497Ssteve.reinhardt@amd.com return out; 15410497Ssteve.reinhardt@amd.com} 15510497Ssteve.reinhardt@amd.com 15610497Ssteve.reinhardt@amd.com#endif // __MEM_RUBY_COMMON_SET_HH__ 15710497Ssteve.reinhardt@amd.com