[
Date Prev][
Date Next][
Thread Prev][
Thread Next][
Date Index][
Thread Index]
[
List Home]
|
[cdt-patch] Symbol Table storage changes
|
This table changes the symbol table to use a TreeMap instead of a HashMap
for storing its symbols. This means that the prefix lookup used by
content assist will now be O( log(n) ) instead of O( n ).
Tested on Windows.
-Andrew
Index: parser/ChangeLog-parser
===================================================================
retrieving revision 1.16
diff -u -r1.16 ChangeLog-parser
--- parser/ChangeLog-parser 9 Jan 2004 16:59:25 -0000 1.16
+++ parser/ChangeLog-parser 12 Jan 2004 22:02:11 -0000
@@ -1,3 +1,6 @@
+2004-01-12 Andrew Niefer
+ Change symbol table to use TreeMap instead of HashMap for storing its symbols to improve prefix lookup performance.
+
2004-01-08 Andrew Niefer
fixing bug 43110 - Parser support needed for functions with ellipses
Added IParameterizedSymbol.setHasVariableArgs() & hasVariableArgs()
Index: parser/org/eclipse/cdt/internal/core/parser/pst/ContainerSymbol.java
===================================================================
retrieving revision 1.6
diff -u -r1.6 ContainerSymbol.java
--- parser/org/eclipse/cdt/internal/core/parser/pst/ContainerSymbol.java 7 Jan 2004 02:00:17 -0000 1.6
+++ parser/org/eclipse/cdt/internal/core/parser/pst/ContainerSymbol.java 12 Jan 2004 22:02:13 -0000
@@ -14,6 +14,7 @@
package org.eclipse.cdt.internal.core.parser.pst;
+import java.util.Comparator;
import java.util.HashMap;
import java.util.HashSet;
import java.util.Iterator;
@@ -21,6 +22,8 @@
import java.util.List;
import java.util.ListIterator;
import java.util.Map;
+import java.util.SortedMap;
+import java.util.TreeMap;
import org.eclipse.cdt.core.parser.ast.ASTAccessVisibility;
import org.eclipse.cdt.core.parser.ast.IASTMember;
@@ -52,7 +55,7 @@
ContainerSymbol copy = (ContainerSymbol)super.clone();
copy._usingDirectives = ( _usingDirectives != null ) ? (LinkedList) _usingDirectives.clone() : null;
- copy._containedSymbols = ( _containedSymbols != null )? (HashMap) _containedSymbols.clone() : null;
+ copy._containedSymbols = ( _containedSymbols != null )? (TreeMap) _containedSymbols.clone() : null;
return copy;
}
@@ -118,7 +121,6 @@
origList.add( origDecl );
origList.add( obj );
- declarations.remove( origDecl );
declarations.put( obj.getName(), origList );
} else {
origList.add( obj );
@@ -262,9 +264,9 @@
/* (non-Javadoc)
* @see org.eclipse.cdt.internal.core.parser.pst.IContainerSymbol#getContainedSymbols()
*/
- public Map getContainedSymbols(){
+ public SortedMap getContainedSymbols(){
if( _containedSymbols == null ){
- _containedSymbols = new HashMap();
+ _containedSymbols = new TreeMap( new SymbolTableComparator() );
}
return _containedSymbols;
}
@@ -760,7 +762,6 @@
}
}
if( list.size() == 1 ){
- _context.getContainedSymbols().remove( _symbol.getName() );
_context.getContainedSymbols().put( _symbol.getName(), list.getFirst() );
}
} else if( obj instanceof BasicSymbol ){
@@ -786,8 +787,22 @@
private IContainerSymbol _decl;
private IContainerSymbol _namespace;
}
-
+
+ static protected class SymbolTableComparator implements Comparator{
+ public int compare( Object o1, Object o2 ){
+ int result = ((String) o1).compareToIgnoreCase( (String) o2 );
+ if( result == 0 ){
+ return ((String) o1).compareTo( (String) o2 );
+ }
+ return result;
+ }
+
+ public boolean equals( Object obj ){
+ return ( obj instanceof SymbolTableComparator );
+ }
+ }
+
private LinkedList _usingDirectives; //collection of nominated namespaces
- private HashMap _containedSymbols; //declarations contained by us.
+ private TreeMap _containedSymbols; //declarations contained by us.
}
Index: parser/org/eclipse/cdt/internal/core/parser/pst/IContainerSymbol.java
===================================================================
retrieving revision 1.10
diff -u -r1.10 IContainerSymbol.java
--- parser/org/eclipse/cdt/internal/core/parser/pst/IContainerSymbol.java 10 Dec 2003 00:07:26 -0000 1.10
+++ parser/org/eclipse/cdt/internal/core/parser/pst/IContainerSymbol.java 12 Jan 2004 22:02:13 -0000
@@ -17,7 +17,7 @@
package org.eclipse.cdt.internal.core.parser.pst;
import java.util.List;
-import java.util.Map;
+import java.util.SortedMap;
/**
@@ -37,7 +37,7 @@
public ISymbol addUsingDeclaration( String name ) throws ParserSymbolTableException;
public ISymbol addUsingDeclaration( String name, IContainerSymbol declContext ) throws ParserSymbolTableException;
- public Map getContainedSymbols();
+ public SortedMap getContainedSymbols();
public List prefixLookup( TypeFilter filter, String prefix, boolean qualified ) throws ParserSymbolTableException;
Index: parser/org/eclipse/cdt/internal/core/parser/pst/IParameterizedSymbol.java
===================================================================
retrieving revision 1.6
diff -u -r1.6 IParameterizedSymbol.java
--- parser/org/eclipse/cdt/internal/core/parser/pst/IParameterizedSymbol.java 9 Jan 2004 16:59:25 -0000 1.6
+++ parser/org/eclipse/cdt/internal/core/parser/pst/IParameterizedSymbol.java 12 Jan 2004 22:02:13 -0000
@@ -17,7 +17,7 @@
package org.eclipse.cdt.internal.core.parser.pst;
import java.util.List;
-import java.util.Map;
+import java.util.SortedMap;
/**
@@ -36,7 +36,7 @@
public List getArgumentList();
//public void setArgumentList( List list );
- public Map getParameterMap();
+ public SortedMap getParameterMap();
public List getParameterList();
//public void setParameterList( List list );
Index: parser/org/eclipse/cdt/internal/core/parser/pst/ParameterizedSymbol.java
===================================================================
retrieving revision 1.2
diff -u -r1.2 ParameterizedSymbol.java
--- parser/org/eclipse/cdt/internal/core/parser/pst/ParameterizedSymbol.java 9 Jan 2004 16:59:25 -0000 1.2
+++ parser/org/eclipse/cdt/internal/core/parser/pst/ParameterizedSymbol.java 12 Jan 2004 22:02:13 -0000
@@ -13,11 +13,12 @@
*/
package org.eclipse.cdt.internal.core.parser.pst;
-import java.util.HashMap;
import java.util.Iterator;
import java.util.LinkedList;
import java.util.List;
import java.util.Map;
+import java.util.SortedMap;
+import java.util.TreeMap;
import org.eclipse.cdt.internal.core.parser.pst.ParserSymbolTable.Command;
@@ -45,7 +46,7 @@
ParameterizedSymbol copy = (ParameterizedSymbol)super.clone();
copy._parameterList = ( _parameterList != null ) ? (LinkedList) _parameterList.clone() : null;
- copy._parameterMap = ( _parameterMap != null ) ? (HashMap) _parameterMap.clone() : null;
+ copy._parameterMap = ( _parameterMap != null ) ? (TreeMap) _parameterMap.clone() : null;
copy._argumentList = ( _argumentList != null ) ? (LinkedList) _argumentList.clone() : null;
copy._specializations = ( _specializations != null ) ? (LinkedList) _specializations.clone() : null;
@@ -140,9 +141,9 @@
/* (non-Javadoc)
* @see org.eclipse.cdt.internal.core.parser.pst.IParameterizedSymbol#getParameterMap()
*/
- public Map getParameterMap(){
+ public SortedMap getParameterMap(){
if( _parameterMap == null ){
- _parameterMap = new HashMap();
+ _parameterMap = new TreeMap( new SymbolTableComparator() );
}
return _parameterMap;
}
@@ -282,7 +283,7 @@
}
private LinkedList _parameterList; //have my cake
- private HashMap _parameterMap; //and eat it too
+ private TreeMap _parameterMap; //and eat it too
private LinkedList _specializations; //template specializations
private LinkedList _argumentList; //template specialization arguments
private ISymbol _returnType;
Index: parser/org/eclipse/cdt/internal/core/parser/pst/ParserSymbolTable.java
===================================================================
retrieving revision 1.33
diff -u -r1.33 ParserSymbolTable.java
--- parser/org/eclipse/cdt/internal/core/parser/pst/ParserSymbolTable.java 9 Jan 2004 16:59:25 -0000 1.33
+++ parser/org/eclipse/cdt/internal/core/parser/pst/ParserSymbolTable.java 12 Jan 2004 22:02:14 -0000
@@ -22,6 +22,7 @@
import java.util.ListIterator;
import java.util.Map;
import java.util.Set;
+import java.util.SortedMap;
import org.eclipse.cdt.core.parser.Enum;
import org.eclipse.cdt.core.parser.ParserLanguage;
@@ -302,9 +303,9 @@
data.associated.remove( lookIn );
}
- Map declarations = lookIn.getContainedSymbols();
+ SortedMap declarations = lookIn.getContainedSymbols();
- Iterator iterator = ( data.mode == LookupMode.PREFIX ) ? declarations.keySet().iterator() : null;
+ Iterator iterator = ( data.mode == LookupMode.PREFIX ) ? declarations.tailMap( data.name.toLowerCase() ).keySet().iterator() : null;
String name = ( iterator != null && iterator.hasNext() ) ? (String) iterator.next() : data.name;
while( name != null ) {
@@ -315,6 +316,8 @@
if( obj != null )
found.put( name, obj );
+ } else {
+ break;
}
if( iterator != null && iterator.hasNext() ){
@@ -329,9 +332,9 @@
}
if( lookIn instanceof IParameterizedSymbol ){
- Map parameters = ((IParameterizedSymbol)lookIn).getParameterMap();
+ SortedMap parameters = ((IParameterizedSymbol)lookIn).getParameterMap();
if( parameters != null ){
- iterator = ( data.mode == LookupMode.PREFIX ) ? parameters.keySet().iterator() : null;
+ iterator = ( data.mode == LookupMode.PREFIX ) ? parameters.tailMap( data.name.toLowerCase() ).keySet().iterator() : null;
name = ( iterator != null && iterator.hasNext() ) ? (String) iterator.next() : data.name;
while( name != null ){
if( nameMatches( data, name ) ){
@@ -340,7 +343,10 @@
if( obj != null ){
found.put( name, obj );
}
+ } else {
+ break;
}
+
if( iterator != null && iterator.hasNext() ){
name = (String) iterator.next();
} else {
