| /* | |
| * Copyright (c) 2014, 2023, Oracle and/or its affiliates. All rights reserved. | |
| * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER. | |
| * | |
| * This code is free software; you can redistribute it and/or modify it | |
| * under the terms of the GNU General Public License version 2 only, as | |
| * published by the Free Software Foundation. Oracle designates this | |
| * particular file as subject to the "Classpath" exception as provided | |
| * by Oracle in the LICENSE file that accompanied this code. | |
| * | |
| * This code is distributed in the hope that it will be useful, but WITHOUT | |
| * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or | |
| * FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License | |
| * version 2 for more details (a copy is included in the LICENSE file that | |
| * accompanied this code). | |
| * | |
| * You should have received a copy of the GNU General Public License version | |
| * 2 along with this work; if not, write to the Free Software Foundation, | |
| * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA. | |
| * | |
| * Please contact Oracle, 500 Oracle Parkway, Redwood Shores, CA 94065 USA | |
| * or visit www.oracle.com if you need additional information or have any | |
| * questions. | |
| */ | |
| package jdk.tools.jlink.internal; | |
| import java.lang.reflect.Array; | |
| import java.util.ArrayList; | |
| import java.util.Arrays; | |
| import java.util.LinkedHashMap; | |
| import java.util.List; | |
| import java.util.Map; | |
| import jdk.internal.jimage.ImageStringsReader; | |
| /* | |
| * The algorithm used here is outlined in Applications of Finite Automata | |
| * Representing Large Vocabularies - Claudio L Lucchesi and Tomasz Kowaltowski, | |
| * 1992, and A Practical Minimal Perfect Hashing Method - Fabiano C. Botelho1, | |
| * Yoshiharu Kohayakawa, and Nivio Ziviani, 2005. | |
| * | |
| * The primary JDK use of this algorithm is managing the jimage location index. | |
| * | |
| * The goal of PerfectHashBuilder is to construct an automaton which maps a | |
| * string key to a unique index 0..N-1, where N is the number of key-value pairs. | |
| * What makes MPHM effective is that the size of the lookup table is N or very | |
| * near N, and the minimum lookup is O(1) maximum lookup is O(2). | |
| * | |
| * The result of PerfectHashBuilder is two integer arrays, redirect and order. | |
| * The redirect table provides a 1-1 mapping to the order table, using the | |
| * reader algorithm described further on. The order table provides a mapping | |
| * to entries. If entries are fixed size and can be put in a direct table, then | |
| * the order table can be used to construct the direct table and then discarded. | |
| * | |
| * The steps for constructing the lookup tables are as follows; | |
| * | |
| * - Compute an MPHM hash for each key, based on a fixed base value modulo N. | |
| * Note, the hash is based on the modified UTF-8 of the key, simplifying | |
| * computation in native code. | |
| * | |
| * - Combine keys that map to the same hash code (collisions) into bucket | |
| * chains. | |
| * | |
| * - Sort bucket chains by length of chains, longest first (most collisions.) | |
| * Sorting is done to pack the redirect table with the worst collision | |
| * offenders first. | |
| * | |
| * - For each chain, recompute the hash of each key using a new base value. | |
| * Recomputation should give a different key distribution. A tally is kept | |
| * of where the key maps, using the order table. The tally is used to detect | |
| * new collisions. If there are further collisions, then restart | |
| * redistribution using a different hash base value. If a chain is | |
| * successfully distributed, then the base value used to compute the hash | |
| * is recorded in the redirect table. | |
| * | |
| * - Once all colliding chains are resolved (length > 1), then the chains with | |
| * only one entry are used to fill in the empty slots in the order table. | |
| * These keys are recorded in the redirect table using the twos complement | |
| * of the order index. | |
| * | |
| * - It is possible that a given set of keys cannot be packed into a table of | |
| * size N. If this situation occurs then the size of the table is | |
| * adjusted so that keys distribute differently. | |
| * | |
| * Readers algorithm; | |
| * | |
| * - Compute the hash for the key using the fixed base value modulo N. This | |
| * will provide an index into the redirect table. The integer value in the | |
| * redirect table will determine the next step. | |
| * | |
| * - If the value in the redirect table is positive, then that value is used | |
| * to rehash the key to get the index into the order table. | |
| * | |
| * - If the value in the redirect table is negative, then that value is the | |
| * twos complement of the index into the order table. | |
| * | |
| * - If the value in the redirect table is zero, then there is no matching | |
| * entry. | |
| * | |
| * - Note that the resulting entry needs to be validated to ensure a match. | |
| * This is typically done by comparing the key with the key in entry. | |
| */ | |
| public class PerfectHashBuilder<E> { | |
| private static final int RETRY_LIMIT = 1000; | |
| private Class<?> entryComponent; | |
| private Class<?> bucketComponent; | |
| private final Map<String, Entry<E>> map = new LinkedHashMap<>(); | |
| private int[] redirect; | |
| private Entry<E>[] order; | |
| private int count = 0; | |
| @SuppressWarnings("EqualsAndHashcode") | |
| public static class Entry<E> { | |
| private final String key; | |
| private final E value; | |
| Entry() { | |
| this("", null); | |
| } | |
| Entry(String key, E value) { | |
| this.key = key; | |
| this.value = value; | |
| } | |
| String getKey() { | |
| return key; | |
| } | |
| E getValue() { | |
| return value; | |
| } | |
| int hashCode(int seed) { | |
| return ImageStringsReader.hashCode(key, seed); | |
| } | |
| @Override | |
| public int hashCode() { | |
| return ImageStringsReader.hashCode(key); | |
| } | |
| @Override | |
| public boolean equals(Object other) { | |
| if (other == this) { | |
| return true; | |
| } | |
| if (!(other instanceof Entry)) { | |
| return false; | |
| } | |
| Entry<?> entry = (Entry<?>) other; | |
| return entry.key.equals(key); | |
| } | |
| } | |
| static class Bucket<E> implements Comparable<Bucket<E>> { | |
| final List<Entry<E>> list = new ArrayList<>(); | |
| void add(Entry<E> entry) { | |
| list.add(entry); | |
| } | |
| int getSize() { | |
| return list.size(); | |
| } | |
| List<Entry<E>> getList() { | |
| return list; | |
| } | |
| Entry<E> getFirst() { | |
| assert !list.isEmpty() : "bucket should never be empty"; | |
| return list.get(0); | |
| } | |
| @Override | |
| public int hashCode() { | |
| return getFirst().hashCode(); | |
| } | |
| @Override | |
| @SuppressWarnings("EqualsWhichDoesntCheckParameterClass") | |
| public boolean equals(Object obj) { | |
| return this == obj; | |
| } | |
| @Override | |
| public int compareTo(Bucket<E> o) { | |
| return o.getSize() - getSize(); | |
| } | |
| } | |
| public PerfectHashBuilder(Class<?> entryComponent, Class<?> bucketComponent) { | |
| this.entryComponent = entryComponent; | |
| this.bucketComponent = bucketComponent; | |
| } | |
| public int getCount() { | |
| return map.size(); | |
| } | |
| public int[] getRedirect() { | |
| return redirect.clone(); | |
| } | |
| public Entry<E>[] getOrder() { | |
| return order.clone(); | |
| } | |
| public Entry<E> put(String key, E value) { | |
| return put(new Entry<>(key, value)); | |
| } | |
| public Entry<E> put(Entry<E> entry) { | |
| Entry<E> old = map.put(entry.key, entry); | |
| if (old == null) { | |
| count++; | |
| } | |
| return old; | |
| } | |
| @SuppressWarnings("unchecked") | |
| public void generate() { | |
| // If the table is empty then exit early. | |
| boolean redo = count != 0; | |
| // Repeat until a valid packing is achieved. | |
| while (redo) { | |
| redo = false; | |
| // Allocate the resulting redirect and order tables. | |
| redirect = new int[count]; | |
| order = (Entry<E>[])Array.newInstance(entryComponent, count); | |
| // Place all the entries in bucket chains based on hash. Sort by | |
| // length of chain. | |
| Bucket<E>[] sorted = createBuckets(); | |
| int free = 0; | |
| // Iterate through the chains, longest first. | |
| for (Bucket<E> bucket : sorted) { | |
| if (bucket.getSize() != 1) { | |
| // Attempt to pack entries until no collisions occur. | |
| if (!collidedEntries(bucket, count)) { | |
| // Failed to pack. Need to grow table. | |
| redo = true; | |
| break; | |
| } | |
| } else { | |
| // A no collision entry (bucket.getSize() == 1). Find a free | |
| // spot in the order table. | |
| for ( ; free < count && order[free] != null; free++) {} | |
| // If none found, then grow table. | |
| if (free >= count) { | |
| redo = true; | |
| break; | |
| } | |
| // Store entry in order table. | |
| order[free] = bucket.getFirst(); | |
| // Twos complement of order index stired in the redirect table. | |
| redirect[(bucket.hashCode() & 0x7FFFFFFF) % count] = -1 - free; | |
| // Update free slot index. | |
| free++; | |
| } | |
| } | |
| // If packing failed, then bump table size. Make odd to increase | |
| // chances of being relatively prime. | |
| if (redo) { | |
| count = (count + 1) | 1; | |
| } | |
| } | |
| } | |
| @SuppressWarnings("unchecked") | |
| private Bucket<E>[] createBuckets() { | |
| // Build bucket chains based on key hash. Collisions end up in same chain. | |
| Bucket<E>[] buckets = (Bucket<E>[])Array.newInstance(bucketComponent, count); | |
| map.values().forEach((entry) -> { | |
| int index = (entry.hashCode() & 0x7FFFFFFF) % count; | |
| Bucket<E> bucket = buckets[index]; | |
| if (bucket == null) { | |
| buckets[index] = bucket = new Bucket<>(); | |
| } | |
| bucket.add(entry); | |
| }); | |
| // Sort chains, longest first. | |
| Bucket<E>[] sorted = Arrays.asList(buckets).stream() | |
| .filter((bucket) -> (bucket != null)) | |
| .sorted() | |
| .toArray((length) -> { | |
| return (Bucket<E>[])Array.newInstance(bucketComponent, length); | |
| }); | |
| return sorted; | |
| } | |
| private boolean collidedEntries(Bucket<E> bucket, int count) { | |
| // Track packing attempts. | |
| List<Integer> undo = new ArrayList<>(); | |
| // Start with a new hash seed. | |
| int seed = ImageStringsReader.HASH_MULTIPLIER + 1; | |
| int retry = 0; | |
| // Attempt to pack all the entries in a single chain. | |
| redo: | |
| while (true) { | |
| for (Entry<E> entry : bucket.getList()) { | |
| // Compute new hash. | |
| int index = entry.hashCode(seed) % count; | |
| // If a collision is detected. | |
| if (order[index] != null) { | |
| // Only retry so many times with current table size. | |
| if (++retry > RETRY_LIMIT) { | |
| return false; | |
| } | |
| // Undo the attempted packing. | |
| undo.forEach((i) -> { | |
| order[i] = null; | |
| }); | |
| // Reset the undo list and bump up the hash seed. | |
| undo.clear(); | |
| seed++; | |
| // Zero seed is not valid. | |
| if (seed == 0) { | |
| seed = 1; | |
| } | |
| // Try again. | |
| continue redo; | |
| } | |
| // No collision. | |
| order[index] = entry; | |
| undo.add(index); | |
| } | |
| // Entire chain packed. Record hash seed used. | |
| redirect[(bucket.hashCode() & 0x7FFFFFFF) % count] = seed; | |
| break; | |
| } | |
| return true; | |
| } | |
| } |