001: /*
002: * RefMap.java
003: *
004: * Copyright (c) 2007 Sun Microsystems, Inc. All Rights Reserved.
005: *
006: * See the file "LICENSE.txt" for information on usage and redistribution
007: * of this file, and for a DISCLAIMER OF ALL WARRANTIES.
008: */
009: package org.pnuts.util;
010:
011: import java.util.*;
012: import java.lang.ref.*;
013:
014: public class RefMap extends AbstractMap implements Map {
015:
016: private static final int DEFAULT_INITIAL_CAPACITY = 16;
017: private static final int MAXIMUM_CAPACITY = 1 << 30;
018: private static final float DEFAULT_LOAD_FACTOR = 0.75f;
019: private static final Object NULL_KEY = new Object();
020: private static final String CACHE_CLEANER_NAME = "Cache Cleaner";
021: private static final ReferenceQueue queue = new ReferenceQueue();
022:
023: private Entry[] table;
024: private int size;
025: private int threshold;
026: private final float loadFactor;
027: private volatile int modCount;
028:
029: public RefMap(int initialCapacity, float loadFactor) {
030: if (initialCapacity < 0) {
031: throw new IllegalArgumentException(
032: "Illegal Initial Capacity: " + initialCapacity);
033: }
034: if (initialCapacity > MAXIMUM_CAPACITY) {
035: initialCapacity = MAXIMUM_CAPACITY;
036: }
037: if (loadFactor <= 0 || Float.isNaN(loadFactor)) {
038: throw new IllegalArgumentException("Illegal Load factor: "
039: + loadFactor);
040: }
041: int capacity = 1;
042: while (capacity < initialCapacity) {
043: capacity <<= 1;
044: }
045: table = new Entry[capacity];
046: this .loadFactor = loadFactor;
047: threshold = (int) (capacity * loadFactor);
048: }
049:
050: public RefMap(int initialCapacity) {
051: this (initialCapacity, DEFAULT_LOAD_FACTOR);
052: }
053:
054: public RefMap() {
055: this .loadFactor = DEFAULT_LOAD_FACTOR;
056: threshold = (int) (DEFAULT_INITIAL_CAPACITY);
057: table = new Entry[DEFAULT_INITIAL_CAPACITY];
058: }
059:
060: public RefMap(Map m) {
061: this (Math.max((int) (m.size() / DEFAULT_LOAD_FACTOR) + 1, 16),
062: DEFAULT_LOAD_FACTOR);
063: putAll(m);
064: }
065:
066: private static Object maskNull(Object key) {
067: return (key == null ? NULL_KEY : key);
068: }
069:
070: private static Object unmaskNull(Object key) {
071: return (key == NULL_KEY ? null : key);
072: }
073:
074: static boolean eq(Object x, Object y) {
075: return x == y || x.equals(y);
076: }
077:
078: static int indexFor(int h, int length) {
079: return h & (length - 1);
080: }
081:
082: private synchronized void expungeStaleEntry(Entry e) {
083: int h = e.hash;
084: int i = indexFor(h, table.length);
085: Entry prev = table[i];
086: Entry p = prev;
087: while (p != null) {
088: Entry next = p.next;
089: if (p == e) {
090: if (prev == e) {
091: table[i] = next;
092: } else {
093: prev.next = next;
094: }
095: e.next = null;
096: e.value = null;
097: size--;
098: break;
099: }
100: prev = p;
101: p = next;
102: }
103: }
104:
105: public int size() {
106: if (size == 0) {
107: return 0;
108: }
109: return size;
110: }
111:
112: public boolean isEmpty() {
113: return size() == 0;
114: }
115:
116: public Object get(Object key) {
117: Object k = maskNull(key);
118: int h = hash(k.hashCode());
119: Entry[] tab = this .table;
120: int index = indexFor(h, tab.length);
121: Entry e = tab[index];
122: while (e != null) {
123: if (e.hash == h && eq(k, e.get())) {
124: return e.value;
125: }
126: e = e.next;
127: }
128: return null;
129: }
130:
131: public boolean containsKey(Object key) {
132: return getEntry(key) != null;
133: }
134:
135: Entry getEntry(Object key) {
136: Object k = maskNull(key);
137: int h = hash(k.hashCode());
138: Entry[] tab = this .table;
139: int index = indexFor(h, tab.length);
140: Entry e = tab[index];
141: while (e != null && !(e.hash == h && eq(k, e.get()))) {
142: e = e.next;
143: }
144: return e;
145: }
146:
147: public synchronized Object put(Object key, Object value) {
148: Object k = maskNull(key);
149: int h = hash(k.hashCode());
150: Entry[] tab = this .table;
151: int i = indexFor(h, tab.length);
152:
153: for (Entry e = tab[i]; e != null; e = e.next) {
154: if (h == e.hash && eq(k, e.get())) {
155: Object oldValue = e.value;
156: if (value != oldValue) {
157: e.value = value;
158: }
159: return oldValue;
160: }
161: }
162:
163: modCount++;
164: Entry e = tab[i];
165: tab[i] = new Entry(k, value, queue, h, e, this );
166: if (++size >= threshold) {
167: resize(tab.length * 2);
168: }
169: return null;
170: }
171:
172: synchronized void resize(int newCapacity) {
173: Entry[] oldTable = this .table;
174: int oldCapacity = oldTable.length;
175: if (oldCapacity == MAXIMUM_CAPACITY) {
176: threshold = Integer.MAX_VALUE;
177: return;
178: }
179:
180: Entry[] newTable = new Entry[newCapacity];
181: transfer(oldTable, newTable);
182: table = newTable;
183:
184: if (size >= threshold / 2) {
185: threshold = (int) (newCapacity * loadFactor);
186: } else {
187: transfer(newTable, oldTable);
188: table = oldTable;
189: }
190: }
191:
192: private void transfer(Entry[] src, Entry[] dest) {
193: for (int j = 0; j < src.length; ++j) {
194: Entry e = src[j];
195: src[j] = null;
196: while (e != null) {
197: Entry next = e.next;
198: Object key = e.get();
199: if (key == null) {
200: e.next = null; // Help GC
201: e.value = null; // " "
202: size--;
203: } else {
204: int i = indexFor(e.hash, dest.length);
205: e.next = dest[i];
206: dest[i] = e;
207: }
208: e = next;
209: }
210: }
211: }
212:
213: public void putAll(Map m) {
214: int numKeysToBeAdded = m.size();
215: if (numKeysToBeAdded == 0) {
216: return;
217: }
218: if (numKeysToBeAdded > threshold) {
219: int targetCapacity = (int) (numKeysToBeAdded / loadFactor + 1);
220: if (targetCapacity > MAXIMUM_CAPACITY) {
221: targetCapacity = MAXIMUM_CAPACITY;
222: }
223: int newCapacity = table.length;
224: while (newCapacity < targetCapacity) {
225: newCapacity <<= 1;
226: }
227: if (newCapacity > table.length) {
228: resize(newCapacity);
229: }
230: }
231:
232: for (Iterator it = m.entrySet().iterator(); it.hasNext();) {
233: Map.Entry e = (Map.Entry) it.next();
234: put(e.getKey(), e.getValue());
235: }
236: }
237:
238: public Object remove(Object key) {
239: Object k = maskNull(key);
240: int h = hash(k.hashCode());
241: Entry[] tab = this .table;
242: int i = indexFor(h, tab.length);
243: Entry prev = tab[i];
244: Entry e = prev;
245:
246: while (e != null) {
247: Entry next = e.next;
248: if (h == e.hash && eq(k, e.get())) {
249: modCount++;
250: size--;
251: if (prev == e) {
252: tab[i] = next;
253: } else {
254: prev.next = next;
255: }
256: return e.value;
257: }
258: prev = e;
259: e = next;
260: }
261:
262: return null;
263: }
264:
265: Entry removeMapping(Object o) {
266: if (!(o instanceof Map.Entry)) {
267: return null;
268: }
269: Entry[] tab = this .table;
270: Map.Entry entry = (Map.Entry) o;
271: Object k = maskNull(entry.getKey());
272: int h = hash(k.hashCode());
273: int i = indexFor(h, tab.length);
274: Entry prev = tab[i];
275: Entry e = prev;
276:
277: while (e != null) {
278: Entry next = e.next;
279: if (h == e.hash && e.equals(entry)) {
280: modCount++;
281: size--;
282: if (prev == e) {
283: tab[i] = next;
284: } else {
285: prev.next = next;
286: }
287: return e;
288: }
289: prev = e;
290: e = next;
291: }
292: return null;
293: }
294:
295: public void clear() {
296: modCount++;
297: Entry[] tab = table;
298: for (int i = 0; i < tab.length; ++i) {
299: tab[i] = null;
300: }
301: size = 0;
302: }
303:
304: public boolean containsValue(Object value) {
305: if (value == null) {
306: return containsNullValue();
307: }
308: Entry[] tab = this .table;
309: for (int i = tab.length; i-- > 0;) {
310: for (Entry e = tab[i]; e != null; e = e.next) {
311: if (value.equals(e.value)) {
312: return true;
313: }
314: }
315: }
316: return false;
317: }
318:
319: private boolean containsNullValue() {
320: Entry[] tab = this .table;
321: for (int i = tab.length; i-- > 0;) {
322: for (Entry e = tab[i]; e != null; e = e.next) {
323: if (e.value == null) {
324: return true;
325: }
326: }
327: }
328: return false;
329: }
330:
331: private static class Entry extends WeakReference implements
332: Map.Entry {
333: private Object value;
334: private final int hash;
335: private Entry next;
336: private RefMap container;
337:
338: Entry(Object key, Object value, ReferenceQueue queue, int hash,
339: Entry next, RefMap container) {
340: super (key, queue);
341: this .value = value;
342: this .hash = hash;
343: this .next = next;
344: this .container = container;
345: }
346:
347: public Object getKey() {
348: return RefMap.unmaskNull(get());
349: }
350:
351: public Object getValue() {
352: return value;
353: }
354:
355: public Object setValue(Object newValue) {
356: Object oldValue = value;
357: value = newValue;
358: return oldValue;
359: }
360:
361: public boolean equals(Object o) {
362: if (!(o instanceof Map.Entry)) {
363: return false;
364: }
365: Map.Entry e = (Map.Entry) o;
366: Object k1 = getKey();
367: Object k2 = e.getKey();
368: if (k1 == k2 || (k1 != null && k1.equals(k2))) {
369: Object v1 = getValue();
370: Object v2 = e.getValue();
371: if (v1 == v2 || (v1 != null && v1.equals(v2))) {
372: return true;
373: }
374: }
375: return false;
376: }
377:
378: public int hashCode() {
379: Object k = getKey();
380: Object v = getValue();
381: return ((k == null ? 0 : k.hashCode()) ^ (v == null ? 0 : v
382: .hashCode()));
383: }
384:
385: public String toString() {
386: return getKey() + "=" + getValue();
387: }
388: }
389:
390: public Set keySet() {
391: throw new UnsupportedOperationException();
392: }
393:
394: public Collection values() {
395: throw new UnsupportedOperationException();
396: }
397:
398: public Set entrySet() {
399: throw new UnsupportedOperationException();
400: }
401:
402: static int hash(int h) {
403: h ^= (h >>> 20) ^ (h >>> 12);
404: return h ^ (h >>> 7) ^ (h >>> 4);
405: }
406:
407: public static void startCleanerThread() {
408: Thread cleanerThread = new Thread(CACHE_CLEANER_NAME) {
409: public void run() {
410: try {
411: while (true) {
412: Entry entry = (Entry) queue.remove();
413: entry.container.expungeStaleEntry(entry);
414: }
415: } catch (InterruptedException e) {
416: e.printStackTrace();
417: }
418: }
419: };
420: cleanerThread.setDaemon(true);
421: cleanerThread.start();
422: }
423:
424: static {
425: startCleanerThread();
426: }
427: }
|