X-Git-Url: https://mattmccutchen.net/rsync/rsync.git/blobdiff_plain/1faa1a6da93065febb7e08830e5da37a09b6444d..79028af116752d192634f44e672f0b8b51ba7785:/flist.c diff --git a/flist.c b/flist.c index 3982662f..8d4ec1de 100644 --- a/flist.c +++ b/flist.c @@ -38,6 +38,7 @@ extern int module_id; extern int ignore_errors; extern int numeric_ids; extern int recurse; +extern int use_qsort; extern int xfer_dirs; extern int filesfrom_fd; extern int one_file_system; @@ -76,6 +77,8 @@ extern int need_unsorted_flist; extern iconv_t ic_send, ic_recv; #endif +#define PTR_SIZE (sizeof (struct file_struct *)) + int io_error; int checksum_len; dev_t filesystem_dev; /* used to implement -x */ @@ -1309,9 +1312,70 @@ static void send_if_directory(int f, struct file_list *flist, } } -static int file_compare(struct file_struct **file1, struct file_struct **file2) +static int file_compare(const void *file1, const void *file2) +{ + return f_name_cmp(*(struct file_struct **)file1, + *(struct file_struct **)file2); +} + +/* The guts of a merge sort algorithm. This was derived from the GNU C + * version, but I (Wayne) changed the merge code to do less copying and + * to require only half the amount of temporary memory. */ +static void fsort_tmp(struct file_struct **fp, size_t num, + struct file_struct **tmp) +{ + struct file_struct **f1, **f2, **t; + size_t n1, n2; + + n1 = num / 2; + n2 = num - n1; + f1 = fp; + f2 = fp + n1; + + if (n1 > 1) + fsort_tmp(f1, n1, tmp); + if (n2 > 1) + fsort_tmp(f2, n2, tmp); + + while (f_name_cmp(*f1, *f2) <= 0) { + if (!--n1) + return; + f1++; + } + + t = tmp; + memcpy(t, f1, n1 * PTR_SIZE); + + *f1++ = *f2++, n2--; + + while (n1 > 0 && n2 > 0) { + if (f_name_cmp(*t, *f2) <= 0) + *f1++ = *t++, n1--; + else + *f1++ = *f2++, n2--; + } + + if (n1 > 0) + memcpy(f1, t, n1 * PTR_SIZE); +} + +/* This file-struct sorting routine makes sure that any identical names in + * the file list stay in the same order as they were in the original list. + * This is particularly vital in inc_recurse mode where we expect a sort + * on the flist to match the exact order of a sort on the dir_flist. */ +static void fsort(struct file_struct **fp, size_t num) { - return f_name_cmp(*file1, *file2); + if (num <= 1) + return; + + if (use_qsort) + qsort(fp, num, PTR_SIZE, file_compare); + else { + struct file_struct **tmp = new_array(struct file_struct *, + (num+1) / 2); + fsort_tmp(fp, num, tmp); + free(tmp); + } } /* We take an entire set of sibling dirs from the sorted flist and link them @@ -1455,55 +1519,34 @@ void send_extra_file_list(int f, int at_least) future_cnt = 0; while (future_cnt < at_least) { struct file_struct *file = dir_flist->sorted[send_dir_ndx]; - int dstart = dir_count; + int dir_ndx, dstart = dir_count; int32 *dp; flist = flist_new(0, "send_extra_file_list"); start_write = stats.total_written; - /* If this is the first of a set of duplicate dirs, we must - * send all the dirs together in a single file-list. We must - * also send the index of the last dir in the header. */ - if (file->flags & FLAG_DUPLICATE) { - int dir_ndx, end_ndx = send_dir_ndx; - struct file_struct *fp = file; - - while (1) { - dp = F_DIRNODE_P(fp); - end_ndx = DIR_NEXT_SIBLING(dp); - fp = dir_flist->sorted[end_ndx]; - if (!(fp->flags & FLAG_DUPLICATE)) - break; - } - #ifdef ICONV_OPTION - if (ic_ndx) - dir_ndx = F_NDX(fp); - else + if (ic_ndx) + dir_ndx = F_NDX(file); + else #endif - dir_ndx = end_ndx; - write_ndx(f, NDX_FLIST_OFFSET - dir_ndx); + dir_ndx = send_dir_ndx; + write_ndx(f, NDX_FLIST_OFFSET - dir_ndx); - while (1) { - send1extra(f, file, flist); - if (send_dir_ndx == end_ndx) - break; - dp = F_DIRNODE_P(file); - send_dir_ndx = DIR_NEXT_SIBLING(dp); - file = dir_flist->sorted[send_dir_ndx]; - } - } else { - int dir_ndx; -#ifdef ICONV_OPTION - if (ic_ndx) - dir_ndx = F_NDX(file); - else -#endif - dir_ndx = send_dir_ndx; - write_ndx(f, NDX_FLIST_OFFSET - dir_ndx); + send1extra(f, file, flist); + dp = F_DIRNODE_P(file); + /* If there are any duplicate directory names that follow, we + * send all the dirs together in one file-list. The dir_flist + * tree links all the child subdirs onto the last dup dir. */ + while ((dir_ndx = DIR_NEXT_SIBLING(dp)) >= 0 + && dir_flist->sorted[dir_ndx]->flags & FLAG_DUPLICATE) { + send_dir_ndx = dir_ndx; + file = dir_flist->sorted[dir_ndx]; send1extra(f, file, flist); + dp = F_DIRNODE_P(file); } + write_byte(f, 0); #ifdef ICONV_OPTION @@ -1527,7 +1570,6 @@ void send_extra_file_list(int f, int at_least) if (verbose > 3) output_flist(flist); - dp = F_DIRNODE_P(file); if (DIR_FIRST_CHILD(dp) >= 0) { send_dir_ndx = DIR_FIRST_CHILD(dp); send_dir_depth++; @@ -1947,8 +1989,7 @@ struct file_list *recv_file_list(int f) dir_flist->count); memcpy(dir_flist->sorted + dstart, dir_flist->files + dstart, (dir_flist->count - dstart) * sizeof (struct file_struct*)); - qsort(dir_flist->sorted + dstart, dir_flist->count - dstart, - sizeof (struct file_struct*), (int (*)())file_compare); + fsort(dir_flist->sorted + dstart, dir_flist->count - dstart); } } else #endif @@ -1956,8 +1997,7 @@ struct file_list *recv_file_list(int f) flist->sorted = flist->files; if (inc_recurse && dir_flist->count > dstart) { dir_flist->sorted = dir_flist->files; - qsort(dir_flist->sorted + dstart, dir_flist->count - dstart, - sizeof (struct file_struct*), (int (*)())file_compare); + fsort(dir_flist->sorted + dstart, dir_flist->count - dstart); } } @@ -2164,8 +2204,7 @@ static void clean_flist(struct file_list *flist, int strip_root) return; } - qsort(flist->sorted, flist->count, - sizeof flist->sorted[0], (int (*)())file_compare); + fsort(flist->sorted, flist->count); if (!am_sender || inc_recurse) { for (i = prev_i = 0; i < flist->count; i++) { @@ -2199,20 +2238,18 @@ static void clean_flist(struct file_list *flist, int strip_root) } else j = -1; if (j >= 0) { - struct file_struct *fp = flist->sorted[j]; int keep, drop; /* If one is a dir and the other is not, we want to * keep the dir because it might have contents in the * list. */ - if (S_ISDIR(file->mode) != S_ISDIR(fp->mode)) { - if (S_ISDIR(file->mode)) + if (S_ISDIR(file->mode)) { + struct file_struct *fp = flist->sorted[j]; + if (!S_ISDIR(fp->mode)) keep = i, drop = j; else keep = j, drop = i; - } else if (protocol_version < 27) + } else keep = j, drop = i; - else - keep = i, drop = j; if (am_sender) flist->sorted[drop]->flags |= FLAG_DUPLICATE;