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 <cstdio>
  33
  34 #include "base/misc.hh"
  35 #include "mem/ruby/common/Set.hh"
  36 #include "mem/ruby/system/System.hh"
  37
  38 Set::Set()
  39 {
  40     m_p_nArray = NULL;
  41     m_nArrayLen = 0;
  42     m_nSize = 0;
  43 }
  44
  45 Set::Set(const Set& obj)
  46 {
  47     m_p_nArray = NULL;
  48     setSize(obj.m_nSize);
  49
  50     // copy from the host to this array
  51     for (int i = 0; i < m_nArrayLen; i++)
  52         m_p_nArray[i] = obj.m_p_nArray[i];
  53 }
  54
  55 Set::Set(int size)
  56 {
  57     m_p_nArray = NULL;
  58     m_nArrayLen = 0;
  59     m_nSize = 0;
  60     if (size > 0)
  61         setSize(size);
  62 }
  63
  64 Set::~Set()
  65 {
  66     if (m_p_nArray && m_p_nArray != &m_p_nArray_Static[0])
  67         delete [] m_p_nArray;
  68     m_p_nArray = NULL;
  69 }
  70
  71 void
  72 Set::clearExcess()
  73 {
  74     // now just ensure that no bits over the maximum size were set
  75 #ifdef _LP64
  76     long mask = 0x7FFFFFFFFFFFFFFF;
  77 #else
  78     long mask = 0x7FFFFFFF;
  79 #endif
  80
  81     // the number of populated spaces in the higest-order array slot
  82     // is: m_nSize % LONG_BITS, so the uppermost LONG_BITS -
  83     // m_nSize%64 bits should be cleared
  84     if ((m_nSize % LONG_BITS) != 0) {
  85         for (int j = 0; j < 64 - (m_nSize & INDEX_MASK); j++) {
  86             m_p_nArray[m_nArrayLen - 1] &= mask;
  87             mask = mask >> 1;
  88         }
  89     }
  90 }
  91
  92
  93 /*
  94  * This function should set all the bits in the current set that are
  95  * already set in the parameter set
  96  */
  97 void
  98 Set::addSet(const Set& set)
  99 {
 100     assert(getSize()==set.getSize());
 101     for (int i = 0; i < m_nArrayLen; i++)
 102         m_p_nArray[i] |= set.m_p_nArray[i];
 103 }
 104
 105 /*
 106  * This function should randomly assign 1 to the bits in the set--it
 107  * should not clear the bits bits first, though?
 108  */
 109 void
 110 Set::addRandom()
 111 {
 112
 113     for (int i = 0; i < m_nArrayLen; i++) {
 114         // this ensures that all 32 bits are subject to random effects,
 115         // as RAND_MAX typically = 0x7FFFFFFF
 116         m_p_nArray[i] |= random() ^ (random() << 4);
 117     }
 118     clearExcess();
 119 }
 120
 121 /*
 122  * This function clears bits that are =1 in the parameter set
 123  */
 124 void
 125 Set::removeSet(const Set& set)
 126 {
 127     assert(m_nSize == set.m_nSize);
 128     for (int i = 0; i < m_nArrayLen; i++)
 129         m_p_nArray[i] &= ~set.m_p_nArray[i];
 130 }
 131
 132 /*
 133  * this function sets all bits in the set
 134  */
 135 void
 136 Set::broadcast()
 137 {
 138     for (int i = 0; i < m_nArrayLen; i++)
 139         m_p_nArray[i] = -1; // note that -1 corresponds to all 1's in 2's comp.
 140
 141     clearExcess();
 142 }
 143
 144 /*
 145  * This function returns the population count of 1's in the set
 146  */
 147 int
 148 Set::count() const
 149 {
 150     int counter = 0;
 151     long mask;
 152
 153     for (int i = 0; i < m_nArrayLen; i++) {
 154         mask = (long)0x01;
 155
 156         for (int j = 0; j < LONG_BITS; j++) {
 157             // FIXME - significant performance loss when array
 158             // population << LONG_BITS
 159             if ((m_p_nArray[i] & mask) != 0) {
 160                 counter++;
 161             }
 162             mask = mask << 1;
 163         }
 164     }
 165
 166     return counter;
 167 }
 168
 169 /*
 170  * This function checks for set equality
 171  */
 172 bool
 173 Set::isEqual(const Set& set) const
 174 {
 175     assert(m_nSize == set.m_nSize);
 176
 177     for (int i = 0; i < m_nArrayLen; i++)
 178         if (m_p_nArray[i] != set.m_p_nArray[i])
 179             return false;
 180
 181     return true;
 182 }
 183
 184 /*
 185  * This function returns the NodeID (int) of the least set bit
 186  */
 187 NodeID
 188 Set::smallestElement() const
 189 {
 190     assert(count() > 0);
 191     long x;
 192     for (int i = 0; i < m_nArrayLen; i++) {
 193         if (m_p_nArray[i] != 0) {
 194             // the least-set bit must be in here
 195             x = m_p_nArray[i];
 196
 197             for (int j = 0; j < LONG_BITS; j++) {
 198                 if (x & (unsigned long)1) {
 199                     return LONG_BITS * i + j;
 200                 }
 201
 202                 x = x >> 1;
 203             }
 204
 205             panic("No smallest element of an empty set.");
 206         }
 207     }
 208
 209     panic("No smallest element of an empty set.");
 210 }
 211
 212 /*
 213  * this function returns true iff all bits are set
 214  */
 215 bool
 216 Set::isBroadcast() const
 217 {
 218     // check the fully-loaded words by equal to 0xffffffff
 219     // only the last word may not be fully loaded, it is not
 220     // fully loaded iff m_nSize % 32 or 64 !=0 => fully loaded iff
 221     // m_nSize % 32 or 64 == 0
 222
 223     int max = (m_nSize % LONG_BITS) == 0 ? m_nArrayLen : m_nArrayLen - 1;
 224     for (int i = 0; i < max; i++) {
 225         if (m_p_nArray[i] != -1) {
 226             return false;
 227         }
 228     }
 229
 230     // now check the last word, which may not be fully loaded
 231     long mask = 1;
 232     for (int j = 0; j < (m_nSize % LONG_BITS); j++) {
 233         if ((mask & m_p_nArray[m_nArrayLen-1]) == 0) {
 234             return false;
 235         }
 236         mask = mask << 1;
 237     }
 238
 239     return true;
 240 }
 241
 242 /*
 243  * this function returns true iff no bits are set
 244  */
 245 bool
 246 Set::isEmpty() const
 247 {
 248     // here we can simply check if all = 0, since we ensure
 249     // that "extra slots" are all zero
 250     for (int i = 0; i < m_nArrayLen ; i++)
 251         if (m_p_nArray[i])
 252             return false;
 253
 254     return true;
 255 }
 256
 257 // returns the logical OR of "this" set and orSet
 258 Set
 259 Set::OR(const Set& orSet) const
 260 {
 261     Set result(m_nSize);
 262     assert(m_nSize == orSet.m_nSize);
 263     for (int i = 0; i < m_nArrayLen; i++)
 264         result.m_p_nArray[i] = m_p_nArray[i] | orSet.m_p_nArray[i];
 265
 266     return result;
 267 }
 268
 269 // returns the logical AND of "this" set and andSet
 270 Set
 271 Set::AND(const Set& andSet) const
 272 {
 273     Set result(m_nSize);
 274     assert(m_nSize == andSet.m_nSize);
 275
 276     for (int i = 0; i < m_nArrayLen; i++) {
 277         result.m_p_nArray[i] = m_p_nArray[i] & andSet.m_p_nArray[i];
 278     }
 279
 280     return result;
 281 }
 282
 283 /*
 284  * Returns false if a bit is set in the parameter set that is NOT set
 285  * in this set
 286  */
 287 bool
 288 Set::isSuperset(const Set& test) const
 289 {
 290     assert(m_nSize == test.m_nSize);
 291
 292     for (int i = 0; i < m_nArrayLen; i++)
 293         if (((test.m_p_nArray[i] & m_p_nArray[i]) | ~test.m_p_nArray[i]) != -1)
 294             return false;
 295
 296     return true;
 297 }
 298
 299 void
 300 Set::setSize(int size)
 301 {
 302     m_nSize = size;
 303     m_nArrayLen = (m_nSize + LONG_BITS - 1) / LONG_BITS;
 304
 305     // decide whether to use dynamic or static alloction
 306     if (m_nArrayLen <= NUMBER_WORDS_PER_SET) {
 307         // constant defined in RubySystem.hh
 308         // its OK to use the static allocation, and it will
 309         // probably be faster (as m_nArrayLen is already in the
 310         // cache and they will probably share the same cache line)
 311
 312         // if switching from dyanamic to static allocation (which
 313         // is probably rare, but why not be complete?), must delete
 314         // the dynamically allocated space
 315         if (m_p_nArray && m_p_nArray != &m_p_nArray_Static[0])
 316             delete [] m_p_nArray;
 317
 318         m_p_nArray = &m_p_nArray_Static[0];
 319     } else {
 320         // can't use static allocation...simply not enough room
 321         // so dynamically allocate some space
 322         if (m_p_nArray && m_p_nArray != &m_p_nArray_Static[0])
 323             delete [] m_p_nArray;
 324
 325         m_p_nArray = new long[m_nArrayLen];
 326     }
 327
 328     clear();
 329 }
 330
 331 Set&
 332 Set::operator=(const Set& obj)
 333 {
 334     if (this != &obj) {
 335         // resize this item
 336         setSize(obj.getSize());
 337
 338         // copy the elements from obj to this
 339         for (int i = 0; i < m_nArrayLen; i++)
 340             m_p_nArray[i] = obj.m_p_nArray[i];
 341     }
 342
 343     return *this;
 344 }
 345
 346 void
 347 Set::print(std::ostream& out) const
 348 {
 349     if (!m_p_nArray) {
 350         out << "[Set {Empty}]";
 351         return;
 352     }
 353
 354     char buff[24];
 355     out << "[Set (" << m_nSize << ")";
 356     for (int i = m_nArrayLen - 1; i >= 0; i--) {
 357         csprintf(buff," 0x%08X", m_p_nArray[i]);
 358         out << buff;
 359     }
 360     out << " ]";
 361 }