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