VectorTime


1   // $Id: VectorTime.java,v 1.4 2005/04/12 06:14:35 belaban Exp $
2   
3   
4   package org.jgroups.protocols;
5   
6   import org.jgroups.Address;
7   
8   import java.util.*;
9   
10  
11  
12  /**
13   * Vector timestamp used in CAUSAL order protocol stack
14   *
15   * @author Vladimir Blagojevic vladimir@cs.yorku.ca
16   * @version $Revision: 1.4 $
17   */
18  public class VectorTime
19  {
20     /**
21      * vector entry sorted map of members
22      */
23     private final TreeMap entries;
24  
25     /**
26      * index of the group member that owns this VectorTime
27      */
28     private int ownerIndex;
29  
30     /**
31      * address of the owner member
32      */
33     private final Address owner;
34  
35     /**
36      * Constructs VectorTime given an adress of a owning group member
37      * @param owner Address of the owner group member
38      */
39     public VectorTime(Address owner)
40     {
41        this.owner = owner;
42        entries = new TreeMap();
43        entries.put(owner, new Integer  (0));
44     }
45  
46     /**
47      * Returns Collection containing addresses of other group members from this Vector clock
48      * @return Addresses of other group members
49      */
50     public Collection getMembers()
51     {
52        return entries.keySet();
53     }
54  
55     /**
56      *Returns Vector clock values of this Vector clock
57      * @return values of the Vector clock
58      */
59     public java.util.Collection   getVectorValues()
60     {
61        return entries.values();
62     }
63  
64     /**
65      *Returns Vector clock values of this Vector clock
66      * @return values of the Vector clock as an array
67      */
68     public int[] getValues()
69     {
70        int count = 0;
71        Collection valuesEntries = entries.values();
72        int values [] = new int[valuesEntries.size()];
73        Iterator iter = valuesEntries.iterator();
74  
75        while (iter.hasNext())
76        {
77           values[count++] = ((Integer  ) iter.next()).intValue();
78        }
79        return values;
80     }
81  
82     /**
83      * Incerements owners current vector value by 1
84      */
85     public void increment()
86     {
87        Integer   value = (Integer  ) entries.get(owner);
88        entries.put(owner, new Integer  (value.intValue() + 1));
89     }
90  
91     /**
92      * Resets all the values in this vector clock to 0
93      */
94     public void reset()
95     {
96        Address member = null;
97        Set keyEntries = entries.keySet();
98        Iterator iter = keyEntries.iterator();
99        while (iter.hasNext())
100       {
101          member = (Address) iter.next();
102          entries.put(member, new Integer  (0));
103       }
104 
105    }
106 
107    /**
108     * Returns minimal lightweigth representation of this Vector Time
109     * suitable for network transport
110     * @return lightweight representation of this VectorTime in the
111     * form of TransportedVectorTime object
112     */
113    public TransportedVectorTime getTransportedVectorTime()
114    {
115       return new TransportedVectorTime(ownerIndex, getValues());
116    }
117 
118    /**
119     *<p>
120     *Updates this VectorTime as follows:
121     *</p>
122     *<p>
123     *    for every k:1...n VT(pj)[k] == max(VT(mi)[k],VT(pj)[k])
124     *</p>
125     *
126     * @param other TrasnportedVectorTime that is max-ed with this VectorTime
127     */
128    public void max(TransportedVectorTime other)
129    {
130       int count = 0;
131       int thisVectorValue = 0;
132       int otherVectorValue = 0;
133       Address member = null;
134 
135       int values[] = other.getValues();
136       Set keyEntries = entries.keySet();
137       Iterator iter = keyEntries.iterator();
138 
139 
140       while (iter.hasNext())
141       {
142          member = (Address) iter.next();
143          thisVectorValue = ((Integer  ) entries.get(member)).intValue();
144          otherVectorValue = values[count++];
145          if (otherVectorValue > thisVectorValue)
146             entries.put(member, new Integer  (otherVectorValue));
147       }
148 
149    }
150 
151    /**
152     * Determines if the vector clock represented by TransportedVectorTime is
153     * causally next to this VectorTime
154     * @param other TransportedVectorTime representation of vector clock
155     * @return true if the given TransportedVectorTime is the next causal to this VectorTime
156     */
157    public boolean isCausallyNext(TransportedVectorTime other)
158    {
159       int senderIndex = other.getSenderIndex();
160       int receiverIndex = ownerIndex;
161 
162       int[] sender = other.getValues();
163       int[] receiver = getValues();
164 
165       boolean nextCasualFromSender = false;
166       boolean nextCasual = true;
167 
168       if (receiverIndex == senderIndex) return true;
169       for (int k = 0; k < receiver.length; k++)
170       {
171          if ((k == senderIndex) && (sender[k] == receiver[k] + 1))
172          {
173             nextCasualFromSender = true;
174             continue;
175          }
176          if (k == receiverIndex) continue;
177          if (sender[k] > receiver[k])
178             nextCasual = false;
179       }
180       return (nextCasualFromSender && nextCasual);
181    }
182 
183    /**
184     * Returns owner index in this VectorTime clock
185     * @return index of the owner of this VectorTime or -1 if not found
186     */
187    public int getOwnerIndex()
188    {
189       return indexOf(owner);
190    }
191 
192    /**
193     * Returns index of the given member represented by it's Address
194     * @param member group member represented by this Address
195     * @return index of the group member or -1 if not found
196     */
197    public int indexOf(Address member)
198    {
199       Set set = entries.keySet();
200       Iterator iter = set.iterator();
201       int index = -1;
202       Address temp = null;
203 
204 
205       while (iter.hasNext())
206       {
207          temp = (Address) iter.next();
208          index++;
209          if (temp.hashCode() == member.hashCode())
210          {
211             return index;
212          }
213       }
214       return -1;
215    }
216 
217    /**
218     * Merges this VectorTime with new members of the group
219     * VectorTime can possibly either grow or shrink
220     * @param newMembers members of this group
221     */
222    public void merge(Vector newMembers)
223    {
224       if (newMembers.size() > entries.size())
225       {
226          newMembers.removeAll(entries.keySet());
227          intializeEntries(newMembers);
228       }
229       else
230       {
231          entries.keySet().retainAll(newMembers);
232       }
233       ownerIndex = indexOf(owner);
234    }
235 
236    /**
237     * return String representation of the VectorTime
238     * @return String representation of this VectorTime object
239     */
240    public String   toString()
241    {
242       String   classType = "VectorTime";
243       int bufferSize = (entries.size() *2) + classType.length() +2; //2 for brackets
244       StringBuffer   buf = new StringBuffer  (bufferSize);
245       buf.append(classType);
246       buf.append(entries);
247       return buf.toString();
248    }
249 
250    /**
251     * Initializes entries of the new members in the VectorTime clock
252     * @param c Collection containing members of this VectorTime that need to be initialized
253     */
254    private void intializeEntries(Collection c)
255    {
256       Iterator iter = c.iterator();
257       while (iter.hasNext())
258       {
259          Address newMember = (Address) iter.next();
260          entries.put(newMember, new Integer  (0));
261       }
262    }
263 }
264 
265
A to Z: JavaDoc & Examples Daily Java News & Articles Open Source Projects Open Source Codes Free Computer Books Remove Frame
Popular Tags