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