001: /*
002: * WeakHashSet.java
003: *
004: * Created on September 25, 2000, 2:59 PM
005: */
006:
007: package org.netbeans.editor.ext.html;
008:
009: import java.lang.ref.WeakReference;
010:
011: /**
012: * This is a special set-like (not java.util.Set-like) class. It holds a set of
013: * objects referenced only weakly, and which can be get() by an equivalent
014: * object. It can be used e.g. as a lightweight (gc()-able) intern() for String
015: * or as a temporal storage for an algorithm creating a lot of long-lasting
016: * equals() immutables.
017: *
018: * @author Petr Nejedly
019: * @version 1.0
020: */
021: public class WeakHashSet {
022:
023: Entry[] data;
024: // count of (possibly) active Entries
025: int count = 0;
026: // Number of Entries at which we rehash
027: int treshold;
028: float loadFactor;
029:
030: /** Creates new WeakHashSet */
031: public WeakHashSet(int capacity, float loadFactor) {
032: this .loadFactor = loadFactor;
033: treshold = (int) (capacity * loadFactor);
034: data = new Entry[capacity];
035: }
036:
037: /** Return the object equals to this object */
038: public Object get(Object obj) {
039: if (obj == null)
040: return null;
041:
042: Entry[] tab = data;
043: Entry prev = null;
044: int hash = obj.hashCode();
045: int index = (hash & 0x7FFFFFFF) % tab.length;
046:
047: for (Entry e = tab[index]; e != null; prev = e, e = e.next)
048: if (e.hash == hash) {
049: Object value = e.value.get();
050: if (value == null) {
051: // remove this entry from chain
052: count--;
053: if (prev == null)
054: tab[index] = e.next;
055: else
056: prev.next = e.next;
057: } else {
058: if (value.equals(obj))
059: return value;
060: }
061: }
062: return null;
063: }
064:
065: public Object put(Object obj) {
066: if (obj == null)
067: return null;
068:
069: Entry[] tab = data;
070: Entry prev = null;
071: int hash = obj.hashCode();
072: int index = (hash & 0x7FFFFFFF) % tab.length;
073:
074: for (Entry e = tab[index]; e != null; prev = e, e = e.next)
075: if (e.hash == hash) {
076: Object value = e.value.get();
077: if (value == null) {
078: count--;
079: if (prev == null)
080: tab[index] = e.next;
081: else
082: prev.next = e.next;
083: } else {
084: if (value.equals(obj))
085: return value;
086: }
087: }
088:
089: if (count >= treshold) {
090: rehash();
091: tab = data;
092: index = (hash & 0x7FFFFFFF) % tab.length;
093: }
094:
095: Entry e = new Entry(hash, obj, tab[index]);
096: tab[index] = e;
097: count++;
098:
099: return obj;
100: }
101:
102: private void rehash() {
103: int oldCapacity = data.length;
104: Entry oldMap[] = data;
105:
106: int newCapacity = oldCapacity * 2 + 1;
107: Entry newMap[] = new Entry[newCapacity];
108:
109: treshold = (int) (newCapacity * loadFactor);
110: data = newMap;
111:
112: for (int i = oldCapacity; i-- > 0;) {
113: for (Entry old = oldMap[i]; old != null;) {
114: Entry e = old;
115: old = old.next;
116:
117: int index = (e.hash & 0x7FFFFFFF) % newCapacity;
118: e.next = newMap[index];
119: newMap[index] = e;
120: }
121: }
122: }
123:
124: /**
125: * WeakHashSet collision list entry.
126: */
127: private static class Entry {
128: int hash;
129: WeakReference value;
130: Entry next;
131:
132: Entry(int hash, Object value, Entry next) {
133: this .hash = hash;
134: this .value = new WeakReference(value);
135: this.next = next;
136: }
137: }
138:
139: }
|