Attachment 161407 Details for Bug 289057 – Proposed patch

[patch] Proposed patch

patch.txt (text/plain), 16.69 KB, created by Satyam Kandula

on 2010-03-09 00:03:14 EST

(hide)

Description:

Filename:

MIME Type:

Creator: Satyam Kandula

Created: 2010-03-09 00:03:14 EST

Size: 16.69 KB

patch

obsolete

>### Eclipse Workspace Patch 1.0
>#P org.eclipse.jdt.core
>Index: compiler/org/eclipse/jdt/internal/compiler/util/HashtableOfObject.java
>===================================================================
>RCS file: /cvsroot/eclipse/org.eclipse.jdt.core/compiler/org/eclipse/jdt/internal/compiler/util/HashtableOfObject.java,v
>retrieving revision 1.34
>diff -u -r1.34 HashtableOfObject.java
>--- compiler/org/eclipse/jdt/internal/compiler/util/HashtableOfObject.java	7 Mar 2009 01:08:09 -0000	1.34
>+++ compiler/org/eclipse/jdt/internal/compiler/util/HashtableOfObject.java	9 Mar 2010 04:55:56 -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
>@@ -15,14 +15,14 @@
> /**
> * Hashtable of {char[] --> Object }
> */
>-public final class HashtableOfObject implements Cloneable {
>+public 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;
>+	protected int threshold;
> 
> 	public HashtableOfObject() {
> 		this(13);
>@@ -64,7 +64,7 @@
> 
> 	public boolean containsKey(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) {
>@@ -79,7 +79,7 @@
> 
> 	public Object get(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) {
>@@ -92,9 +92,26 @@
> 		return null;
> 	}
> 
>+	/*
>+	 * This method implementation is an inline of the {@link CharOperation#hashCode(char[])} method...
>+	 */
>+	protected int hashCode(char[] key) {
>+		int length = key.length;
>+		int hash = length == 0 ? 31 : key[0];
>+		if (length < 8) {
>+			for (int i = length; --i > 0;)
>+				hash = (hash * 31) + key[i];
>+		} else {
>+			// 8 characters is enough to compute a decent hash code, don't waste time examining every character
>+			for (int i = length - 1, last = i > 16 ? i - 16 : 0; i > last; i -= 2)
>+				hash = (hash * 31) + key[i];
>+		}
>+		return hash & 0x7FFFFFFF;
>+	}
>+
> 	public Object put(char[] key, Object value) {
> 		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) {
>@@ -113,9 +130,35 @@
> 		return value;
> 	}
> 
>+	/**
>+	 * Put a value at the index of the given using the local hash code computation.
>+	 * 
>+	 * 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

Flags:

frederic_fusier: iplog+
frederic_fusier: review+

Actions: View | Diff

Attachments on bug 289057: 147120 | 147231 | 147285 | 156655 | 157871 | 158022 | 161165 | 161407