-
Notifications
You must be signed in to change notification settings - Fork 2.3k
/
KeySearch.java
163 lines (150 loc) · 5.89 KB
/
KeySearch.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
/*
* Copyright (c) 2002-2017 "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.gbptree;
import java.util.Comparator;
import org.neo4j.io.pagecache.PageCursor;
/**
* Methods for (binary-)searching keys in a tree node.
*/
class KeySearch
{
private static final int POSITION_MASK = 0x3FFFFFFF;
private static final int HIT_FLAG = 0x80000000;
private static final int NO_HIT_FLAG = 0x00000000;
private static final int HIT_MASK = HIT_FLAG | NO_HIT_FLAG;
private static final int SUCCESS_FLAG = 0x00000000;
private static final int NO_SUCCESS_FLAG = 0x40000000;
private static final int SUCCESS_MASK = SUCCESS_FLAG | NO_SUCCESS_FLAG;
/**
* Search for left most pos such that keyAtPos obeys key <= keyAtPos.
* Return pos (not offset) of keyAtPos, or key count if no such key exist.
* <p>
* On insert, key should be inserted at pos.
* On seek in internal, child at pos should be followed from internal node.
* On seek in leaf, value at pos is correct if keyAtPos is equal to key.
* <p>
* Implemented as binary search.
* <p>
* Leaves cursor on same page as when called. No guarantees on offset.
*
* @param cursor {@link PageCursor} pinned to page with node (internal or leaf does not matter)
* @param bTreeNode {@link TreeNode} that knows how to operate on KEY and VALUE
* @param key KEY to search for
* @param readKey KEY to use as temporary storage during calculation.
* @param keyCount number of keys in node when starting search
* @return search result where least significant 31 bits are first position i for which
* bTreeNode.keyComparator().compare( key, bTreeNode.keyAt( i ) <= 0, or keyCount if no such key exists.
* highest bit (sign bit) says whether or not the exact key was found in the node, if so set to 1, otherwise 0.
* To extract position from the returned search result, then use {@link #positionOf(int)}.
* To extract whether or not the exact key was found, then use {@link #isHit(int)}.
*/
static <KEY,VALUE> int search( PageCursor cursor, TreeNode<KEY,VALUE> bTreeNode, KEY key,
KEY readKey, int keyCount )
{
if ( keyCount == 0 )
{
return searchResult( 0, false );
}
int lower = 0;
int higher = keyCount-1;
int pos;
boolean hit = false;
// Compare key with lower and higher and sort out special cases
Comparator<KEY> comparator = bTreeNode.keyComparator();
int comparison;
// key greater than greatest key in node
if ( comparator.compare( key, bTreeNode.keyAt( cursor, readKey, higher ) ) > 0 )
{
pos = keyCount;
}
// key smaller than or equal to smallest key in node
else if ( (comparison = comparator.compare( key, bTreeNode.keyAt( cursor, readKey, lower ) )) <= 0 )
{
if ( comparison == 0 )
{
hit = true;
}
pos = 0;
}
else
{
// Start binary search
// If key <= keyAtPos -> move higher to pos
// If key > keyAtPos -> move lower to pos+1
// Terminate when lower == higher
while ( lower < higher )
{
pos = (lower + higher) / 2;
comparison = comparator.compare( key, bTreeNode.keyAt( cursor, readKey, pos ) );
if ( comparison <= 0 )
{
higher = pos;
}
else
{
lower = pos+1;
}
}
if ( lower != higher )
{
return NO_SUCCESS_FLAG;
}
pos = lower;
hit = comparator.compare( key, bTreeNode.keyAt( cursor, readKey, pos ) ) == 0;
}
return searchResult( pos, hit );
}
private static int searchResult( int pos, boolean hit )
{
return (pos & POSITION_MASK) | (hit ? HIT_FLAG : NO_HIT_FLAG);
}
/**
* Extracts the position from a search result from {@link #search(PageCursor, TreeNode, Object, Object, int)}.
*
* @param searchResult search result from {@link #search(PageCursor, TreeNode, Object, Object, int)}.
* @return position of the search result.
*/
static int positionOf( int searchResult )
{
return searchResult & POSITION_MASK;
}
/**
* Extracts whether or not the searched key was found from search result from
* {@link #search(PageCursor, TreeNode, Object, Object, int)}.
*
* @param searchResult search result form {@link #search(PageCursor, TreeNode, Object, Object, int)}.
* @return whether or not the searched key was found.
*/
static boolean isHit( int searchResult )
{
return (searchResult & HIT_MASK) == HIT_FLAG;
}
static boolean isSuccess( int searchResult )
{
return (searchResult & SUCCESS_MASK) == SUCCESS_FLAG;
}
static void assertSuccess( int searchResult )
{
if ( !isSuccess( searchResult ) )
{
throw new TreeInconsistencyException( "Search terminated in unexpected way" );
}
}
}