wxFileConfig uses sorted arrays (big performance improvement)

git-svn-id: https://svn.wxwidgets.org/svn/wx/wxWidgets/trunk@281 c3d73ce0-8a6f-49c7-b76d-6d57e0e08775

diff --git a/include/wx/fileconf.h b/include/wx/fileconf.h
index 84a12b4754fa8a91c52a82c34e894aa6bbc92ab2..e499328236c29a4865a5726a35786ea5a542a7f7 100644 (file)
--- a/include/wx/fileconf.h
+++ b/include/wx/fileconf.h
@@ -197,8 +197,8 @@ private:
 //protected: --- if wxFileConfig::ConfigEntry is not public, functions in
 //               ConfigGroup such as Find/AddEntry can't return "ConfigEntry *"
 public:
 //protected: --- if wxFileConfig::ConfigEntry is not public, functions in
 //               ConfigGroup such as Find/AddEntry can't return "ConfigEntry *"
 public:

-  WX_DEFINE_ARRAY(ConfigEntry *, ArrayEntries);
-  WX_DEFINE_ARRAY(ConfigGroup *, ArrayGroups);
+  WX_DEFINE_SORTED_ARRAY(ConfigEntry *, ArrayEntries);
+  WX_DEFINE_SORTED_ARRAY(ConfigGroup *, ArrayGroups);

 
   class ConfigEntry
   {
 
   class ConfigEntry
   {

diff --git a/src/common/fileconf.cpp b/src/common/fileconf.cpp
index f42a86a5bdb3d49e57308a757d99bacfab4f82b7..f25cb997dc44770f7e6c9ec0937d90860f8346f0 100644 (file)
--- a/src/common/fileconf.cpp
+++ b/src/common/fileconf.cpp
@@ -57,6 +57,12 @@
 //     but _not_ ']' (group name delimiter)
 inline bool IsValid(char c) { return isalnum(c) || strchr("@_/-!.*%", c); }
 
 //     but _not_ ']' (group name delimiter)
 inline bool IsValid(char c) { return isalnum(c) || strchr("@_/-!.*%", c); }
 

+// compare functions for sorting the arrays
+static int CompareEntries(wxFileConfig::ConfigEntry *p1,
+                          wxFileConfig::ConfigEntry *p2);
+static int CompareGroups(wxFileConfig::ConfigGroup *p1,
+                         wxFileConfig::ConfigGroup *p2);
+

 // filter strings
 static wxString FilterIn(const wxString& str);
 static wxString FilterOut(const wxString& str);
 // filter strings
 static wxString FilterIn(const wxString& str);
 static wxString FilterOut(const wxString& str);


@@ -637,7 +643,9 @@ bool wxFileConfig::LineListIsEmpty()
 wxFileConfig::ConfigGroup::ConfigGroup(wxFileConfig::ConfigGroup *pParent,
                                        const wxString& strName,
                                        wxFileConfig *pConfig)
 wxFileConfig::ConfigGroup::ConfigGroup(wxFileConfig::ConfigGroup *pParent,
                                        const wxString& strName,
                                        wxFileConfig *pConfig)

-                         : m_strName(strName)
+                         : m_aEntries(CompareEntries),
+                           m_aSubgroups(CompareGroups),
+                           m_strName(strName)

 {
   m_pConfig = pConfig;
   m_pParent = pParent;
 {
   m_pConfig = pConfig;
   m_pParent = pParent;


@@ -741,13 +749,32 @@ wxString wxFileConfig::ConfigGroup::GetFullName() const
 // find an item
 // ----------------------------------------------------------------------------
 
 // find an item
 // ----------------------------------------------------------------------------
 

+// use binary search because the array is sorted

 wxFileConfig::ConfigEntry *
 wxFileConfig::ConfigGroup::FindEntry(const char *szName) const
 {
 wxFileConfig::ConfigEntry *
 wxFileConfig::ConfigGroup::FindEntry(const char *szName) const
 {

-  uint nCount = m_aEntries.Count();
-  for ( uint n = 0; n < nCount; n++ ) {
-    if ( m_aEntries[n]->Name().IsSameAs(szName, APPCONF_CASE_SENSITIVE) )
-      return m_aEntries[n];
+  uint i,
+       lo = 0,
+       hi = m_aEntries.Count();
+  int res;
+  wxFileConfig::ConfigEntry *pEntry;
+
+  while ( lo < hi ) {
+    i = (lo + hi)/2;
+    pEntry = m_aEntries[i];
+
+    #if APPCONF_CASE_SENSITIVE
+      res = strcmp(pEntry->Name(), szName);
+    #else
+      res = Stricmp(pEntry->Name(), szName);
+    #endif
+
+    if ( res < 0 )
+      hi = i;
+    else if ( res > 0 )
+      lo = i + 1;
+    else
+      return pEntry;

   }
 
   return NULL;
   }
 
   return NULL;


@@ -756,10 +783,28 @@ wxFileConfig::ConfigGroup::FindEntry(const char *szName) const
 wxFileConfig::ConfigGroup *
 wxFileConfig::ConfigGroup::FindSubgroup(const char *szName) const
 {
 wxFileConfig::ConfigGroup *
 wxFileConfig::ConfigGroup::FindSubgroup(const char *szName) const
 {

-  uint nCount = m_aSubgroups.Count();
-  for ( uint n = 0; n < nCount; n++ ) {
-    if ( m_aSubgroups[n]->Name().IsSameAs(szName, APPCONF_CASE_SENSITIVE) )
-      return m_aSubgroups[n];
+  uint i,
+       lo = 0,
+       hi = m_aSubgroups.Count();
+  int res;
+  wxFileConfig::ConfigGroup *pGroup;
+
+  while ( lo < hi ) {
+    i = (lo + hi)/2;
+    pGroup = m_aSubgroups[i];
+
+    #if APPCONF_CASE_SENSITIVE
+      res = strcmp(pGroup->Name(), szName);
+    #else
+      res = Stricmp(pGroup->Name(), szName);
+    #endif
+
+    if ( res < 0 )
+      hi = i;
+    else if ( res > 0 )
+      lo = i + 1;
+    else
+      return pGroup;

   }
 
   return NULL;
   }
 
   return NULL;


@@ -946,6 +991,34 @@ void wxFileConfig::ConfigEntry::SetDirty()
 // global functions
 // ============================================================================
 
 // global functions
 // ============================================================================
 

+// ----------------------------------------------------------------------------
+// compare functions for array sorting
+// ----------------------------------------------------------------------------
+
+int CompareEntries(wxFileConfig::ConfigEntry *p1,
+                   wxFileConfig::ConfigEntry *p2)
+{
+  #if APPCONF_CASE_SENSITIVE
+    return strcmp(p1->Name(), p2->Name());
+  #else
+    return Stricmp(p1->Name(), p2->Name());
+  #endif
+}
+
+int CompareGroups(wxFileConfig::ConfigGroup *p1,
+                  wxFileConfig::ConfigGroup *p2)
+{
+  #if APPCONF_CASE_SENSITIVE
+    return strcmp(p1->Name(), p2->Name());
+  #else
+    return Stricmp(p1->Name(), p2->Name());
+  #endif
+}
+
+// ----------------------------------------------------------------------------
+// filter functions
+// ----------------------------------------------------------------------------
+

 // undo FilterOut
 wxString FilterIn(const wxString& str)
 {
 // undo FilterOut
 wxString FilterIn(const wxString& str)
 {