1 /*
2
3 Licensed to the Apache Software Foundation (ASF) under one or more
4 contributor license agreements. See the NOTICE file distributed with
5 this work for additional information regarding copyright ownership.
6 The ASF licenses this file to You under the Apache License, Version 2.0
7 (the "License"); you may not use this file except in compliance with
8 the License. You may obtain a copy of the License at
9
10 http://www.apache.org/licenses/LICENSE-2.0
11
12 Unless required by applicable law or agreed to in writing, software
13 distributed under the License is distributed on an "AS IS" BASIS,
14 WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
15 See the License for the specific language governing permissions and
16 limitations under the License.
17
18 */
19 package org.apache.batik.util;
20
21 import java.util.Iterator;
22 import java.util.NoSuchElementException;
23
24 /**
25 * This class represents a doubly indexed hash table.
26 *
27 * @author <a href="mailto:stephane@hillion.org">Stephane Hillion</a>
28 * @version $Id: DoublyIndexedTable.java 1804130 2017-08-04 14:41:11Z ssteiner $
29 */
30 public class DoublyIndexedTable {
31
32 /**
33 * The initial capacity
34 */
35 protected int initialCapacity;
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 * Creates a new DoublyIndexedTable.
49 */
50 public DoublyIndexedTable() {
51 this(16);
52 }
53
54 /**
55 * Creates a new DoublyIndexedTable.
56 * @param c The inital capacity.
57 */
58 public DoublyIndexedTable(int c) {
59 initialCapacity = c;
60 table = new Entry[c];
61 }
62
63 /**
64 * Creates a new DoublyIndexedTable initialized to contain all of
65 * the entries of the specified other DoublyIndexedTable.
66 */
67 public DoublyIndexedTable(DoublyIndexedTable other) {
68 initialCapacity = other.initialCapacity;
69 table = new Entry[other.table.length];
70 for (int i = 0; i < other.table.length; i++) {
71 Entry newE = null;
72 Entry e = other.table[i];
73 while (e != null) {
74 newE = new Entry(e.hash, e.key1, e.key2, e.value, newE);
75 e = e.next;
76 }
77 table[i] = newE;
78 }
79 count = other.count;
80 }
81
82 /**
83 * Returns the size of this table.
84 */
85 public int size() {
86 return count;
87 }
88
89 /**
90 * Puts a value in the table.
91 * @return the old value or null
92 */
93 public Object put(Object o1, Object o2, Object value) {
94 int hash = hashCode(o1, o2) & 0x7FFFFFFF;
95 int index = hash % table.length;
96
97 for (Entry e = table[index]; e != null; e = e.next) {
98 if ((e.hash == hash) && e.match(o1, o2)) {
99 Object old = e.value;
100 e.value = value;
101 return old;
102 }
103 }
104
105 // The key is not in the hash table
106 int len = table.length;
107 if (count++ >= (len - (len >> 2))) {
108 // more than 75% loaded: grow
109 rehash();
110 index = hash % table.length;
111 }
112
113 Entry e = new Entry(hash, o1, o2, value, table[index]);
114 table[index] = e;
115 return null;
116 }
117
118 /**
119 * Gets the value of an entry
120 * @return the value or null
121 */
122 public Object get(Object o1, Object o2) {
123 int hash = hashCode(o1, o2) & 0x7FFFFFFF;
124 int index = hash % table.length;
125
126 for (Entry e = table[index]; e != null; e = e.next) {
127 if ((e.hash == hash) && e.match(o1, o2)) {
128 return e.value;
129 }
130 }
131 return null;
132 }
133
134 /**
135 * Removes an entry from the table.
136 * @return the value or null
137 */
138 public Object remove(Object o1, Object o2) {
139 int hash = hashCode(o1, o2) & 0x7FFFFFFF;
140 int index = hash % table.length;
141
142 Entry e = table[index];
143 if (e == null) {
144 return null;
145 }
146
147 if (e.hash == hash && e.match(o1, o2)) {
148 table[index] = e.next;
149 count--;
150 return e.value;
151 }
152
153 Entry prev = e;
154 for (e = e.next; e != null; prev = e, e = e.next) {
155 if (e.hash == hash && e.match(o1, o2)) {
156 prev.next = e.next;
157 count--;
158 return e.value;
159 }
160 }
161 return null;
162 }
163
164 /**
165 * Returns an array of all of the values in the table.
166 */
167 public Object[] getValuesArray() {
168 Object[] values = new Object[count];
169 int i = 0;
170
171 for (Entry aTable : table) {
172 for (Entry e = aTable; e != null; e = e.next) {
173 values[i++] = e.value;
174 }
175 }
176 return values;
177 }
178
179 /**
180 * Clears the table.
181 */
182 public void clear() {
183 table = new Entry[initialCapacity];
184 count = 0;
185 }
186
187 /**
188 * Returns an iterator on the entries of the table.
189 */
190 public Iterator iterator() {
191 return new TableIterator();
192 }
193
194 /**
195 * Rehash the table
196 */
197 protected void rehash() {
198 Entry[] oldTable = table;
199
200 table = new Entry[oldTable.length * 2 + 1];
201
202 for (int i = oldTable.length-1; i >= 0; i--) {
203 for (Entry old = oldTable[i]; old != null;) {
204 Entry e = old;
205 old = old.next;
206
207 int index = e.hash % table.length;
208 e.next = table[index];
209 table[index] = e;
210 }
211 }
212 }
213
214 /**
215 * Computes a hash code corresponding to the given objects.
216 */
217 protected int hashCode(Object o1, Object o2) {
218 int result = (o1 == null) ? 0 : o1.hashCode();
219 return result ^ ((o2 == null) ? 0 : o2.hashCode());
220 }
221
222 /**
223 * An entry in the {@link DoublyIndexedTable}.
224 */
225 public static class Entry {
226
227 /**
228 * The hash code.
229 */
230 protected int hash;
231
232 /**
233 * The first key.
234 */
235 protected Object key1;
236
237 /**
238 * The second key.
239 */
240 protected Object key2;
241
242 /**
243 * The value.
244 */
245 protected Object value;
246
247 /**
248 * The next entry.
249 */
250 protected 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 this.hash = hash;
258 this.key1 = key1;
259 this.key2 = key2;
260 this.value = value;
261 this.next = next;
262 }
263
264 /**
265 * Returns this entry's first key.
266 */
267 public Object getKey1() {
268 return key1;
269 }
270
271 /**
272 * Returns this entry's second key.
273 */
274 public Object getKey2() {
275 return key2;
276 }
277
278 /**
279 * Returns this entry's value.
280 */
281 public Object getValue() {
282 return value;
283 }
284
285 /**
286 * Whether this entry match the given keys.
287 */
288 protected boolean match(Object o1, Object o2) {
289 if (key1 != null) {
290 if (!key1.equals(o1)) {
291 return false;
292 }
293 } else if (o1 != null) {
294 return false;
295 }
296 if (key2 != null) {
297 return key2.equals(o2);
298 }
299 return o2 == null;
300 }
301 }
302
303 /**
304 * An Iterator class for a {@link DoublyIndexedTable}.
305 */
306 protected class TableIterator implements Iterator {
307
308 /**
309 * The index of the next entry to return.
310 */
311 private int nextIndex;
312
313 /**
314 * The next Entry to return.
315 */
316 private Entry nextEntry;
317
318 /**
319 * Whether the Iterator has run out of elements.
320 */
321 private boolean finished;
322
323 /**
324 * Creates a new TableIterator.
325 */
326 public TableIterator() {
327 while (nextIndex < table.length) {
328 nextEntry = table[nextIndex];
329 if (nextEntry != null) {
330 break;
331 }
332 nextIndex++;
333 }
334 finished = nextEntry == null;
335 }
336
337 public boolean hasNext() {
338 return !finished;
339 }
340
341 public Object next() {
342 if (finished) {
343 throw new NoSuchElementException();
344 }
345 Entry ret = nextEntry;
346 findNext();
347 return ret;
348 }
349
350 /**
351 * Searches for the next Entry in the table.
352 */
353 protected void findNext() {
354 nextEntry = nextEntry.next;
355 if (nextEntry == null) {
356 nextIndex++;
357 while (nextIndex < table.length) {
358 nextEntry = table[nextIndex];
359 if (nextEntry != null) {
360 break;
361 }
362 nextIndex++;
363 }
364 }
365 finished = nextEntry == null;
366 }
367
368 public void remove() {
369 throw new UnsupportedOperationException();
370 }
371 }
372 }
373