src/mem/ruby/common/Set.cc

   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.cc
  32  *
  33  * Description: See Set.hh
  34  *
  35  * $Id: BigSet.cc 1.9 05/01/19 13:12:25-06:00 mikem@maya.cs.wisc.edu $
  36  *
  37  */
  38
  39 // modified (rewritten) 05/20/05 by Dan Gibson to accomimdate FASTER >32 bit
  40 // set sizes
  41
  42 #include "mem/ruby/common/Set.hh"
  43 #include "mem/ruby/system/System.hh"
  44 #include "mem/ruby/config/RubyConfig.hh"
  45
  46 #if __amd64__ || __LP64__
  47 #define __64BITS__
  48 #else
  49 #define __32BITS__
  50 #endif
  51
  52 Set::Set()
  53 {
  54   m_p_nArray = NULL;
  55   setSize(RubySystem::getNumberOfSequencers());
  56 }
  57
  58 // copy constructor
  59 Set::Set(const Set& obj) {
  60   m_p_nArray = NULL;
  61   setSize(obj.m_nSize);
  62
  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];
  66   }
  67
  68 }
  69
  70 Set::Set(int size)
  71 {
  72   m_p_nArray = NULL;
  73   assert(size>0);
  74   setSize(size);
  75 }
  76
  77 Set::~Set() {
  78   if( (m_p_nArray != (&m_p_nArray_Static[0])) && (m_p_nArray != NULL))
  79     delete [] m_p_nArray;
  80   m_p_nArray = NULL;
  81 }
  82
  83
  84 // /*
  85 //  * This function should set the bit corresponding to index
  86 //  * to 1.
  87 //  */
  88
  89 // void Set::add(NodeID index)
  90 // {
  91 //   assert(index<m_nSize && index >= 0);
  92
  93 // #ifdef __32BITS__
  94 //   m_p_nArray[index>>5] |= (1 << (index & 0x01F));
  95 // #else
  96 //   m_p_nArray[index>>6] |= (((unsigned long) 1) << (index & 0x03F));
  97 // #endif // __32BITS__
  98
  99 // }
 100
 101 /*
 102  * This function should set all the bits in the current set
 103  * that are already set in the parameter set
 104  */
 105 void Set::addSet(const Set& set)
 106 {
 107   assert(getSize()==set.getSize());
 108   for(int i=0; i<m_nArrayLen; i++) {
 109     m_p_nArray[i] |= set.m_p_nArray[i];
 110   }
 111
 112 }
 113
 114 /*
 115  * This function should randomly assign 1 to the bits in the set--
 116  * it should not clear the bits bits first, though?
 117  */
 118 void Set::addRandom()
 119 {
 120
 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
 124   }
 125
 126   // now just ensure that no bits over the maximum size were set
 127 #ifdef __32BITS__
 128   long mask = 0x7FFFFFFF;
 129
 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
 132   // cleared
 133
 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;
 137       mask = mask >> 1;
 138     }
 139   }
 140 #else
 141   long mask = 0x7FFFFFFFFFFFFFFF;
 142
 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
 145   // cleared
 146
 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;
 150       mask = mask >> 1;
 151     }
 152   }
 153 #endif // __32BITS__
 154
 155 }
 156
 157 // /*
 158 //  * This function unsets the bit associated with index
 159 //  */
 160 // void Set::remove(NodeID index)
 161 // {
 162 //   assert(index<m_nSize && index>=0);
 163
 164 // #ifdef __32BITS__
 165 //   m_p_nArray[index>>5] &= ~(0x00000001         << (index & 0x01F));
 166 // #else
 167 //   m_p_nArray[index>>6] &= ~(((unsigned long) 0x0000000000000001) << (index & 0x03F));
 168 // #endif // __32BITS__
 169
 170 // }
 171
 172
 173 /*
 174  * This function clears bits that are =1 in the parameter set
 175  */
 176 void Set::removeSet(const Set& set)
 177 {
 178
 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]);
 182   }
 183
 184 }
 185
 186 // /*
 187 //  * This function clears all bits in the set
 188 //  */
 189 // void Set::clear()
 190 // {
 191 //   for(int i=0; i<m_nArrayLen; i++) {
 192 //     m_p_nArray[i] = 0;
 193 //   }
 194 // }
 195
 196 /*
 197  * this function sets all bits in the set
 198  */
 199 void Set::broadcast()
 200 {
 201
 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.
 204   }
 205
 206   // now just ensure that no bits over the maximum size were set
 207 #ifdef __32BITS__
 208   long mask = 0x7FFFFFFF;
 209
 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
 212   // cleared
 213
 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;
 217       mask = mask >> 1;
 218     }
 219   }
 220 #else
 221   long mask = 0x7FFFFFFFFFFFFFFF;
 222
 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
 225   // cleared
 226
 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;
 230       mask = mask >> 1;
 231     }
 232   }
 233 #endif // __32BITS__
 234
 235 }
 236
 237 /*
 238  * This function returns the population count of 1's in the set
 239  */
 240 int Set::count() const
 241 {
 242   int counter = 0;
 243   long mask;
 244   for( int i=0; i<m_nArrayLen; i++) {
 245     mask = (long) 0x01;
 246
 247 #ifdef __32BITS__
 248     for( int j=0; j<32; j++) {
 249       if(m_p_nArray[i] & mask) counter++;
 250       mask = mask << 1;
 251     }
 252
 253 #else
 254
 255     for( int j=0; j<64; j++) {  // FIXME - significant performance loss when array population << 64
 256       if((m_p_nArray[i] & mask) != 0) {
 257               counter++;
 258       }
 259       mask = mask << 1;
 260     }
 261
 262 #endif // __32BITS__
 263
 264   }
 265
 266   return counter;
 267 }
 268
 269 /*
 270  * This function checks for set equality
 271  */
 272
 273 bool Set::isEqual(const Set& set) const
 274 {
 275   assert(m_nSize==set.m_nSize);
 276
 277   for(int i=0;i<m_nArrayLen;i++) {
 278     if(m_p_nArray[i] != set.m_p_nArray[i]) {
 279       return false;
 280     }
 281   }
 282
 283   return true;
 284 }
 285
 286 /*
 287  * This function returns the NodeID (int) of the
 288  * least set bit
 289  */
 290 NodeID Set::smallestElement() const
 291 {
 292   assert(count() > 0);
 293   long x;
 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
 297       x = m_p_nArray[i];
 298
 299 #ifdef __32BITS__
 300       for( int j=0; j<32; j++) {
 301         if(x & 0x00000001) {
 302           return 32*i+j;
 303         }
 304
 305         x = x >> 1;
 306       }
 307 #else
 308       for( int j=0; j<64; j++) {
 309         if(x & 0x0000000000000001) {
 310           return 64*i+j;
 311         }
 312
 313         x = x >> 1;
 314       }
 315 #endif // __32BITS__
 316
 317       ERROR_MSG("No smallest element of an empty set.");
 318     }
 319   }
 320
 321   ERROR_MSG("No smallest element of an empty set.");
 322
 323   return 0;
 324 }
 325
 326 /*
 327  * this function returns true iff all bits are set
 328  */
 329 bool Set::isBroadcast() const
 330 {
 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
 335
 336 #ifdef __32BITS__
 337   for(int i=0; i< (((m_nSize % 32)==0) ? m_nArrayLen : m_nArrayLen-1); i++) {
 338     if(m_p_nArray[i]!=-1) {
 339       return false;
 340     }
 341   }
 342
 343   // now check the last word, which may not be fully loaded
 344   long mask = 1;
 345   for(int j=0; j< (m_nSize % 32); j++) {
 346     if((mask & m_p_nArray[m_nArrayLen-1])==0) {
 347       return false;
 348     }
 349     mask = mask << 1;
 350   }
 351 #else
 352   for(int i=0; i< (((m_nSize % 64)==0) ? m_nArrayLen : m_nArrayLen-1); i++) {
 353     if(m_p_nArray[i]!=-1) {
 354       return false;
 355     }
 356   }
 357
 358   // now check the last word, which may not be fully loaded
 359   long mask = 1;
 360   for(int j=0; j< (m_nSize % 64); j++) {
 361     if((mask & m_p_nArray[m_nArrayLen-1])==0) {
 362       return false;
 363     }
 364     mask = mask << 1;
 365   }
 366
 367 #endif // __32BITS__
 368
 369   return true;
 370 }
 371
 372 /*
 373  * this function returns true iff no bits are set
 374  */
 375 bool Set::isEmpty() const
 376 {
 377
 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) {
 382             return false;
 383     }
 384   }
 385
 386   return true;
 387 }
 388
 389 // returns the logical OR of "this" set and orSet
 390 Set Set::OR(const Set& orSet) const
 391 {
 392   Set result(m_nSize);
 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];
 396   }
 397
 398   return result;
 399
 400 }
 401
 402 // returns the logical AND of "this" set and andSet
 403 Set Set::AND(const Set& andSet) const
 404 {
 405   Set result(m_nSize);
 406   assert(m_nSize == andSet.m_nSize);
 407
 408   for(int i=0; i< m_nArrayLen; i++) {
 409     result.m_p_nArray[i] = m_p_nArray[i] & andSet.m_p_nArray[i];
 410   }
 411
 412   return result;
 413 }
 414
 415 // // Returns true if the intersection of the two sets is non-empty
 416 // bool Set::intersectionIsNotEmpty(const Set& other_set) const
 417 // {
 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]) {
 421 //       return true;
 422 //     }
 423 //   }
 424
 425 //   return false;
 426
 427 // }
 428
 429 // // Returns true if the intersection of the two sets is empty
 430 // bool Set::intersectionIsEmpty(const Set& other_set) const
 431 // {
 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]) {
 435 //       return false;
 436 //     }
 437 //   }
 438
 439 //   return true;
 440
 441 // }
 442
 443 /*
 444  * Returns false if a bit is set in the parameter set that is
 445  * NOT set in this set
 446  */
 447 bool Set::isSuperset(const Set& test) const
 448 {
 449   assert(m_nSize == test.m_nSize);
 450
 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) {
 453       return false;
 454     }
 455   }
 456
 457   return true;
 458 }
 459
 460 // /*
 461 //  * Returns true iff this bit is set
 462 //  */
 463 // bool Set::isElement(NodeID element) const
 464 // {
 465 //   bool result;
 466
 467 // #ifdef __32BITS__
 468 //   result = ((m_p_nArray[element>>5] & (0x00000001         << (element & 0x01F)))!=0);
 469 // #else
 470 //   result = ((m_p_nArray[element>>6] & (((unsigned long) 0x0000000000000001) << (element & 0x03F)))!=0);
 471 // #endif // __32BITS__
 472
 473 //   return result;
 474 // }
 475
 476 /*
 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.
 481  *
 482  * Was originally implemented for the flight data recorder
 483  * FDR
 484  */
 485
 486 // NodeID Set::elementAt(int n) const
 487 // {
 488 //   if(isElement(n)) return (NodeID) true;
 489 //   else return 0;
 490
 491 // /*
 492 //   int match = -1;
 493 //   for(int i=0;i<m_nSize;i++) {
 494 //     if(isElement(i)) match++;
 495 //     if(match==n) {
 496 //       return i;
 497 //     }
 498 //   }
 499
 500 //   return -1;
 501 //   */
 502 // }
 503
 504 void Set::setSize(int size)
 505 {
 506   m_nSize = size;
 507
 508 #ifdef __32BITS__
 509   m_nArrayLen = m_nSize/32 + ((m_nSize%32==0) ? 0 : 1 );
 510 #else
 511   m_nArrayLen = m_nSize/64 + ((m_nSize%64==0) ? 0 : 1 );
 512 #endif // __32BITS__
 513
 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)
 519
 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;
 525
 526     m_p_nArray = & m_p_nArray_Static[0];
 527   } else {
 528
 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;
 533
 534     m_p_nArray = new long[m_nArrayLen];
 535   }
 536
 537   clear();
 538 }
 539
 540 Set& Set::operator=(const Set& obj) {
 541   if(this == &obj) {
 542     // do nothing
 543   } else {
 544
 545     // resize this item
 546     setSize(obj.getSize());
 547
 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];
 551     }
 552   }
 553
 554   return *this;
 555 }
 556
 557 void Set::print(ostream& out) const
 558 {
 559   if(m_p_nArray==NULL) {
 560     out << "[Set {Empty}]";
 561     return;
 562   }
 563   char buff[24];
 564   out << "[Set (" << m_nSize << ") 0x ";
 565   for (int i=m_nArrayLen-1; i>=0; i--) {
 566 #ifdef __32BITS__
 567     sprintf(buff,"%08X ",m_p_nArray[i]);
 568 #else
 569     sprintf(buff,"0x %016llX ", (long long)m_p_nArray[i]);
 570 #endif // __32BITS__
 571     out << buff;
 572   }
 573   out << " ]";
 574
 575 }
 576
 577