1
2
3
4 package jwutil.collections;
5
6 import java.util.Collections;
7 import java.util.Comparator;
8 import java.util.Iterator;
9 import java.util.LinkedList;
10 import java.util.List;
11 import java.lang.ref.ReferenceQueue;
12 import java.lang.ref.WeakReference;
13 import jwutil.strings.Strings;
14 import jwutil.util.Assert;
15
16 /***
17 * @author John Whaley <jwhaley@alum.mit.edu>
18 * @version $Id: HashCodeComparator.java 2254 2005-05-05 18:52:16Z joewhaley $
19 */
20 public class HashCodeComparator implements Comparator {
21
22 public static final boolean USE_IDENTITY_HASHCODE = false;
23 public static final boolean USE_WEAK_REFERENCES = true;
24
25 public static final HashCodeComparator INSTANCE = new HashCodeComparator();
26
27 public static final boolean TRACE = false;
28 public static final boolean TEST = false;
29
30 private List duplicate_hashcode_objects;
31 private final ReferenceQueue queue;
32 private volatile Thread cleanupThread;
33
34 public HashCodeComparator() {
35 if (USE_WEAK_REFERENCES) {
36 queue = new ReferenceQueue();
37 Runnable cleanUp = new Runnable() {
38 public void run() {
39 Thread thisThread = Thread.currentThread();
40 WeakReference wr;
41 while (thisThread == cleanupThread) {
42 try {
43 wr = (WeakReference)queue.remove();
44 duplicate_hashcode_objects.remove(wr);
45 wr = null;
46 } catch (InterruptedException e) { }
47 }
48 }
49 };
50 cleanupThread = new Thread(cleanUp);
51 cleanupThread.setDaemon(true);
52 cleanupThread.start();
53 } else {
54 queue = null;
55 }
56 }
57
58 protected void finalize() {
59 Thread t = this.cleanupThread;
60 this.cleanupThread = null;
61 t.interrupt();
62 }
63
64 /***
65 * @see java.util.Comparator#compare(java.lang.Object, java.lang.Object)
66 */
67 public int compare(Object arg0, Object arg1) {
68 boolean eq;
69 if (USE_IDENTITY_HASHCODE) eq = arg0 == arg1;
70 else eq = arg0.equals(arg1);
71 if (eq) return 0;
72 int a, b;
73 if (USE_IDENTITY_HASHCODE) {
74 a = System.identityHashCode(arg0);
75 b = System.identityHashCode(arg1);
76 } else {
77 a = arg0.hashCode();
78 b = arg1.hashCode();
79 }
80 if (TEST) {
81 a %= 6835; b %= 6835;
82 }
83 if (a > b) return 1;
84 if (a < b) return -1;
85
86 if (duplicate_hashcode_objects == null) {
87 synchronized (this) {
88 if (duplicate_hashcode_objects == null) {
89 duplicate_hashcode_objects = Collections.synchronizedList(new LinkedList());
90 }
91 }
92 }
93 int i1 = indexOf(arg0);
94 int i2 = indexOf(arg1);
95 if (i1 == -1) {
96 if (i2 == -1) {
97 if (TRACE) {
98 i1 = duplicate_hashcode_objects.size();
99 System.out.println("Hash code conflict: "+Strings.hex8(a)+" "+arg0+" vs. "+arg1+", allocating ("+i1+")");
100 }
101 if (USE_WEAK_REFERENCES) arg0 = new WeakReference(arg0, queue);
102 duplicate_hashcode_objects.add(arg0);
103 return -1;
104 } else {
105 return 1;
106 }
107 } else if (i1 < i2 || i2 == -1) {
108 return -1;
109 } else {
110 Assert._assert(i1 > i2);
111 return 1;
112 }
113 }
114
115 private int indexOf(Object o) {
116 if (!USE_WEAK_REFERENCES) {
117 if (USE_IDENTITY_HASHCODE) o = IdentityHashCodeWrapper.create(o);
118 return duplicate_hashcode_objects.indexOf(o);
119 }
120 int index = 0;
121
122 synchronized (duplicate_hashcode_objects) {
123 for (Iterator i=duplicate_hashcode_objects.iterator(); i.hasNext(); ++index) {
124 WeakReference r = (WeakReference) i.next();
125 if (USE_IDENTITY_HASHCODE) {
126 if (o == r.get()) return index;
127 } else {
128 if (o.equals(r.get())) return index;
129 }
130 }
131 }
132 return -1;
133 }
134
135 }