• file
• revisions
• annotate
• diff
• comparison
• raw

src/share/classes/com/sun/tools/javac/util/IntHashTable.java@8a30511b2ea4 (annotated)

src/share/classes/com/sun/tools/javac/util/IntHashTable.java

Thu, 04 Aug 2016 23:36:47 -0700

author

asaha

date

Thu, 04 Aug 2016 23:36:47 -0700

changeset 3270

8a30511b2ea4

parent 0

959103a6100f

permissions

-rw-r--r--

8162511: 8u111 L10n resource file updates
Summary: 8u111 L10n resource file updates
Reviewed-by: coffeys
Contributed-by: li.jiang@oracle.com

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