/*
* Copyright (c) 2016, Oracle and/or its affiliates. All rights reserved.
* DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER.
*
* This code is free software; you can redistribute it and/or modify it
* under the terms of the GNU General Public License version 2 only, as
* published by the Free Software Foundation. Oracle designates this
* particular file as subject to the "Classpath" exception as provided
* by Oracle in the LICENSE file that accompanied this code.
*
* This code is distributed in the hope that it will be useful, but WITHOUT
* ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
* FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License
* version 2 for more details (a copy is included in the LICENSE file that
* accompanied this code).
*
* You should have received a copy of the GNU General Public License version
* 2 along with this work; if not, write to the Free Software Foundation,
* Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA.
*
* Please contact Oracle, 500 Oracle Parkway, Redwood Shores, CA 94065 USA
* or visit www.oracle.com if you need additional information or have any
* questions.
*/
package java.util.regex;
import java.util.Arrays;
A lightweight hashset implementation for positive 'int'. Not safe for
concurrent access.
/**
* A lightweight hashset implementation for positive 'int'. Not safe for
* concurrent access.
*/
class IntHashSet {
private int[] entries;
private int[] hashes;
private int pos = 0;
public IntHashSet() {
this.entries = new int[16 << 1]; // initCapacity = 16;
this.hashes = new int[(16 / 2) | 1]; // odd -> fewer collisions
Arrays.fill(this.entries, -1);
Arrays.fill(this.hashes, -1);
}
public boolean contains(int i) {
int h = hashes[i % hashes.length];
while (h != -1) {
if (entries[h] == i)
return true;
h = entries[h + 1];
}
return false;
}
public void add(int i) {
int h0 = i % hashes.length;
int next = hashes[h0];
// if invoker guarantees contains(i) checked before add(i)
// the following check is not needed.
int next0 = next;
while (next0 != -1) {
if (entries[next0 ] == i)
return;
next0 = entries[next0 + 1];
}
hashes[h0] = pos;
entries[pos++] = i;
entries[pos++] = next;
if (pos == entries.length)
expand();
}
public void clear() {
Arrays.fill(this.entries, -1);
Arrays.fill(this.hashes, -1);
pos = 0;
}
private void expand() {
int[] old = entries;
int[] es = new int[old.length << 1];
int hlen = (old.length / 2) | 1;
int[] hs = new int[hlen];
Arrays.fill(es, -1);
Arrays.fill(hs, -1);
for (int n = 0; n < pos;) { // re-hashing
int i = old[n];
int hsh = i % hlen;
int next = hs[hsh];
hs[hsh] = n;
es[n++] = i;
es[n++] = next;
}
this.entries = es;
this.hashes = hs;
}
}