Set.hh revision 8608:02d7ac5fb855 
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 <iostream>
36#include <limits>
37
38#include "mem/ruby/common/Global.hh"
39#include "mem/ruby/system/System.hh"
40
41class Set
42{
43  private:
44    int m_nSize;              // the number of bits in this set
45    int m_nArrayLen;          // the number of 32-bit words that are
46                              // held in the array
47
48    // Changed 5/24/05 for static allocation of array
49    // note that "long" corresponds to 32 bits on a 32-bit machine,
50    // 64 bits if the -m64 parameter is passed to g++, which it is
51    // for an AMD opteron under our configuration
52
53    long *m_p_nArray;      // an word array to hold the bits in the set
54    long m_p_nArray_Static[NUMBER_WORDS_PER_SET];
55
56    static const int LONG_BITS = std::numeric_limits<long>::digits + 1;
57    static const int INDEX_SHIFT = LONG_BITS == 64 ? 6 : 5;
58    static const int INDEX_MASK = (1 << INDEX_SHIFT) - 1;
59
60    void clearExcess();
61
62  public:
63    Set();
64    Set(int size);
65    Set(const Set& obj);
66    ~Set();
67
68    Set& operator=(const Set& obj);
69
70    void
71    add(NodeID index)
72    {
73        m_p_nArray[index >> INDEX_SHIFT] |=
74            (((unsigned long) 1) << (index & INDEX_MASK));
75    }
76
77    void addSet(const Set& set);
78    void addRandom();
79
80    void
81    remove(NodeID index)
82    {
83        m_p_nArray[index >> INDEX_SHIFT] &=
84            ~(((unsigned long)1) << (index & INDEX_MASK));
85    }
86
87    void removeSet(const Set& set);
88
89    void
90    clear()
91    {
92        for (int i = 0; i < m_nArrayLen; i++)
93            m_p_nArray[i] = 0;
94    }
95
96    void broadcast();
97    int count() const;
98    bool isEqual(const Set& set) const;
99
100    // return the logical OR of this set and orSet
101    Set OR(const Set& orSet) const;
102
103    // return the logical AND of this set and andSet
104    Set AND(const Set& andSet) const;
105
106    // Returns true if the intersection of the two sets is empty
107    bool
108    intersectionIsEmpty(const Set& other_set) const
109    {
110        for (int i = 0; i < m_nArrayLen; i++)
111            if (m_p_nArray[i] & other_set.m_p_nArray[i])
112                return false;
113        return true;
114    }
115
116    bool isSuperset(const Set& test) const;
117    bool isSubset(const Set& test) const { return test.isSuperset(*this); }
118
119    bool
120    isElement(NodeID element) const
121    {
122        return (m_p_nArray[element>>INDEX_SHIFT] &
123            (((unsigned long)1) << (element & INDEX_MASK))) != 0;
124    }
125
126    bool isBroadcast() const;
127    bool isEmpty() const;
128
129    NodeID smallestElement() const;
130
131    void setSize(int size);
132
133    NodeID
134    elementAt(int index) const
135    {
136        if (isElement(index))
137            return (NodeID)true;
138        else
139            return 0;
140    }
141
142    int getSize() const { return m_nSize; }
143
144    void print(std::ostream& out) const;
145};
146
147inline std::ostream&
148operator<<(std::ostream& out, const Set& obj)
149{
150    obj.print(out);
151    out << std::flush;
152    return out;
153}
154
155#endif // __MEM_RUBY_COMMON_SET_HH__
156