001: /*******************************************************************************
002: * Copyright (c) 2000, 2006 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.core.util;
011:
012: /**
013: * Hashtable of {Object[] --> Object }
014: */
015: public final class HashtableOfArrayToObject implements Cloneable {
016:
017: // to avoid using Enumerations, walk the individual tables skipping nulls
018: public Object[][] keyTable;
019: public Object[] valueTable;
020:
021: public int elementSize; // number of elements in the table
022: int threshold;
023:
024: public HashtableOfArrayToObject() {
025: this (13);
026: }
027:
028: public HashtableOfArrayToObject(int size) {
029:
030: this .elementSize = 0;
031: this .threshold = size; // size represents the expected number of elements
032: int extraRoom = (int) (size * 1.75f);
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: HashtableOfArrayToObject result = (HashtableOfArrayToObject) super
041: .clone();
042: result.elementSize = this .elementSize;
043: result.threshold = this .threshold;
044:
045: int length = this .keyTable.length;
046: result.keyTable = new Object[length][];
047: System.arraycopy(this .keyTable, 0, result.keyTable, 0, length);
048:
049: length = this .valueTable.length;
050: result.valueTable = new Object[length];
051: System.arraycopy(this .valueTable, 0, result.valueTable, 0,
052: length);
053: return result;
054: }
055:
056: public boolean containsKey(Object[] key) {
057: int length = this .keyTable.length;
058: int index = hashCode(key) % length;
059: int keyLength = key.length;
060: Object[] currentKey;
061: while ((currentKey = this .keyTable[index]) != null) {
062: if (currentKey.length == keyLength
063: && Util.equalArraysOrNull(currentKey, key))
064: return true;
065: if (++index == length) {
066: index = 0;
067: }
068: }
069: return false;
070: }
071:
072: public Object get(Object[] key) {
073: int length = this .keyTable.length;
074: int index = hashCode(key) % length;
075: int keyLength = key.length;
076: Object[] currentKey;
077: while ((currentKey = this .keyTable[index]) != null) {
078: if (currentKey.length == keyLength
079: && Util.equalArraysOrNull(currentKey, key))
080: return this .valueTable[index];
081: if (++index == length) {
082: index = 0;
083: }
084: }
085: return null;
086: }
087:
088: public Object[] getKey(Object[] key, int keyLength) {
089: int length = this .keyTable.length;
090: int index = hashCode(key, keyLength) % length;
091: Object[] currentKey;
092: while ((currentKey = this .keyTable[index]) != null) {
093: if (currentKey.length == keyLength
094: && Util.equalArrays(currentKey, key, keyLength))
095: return currentKey;
096: if (++index == length) {
097: index = 0;
098: }
099: }
100: return null;
101: }
102:
103: private int hashCode(Object[] element) {
104: return hashCode(element, element.length);
105: }
106:
107: private int hashCode(Object[] element, int length) {
108: int hash = 0;
109: for (int i = length - 1; i >= 0; i--)
110: hash = Util.combineHashCodes(hash, element[i].hashCode());
111: return hash & 0x7FFFFFFF;
112: }
113:
114: public Object put(Object[] key, Object value) {
115: int length = this .keyTable.length;
116: int index = hashCode(key) % length;
117: int keyLength = key.length;
118: Object[] currentKey;
119: while ((currentKey = this .keyTable[index]) != null) {
120: if (currentKey.length == keyLength
121: && Util.equalArraysOrNull(currentKey, key))
122: return this .valueTable[index] = value;
123: if (++index == length) {
124: index = 0;
125: }
126: }
127: this .keyTable[index] = key;
128: this .valueTable[index] = value;
129:
130: // assumes the threshold is never equal to the size of the table
131: if (++this .elementSize > threshold)
132: rehash();
133: return value;
134: }
135:
136: public Object removeKey(Object[] key) {
137: int length = this .keyTable.length;
138: int index = hashCode(key) % length;
139: int keyLength = key.length;
140: Object[] currentKey;
141: while ((currentKey = this .keyTable[index]) != null) {
142: if (currentKey.length == keyLength
143: && Util.equalArraysOrNull(currentKey, key)) {
144: Object value = this .valueTable[index];
145: this .elementSize--;
146: this .keyTable[index] = null;
147: this .valueTable[index] = null;
148: rehash();
149: return value;
150: }
151: if (++index == length) {
152: index = 0;
153: }
154: }
155: return null;
156: }
157:
158: private void rehash() {
159:
160: HashtableOfArrayToObject newHashtable = new HashtableOfArrayToObject(
161: elementSize * 2); // double the number of expected elements
162: Object[] currentKey;
163: for (int i = this .keyTable.length; --i >= 0;)
164: if ((currentKey = this .keyTable[i]) != null)
165: newHashtable.put(currentKey, this .valueTable[i]);
166:
167: this .keyTable = newHashtable.keyTable;
168: this .valueTable = newHashtable.valueTable;
169: this .threshold = newHashtable.threshold;
170: }
171:
172: public int size() {
173: return elementSize;
174: }
175:
176: public String toString() {
177: StringBuffer buffer = new StringBuffer();
178: Object[] element;
179: for (int i = 0, length = this .keyTable.length; i < length; i++)
180: if ((element = this .keyTable[i]) != null) {
181: buffer.append('{');
182: for (int j = 0, length2 = element.length; j < length2; j++) {
183: buffer.append(element[j]);
184: if (j != length2 - 1)
185: buffer.append(", "); //$NON-NLS-1$
186: }
187: buffer.append("} -> "); //$NON-NLS-1$
188: buffer.append(this .valueTable[i]);
189: if (i != length - 1)
190: buffer.append('\n');
191: }
192: return buffer.toString();
193: }
194: }
|