1 /*******************************************************************************
2 * Copyright (c) 2000, 2009 IBM Corporation and others.
3 *
4 * This program and the accompanying materials
5 * are made available under the terms of the Eclipse Public License 2.0
6 * which accompanies this distribution, and is available at
7 * https://www.eclipse.org/legal/epl-2.0/
8 *
9 * SPDX-License-Identifier: EPL-2.0
10 *
11 * Contributors:
12 * IBM Corporation - initial API and implementation
13 *******************************************************************************/
14 package org.eclipse.jdt.internal.compiler.util;
15
16 /**
17 * A simple lookup table is a non-synchronized Hashtable, whose keys
18 * and values are Objects. It also uses linear probing to resolve collisions
19 * rather than a linked list of hash table entries.
20 */
21 public final class SimpleLookupTable implements Cloneable {
22
23 // to avoid using Enumerations, walk the individual tables skipping nulls
24 public Object[] keyTable;
25 public Object[] valueTable;
26 public int elementSize; // number of elements in the table
27 public int threshold;
28
SimpleLookupTable()29 public SimpleLookupTable() {
30 this(13);
31 }
32
SimpleLookupTable(int size)33 public SimpleLookupTable(int size) {
34 this.elementSize = 0;
35 this.threshold = size; // size represents the expected number of elements
36 int extraRoom = (int) (size * 1.5f);
37 if (this.threshold == extraRoom)
38 extraRoom++;
39 this.keyTable = new Object[extraRoom];
40 this.valueTable = new Object[extraRoom];
41 }
42
43 @Override
clone()44 public Object clone() throws CloneNotSupportedException {
45 SimpleLookupTable result = (SimpleLookupTable) super.clone();
46 result.elementSize = this.elementSize;
47 result.threshold = this.threshold;
48
49 int length = this.keyTable.length;
50 result.keyTable = new Object[length];
51 System.arraycopy(this.keyTable, 0, result.keyTable, 0, length);
52
53 length = this.valueTable.length;
54 result.valueTable = new Object[length];
55 System.arraycopy(this.valueTable, 0, result.valueTable, 0, length);
56 return result;
57 }
58
containsKey(Object key)59 public boolean containsKey(Object key) {
60 int length = this.keyTable.length;
61 int index = (key.hashCode() & 0x7FFFFFFF) % length;
62 Object currentKey;
63 while ((currentKey = this.keyTable[index]) != null) {
64 if (currentKey.equals(key)) return true;
65 if (++index == length) index = 0;
66 }
67 return false;
68 }
69
get(Object key)70 public Object get(Object key) {
71 int length = this.keyTable.length;
72 int index = (key.hashCode() & 0x7FFFFFFF) % length;
73 Object currentKey;
74 while ((currentKey = this.keyTable[index]) != null) {
75 if (currentKey.equals(key)) return this.valueTable[index];
76 if (++index == length) index = 0;
77 }
78 return null;
79 }
80
getKey(Object key)81 public Object getKey(Object key) {
82 int length = this.keyTable.length;
83 int index = (key.hashCode() & 0x7FFFFFFF) % length;
84 Object currentKey;
85 while ((currentKey = this.keyTable[index]) != null) {
86 if (currentKey.equals(key)) return currentKey;
87 if (++index == length) index = 0;
88 }
89 return key;
90 }
91
keyForValue(Object valueToMatch)92 public Object keyForValue(Object valueToMatch) {
93 if (valueToMatch != null)
94 for (int i = 0, l = this.keyTable.length; i < l; i++)
95 if (this.keyTable[i] != null && valueToMatch.equals(this.valueTable[i]))
96 return this.keyTable[i];
97 return null;
98 }
99
put(Object key, Object value)100 public Object put(Object key, Object value) {
101 int length = this.keyTable.length;
102 int index = (key.hashCode() & 0x7FFFFFFF) % length;
103 Object currentKey;
104 while ((currentKey = this.keyTable[index]) != null) {
105 if (currentKey.equals(key)) return this.valueTable[index] = value;
106 if (++index == length) index = 0;
107 }
108 this.keyTable[index] = key;
109 this.valueTable[index] = value;
110
111 // assumes the threshold is never equal to the size of the table
112 if (++this.elementSize > this.threshold) rehash();
113 return value;
114 }
115
removeKey(Object key)116 public Object removeKey(Object key) {
117 int length = this.keyTable.length;
118 int index = (key.hashCode() & 0x7FFFFFFF) % length;
119 Object currentKey;
120 while ((currentKey = this.keyTable[index]) != null) {
121 if (currentKey.equals(key)) {
122 this.elementSize--;
123 Object oldValue = this.valueTable[index];
124 this.keyTable[index] = null;
125 this.valueTable[index] = null;
126 if (this.keyTable[index + 1 == length ? 0 : index + 1] != null)
127 rehash(); // only needed if a possible collision existed
128 return oldValue;
129 }
130 if (++index == length) index = 0;
131 }
132 return null;
133 }
134
removeValue(Object valueToRemove)135 public void removeValue(Object valueToRemove) {
136 boolean rehash = false;
137 for (int i = 0, l = this.valueTable.length; i < l; i++) {
138 Object value = this.valueTable[i];
139 if (value != null && value.equals(valueToRemove)) {
140 this.elementSize--;
141 this.keyTable[i] = null;
142 this.valueTable[i] = null;
143 if (!rehash && this.keyTable[i + 1 == l ? 0 : i + 1] != null)
144 rehash = true; // only needed if a possible collision existed
145 }
146 }
147 if (rehash) rehash();
148 }
149
rehash()150 private void rehash() {
151 SimpleLookupTable newLookupTable = new SimpleLookupTable(this.elementSize * 2); // double the number of expected elements
152 Object currentKey;
153 for (int i = this.keyTable.length; --i >= 0;)
154 if ((currentKey = this.keyTable[i]) != null)
155 newLookupTable.put(currentKey, this.valueTable[i]);
156
157 this.keyTable = newLookupTable.keyTable;
158 this.valueTable = newLookupTable.valueTable;
159 this.elementSize = newLookupTable.elementSize;
160 this.threshold = newLookupTable.threshold;
161 }
162
163 @Override
toString()164 public String toString() {
165 String s = ""; //$NON-NLS-1$
166 Object object;
167 for (int i = 0, l = this.valueTable.length; i < l; i++)
168 if ((object = this.valueTable[i]) != null)
169 s += this.keyTable[i].toString() + " -> " + object.toString() + "\n"; //$NON-NLS-2$ //$NON-NLS-1$
170 return s;
171 }
172 }
173