diff options
author | Doug Schaefer | 2004-05-28 20:53:35 +0000 |
---|---|---|
committer | Doug Schaefer | 2004-05-28 20:53:35 +0000 |
commit | c839041374bf89f46fb5e19114a9a66ca27bb845 (patch) | |
tree | 120301d7ffa58a876ee55288996c8088edc69a93 | |
parent | 764632f0c3a65c2f13b45146b9ae58de754acce4 (diff) | |
download | org.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...
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; + } +} |