From e010a41216efd85eacc4c0711ea405de4fb20526 Mon Sep 17 00:00:00 2001 From: Eric Wong Date: Sun, 6 Oct 2019 23:30:24 +0000 Subject: diff: use hashmap_entry_init on moved_entry.ent Otherwise, the hashmap_entry.next field appears to remain uninitialized, which can lead to problems when add_lines_to_move_detection calls hashmap_add. I found this through manual inspection when converting hashmap_add callers to take "struct hashmap_entry *". Signed-off-by: Eric Wong Reviewed-by: Derrick Stolee Signed-off-by: Junio C Hamano --- diff.c | 3 ++- 1 file changed, 2 insertions(+), 1 deletion(-) (limited to 'diff.c') diff --git a/diff.c b/diff.c index efe42b341a..02491ee684 100644 --- a/diff.c +++ b/diff.c @@ -964,8 +964,9 @@ static struct moved_entry *prepare_entry(struct diff_options *o, 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->len, flags); - ret->ent.hash = xdiff_hash_string(l->line, l->len, flags); + hashmap_entry_init(&ret->ent, hash); ret->es = l; ret->next_line = NULL; -- cgit v1.2.3 From f6eb6bdcf2719defc3d38e0e2712fa3e18d29e91 Mon Sep 17 00:00:00 2001 From: Eric Wong Date: Sun, 6 Oct 2019 23:30:28 +0000 Subject: hashmap_get_next takes "const struct hashmap_entry *" This is less error-prone than "const void *" as the compiler now detects invalid types being passed. Signed-off-by: Eric Wong Reviewed-by: Derrick Stolee Signed-off-by: Junio C Hamano --- diff.c | 5 +++-- 1 file changed, 3 insertions(+), 2 deletions(-) (limited to 'diff.c') diff --git a/diff.c b/diff.c index 02491ee684..1168f0cbb9 100644 --- a/diff.c +++ b/diff.c @@ -1036,7 +1036,7 @@ static void pmb_advance_or_null_multi_match(struct diff_options *o, int i; char *got_match = xcalloc(1, pmb_nr); - for (; match; match = hashmap_get_next(hm, match)) { + for (; match; match = hashmap_get_next(hm, &match->ent)) { for (i = 0; i < pmb_nr; i++) { struct moved_entry *prev = pmb[i].match; struct moved_entry *cur = (prev && prev->next_line) ? @@ -1189,7 +1189,8 @@ static void mark_color_as_moved(struct diff_options *o, * The current line is the start of a new block. * Setup the set of potential blocks. */ - for (; match; match = hashmap_get_next(hm, match)) { + for (; match; match = hashmap_get_next(hm, + &match->ent)) { ALLOC_GROW(pmb, pmb_nr + 1, pmb_alloc); if (o->color_moved_ws_handling & COLOR_MOVED_WS_ALLOW_INDENTATION_CHANGE) { -- cgit v1.2.3 From b94e5c1df674eb4ec8fdeaaae1ad8df552cb5d70 Mon Sep 17 00:00:00 2001 From: Eric Wong Date: Sun, 6 Oct 2019 23:30:29 +0000 Subject: hashmap_add takes "struct hashmap_entry *" This is less error-prone than "void *" as the compiler now detects invalid types being passed. Signed-off-by: Eric Wong Reviewed-by: Derrick Stolee Signed-off-by: Junio C Hamano --- diff.c | 2 +- 1 file changed, 1 insertion(+), 1 deletion(-) (limited to 'diff.c') diff --git a/diff.c b/diff.c index 1168f0cbb9..cc7f06d10d 100644 --- a/diff.c +++ b/diff.c @@ -1003,7 +1003,7 @@ static void add_lines_to_move_detection(struct diff_options *o, if (prev_line && prev_line->es->s == o->emitted_symbols->buf[n].s) prev_line->next_line = key; - hashmap_add(hm, key); + hashmap_add(hm, &key->ent); prev_line = key; } } -- cgit v1.2.3 From b6c5241606e67b57470e86ccf547d4ab90008a1d Mon Sep 17 00:00:00 2001 From: Eric Wong Date: Sun, 6 Oct 2019 23:30:30 +0000 Subject: hashmap_get takes "const struct hashmap_entry *" This is less error-prone than "const void *" as the compiler now detects invalid types being passed. Signed-off-by: Eric Wong Reviewed-by: Derrick Stolee Signed-off-by: Junio C Hamano --- diff.c | 4 ++-- 1 file changed, 2 insertions(+), 2 deletions(-) (limited to 'diff.c') diff --git a/diff.c b/diff.c index cc7f06d10d..72d3c6aa19 100644 --- a/diff.c +++ b/diff.c @@ -1144,13 +1144,13 @@ static void mark_color_as_moved(struct diff_options *o, case DIFF_SYMBOL_PLUS: hm = del_lines; key = prepare_entry(o, n); - match = hashmap_get(hm, key, NULL); + match = hashmap_get(hm, &key->ent, NULL); free(key); break; case DIFF_SYMBOL_MINUS: hm = add_lines; key = prepare_entry(o, n); - match = hashmap_get(hm, key, NULL); + match = hashmap_get(hm, &key->ent, NULL); free(key); break; default: -- cgit v1.2.3 From 6bcbdfb277bdc81b5ad6996b3fb005382a35c2ee Mon Sep 17 00:00:00 2001 From: Eric Wong Date: Sun, 6 Oct 2019 23:30:34 +0000 Subject: hashmap_get_next returns "struct hashmap_entry *" This is a step towards removing the requirement for hashmap_entry being the first field of a struct. Signed-off-by: Eric Wong Reviewed-by: Derrick Stolee Signed-off-by: Junio C Hamano --- diff.c | 19 ++++++++++++------- 1 file changed, 12 insertions(+), 7 deletions(-) (limited to 'diff.c') diff --git a/diff.c b/diff.c index 72d3c6aa19..0978814086 100644 --- a/diff.c +++ b/diff.c @@ -1035,8 +1035,10 @@ static void pmb_advance_or_null_multi_match(struct diff_options *o, { int i; char *got_match = xcalloc(1, pmb_nr); + struct hashmap_entry *ent; - for (; match; match = hashmap_get_next(hm, &match->ent)) { + for (ent = &match->ent; ent; ent = hashmap_get_next(hm, ent)) { + match = container_of(ent, struct moved_entry, ent); for (i = 0; i < pmb_nr; i++) { struct moved_entry *prev = pmb[i].match; struct moved_entry *cur = (prev && prev->next_line) ? @@ -1135,8 +1137,9 @@ static void mark_color_as_moved(struct diff_options *o, for (n = 0; n < o->emitted_symbols->nr; n++) { struct hashmap *hm = NULL; + struct hashmap_entry *ent = NULL; struct moved_entry *key; - struct moved_entry *match = NULL; + struct moved_entry *match; struct emitted_diff_symbol *l = &o->emitted_symbols->buf[n]; enum diff_symbol last_symbol = 0; @@ -1144,20 +1147,20 @@ static void mark_color_as_moved(struct diff_options *o, case DIFF_SYMBOL_PLUS: hm = del_lines; key = prepare_entry(o, n); - match = hashmap_get(hm, &key->ent, NULL); + ent = hashmap_get(hm, &key->ent, NULL); free(key); break; case DIFF_SYMBOL_MINUS: hm = add_lines; key = prepare_entry(o, n); - match = hashmap_get(hm, &key->ent, NULL); + ent = hashmap_get(hm, &key->ent, NULL); free(key); break; default: flipped_block = 0; } - if (!match) { + if (!ent) { int i; adjust_last_block(o, n, block_length); @@ -1169,6 +1172,7 @@ static void mark_color_as_moved(struct diff_options *o, last_symbol = l->s; continue; } + match = container_of(ent, struct moved_entry, ent); if (o->color_moved == COLOR_MOVED_PLAIN) { last_symbol = l->s; @@ -1189,8 +1193,9 @@ static void mark_color_as_moved(struct diff_options *o, * The current line is the start of a new block. * Setup the set of potential blocks. */ - for (; match; match = hashmap_get_next(hm, - &match->ent)) { + for (; ent; ent = hashmap_get_next(hm, ent)) { + match = container_of(ent, struct moved_entry, + ent); ALLOC_GROW(pmb, pmb_nr + 1, pmb_alloc); if (o->color_moved_ws_handling & COLOR_MOVED_WS_ALLOW_INDENTATION_CHANGE) { -- cgit v1.2.3 From f0e63c41139f8982add435536d39aff6f3d4ca98 Mon Sep 17 00:00:00 2001 From: Eric Wong Date: Sun, 6 Oct 2019 23:30:35 +0000 Subject: hashmap: use *_entry APIs to wrap container_of Using `container_of' can be verbose and choosing names for intermediate "struct hashmap_entry" pointers is a hard problem. So introduce "*_entry" APIs inspired by similar linked-list APIs in the Linux kernel. Unfortunately, `__typeof__' is not portable C, so we need an extra parameter to specify the type. Signed-off-by: Eric Wong Reviewed-by: Derrick Stolee Signed-off-by: Junio C Hamano --- diff.c | 21 +++++++++------------ 1 file changed, 9 insertions(+), 12 deletions(-) (limited to 'diff.c') diff --git a/diff.c b/diff.c index 0978814086..66cdf4e9ca 100644 --- a/diff.c +++ b/diff.c @@ -1035,10 +1035,8 @@ static void pmb_advance_or_null_multi_match(struct diff_options *o, { int i; char *got_match = xcalloc(1, pmb_nr); - struct hashmap_entry *ent; - for (ent = &match->ent; ent; ent = hashmap_get_next(hm, ent)) { - match = container_of(ent, struct moved_entry, ent); + hashmap_for_each_entry_from(hm, match, struct moved_entry, ent) { for (i = 0; i < pmb_nr; i++) { struct moved_entry *prev = pmb[i].match; struct moved_entry *cur = (prev && prev->next_line) ? @@ -1137,9 +1135,8 @@ static void mark_color_as_moved(struct diff_options *o, for (n = 0; n < o->emitted_symbols->nr; n++) { struct hashmap *hm = NULL; - struct hashmap_entry *ent = NULL; struct moved_entry *key; - struct moved_entry *match; + struct moved_entry *match = NULL; struct emitted_diff_symbol *l = &o->emitted_symbols->buf[n]; enum diff_symbol last_symbol = 0; @@ -1147,20 +1144,22 @@ static void mark_color_as_moved(struct diff_options *o, case DIFF_SYMBOL_PLUS: hm = del_lines; key = prepare_entry(o, n); - ent = hashmap_get(hm, &key->ent, NULL); + match = hashmap_get_entry(hm, key, NULL, + struct moved_entry, ent); free(key); break; case DIFF_SYMBOL_MINUS: hm = add_lines; key = prepare_entry(o, n); - ent = hashmap_get(hm, &key->ent, NULL); + match = hashmap_get_entry(hm, key, NULL, + struct moved_entry, ent); free(key); break; default: flipped_block = 0; } - if (!ent) { + if (!match) { int i; adjust_last_block(o, n, block_length); @@ -1172,7 +1171,6 @@ static void mark_color_as_moved(struct diff_options *o, last_symbol = l->s; continue; } - match = container_of(ent, struct moved_entry, ent); if (o->color_moved == COLOR_MOVED_PLAIN) { last_symbol = l->s; @@ -1193,9 +1191,8 @@ static void mark_color_as_moved(struct diff_options *o, * The current line is the start of a new block. * Setup the set of potential blocks. */ - for (; ent; ent = hashmap_get_next(hm, ent)) { - match = container_of(ent, struct moved_entry, - ent); + hashmap_for_each_entry_from(hm, match, + struct moved_entry, ent) { ALLOC_GROW(pmb, pmb_nr + 1, pmb_alloc); if (o->color_moved_ws_handling & COLOR_MOVED_WS_ALLOW_INDENTATION_CHANGE) { -- cgit v1.2.3 From 939af16eac1608766273d3971598dbcc4fe09928 Mon Sep 17 00:00:00 2001 From: Eric Wong Date: Sun, 6 Oct 2019 23:30:37 +0000 Subject: hashmap_cmp_fn takes hashmap_entry params Another step in eliminating the requirement of hashmap_entry being the first member of a struct. Signed-off-by: Eric Wong Reviewed-by: Derrick Stolee Signed-off-by: Junio C Hamano --- diff.c | 12 +++++++----- 1 file changed, 7 insertions(+), 5 deletions(-) (limited to 'diff.c') diff --git a/diff.c b/diff.c index 66cdf4e9ca..5eaf689fcc 100644 --- a/diff.c +++ b/diff.c @@ -933,16 +933,18 @@ static int cmp_in_block_with_wsd(const struct diff_options *o, } static int moved_entry_cmp(const void *hashmap_cmp_fn_data, - const void *entry, - const void *entry_or_key, + 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 moved_entry *a = entry; - const struct moved_entry *b = entry_or_key; + const struct moved_entry *a, *b; unsigned flags = diffopt->color_moved_ws_handling & XDF_WHITESPACE_FLAGS; + a = container_of(eptr, const struct moved_entry, ent); + b = container_of(entry_or_key, const struct moved_entry, ent); + if (diffopt->color_moved_ws_handling & COLOR_MOVED_WS_ALLOW_INDENTATION_CHANGE) /* @@ -1019,7 +1021,7 @@ static void pmb_advance_or_null(struct diff_options *o, struct moved_entry *prev = pmb[i].match; struct moved_entry *cur = (prev && prev->next_line) ? prev->next_line : NULL; - if (cur && !hm->cmpfn(o, cur, match, NULL)) { + if (cur && !hm->cmpfn(o, &cur->ent, &match->ent, NULL)) { pmb[i].match = cur; } else { pmb[i].match = NULL; -- cgit v1.2.3 From c8e424c9c94d97b18cd335be17f32a8ce94a5b7f Mon Sep 17 00:00:00 2001 From: Eric Wong Date: Sun, 6 Oct 2019 23:30:40 +0000 Subject: hashmap: introduce hashmap_free_entries `hashmap_free_entries' behaves like `container_of' and passes the offset of the hashmap_entry struct to the internal `hashmap_free_' function, allowing the function to free any struct pointer regardless of where the hashmap_entry field is located. `hashmap_free' no longer takes any arguments aside from the hashmap itself. Signed-off-by: Eric Wong Reviewed-by: Derrick Stolee Signed-off-by: Junio C Hamano --- diff.c | 6 ++++-- 1 file changed, 4 insertions(+), 2 deletions(-) (limited to 'diff.c') diff --git a/diff.c b/diff.c index 5eaf689fcc..f94d9f96af 100644 --- a/diff.c +++ b/diff.c @@ -6236,8 +6236,10 @@ static void diff_flush_patch_all_file_pairs(struct diff_options *o) if (o->color_moved == COLOR_MOVED_ZEBRA_DIM) dim_moved_lines(o); - hashmap_free(&add_lines, 1); - hashmap_free(&del_lines, 1); + hashmap_free_entries(&add_lines, struct moved_entry, + ent); + hashmap_free_entries(&del_lines, struct moved_entry, + ent); } for (i = 0; i < esm.nr; i++) -- cgit v1.2.3 From 23dee69f53cf5024ca79e0b707dcb03c63f33bef Mon Sep 17 00:00:00 2001 From: Eric Wong Date: Sun, 6 Oct 2019 23:30:41 +0000 Subject: OFFSETOF_VAR macro to simplify hashmap iterators While we cannot rely on a `__typeof__' operator being portable to use with `offsetof'; we can calculate the pointer offset using an existing pointer and the address of a member using pointer arithmetic for compilers without `__typeof__'. This allows us to simplify usage of hashmap iterator macros by not having to specify a type when a pointer of that type is already given. In the future, list iterator macros (e.g. list_for_each_entry) may also be implemented using OFFSETOF_VAR to save hackers the trouble of using container_of/list_entry macros and without relying on non-portable `__typeof__'. v3: use `__typeof__' to avoid clang warnings Signed-off-by: Eric Wong Reviewed-by: Derrick Stolee Signed-off-by: Junio C Hamano --- diff.c | 5 ++--- 1 file changed, 2 insertions(+), 3 deletions(-) (limited to 'diff.c') diff --git a/diff.c b/diff.c index f94d9f96af..051de9832d 100644 --- a/diff.c +++ b/diff.c @@ -1038,7 +1038,7 @@ static void pmb_advance_or_null_multi_match(struct diff_options *o, int i; char *got_match = xcalloc(1, pmb_nr); - hashmap_for_each_entry_from(hm, match, struct moved_entry, ent) { + hashmap_for_each_entry_from(hm, match, ent) { for (i = 0; i < pmb_nr; i++) { struct moved_entry *prev = pmb[i].match; struct moved_entry *cur = (prev && prev->next_line) ? @@ -1193,8 +1193,7 @@ static void mark_color_as_moved(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, - struct moved_entry, ent) { + hashmap_for_each_entry_from(hm, match, ent) { ALLOC_GROW(pmb, pmb_nr + 1, pmb_alloc); if (o->color_moved_ws_handling & COLOR_MOVED_WS_ALLOW_INDENTATION_CHANGE) { -- cgit v1.2.3 From 404ab78e39fc74c4eb604b6003642ed264f687a6 Mon Sep 17 00:00:00 2001 From: Eric Wong Date: Sun, 6 Oct 2019 23:30:42 +0000 Subject: hashmap: remove type arg from hashmap_{get,put,remove}_entry Since these macros already take a `keyvar' pointer of a known type, we can rely on OFFSETOF_VAR to get the correct offset without relying on non-portable `__typeof__' and `offsetof'. Argument order is also rearranged, so `keyvar' and `member' are sequential as they are used as: `keyvar->member' Signed-off-by: Eric Wong Reviewed-by: Derrick Stolee Signed-off-by: Junio C Hamano --- diff.c | 6 ++---- 1 file changed, 2 insertions(+), 4 deletions(-) (limited to 'diff.c') diff --git a/diff.c b/diff.c index 051de9832d..a9ecb93af3 100644 --- a/diff.c +++ b/diff.c @@ -1146,15 +1146,13 @@ static void mark_color_as_moved(struct diff_options *o, case DIFF_SYMBOL_PLUS: hm = del_lines; key = prepare_entry(o, n); - match = hashmap_get_entry(hm, key, NULL, - struct moved_entry, ent); + match = hashmap_get_entry(hm, key, ent, NULL); free(key); break; case DIFF_SYMBOL_MINUS: hm = add_lines; key = prepare_entry(o, n); - match = hashmap_get_entry(hm, key, NULL, - struct moved_entry, ent); + match = hashmap_get_entry(hm, key, ent, NULL); free(key); break; default: -- cgit v1.2.3