-
Notifications
You must be signed in to change notification settings - Fork 2.3k
/
TreeNode.java
372 lines (309 loc) · 13.7 KB
/
TreeNode.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
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
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
360
361
362
363
364
365
366
367
368
369
370
371
372
/*
* Copyright (c) 2002-2018 "Neo Technology,"
* Network Engine for Objects in Lund AB [http://neotechnology.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.index.internal.gbptree;
import java.io.IOException;
import java.util.Comparator;
import org.neo4j.io.pagecache.PageCursor;
import static org.neo4j.index.internal.gbptree.GenerationSafePointerPair.NO_LOGICAL_POS;
import static org.neo4j.index.internal.gbptree.GenerationSafePointerPair.read;
/**
* Methods to manipulate single tree node such as set and get header fields,
* insert and fetch keys, values and children.
* <p>
* DESIGN
* <p>
* Using Separate design the internal nodes should look like
* <pre>
* # = empty space
*
* [ HEADER 82B ]|[ KEYS ]|[ CHILDREN ]
* [NODETYPE][TYPE][GENERATION][KEYCOUNT][RIGHTSIBLING][LEFTSIBLING][SUCCESSOR]|[[KEY]...##]|[[CHILD][CHILD]...##]
* 0 1 2 6 10 34 58 82
* </pre>
* Calc offset for key i (starting from 0)
* HEADER_LENGTH + i * SIZE_KEY
* <p>
* Calc offset for child i
* HEADER_LENGTH + SIZE_KEY * MAX_KEY_COUNT_INTERNAL + i * SIZE_CHILD
* <p>
* Using Separate design the leaf nodes should look like
*
* <pre>
* [ HEADER 82B ]|[ KEYS ]|[ VALUES ]
* [NODETYPE][TYPE][GENERATION][KEYCOUNT][RIGHTSIBLING][LEFTSIBLING][SUCCESSOR]|[[KEY]...##]|[[VALUE]...##]
* 0 1 2 6 10 34 58 82
* </pre>
*
* Calc offset for key i (starting from 0)
* HEADER_LENGTH + i * SIZE_KEY
* <p>
* Calc offset for value i
* HEADER_LENGTH + SIZE_KEY * MAX_KEY_COUNT_LEAF + i * SIZE_VALUE
*
* @param <KEY> type of key
* @param <VALUE> type of value
*/
abstract class TreeNode<KEY,VALUE>
{
enum Type
{
LEAF,
INTERNAL
}
enum Overflow
{
YES,
NO,
NEED_DEFRAG
}
// Shared between all node types: TreeNode and FreelistNode
static final int BYTE_POS_NODE_TYPE = 0;
static final byte NODE_TYPE_TREE_NODE = 1;
static final byte NODE_TYPE_FREE_LIST_NODE = 2;
static final int SIZE_PAGE_REFERENCE = GenerationSafePointerPair.SIZE;
static final int BYTE_POS_TYPE = BYTE_POS_NODE_TYPE + Byte.BYTES;
static final int BYTE_POS_GENERATION = BYTE_POS_TYPE + Byte.BYTES;
static final int BYTE_POS_KEYCOUNT = BYTE_POS_GENERATION + Integer.BYTES;
static final int BYTE_POS_RIGHTSIBLING = BYTE_POS_KEYCOUNT + Integer.BYTES;
static final int BYTE_POS_LEFTSIBLING = BYTE_POS_RIGHTSIBLING + SIZE_PAGE_REFERENCE;
static final int BYTE_POS_SUCCESSOR = BYTE_POS_LEFTSIBLING + SIZE_PAGE_REFERENCE;
static final int BASE_HEADER_LENGTH = BYTE_POS_SUCCESSOR + SIZE_PAGE_REFERENCE;
static final byte LEAF_FLAG = 1;
static final byte INTERNAL_FLAG = 0;
static final long NO_NODE_FLAG = 0;
final Layout<KEY,VALUE> layout;
final int pageSize;
TreeNode( int pageSize, Layout<KEY,VALUE> layout )
{
this.pageSize = pageSize;
this.layout = layout;
}
static byte nodeType( PageCursor cursor )
{
return cursor.getByte( BYTE_POS_NODE_TYPE );
}
private static void writeBaseHeader( PageCursor cursor, byte type, long stableGeneration, long unstableGeneration )
{
cursor.putByte( BYTE_POS_NODE_TYPE, NODE_TYPE_TREE_NODE );
cursor.putByte( BYTE_POS_TYPE, type );
setGeneration( cursor, unstableGeneration );
setKeyCount( cursor, 0 );
setRightSibling( cursor, NO_NODE_FLAG, stableGeneration, unstableGeneration );
setLeftSibling( cursor, NO_NODE_FLAG, stableGeneration, unstableGeneration );
setSuccessor( cursor, NO_NODE_FLAG, stableGeneration, unstableGeneration );
}
void initializeLeaf( PageCursor cursor, long stableGeneration, long unstableGeneration )
{
writeBaseHeader( cursor, LEAF_FLAG, stableGeneration, unstableGeneration );
writeAdditionalHeader( cursor );
}
void initializeInternal( PageCursor cursor, long stableGeneration, long unstableGeneration )
{
writeBaseHeader( cursor, INTERNAL_FLAG, stableGeneration, unstableGeneration );
writeAdditionalHeader( cursor );
}
/**
* Write additional header. When called, cursor should be located directly after base header.
* Meaning at {@link #BASE_HEADER_LENGTH}.
*/
abstract void writeAdditionalHeader( PageCursor cursor );
// HEADER METHODS
static boolean isLeaf( PageCursor cursor )
{
return cursor.getByte( BYTE_POS_TYPE ) == LEAF_FLAG;
}
static boolean isInternal( PageCursor cursor )
{
return cursor.getByte( BYTE_POS_TYPE ) == INTERNAL_FLAG;
}
static long generation( PageCursor cursor )
{
return cursor.getInt( BYTE_POS_GENERATION ) & GenerationSafePointer.GENERATION_MASK;
}
static int keyCount( PageCursor cursor )
{
return cursor.getInt( BYTE_POS_KEYCOUNT );
}
static long rightSibling( PageCursor cursor, long stableGeneration, long unstableGeneration )
{
cursor.setOffset( BYTE_POS_RIGHTSIBLING );
return read( cursor, stableGeneration, unstableGeneration, NO_LOGICAL_POS );
}
static long leftSibling( PageCursor cursor, long stableGeneration, long unstableGeneration )
{
cursor.setOffset( BYTE_POS_LEFTSIBLING );
return read( cursor, stableGeneration, unstableGeneration, NO_LOGICAL_POS );
}
static long successor( PageCursor cursor, long stableGeneration, long unstableGeneration )
{
cursor.setOffset( BYTE_POS_SUCCESSOR );
return read( cursor, stableGeneration, unstableGeneration, NO_LOGICAL_POS );
}
static void setGeneration( PageCursor cursor, long generation )
{
GenerationSafePointer.assertGenerationOnWrite( generation );
cursor.putInt( BYTE_POS_GENERATION, (int) generation );
}
static void setKeyCount( PageCursor cursor, int count )
{
if ( count < 0 )
{
throw new IllegalArgumentException( "Invalid key count, " + count + ". On tree node " + cursor.getCurrentPageId() + "." );
}
cursor.putInt( BYTE_POS_KEYCOUNT, count );
}
static void setRightSibling( PageCursor cursor, long rightSiblingId, long stableGeneration,
long unstableGeneration )
{
cursor.setOffset( BYTE_POS_RIGHTSIBLING );
long result = GenerationSafePointerPair.write( cursor, rightSiblingId, stableGeneration, unstableGeneration );
GenerationSafePointerPair.assertSuccess( result );
}
static void setLeftSibling( PageCursor cursor, long leftSiblingId, long stableGeneration, long unstableGeneration )
{
cursor.setOffset( BYTE_POS_LEFTSIBLING );
long result = GenerationSafePointerPair.write( cursor, leftSiblingId, stableGeneration, unstableGeneration );
GenerationSafePointerPair.assertSuccess( result );
}
static void setSuccessor( PageCursor cursor, long successorId, long stableGeneration, long unstableGeneration )
{
cursor.setOffset( BYTE_POS_SUCCESSOR );
long result = GenerationSafePointerPair.write( cursor, successorId, stableGeneration, unstableGeneration );
GenerationSafePointerPair.assertSuccess( result );
}
long pointerGeneration( PageCursor cursor, long readResult )
{
if ( !GenerationSafePointerPair.isRead( readResult ) )
{
throw new IllegalArgumentException( "Expected read result, but got " + readResult );
}
int offset = GenerationSafePointerPair.generationOffset( readResult );
int gsppOffset = GenerationSafePointerPair.isLogicalPos( readResult ) ? childOffset( offset ) : offset;
int gspOffset = GenerationSafePointerPair.resultIsFromSlotA( readResult ) ?
gsppOffset : gsppOffset + GenerationSafePointer.SIZE;
cursor.setOffset( gspOffset );
return GenerationSafePointer.readGeneration( cursor );
}
// BODY METHODS
/**
* Moves items (key/value/child) one step to the right, which means rewriting all items of the particular type
* from pos - itemCount.
* itemCount is keyCount for key and value, but keyCount+1 for children.
*/
static void insertSlotsAt( PageCursor cursor, int pos, int numberOfSlots, int itemCount, int baseOffset,
int itemSize )
{
for ( int posToMoveRight = itemCount - 1, offset = baseOffset + posToMoveRight * itemSize;
posToMoveRight >= pos; posToMoveRight--, offset -= itemSize )
{
cursor.copyTo( offset, cursor, offset + itemSize * numberOfSlots, itemSize );
}
}
static void removeSlotAt( PageCursor cursor, int pos, int itemCount, int baseOffset, int itemSize )
{
for ( int posToMoveLeft = pos + 1, offset = baseOffset + posToMoveLeft * itemSize;
posToMoveLeft < itemCount; posToMoveLeft++, offset += itemSize )
{
cursor.copyTo( offset, cursor, offset - itemSize, itemSize );
}
}
abstract KEY keyAt( PageCursor cursor, KEY into, int pos, Type type );
abstract void insertKeyAndRightChildAt( PageCursor cursor, KEY key, long child, int pos, int keyCount,
long stableGeneration, long unstableGeneration );
abstract void insertKeyValueAt( PageCursor cursor, KEY key, VALUE value, int pos, int keyCount );
abstract void removeKeyValueAt( PageCursor cursor, int pos, int keyCount );
abstract void removeKeyAndRightChildAt( PageCursor cursor, int keyPos, int keyCount );
abstract void removeKeyAndLeftChildAt( PageCursor cursor, int keyPos, int keyCount );
abstract void setKeyAt( PageCursor cursor, KEY key, int pos, Type type );
abstract VALUE valueAt( PageCursor cursor, VALUE value, int pos );
/**
* Overwrite value at position with given value.
* @return True if value was overwritten, false otherwise.
*/
abstract boolean setValueAt( PageCursor cursor, VALUE value, int pos );
abstract long childAt( PageCursor cursor, int pos, long stableGeneration, long unstableGeneration );
abstract void setChildAt( PageCursor cursor, long child, int pos, long stableGeneration, long unstableGeneration );
static void writeChild( PageCursor cursor, long child, long stableGeneration, long unstableGeneration )
{
GenerationSafePointerPair.write( cursor, child, stableGeneration, unstableGeneration );
}
abstract int leafMaxKeyCount();
// HELPERS
abstract boolean reasonableKeyCount( int keyCount );
abstract boolean reasonableChildCount( int childCount );
abstract int childOffset( int pos );
static boolean isNode( long node )
{
return GenerationSafePointerPair.pointer( node ) != NO_NODE_FLAG;
}
Comparator<KEY> keyComparator()
{
return layout;
}
static void goTo( PageCursor cursor, String messageOnError, long nodeId )
throws IOException
{
PageCursorUtil.goTo( cursor, messageOnError, GenerationSafePointerPair.pointer( nodeId ) );
}
/* SPLIT, MERGE AND REBALANCE */
/**
* Will internal overflow if inserting one more key?
* @return true if leaf will overflow, else false.
*/
abstract boolean internalOverflow( int currentKeyCount );
/**
* Will leaf overflow if inserting new key and value?
* @return true if leaf will overflow, else false.
*/
abstract Overflow leafOverflow( PageCursor cursor, int currentKeyCount, KEY newKey, VALUE newValue );
/**
* Clean page from garbage to make room for further insert without having to split.
*/
abstract void defragmentLeaf( PageCursor cursor );
abstract boolean leafUnderflow( int keyCount );
abstract boolean canRebalanceLeaves( int leftKeyCount, int rightKeyCount );
abstract boolean canMergeLeaves( int leftKeyCount, int rightKeyCount );
/**
* Calculate where split should be done and move entries between leaves participating in split.
*
* Keys and values from left are divide between left and right and the new key and value is inserted where it belongs.
*
* Key count is updated.
*/
abstract void doSplitLeaf( PageCursor leftCursor, int leftKeyCount, PageCursor rightCursor, int insertPos, KEY newKey, VALUE newValue,
StructurePropagation<KEY> structurePropagation );
/**
* Performs the entry moving part of split in internal.
*
* Keys and children from left is divided between left and right and the new key and child is inserted where it belongs.
*
* Key count is updated.
*/
abstract void doSplitInternal( PageCursor leftCursor, int leftKeyCount, PageCursor rightCursor, int rightKeyCount, int insertPos,
KEY newKey,
long newRightChild, int middlePos, long stableGeneration, long unstableGeneration );
/**
* Move all rightmost keys and values in left node from given position to right node.
*
* Key count is NOT updated.
*/
abstract void moveKeyValuesFromLeftToRight( PageCursor leftCursor, int leftKeyCount, PageCursor rightCursor, int rightKeyCount,
int fromPosInLeftNode );
}