lucene-java-3.5.0/lucene/src/java/org/apache/lucene/util/packed/Packed64.java

   1 package org.apache.lucene.util.packed;
   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
  20 import org.apache.lucene.store.DataInput;
  21 import org.apache.lucene.util.RamUsageEstimator;
  22
  23 import java.io.IOException;
  24 import java.util.Arrays;
  25
  26 /**
  27  * Space optimized random access capable array of values with a fixed number of
  28  * bits. For 32 bits/value and less, performance on 32 bit machines is not
  29  * optimal. Consider using {@link Packed32} for such a setup.
  30  * </p><p>
  31  * The implementation strives to avoid conditionals and expensive operations,
  32  * sacrificing code clarity to achieve better performance.
  33  */
  34
  35 class Packed64 extends PackedInts.ReaderImpl implements PackedInts.Mutable {
  36   static final int BLOCK_SIZE = 64; // 32 = int, 64 = long
  37   static final int BLOCK_BITS = 6; // The #bits representing BLOCK_SIZE
  38   static final int MOD_MASK = BLOCK_SIZE - 1; // x % BLOCK_SIZE
  39
  40   private static final int ENTRY_SIZE = BLOCK_SIZE + 1;
  41   private static final int FAC_BITPOS = 3;
  42
  43   /*
  44    * In order to make an efficient value-getter, conditionals should be
  45    * avoided. A value can be positioned inside of a block, requiring shifting
  46    * left or right or it can span two blocks, requiring a left-shift on the
  47    * first block and a right-shift on the right block.
  48    * </p><p>
  49    * By always shifting the first block both left and right, we get exactly
  50    * the right bits. By always shifting the second block right and applying
  51    * a mask, we get the right bits there. After that, we | the two bitsets.
  52   */
  53   private static final int[][] SHIFTS =
  54           new int[ENTRY_SIZE][ENTRY_SIZE * FAC_BITPOS];
  55           //new int[BLOCK_SIZE+1][BLOCK_SIZE][BLOCK_SIZE+1];
  56   private static final long[][] MASKS = new long[ENTRY_SIZE][ENTRY_SIZE];
  57
  58   static { // Generate shifts
  59       for (int elementBits = 1 ; elementBits <= BLOCK_SIZE ; elementBits++) {
  60           for (int bitPos = 0 ; bitPos < BLOCK_SIZE ; bitPos++) {
  61               int[] currentShifts = SHIFTS[elementBits];
  62               int base = bitPos * FAC_BITPOS;
  63               currentShifts[base    ] = bitPos;
  64               currentShifts[base + 1] = BLOCK_SIZE - elementBits;
  65               if (bitPos <= BLOCK_SIZE - elementBits) { // Single block
  66                   currentShifts[base + 2] = 0;
  67                   MASKS[elementBits][bitPos] = 0;
  68               } else { // Two blocks
  69                   int rBits = elementBits - (BLOCK_SIZE - bitPos);
  70                   currentShifts[base + 2] = BLOCK_SIZE - rBits;
  71                   MASKS[elementBits][bitPos] = ~(~0L << rBits);
  72               }
  73           }
  74       }
  75   }
  76
  77   /*
  78    * The setter requires more masking than the getter.
  79   */
  80   private static final long[][] WRITE_MASKS =
  81           new long[ENTRY_SIZE][ENTRY_SIZE * FAC_BITPOS];
  82   static {
  83       for (int elementBits = 1 ; elementBits <= BLOCK_SIZE ; elementBits++) {
  84           long elementPosMask = ~(~0L << elementBits);
  85           int[] currentShifts = SHIFTS[elementBits];
  86           long[] currentMasks = WRITE_MASKS[elementBits];
  87           for (int bitPos = 0 ; bitPos < BLOCK_SIZE ; bitPos++) {
  88               int base = bitPos * FAC_BITPOS;
  89               currentMasks[base  ] =~((elementPosMask
  90                                  << currentShifts[base + 1])
  91                                 >>> currentShifts[base]);
  92               if (bitPos <= BLOCK_SIZE - elementBits) { // Second block not used
  93                 currentMasks[base+1] = ~0; // Keep all bits
  94                 currentMasks[base+2] = 0;  // Or with 0
  95               } else {
  96                 currentMasks[base+1] = ~(elementPosMask
  97                                          << currentShifts[base + 2]);
  98                 currentMasks[base+2] = currentShifts[base + 2] == 0 ? 0 : ~0;
  99               }
 100           }
 101       }
 102   }
 103
 104   /* The bits */
 105   private long[] blocks;
 106
 107   // Cached calculations
 108   private int maxPos;      // blocks.length * BLOCK_SIZE / elementBits - 1
 109   private int[] shifts;    // The shifts for the current elementBits
 110   private long[] readMasks;
 111   private long[] writeMasks;
 112
 113   /**
 114    * Creates an array with the internal structures adjusted for the given
 115    * limits and initialized to 0.
 116    * @param valueCount   the number of elements.
 117    * @param bitsPerValue the number of bits available for any given value.
 118    */
 119   public Packed64(int valueCount, int bitsPerValue) {
 120     // TODO: Test for edge-cases (2^31 values, 63 bitsPerValue)
 121     // +2 due to the avoid-conditionals-trick. The last entry is always 0
 122     this(new long[(int)((long)valueCount * bitsPerValue / BLOCK_SIZE + 2)],
 123             valueCount, bitsPerValue);
 124   }
 125
 126
 127   /**
 128    * Creates an array backed by the given blocks.
 129    * </p><p>
 130    * Note: The blocks are used directly, so changes to the given block will
 131    * affect the Packed32-structure.
 132    * @param blocks   used as the internal backing array. Not that the last
 133    *                 element cannot be addressed directly.
 134    * @param valueCount the number of values.
 135    * @param bitsPerValue the number of bits available for any given value.
 136    */
 137   public Packed64(long[] blocks, int valueCount, int bitsPerValue) {
 138     super(valueCount, bitsPerValue);
 139     this.blocks = blocks;
 140     updateCached();
 141   }
 142
 143   /**
 144    * Creates an array with content retrieved from the given DataInput.
 145    * @param in       a DataInput, positioned at the start of Packed64-content.
 146    * @param valueCount  the number of elements.
 147    * @param bitsPerValue the number of bits available for any given value.
 148    * @throws java.io.IOException if the values for the backing array could not
 149    *                             be retrieved.
 150    */
 151   public Packed64(DataInput in, int valueCount, int bitsPerValue)
 152                                                             throws IOException {
 153     super(valueCount, bitsPerValue);
 154     int size = size(valueCount, bitsPerValue);
 155     blocks = new long[size+1]; // +1 due to non-conditional tricks
 156     // TODO: find a faster way to bulk-read longs...
 157     for(int i=0;i<size;i++) {
 158       blocks[i] = in.readLong();
 159     }
 160     updateCached();
 161   }
 162
 163   private static int size(int valueCount, int bitsPerValue) {
 164     final long totBitCount = (long) valueCount * bitsPerValue;
 165     return (int)(totBitCount/64 + ((totBitCount % 64 == 0 ) ? 0:1));
 166   }
 167
 168   private void updateCached() {
 169     readMasks = MASKS[bitsPerValue];
 170     shifts = SHIFTS[bitsPerValue];
 171     writeMasks = WRITE_MASKS[bitsPerValue];
 172     maxPos = (int)((((long)blocks.length) * BLOCK_SIZE / bitsPerValue) - 2);
 173   }
 174
 175   /**
 176    * @param index the position of the value.
 177    * @return the value at the given index.
 178    */
 179   public long get(final int index) {
 180     final long majorBitPos = (long)index * bitsPerValue;
 181     final int elementPos = (int)(majorBitPos >>> BLOCK_BITS); // / BLOCK_SIZE
 182     final int bitPos =     (int)(majorBitPos & MOD_MASK); // % BLOCK_SIZE);
 183
 184     final int base = bitPos * FAC_BITPOS;
 185     assert elementPos < blocks.length : "elementPos: " + elementPos + "; blocks.len: " + blocks.length;
 186     return ((blocks[elementPos] << shifts[base]) >>> shifts[base+1]) |
 187             ((blocks[elementPos+1] >>> shifts[base+2]) & readMasks[bitPos]);
 188   }
 189
 190   public void set(final int index, final long value) {
 191     final long majorBitPos = (long)index * bitsPerValue;
 192     final int elementPos = (int)(majorBitPos >>> BLOCK_BITS); // / BLOCK_SIZE
 193     final int bitPos =     (int)(majorBitPos & MOD_MASK); // % BLOCK_SIZE);
 194     final int base = bitPos * FAC_BITPOS;
 195
 196     blocks[elementPos  ] = (blocks[elementPos  ] & writeMasks[base])
 197                            | (value << shifts[base + 1] >>> shifts[base]);
 198     blocks[elementPos+1] = (blocks[elementPos+1] & writeMasks[base+1])
 199                            | ((value << shifts[base + 2]) & writeMasks[base+2]);
 200   }
 201
 202   @Override
 203   public String toString() {
 204     return "Packed64(bitsPerValue=" + bitsPerValue + ", size="
 205             + size() + ", maxPos=" + maxPos
 206             + ", elements.length=" + blocks.length + ")";
 207   }
 208
 209   public long ramBytesUsed() {
 210     return RamUsageEstimator.NUM_BYTES_ARRAY_HEADER
 211             + blocks.length * RamUsageEstimator.NUM_BYTES_LONG;
 212   }
 213
 214   public void clear() {
 215     Arrays.fill(blocks, 0L);
 216   }
 217 }