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  */
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 final static 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      */
IntHashTable()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      */
IntHashTable(int capacity)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      */
hash(Object key)77     public 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 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      */
lookup(Object key, int hash)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     }
104 
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      */
lookup(Object key)112     public int lookup(Object key) {
113         return lookup(key, hash(key));
114     }
115 
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      */
getFromIndex(int index)123     public int getFromIndex(int index) {
124         Object node = objs[index];
125         return node == null || node == DELETED ? -1 : ints[index];
126     }
127 
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      */
putAtIndex(Object key, int value, int index)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     }
154 
remove(Object key)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     }
163 
164     /**
165      * Expand the hash table when it exceeds the load factor.
166      *
167      * Rehash the existing objects.
168      */
rehash()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     }
188 
189     /**
190      * Removes all mappings from this map.
191      */
clear()192     public void clear() {
193         for (int i = objs.length; --i >= 0;) {
194             objs[i] = null;
195         }
196         num_bindings = 0;
197     }
198 }
199