--- /dev/null
+package org.apache.lucene.util;
+
+/**
+ * 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 static org.apache.lucene.util.ByteBlockPool.BYTE_BLOCK_MASK;
+import static org.apache.lucene.util.ByteBlockPool.BYTE_BLOCK_SHIFT;
+import static org.apache.lucene.util.ByteBlockPool.BYTE_BLOCK_SIZE;
+
+import java.util.Arrays;
+import java.util.Comparator;
+import java.util.concurrent.atomic.AtomicLong;
+
+import org.apache.lucene.util.ByteBlockPool.DirectAllocator;
+
+/**
+ * {@link BytesRefHash} is a special purpose hash-map like data-structure
+ * optimized for {@link BytesRef} instances. BytesRefHash maintains mappings of
+ * byte arrays to ordinal (Map<BytesRef,int>) storing the hashed bytes
+ * efficiently in continuous storage. The mapping to the ordinal is
+ * encapsulated inside {@link BytesRefHash} and is guaranteed to be increased
+ * for each added {@link BytesRef}.
+ *
+ * <p>
+ * Note: The maximum capacity {@link BytesRef} instance passed to
+ * {@link #add(BytesRef)} must not be longer than {@link ByteBlockPool#BYTE_BLOCK_SIZE}-2.
+ * The internal storage is limited to 2GB total byte storage.
+ * </p>
+ *
+ * @lucene.internal
+ */
+public final class BytesRefHash {
+
+ public static final int DEFAULT_CAPACITY = 16;
+
+ // the following fields are needed by comparator,
+ // so package private to prevent access$-methods:
+ final ByteBlockPool pool;
+ int[] bytesStart;
+
+ private final BytesRef scratch1 = new BytesRef();
+ private int hashSize;
+ private int hashHalfSize;
+ private int hashMask;
+ private int count;
+ private int lastCount = -1;
+ private int[] ords;
+ private final BytesStartArray bytesStartArray;
+ private AtomicLong bytesUsed;
+
+ /**
+ * Creates a new {@link BytesRefHash} with a {@link ByteBlockPool} using a
+ * {@link DirectAllocator}.
+ */
+ public BytesRefHash() {
+ this(new ByteBlockPool(new DirectAllocator()));
+ }
+
+ /**
+ * Creates a new {@link BytesRefHash}
+ */
+ public BytesRefHash(ByteBlockPool pool) {
+ this(pool, DEFAULT_CAPACITY, new DirectBytesStartArray(DEFAULT_CAPACITY));
+ }
+
+ /**
+ * Creates a new {@link BytesRefHash}
+ */
+ public BytesRefHash(ByteBlockPool pool, int capacity,
+ BytesStartArray bytesStartArray) {
+ hashSize = capacity;
+ hashHalfSize = hashSize >> 1;
+ hashMask = hashSize - 1;
+ this.pool = pool;
+ ords = new int[hashSize];
+ Arrays.fill(ords, -1);
+ this.bytesStartArray = bytesStartArray;
+ bytesStart = bytesStartArray.init();
+ bytesUsed = bytesStartArray.bytesUsed() == null? new AtomicLong(0) : bytesStartArray.bytesUsed();;
+ bytesUsed.addAndGet(hashSize * RamUsageEstimator.NUM_BYTES_INT);
+ }
+
+ /**
+ * Returns the number of {@link BytesRef} values in this {@link BytesRefHash}.
+ *
+ * @return the number of {@link BytesRef} values in this {@link BytesRefHash}.
+ */
+ public int size() {
+ return count;
+ }
+
+ /**
+ * Populates and returns a {@link BytesRef} with the bytes for the given ord.
+ * <p>
+ * Note: the given ord must be a positive integer less that the current size (
+ * {@link #size()})
+ * </p>
+ *
+ * @param ord the ord
+ * @param ref the {@link BytesRef} to populate
+ *
+ * @return the given BytesRef instance populated with the bytes for the given ord
+ */
+ public BytesRef get(int ord, BytesRef ref) {
+ assert bytesStart != null : "bytesStart is null - not initialized";
+ assert ord < bytesStart.length: "ord exceeds byteStart len: " + bytesStart.length;
+ return pool.setBytesRef(ref, bytesStart[ord]);
+ }
+
+ /**
+ * Returns the ords array in arbitrary order. Valid ords start at offset of 0
+ * and end at a limit of {@link #size()} - 1
+ * <p>
+ * Note: This is a destructive operation. {@link #clear()} must be called in
+ * order to reuse this {@link BytesRefHash} instance.
+ * </p>
+ */
+ public int[] compact() {
+ assert bytesStart != null : "Bytesstart is null - not initialized";
+ int upto = 0;
+ for (int i = 0; i < hashSize; i++) {
+ if (ords[i] != -1) {
+ if (upto < i) {
+ ords[upto] = ords[i];
+ ords[i] = -1;
+ }
+ upto++;
+ }
+ }
+
+ assert upto == count;
+ lastCount = count;
+ return ords;
+ }
+
+ /**
+ * Returns the values array sorted by the referenced byte values.
+ * <p>
+ * Note: This is a destructive operation. {@link #clear()} must be called in
+ * order to reuse this {@link BytesRefHash} instance.
+ * </p>
+ *
+ * @param comp
+ * the {@link Comparator} used for sorting
+ */
+ public int[] sort(final Comparator<BytesRef> comp) {
+ final int[] compact = compact();
+ new SorterTemplate() {
+ @Override
+ protected void swap(int i, int j) {
+ final int o = compact[i];
+ compact[i] = compact[j];
+ compact[j] = o;
+ }
+
+ @Override
+ protected int compare(int i, int j) {
+ final int ord1 = compact[i], ord2 = compact[j];
+ assert bytesStart.length > ord1 && bytesStart.length > ord2;
+ return comp.compare(pool.setBytesRef(scratch1, bytesStart[ord1]),
+ pool.setBytesRef(scratch2, bytesStart[ord2]));
+ }
+
+ @Override
+ protected void setPivot(int i) {
+ final int ord = compact[i];
+ assert bytesStart.length > ord;
+ pool.setBytesRef(pivot, bytesStart[ord]);
+ }
+
+ @Override
+ protected int comparePivot(int j) {
+ final int ord = compact[j];
+ assert bytesStart.length > ord;
+ return comp.compare(pivot,
+ pool.setBytesRef(scratch2, bytesStart[ord]));
+ }
+
+ private final BytesRef pivot = new BytesRef(),
+ scratch1 = new BytesRef(), scratch2 = new BytesRef();
+ }.quickSort(0, count - 1);
+ return compact;
+ }
+
+ private boolean equals(int ord, BytesRef b) {
+ return pool.setBytesRef(scratch1, bytesStart[ord]).bytesEquals(b);
+ }
+
+ private boolean shrink(int targetSize) {
+ // Cannot use ArrayUtil.shrink because we require power
+ // of 2:
+ int newSize = hashSize;
+ while (newSize >= 8 && newSize / 4 > targetSize) {
+ newSize /= 2;
+ }
+ if (newSize != hashSize) {
+ bytesUsed.addAndGet(RamUsageEstimator.NUM_BYTES_INT
+ * -(hashSize - newSize));
+ hashSize = newSize;
+ ords = new int[hashSize];
+ Arrays.fill(ords, -1);
+ hashHalfSize = newSize / 2;
+ hashMask = newSize - 1;
+ return true;
+ } else {
+ return false;
+ }
+ }
+
+ /**
+ * Clears the {@link BytesRef} which maps to the given {@link BytesRef}
+ */
+ public void clear(boolean resetPool) {
+ lastCount = count;
+ count = 0;
+ if (resetPool) {
+ pool.dropBuffersAndReset();
+ }
+ bytesStart = bytesStartArray.clear();
+ if (lastCount != -1 && shrink(lastCount)) {
+ // shrink clears the hash entries
+ return;
+ }
+ Arrays.fill(ords, -1);
+ }
+
+ public void clear() {
+ clear(true);
+ }
+
+ /**
+ * Closes the BytesRefHash and releases all internally used memory
+ */
+ public void close() {
+ clear(true);
+ ords = null;
+ bytesUsed.addAndGet(RamUsageEstimator.NUM_BYTES_INT
+ * -hashSize);
+ }
+
+ /**
+ * Adds a new {@link BytesRef}
+ *
+ * @param bytes
+ * the bytes to hash
+ * @return the ord the given bytes are hashed if there was no mapping for the
+ * given bytes, otherwise <code>(-(ord)-1)</code>. This guarantees
+ * that the return value will always be >= 0 if the given bytes
+ * haven't been hashed before.
+ *
+ * @throws MaxBytesLengthExceededException
+ * if the given bytes are > 2 +
+ * {@link ByteBlockPool#BYTE_BLOCK_SIZE}
+ */
+ public int add(BytesRef bytes) {
+ return add(bytes, bytes.hashCode());
+ }
+
+ /**
+ * Adds a new {@link BytesRef} with a pre-calculated hash code.
+ *
+ * @param bytes
+ * the bytes to hash
+ * @param code
+ * the bytes hash code
+ *
+ * <p>
+ * Hashcode is defined as:
+ *
+ * <pre>
+ * int hash = 0;
+ * for (int i = offset; i < offset + length; i++) {
+ * hash = 31 * hash + bytes[i];
+ * }
+ * </pre>
+ *
+ * @return the ord the given bytes are hashed if there was no mapping for the
+ * given bytes, otherwise <code>(-(ord)-1)</code>. This guarantees
+ * that the return value will always be >= 0 if the given bytes
+ * haven't been hashed before.
+ *
+ * @throws MaxBytesLengthExceededException
+ * if the given bytes are >
+ * {@link ByteBlockPool#BYTE_BLOCK_SIZE} - 2
+ */
+ public int add(BytesRef bytes, int code) {
+ assert bytesStart != null : "Bytesstart is null - not initialized";
+ final int length = bytes.length;
+ // final position
+ int hashPos = code & hashMask;
+ int e = ords[hashPos];
+ if (e != -1 && !equals(e, bytes)) {
+ // Conflict: keep searching different locations in
+ // the hash table.
+ final int inc = ((code >> 8) + code) | 1;
+ do {
+ code += inc;
+ hashPos = code & hashMask;
+ e = ords[hashPos];
+ } while (e != -1 && !equals(e, bytes));
+ }
+
+ if (e == -1) {
+ // new entry
+ final int len2 = 2 + bytes.length;
+ if (len2 + pool.byteUpto > BYTE_BLOCK_SIZE) {
+ if (len2 > BYTE_BLOCK_SIZE) {
+ throw new MaxBytesLengthExceededException("bytes can be at most "
+ + (BYTE_BLOCK_SIZE - 2) + " in length; got " + bytes.length);
+ }
+ pool.nextBuffer();
+ }
+ final byte[] buffer = pool.buffer;
+ final int bufferUpto = pool.byteUpto;
+ if (count >= bytesStart.length) {
+ bytesStart = bytesStartArray.grow();
+ assert count < bytesStart.length + 1 : "count: " + count + " len: "
+ + bytesStart.length;
+ }
+ e = count++;
+
+ bytesStart[e] = bufferUpto + pool.byteOffset;
+
+ // We first encode the length, followed by the
+ // bytes. Length is encoded as vInt, but will consume
+ // 1 or 2 bytes at most (we reject too-long terms,
+ // above).
+ if (length < 128) {
+ // 1 byte to store length
+ buffer[bufferUpto] = (byte) length;
+ pool.byteUpto += length + 1;
+ assert length >= 0: "Length must be positive: " + length;
+ System.arraycopy(bytes.bytes, bytes.offset, buffer, bufferUpto + 1,
+ length);
+ } else {
+ // 2 byte to store length
+ buffer[bufferUpto] = (byte) (0x80 | (length & 0x7f));
+ buffer[bufferUpto + 1] = (byte) ((length >> 7) & 0xff);
+ pool.byteUpto += length + 2;
+ System.arraycopy(bytes.bytes, bytes.offset, buffer, bufferUpto + 2,
+ length);
+ }
+ assert ords[hashPos] == -1;
+ ords[hashPos] = e;
+
+ if (count == hashHalfSize) {
+ rehash(2 * hashSize, true);
+ }
+ return e;
+ }
+ return -(e + 1);
+ }
+
+ public int addByPoolOffset(int offset) {
+ assert bytesStart != null : "Bytesstart is null - not initialized";
+ // final position
+ int code = offset;
+ int hashPos = offset & hashMask;
+ int e = ords[hashPos];
+ if (e != -1 && bytesStart[e] != offset) {
+ // Conflict: keep searching different locations in
+ // the hash table.
+ final int inc = ((code >> 8) + code) | 1;
+ do {
+ code += inc;
+ hashPos = code & hashMask;
+ e = ords[hashPos];
+ } while (e != -1 && bytesStart[e] != offset);
+ }
+ if (e == -1) {
+ // new entry
+ if (count >= bytesStart.length) {
+ bytesStart = bytesStartArray.grow();
+ assert count < bytesStart.length + 1 : "count: " + count + " len: "
+ + bytesStart.length;
+ }
+ e = count++;
+ bytesStart[e] = offset;
+ assert ords[hashPos] == -1;
+ ords[hashPos] = e;
+
+ if (count == hashHalfSize) {
+ rehash(2 * hashSize, false);
+ }
+ return e;
+ }
+ return -(e + 1);
+ }
+
+ /**
+ * Called when hash is too small (> 50% occupied) or too large (< 20%
+ * occupied).
+ */
+ private void rehash(final int newSize, boolean hashOnData) {
+ final int newMask = newSize - 1;
+ bytesUsed.addAndGet(RamUsageEstimator.NUM_BYTES_INT * (newSize));
+ final int[] newHash = new int[newSize];
+ Arrays.fill(newHash, -1);
+ for (int i = 0; i < hashSize; i++) {
+ final int e0 = ords[i];
+ if (e0 != -1) {
+ int code;
+ if (hashOnData) {
+ final int off = bytesStart[e0];
+ final int start = off & BYTE_BLOCK_MASK;
+ final byte[] bytes = pool.buffers[off >> BYTE_BLOCK_SHIFT];
+ code = 0;
+ final int len;
+ int pos;
+ if ((bytes[start] & 0x80) == 0) {
+ // length is 1 byte
+ len = bytes[start];
+ pos = start + 1;
+ } else {
+ len = (bytes[start] & 0x7f) + ((bytes[start + 1] & 0xff) << 7);
+ pos = start + 2;
+ }
+
+ final int endPos = pos + len;
+ while (pos < endPos) {
+ code = BytesRef.HASH_PRIME * code + bytes[pos++];
+ }
+ } else {
+ code = bytesStart[e0];
+ }
+
+ int hashPos = code & newMask;
+ assert hashPos >= 0;
+ if (newHash[hashPos] != -1) {
+ final int inc = ((code >> 8) + code) | 1;
+ do {
+ code += inc;
+ hashPos = code & newMask;
+ } while (newHash[hashPos] != -1);
+ }
+ newHash[hashPos] = e0;
+ }
+ }
+
+ hashMask = newMask;
+ bytesUsed.addAndGet(RamUsageEstimator.NUM_BYTES_INT * (-ords.length));
+ ords = newHash;
+ hashSize = newSize;
+ hashHalfSize = newSize / 2;
+ }
+
+ /**
+ * reinitializes the {@link BytesRefHash} after a previous {@link #clear()}
+ * call. If {@link #clear()} has not been called previously this method has no
+ * effect.
+ */
+ public void reinit() {
+ if (bytesStart == null) {
+ bytesStart = bytesStartArray.init();
+ }
+
+ if (ords == null) {
+ ords = new int[hashSize];
+ bytesUsed.addAndGet(RamUsageEstimator.NUM_BYTES_INT * hashSize);
+ }
+ }
+
+ /**
+ * Returns the bytesStart offset into the internally used
+ * {@link ByteBlockPool} for the given ord
+ *
+ * @param ord
+ * the ord to look up
+ * @return the bytesStart offset into the internally used
+ * {@link ByteBlockPool} for the given ord
+ */
+ public int byteStart(int ord) {
+ assert bytesStart != null : "Bytesstart is null - not initialized";
+ assert ord >= 0 && ord < count : ord;
+ return bytesStart[ord];
+ }
+
+ /**
+ * Thrown if a {@link BytesRef} exceeds the {@link BytesRefHash} limit of
+ * {@link ByteBlockPool#BYTE_BLOCK_SIZE}-2.
+ */
+ @SuppressWarnings("serial")
+ public static class MaxBytesLengthExceededException extends RuntimeException {
+ MaxBytesLengthExceededException(String message) {
+ super(message);
+ }
+ }
+
+ public abstract static class BytesStartArray {
+ /**
+ * Initializes the BytesStartArray. This call will allocate memory
+ *
+ * @return the initialized bytes start array
+ */
+ public abstract int[] init();
+
+ /**
+ * Grows the {@link BytesStartArray}
+ *
+ * @return the grown array
+ */
+ public abstract int[] grow();
+
+ /**
+ * clears the {@link BytesStartArray} and returns the cleared instance.
+ *
+ * @return the cleared instance, this might be <code>null</code>
+ */
+ public abstract int[] clear();
+
+ /**
+ * A {@link AtomicLong} reference holding the number of bytes used by this
+ * {@link BytesStartArray}. The {@link BytesRefHash} uses this reference to
+ * track it memory usage
+ *
+ * @return a {@link AtomicLong} reference holding the number of bytes used
+ * by this {@link BytesStartArray}.
+ */
+ public abstract AtomicLong bytesUsed();
+ }
+
+ /**
+ * A direct {@link BytesStartArray} that tracks all memory allocation using an {@link AtomicLong} instance.
+ */
+ public static class TrackingDirectBytesStartArray extends BytesStartArray {
+ protected final int initSize;
+ private int[] bytesStart;
+ protected final AtomicLong bytesUsed;
+
+ public TrackingDirectBytesStartArray(int initSize, AtomicLong bytesUsed) {
+ this.initSize = initSize;
+ this.bytesUsed = bytesUsed;
+ }
+
+ @Override
+ public int[] clear() {
+ if (bytesStart != null) {
+ bytesUsed.addAndGet(-bytesStart.length * RamUsageEstimator.NUM_BYTES_INT);
+ }
+ return bytesStart = null;
+ }
+
+ @Override
+ public int[] grow() {
+ assert bytesStart != null;
+ final int oldSize = bytesStart.length;
+ bytesStart = ArrayUtil.grow(bytesStart, bytesStart.length + 1);
+ bytesUsed.addAndGet((bytesStart.length - oldSize) * RamUsageEstimator.NUM_BYTES_INT);
+ return bytesStart;
+ }
+
+ @Override
+ public int[] init() {
+ bytesStart = new int[ArrayUtil.oversize(initSize,
+ RamUsageEstimator.NUM_BYTES_INT)];
+ bytesUsed.addAndGet((bytesStart.length) * RamUsageEstimator.NUM_BYTES_INT);
+ return bytesStart;
+ }
+
+ @Override
+ public AtomicLong bytesUsed() {
+ return bytesUsed;
+ }
+ }
+
+ public static class DirectBytesStartArray extends BytesStartArray {
+ protected final int initSize;
+ private int[] bytesStart;
+ private final AtomicLong bytesUsed;
+
+ public DirectBytesStartArray(int initSize) {
+ this.bytesUsed = new AtomicLong(0);
+ this.initSize = initSize;
+ }
+
+
+ @Override
+ public int[] clear() {
+ return bytesStart = null;
+ }
+
+ @Override
+ public int[] grow() {
+ assert bytesStart != null;
+ return bytesStart = ArrayUtil.grow(bytesStart, bytesStart.length + 1);
+ }
+
+ @Override
+ public int[] init() {
+ return bytesStart = new int[ArrayUtil.oversize(initSize,
+ RamUsageEstimator.NUM_BYTES_INT)];
+ }
+
+ @Override
+ public AtomicLong bytesUsed() {
+ return bytesUsed;
+ }
+ }
+}
fnp / pylucene.git / blobdiff