JDK 11 jdk.jlink.jmod - JLink Tool

JDK 11 jdk.jlink.jmod is the JMOD file for JDK 11 JLink tool, which can be invoked by the "jlink" command.

JDK 11 JLink tool compiled class files are stored in \fyicenter\jdk-11.0.1\jmods\jdk.jlink.jmod.

JDK 11 JLink tool compiled class files are also linked and stored in the \fyicenter\jdk-11.0.1\lib\modules JImage file.

JDK 11 JLink tool source code files are stored in \fyicenter\jdk-11.0.1\lib\src.zip\jdk.jlink.

You can click and view the content of each source code file in the list below.

✍: FYIcenter

jdk/tools/jlink/internal/PerfectHashBuilder.java

/*
 * Copyright (c) 2014, Oracle and/or its affiliates. All rights reserved.
 * ORACLE PROPRIETARY/CONFIDENTIAL. Use is subject to license terms.
 *
 *
 *
 *
 *
 *
 *
 *
 *
 *
 *
 *
 *
 *
 *
 *
 *
 *
 *
 *
 */

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 algoritm;
 *
 *   - 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. Meed 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().stream().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.stream().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;
    }
 }

jdk/tools/jlink/internal/PerfectHashBuilder.java

 

JDK 11 jdk.jshell.jmod - JShell Tool

JDK 11 jdk.jfr.jmod - JFR Module

Download and Use JDK 11

⇑⇑ FAQ for JDK (Java Development Kit)

2018-11-09, 2683👍, 0💬