Improve performance of sort_folder_list() method.

Aleksander Machniak

2014-05-22 693612d396ede5c7ed8dc36e792d0e5653ccb8de

Improve performance of sort_folder_list() method.

Now sorting 25k folders takes around 3 seconds.

 program/lib/Roundcube/rcube_imap.php

@@ -4142,59 +4142,75 @@
     */
    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'));

        // 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);
        $folders = array_keys($folders);

        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);
    }