-
Notifications
You must be signed in to change notification settings - Fork 2.3k
/
Reference.java
238 lines (201 loc) · 8.22 KB
/
Reference.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
/*
* Copyright (c) 2002-2016 "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 Affero 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 Affero General Public License for more details.
*
* You should have received a copy of the GNU Affero General Public License
* along with this program. If not, see <http://www.gnu.org/licenses/>.
*/
package org.neo4j.kernel.impl.store.format.highlimit;
import java.io.IOException;
import org.neo4j.io.pagecache.PageCursor;
import static java.lang.String.format;
/**
* {@link #encode(long, Object, DataAdapter) Encoding} and {@link #decode(Object, DataAdapter) decoding} of {@code long}
* references, max 58-bit, into an as compact format as possible. Format is close to how utf-8 does similar encoding.
*
* Basically one or more header bits are used to note the number of bytes required to represent a
* particular {@code long} value followed by the value itself. Number of bytes used for any long ranges from
* 3 up to the full 8 bytes. The header bits sits in the most significant bit(s) of the most significant byte,
* so for that the bytes that make up a value is written (and of course read) in big-endian order.
*
* Negative values are also supported, in order to handle relative references.
*
* @author Mattias Persson
*/
enum Reference
{
// bit masks below contain one bit for 's' (sign) so actual address space is one bit less than advertised
// 3-byte, 23-bit addr space: 0sxx xxxx xxxx xxxx xxxx xxxx
BYTE_3( 3, (byte) 0b0, 1 ),
// 4-byte, 30-bit addr space: 10sx xxxx xxxx xxxx xxxx xxxx xxxx xxxx
BYTE_4( 4, (byte) 0b10, 2 ),
// 5-byte, 37-bit addr space: 110s xxxx xxxx xxxx xxxx xxxx xxxx xxxx xxxx xxxx
BYTE_5( 5, (byte) 0b110, 3 ),
// 6-byte, 44-bit addr space: 1110 sxxx xxxx xxxx xxxx xxxx xxxx xxxx xxxx xxxx xxxx xxxx
BYTE_6( 6, (byte) 0b1110, 4 ),
// 7-byte, 51-bit addr space: 1111 0sxx xxxx xxxx xxxx xxxx xxxx xxxx xxxx xxxx xxxx xxxx xxxx xxxx
BYTE_7( 7, (byte) 0b1111_0, 5 ),
// 8-byte, 59-bit addr space: 1111 1sxx xxxx xxxx xxxx xxxx xxxx xxxx xxxx xxxx xxxx xxxx xxxx xxxx xxxx xxxx
BYTE_8( 8, (byte) 0b1111_1, 5 );
public interface DataAdapter<SOURCE>
{
byte getByte( SOURCE source );
short getShort( SOURCE source );
void putByte( byte oneByte, SOURCE source ) throws IOException;
}
public static final DataAdapter<PageCursor> PAGE_CURSOR_ADAPTER = new DataAdapter<PageCursor>()
{
@Override
public byte getByte( PageCursor source )
{
return source.getByte();
}
@Override
public short getShort( PageCursor cursor )
{
return cursor.getShort();
}
@Override
public void putByte( byte oneByte, PageCursor source )
{
source.putByte( oneByte );
}
};
// Take one copy here since Enum#values() does an unnecessary defensive copy every time.
private static final Reference[] ENCODINGS = Reference.values();
static final int MAX_BITS = 58;
private final int numberOfBytes;
private final short highHeader;
private final int headerShift;
private final long valueOverflowMask;
Reference( int numberOfBytes, byte header, int headerBits )
{
this.numberOfBytes = numberOfBytes;
this.headerShift = Byte.SIZE - headerBits;
this.highHeader = (short) (((byte) (header << headerShift)) & 0xFF);
this.valueOverflowMask = ~valueMask( numberOfBytes, headerShift - 1 /*sign bit uses one bit*/ );
}
private long valueMask( int numberOfBytes, int headerShift )
{
long mask = ( 1L << headerShift ) - 1;
for ( int i = 0; i < numberOfBytes - 1; i++ )
{
mask <<= 8;
mask |= 0xFF;
}
return mask;
}
private boolean canEncode( long absoluteReference )
{
return (absoluteReference & valueOverflowMask) == 0;
}
private <SOURCE> void encode( long absoluteReference, boolean positive, SOURCE source,
DataAdapter<SOURCE> adapter ) throws IOException
{
// use big-endianness, most significant byte written first, since it contains encoding information
int shift = (numberOfBytes-1) << 3;
byte signBit = (byte) ((positive ? 0 : 1) << (headerShift - 1));
// first (most significant) byte
adapter.putByte( (byte) (highHeader | signBit | (byte) (absoluteReference >>> shift)), source );
do // rest of the bytes
{
shift -= 8;
adapter.putByte( (byte) (absoluteReference >>> shift), source );
}
while ( shift > 0 );
}
private int maxBitsSupported()
{
return Long.SIZE - Long.numberOfLeadingZeros( ~valueOverflowMask );
}
public static <TARGET> void encode( long reference, TARGET target, DataAdapter<TARGET> adapter ) throws IOException
{
// checking with < 0 seems to be the fastest way of telling
boolean positive = reference >= 0;
long absoluteReference = positive ? reference : ~reference;
for ( Reference encoding : ENCODINGS )
{
if ( encoding.canEncode( absoluteReference ) )
{
encoding.encode( absoluteReference, positive, target, adapter );
return;
}
}
throw unsupportedOperationDueToTooBigReference( reference );
}
private static UnsupportedOperationException unsupportedOperationDueToTooBigReference( long reference )
{
return new UnsupportedOperationException( format( "Reference %d uses too many bits to be encoded by "
+ "current compression scheme, max %d bits allowed", reference, maxBits() ) );
}
public static int length( long reference )
{
boolean positive = reference >= 0;
long absoluteReference = positive ? reference : ~reference;
for ( Reference encoding : ENCODINGS )
{
if ( encoding.canEncode( absoluteReference ) )
{
return encoding.numberOfBytes;
}
}
throw unsupportedOperationDueToTooBigReference( reference );
}
private static int maxBits()
{
int max = 0;
for ( Reference encoding : ENCODINGS )
{
max = Math.max( max, encoding.maxBitsSupported() );
}
return max;
}
public static <SOURCE> long decode( SOURCE source, DataAdapter<SOURCE> adapter )
{
int header = adapter.getByte( source ) & 0xFF;
int sizeMarks = Integer.numberOfLeadingZeros( (~(header & 0xF8)) & 0xFF ) - 24;
int signShift = 8 - sizeMarks - (sizeMarks == 5 ? 1 : 2);
long signBit = ~((header >>> signShift) & 1) + 1;
long register = (header & ((1 << signShift) - 1)) << 16;
register += adapter.getShort( source ) & 0xFFFFL; // 3 bytes
while ( sizeMarks > 0 )
{
register <<= 8;
register += adapter.getByte( source ) & 0xFF;
sizeMarks--;
}
return signBit ^ register;
}
/**
* Convert provided reference to be relative to basisReference
* @param reference reference that will be converter to relative
* @param basisReference conversion basis
* @return reference relative to basisReference
*/
public static long toRelative( long reference, long basisReference )
{
return Math.subtractExact( reference , basisReference );
}
/**
* Convert provided relative to basis reference into absolute
* @param relativeReference relative reference to convert
* @param basisReference basis reference
* @return absolute reference
*/
public static long toAbsolute( long relativeReference, long basisReference )
{
return Math.addExact( relativeReference, basisReference );
}
}