1
2/*
3 * Copyright (c) 1999-2008 Mark D. Hill and David A. Wood
4 * All rights reserved.
5 *
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.
16 *
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.
28 */
29
30/*
31 * Set.hh
32 *
33 * Description:
34 *
35 * $Id: BigSet.hh 1.6 05/01/19 13:12:25-06:00 mikem@maya.cs.wisc.edu $
36 *
37 */
38
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
41
42// NOTE: Never include this file directly, this should only be
43// included from Set.hh
44
45#ifndef SET_H
46#define SET_H
47
| 1
2/*
3 * Copyright (c) 1999-2008 Mark D. Hill and David A. Wood
4 * All rights reserved.
5 *
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.
16 *
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.
28 */
29
30/*
31 * Set.hh
32 *
33 * Description:
34 *
35 * $Id: BigSet.hh 1.6 05/01/19 13:12:25-06:00 mikem@maya.cs.wisc.edu $
36 *
37 */
38
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
41
42// NOTE: Never include this file directly, this should only be
43// included from Set.hh
44
45#ifndef SET_H
46#define SET_H
47
|
| 48#include <iostream>
49
|
48#include "mem/ruby/system/System.hh"
49#include "mem/ruby/common/Global.hh"
50#include "mem/gems_common/Vector.hh"
51#include "mem/ruby/system/NodeID.hh"
52
53// gibson 05/20/05
54// enum PresenceBit {NotPresent, Present};
55
56class Set {
57public:
58 // Constructors
59 // creates and empty set
60 Set();
61 Set (int size);
62
63 // used during the replay mechanism
64 // Set(const char *str);
65
66 Set(const Set& obj);
67 Set& operator=(const Set& obj);
68
69 // Destructor
70 ~Set();
71
72 // Public Methods
73
74 inline void add(NodeID index)
75 {
76#ifdef __32BITS__
77 m_p_nArray[index>>5] |= (1 << (index & 0x01F));
78#else
79 m_p_nArray[index>>6] |= (((unsigned long) 1) << (index & 0x03F));
80#endif // __32BITS__
81 }
82
83 void addSet(const Set& set);
84 void addRandom();
85
86 inline void remove(NodeID index)
87 {
88#ifdef __32BITS__
89 m_p_nArray[index>>5] &= ~(0x00000001 << (index & 0x01F));
90#else
91 m_p_nArray[index>>6] &= ~(((unsigned long) 0x0000000000000001) << (index & 0x03F));
92#endif // __32BITS__
93 }
94
95
96 void removeSet(const Set& set);
97
98 inline void clear() { for(int i=0; i<m_nArrayLen; i++) m_p_nArray[i] = 0; }
99
100 void broadcast();
101 int count() const;
102 bool isEqual(const Set& set) const;
103
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
106
107 // Returns true if the intersection of the two sets is non-empty
108 inline bool intersectionIsNotEmpty(const Set& other_set) const
109 {
110 for(int i=0; i< m_nArrayLen; i++) {
111 if(m_p_nArray[i] & other_set.m_p_nArray[i]) {
112 return true;
113 }
114 }
115 return false;
116 }
117
118 // Returns true if the intersection of the two sets is empty
119 inline bool intersectionIsEmpty(const Set& other_set) const
120 {
121 for(int i=0; i< m_nArrayLen; i++) {
122 if(m_p_nArray[i] & other_set.m_p_nArray[i]) {
123 return false;
124 }
125 }
126 return true;
127 }
128
129 bool isSuperset(const Set& test) const;
130 bool isSubset(const Set& test) const { return test.isSuperset(*this); }
131
132 inline bool isElement(NodeID element) const
133 {
134#ifdef __32BITS__
135 return ((m_p_nArray[element>>5] & (0x00000001 << (element & 0x01F)))!=0);
136#else
137 return ((m_p_nArray[element>>6] & (((unsigned long) 0x0000000000000001) << (element & 0x03F)))!=0);
138#endif // __32BITS__
139
140 }
141
142 bool isBroadcast() const;
143 bool isEmpty() const;
144
145 NodeID smallestElement() const;
146
147 // int size() const;
148 void setSize (int size);
149
150 // get element for a index
151 inline NodeID elementAt(int index) const
152 {
153 if(isElement(index)) return (NodeID) true;
154 else return 0;
155 }
156
157 // gibson 05/20/05
158 int getSize() const { return m_nSize; }
159
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
166
| 50#include "mem/ruby/system/System.hh"
51#include "mem/ruby/common/Global.hh"
52#include "mem/gems_common/Vector.hh"
53#include "mem/ruby/system/NodeID.hh"
54
55// gibson 05/20/05
56// enum PresenceBit {NotPresent, Present};
57
58class Set {
59public:
60 // Constructors
61 // creates and empty set
62 Set();
63 Set (int size);
64
65 // used during the replay mechanism
66 // Set(const char *str);
67
68 Set(const Set& obj);
69 Set& operator=(const Set& obj);
70
71 // Destructor
72 ~Set();
73
74 // Public Methods
75
76 inline void add(NodeID index)
77 {
78#ifdef __32BITS__
79 m_p_nArray[index>>5] |= (1 << (index & 0x01F));
80#else
81 m_p_nArray[index>>6] |= (((unsigned long) 1) << (index & 0x03F));
82#endif // __32BITS__
83 }
84
85 void addSet(const Set& set);
86 void addRandom();
87
88 inline void remove(NodeID index)
89 {
90#ifdef __32BITS__
91 m_p_nArray[index>>5] &= ~(0x00000001 << (index & 0x01F));
92#else
93 m_p_nArray[index>>6] &= ~(((unsigned long) 0x0000000000000001) << (index & 0x03F));
94#endif // __32BITS__
95 }
96
97
98 void removeSet(const Set& set);
99
100 inline void clear() { for(int i=0; i<m_nArrayLen; i++) m_p_nArray[i] = 0; }
101
102 void broadcast();
103 int count() const;
104 bool isEqual(const Set& set) const;
105
106 Set OR(const Set& orSet) const; // return the logical OR of this set and orSet
107 Set AND(const Set& andSet) const; // return the logical AND of this set and andSet
108
109 // Returns true if the intersection of the two sets is non-empty
110 inline bool intersectionIsNotEmpty(const Set& other_set) const
111 {
112 for(int i=0; i< m_nArrayLen; i++) {
113 if(m_p_nArray[i] & other_set.m_p_nArray[i]) {
114 return true;
115 }
116 }
117 return false;
118 }
119
120 // Returns true if the intersection of the two sets is empty
121 inline bool intersectionIsEmpty(const Set& other_set) const
122 {
123 for(int i=0; i< m_nArrayLen; i++) {
124 if(m_p_nArray[i] & other_set.m_p_nArray[i]) {
125 return false;
126 }
127 }
128 return true;
129 }
130
131 bool isSuperset(const Set& test) const;
132 bool isSubset(const Set& test) const { return test.isSuperset(*this); }
133
134 inline bool isElement(NodeID element) const
135 {
136#ifdef __32BITS__
137 return ((m_p_nArray[element>>5] & (0x00000001 << (element & 0x01F)))!=0);
138#else
139 return ((m_p_nArray[element>>6] & (((unsigned long) 0x0000000000000001) << (element & 0x03F)))!=0);
140#endif // __32BITS__
141
142 }
143
144 bool isBroadcast() const;
145 bool isEmpty() const;
146
147 NodeID smallestElement() const;
148
149 // int size() const;
150 void setSize (int size);
151
152 // get element for a index
153 inline NodeID elementAt(int index) const
154 {
155 if(isElement(index)) return (NodeID) true;
156 else return 0;
157 }
158
159 // gibson 05/20/05
160 int getSize() const { return m_nSize; }
161
162 // DEPRECATED METHODS
163 void addToSet(NodeID newElement) { add(newElement); } // Deprecated
164 void removeFromSet(NodeID newElement) { remove(newElement); } // Deprecated
165 void clearSet() { clear(); } // Deprecated
166 void setBroadcast() { broadcast(); } // Deprecated
167 bool presentInSet(NodeID element) const { return isElement(element); } // Deprecated
168
|
167 void print(ostream& out) const;
| 169 void print(std::ostream& out) const;
|
168private:
169 // Private Methods
170
171 // Data Members (m_ prefix)
172 // gibson 05/20/05
173 // Vector<uint8> m_bits; // This is an vector of uint8 to reduce the size of the set
174
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
177
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
182
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];
185};
186
187// Output operator declaration
| 170private:
171 // Private Methods
172
173 // Data Members (m_ prefix)
174 // gibson 05/20/05
175 // Vector<uint8> m_bits; // This is an vector of uint8 to reduce the size of the set
176
177 int m_nSize; // the number of bits in this set
178 int m_nArrayLen; // the number of 32-bit words that are held in the array
179
180 // Changed 5/24/05 for static allocation of array
181 // note that "long" corresponds to 32 bits on a 32-bit machine,
182 // 64 bits if the -m64 parameter is passed to g++, which it is
183 // for an AMD opteron under our configuration
184
185 long * m_p_nArray; // an word array to hold the bits in the set
186 long m_p_nArray_Static[NUMBER_WORDS_PER_SET];
187};
188
189// Output operator declaration
|
188ostream& operator<<(ostream& out, const Set& obj);
| 190std::ostream& operator<<(std::ostream& out, const Set& obj);
|
189
190// ******************* Definitions *******************
191
192// Output operator definition
193extern inline
| 191
192// ******************* Definitions *******************
193
194// Output operator definition
195extern inline
|
194ostream& operator<<(ostream& out, const Set& obj)
| 196std::ostream& operator<<(std::ostream& out, const Set& obj)
|
195{
196 obj.print(out);
| 197{
198 obj.print(out);
|
197 out << flush;
| 199 out << std::flush;
|
198 return out;
199}
200
201#endif //SET_H
202
| 200 return out;
201}
202
203#endif //SET_H
204
|