1 /******************************************************************************* 2 * Copyright (c) 2000, 2010 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 import org.eclipse.jdt.core.compiler.CharOperation; 17 18 /** 19 * Hashtable of {char[] --> Object } 20 */ 21 public final class HashtableOfObject implements Cloneable { 22 23 // to avoid using Enumerations, walk the individual tables skipping nulls 24 public char[] keyTable[]; 25 public Object valueTable[]; 26 27 public int elementSize; // number of elements in the table 28 int threshold; 29 HashtableOfObject()30 public HashtableOfObject() { 31 this(13); 32 } 33 HashtableOfObject(int size)34 public HashtableOfObject(int size) { 35 36 this.elementSize = 0; 37 this.threshold = size; // size represents the expected number of elements 38 int extraRoom = (int) (size * 1.75f); 39 if (this.threshold == extraRoom) 40 extraRoom++; 41 this.keyTable = new char[extraRoom][]; 42 this.valueTable = new Object[extraRoom]; 43 } 44 clear()45 public void clear() { 46 for (int i = this.keyTable.length; --i >= 0;) { 47 this.keyTable[i] = null; 48 this.valueTable[i] = null; 49 } 50 this.elementSize = 0; 51 } 52 53 @Override clone()54 public Object clone() throws CloneNotSupportedException { 55 HashtableOfObject result = (HashtableOfObject) super.clone(); 56 result.elementSize = this.elementSize; 57 result.threshold = this.threshold; 58 59 int length = this.keyTable.length; 60 result.keyTable = new char[length][]; 61 System.arraycopy(this.keyTable, 0, result.keyTable, 0, length); 62 63 length = this.valueTable.length; 64 result.valueTable = new Object[length]; 65 System.arraycopy(this.valueTable, 0, result.valueTable, 0, length); 66 return result; 67 } 68 containsKey(char[] key)69 public boolean containsKey(char[] key) { 70 int length = this.keyTable.length, 71 index = CharOperation.hashCode(key) % length; 72 int keyLength = key.length; 73 char[] currentKey; 74 while ((currentKey = this.keyTable[index]) != null) { 75 if (currentKey.length == keyLength && CharOperation.equals(currentKey, key)) 76 return true; 77 if (++index == length) { 78 index = 0; 79 } 80 } 81 return false; 82 } 83 get(char[] key)84 public Object get(char[] key) { 85 int length = this.keyTable.length, 86 index = CharOperation.hashCode(key) % length; 87 int keyLength = key.length; 88 char[] currentKey; 89 while ((currentKey = this.keyTable[index]) != null) { 90 if (currentKey.length == keyLength && CharOperation.equals(currentKey, key)) 91 return this.valueTable[index]; 92 if (++index == length) { 93 index = 0; 94 } 95 } 96 return null; 97 } 98 put(char[] key, Object value)99 public Object put(char[] key, Object value) { 100 int length = this.keyTable.length, 101 index = CharOperation.hashCode(key) % length; 102 int keyLength = key.length; 103 char[] currentKey; 104 while ((currentKey = this.keyTable[index]) != null) { 105 if (currentKey.length == keyLength && CharOperation.equals(currentKey, key)) 106 return this.valueTable[index] = value; 107 if (++index == length) { 108 index = 0; 109 } 110 } 111 this.keyTable[index] = key; 112 this.valueTable[index] = value; 113 114 // assumes the threshold is never equal to the size of the table 115 if (++this.elementSize > this.threshold) 116 rehash(); 117 return value; 118 } 119 120 /** 121 * Put a value at the index of the given using the local hash code computation. 122 * <p> 123 * Note that this is an unsafe put as there's no prior verification whether 124 * the given key already exists in the table or not. 125 * </p> 126 * @param key The key of the table entry 127 * @param value The value of the table entry 128 */ putUnsafely(char[] key, Object value)129 public void putUnsafely(char[] key, Object value) { 130 int length = this.keyTable.length, 131 index = CharOperation.hashCode(key) % length; 132 while (this.keyTable[index] != null) { 133 if (++index == length) { 134 index = 0; 135 } 136 } 137 this.keyTable[index] = key; 138 this.valueTable[index] = value; 139 140 // assumes the threshold is never equal to the size of the table 141 if (++this.elementSize > this.threshold) { 142 rehash(); 143 } 144 } 145 removeKey(char[] key)146 public Object removeKey(char[] key) { 147 int length = this.keyTable.length, 148 index = CharOperation.hashCode(key) % length; 149 int keyLength = key.length; 150 char[] currentKey; 151 while ((currentKey = this.keyTable[index]) != null) { 152 if (currentKey.length == keyLength && CharOperation.equals(currentKey, key)) { 153 Object value = this.valueTable[index]; 154 this.elementSize--; 155 this.keyTable[index] = null; 156 this.valueTable[index] = null; 157 rehash(); 158 return value; 159 } 160 if (++index == length) { 161 index = 0; 162 } 163 } 164 return null; 165 } 166 rehash()167 private void rehash() { 168 169 HashtableOfObject newHashtable = new HashtableOfObject(this.elementSize * 2); // double the number of expected elements 170 char[] currentKey; 171 for (int i = this.keyTable.length; --i >= 0;) 172 if ((currentKey = this.keyTable[i]) != null) 173 newHashtable.putUnsafely(currentKey, this.valueTable[i]); 174 175 this.keyTable = newHashtable.keyTable; 176 this.valueTable = newHashtable.valueTable; 177 this.threshold = newHashtable.threshold; 178 } 179 size()180 public int size() { 181 return this.elementSize; 182 } 183 184 @Override toString()185 public String toString() { 186 String s = ""; //$NON-NLS-1$ 187 Object object; 188 for (int i = 0, length = this.valueTable.length; i < length; i++) 189 if ((object = this.valueTable[i]) != null) 190 s += new String(this.keyTable[i]) + " -> " + object.toString() + "\n"; //$NON-NLS-2$ //$NON-NLS-1$ 191 return s; 192 } 193 } 194