001: // $Id: VectorTime.java,v 1.6 2006/03/10 15:45:18 belaban Exp $
002:
003: package org.jgroups.protocols;
004:
005: import org.jgroups.Address;
006:
007: import java.util.*;
008:
009: /**
010: * Vector timestamp used in CAUSAL order protocol stack
011: *
012: * @author Vladimir Blagojevic vladimir@cs.yorku.ca
013: * @version $Revision: 1.6 $
014: */
015: public class VectorTime {
016: /**
017: * vector entry sorted map of members
018: */
019: private final TreeMap entries;
020:
021: /**
022: * index of the group member that owns this VectorTime
023: */
024: private int ownerIndex;
025:
026: /**
027: * address of the owner member
028: */
029: private final Address owner;
030:
031: /**
032: * Constructs VectorTime given an adress of a owning group member
033: * @param owner Address of the owner group member
034: */
035: public VectorTime(Address owner) {
036: this .owner = owner;
037: entries = new TreeMap();
038: entries.put(owner, new Integer(0));
039: }
040:
041: /**
042: * Returns Collection containing addresses of other group members from this Vector clock
043: * @return Addresses of other group members
044: */
045: public Collection getMembers() {
046: return entries.keySet();
047: }
048:
049: /**
050: *Returns Vector clock values of this Vector clock
051: * @return values of the Vector clock
052: */
053: public Collection getVectorValues() {
054: return entries.values();
055: }
056:
057: /**
058: *Returns Vector clock values of this Vector clock
059: * @return values of the Vector clock as an array
060: */
061: public int[] getValues() {
062: int count = 0;
063: Collection valuesEntries = entries.values();
064: int values[] = new int[valuesEntries.size()];
065: Iterator iter = valuesEntries.iterator();
066:
067: while (iter.hasNext()) {
068: values[count++] = ((Integer) iter.next()).intValue();
069: }
070: return values;
071: }
072:
073: /**
074: * Incerements owners current vector value by 1
075: */
076: public void increment() {
077: Integer value = (Integer) entries.get(owner);
078: entries.put(owner, new Integer(value.intValue() + 1));
079: }
080:
081: /**
082: * Resets all the values in this vector clock to 0
083: */
084: public void reset() {
085: Address member = null;
086: Set keyEntries = entries.keySet();
087: Iterator iter = keyEntries.iterator();
088: while (iter.hasNext()) {
089: member = (Address) iter.next();
090: entries.put(member, new Integer(0));
091: }
092:
093: }
094:
095: /**
096: * Returns a minimal lightweight representation of this Vector Time
097: * suitable for network transport.
098: * @return lightweight representation of this VectorTime in the
099: * form of TransportedVectorTime object
100: */
101: public TransportedVectorTime getTransportedVectorTime() {
102: return new TransportedVectorTime(ownerIndex, getValues());
103: }
104:
105: /**
106: *<p>
107: *Maxes this VectorTime with the specified TransportedVectorTime.
108: *Updates this VectorTime as follows:
109: *</p>
110: *<p>
111: * for every k:1...n VT(pj)[k] == max(VT(mi)[k],VT(pj)[k])
112: *</p>
113: *
114: * @param other TransportedVectorTime that is max-ed with this VectorTime
115: */
116: public void max(TransportedVectorTime other) {
117: int count = 0;
118: int this VectorValue = 0;
119: int otherVectorValue = 0;
120: Address member = null;
121:
122: int values[] = other.getValues();
123: Set keyEntries = entries.keySet();
124: Iterator iter = keyEntries.iterator();
125:
126: while (iter.hasNext()) {
127: member = (Address) iter.next();
128: this VectorValue = ((Integer) entries.get(member))
129: .intValue();
130: otherVectorValue = values[count++];
131: if (otherVectorValue > this VectorValue)
132: entries.put(member, new Integer(otherVectorValue));
133: }
134:
135: }
136:
137: /**
138: * Determines if the vector clock represented by TransportedVectorTime is
139: * causally next to this VectorTime
140: * @param other TransportedVectorTime representation of vector clock
141: * @return true if the given TransportedVectorTime is the next causal to this VectorTime
142: */
143: public boolean isCausallyNext(TransportedVectorTime other) {
144: int senderIndex = other.getSenderIndex();
145: int receiverIndex = ownerIndex;
146:
147: int[] sender = other.getValues();
148: int[] receiver = getValues();
149:
150: boolean nextCasualFromSender = false;
151: boolean nextCasual = true;
152:
153: if (receiverIndex == senderIndex)
154: return true;
155: for (int k = 0; k < receiver.length; k++) {
156: if ((k == senderIndex) && (sender[k] == receiver[k] + 1)) {
157: nextCasualFromSender = true;
158: continue;
159: }
160: if (k == receiverIndex)
161: continue;
162: if (sender[k] > receiver[k])
163: nextCasual = false;
164: }
165: return (nextCasualFromSender && nextCasual);
166: }
167:
168: /**
169: * Returns owner index in this VectorTime clock
170: * @return index of the owner of this VectorTime or -1 if not found
171: */
172: public int getOwnerIndex() {
173: return indexOf(owner);
174: }
175:
176: /**
177: * Returns index of the given member represented by it's Address
178: * @param member group member represented by this Address
179: * @return index of the group member or -1 if not found
180: */
181: public int indexOf(Address member) {
182: Set set = entries.keySet();
183: Iterator iter = set.iterator();
184: int index = -1;
185: Address temp = null;
186:
187: while (iter.hasNext()) {
188: temp = (Address) iter.next();
189: index++;
190: if (temp.hashCode() == member.hashCode()) {
191: return index;
192: }
193: }
194: return -1;
195: }
196:
197: /**
198: * Merges this VectorTime with new members of the group
199: * VectorTime can possibly either grow or shrink
200: * @param newMembers members of this group
201: */
202: public void merge(Vector newMembers) {
203: if (newMembers.size() > entries.size()) {
204: newMembers.removeAll(entries.keySet());
205: intializeEntries(newMembers);
206: } else {
207: entries.keySet().retainAll(newMembers);
208: }
209: ownerIndex = indexOf(owner);
210: }
211:
212: /**
213: * return String representation of the VectorTime
214: * @return String representation of this VectorTime object
215: */
216: public String toString() {
217: String classType = "VectorTime";
218: int bufferSize = (entries.size() * 2) + classType.length() + 2; //2 for brackets
219: StringBuffer buf = new StringBuffer(bufferSize);
220: buf.append(classType);
221: buf.append(entries);
222: return buf.toString();
223: }
224:
225: /**
226: * Initializes entries of the new members in the VectorTime clock
227: * @param c Collection containing members of this VectorTime that need to be initialized
228: */
229: private void intializeEntries(Collection c) {
230: Iterator iter = c.iterator();
231: while (iter.hasNext()) {
232: Address newMember = (Address) iter.next();
233: entries.put(newMember, new Integer(0));
234: }
235: }
236: }
|