src/mem/ruby/common/Set.hh

   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 by Dan Gibson on 05/20/05 to accomidate FASTER
  30 // >32 set lengths, using an array of ints w/ 32 bits/int
  31
  32 #ifndef __MEM_RUBY_COMMON_SET_HH__
  33 #define __MEM_RUBY_COMMON_SET_HH__
  34
  35 #include <bitset>
  36 #include <cassert>
  37 #include <iostream>
  38
  39 #include "base/logging.hh"
  40 #include "mem/ruby/common/TypeDefines.hh"
  41
  42 class Set
  43 {
  44   private:
  45     // Number of bits in use in this set.
  46     // can be defined in build_opts file (default=64).
  47     int m_nSize;
  48     std::bitset<NUMBER_BITS_PER_SET> bits;
  49
  50   public:
  51     Set() : m_nSize(0) {}
  52
  53     Set(int size) : m_nSize(size)
  54     {
  55         if (size > NUMBER_BITS_PER_SET)
  56             fatal("Number of bits(%d) < size specified(%d). "
  57                   "Increase the number of bits and recompile.\n",
  58                   NUMBER_BITS_PER_SET, size);
  59     }
  60
  61     Set(const Set& obj) : m_nSize(obj.m_nSize), bits(obj.bits) {}
  62     ~Set() {}
  63
  64     Set& operator=(const Set& obj)
  65     {
  66         m_nSize = obj.m_nSize;
  67         bits = obj.bits;
  68         return *this;
  69     }
  70
  71     void
  72     add(NodeID index)
  73     {
  74         bits.set(index);
  75     }
  76
  77     /*
  78      * This function should set all the bits in the current set that are
  79      * already set in the parameter set
  80      */
  81     void
  82     addSet(const Set& obj)
  83     {
  84         assert(m_nSize == obj.m_nSize);
  85         bits |= obj.bits;
  86     }
  87
  88     /*
  89      * This function clears bits that are =1 in the parameter set
  90      */
  91     void
  92     remove(NodeID index)
  93     {
  94         bits.reset(index);
  95     }
  96
  97     /*
  98      * This function clears bits that are =1 in the parameter set
  99      */
 100     void
 101     removeSet(const Set& obj)
 102     {
 103         assert(m_nSize == obj.m_nSize);
 104         bits &= (~obj.bits);
 105     }
 106
 107     void clear() { bits.reset(); }
 108
 109     /*
 110      * this function sets all bits in the set
 111      */
 112     void broadcast()
 113     {
 114         bits.set();
 115         for (int j = m_nSize; j < NUMBER_BITS_PER_SET; ++j) {
 116             bits.reset(j);
 117         }
 118     }
 119
 120     /*
 121      * This function returns the population count of 1's in the set
 122      */
 123     int count() const { return bits.count(); }
 124
 125     /*
 126      * This function checks for set equality
 127      */
 128     bool
 129     isEqual(const Set& obj) const
 130     {
 131         assert(m_nSize == obj.m_nSize);
 132         return bits == obj.bits;
 133     }
 134
 135     // return the logical OR of this set and orSet
 136     Set
 137     OR(const Set& obj) const
 138     {
 139         assert(m_nSize == obj.m_nSize);
 140         Set r(m_nSize);
 141         r.bits = bits | obj.bits;
 142         return r;
 143     };
 144
 145     // return the logical AND of this set and andSet
 146     Set
 147     AND(const Set& obj) const
 148     {
 149         assert(m_nSize == obj.m_nSize);
 150         Set r(m_nSize);
 151         r.bits = bits & obj.bits;
 152         return r;
 153     }
 154
 155     // Returns true if the intersection of the two sets is empty
 156     bool
 157     intersectionIsEmpty(const Set& obj) const
 158     {
 159         std::bitset<NUMBER_BITS_PER_SET> r = bits & obj.bits;
 160         return r.none();
 161     }
 162
 163     /*
 164      * Returns false if a bit is set in the parameter set that is NOT set
 165      * in this set
 166      */
 167     bool
 168     isSuperset(const Set& test) const
 169     {
 170         assert(m_nSize == test.m_nSize);
 171         std::bitset<NUMBER_BITS_PER_SET> r = bits | test.bits;
 172         return (r == bits);
 173     }
 174
 175     bool isSubset(const Set& test) const { return test.isSuperset(*this); }
 176
 177     bool isElement(NodeID element) const { return bits.test(element); }
 178
 179     /*
 180      * this function returns true iff all bits in use are set
 181      */
 182     bool
 183     isBroadcast() const
 184     {
 185         return (bits.count() == m_nSize);
 186     }
 187
 188     bool isEmpty() const { return bits.none(); }
 189
 190     NodeID smallestElement() const
 191     {
 192         for (int i = 0; i < m_nSize; ++i) {
 193             if (bits.test(i)) {
 194                 return i;
 195             }
 196         }
 197         panic("No smallest element of an empty set.");
 198     }
 199
 200     bool elementAt(int index) const { return bits[index]; }
 201
 202     int getSize() const { return m_nSize; }
 203
 204     void
 205     setSize(int size)
 206     {
 207         if (size > NUMBER_BITS_PER_SET)
 208             fatal("Number of bits(%d) < size specified(%d). "
 209                   "Increase the number of bits and recompile.\n",
 210                   NUMBER_BITS_PER_SET, size);
 211         m_nSize = size;
 212         bits.reset();
 213     }
 214
 215     void print(std::ostream& out) const
 216     {
 217         out << "[Set (" << m_nSize << "): " << bits << "]";
 218     }
 219 };
 220
 221 inline std::ostream&
 222 operator<<(std::ostream& out, const Set& obj)
 223 {
 224     obj.print(out);
 225     out << std::flush;
 226     return out;
 227 }
 228
 229 #endif // __MEM_RUBY_COMMON_SET_HH__