lucene-java-3.5.0/lucene/src/java/org/apache/lucene/util/ByteBlockPool.java

   1 package org.apache.lucene.util;
   2
   3 /**
   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
  10  *
  11  *     http://www.apache.org/licenses/LICENSE-2.0
  12  *
  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.
  18  */
  19 import java.io.IOException;
  20 import java.util.Arrays;
  21 import java.util.List;
  22 import java.util.concurrent.atomic.AtomicLong;
  23
  24 import org.apache.lucene.store.DataOutput;
  25
  26 import static org.apache.lucene.util.RamUsageEstimator.NUM_BYTES_OBJECT_REF;
  27
  28 /**
  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").
  38  *
  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.
  44  *
  45  * @lucene.internal
  46  **/
  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;
  51
  52   public abstract static class Allocator {
  53     protected final int blockSize;
  54
  55     public Allocator(int blockSize) {
  56       this.blockSize = blockSize;
  57     }
  58
  59     public abstract void recycleByteBlocks(byte[][] blocks, int start, int end);
  60
  61     public void recycleByteBlocks(List<byte[]> blocks) {
  62       final byte[][] b = blocks.toArray(new byte[blocks.size()][]);
  63       recycleByteBlocks(b, 0, b.length);
  64     }
  65
  66     public byte[] getByteBlock() {
  67       return new byte[blockSize];
  68     }
  69   }
  70
  71   public static final class DirectAllocator extends Allocator {
  72
  73     public DirectAllocator() {
  74       this(BYTE_BLOCK_SIZE);
  75     }
  76
  77     public DirectAllocator(int blockSize) {
  78       super(blockSize);
  79     }
  80
  81     @Override
  82     public void recycleByteBlocks(byte[][] blocks, int start, int end) {
  83     }
  84
  85   }
  86
  87   public static class DirectTrackingAllocator extends Allocator {
  88     private final AtomicLong bytesUsed;
  89
  90     public DirectTrackingAllocator(AtomicLong bytesUsed) {
  91       this(BYTE_BLOCK_SIZE, bytesUsed);
  92     }
  93
  94     public DirectTrackingAllocator(int blockSize, AtomicLong bytesUsed) {
  95       super(blockSize);
  96       this.bytesUsed = bytesUsed;
  97     }
  98
  99     public byte[] getByteBlock() {
 100       bytesUsed.addAndGet(blockSize);
 101       return new byte[blockSize];
 102     }
 103     @Override
 104     public void recycleByteBlocks(byte[][] blocks, int start, int end) {
 105       bytesUsed.addAndGet(-((end-start)* blockSize));
 106       for (int i = start; i < end; i++) {
 107         blocks[i] = null;
 108       }
 109     }
 110
 111   };
 112
 113
 114   public byte[][] buffers = new byte[10][];
 115
 116   int bufferUpto = -1;                        // Which buffer we are upto
 117   public int byteUpto = BYTE_BLOCK_SIZE;             // Where we are in head buffer
 118
 119   public byte[] buffer;                              // Current head buffer
 120   public int byteOffset = -BYTE_BLOCK_SIZE;          // Current head offset
 121
 122   private final Allocator allocator;
 123
 124   public ByteBlockPool(Allocator allocator) {
 125     this.allocator = allocator;
 126   }
 127
 128   public void dropBuffersAndReset() {
 129     if (bufferUpto != -1) {
 130       // Recycle all but the first buffer
 131       allocator.recycleByteBlocks(buffers, 0, 1+bufferUpto);
 132
 133       // Re-use the first buffer
 134       bufferUpto = -1;
 135       byteUpto = BYTE_BLOCK_SIZE;
 136       byteOffset = -BYTE_BLOCK_SIZE;
 137       buffers = new byte[10][];
 138       buffer = null;
 139     }
 140   }
 141
 142   public void reset() {
 143     if (bufferUpto != -1) {
 144       // We allocated at least one buffer
 145
 146       for(int i=0;i<bufferUpto;i++)
 147         // Fully zero fill buffers that we fully used
 148         Arrays.fill(buffers[i], (byte) 0);
 149
 150       // Partial zero fill the final buffer
 151       Arrays.fill(buffers[bufferUpto], 0, byteUpto, (byte) 0);
 152
 153       if (bufferUpto > 0)
 154         // Recycle all but the first buffer
 155         allocator.recycleByteBlocks(buffers, 1, 1+bufferUpto);
 156
 157       // Re-use the first buffer
 158       bufferUpto = 0;
 159       byteUpto = 0;
 160       byteOffset = 0;
 161       buffer = buffers[0];
 162     }
 163   }
 164
 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;
 171     }
 172     buffer = buffers[1+bufferUpto] = allocator.getByteBlock();
 173     bufferUpto++;
 174
 175     byteUpto = 0;
 176     byteOffset += BYTE_BLOCK_SIZE;
 177   }
 178
 179   public int newSlice(final int size) {
 180     if (byteUpto > BYTE_BLOCK_SIZE-size)
 181       nextBuffer();
 182     final int upto = byteUpto;
 183     byteUpto += size;
 184     buffer[byteUpto-1] = 16;
 185     return upto;
 186   }
 187
 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.
 193
 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];
 197
 198   public int allocSlice(final byte[] slice, final int upto) {
 199
 200     final int level = slice[upto] & 15;
 201     final int newLevel = nextLevelArray[level];
 202     final int newSize = levelSizeArray[newLevel];
 203
 204     // Maybe allocate another block
 205     if (byteUpto > BYTE_BLOCK_SIZE-newSize)
 206       nextBuffer();
 207
 208     final int newUpto = byteUpto;
 209     final int offset = newUpto + byteOffset;
 210     byteUpto += newSize;
 211
 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];
 217
 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;
 223
 224     // Write new level:
 225     buffer[byteUpto-1] = (byte) (16|newLevel);
 226
 227     return newUpto+3;
 228   }
 229
 230   // Fill in a BytesRef from term's length & bytes encoded in
 231   // byte block
 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) {
 236       // length is 1 byte
 237       term.length = bytes[pos];
 238       term.offset = pos+1;
 239     } else {
 240       // length is 2 bytes
 241       term.length = (bytes[pos]&0x7f) + ((bytes[pos+1]&0xff)<<7);
 242       term.offset = pos+2;
 243     }
 244     assert term.length >= 0;
 245     return term;
 246   }
 247
 248   /**
 249    * Copies the given {@link BytesRef} at the current positions (
 250    * {@link #byteUpto} across buffer boundaries
 251    */
 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;
 256     do {
 257       if (overflow <= 0) {
 258         System.arraycopy(bytes.bytes, offset, buffer, byteUpto, length);
 259         byteUpto += length;
 260         break;
 261       } else {
 262         final int bytesToCopy = length-overflow;
 263         System.arraycopy(bytes.bytes, offset, buffer, byteUpto, bytesToCopy);
 264         offset += bytesToCopy;
 265         length -= bytesToCopy;
 266         nextBuffer();
 267         overflow = overflow - BYTE_BLOCK_SIZE;
 268       }
 269     }  while(true);
 270   }
 271
 272   /**
 273    * Writes the pools content to the given {@link DataOutput}
 274    */
 275   public final void writePool(final DataOutput out) throws IOException {
 276     int bytesOffset = byteOffset;
 277     int block = 0;
 278     while (bytesOffset > 0) {
 279       out.writeBytes(buffers[block++], BYTE_BLOCK_SIZE);
 280       bytesOffset -= BYTE_BLOCK_SIZE;
 281     }
 282     out.writeBytes(buffers[block], byteUpto);
 283   }
 284 }
 285