Set.hh (6154:6bb54dcb940e) Set.hh (6163:92318648212f)
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

--- 18 unchanged lines hidden (view full) ---

27 * OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
28 */
29
30/*
31 * Set.h
32 *
33 * Description:
34 *
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

--- 18 unchanged lines hidden (view full) ---

27 * OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
28 */
29
30/*
31 * Set.h
32 *
33 * Description:
34 *
35 * $Id$
35 * $Id: BigSet.h 1.6 05/01/19 13:12:25-06:00 mikem@maya.cs.wisc.edu $
36 *
37 */
38
36 *
37 */
38
39// Define this to use the BigSet class which is slower, but supports
40// sets of size larger than 32.
39// modified by Dan Gibson on 05/20/05 to accomidate FASTER
40// >32 set lengths, using an array of ints w/ 32 bits/int
41
41
42// #define BIGSET
42// NOTE: Never include this file directly, this should only be
43// included from Set.h
43
44
44#define OPTBIGSET
45
46#ifdef OPTBIGSET
47#include "mem/ruby/common/OptBigSet.hh"
48#else
49
50#ifdef BIGSET
51#include "mem/ruby/common/BigSet.hh" // code to supports sets larger than 32
52#else
53
54#ifndef SET_H
55#define SET_H
56
57#include "mem/ruby/common/Global.hh"
58#include "mem/gems_common/Vector.hh"
59#include "mem/ruby/system/NodeID.hh"
60#include "mem/ruby/config/RubyConfig.hh"
61
45#ifndef SET_H
46#define SET_H
47
48#include "mem/ruby/common/Global.hh"
49#include "mem/gems_common/Vector.hh"
50#include "mem/ruby/system/NodeID.hh"
51#include "mem/ruby/config/RubyConfig.hh"
52
53// gibson 05/20/05
54// enum PresenceBit {NotPresent, Present};
55
62class Set {
63public:
64 // Constructors
65 // creates and empty set
66 Set();
56class Set {
57public:
58 // Constructors
59 // creates and empty set
60 Set();
67 Set(int size);
61 Set (int size);
68
69 // used during the replay mechanism
70 // Set(const char *str);
71
62
63 // used during the replay mechanism
64 // Set(const char *str);
65
72 // Set(const Set& obj);
73 // Set& operator=(const Set& obj);
66 Set(const Set& obj);
67 Set& operator=(const Set& obj);
74
75 // Destructor
68
69 // Destructor
76 // ~Set();
70 ~Set();
77
78 // Public Methods
79
71
72 // Public Methods
73
80 void add(NodeID newElement);
74 inline void add(NodeID index)
75 {
76#ifdef __32BITS__
77 m_p_nArray[index>>5] |= (1 << (index & 0x01F));
78#else
79 m_p_nArray[index>>6] |= (((unsigned long) 1) << (index & 0x03F));
80#endif // __32BITS__
81 }
82
81 void addSet(const Set& set);
82 void addRandom();
83 void addSet(const Set& set);
84 void addRandom();
83 void remove(NodeID newElement);
85
86 inline void remove(NodeID index)
87 {
88#ifdef __32BITS__
89 m_p_nArray[index>>5] &= ~(0x00000001 << (index & 0x01F));
90#else
91 m_p_nArray[index>>6] &= ~(((unsigned long) 0x0000000000000001) << (index & 0x03F));
92#endif // __32BITS__
93 }
94
95
84 void removeSet(const Set& set);
96 void removeSet(const Set& set);
85 void clear();
97
98 inline void clear() { for(int i=0; i<m_nArrayLen; i++) m_p_nArray[i] = 0; }
99
86 void broadcast();
87 int count() const;
100 void broadcast();
101 int count() const;
88 bool isEqual(const Set& set);
102 bool isEqual(const Set& set) const;
89
90 Set OR(const Set& orSet) const; // return the logical OR of this set and orSet
91 Set AND(const Set& andSet) const; // return the logical AND of this set and andSet
92
93 // Returns true if the intersection of the two sets is non-empty
103
104 Set OR(const Set& orSet) const; // return the logical OR of this set and orSet
105 Set AND(const Set& andSet) const; // return the logical AND of this set and andSet
106
107 // Returns true if the intersection of the two sets is non-empty
94 bool intersectionIsNotEmpty(const Set& other_set) const;
108 inline bool intersectionIsNotEmpty(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 true;
113 }
114 }
115 return false;
116 }
95
96 // Returns true if the intersection of the two sets is empty
117
118 // Returns true if the intersection of the two sets is empty
97 bool intersectionIsEmpty(const Set& other_set) const;
119 inline bool intersectionIsEmpty(const Set& other_set) const
120 {
121 for(int i=0; i< m_nArrayLen; i++) {
122 if(m_p_nArray[i] & other_set.m_p_nArray[i]) {
123 return false;
124 }
125 }
126 return true;
127 }
98
99 bool isSuperset(const Set& test) const;
100 bool isSubset(const Set& test) const { return test.isSuperset(*this); }
128
129 bool isSuperset(const Set& test) const;
130 bool isSubset(const Set& test) const { return test.isSuperset(*this); }
101 bool isElement(NodeID element) const;
131
132 inline bool isElement(NodeID element) const
133 {
134#ifdef __32BITS__
135 return ((m_p_nArray[element>>5] & (0x00000001 << (element & 0x01F)))!=0);
136#else
137 return ((m_p_nArray[element>>6] & (((unsigned long) 0x0000000000000001) << (element & 0x03F)))!=0);
138#endif // __32BITS__
139
140 }
141
102 bool isBroadcast() const;
103 bool isEmpty() const;
104
105 NodeID smallestElement() const;
106
107 // int size() const;
108 void setSize (int size);
109
110 // get element for a index
142 bool isBroadcast() const;
143 bool isEmpty() const;
144
145 NodeID smallestElement() const;
146
147 // int size() const;
148 void setSize (int size);
149
150 // get element for a index
111 NodeID elementAt(int index);
112 int getSize() const { return m_size; }
151 inline NodeID elementAt(int index) const
152 {
153 if(isElement(index)) return (NodeID) true;
154 else return 0;
155 }
113
156
157 // gibson 05/20/05
158 int getSize() const { return m_nSize; }
159
114 // DEPRECATED METHODS
115 void addToSet(NodeID newElement) { add(newElement); } // Deprecated
116 void removeFromSet(NodeID newElement) { remove(newElement); } // Deprecated
117 void clearSet() { clear(); } // Deprecated
118 void setBroadcast() { broadcast(); } // Deprecated
119 bool presentInSet(NodeID element) const { return isElement(element); } // Deprecated
120
121 void print(ostream& out) const;
122private:
123 // Private Methods
124
125 // Data Members (m_ prefix)
160 // DEPRECATED METHODS
161 void addToSet(NodeID newElement) { add(newElement); } // Deprecated
162 void removeFromSet(NodeID newElement) { remove(newElement); } // Deprecated
163 void clearSet() { clear(); } // Deprecated
164 void setBroadcast() { broadcast(); } // Deprecated
165 bool presentInSet(NodeID element) const { return isElement(element); } // Deprecated
166
167 void print(ostream& out) const;
168private:
169 // Private Methods
170
171 // Data Members (m_ prefix)
126 int m_size;
127 uint32 m_bits; // Set as a bit vector
128 uint32 m_mask; // a 000001111 mask where the number of 1s is equal to m_size
172 // gibson 05/20/05
173 // Vector<uint8> m_bits; // This is an vector of uint8 to reduce the size of the set
129
174
175 int m_nSize; // the number of bits in this set
176 int m_nArrayLen; // the number of 32-bit words that are held in the array
177
178 // Changed 5/24/05 for static allocation of array
179 // note that "long" corresponds to 32 bits on a 32-bit machine,
180 // 64 bits if the -m64 parameter is passed to g++, which it is
181 // for an AMD opteron under our configuration
182
183 long * m_p_nArray; // an word array to hold the bits in the set
184 long m_p_nArray_Static[NUMBER_WORDS_PER_SET];
130};
131
132// Output operator declaration
133ostream& operator<<(ostream& out, const Set& obj);
134
135// ******************* Definitions *******************
136
137// Output operator definition
138extern inline
139ostream& operator<<(ostream& out, const Set& obj)
140{
141 obj.print(out);
142 out << flush;
143 return out;
144}
145
146#endif //SET_H
185};
186
187// Output operator declaration
188ostream& operator<<(ostream& out, const Set& obj);
189
190// ******************* Definitions *******************
191
192// Output operator definition
193extern inline
194ostream& operator<<(ostream& out, const Set& obj)
195{
196 obj.print(out);
197 out << flush;
198 return out;
199}
200
201#endif //SET_H
147#endif //BIGSET
148#endif //OPTBIGSET
149
202