1 /*
  2  * Copyright (c) 2014, 2021, 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  */
 25 
 26 package com.sun.tools.javac.util;
 27 
 28 /**
 29  * A hash table that maps Object to int.
 30  *
 31  * This is a custom hash table optimised for the Object {@literal ->} 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 static final Object DELETED = new Object();
 44 
 45     /**
 46      * Construct an Object {@literal ->} 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     }
 55 
 56     /**
 57      * Construct an Object {@literal ->} 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     }
 70 
 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     protected int hash(Object key) {
 78         return System.identityHashCode(key);
 79     }
 80 
 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 index you want to find.
 85      * @return Either the index of the key's value, or an index pointing to
 86      * unoccupied space.
 87      */
 88     protected int lookup(Object key) {
 89         Object node;
 90         int hash = hash(key);
 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     }
104 
105     /**
106      * Return the value to which the specified key is mapped.
107      *
108      * @param key The key to whose value you want to find.
109      * @return A non-negative integer if the value is found.
110      *         Otherwise, it is -1.
111      */
112     public int get(Object key) {
113         int index = lookup(key);
114         Object node = objs[index];
115         return node == null || node == DELETED ? -1 : ints[index];
116     }
117 
118     /**
119      * Associates the specified key with the specified value in this map.
120      *
121      * @param key key with which the specified value is to be associated.
122      * @param value value to be associated with the specified key.
123      * @return previous value associated with specified key, or -1 if there was
124      * no mapping for key.
125      */
126     public int put(Object key, int value) {
127         int index = lookup(key);
128         Object old = objs[index];
129         if (old == null || old == DELETED) {
130             objs[index] = key;
131             ints[index] = value;
132             if (old != DELETED)
133                 num_bindings++;
134             if (3 * num_bindings >= 2 * objs.length)
135                 rehash();
136             return -1;
137         } else { // update existing mapping
138             int oldValue = ints[index];
139             ints[index] = value;
140             return oldValue;
141         }
142     }
143 
144     /**
145      * Remove the mapping(key and value) of the specified key.
146      *
147      * @param key the key to whose value you want to remove.
148      * @return the removed value associated with the specified key,
149      *         or -1 if there was no mapping for the specified key.
150      */
151     public int remove(Object key) {
152         int index = lookup(key);
153         Object old = objs[index];
154         if (old == null || old == DELETED)
155             return -1;
156         objs[index] = DELETED;
157         return ints[index];
158     }
159 
160     /**
161      * Expand the hash table when it exceeds the load factor.
162      *
163      * Rehash the existing objects.
164      */
165     protected void rehash() {
166         Object[] oldObjsTable = objs;
167         int[] oldIntsTable = ints;
168         int newCapacity = oldObjsTable.length << 1;
169         objs = new Object[newCapacity];
170         ints = new int[newCapacity];
171         mask = newCapacity - 1;
172         num_bindings = 0; // this is recomputed below
173         Object key;
174         for (int i = oldIntsTable.length; --i >= 0;) {
175             key = oldObjsTable[i];
176             if (key != null && key != DELETED)
177                 put(key, oldIntsTable[i]);
178         }
179     }
180 
181     /**
182      * Removes all mappings from this map.
183      */
184     public void clear() {
185         for (int i = objs.length; --i >= 0;) {
186             objs[i] = null;
187         }
188         num_bindings = 0;
189     }
190 }