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 for non-zero int keys.
18 */
19
20 public final class HashtableOfInt {
21 // to avoid using Enumerations, walk the individual tables skipping nulls
22 public int[] keyTable;
23 public Object[] valueTable;
24
25 public int elementSize; // number of elements in the table
26 int threshold;
HashtableOfInt()27 public HashtableOfInt() {
28 this(13);
29 }
HashtableOfInt(int size)30 public HashtableOfInt(int size) {
31 this.elementSize = 0;
32 this.threshold = size; // size represents the expected number of elements
33 int extraRoom = (int) (size * 1.75f);
34 if (this.threshold == extraRoom)
35 extraRoom++;
36 this.keyTable = new int[extraRoom];
37 this.valueTable = new Object[extraRoom];
38 }
containsKey(int key)39 public boolean containsKey(int key) {
40 int length = this.keyTable.length, index = key % length;
41 int currentKey;
42 while ((currentKey = this.keyTable[index]) != 0) {
43 if (currentKey == key)
44 return true;
45 if (++index == length) {
46 index = 0;
47 }
48 }
49 return false;
50 }
get(int key)51 public Object get(int key) {
52 int length = this.keyTable.length, index = key % length;
53 int currentKey;
54 while ((currentKey = this.keyTable[index]) != 0) {
55 if (currentKey == key) return this.valueTable[index];
56 if (++index == length) {
57 index = 0;
58 }
59 }
60 return null;
61 }
put(int key, Object value)62 public Object put(int key, Object value) {
63 int length = this.keyTable.length, index = key % length;
64 int currentKey;
65 while ((currentKey = this.keyTable[index]) != 0) {
66 if (currentKey == key) return this.valueTable[index] = value;
67 if (++index == length) {
68 index = 0;
69 }
70 }
71 this.keyTable[index] = key;
72 this.valueTable[index] = value;
73
74 // assumes the threshold is never equal to the size of the table
75 if (++this.elementSize > this.threshold)
76 rehash();
77 return value;
78 }
rehash()79 private void rehash() {
80 HashtableOfInt newHashtable = new HashtableOfInt(this.elementSize * 2); // double the number of expected elements
81 int currentKey;
82 for (int i = this.keyTable.length; --i >= 0;)
83 if ((currentKey = this.keyTable[i]) != 0)
84 newHashtable.put(currentKey, this.valueTable[i]);
85
86 this.keyTable = newHashtable.keyTable;
87 this.valueTable = newHashtable.valueTable;
88 this.threshold = newHashtable.threshold;
89 }
size()90 public int size() {
91 return this.elementSize;
92 }
93 @Override
toString()94 public String toString() {
95 String s = ""; //$NON-NLS-1$
96 Object object;
97 for (int i = 0, length = this.valueTable.length; i < length; i++)
98 if ((object = this.valueTable[i]) != null)
99 s += this.keyTable[i] + " -> " + object.toString() + "\n"; //$NON-NLS-2$ //$NON-NLS-1$
100 return s;
101 }
102 }
103