001: /* JUG Java Uuid Generator
002: *
003: * Copyright (c) 2002- Tatu Saloranta, tatu.saloranta@iki.fi
004: *
005: * Licensed under the License specified in the file LICENSE which is
006: * included with the source code.
007: * You may not use this file except in compliance with the License.
008: *
009: * Unless required by applicable law or agreed to in writing, software
010: * distributed under the License is distributed on an "AS IS" BASIS,
011: * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
012: * See the License for the specific language governing permissions and
013: * limitations under the License.
014: */
015:
016: package org.drools.util;
017:
018: import java.io.Serializable;
019:
020: /**
021: * UUID represents Universally Unique Identifiers (aka Global UID in
022: * Windows world). UUIDs are usually generated via UUIDGenerator (or in
023: * case of 'Null UUID', 16 zero bytes, via static method getNullUUID()),
024: * or received from external systems.
025: *
026: * By default class caches the string presentations of UUIDs so that
027: * description is only created the first time it's needed. For memory
028: * stingy applications this caching can be turned off (note though
029: * that if uuid.toString() is never called, desc is never calculated
030: * so only loss is the space allocated for the desc pointer... which
031: * can of course be commented out to save memory).
032: *
033: * Similarly, hash code is calculated when it's needed for the first
034: * time, and from thereon that value is just returned. This means
035: * that using UUIDs as keys should be reasonably efficient.
036: *
037: * UUIDs can be compared for equality, serialized, cloned and even sorted.
038: * Equality is a simple bit-wise comparison. Ordering (for sorting) is done by
039: * first ordering based on type (in the order of numeric values of
040: * types), secondarily by time stamp (only for time-based time stamps),
041: * and finally by straight numeric byte-by-byte comparison (from
042: * most to least significant bytes).
043: */
044:
045: public class UUID implements Serializable, Cloneable, Comparable {
046: private final static String kHexChars = "0123456789abcdefABCDEF";
047:
048: public final static byte INDEX_CLOCK_HI = 6;
049: public final static byte INDEX_CLOCK_MID = 4;
050: public final static byte INDEX_CLOCK_LO = 0;
051:
052: public final static byte INDEX_TYPE = 6;
053: // Clock seq. & variant are multiplexed...
054: public final static byte INDEX_CLOCK_SEQUENCE = 8;
055: public final static byte INDEX_VARIATION = 8;
056:
057: public final static byte TYPE_NULL = 0;
058: public final static byte TYPE_TIME_BASED = 1;
059: public final static byte TYPE_DCE = 2; // Not used
060: public final static byte TYPE_NAME_BASED = 3;
061: public final static byte TYPE_RANDOM_BASED = 4;
062:
063: /* 'Standard' namespaces defined (suggested) by UUID specs:
064: */
065: public final static String NAMESPACE_DNS = "6ba7b810-9dad-11d1-80b4-00c04fd430c8";
066: public final static String NAMESPACE_URL = "6ba7b811-9dad-11d1-80b4-00c04fd430c8";
067: public final static String NAMESPACE_OID = "6ba7b812-9dad-11d1-80b4-00c04fd430c8";
068: public final static String NAMESPACE_X500 = "6ba7b814-9dad-11d1-80b4-00c04fd430c8";
069:
070: /* By default let's cache desc, can be turned off. For hash code
071: * there's no point in turning it off (since the int is already
072: * part of the instance memory allocation); if you want to save
073: * those 4 bytes (or possibly bit more if alignment is bad) just
074: * comment out hash caching.
075: */
076: private static boolean sDescCaching = true;
077:
078: /**
079: * The shared null UUID. Would be nice to do lazy instantiation, but
080: * if the instance really has to be a singleton, that would mean
081: * class-level locking (synchronized getNullUUID()), which would
082: * be some overhead... So let's just bite the bullet the first time
083: * assuming creation of the null UUID (plus wasted space if it's
084: * not needed) can be ignored.
085: */
086: private final static UUID sNullUUID = new UUID();
087:
088: private final byte[] mId = new byte[16];
089: // Both string presentation and hash value may be cached...
090: private transient String mDesc = null;
091: private transient int mHashCode = 0;
092:
093: /* *** Object creation: *** */
094:
095: /**
096: * Default constructor creates a NIL UUID, one that contains all
097: * zeroes
098: *
099: * Note that the clearing of array is actually unnecessary as
100: * JVMs are required to clear up the allocated arrays by default.
101: */
102: public UUID() {
103: /*
104: for (int i = 0; i < 16; ++i) {
105: mId[i] = (byte)0;
106: }
107: */
108: }
109:
110: /**
111: * Constructor for cases where you already have the 16-byte binary
112: * representation of the UUID (for example if you save UUIDs binary
113: * takes less than half of space string representation takes).
114: *
115: * @param data array that contains the binary representation of UUID
116: */
117: public UUID(final byte[] data) {
118: /* Could call the other constructor... and/or use System.arraycopy.
119: * However, it's likely that those would make this slower to use,
120: * and initialization is really simple as is in any case.
121: */
122: for (int i = 0; i < 16; ++i) {
123: this .mId[i] = data[i];
124: }
125: }
126:
127: /**
128: * Constructor for cases where you already have the binary
129: * representation of the UUID (for example if you save UUIDs binary
130: * takes less than half of space string representation takes) in
131: * a byte array
132: *
133: * @param data array that contains the binary representation of UUID
134: * @param start byte offset where UUID starts
135: */
136: public UUID(final byte[] data, final int start) {
137: for (int i = 0; i < 16; ++i) {
138: this .mId[i] = data[start + i];
139: }
140: }
141:
142: /**
143: * Protected constructor used by UUIDGenerator
144: *
145: * @param type UUID type
146: * @param data 16 byte UUID contents
147: */
148: UUID(final int type, final byte[] data) {
149: for (int i = 0; i < 16; ++i) {
150: this .mId[i] = data[i];
151: }
152: // Type is multiplexed with time_hi:
153: this .mId[UUID.INDEX_TYPE] &= (byte) 0x0F;
154: this .mId[UUID.INDEX_TYPE] |= (byte) (type << 4);
155: // Variant masks first two bits of the clock_seq_hi:
156: this .mId[UUID.INDEX_VARIATION] &= (byte) 0x3F;
157: this .mId[UUID.INDEX_VARIATION] |= (byte) 0x80;
158: }
159:
160: /**
161: * Constructor for creating UUIDs from the canonical string
162: * representation
163: *
164: * Note that implementation is optimized for speed, not necessarily
165: * code clarity... Also, since what we get might not be 100% canonical
166: * (see below), let's not yet populate mDesc here.
167: *
168: * @param id String that contains the canonical representation of
169: * the UUID to build; 36-char string (see UUID specs for details).
170: * Hex-chars may be in upper-case too; UUID class will always output
171: * them in lowercase.
172: */
173: public UUID(final String id) throws NumberFormatException {
174: if (id == null) {
175: throw new NullPointerException();
176: }
177: if (id.length() != 36) {
178: throw new NumberFormatException(
179: "UUID has to be represented by the standard 36-char representation");
180: }
181:
182: for (int i = 0, j = 0; i < 36; ++j) {
183: // Need to bypass hyphens:
184: switch (i) {
185: case 8:
186: case 13:
187: case 18:
188: case 23:
189: if (id.charAt(i) != '-') {
190: throw new NumberFormatException(
191: "UUID has to be represented by the standard 36-char representation");
192: }
193: ++i;
194: }
195: final int index;
196: char c = id.charAt(i);
197:
198: if (c >= '0' && c <= '9') {
199: this .mId[j] = (byte) ((c - '0') << 4);
200: } else if (c >= 'a' && c <= 'f') {
201: this .mId[j] = (byte) ((c - 'a' + 10) << 4);
202: } else if (c >= 'A' && c <= 'F') {
203: this .mId[j] = (byte) ((c - 'A' + 10) << 4);
204: } else {
205: throw new NumberFormatException("Non-hex character '"
206: + c + "'");
207: }
208:
209: c = id.charAt(++i);
210:
211: if (c >= '0' && c <= '9') {
212: this .mId[j] |= (byte) (c - '0');
213: } else if (c >= 'a' && c <= 'f') {
214: this .mId[j] |= (byte) (c - 'a' + 10);
215: } else if (c >= 'A' && c <= 'F') {
216: this .mId[j] |= (byte) (c - 'A' + 10);
217: } else {
218: throw new NumberFormatException("Non-hex character '"
219: + c + "'");
220: }
221: ++i;
222: }
223: }
224:
225: /**
226: * Default cloning behaviour (bitwise copy) is just fine...
227: *
228: * Could clear out cached string presentation, but there's
229: * probably no point in doing that.
230: */
231: public Object clone() {
232: try {
233: return super .clone();
234: } catch (final CloneNotSupportedException e) {
235: // shouldn't happen
236: return null;
237: }
238: }
239:
240: /* *** Configuration: *** */
241: public static void setDescCaching(final boolean state) {
242: UUID.sDescCaching = state;
243: }
244:
245: /* *** Accessors: *** */
246:
247: /**
248: * Accessor for getting the shared null UUID
249: *
250: * @return the shared null UUID
251: */
252: public static UUID getNullUUID() {
253: return UUID.sNullUUID;
254: }
255:
256: public boolean isNullUUID() {
257: // Assuming null uuid is usually used for nulls:
258: if (this == UUID.sNullUUID) {
259: return true;
260: }
261: // Could also check hash code; null uuid has -1 as hash?
262: final byte[] data = this .mId;
263: int i = this .mId.length;
264: final byte zero = (byte) 0;
265: while (--i >= 0) {
266: if (data[i] != zero) {
267: return false;
268: }
269: }
270:
271: return true;
272: }
273:
274: /**
275: * Returns the UUID type code
276: *
277: * @return UUID type
278: */
279: public int getType() {
280: return (this .mId[UUID.INDEX_TYPE] & 0xFF) >> 4;
281: }
282:
283: /**
284: * Returns the UUID as a 16-byte byte array
285: *
286: * @return 16-byte byte array that contains UUID bytes in the network
287: * byte order
288: */
289: public byte[] asByteArray() {
290: final byte[] result = new byte[16];
291: toByteArray(result);
292: return result;
293: }
294:
295: /**
296: * Fills in the 16 bytes (from index pos) of the specified byte array
297: * with the UUID contents.
298: *
299: * @param dst Byte array to fill
300: * @param pos Offset in the array
301: */
302: public void toByteArray(final byte[] dst, final int pos) {
303: final byte[] src = this .mId;
304: for (int i = 0; i < 16; ++i) {
305: dst[pos + i] = src[i];
306: }
307: }
308:
309: public void toByteArray(final byte[] dst) {
310: toByteArray(dst, 0);
311: }
312:
313: /**
314: * 'Synonym' for 'asByteArray'
315: */
316: public byte[] toByteArray() {
317: return asByteArray();
318: }
319:
320: /* *** Standard methods from Object overridden: *** */
321:
322: /**
323: * Could use just the default hash code, but we can probably create
324: * a better identity hash (ie. same contents generate same hash)
325: * manually, without sacrificing speed too much. Although multiplications
326: * with modulos would generate better hashing, let's use just shifts,
327: * and do 2 bytes at a time.
328: *<p>
329: * Of course, assuming UUIDs are randomized enough, even simpler
330: * approach might be good enough?
331: *<p>
332: * Is this a good hash? ... one of these days I better read more about
333: * basic hashing techniques I swear!
334: */
335: private final static int[] kShifts = { 3, 7, 17, 21, 29, 4, 9 };
336:
337: public int hashCode() {
338: if (this .mHashCode == 0) {
339: // Let's handle first and last byte separately:
340: int result = this .mId[0] & 0xFF;
341:
342: result |= (result << 16);
343: result |= (result << 8);
344:
345: for (int i = 1; i < 15; i += 2) {
346: final int curr = (this .mId[i] & 0xFF) << 8
347: | (this .mId[i + 1] & 0xFF);
348: final int shift = UUID.kShifts[i >> 1];
349:
350: if (shift > 16) {
351: result ^= (curr << shift) | (curr >>> (32 - shift));
352: } else {
353: result ^= (curr << shift);
354: }
355: }
356:
357: // and then the last byte:
358: final int last = this .mId[15] & 0xFF;
359: result ^= (last << 3);
360: result ^= (last << 13);
361:
362: result ^= (last << 27);
363: // Let's not accept hash 0 as it indicates 'not hashed yet':
364: if (result == 0) {
365: this .mHashCode = -1;
366: } else {
367: this .mHashCode = result;
368: }
369: }
370: return this .mHashCode;
371: }
372:
373: public String toString() {
374: /* Could be synchronized, but there isn't much harm in just taking
375: * our chances (ie. in the worst case we'll form the string more
376: * than once... but result is the same)
377: */
378:
379: if (this .mDesc == null) {
380: final StringBuffer b = new StringBuffer(36);
381:
382: for (int i = 0; i < 16; ++i) {
383: // Need to bypass hyphens:
384: switch (i) {
385: case 4:
386: case 6:
387: case 8:
388: case 10:
389: b.append('-');
390: }
391: final int hex = this .mId[i] & 0xFF;
392: b.append(UUID.kHexChars.charAt(hex >> 4));
393: b.append(UUID.kHexChars.charAt(hex & 0x0f));
394: }
395: if (!UUID.sDescCaching) {
396: return b.toString();
397: }
398: this .mDesc = b.toString();
399: }
400: return this .mDesc;
401: }
402:
403: /* *** Comparison methods: *** */
404:
405: private final static int[] sTimeCompare = new int[] {
406: UUID.INDEX_CLOCK_HI, UUID.INDEX_CLOCK_HI + 1,
407: UUID.INDEX_CLOCK_MID, UUID.INDEX_CLOCK_MID + 1,
408: UUID.INDEX_CLOCK_LO, UUID.INDEX_CLOCK_LO + 1,
409: UUID.INDEX_CLOCK_LO + 2, UUID.INDEX_CLOCK_LO + 3, };
410:
411: /**
412: * Let's also make UUIDs sortable. This will mostly/only be useful with
413: * time-based UUIDs; they will sorted by time of creation. The order
414: * will be strictly correct with UUIDs produced over one JVM's lifetime;
415: * that is, if more than one JVMs create UUIDs and/or system is rebooted
416: * the order may not be 100% accurate between UUIDs created under
417: * different JVMs.
418: *
419: * For all UUIDs, type is first compared, and UUIDs of different types
420: * are sorted together (ie. null UUID is before all other UUIDs, then
421: * time-based UUIDs etc). If types are the same, time-based UUIDs'
422: * time stamps (including additional clock counter) are compared, so
423: * UUIDs created first are ordered first. For all other types (and for
424: * time-based UUIDs with same time stamp, which should only occur
425: * when comparing a UUID with itself, or with UUIDs created on
426: * different JVMs or external systems) binary comparison is done
427: * over all 16 bytes.
428: *
429: * @param o Object to compare this UUID to; should be a UUID
430: *
431: * @return -1 if this UUID should be ordered before the one passed,
432: * 1 if after, and 0 if they are the same
433: *
434: * @throws ClassCastException if o is not a UUID.
435: */
436: public int compareTo(final Object o) {
437: final UUID other = (UUID) o;
438:
439: final int this Type = getType();
440: final int thatType = other.getType();
441:
442: /* Let's first order by type:
443: */
444: if (this Type > thatType) {
445: return 1;
446: } else if (this Type < thatType) {
447: return -1;
448: }
449:
450: /* And for time-based UUIDs let's compare time stamps first,
451: * then the rest... For all other types, we'll just do straight
452: * byte-by-byte comparison.
453: */
454: final byte[] this Id = this .mId;
455: final byte[] thatId = other.mId;
456: int i = 0;
457: if (this Type == UUID.TYPE_TIME_BASED) {
458: for (; i < 8; ++i) {
459: final int index = UUID.sTimeCompare[i];
460: final int cmp = ((this Id[index]) & 0xFF)
461: - ((thatId[index]) & 0xFF);
462: if (cmp != 0) {
463: return cmp;
464: }
465: }
466: // Let's fall down to full comparison otherwise
467: }
468:
469: for (; i < 16; ++i) {
470: final int cmp = ((this Id[i]) & 0xFF) - ((thatId[i]) & 0xFF);
471: if (cmp != 0) {
472: return cmp;
473: }
474: }
475:
476: return 0;
477: }
478:
479: /**
480: * Checking equality of UUIDs is easy; just compare the 128-bit
481: * number.
482: */
483: public boolean equals(final Object o) {
484: if (!(o instanceof UUID)) {
485: return false;
486: }
487: final byte[] otherId = ((UUID) o).mId;
488: final byte[] this Id = this .mId;
489: for (int i = 0; i < 16; ++i) {
490: if (otherId[i] != this Id[i]) {
491: return false;
492: }
493: }
494: return true;
495: }
496:
497: /**
498: * Constructs a new UUID instance given the canonical string
499: * representation of an UUID.
500: *
501: * Note that calling this method returns the same result as would
502: * using the matching (1 string arg) constructor.
503: *
504: * @param id Canonical string representation used for constructing
505: * an UUID instance
506: *
507: * @throws NumberFormatException if 'id' is invalid UUID
508: */
509: public static UUID valueOf(final String id)
510: throws NumberFormatException {
511: return new UUID(id);
512: }
513:
514: /**
515: * Constructs a new UUID instance given a byte array that contains
516: * the (16 byte) binary representation.
517: *
518: * Note that calling this method returns the same result as would
519: * using the matching constructor
520: *
521: * @param src Byte array that contains the UUID definition
522: * @param start Offset in the array where the UUID starts
523: */
524: public static UUID valueOf(final byte[] src, final int start) {
525: return new UUID(src, start);
526: }
527:
528: /**
529: * Constructs a new UUID instance given a byte array that contains
530: * the (16 byte) binary representation.
531: *
532: * Note that calling this method returns the same result as would
533: * using the matching constructor
534: *
535: * @param src Byte array that contains the UUID definition
536: */
537: public static UUID valueOf(final byte[] src) {
538: return new UUID(src);
539: }
540:
541: private void copyFrom(final UUID src) {
542: final byte[] srcB = src.mId;
543: final byte[] dstB = this .mId;
544:
545: for (int i = 0; i < 16; ++i) {
546: dstB[i] = srcB[i];
547: }
548:
549: this.mDesc = UUID.sDescCaching ? src.mDesc : null;
550: }
551:
552: }
|