From: Vadim Zeitlin <vadim@wxwidgets.org>
Date: Thu, 16 Jul 1998 17:30:39 +0000 (+0000)
Subject: wxFileConfig uses sorted arrays (big performance improvement)
X-Git-Url: https://git.saurik.com/wxWidgets.git/commitdiff_plain/f5ae0449375b9ad7ccc2faa2e7708d9e74a9c4a4

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 84a12b4754..e499328236 100644
--- 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:
-  WX_DEFINE_ARRAY(ConfigEntry *, ArrayEntries);
-  WX_DEFINE_ARRAY(ConfigGroup *, ArrayGroups);
+  WX_DEFINE_SORTED_ARRAY(ConfigEntry *, ArrayEntries);
+  WX_DEFINE_SORTED_ARRAY(ConfigGroup *, ArrayGroups);
 
   class ConfigEntry
   {
diff --git a/src/common/fileconf.cpp b/src/common/fileconf.cpp
index f42a86a5bd..f25cb997dc 100644
--- 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); }
 
+// 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);
@@ -637,7 +643,9 @@ bool wxFileConfig::LineListIsEmpty()
 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;
@@ -741,13 +749,32 @@ wxString wxFileConfig::ConfigGroup::GetFullName() const
 // find an item
 // ----------------------------------------------------------------------------
 
+// use binary search because the array is sorted
 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;
@@ -756,10 +783,28 @@ wxFileConfig::ConfigGroup::FindEntry(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;
@@ -946,6 +991,34 @@ void wxFileConfig::ConfigEntry::SetDirty()
 // 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)
 {