KickJava   Java API By Example, From Geeks To Geeks.

Java > Open Source Codes > org > apache > batik > util > SoftDoublyIndexedTable


1 /*
2
3    Copyright 2001 The Apache Software Foundation
4
5    Licensed under the Apache License, Version 2.0 (the "License");
6    you may not use this file except in compliance with the License.
7    You may obtain a copy of the License at
8
9        http://www.apache.org/licenses/LICENSE-2.0
10
11    Unless required by applicable law or agreed to in writing, software
12    distributed under the License is distributed on an "AS IS" BASIS,
13    WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
14    See the License for the specific language governing permissions and
15    limitations under the License.
16
17  */
18 package org.apache.batik.util;
19
20 import java.lang.ref.ReferenceQueue JavaDoc;
21 import java.lang.ref.SoftReference JavaDoc;
22
23 /**
24  * This class represents a doubly indexed hash table, which holds
25  * soft references to the contained values..
26  *
27  * @author <a HREF="mailto:stephane@hillion.org">Stephane Hillion</a>
28  * @version $Id: SoftDoublyIndexedTable.java,v 1.3 2004/08/18 07:15:50 vhardy Exp $
29  */
30 public class SoftDoublyIndexedTable {
31     
32     /**
33      * The initial capacity
34      */
35     protected final static int INITIAL_CAPACITY = 11;
36
37     /**
38      * The underlying array
39      */
40     protected Entry[] table;
41         
42     /**
43      * The number of entries
44      */
45     protected int count;
46         
47     /**
48      * The reference queue.
49      */
50     protected ReferenceQueue JavaDoc referenceQueue = new ReferenceQueue JavaDoc();
51         
52     /**
53      * Creates a new SoftDoublyIndexedTable.
54      */
55     public SoftDoublyIndexedTable() {
56         table = new Entry[INITIAL_CAPACITY];
57     }
58
59     /**
60      * Creates a new DoublyIndexedTable.
61      * @param c The inital capacity.
62      */
63     public SoftDoublyIndexedTable(int c) {
64         table = new Entry[c];
65     }
66
67     /**
68      * Returns the size of this table.
69      */
70     public int size() {
71     return count;
72     }
73     
74     /**
75      * Gets the value of a variable
76      * @return the value or null
77      */
78     public Object JavaDoc get(Object JavaDoc o1, Object JavaDoc o2) {
79     int hash = hashCode(o1, o2) & 0x7FFFFFFF;
80     int index = hash % table.length;
81     
82     for (Entry e = table[index]; e != null; e = e.next) {
83         if ((e.hash == hash) && e.match(o1, o2)) {
84         return e.get();
85         }
86     }
87     return null;
88     }
89     
90     /**
91      * Sets a new value for the given variable
92      * @return the old value or null
93      */
94     public Object JavaDoc put(Object JavaDoc o1, Object JavaDoc o2, Object JavaDoc value) {
95         removeClearedEntries();
96
97     int hash = hashCode(o1, o2) & 0x7FFFFFFF;
98     int index = hash % table.length;
99
100     Entry e = table[index];
101         if (e != null) {
102         if ((e.hash == hash) && e.match(o1, o2)) {
103         Object JavaDoc old = e.get();
104         table[index] = new Entry(hash, o1, o2, value, e.next);
105         return old;
106         }
107             Entry o = e;
108             e = e.next;
109             while (e != null) {
110                 if ((e.hash == hash) && e.match(o1, o2)) {
111                     Object JavaDoc old = e.get();
112                     e = new Entry(hash, o1, o2, value, e.next);
113                     o.next = e;
114                     return old;
115                 }
116
117                 o = e;
118                 e = e.next;
119             }
120         }
121     
122     // The key is not in the hash table
123 int len = table.length;
124     if (count++ >= (len * 3) >>> 2) {
125         rehash();
126         index = hash % table.length;
127     }
128     
129     table[index] = new Entry(hash, o1, o2, value, table[index]);
130     return null;
131     }
132
133     /**
134      * Clears the table.
135      */
136     public void clear() {
137         table = new Entry[INITIAL_CAPACITY];
138         count = 0;
139         referenceQueue = new ReferenceQueue JavaDoc();
140     }
141
142     /**
143      * Rehash the table
144      */
145     protected void rehash () {
146     Entry[] oldTable = table;
147     
148     table = new Entry[oldTable.length * 2 + 1];
149     
150     for (int i = oldTable.length-1; i >= 0; i--) {
151         for (Entry old = oldTable[i]; old != null;) {
152         Entry e = old;
153         old = old.next;
154         
155         int index = e.hash % table.length;
156         e.next = table[index];
157         table[index] = e;
158         }
159     }
160     }
161
162     /**
163      * Computes a hash code corresponding to the given objects.
164      */
165     protected int hashCode(Object JavaDoc o1, Object JavaDoc o2) {
166         int result = (o1 == null) ? 0 : o1.hashCode();
167         return result ^ ((o2 == null) ? 0 : o2.hashCode());
168     }
169
170     /**
171      * Removes the cleared entries.
172      */
173     protected void removeClearedEntries() {
174         Entry e;
175         while ((e = (Entry)referenceQueue.poll()) != null) {
176             int index = e.hash % table.length;
177             Entry t = table[index];
178             if (t == e) {
179                 table[index] = e.next;
180             } else {
181                 loop: for (;t!=null;) {
182                     Entry c = t.next;
183                     if (c == e) {
184                         t.next = e.next;
185                         break loop;
186                     }
187                     t = c;
188                 }
189             }
190             count--;
191         }
192     }
193
194     /**
195      * To manage collisions
196      */
197     protected class Entry extends SoftReference JavaDoc {
198
199     /**
200      * The hash code
201      */
202     public int hash;
203     
204     /**
205      * The first key
206      */
207     public Object JavaDoc key1;
208     
209     /**
210      * The second key
211      */
212     public Object JavaDoc key2;
213     
214     /**
215      * The next entry
216      */
217     public Entry next;
218     
219     /**
220      * Creates a new entry
221      */
222     public Entry(int hash, Object JavaDoc key1, Object JavaDoc key2, Object JavaDoc value, Entry next) {
223             super(value, referenceQueue);
224         this.hash = hash;
225         this.key1 = key1;
226         this.key2 = key2;
227         this.next = next;
228     }
229
230         /**
231          * Whether this entry match the given keys.
232          */
233         public boolean match(Object JavaDoc o1, Object JavaDoc o2) {
234             if (key1 != null) {
235                 if (!key1.equals(o1)) {
236                     return false;
237                 }
238             } else if (o1 != null) {
239                 return false;
240             }
241             if (key2 != null) {
242                 return key2.equals(o2);
243             }
244             return o2 == null;
245         }
246     }
247 }
248
Popular Tags