-
Notifications
You must be signed in to change notification settings - Fork 2.3k
/
LongArrayHashTable.java
168 lines (150 loc) · 5.43 KB
/
LongArrayHashTable.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
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
/*
* Copyright (c) 2002-2018 "Neo4j,"
* Neo4j Sweden AB [http://neo4j.com]
*
* This file is part of Neo4j.
*
* Neo4j is free software: you can redistribute it and/or modify
* it under the terms of the GNU General Public License as published by
* the Free Software Foundation, either version 3 of the License, or
* (at your option) any later version.
*
* This program is distributed in the hope that it will be useful,
* but WITHOUT ANY WARRANTY; without even the implied warranty of
* MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
* GNU General Public License for more details.
*
* You should have received a copy of the GNU General Public License
* along with this program. If not, see <http://www.gnu.org/licenses/>.
*/
package org.neo4j.cypher.internal.runtime;
import org.neo4j.helpers.collection.Pair;
import static org.neo4j.cypher.internal.runtime.LongArrayHash.CONTINUE_PROBING;
import static org.neo4j.cypher.internal.runtime.LongArrayHash.NOT_IN_USE;
import static org.neo4j.cypher.internal.runtime.LongArrayHash.SLOT_EMPTY;
import static org.neo4j.cypher.internal.runtime.LongArrayHash.VALUE_FOUND;
/**
* This hash table is used as a backing store for the keys of set, map and multi-map where the keys are arrays of longs.
*/
class LongArrayHashTable
{
public final long[] keys;
public final int width;
public final int capacity;
private int numberOfEntries;
private int resizeLimit;
private static final double LOAD_FACTOR = 0.75;
int tableMask;
LongArrayHashTable( int capacity, int width )
{
resizeLimit = (int) (capacity * LOAD_FACTOR);
tableMask = Integer.highestOneBit( capacity ) - 1;
keys = new long[capacity * width];
this.width = width;
java.util.Arrays.fill( keys, NOT_IN_USE );
this.capacity = capacity;
}
/**
* Signals whether it's time to size up or not. The actual resizing is done slightly differently depending on if this is a map or set. Maps have, in
* addition to a hash table also a separate array for the values.
*
* @return true if the number of keys in the hash table has reached capacity.
*/
boolean timeToResize()
{
return numberOfEntries >= resizeLimit;
}
/***
* Checks whether a slot in the table contains a given key.
* @param slot Slot to check
* @param key Key to check
* @return Can return:
* SLOT_EMPTY - This slot is free. In other words - the key is not in the table
* CONTINUE_PROBING - This slot is taken by a different key
* VALUE_FOUND - The key is in the table at this slot
*/
int checkSlot( int slot, long[] key )
{
assert LongArrayHash.validValue( key, width );
int startOffset = slot * width;
if ( keys[startOffset] == NOT_IN_USE )
{
return SLOT_EMPTY;
}
for ( int i = 0; i < width; i++ )
{
if ( keys[startOffset + i] != key[i] )
{
return CONTINUE_PROBING;
}
}
return VALUE_FOUND;
}
/**
* Writes the key to this slot.
*
* @param slot The slot to write to.
* @param key Le key.
*/
void claimSlot( int slot, long[] key )
{
int offset = slot * width;
assert keys[offset] == NOT_IN_USE : "Tried overwriting an already used slot";
System.arraycopy( key, 0, keys, offset, width );
numberOfEntries++;
}
public boolean isEmpty()
{
return numberOfEntries == 0;
}
/**
* Finds an slot not already claimed, starting from a given slot.
*
* @return First unused slot after fromSlot
*/
private int findUnusedSlot( int fromSlot )
{
while ( true )
{
if ( keys[fromSlot * width] == NOT_IN_USE )
{
return fromSlot;
}
fromSlot = (fromSlot + 1) & tableMask;
}
}
LongArrayHashTable doubleCapacity()
{
LongArrayHashTable toTable = new LongArrayHashTable( capacity * 2, width );
toTable.numberOfEntries = numberOfEntries;
for ( int fromOffset = 0; fromOffset < capacity * width; fromOffset = fromOffset + width )
{
if ( keys[fromOffset] != NOT_IN_USE )
{
int toSlot = LongArrayHash.hashCode( keys, fromOffset, width ) & toTable.tableMask;
toSlot = toTable.findUnusedSlot( toSlot );
System.arraycopy( keys, fromOffset, toTable.keys, toSlot * width, width );
}
}
return toTable;
}
Pair<LongArrayHashTable,Object[]> doubleCapacity( Object[] fromValues )
{
LongArrayHashTable toTable = new LongArrayHashTable( capacity * 2, width );
Object[] toValues = new Object[capacity * 2];
long[] fromKeys = keys;
toTable.numberOfEntries = numberOfEntries;
for ( int fromSlot = 0; fromSlot < capacity; fromSlot = fromSlot + 1 )
{
int fromOffset = fromSlot * width;
if ( fromKeys[fromOffset] != NOT_IN_USE )
{
int toSlot = LongArrayHash.hashCode( fromKeys, fromOffset, width ) & toTable.tableMask;
toSlot = toTable.findUnusedSlot( toSlot );
System.arraycopy( fromKeys, fromOffset, toTable.keys, toSlot * width, width );
toValues[toSlot] = fromValues[fromSlot];
}
}
return Pair.of( toTable, toValues );
}
}