From 48f6407ffec1db18f5ef3316f0d761965bb17f1e Mon Sep 17 00:00:00 2001 From: Karsten Blees Date: Thu, 14 Nov 2013 20:19:04 +0100 Subject: diffcore-rename.c: move code around to prepare for the next patch No actual code changes, just move hash_filespec up and outdent part of find_identical_files. Signed-off-by: Karsten Blees Signed-off-by: Junio C Hamano --- diffcore-rename.c | 98 +++++++++++++++++++++++++++---------------------------- 1 file changed, 49 insertions(+), 49 deletions(-) (limited to 'diffcore-rename.c') diff --git a/diffcore-rename.c b/diffcore-rename.c index 6c7a72fbe7..008a60c09d 100644 --- a/diffcore-rename.c +++ b/diffcore-rename.c @@ -248,6 +248,18 @@ struct file_similarity { struct file_similarity *next; }; +static unsigned int hash_filespec(struct diff_filespec *filespec) +{ + unsigned int hash; + if (!filespec->sha1_valid) { + if (diff_populate_filespec(filespec, 0)) + return 0; + hash_sha1_file(filespec->data, filespec->size, "blob", filespec->sha1); + } + memcpy(&hash, filespec->sha1, sizeof(hash)); + return hash; +} + static int find_identical_files(struct file_similarity *src, struct file_similarity *dst, struct diff_options *options) @@ -258,46 +270,46 @@ static int find_identical_files(struct file_similarity *src, * Walk over all the destinations ... */ do { - struct diff_filespec *target = dst->filespec; - struct file_similarity *p, *best; - int i = 100, best_score = -1; - - /* - * .. to find the best source match - */ - best = NULL; - for (p = src; p; p = p->next) { - int score; - struct diff_filespec *source = p->filespec; - - /* False hash collision? */ - if (hashcmp(source->sha1, target->sha1)) - continue; - /* Non-regular files? If so, the modes must match! */ - if (!S_ISREG(source->mode) || !S_ISREG(target->mode)) { - if (source->mode != target->mode) - continue; - } - /* Give higher scores to sources that haven't been used already */ - score = !source->rename_used; - if (source->rename_used && options->detect_rename != DIFF_DETECT_COPY) - continue; - score += basename_same(source, target); - if (score > best_score) { - best = p; - best_score = score; - if (score == 2) - break; - } + struct diff_filespec *target = dst->filespec; + struct file_similarity *p, *best; + int i = 100, best_score = -1; - /* Too many identical alternatives? Pick one */ - if (!--i) - break; + /* + * .. to find the best source match + */ + best = NULL; + for (p = src; p; p = p->next) { + int score; + struct diff_filespec *source = p->filespec; + + /* False hash collision? */ + if (hashcmp(source->sha1, target->sha1)) + continue; + /* Non-regular files? If so, the modes must match! */ + if (!S_ISREG(source->mode) || !S_ISREG(target->mode)) { + if (source->mode != target->mode) + continue; } - if (best) { - record_rename_pair(dst->index, best->index, MAX_SCORE); - renames++; + /* Give higher scores to sources that haven't been used already */ + score = !source->rename_used; + if (source->rename_used && options->detect_rename != DIFF_DETECT_COPY) + continue; + score += basename_same(source, target); + if (score > best_score) { + best = p; + best_score = score; + if (score == 2) + break; } + + /* Too many identical alternatives? Pick one */ + if (!--i) + break; + } + if (best) { + record_rename_pair(dst->index, best->index, MAX_SCORE); + renames++; + } } while ((dst = dst->next) != NULL); return renames; } @@ -343,18 +355,6 @@ static int find_same_files(void *ptr, void *data) return ret; } -static unsigned int hash_filespec(struct diff_filespec *filespec) -{ - unsigned int hash; - if (!filespec->sha1_valid) { - if (diff_populate_filespec(filespec, 0)) - return 0; - hash_sha1_file(filespec->data, filespec->size, "blob", filespec->sha1); - } - memcpy(&hash, filespec->sha1, sizeof(hash)); - return hash; -} - static void insert_file_table(struct hash_table *table, int src_dst, int index, struct diff_filespec *filespec) { void **pos; -- cgit v1.3 From 7c85f8acb2282e3ed108c46b59fd5daa78bf17db Mon Sep 17 00:00:00 2001 From: Karsten Blees Date: Thu, 14 Nov 2013 20:19:34 +0100 Subject: diffcore-rename.c: simplify finding exact renames The find_exact_renames function currently only uses the hash table for grouping, i.e.: 1. add sources 2. add destinations 3. iterate all buckets, per bucket: 4. split sources from destinations 5. iterate destinations, per destination: 6. iterate sources to find best match This can be simplified by utilizing the lookup functionality of the hash table, i.e.: 1. add sources 2. iterate destinations, per destination: 3. lookup sources matching the current destination 4. iterate sources to find best match This saves several iterations and file_similarity allocations for the destinations. Signed-off-by: Karsten Blees Signed-off-by: Junio C Hamano --- diffcore-rename.c | 75 +++++++++++++++---------------------------------------- 1 file changed, 20 insertions(+), 55 deletions(-) (limited to 'diffcore-rename.c') diff --git a/diffcore-rename.c b/diffcore-rename.c index 008a60c09d..cfeb408ea7 100644 --- a/diffcore-rename.c +++ b/diffcore-rename.c @@ -243,7 +243,7 @@ static int score_compare(const void *a_, const void *b_) } struct file_similarity { - int src_dst, index; + int index; struct diff_filespec *filespec; struct file_similarity *next; }; @@ -260,25 +260,21 @@ static unsigned int hash_filespec(struct diff_filespec *filespec) return hash; } -static int find_identical_files(struct file_similarity *src, - struct file_similarity *dst, +static int find_identical_files(struct hash_table *srcs, + int dst_index, struct diff_options *options) { int renames = 0; - /* - * Walk over all the destinations ... - */ - do { - struct diff_filespec *target = dst->filespec; + struct diff_filespec *target = rename_dst[dst_index].two; struct file_similarity *p, *best; int i = 100, best_score = -1; /* - * .. to find the best source match + * Find the best source match for specified destination. */ best = NULL; - for (p = src; p; p = p->next) { + for (p = lookup_hash(hash_filespec(target), srcs); p; p = p->next) { int score; struct diff_filespec *source = p->filespec; @@ -307,61 +303,28 @@ static int find_identical_files(struct file_similarity *src, break; } if (best) { - record_rename_pair(dst->index, best->index, MAX_SCORE); + record_rename_pair(dst_index, best->index, MAX_SCORE); renames++; } - } while ((dst = dst->next) != NULL); return renames; } -static void free_similarity_list(struct file_similarity *p) +static int free_similarity_list(void *p, void *unused) { while (p) { struct file_similarity *entry = p; - p = p->next; + p = entry->next; free(entry); } + return 0; } -static int find_same_files(void *ptr, void *data) -{ - int ret; - struct file_similarity *p = ptr; - struct file_similarity *src = NULL, *dst = NULL; - struct diff_options *options = data; - - /* Split the hash list up into sources and destinations */ - do { - struct file_similarity *entry = p; - p = p->next; - if (entry->src_dst < 0) { - entry->next = src; - src = entry; - } else { - entry->next = dst; - dst = entry; - } - } while (p); - - /* - * If we have both sources *and* destinations, see if - * we can match them up - */ - ret = (src && dst) ? find_identical_files(src, dst, options) : 0; - - /* Free the hashes and return the number of renames found */ - free_similarity_list(src); - free_similarity_list(dst); - return ret; -} - -static void insert_file_table(struct hash_table *table, int src_dst, int index, struct diff_filespec *filespec) +static void insert_file_table(struct hash_table *table, int index, struct diff_filespec *filespec) { void **pos; unsigned int hash; struct file_similarity *entry = xmalloc(sizeof(*entry)); - entry->src_dst = src_dst; entry->index = index; entry->filespec = filespec; entry->next = NULL; @@ -385,24 +348,26 @@ static void insert_file_table(struct hash_table *table, int src_dst, int index, */ static int find_exact_renames(struct diff_options *options) { - int i; + int i, renames = 0; struct hash_table file_table; + /* Add all sources to the hash table */ init_hash(&file_table); - preallocate_hash(&file_table, rename_src_nr + rename_dst_nr); + preallocate_hash(&file_table, rename_src_nr); for (i = 0; i < rename_src_nr; i++) - insert_file_table(&file_table, -1, i, rename_src[i].p->one); + insert_file_table(&file_table, i, rename_src[i].p->one); + /* Walk the destinations and find best source match */ for (i = 0; i < rename_dst_nr; i++) - insert_file_table(&file_table, 1, i, rename_dst[i].two); + renames += find_identical_files(&file_table, i, options); - /* Find the renames */ - i = for_each_hash(&file_table, find_same_files, options); + /* Free source file_similarity chains */ + for_each_hash(&file_table, free_similarity_list, options); /* .. and free the hash data structure */ free_hash(&file_table); - return i; + return renames; } #define NUM_CANDIDATE_PER_DST 4 -- cgit v1.3 From f79d9c581437d8f48e10506e62c34b9718c7f3f7 Mon Sep 17 00:00:00 2001 From: Karsten Blees Date: Thu, 14 Nov 2013 20:20:26 +0100 Subject: diffcore-rename.c: use new hash map implementation Signed-off-by: Karsten Blees Signed-off-by: Junio C Hamano --- diffcore-rename.c | 48 +++++++++++++----------------------------------- 1 file changed, 13 insertions(+), 35 deletions(-) (limited to 'diffcore-rename.c') diff --git a/diffcore-rename.c b/diffcore-rename.c index cfeb408ea7..9b4f068eb3 100644 --- a/diffcore-rename.c +++ b/diffcore-rename.c @@ -4,7 +4,7 @@ #include "cache.h" #include "diff.h" #include "diffcore.h" -#include "hash.h" +#include "hashmap.h" #include "progress.h" /* Table of rename/copy destinations */ @@ -243,9 +243,9 @@ static int score_compare(const void *a_, const void *b_) } struct file_similarity { + struct hashmap_entry entry; int index; struct diff_filespec *filespec; - struct file_similarity *next; }; static unsigned int hash_filespec(struct diff_filespec *filespec) @@ -260,21 +260,22 @@ static unsigned int hash_filespec(struct diff_filespec *filespec) return hash; } -static int find_identical_files(struct hash_table *srcs, +static int find_identical_files(struct hashmap *srcs, int dst_index, struct diff_options *options) { int renames = 0; struct diff_filespec *target = rename_dst[dst_index].two; - struct file_similarity *p, *best; + struct file_similarity *p, *best, dst; int i = 100, best_score = -1; /* * Find the best source match for specified destination. */ best = NULL; - for (p = lookup_hash(hash_filespec(target), srcs); p; p = p->next) { + hashmap_entry_init(&dst, hash_filespec(target)); + for (p = hashmap_get(srcs, &dst, NULL); p; p = hashmap_get_next(srcs, p)) { int score; struct diff_filespec *source = p->filespec; @@ -309,34 +310,15 @@ static int find_identical_files(struct hash_table *srcs, return renames; } -static int free_similarity_list(void *p, void *unused) +static void insert_file_table(struct hashmap *table, int index, struct diff_filespec *filespec) { - while (p) { - struct file_similarity *entry = p; - p = entry->next; - free(entry); - } - return 0; -} - -static void insert_file_table(struct hash_table *table, int index, struct diff_filespec *filespec) -{ - void **pos; - unsigned int hash; struct file_similarity *entry = xmalloc(sizeof(*entry)); entry->index = index; entry->filespec = filespec; - entry->next = NULL; - - hash = hash_filespec(filespec); - pos = insert_hash(hash, entry, table); - /* We already had an entry there? */ - if (pos) { - entry->next = *pos; - *pos = entry; - } + hashmap_entry_init(entry, hash_filespec(filespec)); + hashmap_add(table, entry); } /* @@ -349,11 +331,10 @@ static void insert_file_table(struct hash_table *table, int index, struct diff_f static int find_exact_renames(struct diff_options *options) { int i, renames = 0; - struct hash_table file_table; + struct hashmap file_table; /* Add all sources to the hash table */ - init_hash(&file_table); - preallocate_hash(&file_table, rename_src_nr); + hashmap_init(&file_table, NULL, rename_src_nr); for (i = 0; i < rename_src_nr; i++) insert_file_table(&file_table, i, rename_src[i].p->one); @@ -361,11 +342,8 @@ static int find_exact_renames(struct diff_options *options) for (i = 0; i < rename_dst_nr; i++) renames += find_identical_files(&file_table, i, options); - /* Free source file_similarity chains */ - for_each_hash(&file_table, free_similarity_list, options); - - /* .. and free the hash data structure */ - free_hash(&file_table); + /* Free the hash data structure and entries */ + hashmap_free(&file_table, 1); return renames; } -- cgit v1.3