1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
|
package gregtech.api.objects;
import java.util.Arrays;
/**
* Object-2-object map based on IntIntMap4a
*/
public class ObjMap<K, V> {
private static final Object FREE_KEY = new Object();
private static final Object REMOVED_KEY = new Object();
/** Keys and values */
private Object[] m_data;
/** Value for the null key (if inserted into a map) */
private Object m_nullValue;
private boolean m_hasNull;
/** Fill factor, must be between (0 and 1) */
private final float m_fillFactor;
/** We will resize a map once it reaches this size */
private int m_threshold;
/** Current map size */
private int m_size;
/** Mask to calculate the original position */
private int m_mask;
/** Mask to wrap the actual array pointer */
private int m_mask2;
public ObjMap(final int size, final float fillFactor) {
if (fillFactor <= 0 || fillFactor >= 1) throw new IllegalArgumentException("FillFactor must be in (0, 1)");
if (size <= 0) throw new IllegalArgumentException("Size must be positive!");
final int capacity = arraySize(size, fillFactor);
m_mask = capacity - 1;
m_mask2 = capacity * 2 - 1;
m_fillFactor = fillFactor;
m_data = new Object[capacity * 2];
Arrays.fill(m_data, FREE_KEY);
m_threshold = (int) (capacity * fillFactor);
}
@SuppressWarnings("unchecked")
public V get(final K key) {
if (key == null) return (V) m_nullValue; // we null it on remove, so safe not to check a flag here
int ptr = (key.hashCode() & m_mask) << 1;
Object k = m_data[ptr];
if (k == FREE_KEY) return null; // end of chain already
if (k.equals(key)) // we check FREE and REMOVED prior to this call
return (V) m_data[ptr + 1];
while (true) {
ptr = (ptr + 2) & m_mask2; // that's next index
k = m_data[ptr];
if (k == FREE_KEY) return null;
if (k.equals(key)) return (V) m_data[ptr + 1];
}
}
@SuppressWarnings("unchecked")
public V put(final K key, final V value) {
if (key == null) return insertNullKey(value);
int ptr = getStartIndex(key) << 1;
Object k = m_data[ptr];
if (k == FREE_KEY) // end of chain already
{
m_data[ptr] = key;
m_data[ptr + 1] = value;
if (m_size >= m_threshold) rehash(m_data.length * 2); // size is set inside
else ++m_size;
return null;
} else if (k.equals(key)) // we check FREE and REMOVED prior to this call
{
final Object ret = m_data[ptr + 1];
m_data[ptr + 1] = value;
return (V) ret;
}
int firstRemoved = -1;
if (k == REMOVED_KEY) firstRemoved = ptr; // we may find a key later
while (true) {
ptr = (ptr + 2) & m_mask2; // that's next index calculation
k = m_data[ptr];
if (k == FREE_KEY) {
if (firstRemoved != -1) ptr = firstRemoved;
m_data[ptr] = key;
m_data[ptr + 1] = value;
if (m_size >= m_threshold) rehash(m_data.length * 2); // size is set inside
else ++m_size;
return null;
} else if (k.equals(key)) {
final Object ret = m_data[ptr + 1];
m_data[ptr + 1] = value;
return (V) ret;
} else if (k == REMOVED_KEY) {
if (firstRemoved == -1) firstRemoved = ptr;
}
}
}
@SuppressWarnings("unchecked")
public V remove(final K key) {
if (key == null) return removeNullKey();
int ptr = getStartIndex(key) << 1;
Object k = m_data[ptr];
if (k == FREE_KEY) return null; // end of chain already
else if (k.equals(key)) // we check FREE and REMOVED prior to this call
{
--m_size;
if (m_data[(ptr + 2) & m_mask2] == FREE_KEY) m_data[ptr] = FREE_KEY;
else m_data[ptr] = REMOVED_KEY;
final V ret = (V) m_data[ptr + 1];
m_data[ptr + 1] = null;
return ret;
}
while (true) {
ptr = (ptr + 2) & m_mask2; // that's next index calculation
k = m_data[ptr];
if (k == FREE_KEY) return null;
else if (k.equals(key)) {
--m_size;
if (m_data[(ptr + 2) & m_mask2] == FREE_KEY) m_data[ptr] = FREE_KEY;
else m_data[ptr] = REMOVED_KEY;
final V ret = (V) m_data[ptr + 1];
m_data[ptr + 1] = null;
return ret;
}
}
}
@SuppressWarnings("unchecked")
private V insertNullKey(final V value) {
if (m_hasNull) {
final Object ret = m_nullValue;
m_nullValue = value;
return (V) ret;
} else {
m_nullValue = value;
++m_size;
return null;
}
}
@SuppressWarnings("unchecked")
private V removeNullKey() {
if (m_hasNull) {
final Object ret = m_nullValue;
m_nullValue = null;
m_hasNull = false;
--m_size;
return (V) ret;
} else {
return null;
}
}
public int size() {
return m_size;
}
@SuppressWarnings("unchecked")
private void rehash(final int newCapacity) {
m_threshold = (int) (newCapacity / 2 * m_fillFactor);
m_mask = newCapacity / 2 - 1;
m_mask2 = newCapacity - 1;
final int oldCapacity = m_data.length;
final Object[] oldData = m_data;
m_data = new Object[newCapacity];
Arrays.fill(m_data, FREE_KEY);
m_size = m_hasNull ? 1 : 0;
for (int i = 0; i < oldCapacity; i += 2) {
final Object oldKey = oldData[i];
if (oldKey != FREE_KEY && oldKey != REMOVED_KEY) put((K) oldKey, (V) oldData[i + 1]);
}
}
public int getStartIndex(final Object key) {
// key is not null here
return key.hashCode() & m_mask;
}
/** Taken from FastUtil implementation */
/** Return the least power of two greater than or equal to the specified value.
*
* <p>Note that this function will return 1 when the argument is 0.
*
* @param x a long integer smaller than or equal to 2<sup>62</sup>.
* @return the least power of two greater than or equal to the specified value.
*/
public static long nextPowerOfTwo(long x) {
if (x == 0) return 1;
x--;
x |= x >> 1;
x |= x >> 2;
x |= x >> 4;
x |= x >> 8;
x |= x >> 16;
return (x | x >> 32) + 1;
}
/** Returns the least power of two smaller than or equal to 2<sup>30</sup> and larger than or equal to <code>Math.ceil( expected / f )</code>.
*
* @param expected the expected number of elements in a hash table.
* @param f the load factor.
* @return the minimum possible size for a backing array.
* @throws IllegalArgumentException if the necessary size is larger than 2<sup>30</sup>.
*/
public static int arraySize(final int expected, final float f) {
final long s = Math.max(2, nextPowerOfTwo((long) Math.ceil(expected / f)));
if (s > (1 << 30))
throw new IllegalArgumentException(
"Too large (" + expected + " expected elements with load factor " + f + ")");
return (int) s;
}
// taken from FastUtil
private static final int INT_PHI = 0x9E3779B9;
public static int phiMix(final int x) {
final int h = x * INT_PHI;
return h ^ (h >> 16);
}
}
|
