1 /******************************************************************************* 2 * Copyright (c) 2018 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 * Hashtable for Integer keys. 18 */ 19 20 public final class HashtableOfInteger { 21 22 // to avoid using Enumerations, walk the individual tables skipping nulls 23 public Integer keyTable[]; 24 public Object valueTable[]; 25 26 public int elementSize; // number of elements in the table 27 int threshold; 28 HashtableOfInteger()29 public HashtableOfInteger() { 30 this(13); 31 } 32 HashtableOfInteger(int size)33 public HashtableOfInteger(int size) { 34 35 this.elementSize = 0; 36 this.threshold = size; // size represents the expected number of elements 37 int extraRoom = (int) (size * 1.75f); 38 if (this.threshold == extraRoom) 39 extraRoom++; 40 this.keyTable = new Integer[extraRoom]; 41 this.valueTable = new Object[extraRoom]; 42 } 43 clear()44 public void clear() { 45 for (int i = this.keyTable.length; --i >= 0;) { 46 this.keyTable[i] = null; 47 this.valueTable[i] = null; 48 } 49 this.elementSize = 0; 50 } 51 52 @Override clone()53 public Object clone() throws CloneNotSupportedException { 54 HashtableOfInteger result = (HashtableOfInteger) super.clone(); 55 result.elementSize = this.elementSize; 56 result.threshold = this.threshold; 57 58 int length = this.keyTable.length; 59 result.keyTable = new Integer[length]; 60 System.arraycopy(this.keyTable, 0, result.keyTable, 0, length); 61 62 length = this.valueTable.length; 63 result.valueTable = new Object[length]; 64 System.arraycopy(this.valueTable, 0, result.valueTable, 0, length); 65 return result; 66 } 67 containsKey(int key)68 public boolean containsKey(int key) { 69 Integer intKey = Integer.valueOf(key); 70 int length = this.keyTable.length, 71 index = intKey.hashCode() % length; 72 Integer currentKey; 73 while ((currentKey = this.keyTable[index]) != null) { 74 if (currentKey.equals(intKey)) 75 return true; 76 if (++index == length) { 77 index = 0; 78 } 79 } 80 return false; 81 } 82 get(int key)83 public Object get(int key) { 84 Integer intKey = Integer.valueOf(key); 85 int length = this.keyTable.length, 86 index = intKey.hashCode() % length; 87 Integer currentKey; 88 while ((currentKey = this.keyTable[index]) != null) { 89 if (currentKey.equals(intKey)) 90 return this.valueTable[index]; 91 if (++index == length) { 92 index = 0; 93 } 94 } 95 return null; 96 } 97 put(int key, Object value)98 public Object put(int key, Object value) { 99 Integer intKey = Integer.valueOf(key); 100 int length = this.keyTable.length, 101 index = intKey.hashCode() % length; 102 Integer currentKey; 103 while ((currentKey = this.keyTable[index]) != null) { 104 if (currentKey.equals(intKey)) 105 return this.valueTable[index] = value; 106 if (++index == length) { 107 index = 0; 108 } 109 } 110 this.keyTable[index] = intKey; 111 this.valueTable[index] = value; 112 113 // assumes the threshold is never equal to the size of the table 114 if (++this.elementSize > this.threshold) 115 rehash(); 116 return value; 117 } 118 119 /** 120 * Put a value at the index of the given using the local hash code computation. 121 * <p> 122 * Note that this is an unsafe put as there's no prior verification whether 123 * the given key already exists in the table or not. 124 * </p> 125 * @param key The key of the table entry 126 * @param value The value of the table entry 127 */ putUnsafely(int key, Object value)128 public void putUnsafely(int key, Object value) { 129 Integer intKey = Integer.valueOf(key); 130 int length = this.keyTable.length, 131 index = intKey.hashCode() % length; 132 while (this.keyTable[index] != null) { 133 if (++index == length) { 134 index = 0; 135 } 136 } 137 this.keyTable[index] = intKey; 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(int key)146 public Object removeKey(int key) { 147 Integer intKey = Integer.valueOf(key); 148 int length = this.keyTable.length, 149 index = intKey.hashCode() % length; 150 Integer currentKey; 151 while ((currentKey = this.keyTable[index]) != null) { 152 if (currentKey.equals(intKey)) { 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 HashtableOfInteger newHashtable = new HashtableOfInteger(this.elementSize * 2); // double the number of expected elements 170 Integer 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 += this.keyTable[i] + " -> " + object.toString() + "\n"; //$NON-NLS-2$ //$NON-NLS-1$ 191 return s; 192 } 193 } 194