1 /*******************************************************************************
2 * Copyright (c) 2000, 2009 IBM Corporation and others.
3 *
4 * This program and the accompanying materials
5 * are made available under the terms of the Eclipse Public License 2.0
6 * which accompanies this distribution, and is available at
7 * https://www.eclipse.org/legal/epl-2.0/
8 *
9 * SPDX-License-Identifier: EPL-2.0
10 *
11 * Contributors:
12 * IBM Corporation - initial API and implementation
13 *******************************************************************************/
14 package org.eclipse.jdt.internal.compiler.util;
15
16 /**
17 * A simple lookup table is a non-synchronized Hashtable, whose keys
18 * and values are Objects. It also uses linear probing to resolve collisions
19 * rather than a linked list of hash table entries.
20 */
21 public final class SimpleSet implements Cloneable {
22
23 // to avoid using Enumerations, walk the individual values skipping nulls
24 public Object[] values;
25 public int elementSize; // number of elements in the table
26 public int threshold;
27
SimpleSet()28 public SimpleSet() {
29 this(13);
30 }
31
SimpleSet(int size)32 public SimpleSet(int size) {
33 if (size < 3) size = 3;
34 this.elementSize = 0;
35 this.threshold = size + 1; // size is the expected number of elements
36 this.values = new Object[2 * size + 1];
37 }
38
add(Object object)39 public Object add(Object object) {
40 int length = this.values.length;
41 int index = (object.hashCode() & 0x7FFFFFFF) % length;
42 Object current;
43 while ((current = this.values[index]) != null) {
44 if (current.equals(object)) return this.values[index] = object;
45 if (++index == length) index = 0;
46 }
47 this.values[index] = object;
48
49 // assumes the threshold is never equal to the size of the table
50 if (++this.elementSize > this.threshold) rehash();
51 return object;
52 }
53
addIfNotIncluded(Object object)54 public Object addIfNotIncluded(Object object) {
55 int length = this.values.length;
56 int index = (object.hashCode() & 0x7FFFFFFF) % length;
57 Object current;
58 while ((current = this.values[index]) != null) {
59 if (current.equals(object)) return null; // already existed
60 if (++index == length) index = 0;
61 }
62 this.values[index] = object;
63
64 // assumes the threshold is never equal to the size of the table
65 if (++this.elementSize > this.threshold) rehash();
66 return object;
67 }
68
asArray(Object[] copy)69 public void asArray(Object[] copy) {
70 if (this.elementSize != copy.length)
71 throw new IllegalArgumentException();
72 int index = this.elementSize;
73 for (int i = 0, l = this.values.length; i < l && index > 0; i++)
74 if (this.values[i] != null)
75 copy[--index] = this.values[i];
76 }
77
clear()78 public void clear() {
79 for (int i = this.values.length; --i >= 0;)
80 this.values[i] = null;
81 this.elementSize = 0;
82 }
83
84 @Override
clone()85 public Object clone() throws CloneNotSupportedException {
86 SimpleSet result = (SimpleSet) super.clone();
87 result.elementSize = this.elementSize;
88 result.threshold = this.threshold;
89
90 int length = this.values.length;
91 result.values = new Object[length];
92 System.arraycopy(this.values, 0, result.values, 0, length);
93 return result;
94 }
95
includes(Object object)96 public boolean includes(Object object) {
97 int length = this.values.length;
98 int index = (object.hashCode() & 0x7FFFFFFF) % length;
99 Object current;
100 while ((current = this.values[index]) != null) {
101 if (current.equals(object)) return true;
102 if (++index == length) index = 0;
103 }
104 return false;
105 }
106
remove(Object object)107 public Object remove(Object object) {
108 int length = this.values.length;
109 int index = (object.hashCode() & 0x7FFFFFFF) % length;
110 Object current;
111 while ((current = this.values[index]) != null) {
112 if (current.equals(object)) {
113 this.elementSize--;
114 Object oldValue = this.values[index];
115 this.values[index] = null;
116 if (this.values[index + 1 == length ? 0 : index + 1] != null)
117 rehash(); // only needed if a possible collision existed
118 return oldValue;
119 }
120 if (++index == length) index = 0;
121 }
122 return null;
123 }
124
rehash()125 private void rehash() {
126 SimpleSet newSet = new SimpleSet(this.elementSize * 2); // double the number of expected elements
127 Object current;
128 for (int i = this.values.length; --i >= 0;)
129 if ((current = this.values[i]) != null)
130 newSet.add(current);
131
132 this.values = newSet.values;
133 this.elementSize = newSet.elementSize;
134 this.threshold = newSet.threshold;
135 }
136
137 @Override
toString()138 public String toString() {
139 String s = ""; //$NON-NLS-1$
140 Object object;
141 for (int i = 0, l = this.values.length; i < l; i++)
142 if ((object = this.values[i]) != null)
143 s += object.toString() + "\n"; //$NON-NLS-1$
144 return s;
145 }
146 }
147