001: /*******************************************************************************
002: * Copyright (c) 2006, 2007 IBM Corporation and others.
003: * All rights reserved. This program and the accompanying materials
004: * are made available under the terms of the Eclipse Public License v1.0
005: * which accompanies this distribution, and is available at
006: * http://www.eclipse.org/legal/epl-v10.html
007: *
008: * Contributors:
009: * IBM Corporation - initial API and implementation
010: *******************************************************************************/package org.eclipse.jdt.internal.compiler.util;
011:
012: import org.eclipse.jdt.core.compiler.CharOperation;
013:
014: /**
015: * A simple lookup table is a non-synchronized Hashtable, whose keys
016: * and values are char[]. It also uses linear probing to resolve collisions
017: * rather than a linked list of hash table entries.
018: */
019: public final class SimpleSetOfCharArray implements Cloneable {
020:
021: // to avoid using Enumerations, walk the individual values skipping nulls
022: public char[][] values;
023: public int elementSize; // number of elements in the table
024: public int threshold;
025:
026: public SimpleSetOfCharArray() {
027: this (13);
028: }
029:
030: public SimpleSetOfCharArray(int size) {
031: if (size < 3)
032: size = 3;
033: this .elementSize = 0;
034: this .threshold = size + 1; // size is the expected number of elements
035: this .values = new char[2 * size + 1][];
036: }
037:
038: public Object add(char[] object) {
039: int length = this .values.length;
040: int index = (CharOperation.hashCode(object) & 0x7FFFFFFF)
041: % length;
042: char[] current;
043: while ((current = this .values[index]) != null) {
044: if (CharOperation.equals(current, object))
045: return this .values[index] = object;
046: if (++index == length)
047: index = 0;
048: }
049: this .values[index] = object;
050:
051: // assumes the threshold is never equal to the size of the table
052: if (++this .elementSize > this .threshold)
053: rehash();
054: return object;
055: }
056:
057: public void asArray(Object[] copy) {
058: if (this .elementSize != copy.length)
059: throw new IllegalArgumentException();
060: int index = this .elementSize;
061: for (int i = 0, l = this .values.length; i < l && index > 0; i++)
062: if (this .values[i] != null)
063: copy[--index] = this .values[i];
064: }
065:
066: public void clear() {
067: for (int i = this .values.length; --i >= 0;)
068: this .values[i] = null;
069: this .elementSize = 0;
070: }
071:
072: public Object clone() throws CloneNotSupportedException {
073: SimpleSetOfCharArray result = (SimpleSetOfCharArray) super
074: .clone();
075: result.elementSize = this .elementSize;
076: result.threshold = this .threshold;
077:
078: int length = this .values.length;
079: result.values = new char[length][];
080: System.arraycopy(this .values, 0, result.values, 0, length);
081: return result;
082: }
083:
084: public char[] get(char[] object) {
085: int length = this .values.length;
086: int index = (CharOperation.hashCode(object) & 0x7FFFFFFF)
087: % length;
088: char[] current;
089: while ((current = this .values[index]) != null) {
090: if (CharOperation.equals(current, object))
091: return current;
092: if (++index == length)
093: index = 0;
094: }
095: this .values[index] = object;
096:
097: // assumes the threshold is never equal to the size of the table
098: if (++this .elementSize > this .threshold)
099: rehash();
100: return object;
101: }
102:
103: public boolean includes(char[] object) {
104: int length = values.length;
105: int index = (CharOperation.hashCode(object) & 0x7FFFFFFF)
106: % length;
107: char[] current;
108: while ((current = values[index]) != null) {
109: if (CharOperation.equals(current, object))
110: return true;
111: if (++index == length)
112: index = 0;
113: }
114: return false;
115: }
116:
117: public char[] remove(char[] object) {
118: int length = values.length;
119: int index = (CharOperation.hashCode(object) & 0x7FFFFFFF)
120: % length;
121: char[] current;
122: while ((current = values[index]) != null) {
123: if (CharOperation.equals(current, object)) {
124: elementSize--;
125: char[] oldValue = values[index];
126: values[index] = null;
127: if (values[index + 1 == length ? 0 : index + 1] != null)
128: rehash(); // only needed if a possible collision existed
129: return oldValue;
130: }
131: if (++index == length)
132: index = 0;
133: }
134: return null;
135: }
136:
137: private void rehash() {
138: SimpleSetOfCharArray newSet = new SimpleSetOfCharArray(
139: elementSize * 2); // double the number of expected elements
140: char[] current;
141: for (int i = values.length; --i >= 0;)
142: if ((current = values[i]) != null)
143: newSet.add(current);
144:
145: this .values = newSet.values;
146: this .elementSize = newSet.elementSize;
147: this .threshold = newSet.threshold;
148: }
149:
150: public String toString() {
151: String s = ""; //$NON-NLS-1$
152: char[] object;
153: for (int i = 0, l = values.length; i < l; i++)
154: if ((object = values[i]) != null)
155: s += new String(object) + "\n"; //$NON-NLS-1$
156: return s;
157: }
158: }
|