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.C
  32  *
  33  * Description: See Set.h
  34  *
  35  * $Id$
  36  *
  37  */
  38
  39 #include "Set.hh"
  40 #include "RubyConfig.hh"
  41
  42 #ifdef OPTBIGSET
  43 #include "OptBigSet.cc"
  44 #else
  45
  46 #ifdef BIGSET
  47 #include "BigSet.cc" // code to supports sets larger than 32
  48 #else
  49
  50 Set::Set()
  51 {
  52   setSize(RubyConfig::numberOfChips());
  53 }
  54
  55 Set::Set(int size)
  56 {
  57   setSize(size);
  58 }
  59
  60 bool Set::isEqual(const Set& set)
  61 {
  62   return (m_bits == set.m_bits);
  63 }
  64
  65 void Set::add(NodeID index)
  66 {
  67   assert((m_bits & m_mask) == m_bits);  // check for any bits outside the range
  68   assert(index < m_size);
  69   m_bits |= (1 << index);
  70   assert((m_bits & m_mask) == m_bits);  // check for any bits outside the range
  71 }
  72
  73 void Set::addSet(const Set& set)
  74 {
  75   assert(m_size == set.m_size);
  76   m_bits |= set.m_bits;
  77   assert((m_bits & m_mask) == m_bits);  // check for any bits outside the range
  78 }
  79
  80 void Set::addRandom()
  81 {
  82   m_bits |= random();
  83   m_bits &= m_mask;
  84   assert((m_bits & m_mask) == m_bits);  // check for any bits outside the range
  85 }
  86
  87 void Set::remove(NodeID index)
  88 {
  89   assert(index < m_size);
  90   m_bits &= ~(1 << index);
  91   assert((m_bits & m_mask) == m_bits);  // check for any bits outside the range
  92 }
  93
  94 void Set::removeSet(const Set& set)
  95 {
  96   assert(m_size == set.m_size);
  97   m_bits &= ~(set.m_bits);
  98   assert((m_bits & m_mask) == m_bits);  // check for any bits outside the range
  99 }
 100
 101 void Set::clear()
 102 {
 103   m_bits = 0;
 104 }
 105
 106 void Set::broadcast()
 107 {
 108   m_bits = m_mask;
 109 }
 110
 111 int Set::count() const
 112 {
 113   int counter = 0;
 114   for (int i=0; i<m_size; i++) {
 115     if ((m_bits & (1 << i)) != 0) {
 116       counter++;
 117     }
 118   }
 119   return counter;
 120 }
 121
 122 NodeID Set::elementAt(int index) {
 123   // count from right to left, index starts from 0
 124   for (int i=0; i<m_size; i++) {
 125     if ((m_bits & (1 << i)) != 0) {
 126       if (index == 0) return i;
 127       index --;
 128     }
 129   }
 130   assert(0); // index out of range
 131   return 0;
 132 }
 133
 134 NodeID Set::smallestElement() const
 135 {
 136   assert(count() > 0);
 137   int counter = 0;
 138   for (int i=0; i<m_size; i++) {
 139     if (isElement(i)) {
 140       return i;
 141     }
 142   }
 143   ERROR_MSG("No smallest element of an empty set.");
 144 }
 145
 146 // Returns true iff all bits are set
 147 bool Set::isBroadcast() const
 148 {
 149   assert((m_bits & m_mask) == m_bits);  // check for any bits outside the range
 150   return (m_mask == m_bits);
 151 }
 152
 153 // Returns true iff no bits are set
 154 bool Set::isEmpty() const
 155 {
 156   assert((m_bits & m_mask) == m_bits);  // check for any bits outside the range
 157   return (m_bits == 0);
 158 }
 159
 160 // returns the logical OR of "this" set and orSet
 161 Set Set::OR(const Set& orSet) const
 162 {
 163   assert(m_size == orSet.m_size);
 164   Set result(m_size);
 165   result.m_bits = (m_bits | orSet.m_bits);
 166   assert((result.m_bits & result.m_mask) == result.m_bits);  // check for any bits outside the range
 167   return result;
 168 }
 169
 170 // returns the logical AND of "this" set and andSet
 171 Set Set::AND(const Set& andSet) const
 172 {
 173   assert(m_size == andSet.m_size);
 174   Set result(m_size);
 175   result.m_bits = (m_bits & andSet.m_bits);
 176   assert((result.m_bits & result.m_mask) == result.m_bits);  // check for any bits outside the range
 177   return result;
 178 }
 179
 180 // Returns true if the intersection of the two sets is non-empty
 181 bool Set::intersectionIsNotEmpty(const Set& other_set) const
 182 {
 183   assert(m_size == other_set.m_size);
 184   return ((m_bits & other_set.m_bits) != 0);
 185 }
 186
 187 // Returns true if the intersection of the two sets is empty
 188 bool Set::intersectionIsEmpty(const Set& other_set) const
 189 {
 190   assert(m_size == other_set.m_size);
 191   return ((m_bits & other_set.m_bits) == 0);
 192 }
 193
 194 bool Set::isSuperset(const Set& test) const
 195 {
 196   assert(m_size == test.m_size);
 197   uint32 temp = (test.m_bits & (~m_bits));
 198   return (temp == 0);
 199 }
 200
 201 bool Set::isElement(NodeID element) const
 202 {
 203   return ((m_bits & (1 << element)) != 0);
 204 }
 205
 206 void Set::setSize(int size)
 207 {
 208   // We're using 32 bit ints, and the 32nd bit acts strangely due to
 209   // signed/unsigned, so restrict the set size to 31 bits.
 210   assert(size < 32);
 211   m_size = size;
 212   m_bits = 0;
 213   m_mask = ~((~0) << m_size);
 214   assert(m_mask != 0);
 215   assert((m_bits & m_mask) == m_bits);  // check for any bits outside the range
 216 }
 217
 218 void Set::print(ostream& out) const
 219 {
 220   out << "[Set (" << m_size << ") ";
 221
 222   for (int i=0; i<m_size; i++) {
 223     out << (bool) isElement(i) << " ";
 224   }
 225   out << "]";
 226 }
 227
 228 #endif // BIGSET
 229
 230 #endif // OPTBIGSET
 231