-
-
Notifications
You must be signed in to change notification settings - Fork 44
/
LongHashMap.java
145 lines (124 loc) · 3.29 KB
/
LongHashMap.java
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
/**
* This file is LGPL licensed.
* "Borrowed" from CraftBukkit.
*/
package me.nallar.patched.collection;
import java.util.Arrays;
import me.nallar.patched.annotation.FakeExtend;
@SuppressWarnings ("unchecked")
@FakeExtend
public abstract class LongHashMap extends net.minecraft.util.LongHashMap {
private static final long EMPTY_KEY = Long.MIN_VALUE;
private static final int BUCKET_SIZE = 4096;
private long[][] keys;
private Object[][] values;
private int size;
public LongHashMap() {
initialize();
}
@Override
public int getNumHashElements() {
return size;
}
@Override
public boolean containsItem(long key) {
return getValueByKey(key) != null;
}
@Override
public Object getValueByKey(long key) {
int index = (int) (keyIndex(key) & (BUCKET_SIZE - 1));
long[] inner = keys[index];
if (inner == null) {
return null;
}
for (int i = 0; i < inner.length; i++) {
long innerKey = inner[i];
if (innerKey == EMPTY_KEY) {
return null;
} else if (innerKey == key) {
Object[] value = values[index];
if (value != null) {
return value[i];
}
}
}
return null;
}
@Override
public synchronized void add(long key, Object value) {
int index = (int) (keyIndex(key) & (BUCKET_SIZE - 1));
long[] innerKeys = keys[index];
Object[] innerValues = values[index];
if (innerKeys == null) {
// need to make a new chain
keys[index] = innerKeys = new long[8];
Arrays.fill(innerKeys, EMPTY_KEY);
values[index] = innerValues = new Object[8];
innerKeys[0] = key;
innerValues[0] = value;
size++;
} else {
int i;
for (i = 0; i < innerKeys.length; i++) {
// found an empty spot in the chain to put this
long currentKey = innerKeys[i];
if (currentKey == EMPTY_KEY) {
size++;
}
if (currentKey == EMPTY_KEY || currentKey == key) {
innerKeys[i] = key;
innerValues[i] = value;
return;
}
}
// chain is full, resize it and add our new entry
keys[index] = innerKeys = Arrays.copyOf(innerKeys, i << 1);
Arrays.fill(innerKeys, i, innerKeys.length, EMPTY_KEY);
values[index] = innerValues = Arrays.copyOf(innerValues, i << 1);
innerKeys[i] = key;
innerValues[i] = value;
size++;
}
}
@Override
public synchronized Object remove(long key) {
int index = (int) (keyIndex(key) & (BUCKET_SIZE - 1));
long[] inner = keys[index];
if (inner == null) {
return null;
}
for (int i = 0; i < inner.length; i++) {
// hit the end of the chain, didn't find this entry
if (inner[i] == EMPTY_KEY) {
break;
}
if (inner[i] == key) {
Object value = values[index][i];
for (i++; i < inner.length; i++) {
if (inner[i] == EMPTY_KEY) {
break;
}
inner[i - 1] = inner[i];
values[index][i - 1] = values[index][i];
}
inner[i - 1] = EMPTY_KEY;
values[index][i - 1] = null;
size--;
return value;
}
}
return null;
}
private void initialize() {
keys = new long[BUCKET_SIZE][];
values = new Object[BUCKET_SIZE][];
}
private static long keyIndex(long key) {
key ^= key >>> 33;
key *= 0xff51afd7ed558ccdL;
key ^= key >>> 33;
key *= 0xc4ceb9fe1a85ec53L;
key ^= key >>> 33;
return key;
}
}