[PATCH] Speed up range name lookup by index.

[Kohei Yoshida]

This should speed up formula calculations considerably during xls
import since shared formulas are also stored in ScRangeName and
they are looked up by index. (bnc#715104)
---
 sc/inc/rangenam.hxx              |   10 ++++++++
 sc/source/core/tool/rangenam.cxx |   45 +++++++++++++++++++++++++++-----------
 2 files changed, 42 insertions(+), 13 deletions(-)

diff --git a/sc/inc/rangenam.hxx b/sc/inc/rangenam.hxx
index 21cf333..e3b1785 100644
--- a/sc/inc/rangenam.hxx
+++ b/sc/inc/rangenam.hxx
@@ -36,6 +36,7 @@
 #include "scdllapi.h"
 
 #include <map>
+#include <vector>
 #include <boost/ptr_container/ptr_set.hpp>
 #include <boost/ptr_container/ptr_map.hpp>
 
@@ -179,8 +180,10 @@ bool operator< (const ScRangeData& left, const ScRangeData& right);
 class ScRangeName
 {
 private:
+    typedef std::vector<ScRangeData*> IndexDataType;
     typedef ::boost::ptr_set<ScRangeData> DataType;
     DataType maData;
+    IndexDataType maIndexToData;
 
 public:
     /// Map that manages stored ScRangeName instances.
@@ -215,7 +218,14 @@ public:
     SC_DLLPUBLIC size_t size() const;
     bool empty() const;
     SC_DLLPUBLIC bool insert(ScRangeData* p);
+
     void erase(const ScRangeData& r);
+
+    /**
+     * Erase by iterator position.  Note that this method doesn't check for
+     * iterator's validity.  The caller must make sure that the iterator is
+     * valid.
+     */
     void erase(const iterator& itr);
     void clear();
     bool operator== (const ScRangeName& r) const;
diff --git a/sc/source/core/tool/rangenam.cxx b/sc/source/core/tool/rangenam.cxx
index efad9fe..599590a 100644
--- a/sc/source/core/tool/rangenam.cxx
+++ b/sc/source/core/tool/rangenam.cxx
@@ -735,7 +735,7 @@ void ScRangeName::copyLocalNames(const TabNameMap& rNames, TabNameCopyMap& rCopy
 ScRangeName::ScRangeName() {}
 
 ScRangeName::ScRangeName(const ScRangeName& r) :
-    maData(r.maData) {}
+    maData(r.maData), maIndexToData(r.maIndexToData) {}
 
 const ScRangeData* ScRangeName::findByRange(const ScRange& rRange) const
 {
@@ -774,9 +774,12 @@ const ScRangeData* ScRangeName::findByUpperName(const OUString& rName) const
 
 ScRangeData* ScRangeName::findByIndex(sal_uInt16 i)
 {
-    DataType::iterator itr = std::find_if(
-        maData.begin(), maData.end(), MatchByIndex(i));
-    return itr == maData.end() ? NULL : &(*itr);
+    if (!i)
+        // index should never be zero.
+        return NULL;
+
+    size_t nPos = i - 1;
+    return nPos < maIndexToData.size() ? maIndexToData[nPos] : NULL;
 }
 
 void ScRangeName::UpdateReference(
@@ -845,35 +848,51 @@ bool ScRangeName::insert(ScRangeData* p)
 
     if (!p->GetIndex())
     {
-        // Assign a new index.  An index must be unique.
-        sal_uInt16 nHigh = 0;
-        DataType::const_iterator itr = maData.begin(), itrEnd = maData.end();
-        for (; itr != itrEnd; ++itr)
+        // Assign a new index.  An index must be unique and is never 0.
+        IndexDataType::iterator itr = std::find(
+            maIndexToData.begin(), maIndexToData.end(), static_cast<ScRangeData*>(NULL));
+        if (itr != maIndexToData.end())
         {
-            sal_uInt16 n = itr->GetIndex();
-            if (n > nHigh)
-                nHigh = n;
+            // Empty slot exists.  Re-use it.
+            size_t nPos = std::distance(maIndexToData.begin(), itr);
+            p->SetIndex(nPos + 1);
         }
-        p->SetIndex(nHigh + 1);
+        else
+            // No empty slot.  Append it to the end.
+            p->SetIndex(maIndexToData.size() + 1);
     }
 
     pair<DataType::iterator, bool> r = maData.insert(p);
+    if (r.second)
+    {
+        // Data inserted.  Store its index for mapping.
+        size_t nPos = p->GetIndex() - 1;
+        if (nPos >= maIndexToData.size())
+            maIndexToData.resize(nPos+1, NULL);
+        maIndexToData[nPos] = p;
+    }
     return r.second;
 }
 
 void ScRangeName::erase(const ScRangeData& r)
 {
-    maData.erase(r);
+    DataType::iterator itr = maData.find(r);
+    if (itr != maData.end())
+        erase(itr);
 }
 
 void ScRangeName::erase(const iterator& itr)
 {
+    sal_uInt16 nIndex = itr->GetIndex();
     maData.erase(itr);
+    if (nIndex < maIndexToData.size())
+        maIndexToData[nIndex] = NULL;
 }
 
 void ScRangeName::clear()
 {
     maData.clear();
+    maIndexToData.clear();
 }
 
 bool ScRangeName::operator== (const ScRangeName& r) const
-- 
1.7.3.4


--=-nmVPkhAZqR/Yxj03yskK--