Source code: com/ubermq/chord/BoundedChordIdentifier.java
1 package com.ubermq.chord;
2
3 /**
4 * Implements an m-bit chord identifier space, where
5 * m ranges from 1 to 30, inclusive. The chord identifier is
6 * stored in an <code>int</code> for compactness and speed
7 * and we use modulo arithmetic to map hash codes
8 * onto the identifier space.
9 */
10 import java.security.*;
11 import java.util.*;
12 import java.util.regex.*;
13
14 public class BoundedChordIdentifier
15 implements ChordIdentifier
16 {
17 private static SecureRandom sr = null;
18 private static final Map factories = new HashMap();
19
20 static {
21 try
22 {
23 sr = SecureRandom.getInstance("SHA1PRNG");
24 }
25 catch (NoSuchAlgorithmException e) {
26 e.printStackTrace();
27 }
28 }
29
30 /**
31 * Returns the bitwise identifier factory given a keyspace
32 * in bits. This provides for 2^bits unique identifier values.
33 */
34 public static ChordIdentifierFactory getFactory(int bits)
35 {
36 ChordIdentifierFactory f = (ChordIdentifierFactory)factories.get(new Integer(bits));
37 if (f == null) {
38 f = new MyFactory(bits);
39 factories.put(new Integer(bits), f);
40 }
41 return f;
42 }
43
44 private static class MyFactory
45 implements ChordIdentifierFactory
46 {
47 private int modulo;
48 private int bits;
49
50 MyFactory(int bits)
51 {
52 this.modulo = (1 << bits);
53 this.bits = bits;
54 }
55
56 public ChordIdentifier getIdentifier(java.net.URI uri)
57 {
58 if (uri.getPath() == null ||
59 uri.getPath().length() == 0)
60 return null;
61 else
62 return new BoundedChordIdentifier(uri.getPath().substring(1), modulo);
63 }
64
65 public ChordIdentifier createIdentifier(Object o)
66 {
67 return new BoundedChordIdentifier(o, modulo);
68 }
69
70 public ChordIdentifier createRandomIdentifier()
71 {
72 return new BoundedChordIdentifier(modulo);
73 }
74
75 public int getFingerTableSize()
76 {
77 // we need to have as many fingers as we
78 // have bits in the identifier space, less one,
79 // because we only need to go halfway around the id circle.
80 return bits - 1;
81 }
82
83 }
84
85 public static final long serialVersionUID = 1L;
86
87 /**
88 * My regex pattern matcher for converting toString representations.
89 */
90 private static final Pattern modPattern = Pattern.compile("(\\d+) mod (\\d+)");
91
92 private final int modulo;
93 private final int value;
94
95 BoundedChordIdentifier(String value, int modulo)
96 {
97 Matcher m = modPattern.matcher(value);
98 if (m.matches()) {
99 this.value = Integer.valueOf(m.group(1)).intValue();
100 this.modulo = Integer.valueOf(m.group(2)).intValue();
101 } else {
102 throw new IllegalArgumentException("unparseable pattern");
103 }
104 }
105
106 BoundedChordIdentifier(int value, int modulo)
107 {
108 this.modulo = modulo;
109 this.value = value;
110
111 if (value % modulo != value)
112 throw new IllegalArgumentException("value specified is outside keyspace.");
113 }
114
115 BoundedChordIdentifier(int modulo)
116 {
117 this.modulo = modulo;
118 this.value = sr.nextInt(modulo);
119 }
120
121 BoundedChordIdentifier(Object o, int modulo)
122 {
123 this.modulo = modulo;
124 this.value = o.hashCode() % modulo;
125 }
126
127 public int hashCode()
128 {
129 int r = 17;
130 r = 37*r + modulo;
131 r = 37*r + value;
132 return r;
133 }
134
135 public int compareTo(Object o)
136 {
137 BoundedChordIdentifier bci = ((BoundedChordIdentifier)o);
138 if (bci.modulo != modulo)
139 throw new ClassCastException("modulos are not the same");
140 else
141 return value - bci.value;
142 }
143
144 public boolean equals(Object o)
145 {
146 if (o instanceof BoundedChordIdentifier)
147 {
148 BoundedChordIdentifier bci = ((BoundedChordIdentifier)o);
149 return (bci.modulo == modulo && bci.value == value);
150 }
151 else return false;
152 }
153
154 public String toString()
155 {
156 return value + " mod " + modulo;
157 }
158
159 /**
160 * Returns the normalized representation of this
161 * identifier relative to other identifiers. The
162 * returned value will be in the interval (0,1).
163 *
164 * @return a normalized identifier representation
165 */
166 public double normal()
167 {
168 return ((double)value) / (modulo - 1);
169 }
170
171 /**
172 * Returns the chord identifier that is <code>l</code>
173 * after this one. This may be a negative number to
174 * go backwards.
175 *
176 * @return a chord identifier that is the specified
177 * interval away.
178 */
179 public ChordIdentifier next(long l)
180 {
181 return new BoundedChordIdentifier((value + (int)(l & 0xffffffff)) % modulo, modulo);
182 }
183
184 /**
185 * Returns the next chord identifier in the
186 * identifier sequence.
187 *
188 * @return a chord identifier that is the next in the
189 * identifier sequence.
190 */
191 public ChordIdentifier next()
192 {
193 return next(1);
194 }
195
196 /**
197 * Returns the identifier for the <code>i</code>th finger
198 * for this identifier. A finger is defined by the Chord
199 * set of algorithms as the identifier that succeeds this
200 * identifier by 2<super>i</super>. However, individual
201 * identifiers can use other finger computations, as appropriate.
202 *
203 * @param i the finger index, from 1 to <code>factory().getFingerTableSize()-1</code>.
204 * The finger at index 0 is defined as the immediate successor to this node.
205 * @return the identifier corresponding to the ith finger.
206 * @throws IllegalArgumentException if i is out of the specified range
207 */
208 public ChordIdentifier nextFinger(int i)
209 {
210 return next(1 << i);
211 }
212
213 /**
214 * Provides the factory instance used to create this
215 * identifier, so that new identifiers can be easily
216 * created from existing ones.
217 * @return an identifier factory
218 */
219 public ChordIdentifierFactory factory()
220 {
221 // determine the i such that m >> i == 1
222 int i;
223 for (i = 0; (modulo >> i) != 1; i++);
224
225 // ok return it as the number of bits
226 return getFactory(i);
227 }
228
229 }