Debian Codegraph @

src/main/java/io/reactivex/rxjava3/internal/util/OpenHashSet.java

raw
1 /*
2 * Copyright (c) 2016-present, RxJava Contributors.
3 *
4 * Licensed under the Apache License, Version 2.0 (the "License"); you may not use this file except in
5 * compliance with the License. You may obtain a copy of the License at
6 *
7 * http://www.apache.org/licenses/LICENSE-2.0
8 *
9 * Unless required by applicable law or agreed to in writing, software distributed under the License is
10 * distributed on an "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. See
11 * the License for the specific language governing permissions and limitations under the License.
12 */
13
14 /*
15 * Inspired by fastutils' OpenHashSet implementation at
16 * https://github.com/vigna/fastutil/blob/master/drv/OpenHashSet.drv
17 */
18
19 package io.reactivex.rxjava3.internal.util;
20
21 /**
22 * A simple open hash set with add, remove and clear capabilities only.
23 * <p>Doesn't support nor checks for {@code null}s.
24 *
25 * @param <T> the element type
26 */
27 public final class OpenHashSet<T> {
28 private static final int INT_PHI = 0x9E3779B9;
29
30 final float loadFactor;
31 int mask;
32 int size;
33 int maxSize;
34 T[] keys;
35
36 public OpenHashSet() {
37 this(16, 0.75f);
38 }
39
40 /**
41 * Creates an OpenHashSet with the initial capacity and load factor of 0.75f.
42 * @param capacity the initial capacity
43 */
44 public OpenHashSet(int capacity) {
45 this(capacity, 0.75f);
46 }
47
48 @SuppressWarnings("unchecked")
49 public OpenHashSet(int capacity, float loadFactor) {
50 this.loadFactor = loadFactor;
51 int c = Pow2.roundToPowerOfTwo(capacity);
52 this.mask = c - 1;
53 this.maxSize = (int)(loadFactor * c);
54 this.keys = (T[])new Object[c];
55 }
56
57 public boolean add(T value) {
58 final T[] a = keys;
59 final int m = mask;
60
61 int pos = mix(value.hashCode()) & m;
62 T curr = a[pos];
63 if (curr != null) {
64 if (curr.equals(value)) {
65 return false;
66 }
67 for (;;) {
68 pos = (pos + 1) & m;
69 curr = a[pos];
70 if (curr == null) {
71 break;
72 }
73 if (curr.equals(value)) {
74 return false;
75 }
76 }
77 }
78 a[pos] = value;
79 if (++size >= maxSize) {
80 rehash();
81 }
82 return true;
83 }
84 public boolean remove(T value) {
85 T[] a = keys;
86 int m = mask;
87 int pos = mix(value.hashCode()) & m;
88 T curr = a[pos];
89 if (curr == null) {
90 return false;
91 }
92 if (curr.equals(value)) {
93 return removeEntry(pos, a, m);
94 }
95 for (;;) {
96 pos = (pos + 1) & m;
97 curr = a[pos];
98 if (curr == null) {
99 return false;
100 }
101 if (curr.equals(value)) {
102 return removeEntry(pos, a, m);
103 }
104 }
105 }
106
107 boolean removeEntry(int pos, T[] a, int m) {
108 size--;
109
110 int last;
111 int slot;
112 T curr;
113 for (;;) {
114 last = pos;
115 pos = (pos + 1) & m;
116 for (;;) {
117 curr = a[pos];
118 if (curr == null) {
119 a[last] = null;
120 return true;
121 }
122 slot = mix(curr.hashCode()) & m;
123
124 if (last <= pos ? last >= slot || slot > pos : last >= slot && slot > pos) {
125 break;
126 }
127
128 pos = (pos + 1) & m;
129 }
130 a[last] = curr;
131 }
132 }
133
134 @SuppressWarnings("unchecked")
135 void rehash() {
136 T[] a = keys;
137 int i = a.length;
138 int newCap = i << 1;
139 int m = newCap - 1;
140
141 T[] b = (T[])new Object[newCap];
142
143 for (int j = size; j-- != 0; ) {
144 while (a[--i] == null) { } // NOPMD
145 int pos = mix(a[i].hashCode()) & m;
146 if (b[pos] != null) {
147 for (;;) {
148 pos = (pos + 1) & m;
149 if (b[pos] == null) {
150 break;
151 }
152 }
153 }
154 b[pos] = a[i];
155 }
156
157 this.mask = m;
158 this.maxSize = (int)(newCap * loadFactor);
159 this.keys = b;
160 }
161
162 static int mix(int x) {
163 final int h = x * INT_PHI;
164 return h ^ (h >>> 16);
165 }
166
167 public Object[] keys() {
168 return keys; // NOPMD
169 }
170
171 public int size() {
172 return size;
173 }
174 }