X-Git-Url: https://mattmccutchen.net/rsync/rsync.git/blobdiff_plain/a36ffd39109cd910a5102e83333d77641c1e6227..beab3078d637de643825a3b8f0c246a7c2db042d:/match.c diff --git a/match.c b/match.c index 55c6d133..4fe23fd5 100644 --- a/match.c +++ b/match.c @@ -20,17 +20,12 @@ #include "rsync.h" extern int verbose; -extern int am_server; extern int do_progress; extern int checksum_seed; +extern int append_mode; int updating_basis_file; -typedef unsigned short tag; - -#define TABLESIZE (1<<16) -#define NULL_TAG ((size_t)-1) - static int false_alarms; static int tag_hits; static int matches; @@ -42,47 +37,37 @@ static int total_matches; extern struct stats stats; -struct target { - tag t; - size_t i; -}; - -static struct target *targets; - -static size_t *tag_table; - -#define gettag2(s1,s2) (((s1) + (s2)) & 0xFFFF) -#define gettag(sum) gettag2((sum)&0xFFFF,(sum)>>16) - -static int compare_targets(struct target *t1,struct target *t2) -{ - return (int)t1->t - (int)t2->t; -} +static uint32 tablesize; +static int32 *sum_table; +#define gettag2(s1,s2) gettag((s1) + ((s2)<<16)) +#define gettag(sum) ((sum)%tablesize) static void build_hash_table(struct sum_struct *s) { - size_t i; - - if (!tag_table) - tag_table = new_array(size_t, TABLESIZE); + int32 i; + uint32 prior_size = tablesize; + + /* Dynamically calculate the hash table size so that the hash load + * for big files is about 80%. This number must be odd or s2 will + * not be able to span the entire set. */ + tablesize = (uint32)(s->count/8) * 10 + 11; + if (tablesize < 65537) + tablesize = 65537; /* a prime number */ + if (tablesize != prior_size) { + free(sum_table); + sum_table = new_array(int32, tablesize); + if (!sum_table) + out_of_memory("build_hash_table"); + } - targets = new_array(struct target, s->count); - if (!tag_table || !targets) - out_of_memory("build_hash_table"); + memset(sum_table, 0xFF, tablesize * sizeof sum_table[0]); for (i = 0; i < s->count; i++) { - targets[i].i = i; - targets[i].t = gettag(s->sums[i].sum1); + uint32 t = gettag(s->sums[i].sum1); + s->sums[i].chain = sum_table[t]; + sum_table[t] = i; } - - qsort(targets,s->count,sizeof(targets[0]),(int (*)())compare_targets); - - for (i = 0; i < TABLESIZE; i++) - tag_table[i] = NULL_TAG; - - for (i = s->count; i-- > 0; ) - tag_table[targets[i].t] = i; } @@ -102,7 +87,7 @@ static OFF_T last_match; * have only literal data. **/ static void matched(int f, struct sum_struct *s, struct map_struct *buf, - OFF_T offset, int i) + OFF_T offset, int32 i) { int32 n = offset - last_match; /* max value: block_size (int32) */ int32 j; @@ -127,18 +112,13 @@ static void matched(int f, struct sum_struct *s, struct map_struct *buf, sum_update(map_ptr(buf, last_match + j, n1), n1); } - if (i >= 0) last_match = offset + s->sums[i].len; else last_match = offset; - if (buf && do_progress) { + if (buf && do_progress) show_progress(last_match, buf->file_size); - - if (i == -1) - end_progress(buf->file_size); - } } @@ -146,8 +126,7 @@ static void hash_search(int f,struct sum_struct *s, struct map_struct *buf, OFF_T len) { OFF_T offset, end, backup; - int32 k; - size_t want_i; + int32 k, want_i; char sum2[SUM_LENGTH]; uint32 s1, s2, sum; int more; @@ -182,21 +161,17 @@ static void hash_search(int f,struct sum_struct *s, } do { - tag t = gettag2(s1,s2); + uint32 t = gettag2(s1,s2); int done_csum2 = 0; - size_t j = tag_table[t]; + int32 i; if (verbose > 4) rprintf(FINFO,"offset=%.0f sum=%08x\n",(double)offset,sum); - if (j == NULL_TAG) - goto null_tag; - sum = (s1 & 0xffff) | (s2 << 16); tag_hits++; - do { + for (i = sum_table[t]; i >= 0; i = s->sums[i].chain) { int32 l; - size_t i = targets[j].i; if (sum != s->sums[i].sum1) continue; @@ -212,9 +187,11 @@ static void hash_search(int f,struct sum_struct *s, && !(s->sums[i].flags & SUMFLG_SAME_OFFSET)) continue; - if (verbose > 3) - rprintf(FINFO,"potential match at %.0f target=%.0f %.0f sum=%08x\n", - (double)offset,(double)j,(double)i,sum); + if (verbose > 3) { + rprintf(FINFO, + "potential match at %.0f i=%ld sum=%08x\n", + (double)offset, (long)i, sum); + } if (!done_csum2) { map = (schar *)map_ptr(buf,offset,l); @@ -231,8 +208,8 @@ static void hash_search(int f,struct sum_struct *s, * one with an identical offset, so we prefer that over * the following want_i optimization. */ if (updating_basis_file) { - do { - size_t i2 = targets[j].i; + int32 i2; + for (i2 = i; i2 >= 0; i2 = s->sums[i2].chain) { if (s->sums[i2].offset != offset) continue; if (i2 != i) { @@ -247,7 +224,7 @@ static void hash_search(int f,struct sum_struct *s, * both the sender and the receiver. */ s->sums[i].flags |= SUMFLG_SAME_OFFSET; goto set_want_i; - } while (++j < s->count && targets[j].t == t); + } } /* we've found a match, but now check to see @@ -273,9 +250,8 @@ static void hash_search(int f,struct sum_struct *s, s2 = sum >> 16; matches++; break; - } while (++j < s->count && targets[j].t == t); + } - null_tag: backup = offset - last_match; /* We sometimes read 1 byte prior to last_match... */ if (backup < 0) @@ -336,6 +312,25 @@ void match_sums(int f, struct sum_struct *s, struct map_struct *buf, OFF_T len) sum_init(checksum_seed); + if (append_mode) { + OFF_T j = 0; + for (j = CHUNK_SIZE; j < s->flength; j += CHUNK_SIZE) { + if (buf && do_progress) + show_progress(last_match, buf->file_size); + sum_update(map_ptr(buf, last_match, CHUNK_SIZE), + CHUNK_SIZE); + last_match = j; + } + if (last_match < s->flength) { + int32 len = s->flength - last_match; + if (buf && do_progress) + show_progress(last_match, buf->file_size); + sum_update(map_ptr(buf, last_match, len), len); + last_match = s->flength; + } + s->count = 0; + } + if (len > 0 && s->count > 0) { build_hash_table(s); @@ -349,7 +344,7 @@ void match_sums(int f, struct sum_struct *s, struct map_struct *buf, OFF_T len) } else { OFF_T j; /* by doing this in pieces we avoid too many seeks */ - for (j = CHUNK_SIZE; j < len; j += CHUNK_SIZE) + for (j = last_match + CHUNK_SIZE; j < len; j += CHUNK_SIZE) matched(f, s, buf, j, -2); matched(f, s, buf, len, -1); } @@ -363,11 +358,6 @@ void match_sums(int f, struct sum_struct *s, struct map_struct *buf, OFF_T len) rprintf(FINFO,"sending file_sum\n"); write_buf(f,file_sum,MD4_SUM_LENGTH); - if (targets) { - free(targets); - targets=NULL; - } - if (verbose > 2) rprintf(FINFO, "false_alarms=%d tag_hits=%d matches=%d\n", false_alarms, tag_hits, matches);