001: /*
002:
003: Licensed to the Apache Software Foundation (ASF) under one or more
004: contributor license agreements. See the NOTICE file distributed with
005: this work for additional information regarding copyright ownership.
006: The ASF licenses this file to You under the Apache License, Version 2.0
007: (the "License"); you may not use this file except in compliance with
008: the License. You may obtain a copy of the License at
009:
010: http://www.apache.org/licenses/LICENSE-2.0
011:
012: Unless required by applicable law or agreed to in writing, software
013: distributed under the License is distributed on an "AS IS" BASIS,
014: WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
015: See the License for the specific language governing permissions and
016: limitations under the License.
017:
018: */
019: package org.apache.batik.util;
020:
021: import java.lang.ref.ReferenceQueue;
022: import java.lang.ref.SoftReference;
023:
024: /**
025: * This class represents a doubly indexed hash table, which holds
026: * soft references to the contained values.
027: * <br>This HashMap is not Thread-safe.
028: *
029: * @author <a href="mailto:stephane@hillion.org">Stephane Hillion</a>
030: * @version $Id: SoftDoublyIndexedTable.java 489226 2006-12-21 00:05:36Z cam $
031: */
032: public class SoftDoublyIndexedTable {
033:
034: /**
035: * The initial capacity
036: */
037: protected static final int INITIAL_CAPACITY = 11;
038:
039: /**
040: * The underlying array
041: */
042: protected Entry[] table;
043:
044: /**
045: * The number of entries
046: */
047: protected int count;
048:
049: /**
050: * The reference queue.
051: */
052: protected ReferenceQueue referenceQueue = new ReferenceQueue();
053:
054: /**
055: * Creates a new SoftDoublyIndexedTable.
056: */
057: public SoftDoublyIndexedTable() {
058: table = new Entry[INITIAL_CAPACITY];
059: }
060:
061: /**
062: * Creates a new DoublyIndexedTable.
063: * @param c The inital capacity.
064: */
065: public SoftDoublyIndexedTable(int c) {
066: table = new Entry[c];
067: }
068:
069: /**
070: * Returns the size of this table.
071: */
072: public int size() {
073: return count;
074: }
075:
076: /**
077: * Gets the value of a variable
078: * @return the value or null
079: */
080: public Object get(Object o1, Object o2) {
081: int hash = hashCode(o1, o2) & 0x7FFFFFFF;
082: int index = hash % table.length;
083:
084: for (Entry e = table[index]; e != null; e = e.next) {
085: if ((e.hash == hash) && e.match(o1, o2)) {
086: return e.get();
087: }
088: }
089: return null;
090: }
091:
092: /**
093: * Sets a new value for the given variable
094: * @return the old value or null
095: */
096: public Object put(Object o1, Object o2, Object value) {
097: removeClearedEntries();
098:
099: int hash = hashCode(o1, o2) & 0x7FFFFFFF;
100: int index = hash % table.length;
101:
102: Entry e = table[index];
103: if (e != null) {
104: if ((e.hash == hash) && e.match(o1, o2)) {
105: Object old = e.get();
106: table[index] = new Entry(hash, o1, o2, value, e.next);
107: return old;
108: }
109: Entry o = e;
110: e = e.next;
111: while (e != null) {
112: if ((e.hash == hash) && e.match(o1, o2)) {
113: Object old = e.get();
114: e = new Entry(hash, o1, o2, value, e.next);
115: o.next = e;
116: return old;
117: }
118:
119: o = e;
120: e = e.next;
121: }
122: }
123:
124: // The key is not in the hash table
125: int len = table.length;
126: if (count++ >= (len - (len >> 2))) {
127: // more than 75% loaded: grow
128: rehash();
129: index = hash % table.length;
130: }
131:
132: table[index] = new Entry(hash, o1, o2, value, table[index]);
133: return null;
134: }
135:
136: /**
137: * Clears the table.
138: */
139: public void clear() {
140: table = new Entry[INITIAL_CAPACITY];
141: count = 0;
142: referenceQueue = new ReferenceQueue();
143: }
144:
145: /**
146: * Rehash the table
147: */
148: protected void rehash() {
149: Entry[] oldTable = table;
150:
151: table = new Entry[oldTable.length * 2 + 1];
152:
153: for (int i = oldTable.length - 1; i >= 0; i--) {
154: for (Entry old = oldTable[i]; old != null;) {
155: Entry e = old;
156: old = old.next;
157:
158: int index = e.hash % table.length;
159: e.next = table[index];
160: table[index] = e;
161: }
162: }
163: }
164:
165: /**
166: * Computes a hash code corresponding to the given objects.
167: */
168: protected int hashCode(Object o1, Object o2) {
169: int result = (o1 == null) ? 0 : o1.hashCode();
170: return result ^ ((o2 == null) ? 0 : o2.hashCode());
171: }
172:
173: /**
174: * Removes the cleared entries.
175: */
176: protected void removeClearedEntries() {
177: Entry e;
178: while ((e = (Entry) referenceQueue.poll()) != null) {
179: int index = e.hash % table.length;
180: Entry t = table[index];
181: if (t == e) {
182: table[index] = e.next;
183: } else {
184: loop: for (; t != null;) {
185: Entry c = t.next;
186: if (c == e) {
187: t.next = e.next;
188: break loop;
189: }
190: t = c;
191: }
192: }
193: count--;
194: }
195: }
196:
197: /**
198: * To manage collisions
199: */
200: protected class Entry extends SoftReference {
201:
202: /**
203: * The hash code
204: */
205: public int hash;
206:
207: /**
208: * The first key
209: */
210: public Object key1;
211:
212: /**
213: * The second key
214: */
215: public Object key2;
216:
217: /**
218: * The next entry
219: */
220: public Entry next;
221:
222: /**
223: * Creates a new entry
224: */
225: public Entry(int hash, Object key1, Object key2, Object value,
226: Entry next) {
227: super (value, referenceQueue);
228: this .hash = hash;
229: this .key1 = key1;
230: this .key2 = key2;
231: this .next = next;
232: }
233:
234: /**
235: * Whether this entry match the given keys.
236: */
237: public boolean match(Object o1, Object o2) {
238: if (key1 != null) {
239: if (!key1.equals(o1)) {
240: return false;
241: }
242: } else if (o1 != null) {
243: return false;
244: }
245: if (key2 != null) {
246: return key2.equals(o2);
247: }
248: return o2 == null;
249: }
250: }
251: }
|