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 

    26 package java.util.regex;

    27 

    28 import java.util.Arrays;

    29 

    30 /**

    31  * A lightweight hashset implementation for positive 'int'. Not safe for

    32  * concurrent access.

    33  */

    34 class 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 }