@@ -18,6 +18,7 @@
#include "submodule-config.h"
#include "submodule.h"
#include "hashmap.h"
+#include "mem-pool.h"
#include "ll-merge.h"
#include "string-list.h"
#include "strvec.h"
@@ -772,6 +773,7 @@ struct emitted_diff_symbol {
int flags;
int indent_off; /* Offset to first non-whitespace character */
int indent_width; /* The visual width of the indentation */
+ unsigned id;
enum diff_symbol s;
};
#define EMITTED_DIFF_SYMBOL_INIT {NULL}
@@ -797,9 +799,9 @@ static void append_emitted_diff_symbol(struct diff_options *o,
}
struct moved_entry {
- struct hashmap_entry ent;
const struct emitted_diff_symbol *es;
struct moved_entry *next_line;
+ struct moved_entry *next_match;
};
struct moved_block {
@@ -865,24 +867,24 @@ static int cmp_in_block_with_wsd(const struct moved_entry *cur,
const struct emitted_diff_symbol *l,
struct moved_block *pmb)
{
- int al = cur->es->len, bl = l->len;
- const char *a = cur->es->line,
- *b = l->line;
- int a_off = cur->es->indent_off,
- a_width = cur->es->indent_width,
- b_off = l->indent_off,
- b_width = l->indent_width;
+ int a_width = cur->es->indent_width, b_width = l->indent_width;
int delta;
- /* If 'l' and 'cur' are both blank then they match. */
- if (a_width == INDENT_BLANKLINE && b_width == INDENT_BLANKLINE)
+ /* The text of each line must match */
+ if (cur->es->id != l->id)
+ return 1;
+
+ /*
+ * If 'l' and 'cur' are both blank then we don't need to check the
+ * indent. We only need to check cur as we know the strings match.
+ * */
+ if (a_width == INDENT_BLANKLINE)
return 0;
/*
* The indent changes of the block are known and stored in pmb->wsd;
* however we need to check if the indent changes of the current line
- * match those of the current block and that the text of 'l' and 'cur'
- * after the indentation match.
+ * match those of the current block.
*/
delta = b_width - a_width;
@@ -893,22 +895,26 @@ static int cmp_in_block_with_wsd(const struct moved_entry *cur,
if (pmb->wsd == INDENT_BLANKLINE)
pmb->wsd = delta;
- return !(delta == pmb->wsd && al - a_off == bl - b_off &&
- !memcmp(a + a_off, b + b_off, al - a_off));
+ return delta != pmb->wsd;
}
-static int moved_entry_cmp(const void *hashmap_cmp_fn_data,
- const struct hashmap_entry *eptr,
- const struct hashmap_entry *entry_or_key,
- const void *keydata)
+struct interned_diff_symbol {
+ struct hashmap_entry ent;
+ struct emitted_diff_symbol *es;
+};
+
+static int interned_diff_symbol_cmp(const void *hashmap_cmp_fn_data,
+ const struct hashmap_entry *eptr,
+ const struct hashmap_entry *entry_or_key,
+ const void *keydata)
{
const struct diff_options *diffopt = hashmap_cmp_fn_data;
const struct emitted_diff_symbol *a, *b;
unsigned flags = diffopt->color_moved_ws_handling
& XDF_WHITESPACE_FLAGS;
- a = container_of(eptr, const struct moved_entry, ent)->es;
- b = container_of(entry_or_key, const struct moved_entry, ent)->es;
+ a = container_of(eptr, const struct interned_diff_symbol, ent)->es;
+ b = container_of(entry_or_key, const struct interned_diff_symbol, ent)->es;
return !xdiff_compare_lines(a->line + a->indent_off,
a->len - a->indent_off,
@@ -916,55 +922,81 @@ static int moved_entry_cmp(const void *hashmap_cmp_fn_data,
b->len - b->indent_off, flags);
}
-static struct moved_entry *prepare_entry(struct diff_options *o,
- int line_no)
+static void prepare_entry(struct diff_options *o, struct emitted_diff_symbol *l,
+ struct interned_diff_symbol *s)
{
- struct moved_entry *ret = xmalloc(sizeof(*ret));
- struct emitted_diff_symbol *l = &o->emitted_symbols->buf[line_no];
unsigned flags = o->color_moved_ws_handling & XDF_WHITESPACE_FLAGS;
unsigned int hash = xdiff_hash_string(l->line + l->indent_off,
l->len - l->indent_off, flags);
- hashmap_entry_init(&ret->ent, hash);
- ret->es = l;
- ret->next_line = NULL;
-
- return ret;
+ hashmap_entry_init(&s->ent, hash);
+ s->es = l;
}
-static void add_lines_to_move_detection(struct diff_options *o,
- struct hashmap *add_lines,
- struct hashmap *del_lines)
+struct moved_entry_list {
+ struct moved_entry *add, *del;
+};
+
+static struct moved_entry_list *add_lines_to_move_detection(struct diff_options *o,
+ struct mem_pool *entry_mem_pool)
{
struct moved_entry *prev_line = NULL;
-
+ struct mem_pool interned_pool;
+ struct hashmap interned_map;
+ struct moved_entry_list *entry_list = NULL;
+ size_t entry_list_alloc = 0;
+ unsigned id = 0;
int n;
+
+ hashmap_init(&interned_map, interned_diff_symbol_cmp, o, 8096);
+ mem_pool_init(&interned_pool, 1024 * 1024);
+
for (n = 0; n < o->emitted_symbols->nr; n++) {
- struct hashmap *hm;
- struct moved_entry *key;
+ struct interned_diff_symbol key;
+ struct emitted_diff_symbol *l = &o->emitted_symbols->buf[n];
+ struct interned_diff_symbol *s;
+ struct moved_entry *entry;
- switch (o->emitted_symbols->buf[n].s) {
- case DIFF_SYMBOL_PLUS:
- hm = add_lines;
- break;
- case DIFF_SYMBOL_MINUS:
- hm = del_lines;
- break;
- default:
+ if (l->s != DIFF_SYMBOL_PLUS && l->s != DIFF_SYMBOL_MINUS) {
prev_line = NULL;
continue;
}
if (o->color_moved_ws_handling &
COLOR_MOVED_WS_ALLOW_INDENTATION_CHANGE)
- fill_es_indent_data(&o->emitted_symbols->buf[n]);
- key = prepare_entry(o, n);
- if (prev_line && prev_line->es->s == o->emitted_symbols->buf[n].s)
- prev_line->next_line = key;
+ fill_es_indent_data(l);
- hashmap_add(hm, &key->ent);
- prev_line = key;
+ prepare_entry(o, l, &key);
+ s = hashmap_get_entry(&interned_map, &key, ent, &key.ent);
+ if (s) {
+ l->id = s->es->id;
+ } else {
+ l->id = id;
+ ALLOC_GROW_BY(entry_list, id, 1, entry_list_alloc);
+ hashmap_add(&interned_map,
+ memcpy(mem_pool_alloc(&interned_pool,
+ sizeof(key)),
+ &key, sizeof(key)));
+ }
+ entry = mem_pool_alloc(entry_mem_pool, sizeof(*entry));
+ entry->es = l;
+ entry->next_line = NULL;
+ if (prev_line && prev_line->es->s == l->s)
+ prev_line->next_line = entry;
+ prev_line = entry;
+ if (l->s == DIFF_SYMBOL_PLUS) {
+ entry->next_match = entry_list[l->id].add;
+ entry_list[l->id].add = entry;
+ } else {
+ entry->next_match = entry_list[l->id].del;
+ entry_list[l->id].del = entry;
+ }
}
+
+ hashmap_clear(&interned_map);
+ mem_pool_discard(&interned_pool, 0);
+
+ return entry_list;
}
static void pmb_advance_or_null(struct diff_options *o,
@@ -973,7 +1005,6 @@ static void pmb_advance_or_null(struct diff_options *o,
int *pmb_nr)
{
int i, j;
- unsigned flags = o->color_moved_ws_handling & XDF_WHITESPACE_FLAGS;
for (i = 0, j = 0; i < *pmb_nr; i++) {
int match;
@@ -986,9 +1017,8 @@ static void pmb_advance_or_null(struct diff_options *o,
match = cur &&
!cmp_in_block_with_wsd(cur, l, &pmb[i]);
else
- match = cur &&
- xdiff_compare_lines(cur->es->line, cur->es->len,
- l->line, l->len, flags);
+ match = cur && cur->es->id == l->id;
+
if (match) {
pmb[j] = pmb[i];
pmb[j++].match = cur;
@@ -998,7 +1028,6 @@ static void pmb_advance_or_null(struct diff_options *o,
}
static void fill_potential_moved_blocks(struct diff_options *o,
- struct hashmap *hm,
struct moved_entry *match,
struct emitted_diff_symbol *l,
struct moved_block **pmb_p,
@@ -1012,7 +1041,7 @@ static void fill_potential_moved_blocks(struct diff_options *o,
* The current line is the start of a new block.
* Setup the set of potential blocks.
*/
- hashmap_for_each_entry_from(hm, match, ent) {
+ for (; match; match = match->next_match) {
ALLOC_GROW(pmb, pmb_nr + 1, pmb_alloc);
if (o->color_moved_ws_handling &
COLOR_MOVED_WS_ALLOW_INDENTATION_CHANGE)
@@ -1067,8 +1096,7 @@ static int adjust_last_block(struct diff_options *o, int n, int block_length)
/* Find blocks of moved code, delegate actual coloring decision to helper */
static void mark_color_as_moved(struct diff_options *o,
- struct hashmap *add_lines,
- struct hashmap *del_lines)
+ struct moved_entry_list *entry_list)
{
struct moved_block *pmb = NULL; /* potentially moved blocks */
int pmb_nr = 0, pmb_alloc = 0;
@@ -1077,23 +1105,15 @@ static void mark_color_as_moved(struct diff_options *o,
for (n = 0; n < o->emitted_symbols->nr; n++) {
- struct hashmap *hm = NULL;
- struct moved_entry *key;
struct moved_entry *match = NULL;
struct emitted_diff_symbol *l = &o->emitted_symbols->buf[n];
switch (l->s) {
case DIFF_SYMBOL_PLUS:
- hm = del_lines;
- key = prepare_entry(o, n);
- match = hashmap_get_entry(hm, key, ent, NULL);
- free(key);
+ match = entry_list[l->id].del;
break;
case DIFF_SYMBOL_MINUS:
- hm = add_lines;
- key = prepare_entry(o, n);
- match = hashmap_get_entry(hm, key, ent, NULL);
- free(key);
+ match = entry_list[l->id].add;
break;
default:
flipped_block = 0;
@@ -1135,7 +1155,7 @@ static void mark_color_as_moved(struct diff_options *o,
*/
n -= block_length;
else
- fill_potential_moved_blocks(o, hm, match, l,
+ fill_potential_moved_blocks(o, match, l,
&pmb, &pmb_alloc,
&pmb_nr);
@@ -6253,20 +6273,18 @@ static void diff_flush_patch_all_file_pairs(struct diff_options *o)
if (o->emitted_symbols) {
if (o->color_moved) {
- struct hashmap add_lines, del_lines;
-
- hashmap_init(&del_lines, moved_entry_cmp, o, 0);
- hashmap_init(&add_lines, moved_entry_cmp, o, 0);
+ struct mem_pool entry_pool;
+ struct moved_entry_list *entry_list;
- add_lines_to_move_detection(o, &add_lines, &del_lines);
- mark_color_as_moved(o, &add_lines, &del_lines);
+ mem_pool_init(&entry_pool, 1024 * 1024);
+ entry_list = add_lines_to_move_detection(o,
+ &entry_pool);
+ mark_color_as_moved(o, entry_list);
if (o->color_moved == COLOR_MOVED_ZEBRA_DIM)
dim_moved_lines(o);
- hashmap_clear_and_free(&add_lines, struct moved_entry,
- ent);
- hashmap_clear_and_free(&del_lines, struct moved_entry,
- ent);
+ mem_pool_discard(&entry_pool, 0);
+ free(entry_list);
}
for (i = 0; i < esm.nr; i++)