ByteArraySet.java
/*
* Copyright (C) 2009, Google Inc.
* Copyright (C) 2008, Marek Zawirski <marek.zawirski@gmail.com>
* Copyright (C) 2008, Shawn O. Pearce <spearce@spearce.org>
* Copyright (C) 2013, Robin Rosenberg and others
*
* This program and the accompanying materials are made available under the
* terms of the Eclipse Distribution License v. 1.0 which is available at
* https://www.eclipse.org/org/documents/edl-v10.php.
*
* SPDX-License-Identifier: BSD-3-Clause
*/
package org.eclipse.jgit.treewalk.filter;
import org.eclipse.jgit.util.RawParseUtils;
/**
* Specialized set for byte arrays, interpreted as strings for use in
* {@link PathFilterGroup.Group}. Most methods assume the hash is already know
* and therefore requires the caller to supply it beforehand. The implementation
* is a loose derivative of ObjectIdSubclassMap.
* <p>
* The class is only intended for use by PathFilterGroup.
* <p>
* The arrays stored may not be changed after adding.
*/
class ByteArraySet {
private int size;
private int grow;
private int mask;
private byte[][] table;
/**
* Create an empty set.
*
* @param capacity
*/
ByteArraySet(int capacity) {
initTable(1 << Integer.highestOneBit((capacity * 2) - 1));
}
private byte[] get(byte[] toFind, int length, int hash) {
final int msk = mask;
int i = hash & msk;
final byte[][] tbl = table;
byte[] obj;
while ((obj = tbl[i]) != null) {
if (equals(obj, toFind, length))
return obj;
i = (i + 1) & msk;
}
return null;
}
private static boolean equals(byte[] storedObj, byte[] toFind, int length) {
if (storedObj.length != length || toFind.length < length)
return false;
for (int i = 0; i < length; ++i) {
if (storedObj[i] != toFind[i])
return false;
}
return true;
}
/**
* Returns true if this set contains the specified array.
*
* @param toFind
* array to find.
* @param length
* The number of bytes in toFind that are used
* @param hash
* pre-computed hash of toFind
* @return true if the mapping exists for this byte array; false otherwise.
*/
boolean contains(byte[] toFind, int length, int hash) {
return get(toFind, length, hash) != null;
}
/**
* Store a byte array for future lookup.
* <p>
* Stores {@code newValue}, but only if it does not already exist in the
* set. Callers can tell if the value is new by checking the return value
* with reference equality:
*
* <pre>
* byte[] obj = ...;
* boolean wasNew = map.addIfAbsent(array, length, hash) == array;
* </pre>
*
* @param newValue
* the array to store by reference if the length is the same as
* the length parameter
* @param length
* The number of bytes in newValue that are used
* @param hash
* pre-computed hash of toFind
* @return {@code newValue} if stored, or the prior value already stored and
* that would have been returned had the caller used
* {@code get(newValue)} first.
*/
byte[] addIfAbsent(final byte[] newValue, int length, int hash) {
final int msk = mask;
int i = hash & msk;
final byte[][] tbl = table;
byte[] obj;
while ((obj = tbl[i]) != null) {
if (equals(obj, newValue, length))
return obj;
i = (i + 1) & msk;
}
byte[] valueToInsert = copyIfNotSameSize(newValue, length);
if (++size == grow) {
grow();
insert(valueToInsert, hash);
} else
tbl[i] = valueToInsert;
return valueToInsert;
}
private static byte[] copyIfNotSameSize(byte[] newValue, int length) {
if (newValue.length == length)
return newValue;
byte[] ret = new byte[length];
System.arraycopy(newValue, 0, ret, 0, length);
return ret;
}
/**
* @return number of arrays in the set
*/
int size() {
return size;
}
/** @return true if {@link #size()} is 0. */
boolean isEmpty() {
return size == 0;
}
private void insert(byte[] newValue, int hash) {
final int msk = mask;
int j = hash & msk;
final byte[][] tbl = table;
while (tbl[j] != null)
j = (j + 1) & msk;
tbl[j] = newValue;
}
private Hasher hasher = new Hasher(null, 0);
private void grow() {
final byte[][] oldTable = table;
final int oldSize = table.length;
initTable(oldSize << 1);
for (int i = 0; i < oldSize; i++) {
final byte[] obj = oldTable[i];
if (obj != null) {
hasher.init(obj, obj.length);
insert(obj, hasher.hash());
}
}
}
private void initTable(int sz) {
if (sz < 2)
sz = 2;
grow = sz >> 1;
mask = sz - 1;
table = new byte[sz][];
}
/** {@inheritDoc} */
@Override
public String toString() {
StringBuilder sb = new StringBuilder();
sb.append('[');
for (byte[] b : table) {
if (b == null)
continue;
if (sb.length() > 1)
sb.append(" , "); //$NON-NLS-1$
sb.append('"');
sb.append(RawParseUtils.decode(b));
sb.append('"');
sb.append('(');
sb.append(chainlength(b));
sb.append(')');
}
sb.append(']');
return sb.toString();
}
private int chainlength(byte[] b) {
Hasher h = new Hasher(b, b.length);
int hash = h.hash();
final int msk = mask;
int i = hash & msk;
final byte[][] tbl = table;
byte[] obj;
int n = 0;
while ((obj = tbl[i]) != null) {
if (equals(obj, b, b.length))
return n;
i = (i + 1) & msk;
++n;
}
return -1;
}
/**
* An incremental hash function.
*/
static class Hasher {
private int hash;
private int pos;
private byte[] data;
private int length;
Hasher(byte[] data, int length) {
init(data, length);
}
void init(byte[] d, int l) {
this.data = d;
this.length = l;
pos = 0;
hash = 0;
}
int hash() {
while (pos < length)
hash = hash * 31 + data[pos++];
return hash;
}
int nextHash() {
for (;;) {
hash = hash * 31 + data[pos];
++pos;
if (pos == length || data[pos] == '/')
return hash;
}
}
int getHash() {
return hash;
}
boolean hasNext() {
return pos < length;
}
public int length() {
return pos;
}
@Override
public String toString() {
StringBuilder sb = new StringBuilder();
for (int i = 0; i < pos; ++i)
sb.append((char) data[i]);
sb.append(" | "); //$NON-NLS-1$
for (int i = pos; i < length; ++i)
sb.append((char) data[i]);
return sb.toString();
}
}
byte[][] toArray() {
byte[][] ret = new byte[size][];
int i = 0;
for (byte[] entry : table) {
if (entry != null)
ret[i++] = entry;
}
return ret;
}
}