2 * Copyright (c) 1999-2008 Mark D. Hill and David A. Wood
5 * Redistribution and use in source and binary forms, with or without
6 * modification, are permitted provided that the following conditions are
7 * met: redistributions of source code must retain the above copyright
8 * notice, this list of conditions and the following disclaimer;
9 * redistributions in binary form must reproduce the above copyright
10 * notice, this list of conditions and the following disclaimer in the
11 * documentation and/or other materials provided with the distribution;
12 * neither the name of the copyright holders nor the names of its
13 * contributors may be used to endorse or promote products derived from
14 * this software without specific prior written permission.
16 * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
17 * "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
18 * LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
19 * A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT
20 * OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
21 * SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT
22 * LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
23 * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
24 * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
25 * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
26 * OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
29 // modified (rewritten) 05/20/05 by Dan Gibson to accomimdate FASTER
32 #include "base/misc.hh"
33 #include "mem/ruby/common/Set.hh"
34 #include "mem/ruby/system/System.hh"
43 Set::Set(const Set
& obj
)
48 // copy from the host to this array
49 for (int i
= 0; i
< m_nArrayLen
; i
++)
50 m_p_nArray
[i
] = obj
.m_p_nArray
[i
];
64 if (m_p_nArray
&& m_p_nArray
!= &m_p_nArray_Static
[0])
72 // now just ensure that no bits over the maximum size were set
74 long mask
= 0x7FFFFFFFFFFFFFFF;
76 long mask
= 0x7FFFFFFF;
79 // the number of populated spaces in the higest-order array slot
80 // is: m_nSize % LONG_BITS, so the uppermost LONG_BITS -
81 // m_nSize%64 bits should be cleared
82 if ((m_nSize
% LONG_BITS
) != 0) {
83 for (int j
= 0; j
< 64 - (m_nSize
& INDEX_MASK
); j
++) {
84 m_p_nArray
[m_nArrayLen
- 1] &= mask
;
92 * This function should set all the bits in the current set that are
93 * already set in the parameter set
96 Set::addSet(const Set
& set
)
98 assert(getSize()==set
.getSize());
99 for (int i
= 0; i
< m_nArrayLen
; i
++)
100 m_p_nArray
[i
] |= set
.m_p_nArray
[i
];
104 * This function should randomly assign 1 to the bits in the set--it
105 * should not clear the bits bits first, though?
111 for (int i
= 0; i
< m_nArrayLen
; i
++) {
112 // this ensures that all 32 bits are subject to random effects,
113 // as RAND_MAX typically = 0x7FFFFFFF
114 m_p_nArray
[i
] |= random() ^ (random() << 4);
120 * This function clears bits that are =1 in the parameter set
123 Set::removeSet(const Set
& set
)
125 assert(m_nSize
== set
.m_nSize
);
126 for (int i
= 0; i
< m_nArrayLen
; i
++)
127 m_p_nArray
[i
] &= ~set
.m_p_nArray
[i
];
131 * this function sets all bits in the set
136 for (int i
= 0; i
< m_nArrayLen
; i
++)
137 m_p_nArray
[i
] = -1; // note that -1 corresponds to all 1's in 2's comp.
143 * This function returns the population count of 1's in the set
151 for (int i
= 0; i
< m_nArrayLen
; i
++) {
154 for (int j
= 0; j
< LONG_BITS
; j
++) {
155 // FIXME - significant performance loss when array
156 // population << LONG_BITS
157 if ((m_p_nArray
[i
] & mask
) != 0) {
168 * This function checks for set equality
171 Set::isEqual(const Set
& set
) const
173 assert(m_nSize
== set
.m_nSize
);
175 for (int i
= 0; i
< m_nArrayLen
; i
++)
176 if (m_p_nArray
[i
] != set
.m_p_nArray
[i
])
183 * This function returns the NodeID (int) of the least set bit
186 Set::smallestElement() const
190 for (int i
= 0; i
< m_nArrayLen
; i
++) {
191 if (m_p_nArray
[i
] != 0) {
192 // the least-set bit must be in here
195 for (int j
= 0; j
< LONG_BITS
; j
++) {
196 if (x
& (unsigned long)1) {
197 return LONG_BITS
* i
+ j
;
203 panic("No smallest element of an empty set.");
207 panic("No smallest element of an empty set.");
211 * this function returns true iff all bits are set
214 Set::isBroadcast() const
216 // check the fully-loaded words by equal to 0xffffffff
217 // only the last word may not be fully loaded, it is not
218 // fully loaded iff m_nSize % 32 or 64 !=0 => fully loaded iff
219 // m_nSize % 32 or 64 == 0
221 int max
= (m_nSize
% LONG_BITS
) == 0 ? m_nArrayLen
: m_nArrayLen
- 1;
222 for (int i
= 0; i
< max
; i
++) {
223 if (m_p_nArray
[i
] != -1) {
228 // now check the last word, which may not be fully loaded
230 for (int j
= 0; j
< (m_nSize
% LONG_BITS
); j
++) {
231 if ((mask
& m_p_nArray
[m_nArrayLen
-1]) == 0) {
241 * this function returns true iff no bits are set
246 // here we can simply check if all = 0, since we ensure
247 // that "extra slots" are all zero
248 for (int i
= 0; i
< m_nArrayLen
; i
++)
255 // returns the logical OR of "this" set and orSet
257 Set::OR(const Set
& orSet
) const
260 assert(m_nSize
== orSet
.m_nSize
);
261 for (int i
= 0; i
< m_nArrayLen
; i
++)
262 result
.m_p_nArray
[i
] = m_p_nArray
[i
] | orSet
.m_p_nArray
[i
];
267 // returns the logical AND of "this" set and andSet
269 Set::AND(const Set
& andSet
) const
272 assert(m_nSize
== andSet
.m_nSize
);
274 for (int i
= 0; i
< m_nArrayLen
; i
++) {
275 result
.m_p_nArray
[i
] = m_p_nArray
[i
] & andSet
.m_p_nArray
[i
];
282 * Returns false if a bit is set in the parameter set that is NOT set
286 Set::isSuperset(const Set
& test
) const
288 assert(m_nSize
== test
.m_nSize
);
290 for (int i
= 0; i
< m_nArrayLen
; i
++)
291 if (((test
.m_p_nArray
[i
] & m_p_nArray
[i
]) | ~test
.m_p_nArray
[i
]) != -1)
298 Set::setSize(int size
)
302 m_nArrayLen
= m_nSize
/ LONG_BITS
+ ((m_nSize
% LONG_BITS
== 0) ? 0 : 1 );
304 // decide whether to use dynamic or static alloction
305 if (m_nArrayLen
<= NUMBER_WORDS_PER_SET
) {
306 // constant defined in RubySystem.hh
307 // its OK to use the static allocation, and it will
308 // probably be faster (as m_nArrayLen is already in the
309 // cache and they will probably share the same cache line)
311 // if switching from dyanamic to static allocation (which
312 // is probably rare, but why not be complete?), must delete
313 // the dynamically allocated space
314 if (m_p_nArray
&& m_p_nArray
!= &m_p_nArray_Static
[0])
315 delete [] m_p_nArray
;
317 m_p_nArray
= &m_p_nArray_Static
[0];
319 // can't use static allocation...simply not enough room
320 // so dynamically allocate some space
321 if (m_p_nArray
&& m_p_nArray
!= &m_p_nArray_Static
[0])
322 delete [] m_p_nArray
;
324 m_p_nArray
= new long[m_nArrayLen
];
331 Set::operator=(const Set
& obj
)
335 setSize(obj
.getSize());
337 // copy the elements from obj to this
338 for (int i
= 0; i
< m_nArrayLen
; i
++)
339 m_p_nArray
[i
] = obj
.m_p_nArray
[i
];
346 Set::print(std::ostream
& out
) const
349 out
<< "[Set {Empty}]";
354 out
<< "[Set (" << m_nSize
<< ") 0x ";
355 for (int i
= m_nArrayLen
- 1; i
>= 0; i
--) {
357 sprintf(buff
,"0x %016llX ", (long long)m_p_nArray
[i
]);
359 sprintf(buff
,"%08X ", m_p_nArray
[i
]);