Improve performance of sort_folder_list() method.

Now sorting 25k folders takes around 3 seconds.

1 files changed, 49 insertions, 33 deletions

diff --git a/program/lib/Roundcube/rcube_imap.php b/program/lib/Roundcube/rcube_imap.php
index bf588cacf..41d1c373f 100644
--- a/program/lib/Roundcube/rcube_imap.php
+++ b/program/lib/Roundcube/rcube_imap.php
@@ -4142,59 +4142,75 @@ class rcube_imap extends rcube_storage
      */
     public function sort_folder_list($a_folders, $skip_default = false)
     {
-        $a_out = $a_defaults = $folders = array();
-
         $delimiter = $this->get_hierarchy_delimiter();
         $specials  = array_merge(array('INBOX'), array_values($this->get_special_folders()));
+        $folders   = array_flip($a_folders);
 
-        // find default folders and skip folders starting with '.'
+        // convert names to UTF-8 and skip folders starting with '.'
         foreach ($a_folders as $folder) {
-            if ($folder[0] == '.') {
-                continue;
-            }
-
-            if (!$skip_default && ($p = array_search($folder, $specials)) !== false && !$a_defaults[$p]) {
-                $a_defaults[$p] = $folder;
+            if ($folder[0] != '.') {
+                // for better performance skip encoding conversion
+                // if the string does not look like UTF7-IMAP
+                $folders[$folder] = strpos($folder, '+') === false ? $folder : rcube_charset::convert($folder, 'UTF7-IMAP');
             }
             else {
-                $folders[$folder] = rcube_charset::convert($folder, 'UTF7-IMAP');
+                unset($folders[$idx]);
             }
         }
 
-        // sort folders and place defaults on the top
-        asort($folders, SORT_LOCALE_STRING);
-        ksort($a_defaults);
-        $folders = array_merge($a_defaults, array_keys($folders));
+        // sort folders
+        // asort($folders, SORT_LOCALE_STRING) is not properly sorting case sensitive names
+        uasort($folders, array($this, 'sort_folder_comparator'));
+
+        $folders = array_keys($folders);
 
-        // finally we must rebuild the list to move
-        // subfolders of default folders to their place...
-        // ...also do this for the rest of folders because
-        // asort() is not properly sorting case sensitive names
-        while (list($key, $folder) = each($folders)) {
-            // set the type of folder name variable (#1485527)
-            $a_out[] = (string) $folder;
-            unset($folders[$key]);
-            $this->rsort($folder, $delimiter, $folders, $a_out);
+        if ($skip_default) {
+            return $folders;
         }
 
-        return $a_out;
+        $specials = array_unique(array_intersect($specials, $folders));
+        $head     = array();
+
+        // place default folders on the top
+        foreach ($specials as $special) {
+            $prefix = $special . $delimiter;
+
+            foreach ($folders as $idx => $folder) {
+                if ($folder === $special) {
+                    $head[] = (string) $special;
+                    unset($folders[$idx]);
+                }
+                // put subfolders of default folders on their place...
+                else if (strpos($folder, $prefix) === 0) {
+                    $head[] = (string) $folder;
+                    unset($folders[$idx]);
+                }
+            }
+        }
+
+        return array_merge($head, $folders);
     }
 
 
     /**
-     * Recursive method for sorting folders
+     * Callback for uasort() that implements correct
+     * locale-aware case-sensitive sorting
      */
-    protected function rsort($folder, $delimiter, &$list, &$out)
+    protected function sort_folder_comparator($str1, $str2)
     {
-        while (list($key, $name) = each($list)) {
-            if (strpos($name, $folder.$delimiter) === 0) {
-                // set the type of folder name variable (#1485527)
-                $out[] = (string) $name;
-                unset($list[$key]);
-                $this->rsort($name, $delimiter, $list, $out);
+        $delimiter = $this->get_hierarchy_delimiter();
+        $path1     = explode($delimiter, $str1);
+        $path2     = explode($delimiter, $str2);
+
+        foreach ($path1 as $idx => $folder1) {
+            $folder2 = $path2[$idx];
+
+            if ($folder1 === $folder2) {
+                continue;
             }
+
+            return strcoll($folder1, $folder2);
         }
-        reset($list);
     }