1 /*
2 * Copyright (C) 2019 The Guava Authors
3 *
4 * Licensed under the Apache License, Version 2.0 (the "License");
5 * you may not use this file except in compliance with the License.
6 * You may obtain a copy of the License at
7 *
8 * http://www.apache.org/licenses/LICENSE-2.0
9 *
10 * Unless required by applicable law or agreed to in writing, software
11 * distributed under the License is distributed on an "AS IS" BASIS,
12 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
13 * See the License for the specific language governing permissions and
14 * limitations under the License.
15 */
16
17 package com.google.common.collect;
18
19 import com.google.common.annotations.GwtIncompatible;
20 import com.google.common.base.Objects;
21 import com.google.common.primitives.Ints;
22 import java.util.Arrays;
23 import org.checkerframework.checker.nullness.qual.Nullable;
24
25 /**
26 * Helper classes and static methods for implementing compact hash-based collections.
27 *
28 * @author Jon Noack
29 */
30 @GwtIncompatible
31 final class CompactHashing {
32 private CompactHashing() {}
33
34 /** Indicates blank table entries. */
35 static final byte UNSET = 0;
36
37 /** Number of bits used to store the numbers of hash table bits (max 30). */
38 private static final int HASH_TABLE_BITS_MAX_BITS = 5;
39
40 /** Use high bits of metadata for modification count. */
41 static final int MODIFICATION_COUNT_INCREMENT = (1 << HASH_TABLE_BITS_MAX_BITS);
42
43 /** Bitmask that selects the low bits of metadata to get hashTableBits. */
44 static final int HASH_TABLE_BITS_MASK = (1 << HASH_TABLE_BITS_MAX_BITS) - 1;
45
46 /** Maximum size of a compact hash-based collection (2^30 - 1 because 0 is UNSET). */
47 static final int MAX_SIZE = Ints.MAX_POWER_OF_TWO - 1;
48
49 /** Default size of a compact hash-based collection. */
50 static final int DEFAULT_SIZE = 3;
51
52 /**
53 * Minimum size of the hash table of a compact hash-based collection. Because small hash tables
54 * use a byte[], any smaller size uses the same amount of memory due to object padding.
55 */
56 private static final int MIN_HASH_TABLE_SIZE = 4;
57
58 private static final int BYTE_MAX_SIZE = 1 << Byte.SIZE; // 2^8 = 256
59 private static final int BYTE_MASK = (1 << Byte.SIZE) - 1; // 2^8 - 1 = 255
60
61 private static final int SHORT_MAX_SIZE = 1 << Short.SIZE; // 2^16 = 65_536
62 private static final int SHORT_MASK = (1 << Short.SIZE) - 1; // 2^16 - 1 = 65_535
63
64 /**
65 * Returns the power of 2 hashtable size required to hold the expected number of items or the
66 * minimum hashtable size, whichever is greater.
67 */
68 static int tableSize(int expectedSize) {
69 // We use entries next == 0 to indicate UNSET, so actual capacity is 1 less than requested.
70 return Math.max(MIN_HASH_TABLE_SIZE, Hashing.closedTableSize(expectedSize + 1, 1.0f));
71 }
72
73 /** Creates and returns a properly-sized array with the given number of buckets. */
74 static Object createTable(int buckets) {
75 if (buckets < 2
76 || buckets > Ints.MAX_POWER_OF_TWO
77 || Integer.highestOneBit(buckets) != buckets) {
78 throw new IllegalArgumentException("must be power of 2 between 2^1 and 2^30: " + buckets);
79 }
80 if (buckets <= BYTE_MAX_SIZE) {
81 return new byte[buckets];
82 } else if (buckets <= SHORT_MAX_SIZE) {
83 return new short[buckets];
84 } else {
85 return new int[buckets];
86 }
87 }
88
89 static void tableClear(Object table) {
90 if (table instanceof byte[]) {
91 Arrays.fill((byte[]) table, (byte) 0);
92 } else if (table instanceof short[]) {
93 Arrays.fill((short[]) table, (short) 0);
94 } else {
95 Arrays.fill((int[]) table, 0);
96 }
97 }
98
99 static int tableGet(Object table, int index) {
100 if (table instanceof byte[]) {
101 return ((byte[]) table)[index] & BYTE_MASK; // unsigned read
102 } else if (table instanceof short[]) {
103 return ((short[]) table)[index] & SHORT_MASK; // unsigned read
104 } else {
105 return ((int[]) table)[index];
106 }
107 }
108
109 static void tableSet(Object table, int index, int entry) {
110 if (table instanceof byte[]) {
111 ((byte[]) table)[index] = (byte) entry; // unsigned write
112 } else if (table instanceof short[]) {
113 ((short[]) table)[index] = (short) entry; // unsigned write
114 } else {
115 ((int[]) table)[index] = entry;
116 }
117 }
118
119 /**
120 * Returns a larger power of 2 hashtable size given the current mask.
121 *
122 * <p>For hashtable sizes less than or equal to 32, the returned power of 2 is 4x the current
123 * hashtable size to reduce expensive rehashing. Otherwise the returned power of 2 is 2x the
124 * current hashtable size.
125 */
126 static int newCapacity(int mask) {
127 return ((mask < 32) ? 4 : 2) * (mask + 1);
128 }
129
130 /** Returns the hash prefix given the current mask. */
131 static int getHashPrefix(int value, int mask) {
132 return value & ~mask;
133 }
134
135 /** Returns the index, or 0 if the entry is "null". */
136 static int getNext(int entry, int mask) {
137 return entry & mask;
138 }
139
140 /** Returns a new value combining the prefix and suffix using the given mask. */
141 static int maskCombine(int prefix, int suffix, int mask) {
142 return (prefix & ~mask) | (suffix & mask);
143 }
144
145 static int remove(
146 @Nullable Object key,
147 @Nullable Object value,
148 int mask,
149 Object table,
150 int[] entries,
151 Object[] keys,
152 Object @Nullable [] values) {
153 int hash = Hashing.smearedHash(key);
154 int tableIndex = hash & mask;
155 int next = tableGet(table, tableIndex);
156 if (next == UNSET) {
157 return -1;
158 }
159 int hashPrefix = getHashPrefix(hash, mask);
160 int lastEntryIndex = -1;
161 do {
162 int entryIndex = next - 1;
163 int entry = entries[entryIndex];
164 if (getHashPrefix(entry, mask) == hashPrefix
165 && Objects.equal(key, keys[entryIndex])
166 && (values == null || Objects.equal(value, values[entryIndex]))) {
167 int newNext = getNext(entry, mask);
168 if (lastEntryIndex == -1) {
169 // we need to update the root link from table[]
170 tableSet(table, tableIndex, newNext);
171 } else {
172 // we need to update the link from the chain
173 entries[lastEntryIndex] = maskCombine(entries[lastEntryIndex], newNext, mask);
174 }
175
176 return entryIndex;
177 }
178 lastEntryIndex = entryIndex;
179 next = getNext(entry, mask);
180 } while (next != UNSET);
181 return -1;
182 }
183 }