3 * Copyright (c) 1999-2008 Mark D. Hill and David A. Wood
6 * Redistribution and use in source and binary forms, with or without
7 * modification, are permitted provided that the following conditions are
8 * met: redistributions of source code must retain the above copyright
9 * notice, this list of conditions and the following disclaimer;
10 * redistributions in binary form must reproduce the above copyright
11 * notice, this list of conditions and the following disclaimer in the
12 * documentation and/or other materials provided with the distribution;
13 * neither the name of the copyright holders nor the names of its
14 * contributors may be used to endorse or promote products derived from
15 * this software without specific prior written permission.
17 * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
18 * "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
19 * LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
20 * A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT
21 * OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
22 * SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT
23 * LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
24 * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
25 * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
26 * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
27 * OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
35 * $Id: BigSet.h 1.6 05/01/19 13:12:25-06:00 mikem@maya.cs.wisc.edu $
39 // modified by Dan Gibson on 05/20/05 to accomidate FASTER
40 // >32 set lengths, using an array of ints w/ 32 bits/int
42 // NOTE: Never include this file directly, this should only be
43 // included from Set.h
48 #include "mem/ruby/common/Global.hh"
49 #include "mem/gems_common/Vector.hh"
50 #include "mem/ruby/system/NodeID.hh"
51 #include "mem/ruby/config/RubyConfig.hh"
54 // enum PresenceBit {NotPresent, Present};
59 // creates and empty set
63 // used during the replay mechanism
64 // Set(const char *str);
67 Set& operator=(const Set& obj);
74 inline void add(NodeID index)
77 m_p_nArray[index>>5] |= (1 << (index & 0x01F));
79 m_p_nArray[index>>6] |= (((unsigned long) 1) << (index & 0x03F));
83 void addSet(const Set& set);
86 inline void remove(NodeID index)
89 m_p_nArray[index>>5] &= ~(0x00000001 << (index & 0x01F));
91 m_p_nArray[index>>6] &= ~(((unsigned long) 0x0000000000000001) << (index & 0x03F));
96 void removeSet(const Set& set);
98 inline void clear() { for(int i=0; i<m_nArrayLen; i++) m_p_nArray[i] = 0; }
102 bool isEqual(const Set& set) const;
104 Set OR(const Set& orSet) const; // return the logical OR of this set and orSet
105 Set AND(const Set& andSet) const; // return the logical AND of this set and andSet
107 // Returns true if the intersection of the two sets is non-empty
108 inline bool intersectionIsNotEmpty(const Set& other_set) const
110 for(int i=0; i< m_nArrayLen; i++) {
111 if(m_p_nArray[i] & other_set.m_p_nArray[i]) {
118 // Returns true if the intersection of the two sets is empty
119 inline bool intersectionIsEmpty(const Set& other_set) const
121 for(int i=0; i< m_nArrayLen; i++) {
122 if(m_p_nArray[i] & other_set.m_p_nArray[i]) {
129 bool isSuperset(const Set& test) const;
130 bool isSubset(const Set& test) const { return test.isSuperset(*this); }
132 inline bool isElement(NodeID element) const
135 return ((m_p_nArray[element>>5] & (0x00000001 << (element & 0x01F)))!=0);
137 return ((m_p_nArray[element>>6] & (((unsigned long) 0x0000000000000001) << (element & 0x03F)))!=0);
142 bool isBroadcast() const;
143 bool isEmpty() const;
145 NodeID smallestElement() const;
148 void setSize (int size);
150 // get element for a index
151 inline NodeID elementAt(int index) const
153 if(isElement(index)) return (NodeID) true;
158 int getSize() const { return m_nSize; }
160 // DEPRECATED METHODS
161 void addToSet(NodeID newElement) { add(newElement); } // Deprecated
162 void removeFromSet(NodeID newElement) { remove(newElement); } // Deprecated
163 void clearSet() { clear(); } // Deprecated
164 void setBroadcast() { broadcast(); } // Deprecated
165 bool presentInSet(NodeID element) const { return isElement(element); } // Deprecated
167 void print(ostream& out) const;
171 // Data Members (m_ prefix)
173 // Vector<uint8> m_bits; // This is an vector of uint8 to reduce the size of the set
175 int m_nSize; // the number of bits in this set
176 int m_nArrayLen; // the number of 32-bit words that are held in the array
178 // Changed 5/24/05 for static allocation of array
179 // note that "long" corresponds to 32 bits on a 32-bit machine,
180 // 64 bits if the -m64 parameter is passed to g++, which it is
181 // for an AMD opteron under our configuration
183 long * m_p_nArray; // an word array to hold the bits in the set
184 long m_p_nArray_Static[NUMBER_WORDS_PER_SET];
187 // Output operator declaration
188 ostream& operator<<(ostream& out, const Set& obj);
190 // ******************* Definitions *******************
192 // Output operator definition
194 ostream& operator<<(ostream& out, const Set& obj)