1 /*
2 * Copyright (c) 2018, 2019, 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.
8 *
9 * This code is distributed in the hope that it will be useful, but WITHOUT
10 * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
11 * FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License
12 * version 2 for more details (a copy is included in the LICENSE file that
13 * accompanied this code).
14 *
15 * You should have received a copy of the GNU General Public License version
16 * 2 along with this work; if not, write to the Free Software Foundation,
17 * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA.
18 *
19 * Please contact Oracle, 500 Oracle Parkway, Redwood Shores, CA 94065 USA
20 * or visit www.oracle.com if you need additional information or have any
21 * questions.
22 */
23
24
25 package org.graalvm.compiler.lir.hashing;
26
27 import java.util.Comparator;
28 import java.util.HashSet;
29 import java.util.Optional;
30 import java.util.Set;
31 import java.util.TreeSet;
32
33 import org.graalvm.compiler.lir.gen.ArithmeticLIRGenerator;
34
35 import jdk.vm.ci.meta.JavaConstant;
36 import jdk.vm.ci.meta.Value;
37
38 /**
39 * This class holds a hash function at a specific cardinality and min value (lowest key). The
40 * cardinality is the required size of the hash table to make the hasher injective for the provided
41 * keys.
42 */
43 public final class Hasher {
44
45 /**
46 * Tries to find a hash function without conflicts for the provided keys.
47 *
48 * @param keys the keys
49 * @param minDensity the minimum density of the switch table. Used to determine the maximum
50 * cardinality of the hash function
51 * @return an optional hasher
52 */
53 public static Optional<Hasher> forKeys(JavaConstant[] keys, double minDensity) {
54 if (keys.length <= 2) {
55 return Optional.empty();
56 } else {
57 int maxCardinality = (int) Math.round(keys.length / minDensity);
58 assertSorted(keys);
59 TreeSet<Hasher> candidates = new TreeSet<>(new Comparator<Hasher>() {
60 @Override
61 public int compare(Hasher o1, Hasher o2) {
62 int d = o1.cardinality - o2.cardinality;
63 if (d != 0) {
64 return d;
65 } else {
66 return o1.effort() - o2.effort();
67 }
68 }
69 });
70 long min = keys[0].asLong();
71 for (HashFunction f : HashFunction.instances()) {
72 for (int cardinality = keys.length; cardinality < maxCardinality; cardinality++) {
73 if (isValid(keys, min, f, cardinality)) {
74 candidates.add(new Hasher(f, cardinality, min));
75 break;
76 }
77 }
78 }
79 if (candidates.isEmpty()) {
80 return Optional.empty();
81 } else {
82 return Optional.of(candidates.first());
83 }
84 }
85 }
86
87 private static void assertSorted(JavaConstant[] keys) {
88 for (int i = 1; i < keys.length; i++) {
89 assert keys[i - 1].asLong() < keys[i].asLong();
90 }
91 }
92
93 private static boolean isValid(JavaConstant[] keys, long min, HashFunction function, int cardinality) {
94 Set<Integer> seen = new HashSet<>(keys.length);
95 for (JavaConstant key : keys) {
96 int hash = function.apply(key.asLong(), min) & (cardinality - 1);
97 if (!seen.add(hash)) {
98 return false;
99 }
100 }
101 return true;
102 }
103
104 private final HashFunction function;
105 private final int cardinality;
106 private final long min;
107
108 private Hasher(HashFunction function, int cardinality, long min) {
109 this.function = function;
110 this.cardinality = cardinality;
111 this.min = min;
112 }
113
114 /**
115 * Applies the hash function.
116 *
117 * @param value the value to be hashed
118 * @return the hash value
119 */
120 public int hash(long value) {
121 return function.apply(value, min) & (cardinality - 1);
122 }
123
124 /**
125 * Applies the hash function to a lir value.
126 *
127 * @param value the value to be hashed
128 * @param gen the lir generator
129 * @return the hashed lir value
130 */
131 public Value hash(Value value, ArithmeticLIRGenerator gen) {
132 Value h = function.gen(value, gen.getLIRGen().emitJavaConstant(JavaConstant.forLong(min)), gen);
133 return gen.emitAnd(h, gen.getLIRGen().emitJavaConstant(JavaConstant.forInt(cardinality - 1)));
134 }
135
136 /**
137 * @return the hashing effort
138 */
139 public int effort() {
140 return function.effort() + 1;
141 }
142
143 /**
144 * @return the cardinality of the hash function that should match the size of the table switch.
145 */
146 public int cardinality() {
147 return cardinality;
148 }
149
150 /**
151 * @return the hash function
152 */
153 public HashFunction function() {
154 return function;
155 }
156
157 @Override
158 public String toString() {
159 return "Hasher[function=" + function + ", effort=" + effort() + ", cardinality=" + cardinality + "]";
160 }
161 }