View Javadoc

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