Mercurial > jdk8-mips64-public > langtools / file revision
src/share/classes/com/sun/tools/javac/util/IntHashTable.java@d4051d4f5daf
src/share/classes/com/sun/tools/javac/util/IntHashTable.java
Wed, 10 Jun 2015 14:22:04 -0700
- author
- mfang
- date
- Wed, 10 Jun 2015 14:22:04 -0700
- changeset 2815
- d4051d4f5daf
- parent 0
- 959103a6100f
- permissions
- -rw-r--r--
8083601: jdk8u60 l10n resource file translation update 2
Reviewed-by: ksrini, yhuang
1 /*
2 * Copyright (c) 2014, Oracle and/or its affiliates. All rights reserved.
3 * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER.
4 *
5 * This code is free software; you can redistribute it and/or modify it
6 * under the terms of the GNU General Public License version 2 only, as
7 * published by the Free Software Foundation. Oracle designates this
8 * particular file as subject to the "Classpath" exception as provided
9 * by Oracle in the LICENSE file that accompanied this code.
10 *
11 * This code is distributed in the hope that it will be useful, but WITHOUT
12 * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
13 * FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License
14 * version 2 for more details (a copy is included in the LICENSE file that
15 * accompanied this code).
16 *
17 * You should have received a copy of the GNU General Public License version
18 * 2 along with this work; if not, write to the Free Software Foundation,
19 * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA.
20 *
21 * Please contact Oracle, 500 Oracle Parkway, Redwood Shores, CA 94065 USA
22 * or visit www.oracle.com if you need additional information or have any
23 * questions.
24 */
26 package com.sun.tools.javac.util;
28 /**
29 * A hash table that maps Object to int.
30 *
31 * This is a custom hash table optimised for the Object -> int
32 * maps. This is done to avoid unnecessary object allocation in the image set.
33 *
34 * @author Charles Turner
35 * @author Per Bothner
36 */
37 public class IntHashTable {
38 private static final int DEFAULT_INITIAL_SIZE = 64;
39 protected Object[] objs; // the domain set
40 protected int[] ints; // the image set
41 protected int mask; // used to clip int's into the domain
42 protected int num_bindings; // the number of mappings (including DELETED)
43 private final static Object DELETED = new Object();
45 /**
46 * Construct an Object -> int hash table.
47 *
48 * The default size of the hash table is 64 mappings.
49 */
50 public IntHashTable() {
51 objs = new Object[DEFAULT_INITIAL_SIZE];
52 ints = new int[DEFAULT_INITIAL_SIZE];
53 mask = DEFAULT_INITIAL_SIZE - 1;
54 }
56 /**
57 * Construct an Object -> int hash table with a specified amount of mappings.
58 * @param capacity The number of default mappings in this hash table.
59 */
60 public IntHashTable(int capacity) {
61 int log2Size = 4;
62 while (capacity > (1 << log2Size)) {
63 log2Size++;
64 }
65 capacity = 1 << log2Size;
66 objs = new Object[capacity];
67 ints = new int[capacity];
68 mask = capacity - 1;
69 }
71 /**
72 * Compute the hash code of a given object.
73 *
74 * @param key The object whose hash code is to be computed.
75 * @return zero if the object is null, otherwise the identityHashCode
76 */
77 public int hash(Object key) {
78 return System.identityHashCode(key);
79 }
81 /**
82 * Find either the index of a key's value, or the index of an available space.
83 *
84 * @param key The key to whose value you want to find.
85 * @param hash The hash code of this key.
86 * @return Either the index of the key's value, or an index pointing to
87 * unoccupied space.
88 */
89 public int lookup(Object key, int hash) {
90 Object node;
91 int hash1 = hash ^ (hash >>> 15);
92 int hash2 = (hash ^ (hash << 6)) | 1; //ensure coprimeness
93 int deleted = -1;
94 for (int i = hash1 & mask;; i = (i + hash2) & mask) {
95 node = objs[i];
96 if (node == key)
97 return i;
98 if (node == null)
99 return deleted >= 0 ? deleted : i;
100 if (node == DELETED && deleted < 0)
101 deleted = i;
102 }
103 }
105 /**
106 * Lookup a given key's value in the hash table.
107 *
108 * @param key The key whose value you want to find.
109 * @return Either the index of the key's value, or an index pointing to
110 * unoccupied space.
111 */
112 public int lookup(Object key) {
113 return lookup(key, hash(key));
114 }
116 /**
117 * Return the value stored at the specified index in the table.
118 *
119 * @param index The index to inspect, as returned from {@link #lookup}
120 * @return A non-negative integer if the index contains a non-null
121 * value, or -1 if it does.
122 */
123 public int getFromIndex(int index) {
124 Object node = objs[index];
125 return node == null || node == DELETED ? -1 : ints[index];
126 }
128 /**
129 * Associates the specified key with the specified value in this map.
130 *
131 * @param key key with which the specified value is to be associated.
132 * @param value value to be associated with the specified key.
133 * @param index the index at which to place this binding, as returned
134 * from {@link #lookup}.
135 * @return previous value associated with specified key, or -1 if there was
136 * no mapping for key.
137 */
138 public int putAtIndex(Object key, int value, int index) {
139 Object old = objs[index];
140 if (old == null || old == DELETED) {
141 objs[index] = key;
142 ints[index] = value;
143 if (old != DELETED)
144 num_bindings++;
145 if (3 * num_bindings >= 2 * objs.length)
146 rehash();
147 return -1;
148 } else { // update existing mapping
149 int oldValue = ints[index];
150 ints[index] = value;
151 return oldValue;
152 }
153 }
155 public int remove(Object key) {
156 int index = lookup(key);
157 Object old = objs[index];
158 if (old == null || old == DELETED)
159 return -1;
160 objs[index] = DELETED;
161 return ints[index];
162 }
164 /**
165 * Expand the hash table when it exceeds the load factor.
166 *
167 * Rehash the existing objects.
168 */
169 protected void rehash() {
170 Object[] oldObjsTable = objs;
171 int[] oldIntsTable = ints;
172 int oldCapacity = oldObjsTable.length;
173 int newCapacity = oldCapacity << 1;
174 Object[] newObjTable = new Object[newCapacity];
175 int[] newIntTable = new int[newCapacity];
176 int newMask = newCapacity - 1;
177 objs = newObjTable;
178 ints = newIntTable;
179 mask = newMask;
180 num_bindings = 0; // this is recomputed below
181 Object key;
182 for (int i = oldIntsTable.length; --i >= 0;) {
183 key = oldObjsTable[i];
184 if (key != null && key != DELETED)
185 putAtIndex(key, oldIntsTable[i], lookup(key, hash(key)));
186 }
187 }
189 /**
190 * Removes all mappings from this map.
191 */
192 public void clear() {
193 for (int i = objs.length; --i >= 0;) {
194 objs[i] = null;
195 }
196 num_bindings = 0;
197 }
198 }
