001: /*******************************************************************************
002: * Copyright (c) 2000, 2007 IBM Corporation and others.
003: * All rights reserved. This program and the accompanying materials
004: * are made available under the terms of the Eclipse Public License v1.0
005: * which accompanies this distribution, and is available at
006: * http://www.eclipse.org/legal/epl-v10.html
007: *
008: * Contributors:
009: * IBM Corporation - initial API and implementation
010: *******************************************************************************/package org.eclipse.jdt.internal.compiler.util;
011:
012: /**
013: * A simple lookup table is a non-synchronized Hashtable, whose keys
014: * and values are Objects. It also uses linear probing to resolve collisions
015: * rather than a linked list of hash table entries.
016: */
017: public final class SimpleLookupTable implements Cloneable {
018:
019: // to avoid using Enumerations, walk the individual tables skipping nulls
020: public Object[] keyTable;
021: public Object[] valueTable;
022: public int elementSize; // number of elements in the table
023: public int threshold;
024:
025: public SimpleLookupTable() {
026: this (13);
027: }
028:
029: public SimpleLookupTable(int size) {
030: this .elementSize = 0;
031: this .threshold = size; // size represents the expected number of elements
032: int extraRoom = (int) (size * 1.5f);
033: if (this .threshold == extraRoom)
034: extraRoom++;
035: this .keyTable = new Object[extraRoom];
036: this .valueTable = new Object[extraRoom];
037: }
038:
039: public Object clone() throws CloneNotSupportedException {
040: SimpleLookupTable result = (SimpleLookupTable) super .clone();
041: result.elementSize = this .elementSize;
042: result.threshold = this .threshold;
043:
044: int length = this .keyTable.length;
045: result.keyTable = new Object[length];
046: System.arraycopy(this .keyTable, 0, result.keyTable, 0, length);
047:
048: length = this .valueTable.length;
049: result.valueTable = new Object[length];
050: System.arraycopy(this .valueTable, 0, result.valueTable, 0,
051: length);
052: return result;
053: }
054:
055: public boolean containsKey(Object key) {
056: int length = keyTable.length;
057: int index = (key.hashCode() & 0x7FFFFFFF) % length;
058: Object currentKey;
059: while ((currentKey = keyTable[index]) != null) {
060: if (currentKey.equals(key))
061: return true;
062: if (++index == length)
063: index = 0;
064: }
065: return false;
066: }
067:
068: public Object get(Object key) {
069: int length = keyTable.length;
070: int index = (key.hashCode() & 0x7FFFFFFF) % length;
071: Object currentKey;
072: while ((currentKey = keyTable[index]) != null) {
073: if (currentKey.equals(key))
074: return valueTable[index];
075: if (++index == length)
076: index = 0;
077: }
078: return null;
079: }
080:
081: public Object getKey(Object key) {
082: int length = keyTable.length;
083: int index = (key.hashCode() & 0x7FFFFFFF) % length;
084: Object currentKey;
085: while ((currentKey = keyTable[index]) != null) {
086: if (currentKey.equals(key))
087: return currentKey;
088: if (++index == length)
089: index = 0;
090: }
091: return key;
092: }
093:
094: public Object keyForValue(Object valueToMatch) {
095: if (valueToMatch != null)
096: for (int i = 0, l = keyTable.length; i < l; i++)
097: if (keyTable[i] != null
098: && valueToMatch.equals(valueTable[i]))
099: return keyTable[i];
100: return null;
101: }
102:
103: public Object put(Object key, Object value) {
104: int length = keyTable.length;
105: int index = (key.hashCode() & 0x7FFFFFFF) % length;
106: Object currentKey;
107: while ((currentKey = keyTable[index]) != null) {
108: if (currentKey.equals(key))
109: return valueTable[index] = value;
110: if (++index == length)
111: index = 0;
112: }
113: keyTable[index] = key;
114: valueTable[index] = value;
115:
116: // assumes the threshold is never equal to the size of the table
117: if (++elementSize > threshold)
118: rehash();
119: return value;
120: }
121:
122: public Object removeKey(Object key) {
123: int length = keyTable.length;
124: int index = (key.hashCode() & 0x7FFFFFFF) % length;
125: Object currentKey;
126: while ((currentKey = keyTable[index]) != null) {
127: if (currentKey.equals(key)) {
128: elementSize--;
129: Object oldValue = valueTable[index];
130: keyTable[index] = null;
131: valueTable[index] = null;
132: if (keyTable[index + 1 == length ? 0 : index + 1] != null)
133: rehash(); // only needed if a possible collision existed
134: return oldValue;
135: }
136: if (++index == length)
137: index = 0;
138: }
139: return null;
140: }
141:
142: public void removeValue(Object valueToRemove) {
143: boolean rehash = false;
144: for (int i = 0, l = valueTable.length; i < l; i++) {
145: Object value = valueTable[i];
146: if (value != null && value.equals(valueToRemove)) {
147: elementSize--;
148: keyTable[i] = null;
149: valueTable[i] = null;
150: if (!rehash && keyTable[i + 1 == l ? 0 : i + 1] != null)
151: rehash = true; // only needed if a possible collision existed
152: }
153: }
154: if (rehash)
155: rehash();
156: }
157:
158: private void rehash() {
159: SimpleLookupTable newLookupTable = new SimpleLookupTable(
160: elementSize * 2); // double the number of expected elements
161: Object currentKey;
162: for (int i = keyTable.length; --i >= 0;)
163: if ((currentKey = keyTable[i]) != null)
164: newLookupTable.put(currentKey, valueTable[i]);
165:
166: this .keyTable = newLookupTable.keyTable;
167: this .valueTable = newLookupTable.valueTable;
168: this .elementSize = newLookupTable.elementSize;
169: this .threshold = newLookupTable.threshold;
170: }
171:
172: public String toString() {
173: String s = ""; //$NON-NLS-1$
174: Object object;
175: for (int i = 0, l = valueTable.length; i < l; i++)
176: if ((object = valueTable[i]) != null)
177: s += keyTable[i].toString()
178: + " -> " + object.toString() + "\n"; //$NON-NLS-2$ //$NON-NLS-1$
179: return s;
180: }
181: }
|