| /* |
| * Copyright (c) 2014, Oracle and/or its affiliates. All rights reserved. |
| * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER. |
| * |
| * This code is free software; you can redistribute it and/or modify it |
| * under the terms of the GNU General Public License version 2 only, as |
| * published by the Free Software Foundation. Oracle designates this |
| * particular file as subject to the "Classpath" exception as provided |
| * by Oracle in the LICENSE file that accompanied this code. |
| * |
| * This code is distributed in the hope that it will be useful, but WITHOUT |
| * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or |
| * FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License |
| * version 2 for more details (a copy is included in the LICENSE file that |
| * accompanied this code). |
| * |
| * You should have received a copy of the GNU General Public License version |
| * 2 along with this work; if not, write to the Free Software Foundation, |
| * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA. |
| * |
| * Please contact Oracle, 500 Oracle Parkway, Redwood Shores, CA 94065 USA |
| * or visit www.oracle.com if you need additional information or have any |
| * questions. |
| */ |
| |
| package com.sun.tools.javac.util; |
| |
| /** |
| * A hash table that maps Object to int. |
| * |
| * This is a custom hash table optimised for the Object -> int |
| * maps. This is done to avoid unnecessary object allocation in the image set. |
| * |
| * @author Charles Turner |
| * @author Per Bothner |
| */ |
| public class IntHashTable { |
| private static final int DEFAULT_INITIAL_SIZE = 64; |
| protected Object[] objs; // the domain set |
| protected int[] ints; // the image set |
| protected int mask; // used to clip int's into the domain |
| protected int num_bindings; // the number of mappings (including DELETED) |
| private final static Object DELETED = new Object(); |
| |
| /** |
| * Construct an Object -> int hash table. |
| * |
| * The default size of the hash table is 64 mappings. |
| */ |
| public IntHashTable() { |
| objs = new Object[DEFAULT_INITIAL_SIZE]; |
| ints = new int[DEFAULT_INITIAL_SIZE]; |
| mask = DEFAULT_INITIAL_SIZE - 1; |
| } |
| |
| /** |
| * Construct an Object -> int hash table with a specified amount of mappings. |
| * @param capacity The number of default mappings in this hash table. |
| */ |
| public IntHashTable(int capacity) { |
| int log2Size = 4; |
| while (capacity > (1 << log2Size)) { |
| log2Size++; |
| } |
| capacity = 1 << log2Size; |
| objs = new Object[capacity]; |
| ints = new int[capacity]; |
| mask = capacity - 1; |
| } |
| |
| /** |
| * Compute the hash code of a given object. |
| * |
| * @param key The object whose hash code is to be computed. |
| * @return zero if the object is null, otherwise the identityHashCode |
| */ |
| public int hash(Object key) { |
| return System.identityHashCode(key); |
| } |
| |
| /** |
| * Find either the index of a key's value, or the index of an available space. |
| * |
| * @param key The key to whose value you want to find. |
| * @param hash The hash code of this key. |
| * @return Either the index of the key's value, or an index pointing to |
| * unoccupied space. |
| */ |
| public int lookup(Object key, int hash) { |
| Object node; |
| int hash1 = hash ^ (hash >>> 15); |
| int hash2 = (hash ^ (hash << 6)) | 1; //ensure coprimeness |
| int deleted = -1; |
| for (int i = hash1 & mask;; i = (i + hash2) & mask) { |
| node = objs[i]; |
| if (node == key) |
| return i; |
| if (node == null) |
| return deleted >= 0 ? deleted : i; |
| if (node == DELETED && deleted < 0) |
| deleted = i; |
| } |
| } |
| |
| /** |
| * Lookup a given key's value in the hash table. |
| * |
| * @param key The key whose value you want to find. |
| * @return Either the index of the key's value, or an index pointing to |
| * unoccupied space. |
| */ |
| public int lookup(Object key) { |
| return lookup(key, hash(key)); |
| } |
| |
| /** |
| * Return the value stored at the specified index in the table. |
| * |
| * @param index The index to inspect, as returned from {@link #lookup} |
| * @return A non-negative integer if the index contains a non-null |
| * value, or -1 if it does. |
| */ |
| public int getFromIndex(int index) { |
| Object node = objs[index]; |
| return node == null || node == DELETED ? -1 : ints[index]; |
| } |
| |
| /** |
| * Associates the specified key with the specified value in this map. |
| * |
| * @param key key with which the specified value is to be associated. |
| * @param value value to be associated with the specified key. |
| * @param index the index at which to place this binding, as returned |
| * from {@link #lookup}. |
| * @return previous value associated with specified key, or -1 if there was |
| * no mapping for key. |
| */ |
| public int putAtIndex(Object key, int value, int index) { |
| Object old = objs[index]; |
| if (old == null || old == DELETED) { |
| objs[index] = key; |
| ints[index] = value; |
| if (old != DELETED) |
| num_bindings++; |
| if (3 * num_bindings >= 2 * objs.length) |
| rehash(); |
| return -1; |
| } else { // update existing mapping |
| int oldValue = ints[index]; |
| ints[index] = value; |
| return oldValue; |
| } |
| } |
| |
| public int remove(Object key) { |
| int index = lookup(key); |
| Object old = objs[index]; |
| if (old == null || old == DELETED) |
| return -1; |
| objs[index] = DELETED; |
| return ints[index]; |
| } |
| |
| /** |
| * Expand the hash table when it exceeds the load factor. |
| * |
| * Rehash the existing objects. |
| */ |
| protected void rehash() { |
| Object[] oldObjsTable = objs; |
| int[] oldIntsTable = ints; |
| int oldCapacity = oldObjsTable.length; |
| int newCapacity = oldCapacity << 1; |
| Object[] newObjTable = new Object[newCapacity]; |
| int[] newIntTable = new int[newCapacity]; |
| int newMask = newCapacity - 1; |
| objs = newObjTable; |
| ints = newIntTable; |
| mask = newMask; |
| num_bindings = 0; // this is recomputed below |
| Object key; |
| for (int i = oldIntsTable.length; --i >= 0;) { |
| key = oldObjsTable[i]; |
| if (key != null && key != DELETED) |
| putAtIndex(key, oldIntsTable[i], lookup(key, hash(key))); |
| } |
| } |
| |
| /** |
| * Removes all mappings from this map. |
| */ |
| public void clear() { |
| for (int i = objs.length; --i >= 0;) { |
| objs[i] = null; |
| } |
| num_bindings = 0; |
| } |
| } |