1 package org.apache.lucene.index;
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.
20 /* Class that Posting and PostingVector use to write byte
21 * streams into shared fixed-size byte[] arrays. The idea
22 * is to allocate slices of increasing lengths For
23 * example, the first slice is 5 bytes, the next slice is
24 * 14, etc. We start by writing our bytes into the first
25 * 5 bytes. When we hit the end of the slice, we allocate
26 * the next slice and then write the address of the new
27 * slice into the last 4 bytes of the previous slice (the
28 * "forwarding address").
30 * Each slice is filled with 0's initially, and we mark
31 * the end with a non-zero byte. This way the methods
32 * that are writing into the slice don't need to record
33 * its length and instead allocate a new slice once they
34 * hit a non-zero byte. */
36 import java.util.Arrays;
37 import java.util.List;
38 import static org.apache.lucene.util.RamUsageEstimator.NUM_BYTES_OBJECT_REF;
39 import org.apache.lucene.util.ArrayUtil;
42 final class ByteBlockPool {
44 abstract static class Allocator {
45 abstract void recycleByteBlocks(byte[][] blocks, int start, int end);
46 abstract void recycleByteBlocks(List<byte[]> blocks);
47 abstract byte[] getByteBlock();
50 public byte[][] buffers = new byte[10][];
52 int bufferUpto = -1; // Which buffer we are upto
53 public int byteUpto = DocumentsWriter.BYTE_BLOCK_SIZE; // Where we are in head buffer
55 public byte[] buffer; // Current head buffer
56 public int byteOffset = -DocumentsWriter.BYTE_BLOCK_SIZE; // Current head offset
58 private final Allocator allocator;
60 public ByteBlockPool(Allocator allocator) {
61 this.allocator = allocator;
65 if (bufferUpto != -1) {
66 // We allocated at least one buffer
68 for(int i=0;i<bufferUpto;i++)
69 // Fully zero fill buffers that we fully used
70 Arrays.fill(buffers[i], (byte) 0);
72 // Partial zero fill the final buffer
73 Arrays.fill(buffers[bufferUpto], 0, byteUpto, (byte) 0);
76 // Recycle all but the first buffer
77 allocator.recycleByteBlocks(buffers, 1, 1+bufferUpto);
79 // Re-use the first buffer
87 public void nextBuffer() {
88 if (1+bufferUpto == buffers.length) {
89 byte[][] newBuffers = new byte[ArrayUtil.oversize(buffers.length+1,
90 NUM_BYTES_OBJECT_REF)][];
91 System.arraycopy(buffers, 0, newBuffers, 0, buffers.length);
94 buffer = buffers[1+bufferUpto] = allocator.getByteBlock();
98 byteOffset += DocumentsWriter.BYTE_BLOCK_SIZE;
101 public int newSlice(final int size) {
102 if (byteUpto > DocumentsWriter.BYTE_BLOCK_SIZE-size)
104 final int upto = byteUpto;
106 buffer[byteUpto-1] = 16;
110 // Size of each slice. These arrays should be at most 16
111 // elements (index is encoded with 4 bits). First array
112 // is just a compact way to encode X+1 with a max. Second
113 // array is the length of each slice, ie first slice is 5
114 // bytes, next slice is 14 bytes, etc.
115 final static int[] nextLevelArray = {1, 2, 3, 4, 5, 6, 7, 8, 9, 9};
116 final static int[] levelSizeArray = {5, 14, 20, 30, 40, 40, 80, 80, 120, 200};
117 final static int FIRST_LEVEL_SIZE = levelSizeArray[0];
119 public int allocSlice(final byte[] slice, final int upto) {
121 final int level = slice[upto] & 15;
122 final int newLevel = nextLevelArray[level];
123 final int newSize = levelSizeArray[newLevel];
125 // Maybe allocate another block
126 if (byteUpto > DocumentsWriter.BYTE_BLOCK_SIZE-newSize)
129 final int newUpto = byteUpto;
130 final int offset = newUpto + byteOffset;
133 // Copy forward the past 3 bytes (which we are about
134 // to overwrite with the forwarding address):
135 buffer[newUpto] = slice[upto-3];
136 buffer[newUpto+1] = slice[upto-2];
137 buffer[newUpto+2] = slice[upto-1];
139 // Write forwarding address at end of last slice:
140 slice[upto-3] = (byte) (offset >>> 24);
141 slice[upto-2] = (byte) (offset >>> 16);
142 slice[upto-1] = (byte) (offset >>> 8);
143 slice[upto] = (byte) offset;
146 buffer[byteUpto-1] = (byte) (16|newLevel);