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