Skip to main content
aboutsummaryrefslogtreecommitdiffstats
diff options
context:
space:
mode:
authorDoug Schaefer2004-05-28 20:53:35 +0000
committerDoug Schaefer2004-05-28 20:53:35 +0000
commitc839041374bf89f46fb5e19114a9a66ca27bb845 (patch)
tree120301d7ffa58a876ee55288996c8088edc69a93
parent764632f0c3a65c2f13b45146b9ae58de754acce4 (diff)
downloadorg.eclipse.cdt-c839041374bf89f46fb5e19114a9a66ca27bb845.tar.gz
org.eclipse.cdt-c839041374bf89f46fb5e19114a9a66ca27bb845.tar.xz
org.eclipse.cdt-c839041374bf89f46fb5e19114a9a66ca27bb845.zip
New character array utilities that should make things much faster, one day...
-rw-r--r--core/org.eclipse.cdt.core.tests/parser/org/eclipse/cdt/core/parser/tests/CharArrayUtilsTest.java97
-rw-r--r--core/org.eclipse.cdt.core/parser/org/eclipse/cdt/core/parser/CharArrayMap.java101
-rw-r--r--core/org.eclipse.cdt.core/parser/org/eclipse/cdt/core/parser/CharArrayPool.java121
-rw-r--r--core/org.eclipse.cdt.core/parser/org/eclipse/cdt/core/parser/CharArrayUtils.java47
4 files changed, 366 insertions, 0 deletions
diff --git a/core/org.eclipse.cdt.core.tests/parser/org/eclipse/cdt/core/parser/tests/CharArrayUtilsTest.java b/core/org.eclipse.cdt.core.tests/parser/org/eclipse/cdt/core/parser/tests/CharArrayUtilsTest.java
new file mode 100644
index 00000000000..6d7e44a0de7
--- /dev/null
+++ b/core/org.eclipse.cdt.core.tests/parser/org/eclipse/cdt/core/parser/tests/CharArrayUtilsTest.java
@@ -0,0 +1,97 @@
+/*
+ * Created on May 28, 2004
+ *
+ * TODO To change the template for this generated file go to
+ * Window - Preferences - Java - Code Style - Code Templates
+ */
+package org.eclipse.cdt.core.parser.tests;
+
+import junit.framework.TestCase;
+
+import org.eclipse.cdt.core.parser.CharArrayMap;
+import org.eclipse.cdt.core.parser.CharArrayPool;
+import org.eclipse.cdt.core.parser.CharArrayUtils;
+
+/**
+ * @author dschaefe
+ *
+ * TODO To change the template for this generated type comment go to
+ * Window - Preferences - Java - Code Style - Code Templates
+ */
+public class CharArrayUtilsTest extends TestCase {
+
+ public void testPoolAdd() {
+ CharArrayPool dict = new CharArrayPool(1);
+
+ char[] str1 = new char[] {'h', 'e', 'l', 'l', 'o'};
+ char[] str2 = dict.add(str1);
+ assertTrue(CharArrayUtils.equals(str1, str2));
+ assertNotSame(str1, str2);
+ char[] str3 = dict.add(str1);
+ assertSame(str2, str3);
+
+ char[] str4 = new char[] {'w', 'o', 'r', 'l', 'd'};
+ char[] str5 = dict.add(str4, 0, str4.length);
+ assertTrue(CharArrayUtils.equals(str4, str5));
+ assertNotSame(str4, str5);
+ char[] str6 = dict.add(str4);
+ assertSame(str5, str6);
+
+ char[] str7 = dict.add(str1, 0, str1.length);
+ assertTrue(CharArrayUtils.equals(str1, str7));
+ assertNotSame(str1, str7);
+ char[] str8 = dict.add(str1);
+ assertSame(str7, str8);
+ }
+
+ public void testPoolConflict() {
+ CharArrayPool dict = new CharArrayPool(2);
+
+ char[] str1 = new char[] {'h', 'e', 'l', 'l', 'o'};
+ char[] str2 = dict.add(str1);
+
+ // The hash algorithm should give this the same hash code
+ char[] str3 = new char[] {'h', 'o', 'l', 'l', 'e'};
+ char[] str4 = dict.add(str3);
+ assertNotSame(str2, str4);
+
+ char[] str5 = dict.add(str1);
+ assertTrue(CharArrayUtils.equals(str1, str5));
+
+ char[] str6 = new char[] {'w', 'o', 'r', 'l', 'd'};
+ char[] str7 = dict.add(str6);
+ assertTrue(CharArrayUtils.equals(str6, str7));
+
+ char[] str8 = dict.add(str3);
+ assertSame(str4, str8);
+
+ char[] str9 = dict.add(str1);
+ assertNotSame(str2, str9);
+
+ // This should be the same since the removals are done by addition time,
+ // not access time
+ char[] str10 = dict.add(str6);
+ assertSame(str7, str10);
+ }
+
+ public void testMapAdd() {
+ CharArrayMap map = new CharArrayMap(4);
+ char[] key1 = "key1".toCharArray();
+ Object value1 = new Integer(43);
+ map.put(key1, value1);
+
+ char[] key2 = "key1".toCharArray();
+ Object value2 = map.get(key2);
+ assertEquals(value1, value2);
+
+ for (int i = 0; i < 5; ++i) {
+ map.put(("ikey" + i).toCharArray(), new Integer(i));
+ }
+
+ Object ivalue1 = map.get("ikey1".toCharArray());
+ assertEquals(ivalue1, new Integer(1));
+
+ Object ivalue4 = map.get("ikey4".toCharArray());
+ assertEquals(ivalue4, new Integer(4));
+ }
+}
diff --git a/core/org.eclipse.cdt.core/parser/org/eclipse/cdt/core/parser/CharArrayMap.java b/core/org.eclipse.cdt.core/parser/org/eclipse/cdt/core/parser/CharArrayMap.java
new file mode 100644
index 00000000000..46d699c185b
--- /dev/null
+++ b/core/org.eclipse.cdt.core/parser/org/eclipse/cdt/core/parser/CharArrayMap.java
@@ -0,0 +1,101 @@
+/*
+ * Created on May 28, 2004
+ *
+ * TODO To change the template for this generated file go to
+ * Window - Preferences - Java - Code Style - Code Templates
+ */
+package org.eclipse.cdt.core.parser;
+
+/**
+ * @author dschaefe
+ *
+ * TODO To change the template for this generated type comment go to
+ * Window - Preferences - Java - Code Style - Code Templates
+ */
+public class CharArrayMap {
+
+ private char[][] keyTable;
+ private Object[] valueTable;
+ private int[] hashTable;
+ private int[] nextTable;
+
+ private int currEntry;
+
+ public CharArrayMap(int initialSize) {
+ // Make sure size is a power of two
+ int size = 1;
+ while (size < initialSize)
+ size <<= 1;
+ createTables(size);
+ }
+
+ private final void createTables(int size) {
+ keyTable = new char[size][];
+ valueTable = new Object[size];
+ nextTable = new int[size];
+ hashTable = new int[size << 1];
+ currEntry = 0;
+ }
+
+ private final int hash(char[] key) {
+ return CharArrayUtils.hash(key) & (hashTable.length - 1);
+ }
+
+ private final int add(char[] key, Object value) {
+ keyTable[currEntry] = key;
+ valueTable[currEntry] = value;
+ return ++currEntry;
+ }
+
+ // returns the overwritten object if there was one
+ public Object put(char[] key, Object value) {
+ try {
+ int hash = hash(key);
+ int i = hashTable[hash] - 1;
+ if (i < 0) {
+ // Nobody here
+ hashTable[hash] = add(key, value);
+ } else {
+ // See if the key is already defined
+ int last = i;
+ while (i >= 0) {
+ if (CharArrayUtils.equals(key, keyTable[i])) {
+ Object oldvalue = valueTable[i];
+ valueTable[i] = value;
+ // Nothing left to do, escape...
+ return oldvalue;
+ }
+ last = i;
+ i = nextTable[i] - 1;
+ }
+
+ // Not there, time to add
+ nextTable[last] = add(key, value);
+ }
+
+ return null;
+ } catch (IndexOutOfBoundsException e) {
+ // Oops, too many, resize and try again
+ char[][] oldKeyTable = keyTable;
+ Object[] oldValueTable = valueTable;
+
+ int newSize = hashTable.length << 1;
+ createTables(newSize);
+ for (int i = 0; i < oldKeyTable.length; ++i)
+ put(oldKeyTable[i], oldValueTable[i]);
+
+ return put(key, value);
+ }
+ }
+
+ public Object get(char[] key) {
+ int hash = hash(key);
+ int i = hashTable[hash] - 1;
+ while (i >= 0) {
+ if (CharArrayUtils.equals(key, keyTable[i]))
+ return valueTable[i];
+ i = nextTable[i] - 1;
+ }
+ return null;
+ }
+}
diff --git a/core/org.eclipse.cdt.core/parser/org/eclipse/cdt/core/parser/CharArrayPool.java b/core/org.eclipse.cdt.core/parser/org/eclipse/cdt/core/parser/CharArrayPool.java
new file mode 100644
index 00000000000..0a0c6453c78
--- /dev/null
+++ b/core/org.eclipse.cdt.core/parser/org/eclipse/cdt/core/parser/CharArrayPool.java
@@ -0,0 +1,121 @@
+/*
+ * Created on May 28, 2004
+ *
+ * TODO To change the template for this generated file go to
+ * Window - Preferences - Java - Code Style - Code Templates
+ */
+package org.eclipse.cdt.core.parser;
+
+/**
+ * @author dschaefe
+ *
+ * TODO To change the template for this generated type comment go to
+ * Window - Preferences - Java - Code Style - Code Templates
+ */
+public class CharArrayPool {
+
+ private int currEntry = -1;
+
+ // Hash table is twice the size of the others
+ private int[] hashTable;
+ private int[] nextTable;
+ private char[][] stringTable;
+
+ public CharArrayPool(int tableSize) {
+ // make sure size is a power of 2
+ int size = 1;
+ while (size < tableSize)
+ size <<= 1;
+
+ hashTable = new int[size << 1];
+ nextTable = new int[tableSize];
+ stringTable = new char[tableSize][];
+ }
+
+ private final int hash(char[] source, int start, int length) {
+ return CharArrayUtils.hash(source, start, length) & (hashTable.length - 1);
+ }
+
+ private static final boolean equals(char[] str1, int start, int length, char[] str2) {
+ if (str2.length != length)
+ return false;
+
+ int curr = start;
+ for (int i = 0; i < length; ++i)
+ if (str1[curr++] != str2[i])
+ return false;
+
+ return true;
+ }
+
+ private final char[] find(char[] source, int start, int length, int hash) {
+ int i = hashTable[hash] - 1;
+
+ do {
+ char[] str = stringTable[i];
+ if (equals(source, start, length, str))
+ return str;
+ i = nextTable[i] - 1;
+ } while (i >= 0);
+
+ return null;
+ }
+
+ // Removes the current entry
+ private final void remove() {
+ int hash = hash(stringTable[currEntry], 0, stringTable[currEntry].length);
+ int i = hashTable[hash] - 1;
+ if (i == currEntry)
+ // make my next the hash entry
+ hashTable[hash] = nextTable[currEntry];
+ else {
+ // remove me from the next list
+ int last;
+ do {
+ last = i;
+ i = nextTable[i] - 1;
+ } while (i != currEntry);
+
+ nextTable[last] = nextTable[currEntry];
+ }
+
+ stringTable[currEntry] = null;
+ nextTable[currEntry] = 0;
+ }
+
+ private final void addHashed(char[] str, int hash) {
+ // First remove the existing string if there is one
+ if (++currEntry == stringTable.length)
+ currEntry = 0;
+
+ if (stringTable[currEntry] != null)
+ remove();
+
+ stringTable[currEntry] = str;
+
+ // Now add it to the hash table, insert into next entries as necessary
+ if (hashTable[hash] != 0)
+ nextTable[currEntry] = hashTable[hash];
+ hashTable[hash] = currEntry + 1;
+ }
+
+ public final char[] add(char[] source, int start, int length) {
+ // do we have it already?
+ int hash = hash(source, start, length);
+ char[] result = null;
+ if (hashTable[hash] > 0)
+ result = find(source, start, length, hash);
+
+ // if not, add it
+ if (result == null) {
+ System.arraycopy(source, 0, result = new char[length], 0, length);
+ addHashed(result, hash);
+ }
+
+ return result;
+ }
+
+ public final char[] add(char[] source) {
+ return add(source, 0, source.length);
+ }
+}
diff --git a/core/org.eclipse.cdt.core/parser/org/eclipse/cdt/core/parser/CharArrayUtils.java b/core/org.eclipse.cdt.core/parser/org/eclipse/cdt/core/parser/CharArrayUtils.java
new file mode 100644
index 00000000000..028b90abb36
--- /dev/null
+++ b/core/org.eclipse.cdt.core/parser/org/eclipse/cdt/core/parser/CharArrayUtils.java
@@ -0,0 +1,47 @@
+/*
+ * Created on May 28, 2004
+ *
+ * TODO To change the template for this generated file go to
+ * Window - Preferences - Java - Code Style - Code Templates
+ */
+package org.eclipse.cdt.core.parser;
+
+/**
+ * @author dschaefe
+ *
+ * TODO To change the template for this generated type comment go to
+ * Window - Preferences - Java - Code Style - Code Templates
+ */
+public class CharArrayUtils {
+
+ public static final int hash(char[] str, int start, int length) {
+ int h = 0;
+
+ int curr = start;
+ for (int i = length; i > 0; --i, curr++)
+ h += str[curr];
+
+ return h;
+ }
+
+ public static final int hash(char[] str) {
+ return hash(str, 0, str.length);
+ }
+
+ public static final boolean equals(char[] str1, char[] str2) {
+ if (str1 == str2)
+ return true;
+
+ if (str1 == null || str2 == null)
+ return false;
+
+ if (str1.length != str2.length)
+ return false;
+
+ for (int i = 0; i < str1.length; ++i)
+ if (str1[i] != str2[i])
+ return false;
+
+ return true;
+ }
+}

Back to the top