src/mem/ruby/common/Set.cc

   1 /*
   2  * Copyright (c) 1999-2008 Mark D. Hill and David A. Wood
   3  * All rights reserved.
   4  *
   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.
  15  *
  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.
  27  */
  28
  29 // modified (rewritten) 05/20/05 by Dan Gibson to accomimdate FASTER
  30 // >32 bit set sizes
  31
  32 #include "base/misc.hh"
  33 #include "mem/ruby/common/Set.hh"
  34 #include "mem/ruby/system/System.hh"
  35
  36 Set::Set()
  37 {
  38     m_p_nArray = NULL;
  39     m_nArrayLen = 0;
  40     m_nSize = 0;
  41 }
  42
  43 Set::Set(const Set& obj)
  44 {
  45     m_p_nArray = NULL;
  46     setSize(obj.m_nSize);
  47
  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];
  51 }
  52
  53 Set::Set(int size)
  54 {
  55     m_p_nArray = NULL;
  56     m_nArrayLen = 0;
  57     m_nSize = 0;
  58     if (size > 0)
  59         setSize(size);
  60 }
  61
  62 Set::~Set()
  63 {
  64     if (m_p_nArray && m_p_nArray != &m_p_nArray_Static[0])
  65         delete [] m_p_nArray;
  66     m_p_nArray = NULL;
  67 }
  68
  69 void
  70 Set::clearExcess()
  71 {
  72     // now just ensure that no bits over the maximum size were set
  73 #ifdef _LP64
  74     long mask = 0x7FFFFFFFFFFFFFFF;
  75 #else
  76     long mask = 0x7FFFFFFF;
  77 #endif
  78
  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;
  85             mask = mask >> 1;
  86         }
  87     }
  88 }
  89
  90
  91 /*
  92  * This function should set all the bits in the current set that are
  93  * already set in the parameter set
  94  */
  95 void
  96 Set::addSet(const Set& set)
  97 {
  98     assert(getSize()==set.getSize());
  99     for (int i = 0; i < m_nArrayLen; i++)
 100         m_p_nArray[i] |= set.m_p_nArray[i];
 101 }
 102
 103 /*
 104  * This function should randomly assign 1 to the bits in the set--it
 105  * should not clear the bits bits first, though?
 106  */
 107 void
 108 Set::addRandom()
 109 {
 110
 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);
 115     }
 116     clearExcess();
 117 }
 118
 119 /*
 120  * This function clears bits that are =1 in the parameter set
 121  */
 122 void
 123 Set::removeSet(const Set& set)
 124 {
 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];
 128 }
 129
 130 /*
 131  * this function sets all bits in the set
 132  */
 133 void
 134 Set::broadcast()
 135 {
 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.
 138
 139     clearExcess();
 140 }
 141
 142 /*
 143  * This function returns the population count of 1's in the set
 144  */
 145 int
 146 Set::count() const
 147 {
 148     int counter = 0;
 149     long mask;
 150
 151     for (int i = 0; i < m_nArrayLen; i++) {
 152         mask = (long)0x01;
 153
 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) {
 158                 counter++;
 159             }
 160             mask = mask << 1;
 161         }
 162     }
 163
 164     return counter;
 165 }
 166
 167 /*
 168  * This function checks for set equality
 169  */
 170 bool
 171 Set::isEqual(const Set& set) const
 172 {
 173     assert(m_nSize == set.m_nSize);
 174
 175     for (int i = 0; i < m_nArrayLen; i++)
 176         if (m_p_nArray[i] != set.m_p_nArray[i])
 177             return false;
 178
 179     return true;
 180 }
 181
 182 /*
 183  * This function returns the NodeID (int) of the least set bit
 184  */
 185 NodeID
 186 Set::smallestElement() const
 187 {
 188     assert(count() > 0);
 189     long x;
 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
 193             x = m_p_nArray[i];
 194
 195             for (int j = 0; j < LONG_BITS; j++) {
 196                 if (x & (unsigned long)1) {
 197                     return LONG_BITS * i + j;
 198                 }
 199
 200                 x = x >> 1;
 201             }
 202
 203             panic("No smallest element of an empty set.");
 204         }
 205     }
 206
 207     panic("No smallest element of an empty set.");
 208 }
 209
 210 /*
 211  * this function returns true iff all bits are set
 212  */
 213 bool
 214 Set::isBroadcast() const
 215 {
 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
 220
 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) {
 224             return false;
 225         }
 226     }
 227
 228     // now check the last word, which may not be fully loaded
 229     long mask = 1;
 230     for (int j = 0; j < (m_nSize % LONG_BITS); j++) {
 231         if ((mask & m_p_nArray[m_nArrayLen-1]) == 0) {
 232             return false;
 233         }
 234         mask = mask << 1;
 235     }
 236
 237     return true;
 238 }
 239
 240 /*
 241  * this function returns true iff no bits are set
 242  */
 243 bool
 244 Set::isEmpty() const
 245 {
 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++)
 249         if (m_p_nArray[i])
 250             return false;
 251
 252     return true;
 253 }
 254
 255 // returns the logical OR of "this" set and orSet
 256 Set
 257 Set::OR(const Set& orSet) const
 258 {
 259     Set result(m_nSize);
 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];
 263
 264     return result;
 265 }
 266
 267 // returns the logical AND of "this" set and andSet
 268 Set
 269 Set::AND(const Set& andSet) const
 270 {
 271     Set result(m_nSize);
 272     assert(m_nSize == andSet.m_nSize);
 273
 274     for (int i = 0; i < m_nArrayLen; i++) {
 275         result.m_p_nArray[i] = m_p_nArray[i] & andSet.m_p_nArray[i];
 276     }
 277
 278     return result;
 279 }
 280
 281 /*
 282  * Returns false if a bit is set in the parameter set that is NOT set
 283  * in this set
 284  */
 285 bool
 286 Set::isSuperset(const Set& test) const
 287 {
 288     assert(m_nSize == test.m_nSize);
 289
 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)
 292             return false;
 293
 294     return true;
 295 }
 296
 297 void
 298 Set::setSize(int size)
 299 {
 300     m_nSize = size;
 301
 302     m_nArrayLen = m_nSize / LONG_BITS + ((m_nSize % LONG_BITS == 0) ? 0 : 1 );
 303
 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)
 310
 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;
 316
 317         m_p_nArray = &m_p_nArray_Static[0];
 318     } else {
 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;
 323
 324         m_p_nArray = new long[m_nArrayLen];
 325     }
 326
 327     clear();
 328 }
 329
 330 Set&
 331 Set::operator=(const Set& obj)
 332 {
 333     if (this != &obj) {
 334         // resize this item
 335         setSize(obj.getSize());
 336
 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];
 340     }
 341
 342     return *this;
 343 }
 344
 345 void
 346 Set::print(std::ostream& out) const
 347 {
 348     if (!m_p_nArray) {
 349         out << "[Set {Empty}]";
 350         return;
 351     }
 352
 353     char buff[24];
 354     out << "[Set (" << m_nSize << ") 0x ";
 355     for (int i = m_nArrayLen - 1; i >= 0; i--) {
 356 #ifdef _LP64
 357         sprintf(buff,"0x %016llX ", (long long)m_p_nArray[i]);
 358 #else
 359         sprintf(buff,"%08X ", m_p_nArray[i]);
 360 #endif // __32BITS__
 361         out << buff;
 362     }
 363     out << " ]";
 364 }