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