IntHashTable.java revision 2981:d1e5707cd4eb
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 26package 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 */ 37public 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 */ 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 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 */ 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 */ 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 */ 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 */ 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 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 */ 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 */ 192 public void clear() { 193 for (int i = objs.length; --i >= 0;) { 194 objs[i] = null; 195 } 196 num_bindings = 0; 197 } 198} 199