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 * Hashtable of {Object --> int } 18 */ 19 public final class HashtableOfObjectToInt implements Cloneable { 20 21 // to avoid using Enumerations, walk the individual tables skipping nulls 22 public Object[] keyTable; 23 public int[] valueTable; 24 25 public int elementSize; // number of elements in the table 26 int threshold; 27 HashtableOfObjectToInt()28 public HashtableOfObjectToInt() { 29 this(13); 30 } 31 HashtableOfObjectToInt(int size)32 public HashtableOfObjectToInt(int size) { 33 34 this.elementSize = 0; 35 this.threshold = size; // size represents the expected number of elements 36 int extraRoom = (int) (size * 1.75f); 37 if (this.threshold == extraRoom) 38 extraRoom++; 39 this.keyTable = new Object[extraRoom]; 40 this.valueTable = new int[extraRoom]; 41 } 42 43 @Override clone()44 public Object clone() throws CloneNotSupportedException { 45 HashtableOfObjectToInt result = (HashtableOfObjectToInt) 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 int[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 index = (key.hashCode()& 0x7FFFFFFF) % length; 62 Object currentKey; 63 while ((currentKey = this.keyTable[index]) != null) { 64 if (currentKey.equals(key)) 65 return true; 66 if (++index == length) { 67 index = 0; 68 } 69 } 70 return false; 71 } 72 get(Object key)73 public int get(Object key) { 74 int length = this.keyTable.length, 75 index = (key.hashCode()& 0x7FFFFFFF) % length; 76 Object currentKey; 77 while ((currentKey = this.keyTable[index]) != null) { 78 if (currentKey.equals(key)) 79 return this.valueTable[index]; 80 if (++index == length) { 81 index = 0; 82 } 83 } 84 return -1; 85 } 86 keysToArray(Object[] array)87 public void keysToArray(Object[] array) { 88 int index = 0; 89 for (int i=0, length=this.keyTable.length; i<length; i++) { 90 if (this.keyTable[i] != null) 91 array[index++] = this.keyTable[i]; 92 } 93 } 94 put(Object key, int value)95 public int put(Object key, int value) { 96 int length = this.keyTable.length, 97 index = (key.hashCode()& 0x7FFFFFFF) % length; 98 Object currentKey; 99 while ((currentKey = this.keyTable[index]) != null) { 100 if (currentKey.equals(key)) 101 return this.valueTable[index] = value; 102 if (++index == length) { 103 index = 0; 104 } 105 } 106 this.keyTable[index] = key; 107 this.valueTable[index] = value; 108 109 // assumes the threshold is never equal to the size of the table 110 if (++this.elementSize > this.threshold) 111 rehash(); 112 return value; 113 } 114 removeKey(Object key)115 public int removeKey(Object key) { 116 int length = this.keyTable.length, 117 index = (key.hashCode()& 0x7FFFFFFF) % length; 118 Object currentKey; 119 while ((currentKey = this.keyTable[index]) != null) { 120 if (currentKey.equals(key)) { 121 int value = this.valueTable[index]; 122 this.elementSize--; 123 this.keyTable[index] = null; 124 rehash(); 125 return value; 126 } 127 if (++index == length) { 128 index = 0; 129 } 130 } 131 return -1; 132 } 133 rehash()134 private void rehash() { 135 136 HashtableOfObjectToInt newHashtable = new HashtableOfObjectToInt(this.elementSize * 2); // double the number of expected elements 137 Object currentKey; 138 for (int i = this.keyTable.length; --i >= 0;) 139 if ((currentKey = this.keyTable[i]) != null) 140 newHashtable.put(currentKey, this.valueTable[i]); 141 142 this.keyTable = newHashtable.keyTable; 143 this.valueTable = newHashtable.valueTable; 144 this.threshold = newHashtable.threshold; 145 } 146 size()147 public int size() { 148 return this.elementSize; 149 } 150 151 @Override toString()152 public String toString() { 153 String s = ""; //$NON-NLS-1$ 154 Object key; 155 for (int i = 0, length = this.keyTable.length; i < length; i++) 156 if ((key = this.keyTable[i]) != null) 157 s += key + " -> " + this.valueTable[i] + "\n"; //$NON-NLS-2$ //$NON-NLS-1$ 158 return s; 159 } 160 } 161