+ * Note that this is an unsafe put as there's no prior verification whether + * the given key already exists in the table or not. + *
+ * @param key The key of the table entry + * @param value The value of the table entry + */ + public void putUnsafely(char[] key, Object value) { + int length = this.keyTable.length, + index = hashCode(key) % length; + while (this.keyTable[index] != null) { + if (++index == length) { + index = 0; + } + } + this.keyTable[index] = key; + this.valueTable[index] = value; + + // assumes the threshold is never equal to the size of the table + if (++this.elementSize > this.threshold) { + rehash(); + } + } + public Object removeKey(char[] key) { int length = this.keyTable.length, - index = CharOperation.hashCode(key) % length; + index = hashCode(key) % length; int keyLength = key.length; char[] currentKey; while ((currentKey = this.keyTable[index]) != null) { @@ -134,13 +177,13 @@ return null; } - private void rehash() { + protected void rehash() { HashtableOfObject newHashtable = new HashtableOfObject(this.elementSize * 2); // double the number of expected elements char[] currentKey; for (int i = this.keyTable.length; --i >= 0;) if ((currentKey = this.keyTable[i]) != null) - newHashtable.put(currentKey, this.valueTable[i]); + newHashtable.putUnsafely(currentKey, this.valueTable[i]); this.keyTable = newHashtable.keyTable; this.valueTable = newHashtable.valueTable; Index: search/org/eclipse/jdt/internal/core/index/CategoryTable.java =================================================================== RCS file: search/org/eclipse/jdt/internal/core/index/CategoryTable.java diff -N search/org/eclipse/jdt/internal/core/index/CategoryTable.java --- /dev/null 1 Jan 1970 00:00:00 -0000 +++ search/org/eclipse/jdt/internal/core/index/CategoryTable.java 1 Jan 1970 00:00:00 -0000 @@ -0,0 +1,76 @@ +/******************************************************************************* + * Copyright (c) 2000, 2010 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.eclipse.jdt.internal.core.index; + +import org.eclipse.jdt.internal.compiler.util.HashtableOfObject; + + +/** + * Hashtable of {char[] --> Object } typically used for the category table + * stored in the {@link DiskIndex disk index}. + *+ * This is a more specific {@link HashtableOfObject hashtable of objects} where + * the hash code is computed by using twice more characters than the hash + * code computation of the {@link HashtableOfObject original hashtable}. + *
+ * This is typically important for type declaration category table for which the + * key postfix might have more than 16 identical characters... + *
+ * @see "https://bugs.eclipse.org/bugs/show_bug.cgi?id=289057" + */ +public final class CategoryTable extends HashtableOfObject { + + public CategoryTable() { + super(); + } + public CategoryTable(int size) { + super(size); + } + + /* (non-Javadoc) + * + * The hash code computation is done by using half of the 32 characters last + * characters of the given array instead of only half of the 16 last ones for the + * super implementation... + * + * @see org.eclipse.jdt.internal.compiler.util.HashtableOfObject#hashCode(char[]) + */ + protected int hashCode(char[] array) { + int length = array.length; + int hash = length == 0 ? 31 : array[0]; + if (length < 16) { + for (int i = length; --i > 0;) + hash = (hash * 31) + array[i]; + } else { + // 16 characters is enough to compute a decent hash code, don't waste time examining every character + for (int i = length - 1, last = i > 32 ? i - 32 : 0; i > last; i -= 2) + hash = (hash * 31) + array[i]; + + } + return hash & 0x7FFFFFFF; + + } + + /* (non-Javadoc) + * @see org.eclipse.jdt.internal.compiler.util.HashtableOfObject#rehash() + */ + protected void rehash() { + CategoryTable newHashtable = new CategoryTable(this.elementSize * 2); // double the number of expected elements + char[] currentKey; + for (int i = this.keyTable.length; --i >= 0;) + if ((currentKey = this.keyTable[i]) != null) + newHashtable.putUnsafely(currentKey, this.valueTable[i]); + + this.keyTable = newHashtable.keyTable; + this.valueTable = newHashtable.valueTable; + this.threshold = newHashtable.threshold; + } +} Index: search/org/eclipse/jdt/internal/core/index/DiskIndex.java =================================================================== RCS file: /cvsroot/eclipse/org.eclipse.jdt.core/search/org/eclipse/jdt/internal/core/index/DiskIndex.java,v retrieving revision 1.68 diff -u -r1.68 DiskIndex.java --- search/org/eclipse/jdt/internal/core/index/DiskIndex.java 16 Jan 2009 14:29:29 -0000 1.68 +++ search/org/eclipse/jdt/internal/core/index/DiskIndex.java 9 Mar 2010 04:55:59 -0000 @@ -1,5 +1,5 @@ /******************************************************************************* - * Copyright (c) 2000, 2009 IBM Corporation and others. + * Copyright (c) 2000, 2010 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 @@ -132,14 +132,14 @@ } return results; } -private HashtableOfObject addQueryResult(HashtableOfObject results, char[] word, HashtableOfObject wordsToDocNumbers, MemoryIndex memoryIndex) throws IOException { +private HashtableOfObject addQueryResult(HashtableOfObject results, char[] word, CategoryTable wordsToDocNumbers, MemoryIndex memoryIndex) throws IOException { // must skip over documents which have been added/changed/deleted in the memory index if (results == null) results = new HashtableOfObject(13); EntryResult result = (EntryResult) results.get(word); if (memoryIndex == null) { if (result == null) - results.put(word, new EntryResult(word, wordsToDocNumbers)); + results.putUnsafely(word, new EntryResult(word, wordsToDocNumbers)); else result.addDocumentTable(wordsToDocNumbers); } else { @@ -163,7 +163,7 @@ HashtableOfObject results = null; // initialized if needed if (key == null) { for (int i = 0, l = categories.length; i < l; i++) { - HashtableOfObject wordsToDocNumbers = readCategoryTable(categories[i], true); // cache if key is null since its a definite match + CategoryTable wordsToDocNumbers = readCategoryTable(categories[i], true); // cache if key is null since its a definite match if (wordsToDocNumbers != null) { char[][] words = wordsToDocNumbers.keyTable; if (results == null) @@ -179,14 +179,14 @@ switch (matchRule) { case SearchPattern.R_EXACT_MATCH | SearchPattern.R_CASE_SENSITIVE: for (int i = 0, l = categories.length; i < l; i++) { - HashtableOfObject wordsToDocNumbers = readCategoryTable(categories[i], false); + CategoryTable wordsToDocNumbers = readCategoryTable(categories[i], false); if (wordsToDocNumbers != null && wordsToDocNumbers.containsKey(key)) results = addQueryResult(results, key, wordsToDocNumbers, memoryIndex); } break; case SearchPattern.R_PREFIX_MATCH | SearchPattern.R_CASE_SENSITIVE: for (int i = 0, l = categories.length; i < l; i++) { - HashtableOfObject wordsToDocNumbers = readCategoryTable(categories[i], false); + CategoryTable wordsToDocNumbers = readCategoryTable(categories[i], false); if (wordsToDocNumbers != null) { char[][] words = wordsToDocNumbers.keyTable; for (int j = 0, m = words.length; j < m; j++) { @@ -199,7 +199,7 @@ break; default: for (int i = 0, l = categories.length; i < l; i++) { - HashtableOfObject wordsToDocNumbers = readCategoryTable(categories[i], false); + CategoryTable wordsToDocNumbers = readCategoryTable(categories[i], false); if (wordsToDocNumbers != null) { char[][] words = wordsToDocNumbers.keyTable; for (int j = 0, m = words.length; j < m; j++) { @@ -336,9 +336,9 @@ char[] categoryName = categoryNames[i]; if (categoryName != null) { SimpleWordSet wordSet = (SimpleWordSet) wordSets[i]; - HashtableOfObject wordsToDocs = (HashtableOfObject) this.categoryTables.get(categoryName); + CategoryTable wordsToDocs = (CategoryTable) this.categoryTables.get(categoryName); if (wordsToDocs == null) - this.categoryTables.put(categoryName, wordsToDocs = new HashtableOfObject(wordSet.elementSize)); + this.categoryTables.put(categoryName, wordsToDocs = new CategoryTable(wordSet.elementSize)); char[][] words = wordSet.words; for (int j = 0, m = words.length; j < m; j++) { @@ -346,7 +346,7 @@ if (word != null) { Object o = wordsToDocs.get(word); if (o == null) { - wordsToDocs.put(word, new int[] {newPosition}); + wordsToDocs.putUnsafely(word, new int[] {newPosition}); } else if (o instanceof IntList) { ((IntList) o).add(newPosition); } else { @@ -442,11 +442,11 @@ this.categoryTables = null; } private void mergeCategory(char[] categoryName, DiskIndex onDisk, int[] positions, FileOutputStream stream) throws IOException { - HashtableOfObject wordsToDocs = (HashtableOfObject) this.categoryTables.get(categoryName); + CategoryTable wordsToDocs = (CategoryTable) this.categoryTables.get(categoryName); if (wordsToDocs == null) - wordsToDocs = new HashtableOfObject(3); + wordsToDocs = new CategoryTable(3); - HashtableOfObject oldWordsToDocs = onDisk.readCategoryTable(categoryName, true); + CategoryTable oldWordsToDocs = onDisk.readCategoryTable(categoryName, true); if (oldWordsToDocs != null) { char[][] oldWords = oldWordsToDocs.keyTable; Object[] oldArrayOffsets = oldWordsToDocs.valueTable; @@ -469,7 +469,7 @@ Object o = wordsToDocs.get(oldWord); if (o == null) { - wordsToDocs.put(oldWord, mappedNumbers); + wordsToDocs.putUnsafely(oldWord, mappedNumbers); } else { IntList list = null; if (o instanceof IntList) { @@ -580,7 +580,7 @@ this.streamBuffer = null; } } -private synchronized HashtableOfObject readCategoryTable(char[] categoryName, boolean readDocNumbers) throws IOException { +private synchronized CategoryTable readCategoryTable(char[] categoryName, boolean readDocNumbers) throws IOException { // result will be null if categoryName is unknown int offset = this.categoryOffsets.get(categoryName); if (offset == HashtableOfIntValues.NO_VALUE) { @@ -590,7 +590,7 @@ if (this.categoryTables == null) { this.categoryTables = new HashtableOfObject(3); } else { - HashtableOfObject cachedTable = (HashtableOfObject) this.categoryTables.get(categoryName); + CategoryTable cachedTable = (CategoryTable) this.categoryTables.get(categoryName); if (cachedTable != null) { if (readDocNumbers) { // must cache remaining document number arrays Object[] arrayOffsets = cachedTable.valueTable; @@ -603,7 +603,7 @@ } FileInputStream stream = new FileInputStream(this.indexFile); - HashtableOfObject categoryTable = null; + CategoryTable categoryTable = null; char[][] matchingWords = null; int count = 0; int firstOffset = -1; @@ -621,7 +621,7 @@ System.err.println("size = "+size); //$NON-NLS-1$ System.err.println("-------------------- END --------------------"); //$NON-NLS-1$ } - categoryTable = new HashtableOfObject(size); + categoryTable = new CategoryTable(size); } catch (OutOfMemoryError oom) { // DEBUG oom.printStackTrace(); @@ -641,9 +641,9 @@ // > 1 & < 256 then the size of the array is > 1 & < 256, the document array follows immediately // 256 if the array size >= 256 followed by another int which is the offset to the array (written prior to the table) if (arrayOffset <= 0) { - categoryTable.put(word, new int[] {-arrayOffset}); // store 1 element array by negating documentNumber + categoryTable.putUnsafely(word, new int[] {-arrayOffset}); // store 1 element array by negating documentNumber } else if (arrayOffset < largeArraySize) { - categoryTable.put(word, readStreamDocumentArray(stream, arrayOffset)); // read in-lined array providing size + categoryTable.putUnsafely(word, readStreamDocumentArray(stream, arrayOffset)); // read in-lined array providing size } else { arrayOffset = readStreamInt(stream); // read actual offset if (readDocNumbers) { @@ -653,7 +653,7 @@ firstOffset = arrayOffset; matchingWords[count++] = word; } - categoryTable.put(word, new Integer(arrayOffset)); // offset to array in the file + categoryTable.putUnsafely(word, new Integer(arrayOffset)); // offset to array in the file } } this.categoryTables.put(INTERNED_CATEGORY_NAMES.get(categoryName), categoryTable); @@ -1030,10 +1030,10 @@ Object[] tables = this.categoryTables.valueTable; for (int i = 0, l = categoryNames.length; i < l; i++) if (categoryNames[i] != null) - writeCategoryTable(categoryNames[i], (HashtableOfObject) tables[i], stream); + writeCategoryTable(categoryNames[i], (CategoryTable) tables[i], stream); this.categoryTables = null; } -private void writeCategoryTable(char[] categoryName, HashtableOfObject wordsToDocs, FileOutputStream stream) throws IOException { +private void writeCategoryTable(char[] categoryName, CategoryTable wordsToDocs, FileOutputStream stream) throws IOException { // the format of a category table is as follows: // any document number arrays with >= 256 elements are written before the table (the offset to each array is remembered) // then the number of word->int[] pairs in the table is written