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.
33 * Description: See Set.hh
35 * $Id: BigSet.cc 1.9 05/01/19 13:12:25-06:00 mikem@maya.cs.wisc.edu $
39 // modified (rewritten) 05/20/05 by Dan Gibson to accomimdate FASTER >32 bit
42 #include "mem/ruby/common/Set.hh"
43 #include "mem/ruby/system/System.hh"
44 #include "mem/ruby/config/RubyConfig.hh"
46 #if __amd64__ || __LP64__
55 setSize(RubySystem::getNumberOfSequencers());
59 Set::Set(const Set
& obj
) {
63 // copy from the host to this array
64 for(int i
=0; i
<m_nArrayLen
; i
++) {
65 m_p_nArray
[i
] = obj
.m_p_nArray
[i
];
78 if( (m_p_nArray
!= (&m_p_nArray_Static
[0])) && (m_p_nArray
!= NULL
))
85 // * This function should set the bit corresponding to index
89 // void Set::add(NodeID index)
91 // assert(index<m_nSize && index >= 0);
94 // m_p_nArray[index>>5] |= (1 << (index & 0x01F));
96 // m_p_nArray[index>>6] |= (((unsigned long) 1) << (index & 0x03F));
97 // #endif // __32BITS__
102 * This function should set all the bits in the current set
103 * that are already set in the parameter set
105 void Set::addSet(const Set
& set
)
107 assert(getSize()==set
.getSize());
108 for(int i
=0; i
<m_nArrayLen
; i
++) {
109 m_p_nArray
[i
] |= set
.m_p_nArray
[i
];
115 * This function should randomly assign 1 to the bits in the set--
116 * it should not clear the bits bits first, though?
118 void Set::addRandom()
121 for(int i
=0; i
<m_nArrayLen
; i
++) {
122 m_p_nArray
[i
] |= random() ^ (random() << 4); // this ensures that all 32 bits are subject to random effects,
123 // as RAND_MAX typically = 0x7FFFFFFF
126 // now just ensure that no bits over the maximum size were set
128 long mask
= 0x7FFFFFFF;
130 // the number of populated spaces in the higest-order array slot is:
131 // m_nSize % 32, so the uppermost 32 - m_nSize%32 bits should be
134 if((m_nSize
% 32) != 0) {
135 for(int j
=0; j
<32-(m_nSize
&0x01F); j
++) {
136 m_p_nArray
[m_nArrayLen
-1] &= mask
;
141 long mask
= 0x7FFFFFFFFFFFFFFF;
143 // the number of populated spaces in the higest-order array slot is:
144 // m_nSize % 64, so the uppermost 64 - m_nSize%64 bits should be
147 if((m_nSize
% 64) != 0) {
148 for(int j
=0; j
<64-(m_nSize
&0x03F); j
++) {
149 m_p_nArray
[m_nArrayLen
-1] &= mask
;
158 // * This function unsets the bit associated with index
160 // void Set::remove(NodeID index)
162 // assert(index<m_nSize && index>=0);
165 // m_p_nArray[index>>5] &= ~(0x00000001 << (index & 0x01F));
167 // m_p_nArray[index>>6] &= ~(((unsigned long) 0x0000000000000001) << (index & 0x03F));
168 // #endif // __32BITS__
174 * This function clears bits that are =1 in the parameter set
176 void Set::removeSet(const Set
& set
)
179 assert(m_nSize
==set
.m_nSize
);
180 for(int i
=0; i
<m_nArrayLen
; i
++) {
181 m_p_nArray
[i
] &= ~(set
.m_p_nArray
[i
]);
187 // * This function clears all bits in the set
191 // for(int i=0; i<m_nArrayLen; i++) {
192 // m_p_nArray[i] = 0;
197 * this function sets all bits in the set
199 void Set::broadcast()
202 for(int i
=0; i
<m_nArrayLen
; i
++) {
203 m_p_nArray
[i
] = -1; // note that -1 corresponds to all 1's in 2's comp.
206 // now just ensure that no bits over the maximum size were set
208 long mask
= 0x7FFFFFFF;
210 // the number of populated spaces in the higest-order array slot is:
211 // m_nSize % 32, so the uppermost 32 - m_nSize%32 bits should be
214 if((m_nSize
% 32) != 0) {
215 for(int j
=0; j
<32-(m_nSize
&0x01F); j
++) {
216 m_p_nArray
[m_nArrayLen
-1] &= mask
;
221 long mask
= 0x7FFFFFFFFFFFFFFF;
223 // the number of populated spaces in the higest-order array slot is:
224 // m_nSize % 64, so the uppermost 64 - m_nSize%64 bits should be
227 if((m_nSize
% 64) != 0) {
228 for(int j
=0; j
<64-(m_nSize
&0x03F); j
++) {
229 m_p_nArray
[m_nArrayLen
-1] &= mask
;
238 * This function returns the population count of 1's in the set
240 int Set::count() const
244 for( int i
=0; i
<m_nArrayLen
; i
++) {
248 for( int j
=0; j
<32; j
++) {
249 if(m_p_nArray
[i
] & mask
) counter
++;
255 for( int j
=0; j
<64; j
++) { // FIXME - significant performance loss when array population << 64
256 if((m_p_nArray
[i
] & mask
) != 0) {
270 * This function checks for set equality
273 bool Set::isEqual(const Set
& set
) const
275 assert(m_nSize
==set
.m_nSize
);
277 for(int i
=0;i
<m_nArrayLen
;i
++) {
278 if(m_p_nArray
[i
] != set
.m_p_nArray
[i
]) {
287 * This function returns the NodeID (int) of the
290 NodeID
Set::smallestElement() const
294 for( int i
=0; i
<m_nArrayLen
; i
++) {
295 if(m_p_nArray
[i
]!=0) {
296 // the least-set bit must be in here
300 for( int j
=0; j
<32; j
++) {
308 for( int j
=0; j
<64; j
++) {
309 if(x
& 0x0000000000000001) {
317 ERROR_MSG("No smallest element of an empty set.");
321 ERROR_MSG("No smallest element of an empty set.");
327 * this function returns true iff all bits are set
329 bool Set::isBroadcast() const
331 // check the fully-loaded words by equal to 0xffffffff
332 // only the last word may not be fully loaded, it is not
333 // fully loaded iff m_nSize % 32 or 64 !=0 => fully loaded iff
334 // m_nSize % 32 or 64 == 0
337 for(int i
=0; i
< (((m_nSize
% 32)==0) ? m_nArrayLen
: m_nArrayLen
-1); i
++) {
338 if(m_p_nArray
[i
]!=-1) {
343 // now check the last word, which may not be fully loaded
345 for(int j
=0; j
< (m_nSize
% 32); j
++) {
346 if((mask
& m_p_nArray
[m_nArrayLen
-1])==0) {
352 for(int i
=0; i
< (((m_nSize
% 64)==0) ? m_nArrayLen
: m_nArrayLen
-1); i
++) {
353 if(m_p_nArray
[i
]!=-1) {
358 // now check the last word, which may not be fully loaded
360 for(int j
=0; j
< (m_nSize
% 64); j
++) {
361 if((mask
& m_p_nArray
[m_nArrayLen
-1])==0) {
373 * this function returns true iff no bits are set
375 bool Set::isEmpty() const
378 // here we can simply check if all = 0, since we ensure
379 // that "extra slots" are all zero
380 for(int i
=0; i
< m_nArrayLen
; i
++) {
381 if(m_p_nArray
[i
]!=0) {
389 // returns the logical OR of "this" set and orSet
390 Set
Set::OR(const Set
& orSet
) const
393 assert(m_nSize
== orSet
.m_nSize
);
394 for(int i
=0; i
< m_nArrayLen
; i
++) {
395 result
.m_p_nArray
[i
] = m_p_nArray
[i
] | orSet
.m_p_nArray
[i
];
402 // returns the logical AND of "this" set and andSet
403 Set
Set::AND(const Set
& andSet
) const
406 assert(m_nSize
== andSet
.m_nSize
);
408 for(int i
=0; i
< m_nArrayLen
; i
++) {
409 result
.m_p_nArray
[i
] = m_p_nArray
[i
] & andSet
.m_p_nArray
[i
];
415 // // Returns true if the intersection of the two sets is non-empty
416 // bool Set::intersectionIsNotEmpty(const Set& other_set) const
418 // assert(m_nSize == other_set.m_nSize);
419 // for(int i=0; i< m_nArrayLen; i++) {
420 // if(m_p_nArray[i] & other_set.m_p_nArray[i]) {
429 // // Returns true if the intersection of the two sets is empty
430 // bool Set::intersectionIsEmpty(const Set& other_set) const
432 // assert(m_nSize == other_set.m_nSize);
433 // for(int i=0; i< m_nArrayLen; i++) {
434 // if(m_p_nArray[i] & other_set.m_p_nArray[i]) {
444 * Returns false if a bit is set in the parameter set that is
445 * NOT set in this set
447 bool Set::isSuperset(const Set
& test
) const
449 assert(m_nSize
== test
.m_nSize
);
451 for(int i
=0;i
<m_nArrayLen
;i
++) {
452 if(((test
.m_p_nArray
[i
] & m_p_nArray
[i
]) | ~test
.m_p_nArray
[i
]) != -1) {
461 // * Returns true iff this bit is set
463 // bool Set::isElement(NodeID element) const
468 // result = ((m_p_nArray[element>>5] & (0x00000001 << (element & 0x01F)))!=0);
470 // result = ((m_p_nArray[element>>6] & (((unsigned long) 0x0000000000000001) << (element & 0x03F)))!=0);
471 // #endif // __32BITS__
477 * "Supposed" to return the node id of the (n+1)th set
478 * bit, IE n=0 => returns nodeid of first set bit, BUT
479 * since BigSet.cc behaves strangely, this implementation
480 * will behave strangely just for reverse compatability.
482 * Was originally implemented for the flight data recorder
486 // NodeID Set::elementAt(int n) const
488 // if(isElement(n)) return (NodeID) true;
493 // for(int i=0;i<m_nSize;i++) {
494 // if(isElement(i)) match++;
504 void Set::setSize(int size
)
509 m_nArrayLen
= m_nSize
/32 + ((m_nSize
%32==0) ? 0 : 1 );
511 m_nArrayLen
= m_nSize
/64 + ((m_nSize
%64==0) ? 0 : 1 );
514 // decide whether to use dynamic or static alloction
515 if(m_nArrayLen
<=NUMBER_WORDS_PER_SET
) { // constant defined in RubyConfig.hh
516 // its OK to use the static allocation, and it will
517 // probably be faster (as m_nArrayLen is already in the
518 // cache and they will probably share the same cache line)
520 // if switching from dyanamic to static allocation (which
521 // is probably rare, but why not be complete?), must delete
522 // the dynamically allocated space
523 if((m_p_nArray
!= NULL
) && (m_p_nArray
!= &m_p_nArray_Static
[0]))
524 delete [] m_p_nArray
;
526 m_p_nArray
= & m_p_nArray_Static
[0];
529 // can't use static allocation...simply not enough room
530 // so dynamically allocate some space
531 if((m_p_nArray
!= NULL
) && (m_p_nArray
!= &m_p_nArray_Static
[0]))
532 delete [] m_p_nArray
;
534 m_p_nArray
= new long[m_nArrayLen
];
540 Set
& Set::operator=(const Set
& obj
) {
546 setSize(obj
.getSize());
548 // copy the elements from obj to this
549 for(int i
=0; i
<m_nArrayLen
; i
++) {
550 m_p_nArray
[i
] = obj
.m_p_nArray
[i
];
557 void Set::print(ostream
& out
) const
559 if(m_p_nArray
==NULL
) {
560 out
<< "[Set {Empty}]";
564 out
<< "[Set (" << m_nSize
<< ") 0x ";
565 for (int i
=m_nArrayLen
-1; i
>=0; i
--) {
567 sprintf(buff
,"%08X ",m_p_nArray
[i
]);
569 sprintf(buff
,"0x %016llX ", (long long)m_p_nArray
[i
]);