From 1db27b7c1a718380ee162ee30bf3b4707d65e851 Mon Sep 17 00:00:00 2001 From: Wayne Davison Date: Tue, 28 Feb 2006 00:26:17 +0000 Subject: [PATCH] Fixed a few bugs. --- dynamic_hash.diff | 88 ++++++++++++++++++++++++++++++++++++----------- 1 file changed, 67 insertions(+), 21 deletions(-) diff --git a/dynamic_hash.diff b/dynamic_hash.diff index 3713823..480384d 100644 --- a/dynamic_hash.diff +++ b/dynamic_hash.diff @@ -7,7 +7,7 @@ An extended version of a patch by Shachar Shemesh. --- old/match.c +++ new/match.c -@@ -26,11 +26,6 @@ extern int append_mode; +@@ -26,63 +26,47 @@ extern int append_mode; int updating_basis_file; @@ -17,9 +17,15 @@ An extended version of a patch by Shachar Shemesh. -#define NULL_TAG (-1) - static int false_alarms; - static int tag_hits; +-static int tag_hits; ++static int hash_hits; static int matches; -@@ -42,47 +37,37 @@ static int total_matches; + static int64 data_transfer; + + static int total_false_alarms; +-static int total_tag_hits; ++static int total_hash_hits; + static int total_matches; extern struct stats stats; @@ -42,8 +48,7 @@ An extended version of a patch by Shachar Shemesh. +static uint32 tablesize; +static int32 *sum_table; -+#define gettag2(s1,s2) gettag((s1) + ((s2)<<16)) -+#define gettag(sum) ((sum)%tablesize) ++#define GETTAG(sum) ((sum)%tablesize) static void build_hash_table(struct sum_struct *s) { @@ -73,7 +78,7 @@ An extended version of a patch by Shachar Shemesh. 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); ++ uint32 t = GETTAG(s->sums[i].sum1); + s->sums[i].chain = sum_table[t]; + sum_table[t] = i; } @@ -88,32 +93,36 @@ An extended version of a patch by Shachar Shemesh. } -@@ -176,20 +161,17 @@ static void hash_search(int f,struct sum +@@ -176,20 +160,21 @@ static void hash_search(int f,struct sum } do { - tag t = gettag2(s1,s2); -+ uint32 t = gettag2(s1,s2); int done_csum2 = 0; - int32 j = tag_table[t]; + int32 i; ++ uint32 t; 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 { ++ t = GETTAG(sum); ++ i = sum_table[t]; ++ if (i < 0) ++ goto null_hash; + +- sum = (s1 & 0xffff) | (s2 << 16); +- tag_hits++; ++ hash_hits++; + do { - int32 l, i = targets[j].i; -+ for (i = sum_table[t]; i >= 0; i = s->sums[i].chain) { + int32 l; if (sum != s->sums[i].sum1) continue; -@@ -205,9 +187,11 @@ static void hash_search(int f,struct sum +@@ -205,9 +190,11 @@ static void hash_search(int f,struct sum && !(s->sums[i].flags & SUMFLG_SAME_OFFSET)) continue; @@ -128,7 +137,7 @@ An extended version of a patch by Shachar Shemesh. if (!done_csum2) { map = (schar *)map_ptr(buf,offset,l); -@@ -224,8 +208,8 @@ static void hash_search(int f,struct sum +@@ -224,8 +211,8 @@ static void hash_search(int f,struct sum * one with an identical offset, so we prefer that over * the following want_i optimization. */ if (updating_basis_file) { @@ -139,7 +148,7 @@ An extended version of a patch by Shachar Shemesh. if (s->sums[i2].offset != offset) continue; if (i2 != i) { -@@ -240,7 +224,7 @@ static void hash_search(int f,struct sum +@@ -240,7 +227,7 @@ static void hash_search(int f,struct sum * both the sender and the receiver. */ s->sums[i].flags |= SUMFLG_SAME_OFFSET; goto set_want_i; @@ -148,18 +157,36 @@ An extended version of a patch by Shachar Shemesh. } /* we've found a match, but now check to see -@@ -266,9 +250,8 @@ static void hash_search(int f,struct sum +@@ -266,9 +253,9 @@ static void hash_search(int f,struct sum s2 = sum >> 16; matches++; break; - } while (++j < s->count && targets[j].t == t); -+ } ++ } while ((i = s->sums[i].chain) >= 0); - null_tag: ++ null_hash: backup = offset - last_match; /* We sometimes read 1 byte prior to last_match... */ if (backup < 0) -@@ -375,11 +358,6 @@ void match_sums(int f, struct sum_struct +@@ -287,6 +274,7 @@ static void hash_search(int f,struct sum + s2 += s1; + } else + --k; ++ sum = (s1 & 0xffff) | (s2 << 16); + + /* By matching early we avoid re-reading the + data 3 times in the case where a token +@@ -323,7 +311,7 @@ void match_sums(int f, struct sum_struct + + last_match = 0; + false_alarms = 0; +- tag_hits = 0; ++ hash_hits = 0; + matches = 0; + data_transfer = 0; + +@@ -375,16 +363,11 @@ void match_sums(int f, struct sum_struct rprintf(FINFO,"sending file_sum\n"); write_buf(f,file_sum,MD4_SUM_LENGTH); @@ -169,8 +196,27 @@ An extended version of a patch by Shachar Shemesh. - } - if (verbose > 2) - rprintf(FINFO, "false_alarms=%d tag_hits=%d matches=%d\n", - false_alarms, tag_hits, matches); +- rprintf(FINFO, "false_alarms=%d tag_hits=%d matches=%d\n", +- false_alarms, tag_hits, matches); ++ rprintf(FINFO, "false_alarms=%d hash_hits=%d matches=%d\n", ++ false_alarms, hash_hits, matches); + +- total_tag_hits += tag_hits; ++ total_hash_hits += hash_hits; + total_false_alarms += false_alarms; + total_matches += matches; + stats.literal_data += data_transfer; +@@ -396,8 +379,7 @@ void match_report(void) + return; + + rprintf(FINFO, +- "total: matches=%d tag_hits=%d false_alarms=%d data=%.0f\n", +- total_matches,total_tag_hits, +- total_false_alarms, ++ "total: matches=%d hash_hits=%d false_alarms=%d data=%.0f\n", ++ total_matches, total_hash_hits, total_false_alarms, + (double)stats.literal_data); + } --- old/rsync.h +++ new/rsync.h @@ -560,6 +560,7 @@ struct sum_buf { -- 2.34.1