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 jdk.internal.jimage; 27 28 import java.lang.reflect.Array; 29 import java.util.ArrayList; 30 import java.util.Arrays; 31 import java.util.LinkedHashMap; 32 import java.util.List; 33 import java.util.Map; 34 35 public class PerfectHashBuilder<E> { 36 private final static int RETRY_LIMIT = 1000; 37 38 private Class<?> entryComponent; 39 private Class<?> bucketComponent; 40 41 private final Map<UTF8String, Entry<E>> map = new LinkedHashMap<>(); 42 private int[] redirect; 43 private Entry<E>[] order; 44 private int count = 0; 45 46 @SuppressWarnings("EqualsAndHashcode") 47 public static class Entry<E> { 48 private final UTF8String key; 49 private final E value; 50 51 Entry() { 52 this("", null); 53 } 54 55 Entry(String key, E value) { 56 this(new UTF8String(key), value); 57 } 58 59 Entry(UTF8String key, E value) { 60 this.key = key; 61 this.value = value; 62 } 63 64 UTF8String getKey() { 65 return key; 66 } 67 68 E getValue() { 69 return value; 70 } 71 72 int hashCode(int seed) { 73 return key.hashCode(seed); 74 } 75 76 @Override 77 public int hashCode() { 78 return key.hashCode(); 79 } 80 } 81 82 static class Bucket<E> implements Comparable<Bucket<E>> { 83 final List<Entry<E>> list = new ArrayList<>(); 84 85 void add(Entry<E> entry) { 86 list.add(entry); 87 } 88 89 int getSize() { 90 return list.size(); 91 } 92 93 List<Entry<E>> getList() { 94 return list; 95 } 96 97 Entry<E> getFirst() { 98 assert !list.isEmpty() : "bucket should never be empty"; 99 return list.get(0); 100 } 101 102 @Override 103 public int hashCode() { 104 return getFirst().hashCode(); 105 } 106 107 @Override 108 @SuppressWarnings("EqualsWhichDoesntCheckParameterClass") 109 public boolean equals(Object obj) { 110 return this == obj; 111 } 112 113 @Override 114 public int compareTo(Bucket<E> o) { 115 return o.getSize() - getSize(); 116 } 117 } 118 119 public PerfectHashBuilder(Class<?> entryComponent, Class<?> bucketComponent) { 120 this.entryComponent = entryComponent; 121 this.bucketComponent = bucketComponent; 122 } 123 124 public int getCount() { 125 return map.size(); 126 } 127 128 public int[] getRedirect() { 129 return redirect; 130 } 131 132 public Entry<E>[] getOrder() { 133 return order; 134 } 135 136 public Entry<E> put(String key, E value) { 137 return put(new UTF8String(key), value); 138 } 139 140 public Entry<E> put(UTF8String key, E value) { 141 return put(new Entry<>(key, value)); 142 } 143 144 public Entry<E> put(Entry<E> entry) { 145 Entry<E> old = map.put(entry.key, entry); 146 147 if (old == null) { 148 count++; 149 } 150 151 return old; 152 } 153 154 @SuppressWarnings("unchecked") 155 public void generate() { 156 boolean redo = count != 0; 157 while (redo) { 158 redo = false; 159 redirect = new int[count]; 160 order = (Entry<E>[])Array.newInstance(entryComponent, count); 161 162 Bucket<E>[] sorted = createBuckets(); 163 int free = 0; 164 165 for (Bucket<E> bucket : sorted) { 166 if (bucket.getSize() != 1) { 167 if (!collidedEntries(bucket, count)) { 168 redo = true; 169 break; 170 } 171 } else { 172 for ( ; free < count && order[free] != null; free++) {} 173 174 if (free >= count) { 175 redo = true; 176 break; 177 } 178 179 order[free] = bucket.getFirst(); 180 redirect[bucket.hashCode() % count] = -1 - free; 181 free++; 182 } 183 } 184 185 if (redo) { 186 count = (count + 1) | 1; 187 } 188 } 189 } 190 191 @SuppressWarnings("unchecked") 192 private Bucket<E>[] createBuckets() { 193 Bucket<E>[] buckets = (Bucket<E>[])Array.newInstance(bucketComponent, count); 194 195 map.values().stream().forEach((entry) -> { 196 int index = entry.hashCode() % count; 197 Bucket<E> bucket = buckets[index]; 198 199 if (bucket == null) { 200 buckets[index] = bucket = new Bucket<>(); 201 } 202 203 bucket.add(entry); 204 }); 205 206 Bucket<E>[] sorted = Arrays.asList(buckets).stream() 207 .filter((bucket) -> (bucket != null)) 208 .sorted() 209 .toArray((length) -> { 210 return (Bucket<E>[])Array.newInstance(bucketComponent, length); 211 }); 212 213 return sorted; 214 } 215 216 private boolean collidedEntries(Bucket<E> bucket, int count) { 217 List<Integer> undo = new ArrayList<>(); 218 int seed = UTF8String.HASH_MULTIPLIER + 1; 219 int retry = 0; 220 221 redo: 222 while (true) { 223 for (Entry<E> entry : bucket.getList()) { 224 int index = entry.hashCode(seed) % count; 225 if (order[index] != null) { 226 if (++retry > RETRY_LIMIT) { 227 return false; 228 } 229 230 undo.stream().forEach((i) -> { 231 order[i] = null; 232 }); 233 234 undo.clear(); 235 seed++; 236 237 if (seed == 0) { 238 seed = 1; 239 } 240 241 continue redo; 242 } 243 244 order[index] = entry; 245 undo.add(index); 246 } 247 248 redirect[bucket.hashCode() % count] = seed; 249 250 break; 251 } 252 253 return true; 254 } 255 }