Optimized flist_find() so that we never scan a series of empty

[rsync/rsync.git] / flist.c

diff --git a/flist.c b/flist.c
index 763d826..dc283a1 100644 (file)
--- a/flist.c
+++ b/flist.c
@@ -53,6 +53,7 @@ extern int preserve_uid;
 extern int preserve_gid;
 extern int relative_paths;
 extern int implied_dirs;
+extern int skip_empty_dirs;
 extern int copy_links;
 extern int copy_unsafe_links;
 extern int protocol_version;
@@ -75,6 +76,7 @@ unsigned int file_struct_len;
 
 static char empty_sum[MD4_SUM_LENGTH];
 static int flist_count_offset;
+static int max_dir_depth = 0;
 
 static void clean_flist(struct file_list *flist, int strip_root, int no_dups);
 static void output_flist(struct file_list *flist);
@@ -633,6 +635,8 @@ static struct file_struct *receive_file_entry(struct file_list *flist,
                bp[-1] = '\0';
                lastdir_depth = count_dir_elements(lastdir);
                file->dir.depth = lastdir_depth + 1;
+               if (lastdir_depth >= max_dir_depth)
+                       max_dir_depth = lastdir_depth + 1;
        } else if (dirname) {
                file->dirname = dirname; /* we're reusing lastname */
                file->dir.depth = lastdir_depth + 1;
@@ -1439,11 +1443,30 @@ int flist_find(struct file_list *flist, struct file_struct *f)
 
        while (low <= high) {
                mid = (low + high) / 2;
-               for (mid_up = mid; !flist->files[mid_up]->basename; mid_up++) {}
-               if (mid_up <= high)
-                       ret = f_name_cmp(flist->files[mid_up], f);
-               else
-                       ret = 1;
+               if (flist->files[mid]->basename)
+                       mid_up = mid;
+               else if (flist->files[mid]->dir.depth) {
+                       mid_up = mid + flist->files[mid]->dir.depth;
+                       if (mid_up < mid) {
+                               high = mid_up;
+                               continue;
+                       }
+               } else {
+                       /* Scan for the next non-empty entry and cache
+                        * the distance so we never do this again. */
+                       mid_up = mid;
+                       while (++mid_up <= high
+                           && !flist->files[mid_up]->basename) {}
+                       if (mid_up > high) {
+                               high = mid;
+                               while (--high >= low
+                                   && !flist->files[high]->basename) {}
+                               flist->files[mid]->dir.depth = high - mid;
+                               continue;
+                       }
+                       flist->files[mid]->dir.depth = mid_up - mid;
+               }
+               ret = f_name_cmp(flist->files[mid_up], f);
                if (ret == 0) {
                        if (protocol_version < 29
                            && S_ISDIR(flist->files[mid_up]->mode)
@@ -1570,8 +1593,8 @@ static void clean_flist(struct file_list *flist, int strip_root, int no_dups)
                                        "removing duplicate name %s from file list (%d)\n",
                                        f_name(file, NULL), drop);
                        }
-                       /* Make sure that if we unduplicate '.', that we don't
-                        * lose track of a user-specified top directory. */
+                       /* Make sure we don't lose track of a user-specified
+                        * top directory. */
                        flist->files[keep]->flags |= flist->files[drop]->flags
                                                   & (FLAG_TOP_DIR|FLAG_DEL_HERE);
 
@@ -1599,16 +1622,53 @@ static void clean_flist(struct file_list *flist, int strip_root, int no_dups)
 
                        if (!file->dirname)
                                continue;
-                       if (*file->dirname == '/') {
-                               char *s = file->dirname + 1;
-                               while (*s == '/') s++;
-                               memmove(file->dirname, s, strlen(s) + 1);
-                       }
-
+                       while (*file->dirname == '/')
+                               file->dirname++;
                        if (!*file->dirname)
                                file->dirname = NULL;
                }
        }
+
+       if (skip_empty_dirs && no_dups && max_dir_depth) {
+               int j, cur_depth = 0;
+               int *maybe_dirs = new_array(int, max_dir_depth);
+
+               maybe_dirs[0] = -1;
+
+               for (i = flist->low; i <= flist->high; i++) {
+                       struct file_struct *file = flist->files[i];
+
+                       if (S_ISDIR(file->mode) && file->dir.depth) {
+                               j = cur_depth;
+                               cur_depth = file->dir.depth - 1;
+                               for ( ; j >= cur_depth; j--) {
+                                       if (maybe_dirs[j] < 0)
+                                               continue;
+                                       clear_file(maybe_dirs[j], flist);
+                               }
+                               maybe_dirs[cur_depth] = i;
+                       } else if (maybe_dirs[cur_depth] >= 0) {
+                               for (j = 0; j <= cur_depth; j++)
+                                       maybe_dirs[j] = -1;
+                       }
+               }
+               for (j = cur_depth; j >= 0; j--) {
+                       if (maybe_dirs[j] < 0)
+                               continue;
+                       clear_file(maybe_dirs[j], flist);
+               }
+
+               for (i = flist->low; i <= flist->high; i++) {
+                       if (flist->files[i]->basename)
+                               break;
+               }
+               flist->low = i;
+               for (i = flist->high; i >= flist->low; i--) {
+                       if (flist->files[i]->basename)
+                               break;
+               }
+               flist->high = i;
+       }
 }
 
 static void output_flist(struct file_list *flist)