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/config/RubyConfig.hh"
45 #if __amd64__ || __LP64__
54 setSize(RubyConfig::numberOfProcessors());
58 Set::Set(const Set
& obj
) {
62 // copy from the host to this array
63 for(int i
=0; i
<m_nArrayLen
; i
++) {
64 m_p_nArray
[i
] = obj
.m_p_nArray
[i
];
77 if( (m_p_nArray
!= (&m_p_nArray_Static
[0])) && (m_p_nArray
!= NULL
))
84 // * This function should set the bit corresponding to index
88 // void Set::add(NodeID index)
90 // assert(index<m_nSize && index >= 0);
93 // m_p_nArray[index>>5] |= (1 << (index & 0x01F));
95 // m_p_nArray[index>>6] |= (((unsigned long) 1) << (index & 0x03F));
96 // #endif // __32BITS__
101 * This function should set all the bits in the current set
102 * that are already set in the parameter set
104 void Set::addSet(const Set
& set
)
106 assert(getSize()==set
.getSize());
107 for(int i
=0; i
<m_nArrayLen
; i
++) {
108 m_p_nArray
[i
] |= set
.m_p_nArray
[i
];
114 * This function should randomly assign 1 to the bits in the set--
115 * it should not clear the bits bits first, though?
117 void Set::addRandom()
120 for(int i
=0; i
<m_nArrayLen
; i
++) {
121 m_p_nArray
[i
] |= random() ^ (random() << 4); // this ensures that all 32 bits are subject to random effects,
122 // as RAND_MAX typically = 0x7FFFFFFF
125 // now just ensure that no bits over the maximum size were set
127 long mask
= 0x7FFFFFFF;
129 // the number of populated spaces in the higest-order array slot is:
130 // m_nSize % 32, so the uppermost 32 - m_nSize%32 bits should be
133 if((m_nSize
% 32) != 0) {
134 for(int j
=0; j
<32-(m_nSize
&0x01F); j
++) {
135 m_p_nArray
[m_nArrayLen
-1] &= mask
;
140 long mask
= 0x7FFFFFFFFFFFFFFF;
142 // the number of populated spaces in the higest-order array slot is:
143 // m_nSize % 64, so the uppermost 64 - m_nSize%64 bits should be
146 if((m_nSize
% 64) != 0) {
147 for(int j
=0; j
<64-(m_nSize
&0x03F); j
++) {
148 m_p_nArray
[m_nArrayLen
-1] &= mask
;
157 // * This function unsets the bit associated with index
159 // void Set::remove(NodeID index)
161 // assert(index<m_nSize && index>=0);
164 // m_p_nArray[index>>5] &= ~(0x00000001 << (index & 0x01F));
166 // m_p_nArray[index>>6] &= ~(((unsigned long) 0x0000000000000001) << (index & 0x03F));
167 // #endif // __32BITS__
173 * This function clears bits that are =1 in the parameter set
175 void Set::removeSet(const Set
& set
)
178 assert(m_nSize
==set
.m_nSize
);
179 for(int i
=0; i
<m_nArrayLen
; i
++) {
180 m_p_nArray
[i
] &= ~(set
.m_p_nArray
[i
]);
186 // * This function clears all bits in the set
190 // for(int i=0; i<m_nArrayLen; i++) {
191 // m_p_nArray[i] = 0;
196 * this function sets all bits in the set
198 void Set::broadcast()
201 for(int i
=0; i
<m_nArrayLen
; i
++) {
202 m_p_nArray
[i
] = -1; // note that -1 corresponds to all 1's in 2's comp.
205 // now just ensure that no bits over the maximum size were set
207 long mask
= 0x7FFFFFFF;
209 // the number of populated spaces in the higest-order array slot is:
210 // m_nSize % 32, so the uppermost 32 - m_nSize%32 bits should be
213 if((m_nSize
% 32) != 0) {
214 for(int j
=0; j
<32-(m_nSize
&0x01F); j
++) {
215 m_p_nArray
[m_nArrayLen
-1] &= mask
;
220 long mask
= 0x7FFFFFFFFFFFFFFF;
222 // the number of populated spaces in the higest-order array slot is:
223 // m_nSize % 64, so the uppermost 64 - m_nSize%64 bits should be
226 if((m_nSize
% 64) != 0) {
227 for(int j
=0; j
<64-(m_nSize
&0x03F); j
++) {
228 m_p_nArray
[m_nArrayLen
-1] &= mask
;
237 * This function returns the population count of 1's in the set
239 int Set::count() const
243 for( int i
=0; i
<m_nArrayLen
; i
++) {
247 for( int j
=0; j
<32; j
++) {
248 if(m_p_nArray
[i
] & mask
) counter
++;
254 for( int j
=0; j
<64; j
++) { // FIXME - significant performance loss when array population << 64
255 if((m_p_nArray
[i
] & mask
) != 0) {
269 * This function checks for set equality
272 bool Set::isEqual(const Set
& set
) const
274 assert(m_nSize
==set
.m_nSize
);
276 for(int i
=0;i
<m_nArrayLen
;i
++) {
277 if(m_p_nArray
[i
] != set
.m_p_nArray
[i
]) {
286 * This function returns the NodeID (int) of the
289 NodeID
Set::smallestElement() const
293 for( int i
=0; i
<m_nArrayLen
; i
++) {
294 if(m_p_nArray
[i
]!=0) {
295 // the least-set bit must be in here
299 for( int j
=0; j
<32; j
++) {
307 for( int j
=0; j
<64; j
++) {
308 if(x
& 0x0000000000000001) {
316 ERROR_MSG("No smallest element of an empty set.");
320 ERROR_MSG("No smallest element of an empty set.");
326 * this function returns true iff all bits are set
328 bool Set::isBroadcast() const
330 // check the fully-loaded words by equal to 0xffffffff
331 // only the last word may not be fully loaded, it is not
332 // fully loaded iff m_nSize % 32 or 64 !=0 => fully loaded iff
333 // m_nSize % 32 or 64 == 0
336 for(int i
=0; i
< (((m_nSize
% 32)==0) ? m_nArrayLen
: m_nArrayLen
-1); i
++) {
337 if(m_p_nArray
[i
]!=-1) {
342 // now check the last word, which may not be fully loaded
344 for(int j
=0; j
< (m_nSize
% 32); j
++) {
345 if((mask
& m_p_nArray
[m_nArrayLen
-1])==0) {
351 for(int i
=0; i
< (((m_nSize
% 64)==0) ? m_nArrayLen
: m_nArrayLen
-1); i
++) {
352 if(m_p_nArray
[i
]!=-1) {
357 // now check the last word, which may not be fully loaded
359 for(int j
=0; j
< (m_nSize
% 64); j
++) {
360 if((mask
& m_p_nArray
[m_nArrayLen
-1])==0) {
372 * this function returns true iff no bits are set
374 bool Set::isEmpty() const
377 // here we can simply check if all = 0, since we ensure
378 // that "extra slots" are all zero
379 for(int i
=0; i
< m_nArrayLen
; i
++) {
380 if(m_p_nArray
[i
]!=0) {
388 // returns the logical OR of "this" set and orSet
389 Set
Set::OR(const Set
& orSet
) const
392 assert(m_nSize
== orSet
.m_nSize
);
393 for(int i
=0; i
< m_nArrayLen
; i
++) {
394 result
.m_p_nArray
[i
] = m_p_nArray
[i
] | orSet
.m_p_nArray
[i
];
401 // returns the logical AND of "this" set and andSet
402 Set
Set::AND(const Set
& andSet
) const
405 assert(m_nSize
== andSet
.m_nSize
);
407 for(int i
=0; i
< m_nArrayLen
; i
++) {
408 result
.m_p_nArray
[i
] = m_p_nArray
[i
] & andSet
.m_p_nArray
[i
];
414 // // Returns true if the intersection of the two sets is non-empty
415 // bool Set::intersectionIsNotEmpty(const Set& other_set) const
417 // assert(m_nSize == other_set.m_nSize);
418 // for(int i=0; i< m_nArrayLen; i++) {
419 // if(m_p_nArray[i] & other_set.m_p_nArray[i]) {
428 // // Returns true if the intersection of the two sets is empty
429 // bool Set::intersectionIsEmpty(const Set& other_set) const
431 // assert(m_nSize == other_set.m_nSize);
432 // for(int i=0; i< m_nArrayLen; i++) {
433 // if(m_p_nArray[i] & other_set.m_p_nArray[i]) {
443 * Returns false if a bit is set in the parameter set that is
444 * NOT set in this set
446 bool Set::isSuperset(const Set
& test
) const
448 assert(m_nSize
== test
.m_nSize
);
450 for(int i
=0;i
<m_nArrayLen
;i
++) {
451 if(((test
.m_p_nArray
[i
] & m_p_nArray
[i
]) | ~test
.m_p_nArray
[i
]) != -1) {
460 // * Returns true iff this bit is set
462 // bool Set::isElement(NodeID element) const
467 // result = ((m_p_nArray[element>>5] & (0x00000001 << (element & 0x01F)))!=0);
469 // result = ((m_p_nArray[element>>6] & (((unsigned long) 0x0000000000000001) << (element & 0x03F)))!=0);
470 // #endif // __32BITS__
476 * "Supposed" to return the node id of the (n+1)th set
477 * bit, IE n=0 => returns nodeid of first set bit, BUT
478 * since BigSet.cc behaves strangely, this implementation
479 * will behave strangely just for reverse compatability.
481 * Was originally implemented for the flight data recorder
485 // NodeID Set::elementAt(int n) const
487 // if(isElement(n)) return (NodeID) true;
492 // for(int i=0;i<m_nSize;i++) {
493 // if(isElement(i)) match++;
503 void Set::setSize(int size
)
508 m_nArrayLen
= m_nSize
/32 + ((m_nSize
%32==0) ? 0 : 1 );
510 m_nArrayLen
= m_nSize
/64 + ((m_nSize
%64==0) ? 0 : 1 );
513 // decide whether to use dynamic or static alloction
514 if(m_nArrayLen
<=NUMBER_WORDS_PER_SET
) { // constant defined in RubyConfig.h
515 // its OK to use the static allocation, and it will
516 // probably be faster (as m_nArrayLen is already in the
517 // cache and they will probably share the same cache line)
519 // if switching from dyanamic to static allocation (which
520 // is probably rare, but why not be complete?), must delete
521 // the dynamically allocated space
522 if((m_p_nArray
!= NULL
) && (m_p_nArray
!= &m_p_nArray_Static
[0]))
523 delete [] m_p_nArray
;
525 m_p_nArray
= & m_p_nArray_Static
[0];
528 // can't use static allocation...simply not enough room
529 // so dynamically allocate some space
530 if((m_p_nArray
!= NULL
) && (m_p_nArray
!= &m_p_nArray_Static
[0]))
531 delete [] m_p_nArray
;
533 m_p_nArray
= new long[m_nArrayLen
];
539 Set
& Set::operator=(const Set
& obj
) {
545 setSize(obj
.getSize());
547 // copy the elements from obj to this
548 for(int i
=0; i
<m_nArrayLen
; i
++) {
549 m_p_nArray
[i
] = obj
.m_p_nArray
[i
];
556 void Set::print(ostream
& out
) const
558 if(m_p_nArray
==NULL
) {
559 out
<< "[Set {Empty}]";
564 for (int i
=m_nArrayLen
-1; i
>=0; i
--) {
566 sprintf(buff
,"%08X ",m_p_nArray
[i
]);
568 sprintf(buff
,"0x %016llX ",m_p_nArray
[i
]);