1 package org.apache.lucene.util;
4 * Licensed to the Apache Software Foundation (ASF) under one or more
5 * contributor license agreements. See the NOTICE file distributed with
6 * this work for additional information regarding copyright ownership.
7 * The ASF licenses this file to You under the Apache License, Version 2.0
8 * (the "License"); you may not use this file except in compliance with
9 * the License. You may obtain a copy of the License at
11 * http://www.apache.org/licenses/LICENSE-2.0
13 * Unless required by applicable law or agreed to in writing, software
14 * distributed under the License is distributed on an "AS IS" BASIS,
15 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
16 * See the License for the specific language governing permissions and
17 * limitations under the License.
19 import java.io.IOException;
20 import java.util.Arrays;
21 import java.util.List;
22 import java.util.concurrent.atomic.AtomicLong;
24 import org.apache.lucene.store.DataOutput;
26 import static org.apache.lucene.util.RamUsageEstimator.NUM_BYTES_OBJECT_REF;
29 * Class that Posting and PostingVector use to write byte
30 * streams into shared fixed-size byte[] arrays. The idea
31 * is to allocate slices of increasing lengths For
32 * example, the first slice is 5 bytes, the next slice is
33 * 14, etc. We start by writing our bytes into the first
34 * 5 bytes. When we hit the end of the slice, we allocate
35 * the next slice and then write the address of the new
36 * slice into the last 4 bytes of the previous slice (the
37 * "forwarding address").
39 * Each slice is filled with 0's initially, and we mark
40 * the end with a non-zero byte. This way the methods
41 * that are writing into the slice don't need to record
42 * its length and instead allocate a new slice once they
43 * hit a non-zero byte.
47 public final class ByteBlockPool {
48 public final static int BYTE_BLOCK_SHIFT = 15;
49 public final static int BYTE_BLOCK_SIZE = 1 << BYTE_BLOCK_SHIFT;
50 public final static int BYTE_BLOCK_MASK = BYTE_BLOCK_SIZE - 1;
52 public abstract static class Allocator {
53 protected final int blockSize;
55 public Allocator(int blockSize) {
56 this.blockSize = blockSize;
59 public abstract void recycleByteBlocks(byte[][] blocks, int start, int end);
61 public void recycleByteBlocks(List<byte[]> blocks) {
62 final byte[][] b = blocks.toArray(new byte[blocks.size()][]);
63 recycleByteBlocks(b, 0, b.length);
66 public byte[] getByteBlock() {
67 return new byte[blockSize];
71 public static final class DirectAllocator extends Allocator {
73 public DirectAllocator() {
74 this(BYTE_BLOCK_SIZE);
77 public DirectAllocator(int blockSize) {
82 public void recycleByteBlocks(byte[][] blocks, int start, int end) {
87 public static class DirectTrackingAllocator extends Allocator {
88 private final AtomicLong bytesUsed;
90 public DirectTrackingAllocator(AtomicLong bytesUsed) {
91 this(BYTE_BLOCK_SIZE, bytesUsed);
94 public DirectTrackingAllocator(int blockSize, AtomicLong bytesUsed) {
96 this.bytesUsed = bytesUsed;
99 public byte[] getByteBlock() {
100 bytesUsed.addAndGet(blockSize);
101 return new byte[blockSize];
104 public void recycleByteBlocks(byte[][] blocks, int start, int end) {
105 bytesUsed.addAndGet(-((end-start)* blockSize));
106 for (int i = start; i < end; i++) {
114 public byte[][] buffers = new byte[10][];
116 int bufferUpto = -1; // Which buffer we are upto
117 public int byteUpto = BYTE_BLOCK_SIZE; // Where we are in head buffer
119 public byte[] buffer; // Current head buffer
120 public int byteOffset = -BYTE_BLOCK_SIZE; // Current head offset
122 private final Allocator allocator;
124 public ByteBlockPool(Allocator allocator) {
125 this.allocator = allocator;
128 public void dropBuffersAndReset() {
129 if (bufferUpto != -1) {
130 // Recycle all but the first buffer
131 allocator.recycleByteBlocks(buffers, 0, 1+bufferUpto);
133 // Re-use the first buffer
135 byteUpto = BYTE_BLOCK_SIZE;
136 byteOffset = -BYTE_BLOCK_SIZE;
137 buffers = new byte[10][];
142 public void reset() {
143 if (bufferUpto != -1) {
144 // We allocated at least one buffer
146 for(int i=0;i<bufferUpto;i++)
147 // Fully zero fill buffers that we fully used
148 Arrays.fill(buffers[i], (byte) 0);
150 // Partial zero fill the final buffer
151 Arrays.fill(buffers[bufferUpto], 0, byteUpto, (byte) 0);
154 // Recycle all but the first buffer
155 allocator.recycleByteBlocks(buffers, 1, 1+bufferUpto);
157 // Re-use the first buffer
165 public void nextBuffer() {
166 if (1+bufferUpto == buffers.length) {
167 byte[][] newBuffers = new byte[ArrayUtil.oversize(buffers.length+1,
168 NUM_BYTES_OBJECT_REF)][];
169 System.arraycopy(buffers, 0, newBuffers, 0, buffers.length);
170 buffers = newBuffers;
172 buffer = buffers[1+bufferUpto] = allocator.getByteBlock();
176 byteOffset += BYTE_BLOCK_SIZE;
179 public int newSlice(final int size) {
180 if (byteUpto > BYTE_BLOCK_SIZE-size)
182 final int upto = byteUpto;
184 buffer[byteUpto-1] = 16;
188 // Size of each slice. These arrays should be at most 16
189 // elements (index is encoded with 4 bits). First array
190 // is just a compact way to encode X+1 with a max. Second
191 // array is the length of each slice, ie first slice is 5
192 // bytes, next slice is 14 bytes, etc.
194 public final static int[] nextLevelArray = {1, 2, 3, 4, 5, 6, 7, 8, 9, 9};
195 public final static int[] levelSizeArray = {5, 14, 20, 30, 40, 40, 80, 80, 120, 200};
196 public final static int FIRST_LEVEL_SIZE = levelSizeArray[0];
198 public int allocSlice(final byte[] slice, final int upto) {
200 final int level = slice[upto] & 15;
201 final int newLevel = nextLevelArray[level];
202 final int newSize = levelSizeArray[newLevel];
204 // Maybe allocate another block
205 if (byteUpto > BYTE_BLOCK_SIZE-newSize)
208 final int newUpto = byteUpto;
209 final int offset = newUpto + byteOffset;
212 // Copy forward the past 3 bytes (which we are about
213 // to overwrite with the forwarding address):
214 buffer[newUpto] = slice[upto-3];
215 buffer[newUpto+1] = slice[upto-2];
216 buffer[newUpto+2] = slice[upto-1];
218 // Write forwarding address at end of last slice:
219 slice[upto-3] = (byte) (offset >>> 24);
220 slice[upto-2] = (byte) (offset >>> 16);
221 slice[upto-1] = (byte) (offset >>> 8);
222 slice[upto] = (byte) offset;
225 buffer[byteUpto-1] = (byte) (16|newLevel);
230 // Fill in a BytesRef from term's length & bytes encoded in
232 public final BytesRef setBytesRef(BytesRef term, int textStart) {
233 final byte[] bytes = term.bytes = buffers[textStart >> BYTE_BLOCK_SHIFT];
234 int pos = textStart & BYTE_BLOCK_MASK;
235 if ((bytes[pos] & 0x80) == 0) {
237 term.length = bytes[pos];
241 term.length = (bytes[pos]&0x7f) + ((bytes[pos+1]&0xff)<<7);
244 assert term.length >= 0;
249 * Copies the given {@link BytesRef} at the current positions (
250 * {@link #byteUpto} across buffer boundaries
252 public final void copy(final BytesRef bytes) {
253 int length = bytes.length;
254 int offset = bytes.offset;
255 int overflow = (length + byteUpto) - BYTE_BLOCK_SIZE;
258 System.arraycopy(bytes.bytes, offset, buffer, byteUpto, length);
262 final int bytesToCopy = length-overflow;
263 System.arraycopy(bytes.bytes, offset, buffer, byteUpto, bytesToCopy);
264 offset += bytesToCopy;
265 length -= bytesToCopy;
267 overflow = overflow - BYTE_BLOCK_SIZE;
273 * Writes the pools content to the given {@link DataOutput}
275 public final void writePool(final DataOutput out) throws IOException {
276 int bytesOffset = byteOffset;
278 while (bytesOffset > 0) {
279 out.writeBytes(buffers[block++], BYTE_BLOCK_SIZE);
280 bytesOffset -= BYTE_BLOCK_SIZE;
282 out.writeBytes(buffers[block], byteUpto);