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 }