Menu
▾
▴
[Rubyeclipse-commit] SF.net SVN: rubyeclipse: [2231] trunk/org.rubypeople.rdt.core/src/org/ rubypeople/rdt/internal/compiler/util
|
From: <caw...@us...> - 2007-03-26 19:41:21
|
Revision: 2231
http://svn.sourceforge.net/rubyeclipse/?rev=2231&view=rev
Author: cawilliams
Date: 2007-03-26 12:41:19 -0700 (Mon, 26 Mar 2007)
Log Message:
-----------
Added Paths:
-----------
trunk/org.rubypeople.rdt.core/src/org/rubypeople/rdt/internal/compiler/util/HashtableOfIntValues.java
trunk/org.rubypeople.rdt.core/src/org/rubypeople/rdt/internal/compiler/util/HashtableOfObject.java
trunk/org.rubypeople.rdt.core/src/org/rubypeople/rdt/internal/compiler/util/SimpleLookupTable.java
trunk/org.rubypeople.rdt.core/src/org/rubypeople/rdt/internal/compiler/util/SimpleSet.java
Added: trunk/org.rubypeople.rdt.core/src/org/rubypeople/rdt/internal/compiler/util/HashtableOfIntValues.java
===================================================================
--- trunk/org.rubypeople.rdt.core/src/org/rubypeople/rdt/internal/compiler/util/HashtableOfIntValues.java (rev 0)
+++ trunk/org.rubypeople.rdt.core/src/org/rubypeople/rdt/internal/compiler/util/HashtableOfIntValues.java 2007-03-26 19:41:19 UTC (rev 2231)
@@ -0,0 +1,156 @@
+/*******************************************************************************
+ * Copyright (c) 2000, 2006 IBM Corporation and others.
+ * All rights reserved. This program and the accompanying materials
+ * are made available under the terms of the Eclipse Public License v1.0
+ * which accompanies this distribution, and is available at
+ * http://www.eclipse.org/legal/epl-v10.html
+ *
+ * Contributors:
+ * IBM Corporation - initial API and implementation
+ *******************************************************************************/
+package org.rubypeople.rdt.internal.compiler.util;
+
+import org.rubypeople.rdt.internal.core.util.CharOperation;
+
+/**
+ * Hashtable of {char[] --> int}
+ */
+public final class HashtableOfIntValues implements Cloneable {
+
+ public static final int NO_VALUE = Integer.MIN_VALUE;
+
+ // to avoid using Enumerations, walk the individual tables skipping nulls
+ public char[] keyTable[];
+ public int valueTable[];
+
+ public int elementSize; // number of elements in the table
+ int threshold;
+
+ public HashtableOfIntValues() {
+ this(13);
+ }
+
+ public HashtableOfIntValues(int size) {
+
+ this.elementSize = 0;
+ this.threshold = size; // size represents the expected number of elements
+ int extraRoom = (int) (size * 1.75f);
+ if (this.threshold == extraRoom)
+ extraRoom++;
+ this.keyTable = new char[extraRoom][];
+ this.valueTable = new int[extraRoom];
+ }
+
+ public Object clone() throws CloneNotSupportedException {
+ HashtableOfIntValues result = (HashtableOfIntValues) super.clone();
+ result.elementSize = this.elementSize;
+ result.threshold = this.threshold;
+
+ int length = this.keyTable.length;
+ result.keyTable = new char[length][];
+ System.arraycopy(this.keyTable, 0, result.keyTable, 0, length);
+
+ length = this.valueTable.length;
+ result.valueTable = new int[length];
+ System.arraycopy(this.valueTable, 0, result.valueTable, 0, length);
+ return result;
+ }
+
+ public boolean containsKey(char[] key) {
+ int length = keyTable.length,
+ index = CharOperation.hashCode(key) % length;
+ int keyLength = key.length;
+ char[] currentKey;
+ while ((currentKey = keyTable[index]) != null) {
+ if (currentKey.length == keyLength && CharOperation.equals(currentKey, key))
+ return true;
+ if (++index == length) {
+ index = 0;
+ }
+ }
+ return false;
+ }
+
+ public int get(char[] key) {
+ int length = keyTable.length,
+ index = CharOperation.hashCode(key) % length;
+ int keyLength = key.length;
+ char[] currentKey;
+ while ((currentKey = keyTable[index]) != null) {
+ if (currentKey.length == keyLength && CharOperation.equals(currentKey, key))
+ return valueTable[index];
+ if (++index == length) {
+ index = 0;
+ }
+ }
+ return NO_VALUE;
+ }
+
+ public int put(char[] key, int value) {
+ int length = keyTable.length,
+ index = CharOperation.hashCode(key) % length;
+ int keyLength = key.length;
+ char[] currentKey;
+ while ((currentKey = keyTable[index]) != null) {
+ if (currentKey.length == keyLength && CharOperation.equals(currentKey, key))
+ return valueTable[index] = value;
+ if (++index == length) {
+ index = 0;
+ }
+ }
+ keyTable[index] = key;
+ valueTable[index] = value;
+
+ // assumes the threshold is never equal to the size of the table
+ if (++elementSize > threshold)
+ rehash();
+ return value;
+ }
+
+ public int removeKey(char[] key) {
+ int length = keyTable.length,
+ index = CharOperation.hashCode(key) % length;
+ int keyLength = key.length;
+ char[] currentKey;
+ while ((currentKey = keyTable[index]) != null) {
+ if (currentKey.length == keyLength && CharOperation.equals(currentKey, key)) {
+ int value = valueTable[index];
+ elementSize--;
+ keyTable[index] = null;
+ valueTable[index] = NO_VALUE;
+ rehash();
+ return value;
+ }
+ if (++index == length) {
+ index = 0;
+ }
+ }
+ return NO_VALUE;
+ }
+
+ private void rehash() {
+
+ HashtableOfIntValues newHashtable = new HashtableOfIntValues(elementSize * 2); // double the number of expected elements
+ char[] currentKey;
+ for (int i = keyTable.length; --i >= 0;)
+ if ((currentKey = keyTable[i]) != null)
+ newHashtable.put(currentKey, valueTable[i]);
+
+ this.keyTable = newHashtable.keyTable;
+ this.valueTable = newHashtable.valueTable;
+ this.threshold = newHashtable.threshold;
+ }
+
+ public int size() {
+ return elementSize;
+ }
+
+ public String toString() {
+ String s = ""; //$NON-NLS-1$
+ char[] key;
+ for (int i = 0, length = valueTable.length; i < length; i++)
+ if ((key = keyTable[i]) != null)
+ s += new String(key) + " -> " + valueTable[i] + "\n"; //$NON-NLS-2$ //$NON-NLS-1$
+ return s;
+ }
+}
Added: trunk/org.rubypeople.rdt.core/src/org/rubypeople/rdt/internal/compiler/util/HashtableOfObject.java
===================================================================
--- trunk/org.rubypeople.rdt.core/src/org/rubypeople/rdt/internal/compiler/util/HashtableOfObject.java (rev 0)
+++ trunk/org.rubypeople.rdt.core/src/org/rubypeople/rdt/internal/compiler/util/HashtableOfObject.java 2007-03-26 19:41:19 UTC (rev 2231)
@@ -0,0 +1,162 @@
+/*******************************************************************************
+ * Copyright (c) 2000, 2006 IBM Corporation and others.
+ * All rights reserved. This program and the accompanying materials
+ * are made available under the terms of the Eclipse Public License v1.0
+ * which accompanies this distribution, and is available at
+ * http://www.eclipse.org/legal/epl-v10.html
+ *
+ * Contributors:
+ * IBM Corporation - initial API and implementation
+ *******************************************************************************/
+package org.rubypeople.rdt.internal.compiler.util;
+
+import org.rubypeople.rdt.internal.core.util.CharOperation;
+
+/**
+ * Hashtable of {char[] --> Object }
+ */
+public final class HashtableOfObject implements Cloneable {
+
+ // to avoid using Enumerations, walk the individual tables skipping nulls
+ public char[] keyTable[];
+ public Object valueTable[];
+
+ public int elementSize; // number of elements in the table
+ int threshold;
+
+ public HashtableOfObject() {
+ this(13);
+ }
+
+ public HashtableOfObject(int size) {
+
+ this.elementSize = 0;
+ this.threshold = size; // size represents the expected number of elements
+ int extraRoom = (int) (size * 1.75f);
+ if (this.threshold == extraRoom)
+ extraRoom++;
+ this.keyTable = new char[extraRoom][];
+ this.valueTable = new Object[extraRoom];
+ }
+
+ public void clear() {
+ for (int i = this.keyTable.length; --i >= 0;) {
+ this.keyTable[i] = null;
+ this.valueTable[i] = null;
+ }
+ this.elementSize = 0;
+ }
+
+ public Object clone() throws CloneNotSupportedException {
+ HashtableOfObject result = (HashtableOfObject) super.clone();
+ result.elementSize = this.elementSize;
+ result.threshold = this.threshold;
+
+ int length = this.keyTable.length;
+ result.keyTable = new char[length][];
+ System.arraycopy(this.keyTable, 0, result.keyTable, 0, length);
+
+ length = this.valueTable.length;
+ result.valueTable = new Object[length];
+ System.arraycopy(this.valueTable, 0, result.valueTable, 0, length);
+ return result;
+ }
+
+ public boolean containsKey(char[] key) {
+ int length = keyTable.length,
+ index = CharOperation.hashCode(key) % length;
+ int keyLength = key.length;
+ char[] currentKey;
+ while ((currentKey = keyTable[index]) != null) {
+ if (currentKey.length == keyLength && CharOperation.equals(currentKey, key))
+ return true;
+ if (++index == length) {
+ index = 0;
+ }
+ }
+ return false;
+ }
+
+ public Object get(char[] key) {
+ int length = keyTable.length,
+ index = CharOperation.hashCode(key) % length;
+ int keyLength = key.length;
+ char[] currentKey;
+ while ((currentKey = keyTable[index]) != null) {
+ if (currentKey.length == keyLength && CharOperation.equals(currentKey, key))
+ return valueTable[index];
+ if (++index == length) {
+ index = 0;
+ }
+ }
+ return null;
+ }
+
+ public Object put(char[] key, Object value) {
+ int length = keyTable.length,
+ index = CharOperation.hashCode(key) % length;
+ int keyLength = key.length;
+ char[] currentKey;
+ while ((currentKey = keyTable[index]) != null) {
+ if (currentKey.length == keyLength && CharOperation.equals(currentKey, key))
+ return valueTable[index] = value;
+ if (++index == length) {
+ index = 0;
+ }
+ }
+ keyTable[index] = key;
+ valueTable[index] = value;
+
+ // assumes the threshold is never equal to the size of the table
+ if (++elementSize > threshold)
+ rehash();
+ return value;
+ }
+
+ public Object removeKey(char[] key) {
+ int length = keyTable.length,
+ index = CharOperation.hashCode(key) % length;
+ int keyLength = key.length;
+ char[] currentKey;
+ while ((currentKey = keyTable[index]) != null) {
+ if (currentKey.length == keyLength && CharOperation.equals(currentKey, key)) {
+ Object value = valueTable[index];
+ elementSize--;
+ keyTable[index] = null;
+ valueTable[index] = null;
+ rehash();
+ return value;
+ }
+ if (++index == length) {
+ index = 0;
+ }
+ }
+ return null;
+ }
+
+ private void rehash() {
+
+ HashtableOfObject newHashtable = new HashtableOfObject(elementSize * 2); // double the number of expected elements
+ char[] currentKey;
+ for (int i = keyTable.length; --i >= 0;)
+ if ((currentKey = keyTable[i]) != null)
+ newHashtable.put(currentKey, valueTable[i]);
+
+ this.keyTable = newHashtable.keyTable;
+ this.valueTable = newHashtable.valueTable;
+ this.threshold = newHashtable.threshold;
+ }
+
+ public int size() {
+ return elementSize;
+ }
+
+ public String toString() {
+ String s = ""; //$NON-NLS-1$
+ Object object;
+ for (int i = 0, length = valueTable.length; i < length; i++)
+ if ((object = valueTable[i]) != null)
+ s += new String(keyTable[i]) + " -> " + object.toString() + "\n"; //$NON-NLS-2$ //$NON-NLS-1$
+ return s;
+ }
+}
Added: trunk/org.rubypeople.rdt.core/src/org/rubypeople/rdt/internal/compiler/util/SimpleLookupTable.java
===================================================================
--- trunk/org.rubypeople.rdt.core/src/org/rubypeople/rdt/internal/compiler/util/SimpleLookupTable.java (rev 0)
+++ trunk/org.rubypeople.rdt.core/src/org/rubypeople/rdt/internal/compiler/util/SimpleLookupTable.java 2007-03-26 19:41:19 UTC (rev 2231)
@@ -0,0 +1,156 @@
+/*******************************************************************************
+ * Copyright (c) 2000, 2006 IBM Corporation and others.
+ * All rights reserved. This program and the accompanying materials
+ * are made available under the terms of the Eclipse Public License v1.0
+ * which accompanies this distribution, and is available at
+ * http://www.eclipse.org/legal/epl-v10.html
+ *
+ * Contributors:
+ * IBM Corporation - initial API and implementation
+ *******************************************************************************/
+package org.rubypeople.rdt.internal.compiler.util;
+
+/**
+ * A simple lookup table is a non-synchronized Hashtable, whose keys
+ * and values are Objects. It also uses linear probing to resolve collisions
+ * rather than a linked list of hash table entries.
+ */
+public final class SimpleLookupTable implements Cloneable {
+
+// to avoid using Enumerations, walk the individual tables skipping nulls
+public Object[] keyTable;
+public Object[] valueTable;
+public int elementSize; // number of elements in the table
+public int threshold;
+
+public SimpleLookupTable() {
+ this(13);
+}
+
+public SimpleLookupTable(int size) {
+ this.elementSize = 0;
+ this.threshold = size; // size represents the expected number of elements
+ int extraRoom = (int) (size * 1.5f);
+ if (this.threshold == extraRoom)
+ extraRoom++;
+ this.keyTable = new Object[extraRoom];
+ this.valueTable = new Object[extraRoom];
+}
+
+public Object clone() throws CloneNotSupportedException {
+ SimpleLookupTable result = (SimpleLookupTable) super.clone();
+ result.elementSize = this.elementSize;
+ result.threshold = this.threshold;
+
+ int length = this.keyTable.length;
+ result.keyTable = new Object[length];
+ System.arraycopy(this.keyTable, 0, result.keyTable, 0, length);
+
+ length = this.valueTable.length;
+ result.valueTable = new Object[length];
+ System.arraycopy(this.valueTable, 0, result.valueTable, 0, length);
+ return result;
+}
+
+public boolean containsKey(Object key) {
+ int length = keyTable.length;
+ int index = (key.hashCode() & 0x7FFFFFFF) % length;
+ Object currentKey;
+ while ((currentKey = keyTable[index]) != null) {
+ if (currentKey.equals(key)) return true;
+ if (++index == length) index = 0;
+ }
+ return false;
+}
+
+public Object get(Object key) {
+ int length = keyTable.length;
+ int index = (key.hashCode() & 0x7FFFFFFF) % length;
+ Object currentKey;
+ while ((currentKey = keyTable[index]) != null) {
+ if (currentKey.equals(key)) return valueTable[index];
+ if (++index == length) index = 0;
+ }
+ return null;
+}
+
+public Object keyForValue(Object valueToMatch) {
+ if (valueToMatch != null)
+ for (int i = 0, l = keyTable.length; i < l; i++)
+ if (keyTable[i] != null && valueToMatch.equals(valueTable[i]))
+ return keyTable[i];
+ return null;
+}
+
+public Object put(Object key, Object value) {
+ int length = keyTable.length;
+ int index = (key.hashCode() & 0x7FFFFFFF) % length;
+ Object currentKey;
+ while ((currentKey = keyTable[index]) != null) {
+ if (currentKey.equals(key)) return valueTable[index] = value;
+ if (++index == length) index = 0;
+ }
+ keyTable[index] = key;
+ valueTable[index] = value;
+
+ // assumes the threshold is never equal to the size of the table
+ if (++elementSize > threshold) rehash();
+ return value;
+}
+
+public Object removeKey(Object key) {
+ int length = keyTable.length;
+ int index = (key.hashCode() & 0x7FFFFFFF) % length;
+ Object currentKey;
+ while ((currentKey = keyTable[index]) != null) {
+ if (currentKey.equals(key)) {
+ elementSize--;
+ Object oldValue = valueTable[index];
+ keyTable[index] = null;
+ valueTable[index] = null;
+ if (keyTable[index + 1 == length ? 0 : index + 1] != null)
+ rehash(); // only needed if a possible collision existed
+ return oldValue;
+ }
+ if (++index == length) index = 0;
+ }
+ return null;
+}
+
+public void removeValue(Object valueToRemove) {
+ boolean rehash = false;
+ for (int i = 0, l = valueTable.length; i < l; i++) {
+ Object value = valueTable[i];
+ if (value != null && value.equals(valueToRemove)) {
+ elementSize--;
+ keyTable[i] = null;
+ valueTable[i] = null;
+ if (!rehash && keyTable[i + 1 == l ? 0 : i + 1] != null)
+ rehash = true; // only needed if a possible collision existed
+ }
+ }
+ if (rehash) rehash();
+}
+
+private void rehash() {
+ SimpleLookupTable newLookupTable = new SimpleLookupTable(elementSize * 2); // double the number of expected elements
+ Object currentKey;
+ for (int i = keyTable.length; --i >= 0;)
+ if ((currentKey = keyTable[i]) != null)
+ newLookupTable.put(currentKey, valueTable[i]);
+
+ this.keyTable = newLookupTable.keyTable;
+ this.valueTable = newLookupTable.valueTable;
+ this.elementSize = newLookupTable.elementSize;
+ this.threshold = newLookupTable.threshold;
+}
+
+public String toString() {
+ String s = ""; //$NON-NLS-1$
+ Object object;
+ for (int i = 0, l = valueTable.length; i < l; i++)
+ if ((object = valueTable[i]) != null)
+ s += keyTable[i].toString() + " -> " + object.toString() + "\n"; //$NON-NLS-2$ //$NON-NLS-1$
+ return s;
+}
+}
Added: trunk/org.rubypeople.rdt.core/src/org/rubypeople/rdt/internal/compiler/util/SimpleSet.java
===================================================================
--- trunk/org.rubypeople.rdt.core/src/org/rubypeople/rdt/internal/compiler/util/SimpleSet.java (rev 0)
+++ trunk/org.rubypeople.rdt.core/src/org/rubypeople/rdt/internal/compiler/util/SimpleSet.java 2007-03-26 19:41:19 UTC (rev 2231)
@@ -0,0 +1,126 @@
+/*******************************************************************************
+ * Copyright (c) 2000, 2006 IBM Corporation and others.
+ * All rights reserved. This program and the accompanying materials
+ * are made available under the terms of the Eclipse Public License v1.0
+ * which accompanies this distribution, and is available at
+ * http://www.eclipse.org/legal/epl-v10.html
+ *
+ * Contributors:
+ * IBM Corporation - initial API and implementation
+ *******************************************************************************/
+package org.rubypeople.rdt.internal.compiler.util;
+
+/**
+ * A simple lookup table is a non-synchronized Hashtable, whose keys
+ * and values are Objects. It also uses linear probing to resolve collisions
+ * rather than a linked list of hash table entries.
+ */
+public final class SimpleSet implements Cloneable {
+
+// to avoid using Enumerations, walk the individual values skipping nulls
+public Object[] values;
+public int elementSize; // number of elements in the table
+public int threshold;
+
+public SimpleSet() {
+ this(13);
+}
+
+public SimpleSet(int size) {
+ if (size < 3) size = 3;
+ this.elementSize = 0;
+ this.threshold = size + 1; // size is the expected number of elements
+ this.values = new Object[2 * size + 1];
+}
+
+public Object add(Object object) {
+ int length = this.values.length;
+ int index = (object.hashCode() & 0x7FFFFFFF) % length;
+ Object current;
+ while ((current = this.values[index]) != null) {
+ if (current.equals(object)) return this.values[index] = object;
+ if (++index == length) index = 0;
+ }
+ this.values[index] = object;
+
+ // assumes the threshold is never equal to the size of the table
+ if (++this.elementSize > this.threshold) rehash();
+ return object;
+}
+
+public void asArray(Object[] copy) {
+ if (this.elementSize != copy.length)
+ throw new IllegalArgumentException();
+ int index = this.elementSize;
+ for (int i = 0, l = this.values.length; i < l && index > 0; i++)
+ if (this.values[i] != null)
+ copy[--index] = this.values[i];
+}
+
+public void clear() {
+ for (int i = this.values.length; --i >= 0;)
+ this.values[i] = null;
+ this.elementSize = 0;
+}
+
+public Object clone() throws CloneNotSupportedException {
+ SimpleSet result = (SimpleSet) super.clone();
+ result.elementSize = this.elementSize;
+ result.threshold = this.threshold;
+
+ int length = this.values.length;
+ result.values = new Object[length];
+ System.arraycopy(this.values, 0, result.values, 0, length);
+ return result;
+}
+
+public boolean includes(Object object) {
+ int length = values.length;
+ int index = (object.hashCode() & 0x7FFFFFFF) % length;
+ Object current;
+ while ((current = values[index]) != null) {
+ if (current.equals(object)) return true;
+ if (++index == length) index = 0;
+ }
+ return false;
+}
+
+public Object remove(Object object) {
+ int length = values.length;
+ int index = (object.hashCode() & 0x7FFFFFFF) % length;
+ Object current;
+ while ((current = values[index]) != null) {
+ if (current.equals(object)) {
+ elementSize--;
+ Object oldValue = values[index];
+ values[index] = null;
+ if (values[index + 1 == length ? 0 : index + 1] != null)
+ rehash(); // only needed if a possible collision existed
+ return oldValue;
+ }
+ if (++index == length) index = 0;
+ }
+ return null;
+}
+
+private void rehash() {
+ SimpleSet newSet = new SimpleSet(elementSize * 2); // double the number of expected elements
+ Object current;
+ for (int i = values.length; --i >= 0;)
+ if ((current = values[i]) != null)
+ newSet.add(current);
+
+ this.values = newSet.values;
+ this.elementSize = newSet.elementSize;
+ this.threshold = newSet.threshold;
+}
+
+public String toString() {
+ String s = ""; //$NON-NLS-1$
+ Object object;
+ for (int i = 0, l = values.length; i < l; i++)
+ if ((object = values[i]) != null)
+ s += object.toString() + "\n"; //$NON-NLS-1$
+ return s;
+}
+}
This was sent by the SourceForge.net collaborative development platform, the world's largest Open Source development site.
|
