Mercurial > hg > jdk9-shenandoah > jdk
view src/java.base/share/classes/jdk/internal/jimage/PerfectHashBuilder.java @ 12745:f068a4ffddd2
8136583: Core libraries should use blessed modifier order
Summary: Run blessed-modifier-order script (see bug)
Reviewed-by: psandoz, chegar, alanb, plevart
author | martin |
---|---|
date | Tue, 15 Sep 2015 21:56:04 -0700 |
parents | 7dac2fc3d705 |
children |
line wrap: on
line source
/* * Copyright (c) 2014, 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.internal.jimage; 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; public class PerfectHashBuilder<E> { private static final int RETRY_LIMIT = 1000; private Class<?> entryComponent; private Class<?> bucketComponent; private final Map<UTF8String, 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 UTF8String key; private final E value; Entry() { this("", null); } Entry(String key, E value) { this(new UTF8String(key), value); } Entry(UTF8String key, E value) { this.key = key; this.value = value; } UTF8String getKey() { return key; } E getValue() { return value; } int hashCode(int seed) { return key.hashCode(seed); } @Override public int hashCode() { return key.hashCode(); } } 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; } public Entry<E>[] getOrder() { return order; } public Entry<E> put(String key, E value) { return put(new UTF8String(key), value); } public Entry<E> put(UTF8String 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() { boolean redo = count != 0; while (redo) { redo = false; redirect = new int[count]; order = (Entry<E>[])Array.newInstance(entryComponent, count); Bucket<E>[] sorted = createBuckets(); int free = 0; for (Bucket<E> bucket : sorted) { if (bucket.getSize() != 1) { if (!collidedEntries(bucket, count)) { redo = true; break; } } else { for ( ; free < count && order[free] != null; free++) {} if (free >= count) { redo = true; break; } order[free] = bucket.getFirst(); redirect[bucket.hashCode() % count] = -1 - free; free++; } } if (redo) { count = (count + 1) | 1; } } } @SuppressWarnings("unchecked") private Bucket<E>[] createBuckets() { Bucket<E>[] buckets = (Bucket<E>[])Array.newInstance(bucketComponent, count); map.values().stream().forEach((entry) -> { int index = entry.hashCode() % count; Bucket<E> bucket = buckets[index]; if (bucket == null) { buckets[index] = bucket = new Bucket<>(); } bucket.add(entry); }); 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) { List<Integer> undo = new ArrayList<>(); int seed = UTF8String.HASH_MULTIPLIER + 1; int retry = 0; redo: while (true) { for (Entry<E> entry : bucket.getList()) { int index = entry.hashCode(seed) % count; if (order[index] != null) { if (++retry > RETRY_LIMIT) { return false; } undo.stream().forEach((i) -> { order[i] = null; }); undo.clear(); seed++; if (seed == 0) { seed = 1; } continue redo; } order[index] = entry; undo.add(index); } redirect[bucket.hashCode() % count] = seed; break; } return true; } }