← Back to branch summary

~slub.team/goobi-indexserver/3.x

« back to all changes in this revision

Viewing changes to lucene/src/java/org/apache/lucene/util/packed/PackedInts.java

  • Committer: Sebastian Meyer
  • Date: 2012-08-03 09:12:40 UTC
  • Revision ID: sebastian.meyer@slub-dresden.de-20120803091240-x6861b0vabq1xror
https://launchpad.net/bugs/985487
Remove Lucene and Solr source code and add patches instead
Fix Bug #985487: Auto-suggestion for the search interface

Show diffs side-by-side

added added

removed removed

Lines of Context:
lucene/src/java/org/apache/lucene/util/packed/PackedInts.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.store.DataOutput;
22
 
import org.apache.lucene.util.CodecUtil;
23
 
import org.apache.lucene.util.Constants;
24
 
 
25
 
import java.io.IOException;
26
 
 
27
 
/**
28
 
 * Simplistic compression for array of unsigned long values.
29
 
 * Each value is >= 0 and <= a specified maximum value.  The
30
 
 * values are stored as packed ints, with each value
31
 
 * consuming a fixed number of bits.
32
 
 *
33
 
 * @lucene.internal
34
 
 */
35
 
 
36
 
public class PackedInts {
37
 
 
38
 
  private final static String CODEC_NAME = "PackedInts";
39
 
  private final static int VERSION_START = 0;
40
 
  private final static int VERSION_CURRENT = VERSION_START;
41
 
 
42
 
  /**
43
 
   * A read-only random access array of positive integers.
44
 
   * @lucene.internal
45
 
   */
46
 
  public static interface Reader {
47
 
    /**
48
 
     * @param index the position of the wanted value.
49
 
     * @return the value at the stated index.
50
 
     */
51
 
    long get(int index);
52
 
 
53
 
    /**
54
 
     * @return the number of bits used to store any given value.
55
 
     *         Note: This does not imply that memory usage is
56
 
     *         {@code bitsPerValue * #values} as implementations are free to
57
 
     *         use non-space-optimal packing of bits.
58
 
     */
59
 
    int getBitsPerValue();
60
 
 
61
 
    /**
62
 
     * @return the number of values.
63
 
     */
64
 
    int size();
65
 
 
66
 
    /**
67
 
     * Expert: if the bit-width of this reader matches one of
68
 
     * java's native types, returns the underlying array
69
 
     * (ie, byte[], short[], int[], long[]); else, returns
70
 
     * null.  Note that when accessing the array you must
71
 
     * upgrade the type (bitwise AND with all ones), to
72
 
     * interpret the full value as unsigned.  Ie,
73
 
     * bytes[idx]&0xFF, shorts[idx]&0xFFFF, etc.
74
 
     */
75
 
    Object getArray();
76
 
 
77
 
    /**
78
 
     * Returns true if this implementation is backed by a
79
 
     * native java array.
80
 
     *
81
 
     * @see #getArray
82
 
     */
83
 
    boolean hasArray();
84
 
  }
85
 
  
86
 
  /**
87
 
   * A packed integer array that can be modified.
88
 
   * @lucene.internal
89
 
   */
90
 
  public static interface Mutable extends Reader {
91
 
    /**
92
 
     * Set the value at the given index in the array.
93
 
     * @param index where the value should be positioned.
94
 
     * @param value a value conforming to the constraints set by the array.
95
 
     */
96
 
    void set(int index, long value);
97
 
 
98
 
    /**
99
 
     * Sets all values to 0.
100
 
     */
101
 
    
102
 
    void clear();
103
 
  }
104
 
 
105
 
  /**
106
 
   * A simple base for Readers that keeps track of valueCount and bitsPerValue.
107
 
   * @lucene.internal
108
 
   */
109
 
  public static abstract class ReaderImpl implements Reader {
110
 
    protected final int bitsPerValue;
111
 
    protected final int valueCount;
112
 
 
113
 
    protected ReaderImpl(int valueCount, int bitsPerValue) {
114
 
      this.bitsPerValue = bitsPerValue;
115
 
      assert bitsPerValue > 0 && bitsPerValue <= 64 : "bitsPerValue=" + bitsPerValue;
116
 
      this.valueCount = valueCount;
117
 
    }
118
 
 
119
 
    public int getBitsPerValue() {
120
 
      return bitsPerValue;
121
 
    }
122
 
    
123
 
    public int size() {
124
 
      return valueCount;
125
 
    }
126
 
 
127
 
    public long getMaxValue() { // Convenience method
128
 
      return maxValue(bitsPerValue);
129
 
    }
130
 
 
131
 
    public Object getArray() {
132
 
      return null;
133
 
    }
134
 
 
135
 
    public boolean hasArray() {
136
 
      return false;
137
 
    }
138
 
  }
139
 
 
140
 
  /** A write-once Writer.
141
 
   * @lucene.internal
142
 
   */
143
 
  public static abstract class Writer {
144
 
    protected final DataOutput out;
145
 
    protected final int bitsPerValue;
146
 
    protected final int valueCount;
147
 
 
148
 
    protected Writer(DataOutput out, int valueCount, int bitsPerValue)
149
 
      throws IOException {
150
 
      assert bitsPerValue <= 64;
151
 
 
152
 
      this.out = out;
153
 
      this.valueCount = valueCount;
154
 
      this.bitsPerValue = bitsPerValue;
155
 
      CodecUtil.writeHeader(out, CODEC_NAME, VERSION_CURRENT);
156
 
      out.writeVInt(bitsPerValue);
157
 
      out.writeVInt(valueCount);
158
 
    }
159
 
 
160
 
    public abstract void add(long v) throws IOException;
161
 
    public abstract void finish() throws IOException;
162
 
  }
163
 
 
164
 
  /**
165
 
   * Retrieve PackedInt data from the DataInput and return a packed int
166
 
   * structure based on it.
167
 
   * @param in positioned at the beginning of a stored packed int structure.
168
 
   * @return a read only random access capable array of positive integers.
169
 
   * @throws IOException if the structure could not be retrieved.
170
 
   * @lucene.internal
171
 
   */
172
 
  public static Reader getReader(DataInput in) throws IOException {
173
 
    CodecUtil.checkHeader(in, CODEC_NAME, VERSION_START, VERSION_START);
174
 
    final int bitsPerValue = in.readVInt();
175
 
    assert bitsPerValue > 0 && bitsPerValue <= 64: "bitsPerValue=" + bitsPerValue;
176
 
    final int valueCount = in.readVInt();
177
 
 
178
 
    switch (bitsPerValue) {
179
 
    case 8:
180
 
      return new Direct8(in, valueCount);
181
 
    case 16:
182
 
      return new Direct16(in, valueCount);
183
 
    case 32:
184
 
      return new Direct32(in, valueCount);
185
 
    case 64:
186
 
      return new Direct64(in, valueCount);
187
 
    default:
188
 
      if (Constants.JRE_IS_64BIT || bitsPerValue >= 32) {
189
 
        return new Packed64(in, valueCount, bitsPerValue);
190
 
      } else {
191
 
        return new Packed32(in, valueCount, bitsPerValue);
192
 
      }
193
 
    }
194
 
  }
195
 
 
196
 
  /**
197
 
   * Create a packed integer array with the given amount of values initialized
198
 
   * to 0. the valueCount and the bitsPerValue cannot be changed after creation.
199
 
   * All Mutables known by this factory are kept fully in RAM.
200
 
   * @param valueCount   the number of elements.
201
 
   * @param bitsPerValue the number of bits available for any given value.
202
 
   * @return a mutable packed integer array.
203
 
   * @throws java.io.IOException if the Mutable could not be created. With the
204
 
   *         current implementations, this never happens, but the method
205
 
   *         signature allows for future persistence-backed Mutables.
206
 
   * @lucene.internal
207
 
   */
208
 
  public static Mutable getMutable(
209
 
         int valueCount, int bitsPerValue) {
210
 
    switch (bitsPerValue) {
211
 
    case 8:
212
 
      return new Direct8(valueCount);
213
 
    case 16:
214
 
      return new Direct16(valueCount);
215
 
    case 32:
216
 
      return new Direct32(valueCount);
217
 
    case 64:
218
 
      return new Direct64(valueCount);
219
 
    default:
220
 
      if (Constants.JRE_IS_64BIT || bitsPerValue >= 32) {
221
 
        return new Packed64(valueCount, bitsPerValue);
222
 
      } else {
223
 
        return new Packed32(valueCount, bitsPerValue);
224
 
      }
225
 
    }
226
 
  }
227
 
 
228
 
  /**
229
 
   * Create a packed integer array writer for the given number of values at the
230
 
   * given bits/value. Writers append to the given IndexOutput and has very
231
 
   * low memory overhead.
232
 
   * @param out          the destination for the produced bits.
233
 
   * @param valueCount   the number of elements.
234
 
   * @param bitsPerValue the number of bits available for any given value.
235
 
   * @return a Writer ready for receiving values.
236
 
   * @throws IOException if bits could not be written to out.
237
 
   * @lucene.internal
238
 
   */
239
 
  public static Writer getWriter(DataOutput out, int valueCount, int bitsPerValue)
240
 
    throws IOException {
241
 
    return new PackedWriter(out, valueCount, bitsPerValue);
242
 
  }
243
 
 
244
 
  /** Returns how many bits are required to hold values up
245
 
   *  to and including maxValue
246
 
   * @param maxValue the maximum value that should be representable.
247
 
   * @return the amount of bits needed to represent values from 0 to maxValue.
248
 
   * @lucene.internal
249
 
   */
250
 
  public static int bitsRequired(long maxValue) {
251
 
    // Very high long values does not translate well to double, so we do an
252
 
    // explicit check for the edge cases
253
 
    if (maxValue > 0x3FFFFFFFFFFFFFFFL) {
254
 
      return 63;
255
 
    } if (maxValue > 0x1FFFFFFFFFFFFFFFL) {
256
 
      return 62;
257
 
    }
258
 
    return Math.max(1, (int) Math.ceil(Math.log(1+maxValue)/Math.log(2.0)));
259
 
  }
260
 
 
261
 
  /**
262
 
   * Calculates the maximum unsigned long that can be expressed with the given
263
 
   * number of bits.
264
 
   * @param bitsPerValue the number of bits available for any given value.
265
 
   * @return the maximum value for the given bits.
266
 
   * @lucene.internal
267
 
   */
268
 
  public static long maxValue(int bitsPerValue) {
269
 
    return bitsPerValue == 64 ? Long.MAX_VALUE : ~(~0L << bitsPerValue);
270
 
  }
271
 
 
272
 
  /** Rounds bitsPerValue up to 8, 16, 32 or 64. */
273
 
  public static int getNextFixedSize(int bitsPerValue) {
274
 
    if (bitsPerValue <= 8) {
275
 
      return 8;
276
 
    } else if (bitsPerValue <= 16) {
277
 
      return 16;
278
 
    } else if (bitsPerValue <= 32) {
279
 
      return 32;
280
 
    } else {
281
 
      return 64;
282
 
    }
283
 
  }
284
 
 
285
 
  /** Possibly wastes some storage in exchange for faster lookups */
286
 
  public static int getRoundedFixedSize(int bitsPerValue) {
287
 
    if (bitsPerValue > 58 || (bitsPerValue < 32 && bitsPerValue > 29)) { // 10% space-waste is ok
288
 
      return getNextFixedSize(bitsPerValue);
289
 
    } else {
290
 
      return bitsPerValue;
291
 
    }
292
 
  }
293
 
}