001: /*
002:
003: ============================================================================
004: The Apache Software License, Version 1.1
005: ============================================================================
006:
007: Copyright (C) 1999-2003 The Apache Software Foundation. All rights reserved.
008:
009: Redistribution and use in source and binary forms, with or without modifica-
010: tion, are permitted provided that the following conditions are met:
011:
012: 1. Redistributions of source code must retain the above copyright notice,
013: this list of conditions and the following disclaimer.
014:
015: 2. Redistributions in binary form must reproduce the above copyright notice,
016: this list of conditions and the following disclaimer in the documentation
017: and/or other materials provided with the distribution.
018:
019: 3. The end-user documentation included with the redistribution, if any, must
020: include the following acknowledgment: "This product includes software
021: developed by the Apache Software Foundation (http://www.apache.org/)."
022: Alternately, this acknowledgment may appear in the software itself, if
023: and wherever such third-party acknowledgments normally appear.
024:
025: 4. The names "Batik" and "Apache Software Foundation" must not be
026: used to endorse or promote products derived from this software without
027: prior written permission. For written permission, please contact
028: apache@apache.org.
029:
030: 5. Products derived from this software may not be called "Apache", nor may
031: "Apache" appear in their name, without prior written permission of the
032: Apache Software Foundation.
033:
034: THIS SOFTWARE IS PROVIDED ``AS IS'' AND ANY EXPRESSED OR IMPLIED WARRANTIES,
035: INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND
036: FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE
037: APACHE SOFTWARE FOUNDATION OR ITS CONTRIBUTORS BE LIABLE FOR ANY DIRECT,
038: INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLU-
039: DING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS
040: OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON
041: ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
042: (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF
043: THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
044:
045: This software consists of voluntary contributions made by many individuals
046: on behalf of the Apache Software Foundation. For more information on the
047: Apache Software Foundation, please see <http://www.apache.org/>.
048:
049: */
050:
051: package org.apache.batik.util;
052:
053: import java.lang.ref.ReferenceQueue;
054: import java.lang.ref.SoftReference;
055:
056: /**
057: * This class represents a doubly indexed hash table, which holds
058: * soft references to the contained values..
059: *
060: * @author <a href="mailto:stephane@hillion.org">Stephane Hillion</a>
061: * @version $Id$
062: */
063: public class SoftDoublyIndexedTable {
064:
065: /**
066: * The initial capacity
067: */
068: protected final static int INITIAL_CAPACITY = 11;
069:
070: /**
071: * The underlying array
072: */
073: protected Entry[] table;
074:
075: /**
076: * The number of entries
077: */
078: protected int count;
079:
080: /**
081: * The reference queue.
082: */
083: protected ReferenceQueue referenceQueue = new ReferenceQueue();
084:
085: /**
086: * Creates a new SoftDoublyIndexedTable.
087: */
088: public SoftDoublyIndexedTable() {
089: table = new Entry[INITIAL_CAPACITY];
090: }
091:
092: /**
093: * Creates a new DoublyIndexedTable.
094: * @param c The inital capacity.
095: */
096: public SoftDoublyIndexedTable(int c) {
097: table = new Entry[c];
098: }
099:
100: /**
101: * Returns the size of this table.
102: */
103: public int size() {
104: return count;
105: }
106:
107: /**
108: * Gets the value of a variable
109: * @return the value or null
110: */
111: public Object get(Object o1, Object o2) {
112: int hash = hashCode(o1, o2) & 0x7FFFFFFF;
113: int index = hash % table.length;
114:
115: for (Entry e = table[index]; e != null; e = e.next) {
116: if ((e.hash == hash) && e.match(o1, o2)) {
117: return e.get();
118: }
119: }
120: return null;
121: }
122:
123: /**
124: * Sets a new value for the given variable
125: * @return the old value or null
126: */
127: public Object put(Object o1, Object o2, Object value) {
128: removeClearedEntries();
129:
130: int hash = hashCode(o1, o2) & 0x7FFFFFFF;
131: int index = hash % table.length;
132:
133: Entry e = table[index];
134: if (e != null) {
135: if ((e.hash == hash) && e.match(o1, o2)) {
136: Object old = e.get();
137: table[index] = new Entry(hash, o1, o2, value, e.next);
138: return old;
139: }
140: Entry o = e;
141: e = e.next;
142: while (e != null) {
143: if ((e.hash == hash) && e.match(o1, o2)) {
144: Object old = e.get();
145: e = new Entry(hash, o1, o2, value, e.next);
146: o.next = e;
147: return old;
148: }
149:
150: o = e;
151: e = e.next;
152: }
153: }
154:
155: // The key is not in the hash table
156: int len = table.length;
157: if (count++ >= (len * 3) >>> 2) {
158: rehash();
159: index = hash % table.length;
160: }
161:
162: table[index] = new Entry(hash, o1, o2, value, table[index]);
163: return null;
164: }
165:
166: /**
167: * Clears the table.
168: */
169: public void clear() {
170: table = new Entry[INITIAL_CAPACITY];
171: count = 0;
172: referenceQueue = new ReferenceQueue();
173: }
174:
175: /**
176: * Rehash the table
177: */
178: protected void rehash() {
179: Entry[] oldTable = table;
180:
181: table = new Entry[oldTable.length * 2 + 1];
182:
183: for (int i = oldTable.length - 1; i >= 0; i--) {
184: for (Entry old = oldTable[i]; old != null;) {
185: Entry e = old;
186: old = old.next;
187:
188: int index = e.hash % table.length;
189: e.next = table[index];
190: table[index] = e;
191: }
192: }
193: }
194:
195: /**
196: * Computes a hash code corresponding to the given objects.
197: */
198: protected int hashCode(Object o1, Object o2) {
199: int result = (o1 == null) ? 0 : o1.hashCode();
200: return result ^ ((o2 == null) ? 0 : o2.hashCode());
201: }
202:
203: /**
204: * Removes the cleared entries.
205: */
206: protected void removeClearedEntries() {
207: Entry e;
208: while ((e = (Entry) referenceQueue.poll()) != null) {
209: int index = e.hash % table.length;
210: Entry t = table[index];
211: if (t == e) {
212: table[index] = e.next;
213: } else {
214: loop: for (; t != null;) {
215: Entry c = t.next;
216: if (c == e) {
217: t.next = e.next;
218: break loop;
219: }
220: t = c;
221: }
222: }
223: count--;
224: }
225: }
226:
227: /**
228: * To manage collisions
229: */
230: protected class Entry extends SoftReference {
231:
232: /**
233: * The hash code
234: */
235: public int hash;
236:
237: /**
238: * The first key
239: */
240: public Object key1;
241:
242: /**
243: * The second key
244: */
245: public Object key2;
246:
247: /**
248: * The next entry
249: */
250: public Entry next;
251:
252: /**
253: * Creates a new entry
254: */
255: public Entry(int hash, Object key1, Object key2, Object value,
256: Entry next) {
257: super (value, referenceQueue);
258: this .hash = hash;
259: this .key1 = key1;
260: this .key2 = key2;
261: this .next = next;
262: }
263:
264: /**
265: * Whether this entry match the given keys.
266: */
267: public boolean match(Object o1, Object o2) {
268: if (key1 != null) {
269: if (!key1.equals(o1)) {
270: return false;
271: }
272: } else if (o1 != null) {
273: return false;
274: }
275: if (key2 != null) {
276: return key2.equals(o2);
277: }
278: return o2 == null;
279: }
280: }
281: }
|