--- /dev/null
+package org.apache.lucene.util.packed;
+
+/**
+ * Licensed to the Apache Software Foundation (ASF) under one or more
+ * contributor license agreements. See the NOTICE file distributed with
+ * this work for additional information regarding copyright ownership.
+ * The ASF licenses this file to You under the Apache License, Version 2.0
+ * (the "License"); you may not use this file except in compliance with
+ * the License. You may obtain a copy of the License at
+ *
+ * http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License.
+ */
+
+import org.apache.lucene.store.DataInput;
+import org.apache.lucene.store.DataOutput;
+import org.apache.lucene.util.CodecUtil;
+import org.apache.lucene.util.Constants;
+
+import java.io.IOException;
+
+/**
+ * Simplistic compression for array of unsigned long values.
+ * Each value is >= 0 and <= a specified maximum value. The
+ * values are stored as packed ints, with each value
+ * consuming a fixed number of bits.
+ *
+ * @lucene.internal
+ */
+
+public class PackedInts {
+
+ private final static String CODEC_NAME = "PackedInts";
+ private final static int VERSION_START = 0;
+ private final static int VERSION_CURRENT = VERSION_START;
+
+ /**
+ * A read-only random access array of positive integers.
+ * @lucene.internal
+ */
+ public static interface Reader {
+ /**
+ * @param index the position of the wanted value.
+ * @return the value at the stated index.
+ */
+ long get(int index);
+
+ /**
+ * @return the number of bits used to store any given value.
+ * Note: This does not imply that memory usage is
+ * {@code bitsPerValue * #values} as implementations are free to
+ * use non-space-optimal packing of bits.
+ */
+ int getBitsPerValue();
+
+ /**
+ * @return the number of values.
+ */
+ int size();
+
+ /**
+ * Expert: if the bit-width of this reader matches one of
+ * java's native types, returns the underlying array
+ * (ie, byte[], short[], int[], long[]); else, returns
+ * null. Note that when accessing the array you must
+ * upgrade the type (bitwise AND with all ones), to
+ * interpret the full value as unsigned. Ie,
+ * bytes[idx]&0xFF, shorts[idx]&0xFFFF, etc.
+ */
+ Object getArray();
+
+ /**
+ * Returns true if this implementation is backed by a
+ * native java array.
+ *
+ * @see #getArray
+ */
+ boolean hasArray();
+ }
+
+ /**
+ * A packed integer array that can be modified.
+ * @lucene.internal
+ */
+ public static interface Mutable extends Reader {
+ /**
+ * Set the value at the given index in the array.
+ * @param index where the value should be positioned.
+ * @param value a value conforming to the constraints set by the array.
+ */
+ void set(int index, long value);
+
+ /**
+ * Sets all values to 0.
+ */
+
+ void clear();
+ }
+
+ /**
+ * A simple base for Readers that keeps track of valueCount and bitsPerValue.
+ * @lucene.internal
+ */
+ public static abstract class ReaderImpl implements Reader {
+ protected final int bitsPerValue;
+ protected final int valueCount;
+
+ protected ReaderImpl(int valueCount, int bitsPerValue) {
+ this.bitsPerValue = bitsPerValue;
+ assert bitsPerValue > 0 && bitsPerValue <= 64 : "bitsPerValue=" + bitsPerValue;
+ this.valueCount = valueCount;
+ }
+
+ public int getBitsPerValue() {
+ return bitsPerValue;
+ }
+
+ public int size() {
+ return valueCount;
+ }
+
+ public long getMaxValue() { // Convenience method
+ return maxValue(bitsPerValue);
+ }
+
+ public Object getArray() {
+ return null;
+ }
+
+ public boolean hasArray() {
+ return false;
+ }
+ }
+
+ /** A write-once Writer.
+ * @lucene.internal
+ */
+ public static abstract class Writer {
+ protected final DataOutput out;
+ protected final int bitsPerValue;
+ protected final int valueCount;
+
+ protected Writer(DataOutput out, int valueCount, int bitsPerValue)
+ throws IOException {
+ assert bitsPerValue <= 64;
+
+ this.out = out;
+ this.valueCount = valueCount;
+ this.bitsPerValue = bitsPerValue;
+ CodecUtil.writeHeader(out, CODEC_NAME, VERSION_CURRENT);
+ out.writeVInt(bitsPerValue);
+ out.writeVInt(valueCount);
+ }
+
+ public abstract void add(long v) throws IOException;
+ public abstract void finish() throws IOException;
+ }
+
+ /**
+ * Retrieve PackedInt data from the DataInput and return a packed int
+ * structure based on it.
+ * @param in positioned at the beginning of a stored packed int structure.
+ * @return a read only random access capable array of positive integers.
+ * @throws IOException if the structure could not be retrieved.
+ * @lucene.internal
+ */
+ public static Reader getReader(DataInput in) throws IOException {
+ CodecUtil.checkHeader(in, CODEC_NAME, VERSION_START, VERSION_START);
+ final int bitsPerValue = in.readVInt();
+ assert bitsPerValue > 0 && bitsPerValue <= 64: "bitsPerValue=" + bitsPerValue;
+ final int valueCount = in.readVInt();
+
+ switch (bitsPerValue) {
+ case 8:
+ return new Direct8(in, valueCount);
+ case 16:
+ return new Direct16(in, valueCount);
+ case 32:
+ return new Direct32(in, valueCount);
+ case 64:
+ return new Direct64(in, valueCount);
+ default:
+ if (Constants.JRE_IS_64BIT || bitsPerValue >= 32) {
+ return new Packed64(in, valueCount, bitsPerValue);
+ } else {
+ return new Packed32(in, valueCount, bitsPerValue);
+ }
+ }
+ }
+
+ /**
+ * Create a packed integer array with the given amount of values initialized
+ * to 0. the valueCount and the bitsPerValue cannot be changed after creation.
+ * All Mutables known by this factory are kept fully in RAM.
+ * @param valueCount the number of elements.
+ * @param bitsPerValue the number of bits available for any given value.
+ * @return a mutable packed integer array.
+ * @throws java.io.IOException if the Mutable could not be created. With the
+ * current implementations, this never happens, but the method
+ * signature allows for future persistence-backed Mutables.
+ * @lucene.internal
+ */
+ public static Mutable getMutable(
+ int valueCount, int bitsPerValue) {
+ switch (bitsPerValue) {
+ case 8:
+ return new Direct8(valueCount);
+ case 16:
+ return new Direct16(valueCount);
+ case 32:
+ return new Direct32(valueCount);
+ case 64:
+ return new Direct64(valueCount);
+ default:
+ if (Constants.JRE_IS_64BIT || bitsPerValue >= 32) {
+ return new Packed64(valueCount, bitsPerValue);
+ } else {
+ return new Packed32(valueCount, bitsPerValue);
+ }
+ }
+ }
+
+ /**
+ * Create a packed integer array writer for the given number of values at the
+ * given bits/value. Writers append to the given IndexOutput and has very
+ * low memory overhead.
+ * @param out the destination for the produced bits.
+ * @param valueCount the number of elements.
+ * @param bitsPerValue the number of bits available for any given value.
+ * @return a Writer ready for receiving values.
+ * @throws IOException if bits could not be written to out.
+ * @lucene.internal
+ */
+ public static Writer getWriter(DataOutput out, int valueCount, int bitsPerValue)
+ throws IOException {
+ return new PackedWriter(out, valueCount, bitsPerValue);
+ }
+
+ /** Returns how many bits are required to hold values up
+ * to and including maxValue
+ * @param maxValue the maximum value that should be representable.
+ * @return the amount of bits needed to represent values from 0 to maxValue.
+ * @lucene.internal
+ */
+ public static int bitsRequired(long maxValue) {
+ // Very high long values does not translate well to double, so we do an
+ // explicit check for the edge cases
+ if (maxValue > 0x3FFFFFFFFFFFFFFFL) {
+ return 63;
+ } if (maxValue > 0x1FFFFFFFFFFFFFFFL) {
+ return 62;
+ }
+ return Math.max(1, (int) Math.ceil(Math.log(1+maxValue)/Math.log(2.0)));
+ }
+
+ /**
+ * Calculates the maximum unsigned long that can be expressed with the given
+ * number of bits.
+ * @param bitsPerValue the number of bits available for any given value.
+ * @return the maximum value for the given bits.
+ * @lucene.internal
+ */
+ public static long maxValue(int bitsPerValue) {
+ return bitsPerValue == 64 ? Long.MAX_VALUE : ~(~0L << bitsPerValue);
+ }
+
+ /** Rounds bitsPerValue up to 8, 16, 32 or 64. */
+ public static int getNextFixedSize(int bitsPerValue) {
+ if (bitsPerValue <= 8) {
+ return 8;
+ } else if (bitsPerValue <= 16) {
+ return 16;
+ } else if (bitsPerValue <= 32) {
+ return 32;
+ } else {
+ return 64;
+ }
+ }
+
+ /** Possibly wastes some storage in exchange for faster lookups */
+ public static int getRoundedFixedSize(int bitsPerValue) {
+ if (bitsPerValue > 58 || (bitsPerValue < 32 && bitsPerValue > 29)) { // 10% space-waste is ok
+ return getNextFixedSize(bitsPerValue);
+ } else {
+ return bitsPerValue;
+ }
+ }
+}
fnp / pylucene.git / blobdiff