#i2800# #99677# performance: use hash maps

5 files changed, 146 insertions, 66 deletions

diff --git a/sc/inc/addincol.hxx b/sc/inc/addincol.hxx
index b555e1f44d47..23062ea22941 100644
--- a/sc/inc/addincol.hxx
+++ b/sc/inc/addincol.hxx
@@ -2,9 +2,9 @@
  *
  *  $RCSfile: addincol.hxx,v $
  *
- *  $Revision: 1.2 $
+ *  $Revision: 1.3 $
  *
- *  last change: $Author: gt $ $Date: 2001-02-13 14:37:23 $
+ *  last change: $Author: er $ $Date: 2002-11-19 22:05:18 $
  *
  *  The Contents of this file are made available subject to the terms of
  *  either of the following licenses
@@ -87,6 +87,13 @@
 #include <tools/lang.hxx>
 #endif
 
+#ifndef _RTL_USTRING_H_
+#include <rtl/ustring.h>
+#endif
+
+#include <hash_map>
+
+
 class String;
 class SfxObjectShell;
 class ScUnoAddInFuncData;
@@ -94,6 +101,16 @@ class ScMatrix;
 class ScFuncDesc;
 
 
+struct ScAddInStringHashCode
+{
+    size_t operator()( const String& rStr ) const
+    {
+        return rtl_ustr_hashCode_WithLength( rStr.GetBuffer(), rStr.Len() );
+    }
+};
+typedef ::std::hash_map< String, const ScUnoAddInFuncData*, ScAddInStringHashCode, ::std::equal_to< String > > ScAddInHashMap;
+
+
 enum ScAddInArgumentType
 {
     SC_ADDINARG_NONE,                   // -
@@ -116,6 +133,9 @@ class ScUnoAddInCollection
 private:
     long                    nFuncCount;
     ScUnoAddInFuncData**    ppFuncData;
+    ScAddInHashMap*         pExactHashMap;      // exact internal name
+    ScAddInHashMap*         pNameHashMap;       // internal name upper
+    ScAddInHashMap*         pLocalHashMap;      // localized name upper
     BOOL                    bInitialized;
 
     void        Initialize();
@@ -127,7 +147,7 @@ public:
                 ~ScUnoAddInCollection();
 
     String              FindFunction( const String& rName, BOOL bLocalFirst );  // user entered name
-    ScUnoAddInFuncData* GetFuncData( const String& rName );                     // exact name
+    const ScUnoAddInFuncData*   GetFuncData( const String& rName );             // exact name
 
     void                LocalizeString( String& rName );    // modify rName - input: exact name
 
diff --git a/sc/inc/compiler.hxx b/sc/inc/compiler.hxx
index f18f2232b7a0..2f06ee0578e0 100644
--- a/sc/inc/compiler.hxx
+++ b/sc/inc/compiler.hxx
@@ -2,9 +2,9 @@
  *
  *  $RCSfile: compiler.hxx,v $
  *
- *  $Revision: 1.12 $
+ *  $Revision: 1.13 $
  *
- *  last change: $Author: er $ $Date: 2002-09-16 12:42:35 $
+ *  last change: $Author: er $ $Date: 2002-11-19 22:06:34 $
  *
  *  The Contents of this file are made available subject to the terms of
  *  either of the following licenses
@@ -83,6 +83,7 @@
 #ifndef _RTL_USTRBUF_HXX_
 #include <rtl/ustrbuf.hxx>
 #endif
+#include <hash_map>
 
 //-----------------------------------------------
 
@@ -480,12 +481,23 @@ public:
 
 struct ScArrayStack;
 
+struct ScStringHashCode
+{
+    size_t operator()( const String& rStr ) const
+    {
+        return rtl_ustr_hashCode_WithLength( rStr.GetBuffer(), rStr.Len() );
+    }
+};
+typedef ::std::hash_map< String, OpCode, ScStringHashCode, ::std::equal_to< String > > ScOpCodeHashMap;
+
 class ScCompiler
 {
 public:
-    static String*  pSymbolTableNative;             // Liste der Symbole: String[]
-    static String*  pSymbolTableEnglish;            // Liste der Symbole English
-    static USHORT   nAnzStrings;                    // Anzahl der Symbole
+    static String*  pSymbolTableNative;             // array of native symbols, offset==OpCode
+    static String*  pSymbolTableEnglish;            // array of English symbols, offset==OpCode
+    static USHORT   nAnzStrings;                    // count of symbols
+    static ScOpCodeHashMap* pSymbolHashMapNative;   // hash map of native symbols
+    static ScOpCodeHashMap* pSymbolHashMapEnglish;  // hash map of English symbols
 private:
     static USHORT*  pCharTable;                     // char[];
     ScDocument* pDoc;
@@ -502,7 +514,8 @@ private:
     OpCode      eLastOp;
     ScToken**   pCode;
     ScArrayStack* pStack;
-    String*     pSymbolTable;               // welche SymbolTable benutzt wird
+    String*     pSymbolTable;               // which symbol table is used
+    ScOpCodeHashMap*    pSymbolHashMap;     // which symbol hash map is used
     USHORT      pc;
     short       nNumFmt;                    // bei CompileTokenArray() gesetzt
     short       nMaxTab;                    // letzte Tabelle im Doc
diff --git a/sc/source/core/tool/addincol.cxx b/sc/source/core/tool/addincol.cxx
index 7868690824c2..537b9abb13b4 100644
--- a/sc/source/core/tool/addincol.cxx
+++ b/sc/source/core/tool/addincol.cxx
@@ -2,9 +2,9 @@
  *
  *  $RCSfile: addincol.cxx,v $
  *
- *  $Revision: 1.10 $
+ *  $Revision: 1.11 $
  *
- *  last change: $Author: dr $ $Date: 2001-11-08 14:00:52 $
+ *  last change: $Author: er $ $Date: 2002-11-19 22:07:09 $
  *
  *  The Contents of this file are made available subject to the terms of
  *  either of the following licenses
@@ -149,8 +149,8 @@ private:
     long                nCallerPos;
     USHORT              nCategory;
     USHORT              nHelpId;
-    uno::Sequence<sheet::LocalizedName> aCompNames;
-    BOOL                bCompInitialized;
+    mutable uno::Sequence<sheet::LocalizedName> aCompNames;
+    mutable BOOL        bCompInitialized;
 
 public:
                 ScUnoAddInFuncData( const String& rNam, const String& rLoc,
@@ -176,7 +176,7 @@ public:
     USHORT                  GetCategory() const         { return nCategory; }
     USHORT                  GetHelpId() const           { return nHelpId; }
 
-    const uno::Sequence<sheet::LocalizedName>& GetCompNames();
+    const uno::Sequence<sheet::LocalizedName>& GetCompNames() const;
 };
 
 //------------------------------------------------------------------------
@@ -219,7 +219,7 @@ ScUnoAddInFuncData::~ScUnoAddInFuncData()
     delete[] pArgDescs;
 }
 
-const uno::Sequence<sheet::LocalizedName>& ScUnoAddInFuncData::GetCompNames()
+const uno::Sequence<sheet::LocalizedName>& ScUnoAddInFuncData::GetCompNames() const
 {
     if ( !bCompInitialized )
     {
@@ -290,12 +290,18 @@ BOOL lcl_ConvertToDouble( const uno::Any& rAny, double& rOut )
 ScUnoAddInCollection::ScUnoAddInCollection() :
     nFuncCount( 0 ),
     ppFuncData( NULL ),
+    pExactHashMap( NULL ),
+    pNameHashMap( NULL ),
+    pLocalHashMap( NULL ),
     bInitialized( FALSE )
 {
 }
 
 ScUnoAddInCollection::~ScUnoAddInCollection()
 {
+    delete pExactHashMap;
+    delete pNameHashMap;
+    delete pLocalHashMap;
     if ( ppFuncData )
     {
         for ( long i=0; i<nFuncCount; i++ )
@@ -345,7 +351,7 @@ void ScUnoAddInCollection::Initialize()
 BOOL ScUnoAddInCollection::GetExcelName( const String& rCalcName,
                                         LanguageType eDestLang, String& rRetExcelName )
 {
-    ScUnoAddInFuncData* pFuncData = GetFuncData( rCalcName );
+    const ScUnoAddInFuncData* pFuncData = GetFuncData( rCalcName );
     if ( pFuncData )
     {
         const uno::Sequence<sheet::LocalizedName>& rSequence = pFuncData->GetCompNames();
@@ -586,6 +592,14 @@ void ScUnoAddInCollection::ReadFromAddIn( const uno::Reference<uno::XInterface>&
                         else
                             ppFuncData = new ScUnoAddInFuncData*[nFuncCount];
 
+                        //! TODO: adjust bucket count?
+                        if ( !pExactHashMap )
+                            pExactHashMap = new ScAddInHashMap;
+                        if ( !pNameHashMap )
+                            pNameHashMap = new ScAddInHashMap;
+                        if ( !pLocalHashMap )
+                            pLocalHashMap = new ScAddInHashMap;
+
                         const uno::Reference<reflection::XIdlMethod>* pArray = aMethods.getConstArray();
                         for (long nFuncPos=0; nFuncPos<nNewCount; nFuncPos++)
                         {
@@ -741,6 +755,21 @@ void ScUnoAddInCollection::ReadFromAddIn( const uno::Reference<uno::XInterface>&
                                             xFunc, aObject,
                                             nVisibleCount, pVisibleArgs, nCallerPos );
 
+                                        const ScUnoAddInFuncData* pData =
+                                            ppFuncData[nFuncPos+nOld];
+                                        pExactHashMap->insert(
+                                                ScAddInHashMap::value_type(
+                                                    pData->GetOriginalName(),
+                                                    pData ) );
+                                        pNameHashMap->insert(
+                                                ScAddInHashMap::value_type(
+                                                    pData->GetUpperName(),
+                                                    pData ) );
+                                        pLocalHashMap->insert(
+                                                ScAddInHashMap::value_type(
+                                                    pData->GetUpperLocal(),
+                                                    pData ) );
+
                                         delete[] pVisibleArgs;
                                     }
                                 }
@@ -761,24 +790,22 @@ String ScUnoAddInCollection::FindFunction( const String& rName, BOOL bLocalFirst
     if (nFuncCount == 0)
         return EMPTY_STRING;
 
-    String aUpperCmp = rName;
-    ScGlobal::pCharClass->toUpper(aUpperCmp);
-    long i;
+    String aUpperCmp( ScGlobal::pCharClass->upper( rName ) );
 
     if ( bLocalFirst )
     {
         //  first scan all local names (used for entering formulas)
 
-        for (i=0; i<nFuncCount; i++)
-            if ( ppFuncData[i] && ppFuncData[i]->GetUpperLocal() == aUpperCmp )
-                return ppFuncData[i]->GetOriginalName();
+        ScAddInHashMap::const_iterator iLook( pLocalHashMap->find( aUpperCmp ) );
+        if ( iLook != pLocalHashMap->end() )
+            return iLook->second->GetOriginalName();
 
 #if 0
         //  after that, scan international names (really?)
 
-        for (i=0; i<nFuncCount; i++)
-            if ( ppFuncData[i] && ppFuncData[i]->GetUpperName() == aUpperCmp )
-                return ppFuncData[i]->GetOriginalName();
+        iLook = pNameHashMap->find( aUpperCmp );
+        if ( iLook != pNameHashMap->end() )
+            return iLook->second->GetOriginalName();
 #endif
     }
     else
@@ -786,30 +813,30 @@ String ScUnoAddInCollection::FindFunction( const String& rName, BOOL bLocalFirst
         //  first scan international names (used when calling a function)
         //! before that, check for exact match???
 
-        for (i=0; i<nFuncCount; i++)
-            if ( ppFuncData[i] && ppFuncData[i]->GetUpperName() == aUpperCmp )
-                return ppFuncData[i]->GetOriginalName();
+        ScAddInHashMap::const_iterator iLook( pNameHashMap->find( aUpperCmp ) );
+        if ( iLook != pNameHashMap->end() )
+            return iLook->second->GetOriginalName();
 
         //  after that, scan all local names (to allow replacing old AddIns with Uno)
 
-        for (i=0; i<nFuncCount; i++)
-            if ( ppFuncData[i] && ppFuncData[i]->GetUpperLocal() == aUpperCmp )
-                return ppFuncData[i]->GetOriginalName();
+        iLook = pLocalHashMap->find( aUpperCmp );
+        if ( iLook != pLocalHashMap->end() )
+            return iLook->second->GetOriginalName();
     }
 
     return EMPTY_STRING;
 }
 
-ScUnoAddInFuncData* ScUnoAddInCollection::GetFuncData( const String& rName )
+const ScUnoAddInFuncData* ScUnoAddInCollection::GetFuncData( const String& rName )
 {
     if (!bInitialized)
         Initialize();
 
     //  rName must be the exact internal name
 
-    for (long i=0; i<nFuncCount; i++)
-        if ( ppFuncData[i] && ppFuncData[i]->GetOriginalName() == rName )
-            return ppFuncData[i];
+    ScAddInHashMap::const_iterator iLook( pExactHashMap->find( rName ) );
+    if ( iLook != pExactHashMap->end() )
+        return iLook->second;
 
     return NULL;
 }
@@ -821,12 +848,9 @@ void ScUnoAddInCollection::LocalizeString( String& rName )
 
     //  modify rName - input: exact name
 
-    for (long i=0; i<nFuncCount; i++)
-        if ( ppFuncData[i] && ppFuncData[i]->GetOriginalName() == rName )
-        {
-            rName = ppFuncData[i]->GetUpperLocal();         //! upper?
-            return;
-        }
+    ScAddInHashMap::const_iterator iLook( pExactHashMap->find( rName ) );
+    if ( iLook != pExactHashMap->end() )
+        rName = iLook->second->GetUpperLocal();         //! upper?
 }
 
 
diff --git a/sc/source/core/tool/compiler.cxx b/sc/source/core/tool/compiler.cxx
index 9a0b3ae51f90..b9033fc104ba 100644
--- a/sc/source/core/tool/compiler.cxx
+++ b/sc/source/core/tool/compiler.cxx
@@ -2,9 +2,9 @@
  *
  *  $RCSfile: compiler.cxx,v $
  *
- *  $Revision: 1.34 $
+ *  $Revision: 1.35 $
  *
- *  last change: $Author: er $ $Date: 2002-11-01 18:25:38 $
+ *  last change: $Author: er $ $Date: 2002-11-19 22:07:08 $
  *
  *  The Contents of this file are made available subject to the terms of
  *  either of the following licenses
@@ -106,10 +106,12 @@
 #include "docoptio.hxx"
 
 
-String* ScCompiler::pSymbolTableNative = NULL;          // Liste der Symbole
-String* ScCompiler::pSymbolTableEnglish = NULL;         // Liste der Symbole English
-USHORT  ScCompiler::nAnzStrings = 0;                    // Anzahl der Symbole
+String* ScCompiler::pSymbolTableNative = NULL;
+String* ScCompiler::pSymbolTableEnglish = NULL;
+USHORT  ScCompiler::nAnzStrings = 0;
 USHORT* ScCompiler::pCharTable = 0;
+ScOpCodeHashMap* ScCompiler::pSymbolHashMapNative = NULL;
+ScOpCodeHashMap* ScCompiler::pSymbolHashMapEnglish = NULL;
 
 enum ScanState
 {
@@ -204,10 +206,10 @@ short lcl_GetRetFormat( OpCode eOpCode )
 class ScOpCodeList : public Resource        // temp object fuer Resource
 {
 public:
-    ScOpCodeList( USHORT, String[] );
+    ScOpCodeList( USHORT, String[], ScOpCodeHashMap& );
 };
 
-ScOpCodeList::ScOpCodeList( USHORT nRID, String pSymbolTable[] )
+ScOpCodeList::ScOpCodeList( USHORT nRID, String pSymbolTable[], ScOpCodeHashMap& rHashMap )
         :
         Resource( ScResId( nRID ) )
 {
@@ -216,7 +218,10 @@ ScOpCodeList::ScOpCodeList( USHORT nRID, String pSymbolTable[] )
         ScResId aRes(i);
         aRes.SetRT(RSC_STRING);
         if (IsAvailableRes(aRes))
+        {
             pSymbolTable[i] = aRes;
+            rHashMap.insert( ScOpCodeHashMap::value_type( pSymbolTable[i], i ) );
+        }
     }
     FreeResource();
 }
@@ -236,7 +241,9 @@ public:
 void ScCompiler::Init()
 {
     pSymbolTableNative = new String[SC_OPCODE_LAST_OPCODE_ID+1];
-    ScOpCodeList aOpCodeListNative( RID_SC_FUNCTION_NAMES, pSymbolTableNative );
+    pSymbolHashMapNative = new ScOpCodeHashMap( SC_OPCODE_LAST_OPCODE_ID+1 );
+    ScOpCodeList aOpCodeListNative( RID_SC_FUNCTION_NAMES, pSymbolTableNative,
+            *pSymbolHashMapNative );
     nAnzStrings = SC_OPCODE_LAST_OPCODE_ID+1;
 
     pCharTable = new USHORT [128];
@@ -298,6 +305,18 @@ void ScCompiler::DeInit()
         delete [] pSymbolTableEnglish;
         pSymbolTableEnglish = NULL;
     }
+    if ( pSymbolHashMapNative )
+    {
+        pSymbolHashMapNative->clear();
+        delete pSymbolHashMapNative;
+        pSymbolHashMapNative = NULL;
+    }
+    if ( pSymbolHashMapEnglish )
+    {
+        pSymbolHashMapEnglish->clear();
+        delete pSymbolHashMapEnglish;
+        pSymbolHashMapEnglish = NULL;
+    }
     delete [] pCharTable;
     pCharTable = NULL;
 }
@@ -309,13 +328,18 @@ void ScCompiler::SetCompileEnglish( BOOL bCompileEnglish )
         if ( !pSymbolTableEnglish )
         {
             pSymbolTableEnglish = new String[SC_OPCODE_LAST_OPCODE_ID+1];
+            pSymbolHashMapEnglish = new ScOpCodeHashMap( SC_OPCODE_LAST_OPCODE_ID+1 );
             ScOpCodeList aOpCodeListEnglish( RID_SC_FUNCTION_NAMES_ENGLISH,
-                pSymbolTableEnglish );
+                pSymbolTableEnglish, *pSymbolHashMapEnglish );
         }
         pSymbolTable = pSymbolTableEnglish;
+        pSymbolHashMap = pSymbolHashMapEnglish;
     }
     else
+    {
         pSymbolTable = pSymbolTableNative;
+        pSymbolHashMap = pSymbolHashMapNative;
+    }
 }
 
 //-----------------------Funktionen der Klasse ScCompiler----------------------
@@ -325,6 +349,7 @@ ScCompiler::ScCompiler( ScDocument* pDocument, const ScAddress& rPos,
         :
         aPos( rPos ),
         pSymbolTable( pSymbolTableNative ),
+        pSymbolHashMap( pSymbolHashMapNative ),
         nRecursion(0),
         bAutoCorrect( FALSE ),
         bCorrected( FALSE ),
@@ -346,6 +371,7 @@ ScCompiler::ScCompiler(ScDocument* pDocument, const ScAddress& rPos )
         :
         aPos( rPos ),
         pSymbolTable( pSymbolTableNative ),
+        pSymbolHashMap( pSymbolHashMapNative ),
         nRecursion(0),
         bAutoCorrect( FALSE ),
         bCorrected( FALSE ),
@@ -785,15 +811,12 @@ xub_StrLen ScCompiler::NextSymbol()
 
 BOOL ScCompiler::IsOpCode( const String& rName )
 {
-    BOOL bFound = FALSE;
-
-    for( USHORT i = 0; i < nAnzStrings && !bFound; i++ )
-        bFound = (pSymbolTable[i] == rName);
-
+    ScOpCodeHashMap::const_iterator iLook( pSymbolHashMap->find( rName ) );
+    BOOL bFound = (iLook != pSymbolHashMap->end());
     if (bFound)
     {
         ScRawToken aToken;
-        aToken.SetOpCode( (OpCode) --i );
+        aToken.SetOpCode( iLook->second );
         pRawToken = aToken.Clone();
     }
     else
diff --git a/sc/source/ui/unoobj/funcuno.cxx b/sc/source/ui/unoobj/funcuno.cxx
index 97a8ce41ba2e..aac06fee094b 100644
--- a/sc/source/ui/unoobj/funcuno.cxx
+++ b/sc/source/ui/unoobj/funcuno.cxx
@@ -2,9 +2,9 @@
  *
  *  $RCSfile: funcuno.cxx,v $
  *
- *  $Revision: 1.6 $
+ *  $Revision: 1.7 $
  *
- *  last change: $Author: nn $ $Date: 2001-06-06 18:17:27 $
+ *  last change: $Author: er $ $Date: 2002-11-19 22:08:22 $
  *
  *  The Contents of this file are made available subject to the terms of
  *  either of the following licenses
@@ -358,16 +358,16 @@ BOOL lcl_AddFunctionToken( ScTokenArray& rArray, const rtl::OUString& rName )
     // same options as in ScCompiler::IsOpCode:
     // 1. built-in function name
 
-    DBG_ASSERT( ScCompiler::pSymbolTableEnglish, "no symbol table" );
-    if (!ScCompiler::pSymbolTableEnglish)
+    DBG_ASSERT( ScCompiler::pSymbolHashMapEnglish, "no symbol hash map" );
+    if (!ScCompiler::pSymbolHashMapEnglish)
         return FALSE;
 
-    for ( USHORT nPos=0; nPos<ScCompiler::nAnzStrings; nPos++ )
-        if ( ScCompiler::pSymbolTableEnglish[nPos] == aUpper )
-        {
-            rArray.AddOpCode( (OpCode) nPos );
-            return TRUE;
-        }
+    ScOpCodeHashMap::const_iterator iLook( ScCompiler::pSymbolHashMapEnglish->find( aUpper ) );
+    if ( iLook != ScCompiler::pSymbolHashMapEnglish->end() )
+    {
+        rArray.AddOpCode( iLook->second );
+        return TRUE;
+    }
 
     // 2. old add in functions