Java > Open Source Codes > org > netbeans > mdr > persistence > btreeimpl > btreestorage > UUID


1 /*
2  * The contents of this file are subject to the terms of the Common Development
3  * and Distribution License (the License). You may not use this file except in
4  * compliance with the License.
5  *
6  * You can obtain a copy of the License at http://www.netbeans.org/cddl.html
7  * or http://www.netbeans.org/cddl.txt.
8  *
9  * When distributing Covered Code, include this CDDL Header Notice in each file
10  * and include the License file at http://www.netbeans.org/cddl.txt.
11  * If applicable, add the following below the CDDL Header, with the fields
12  * enclosed by brackets [] replaced by your own identifying information:
13  * "Portions Copyrighted [year] [name of copyright owner]"
14  *
15  * The Original Software is NetBeans. The Initial Developer of the Original
16  * Software is Sun Microsystems, Inc. Portions Copyright 1997-2006 Sun
17  * Microsystems, Inc. All Rights Reserved.
18  */
19 package org.netbeans.mdr.persistence.btreeimpl.btreestorage;
20
21 import java.io.*;
22 import java.text.*;
23 import java.util.*;
24
25 /**
26 * UUID is a DCE UUID, that is, a 128-bit universally unique identifier.
27 *
28 * <p> The UUID has the following fields:
29 *
30 * <ol>
31 * <li>
32 * timeLow(ui4) - the low 32 bits of the current time
33 * <li>
34 * timeMid(ui2) - the next 16 bits of the current time
35 * <li>
36 * timeHiAndVersion(ui2) - the high 12 bits of the current time, or'ed
37 * with UUID version information, which occupies the top 4 bits.
38 * <li>
39 * clockSeqHiAndReserved(ui1) - the top 6 bits of the 'Clock Sequence',
40 * which is a random number. The top two bits of this field must be
41 * '10' to be a valid variant 1 UUID.
42 * <li>
43 * clockSeqLow(ui1) - the low 8 bits of the Clock Sequence
44 * <li>
45 * nodeId (u_i1[6]) - intended to be the Ethernet address, which is
46 * guaranteed unique in the world.
47 * </ol>
48 *
49 * <p> Time is expressed as in VMS, i.e. 100's of nanoseconds since a base date,
50 * but the base dat is 10/15/1582, rather than VMS's 1858.
51 * Since 100 nanoseconds is probably much smaller than the system clock
52 * resolution, implementations are allowed to construct many UUIDs per
53 * clock tick by keeping track of a 'time adjustment', which is bumped
54 * for each UUID constructed during a clock tick and added into the UUID's
55 * time fields.
56 *
57 * <p> The intent of the UUID algorithm is to generate a globally unique ID.
58 * The reasoning goes:
59 *
60 * <ol>
61 * <li>
62 * First of all, the nodeId is globally unique, so the only possible
63 * duplications will come from the same machine.
64 * <li>
65 * Second, the time value will be unique for each producer of UUIDs on
66 * a given machine.
67 * <li>
68 * Third (not explicitly stated anywhere I can find), different producers
69 * on a single machine will have different Clock Sequence values. The
70 * implmentations of Clock Sequence I've seen use pid as an input to
71 * the random number generator.
72 * </ol>
73 *
74 * <p> Java has one large problem using this logic: the Ethernet address is
75 * not findable in any documented way. The DCE
76 * implementation on SunOS evidently has had the same problem, since they use
77 * the Internet address instead of the Ethernet address as four bytes of
78 * their node ID (they set the fifth and sixth bytes not to conflict with any
79 * true Ethernet address.)
80 * <p>Forte's version of UUID generation, implemented in the UUID.UUIDGenerator
81 * class, is:
82 *
83 * <ol>
84 * <li>
85 * nodeId:
86 * Generate a 4-byte random number. Like DCE on SunOS, set bytes 5 and 6
87 * to values illegal for an Ethernet address.
88 * <li>
89 * time:
90 * Get a 32-bit time value from System.currentTimeMills(),
91 * and convert it to VMS-like format.
92 * Since the conversion from milliseconds to hundreds of nanoseconds is a
93 * multiplication by 10**4, this leaves the result always 0 mod
94 * 10**4. We add a randomly generated 12-bit number to this, which
95 * leaves room to generate at least 10**4 - 2**12 or about 6000 UUIDs
96 * in the current millisecond.
97 * <li>
98 * clock sequence:
99 * A 14-bit random number
100 * </ol>
101 *
102 */
103 //
104 // CHANGES
105 // 31-mar-2000
106 // (MikeS) Ported from C++ implementation
107
108 public class UUID implements Comparable , Serializable
109 {
110     /** the length of a UUID converted to a string */
111     public static final int STRING_LENGTH = 36;
112
113     /* fields of the UUID, as described above */
114     private int timeLow;
115     private short timeMid;
116     private short timeHiAndVersion;
117     private byte clockSeqHiAndReserved;
118     private byte clockSeqLow;
119     private byte nodeId[];
120
121     /**
122     * Generate a new UUID
123     */
124     public UUID()
125     {
126     nodeId = new byte[6];
127     this.generate();
128     }
129
130     /**
131     * Create a UUID from a string
132     * @param str A string in standard UUID format
133     * @exception java.lang.NumberFormatException Thrown if the string isn't
134     * a valid UUID.
135     */
136     public UUID(String str) throws NumberFormatException
137     {
138     StringTokenizer st = new StringTokenizer(str, "-", true);
139     nodeId = new byte[6];
140     try
141     {
142         timeLow = (int)Long.parseLong(st.nextToken(), 16);
143         if (!st.nextToken().equals("-"))
144         throw new NumberFormatException ();
145         timeMid = (short)Integer.parseInt(st.nextToken(), 16);
146         if (!st.nextToken().equals("-"))
147         throw new NumberFormatException ();
148         timeHiAndVersion = (short)Integer.parseInt(st.nextToken(), 16);
149         if (!st.nextToken().equals("-"))
150         throw new NumberFormatException ();
151         short clock = (short)Integer.parseInt(st.nextToken(), 16);
152         clockSeqHiAndReserved = (byte)((clock >> 8) & 0xFF);
153         clockSeqLow = (byte)(clock & 0xFF);
154         if (!st.nextToken().equals("-"))
155         throw new NumberFormatException ();
156         String node = st.nextToken();
157         for (int i = 0; i < 6; i++)
158         {
159         nodeId[i] = (byte)Integer.parseInt(
160                     node.substring(i*2, i*2+2), 16);
161         }
162     }
163     catch (Exception ex)
164     {
165         throw new NumberFormatException ();
166     }
167     }
168         
169     /**
170     * Get a UUIDGenerator and generate into this
171     */
172     private void generate()
173     {
174     UUIDGenerator gener = UUIDGenerator.create();
175     gener.generate(this);
176     }
177
178     /**
179     * Convert a UUID to a string in standard form:
180     * <p>
181     * XXXXXXXX-XXXX-XXXX-XXXX-XXXXXXXXXXXX
182     * <p>
183     * timeLow-timeMid-timeHiAndVersion-clockSeqAndReserved-nodeId
184     * @return String version of UUID
185     */
186     public String toString()
187     {
188     Object nodeArgs[] = {
189         toHex(nodeId[0]), toHex(nodeId[1]), toHex(nodeId[2]),
190         toHex(nodeId[3]), toHex(nodeId[4]), toHex(nodeId[5])
191                 };
192     String nodeString =
193         MessageFormat.format("{0}{1}{2}{3}{4}{5}", nodeArgs);
194
195     Object args[] = {
196         toHex(timeLow), toHex(timeMid), toHex(timeHiAndVersion),
197         toHex(clockSeqHiAndReserved), toHex(clockSeqLow),
198         nodeString
199             };
200
201     return MessageFormat.format("{0}-{1}-{2}-{3}{4}-{5}", args);
202     }
203
204     /**
205     * Two UUIDs are equal if all of their fields are equal
206     */
207     public boolean equals(Object o)
208     {
209     if (!(o instanceof UUID))
210         return false;
211
212     UUID other = (UUID)o;
213     return (
214         other.timeLow == this.timeLow &&
215         other.timeMid == this.timeMid &&
216         other.timeHiAndVersion == this.timeHiAndVersion &&
217         other.clockSeqHiAndReserved == this.clockSeqHiAndReserved &&
218         other.clockSeqLow == this.clockSeqLow &&
219         other.nodeId[0] == this.nodeId[0] &&
220         other.nodeId[1] == this.nodeId[1] &&
221         other.nodeId[2] == this.nodeId[2] &&
222         other.nodeId[3] == this.nodeId[3] &&
223         other.nodeId[4] == this.nodeId[4] &&
224         other.nodeId[5] == this.nodeId[5]);
225     }
226
227     /**
228     * Orders UUIDs by their field values
229     */
230     public int compareTo(Object o)
231     {
232     if (!(o instanceof UUID))
233         throw new ClassCastException ();
234
235     UUID other = (UUID)o;
236     if (other.timeLow != this.timeLow)
237         return this.timeLow - other.timeLow;
238     if (other.timeMid != this.timeMid)
239         return this.timeMid - other.timeMid;
240     if (other.timeHiAndVersion != this.timeHiAndVersion)
241         return this.timeHiAndVersion - other.timeHiAndVersion;
242     if (other.clockSeqHiAndReserved != this.clockSeqHiAndReserved)
243         return this.clockSeqHiAndReserved - other.clockSeqHiAndReserved;
244     if (other.clockSeqLow != this.clockSeqLow)
245         return this.clockSeqLow - other.clockSeqLow;
246     for (int i = 0; i < 6; i++)
247     {
248         if (other.nodeId[i] != this.nodeId[i])
249         return this.nodeId[i] - other.nodeId[i];
250     }
251     return 0;
252     }
253         
254     /**
255     * Use timeLow for the hashCode, so equal UUIDs hash equal
256     */
257     public int hashCode()
258     {
259     return (int)timeLow;
260     }
261
262     /**
263     * Convert a byte to XX in hex, with leading zeros if need be
264     */
265     private static String toHex(byte num)
266     {
267     return toHex(((int)num & 0xFF), 2);
268     }
269
270     /**
271     * Convert a short to XXXX in hex, with leading zeros if need be
272     */
273     private static String toHex(short num)
274     {
275     return toHex(((int)num & 0xFFFF), 4);
276     }
277
278     /**
279     * Convert an int to XXXXXXX in hex, with leading zeros if need be
280     */
281     private static String toHex(int num)
282     {
283     return toHex(num, 8);
284     }
285
286
287     /**
288     * Convert an int to as many hex digits as specified,
289     * with leading zeros if need be
290     */
291     private static String toHex(int num, int digits)
292     {
293     String hex = Integer.toHexString(num);
294     if (hex.length() < digits)
295     {
296         StringBuffer sb = new StringBuffer ();
297         int toAdd = digits - hex.length();
298         for (int i = 0; i < toAdd; i++)
299         {
300         sb.append('0');
301         }
302         sb.append(hex);
303         hex = sb.toString();
304     }
305     return hex.toUpperCase();
306     }
307         
308
309     /**
310     * Generate a unique UUID. Only one instance of this class is ever
311     * created.
312     * <p>
313     * Random number generators used:
314     * <p>
315     * nodeId is generated once, based on the time the UUIDGenerator is
316     * created and the hashCode of a Random created at that time.
317     * <p>
318     * clockSequence is generated when the UUIDGenerator is created
319     * and again if the system time is ever reset to a time before the
320     * previous UUID generation. It is generated based on the hashcode of
321     * the UUIDGenerator.
322     * <p>
323     * timeAdjust is generated for the first UUID generation in each millisecond,
324     * based on the hashCode of the Thread which generated the UUID.
325     */
326     private static class UUIDGenerator
327     {
328     /** The unique instance of this class */
329     private static UUIDGenerator theGenerator;
330
331     /** random number generators */
332     private Random random1;
333     private Random random2;
334
335     /** The last time a UUID was generated */
336     private long lastTime;
337
338     /**
339     * An adjustment to allow mulitple UUIDs to be generated
340     * within the same millisecond.
341     */
342     private long timeAdjust;
343
344     /**
345     * An adjustment to allow UUIDs to be generated if the system
346     * clock is moved backwards.
347     */
348     private int clockSequence;
349
350     /**
351     * The node Id for this instance.
352     */
353     private byte nodeId[];
354
355     /** The clock sequence is 14 bits */
356     private static final int CLOCK_SEQ_MASK = 0x3FFF;
357
358     /** The UUID version is one bit */
359     private static final int VERSION_BITS = 0x1000;
360
361     /** One bit is reserved */
362     private static final int RESERVED_BITS = 0x0080;
363
364     /** The time adjust is 12 bits */
365     private static final int TIME_ADJUST_MASK = 0x0FFF;
366
367     /** convesion from milliseconds to 10s of nanoseconds */
368     private static final long N100NS_PER_MILLI = 10000;
369
370     /** convert from 1/1/70 to 10/15/1582 */
371     private static final long EPOCH_CVT = 0x1B21DD213814000L;
372
373
374     /** return the singleton UUID generator */
375     public synchronized static UUIDGenerator create()
376     {
377         if (theGenerator == null)
378         theGenerator = new UUIDGenerator();
379         return theGenerator;
380     }
381
382     /** Intitialize the generator's fields */
383     private UUIDGenerator()
384     {
385         random1 = new Random(this.hashCode());
386         random2 = new Random(Thread.currentThread().hashCode());
387         nodeId = new byte[6];
388         initializeNodeId();
389         getClockSequence();
390     }
391
392     /** Generate a new UUID. */
393     public synchronized void generate(UUID uuid)
394     {
395         long now = System.currentTimeMillis();
396
397         while (true)
398         {
399         if (now > lastTime)
400         {
401             /* The easiest case */
402             getTimeAdjust();
403             break;
404         }
405         else if (now < lastTime)
406         {
407             /* Time moved backward! Get a new clock sequence
408              * to avid generating duplicates.
409              */
410             getClockSequence();
411             getTimeAdjust();
412             break;
413         }
414         else
415         {
416             /* increment time adjustment to avois a duplicate. */
417             timeAdjust++;
418             if (timeAdjust < N100NS_PER_MILLI)
419             {
420             break;
421             }
422             else
423             {
424             /* ran out of time adjustments -- wait for the
425              * clock to tick again. Note this can only happen
426              * if we try to generate > 6000 UUIDs per millisecond.
427              */
428             Thread.yield();
429             }
430         }
431         }
432
433         lastTime = now;
434         long result =
435             (lastTime * N100NS_PER_MILLI) + EPOCH_CVT + timeAdjust;
436
437
438         uuid.timeLow = (int)(result & 0xFFFFFFFF);
439         uuid.timeMid = (short)((result >> 32) & 0xFFFF);
440         uuid.timeHiAndVersion =
441             (short)(((result >> 48) & 0xFFFF) | VERSION_BITS);
442         uuid.clockSeqHiAndReserved =
443             (byte)(((clockSequence >> 8) & 0xFF) | RESERVED_BITS);
444         uuid.clockSeqLow = (byte)(clockSequence & 0xFF);
445         for (int i = 0; i < 6; i++)
446         {
447         uuid.nodeId[i] = nodeId[i];
448         }
449     }
450
451     /** Randomly generate a time adjustment */
452     private void getTimeAdjust()
453     {
454         timeAdjust = random2.nextInt() & TIME_ADJUST_MASK;
455     }
456         
457     /** Randomly generate a clock sequence */
458     private void getClockSequence()
459     {
460         clockSequence = random1.nextInt() & CLOCK_SEQ_MASK;
461         if (clockSequence == 0)
462         clockSequence++;
463     }
464             
465         
466     /** randomly generate a node ID. make the last two bytes
467     * 0xAA77, which cannot conflict with a real Ethernet address */
468     private void initializeNodeId()
469     {
470         byte barr[] = new byte[2];
471
472         Random r1 = new Random();
473         Random r2 = new Random(r1.hashCode());
474         r1.nextBytes(barr);
475         nodeId[0] = barr[0];
476         nodeId[1] = barr[1];
477
478         r2.nextBytes(barr);
479         nodeId[2] = barr[0];
480         nodeId[3] = barr[1];
481
482         nodeId[4] = (byte)0xaa;
483         nodeId[5] = 0x77;
484     }
485     }
486 }
487

A to Z: JavaDoc & Examples

---

Daily Java News & Articles

---

Open Source Projects

---

Open Source Codes

---

Free Computer Books

---

Remove Frame

---

Popular Tags