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 jdk.vm.ci.meta.JavaKind;
34 import org.graalvm.compiler.lir.gen.ArithmeticLIRGenerator;
35
36 import jdk.vm.ci.meta.JavaConstant;
37 import jdk.vm.ci.meta.Value;
38
39 /**
40 * This class holds a hash function at a specific cardinality and min value (lowest key). The
41 * cardinality is the required size of the hash table to make the hasher injective for the provided
42 * keys.
43 */
44 public final class Hasher {
45
46 /**
47 * Tries to find a hash function without conflicts for the provided keys.
48 *
49 * @param keys the keys
50 * @param minDensity the minimum density of the switch table. Used to determine the maximum
51 * cardinality of the hash function
52 * @return an optional hasher
53 */
54 public static Optional<Hasher> forKeys(JavaConstant[] keys, double minDensity) {
55 assert checkKeyKind(keys);
56 if (keys.length <= 2) {
57 return Optional.empty();
58 } else {
59 int maxCardinality = (int) Math.round(keys.length / minDensity);
60 assert checkIfSorted(keys);
61 TreeSet<Hasher> candidates = new TreeSet<>(new Comparator<Hasher>() {
62 @Override
63 public int compare(Hasher o1, Hasher o2) {
64 int d = o1.cardinality - o2.cardinality;
65 if (d != 0) {
66 return d;
67 } else {
68 return o1.effort() - o2.effort();
69 }
70 }
71 });
72 int min = keys[0].asInt();
73 for (HashFunction f : HashFunction.instances()) {
74 for (int cardinality = keys.length; cardinality < maxCardinality; cardinality++) {
75 if (isValid(keys, min, f, cardinality)) {
76 candidates.add(new Hasher(f, cardinality, min));
77 break;
78 }
79 }
80 }
81 if (candidates.isEmpty()) {
82 return Optional.empty();
83 } else {
84 return Optional.of(candidates.first());
85 }
86 }
87 }
88
89 private static boolean checkKeyKind(JavaConstant[] keys) {
90 for (int i = 0; i < keys.length; i++) {
91 if (keys[i].getJavaKind() != JavaKind.Int) {
92 throw new AssertionError(String.format("Key at index %d is not an int: %s", i, keys[i]));
93 }
94 }
95 return true;
96 }
97
98 private static boolean checkIfSorted(JavaConstant[] keys) {
99 for (int i = 1; i < keys.length; i++) {
100 if (keys[i - 1].asInt() >= keys[i].asInt()) {
101 throw new AssertionError("Keys array is not sorted");
102 }
103 }
104 return true;
105 }
106
107 private static boolean isValid(JavaConstant[] keys, int min, HashFunction function, int cardinality) {
108 Set<Integer> seen = new HashSet<>(keys.length);
109 for (JavaConstant key : keys) {
110 int hash = function.apply(key.asInt(), min) & (cardinality - 1);
111 if (!seen.add(hash)) {
112 return false;
113 }
114 }
115 return true;
116 }
117
118 private final HashFunction function;
119 private final int cardinality;
120 private final int min;
121
122 private Hasher(HashFunction function, int cardinality, int min) {
123 this.function = function;
124 this.cardinality = cardinality;
125 this.min = min;
126 }
127
128 /**
129 * Applies the hash function.
130 *
131 * @param value the value to be hashed
132 * @return the hash value
133 */
134 public int hash(int value) {
135 return function.apply(value, min) & (cardinality - 1);
136 }
137
138 /**
139 * Applies the hash function to a lir value.
140 *
141 * @param value the value to be hashed
142 * @param gen the lir generator
143 * @return the hashed lir value
144 */
145 public Value hash(Value value, ArithmeticLIRGenerator gen) {
146 Value h = function.gen(value, gen.getLIRGen().emitJavaConstant(JavaConstant.forInt(min)), gen);
147 return gen.emitAnd(h, gen.getLIRGen().emitJavaConstant(JavaConstant.forInt(cardinality - 1)));
148 }
149
150 /**
151 * @return the hashing effort
152 */
153 public int effort() {
154 return function.effort() + 1;
155 }
156
157 /**
158 * @return the cardinality of the hash function that should match the size of the table switch.
159 */
160 public int cardinality() {
161 return cardinality;
162 }
163
164 /**
165 * @return the hash function
166 */
167 public HashFunction function() {
168 return function;
169 }
170
171 @Override
172 public String toString() {
173 return "Hasher[function=" + function + ", effort=" + effort() + ", cardinality=" + cardinality + "]";
174 }
175 }