1 /*
2 * Copyright (c) 1998-2002 The Jgroup Team.
3 *
4 * This program is free software; you can redistribute it and/or modify
5 * it under the terms of the GNU Lesser General Public License version 2 as
6 * published by the Free Software Foundation.
7 *
8 * This program is distributed in the hope that it will be useful,
9 * but WITHOUT ANY WARRANTY; without even the implied warranty of
10 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
11 * GNU Lesser General Public License for more details.
12 *
13 * You should have received a copy of the GNU Lesser General Public License
14 * along with this program; if not, write to the Free Software
15 * Foundation, Inc., 675 Mass Ave, Cambridge, MA 02139, USA.
16 *
17 */
18
19 package jgroup.relacs.daemon;
20
21 import java.util.Collection;
22 import java.util.HashSet;
23 import java.util.Iterator;
24 import java.util.Map;
25 import java.util.Set;
26 import java.util.SortedMap;
27 import java.util.TreeMap;
28
29 import jgroup.core.EndPoint;
30
31 import org.apache.log4j.Logger;
32
33 /**
34 * The <code>Estimate</code> class
35 *
36 * @author Alberto Montresor
37 * @since Jgroup 0.3
38 */
39 final class Estimate
40 {
41
42 ////////////////////////////////////////////////////////////////////////////////////////////
43 // Logger
44 ////////////////////////////////////////////////////////////////////////////////////////////
45
46 /** Obtain logger for this class */
47 private static final Logger log = Logger.getLogger(Estimate.class);
48
49
50 ////////////////////////////////////////////////////////////////////////////////////////////
51 // Fields
52 ////////////////////////////////////////////////////////////////////////////////////////////
53
54 /** Map from EndPoint to HostData objects */
55 private final SortedMap<EndPoint,HostData> estimate = new TreeMap<EndPoint,HostData>();
56
57 /** Set of reachable endpoints that remains to be synchronized */
58 private final Set<EndPoint> toSynchronize = new HashSet<EndPoint>();
59
60 /** True if estimate has changed */
61 private boolean changed;
62
63 /** Send buffer used to notify acknowledgment */
64 private final SendBuffer sbuffer;
65
66
67 ////////////////////////////////////////////////////////////////////////////////////////////
68 // Constructors
69 ////////////////////////////////////////////////////////////////////////////////////////////
70
71 /**
72 * Creates a new estimate by adding the hosts contained in
73 * <code>rset</code>.
74 *
75 * @param sbuffer send buffer used to communicate the list of suspect
76 * to remove
77 * @param thosts the total list of hosts
78 * @param rset the reachable set
79 */
80 Estimate(SendBuffer sbuffer, Map thosts, EndPoint[] rset)
81 {
82 /* Initialize the estimate to empty */
83 this.sbuffer = sbuffer;
84 initEstimate(thosts, rset);
85 }
86
87
88 void reset(Map thosts, EndPoint[] rset)
89 {
90 estimate.clear();
91 toSynchronize.clear();
92 initEstimate(thosts, rset);
93 }
94
95
96 private void initEstimate(Map thosts, EndPoint[] rset)
97 {
98 /* Add the elements in the reachable sets */
99 for (int i=0; i < rset.length; i++) {
100 if (log.isDebugEnabled())
101 log.debug("rset[" +i+ "]: " +rset[i]);
102 HostData host = (HostData) thosts.get(rset[i]);
103 if (host == null) {
104 /*
105 * Note that the system can contain an endpoint for a node that
106 * do not belong to the group; the node may belong to a
107 * different group. We simply ignore those entries.
108 */
109 continue;
110 }
111 if (!host.isLeaving()) {
112 estimate.put(rset[i], host);
113 if (!host.getHost().isLocal())
114 toSynchronize.add(rset[i]);
115 } else {
116 sbuffer.suspect(host);
117 }
118 }
119
120 if (log.isDebugEnabled())
121 log.debug(toString());
122 }
123
124
125 ////////////////////////////////////////////////////////////////////////////////////////////
126 // Methods
127 ////////////////////////////////////////////////////////////////////////////////////////////
128
129 /**
130 * Returns true if the agreed version numbers of the intersection
131 * between the estimate and endpoints (P) are equal. Otherwise,
132 * false is returned.
133 *
134 * See mrecv(ESTIMATE) in Figure 5.8, page 94 of Albertos thesis;
135 * the elseif part.
136 */
137 boolean checkAgreed(EndPoint[] endpoints, int[] agreed)
138 {
139 for (int i=0; i < endpoints.length; i++) {
140 HostData host = estimate.get(endpoints[i]);
141 if (host != null && host.getAgreed() != agreed[i]) {
142 if (log.isDebugEnabled())
143 log.debug(endpoints[i] + ": local agreed=" + host.getAgreed() + ", remote agreed=" + agreed[i]);
144 return false;
145 }
146 }
147 return true;
148 }
149
150
151 /**
152 * Update the agreed values for the given hosts.
153 *
154 * @param hosts The hosts whose agreed value to update
155 * @param agreed The agreed version numbers received with the hosts
156 */
157 void updateAgreed(EndPoint[] hosts, int[] agreed)
158 {
159 if (agreed != null) {
160 for (int i = 0; i < hosts.length; i++) {
161 HostData host = estimate.get(hosts[i]);
162 if (host != null)
163 host.setAgreed(agreed[i]);
164 }
165 }
166 }
167
168
169 /**
170 * Computes the intersection between the current estimate and
171 * the given set of <code>hosts</code>.
172 *
173 * @param hosts
174 * The hosts to be intersected with the current estimate
175 */
176 void intersect(EndPoint[] hosts)
177 {
178 /* Identify the elements to be removed */
179 Set<EndPoint> toRemove = new HashSet<EndPoint>(estimate.keySet());
180 for (EndPoint host : hosts)
181 toRemove.remove(host);
182
183 /* Remove the elements in toRemove */
184 for (EndPoint endpoint : toRemove) {
185 changed = true;
186 sbuffer.suspect(estimate.get(endpoint));
187 estimate.remove(endpoint);
188 toSynchronize.remove(endpoint);
189 }
190 }
191
192
193 /**
194 * Remove the host identified by <code>endpoint</code> from the
195 * estimate.
196 *
197 * @param endpoint
198 * The endpoint to be removed.
199 */
200 void remove(EndPoint endpoint)
201 {
202 /* Remove the endpoint */
203 HostData host = estimate.remove(endpoint);
204 if (host != null) {
205 toSynchronize.remove(endpoint);
206 sbuffer.suspect(host);
207 changed = true;
208 }
209 }
210
211
212 /**
213 * Remove from estimate, those hosts whose endpoint address is
214 * contained in the given <code>set</code>.
215 *
216 * @param set
217 * The endpoints of the hosts to be removed.
218 */
219 void remove(EndPoint[] set)
220 {
221 for (int i=0; i < set.length; i++)
222 remove(set[i]);
223 }
224
225
226 /**
227 * Returns true if the specified endpoint is included in the estimate;
228 * false otherwise.
229 *
230 * @param endpoint the endpoint to check
231 */
232 boolean contains(EndPoint endpoint)
233 {
234 return estimate.containsKey(endpoint);
235 }
236
237 /**
238 * Return the <CODE>HostData</CODE> object associated to the specified endpoint if the
239 * host is contained in the estimate; null otherwise.
240 */
241 HostData get(EndPoint endpoint)
242 {
243 return estimate.get(endpoint);
244 }
245
246 /**
247 * Returns a collection containing the <CODE>HostData</CODE> objects
248 * associated with the hosts included in the estimate.
249 */
250 Collection<HostData> getHosts()
251 {
252 return estimate.values();
253 }
254
255 /**
256 * Returns array of the endpoints contained in this estimate.
257 */
258 EndPoint[] getEndPoints()
259 {
260 return estimate.keySet().toArray(new EndPoint[estimate.size()]);
261 }
262
263 /**
264 * Returns the size of this estimate.
265 */
266 int size()
267 {
268 return estimate.size();
269 }
270
271 /**
272 * Returns true if this estimate is empty; false otherwise.
273 */
274 boolean isEmpty()
275 {
276 return estimate.isEmpty();
277 }
278
279 /**
280 * Returns true if the estimates are equal.
281 */
282 public boolean equals(Object o)
283 {
284 if (o instanceof Estimate) {
285 Estimate e = (Estimate) o;
286 return (e.estimate.equals(this.estimate) && e.toSynchronize.equals(this.toSynchronize));
287 }
288 return false;
289 }
290
291 /**
292 * Add the specified endpoint to the set of synchronized objects.
293 */
294 void setSynchronized(EndPoint endpoint)
295 {
296 toSynchronize.remove(endpoint);
297 }
298
299 /**
300 * Return true if every element is synchronized
301 */
302 boolean isSynchronized()
303 {
304 return toSynchronize.size() == 0;
305 }
306
307 /**
308 * Return true if the last operation on this estimate has changed it.
309 */
310 boolean hasChanged()
311 {
312 boolean ret = changed;
313 changed = false;
314 return ret;
315 }
316
317 /**
318 * Return the endpoint of the host that acts as coordinator.
319 */
320 EndPoint getCoordinator()
321 {
322 if (estimate.isEmpty()) {
323 log.warn("Estimate is empty: " + estimate);
324 return null;
325 }
326 return (EndPoint) estimate.firstKey();
327 }
328
329
330 /**
331 * Returns a string representation of this object
332 */
333 public String toString()
334 {
335 StringBuilder buf = new StringBuilder();
336 buf.append("[Estimate: size=");
337 buf.append(estimate.size());
338 buf.append(", comp={");
339 for (Iterator<EndPoint> iter = estimate.keySet().iterator(); iter.hasNext();) {
340 EndPoint endpoint = iter.next();
341 buf.append(endpoint);
342 if (iter.hasNext())
343 buf.append(", ");
344 }
345 buf.append("}");
346 buf.append(", toSynchronize=");
347 buf.append(toSynchronize);
348 buf.append("]");
349 return buf.toString();
350 }
351
352 } // END Estimate