1/* 2 * Copyright (c) 2016, Oracle and/or its affiliates. All rights reserved. 3 * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER. 4 * 5 * This code is free software; you can redistribute it and/or modify it 6 * under the terms of the GNU General Public License version 2 only, as 7 * published by the Free Software Foundation. Oracle designates this 8 * particular file as subject to the "Classpath" exception as provided 9 * by Oracle in the LICENSE file that accompanied this code. 10 * 11 * This code is distributed in the hope that it will be useful, but WITHOUT 12 * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or 13 * FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License 14 * version 2 for more details (a copy is included in the LICENSE file that 15 * accompanied this code). 16 * 17 * You should have received a copy of the GNU General Public License version 18 * 2 along with this work; if not, write to the Free Software Foundation, 19 * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA. 20 * 21 * Please contact Oracle, 500 Oracle Parkway, Redwood Shores, CA 94065 USA 22 * or visit www.oracle.com if you need additional information or have any 23 * questions. 24 */ 25 26package java.util.regex; 27 28import java.util.Arrays; 29 30/** 31 * A lightweight hashset implementation for positive 'int'. Not safe for 32 * concurrent access. 33 */ 34class IntHashSet { 35 private int[] entries; 36 private int[] hashes; 37 private int pos = 0; 38 39 public IntHashSet() { 40 this.entries = new int[16 << 1]; // initCapacity = 16; 41 this.hashes = new int[(16 / 2) | 1]; // odd -> fewer collisions 42 Arrays.fill(this.entries, -1); 43 Arrays.fill(this.hashes, -1); 44 } 45 46 public boolean contains(int i) { 47 int h = hashes[i % hashes.length]; 48 while (h != -1) { 49 if (entries[h] == i) 50 return true; 51 h = entries[h + 1]; 52 } 53 return false; 54 } 55 56 public void add(int i) { 57 int h0 = i % hashes.length; 58 int next = hashes[h0]; 59 // if invoker guarantees contains(i) checked before add(i) 60 // the following check is not needed. 61 int next0 = next; 62 while (next0 != -1) { 63 if (entries[next0 ] == i) 64 return; 65 next0 = entries[next0 + 1]; 66 } 67 hashes[h0] = pos; 68 entries[pos++] = i; 69 entries[pos++] = next; 70 if (pos == entries.length) 71 expand(); 72 } 73 74 public void clear() { 75 Arrays.fill(this.entries, -1); 76 Arrays.fill(this.hashes, -1); 77 pos = 0; 78 } 79 80 private void expand() { 81 int[] old = entries; 82 int[] es = new int[old.length << 1]; 83 int hlen = (old.length / 2) | 1; 84 int[] hs = new int[hlen]; 85 Arrays.fill(es, -1); 86 Arrays.fill(hs, -1); 87 for (int n = 0; n < pos;) { // re-hashing 88 int i = old[n]; 89 int hsh = i % hlen; 90 int next = hs[hsh]; 91 hs[hsh] = n; 92 es[n++] = i; 93 es[n++] = next; 94 } 95 this.entries = es; 96 this.hashes = hs; 97 } 98} 99