| Message ID | 20190924010324.22619-13-e@80x24.org (mailing list archive) |
|---|---|
| State | New, archived |
| Headers | show |
| Series | [v2,01/19] diff: use hashmap_entry_init on moved_entry.ent | expand |
On 9/23/2019 9:03 PM, Eric Wong wrote: > 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 <e@80x24.org> > --- > diff.c | 21 +++++++++------------ > diffcore-rename.c | 14 +++++--------- > git-compat-util.h | 16 ++++++++++++++++ > hashmap.h | 40 ++++++++++++++++++++++++++++++++++------ > name-hash.c | 11 +++++------ > t/helper/test-hashmap.c | 12 +++++------- > 6 files changed, 74 insertions(+), 40 deletions(-) > > diff --git a/diff.c b/diff.c > index 663b5d01f8..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 = &match->ent; > > - 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) { Of course, my recommendation for using the initializer in the for(;;) is undone here, anyway. However, how does this work? Let's investigate the macro. > +/* > + * iterate @map starting from @var, where @var is a pointer of @type > + * and @member is the name of the "struct hashmap_entry" field in @type > + */ > +#define hashmap_for_each_entry_from(map, var, type, member) \ > + for (; \ > + var; \ > + var = hashmap_get_next_entry(map, var, type, member)) > + When reading this patch immediately after the previous change to use "ent" as the iteration variable, I was confused as to which entry was used for "var". The expansion of this macro more closely resembles the code without the previous patch. In fact, after pulling your code, I think the diff for PATCHes 10 & 11 together is cleaner than looking at the two together. I include that diff below. Thanks, -Stolee --- diff --git a/diff.c b/diff.c index 72d3c6aa19..66cdf4e9ca 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->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) ? @@ -1144,13 +1144,15 @@ 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); + 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); - match = hashmap_get(hm, &key->ent, NULL); + match = hashmap_get_entry(hm, key, NULL, + struct moved_entry, ent); free(key); break; default: @@ -1189,8 +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 (; match; match = hashmap_get_next(hm, - &match->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) { diff --git a/diffcore-rename.c b/diffcore-rename.c index 4670a40179..611b08f463 100644 --- a/diffcore-rename.c +++ b/diffcore-rename.c @@ -274,18 +274,17 @@ static int find_identical_files(struct hashmap *srcs, struct diff_options *options) { int renames = 0; - struct diff_filespec *target = rename_dst[dst_index].two; struct file_similarity *p, *best = NULL; int i = 100, best_score = -1; + unsigned int hash = hash_filespec(options->repo, target); /* * Find the best source match for specified destination. */ - p = hashmap_get_from_hash(srcs, - hash_filespec(options->repo, target), - NULL); - for (; p; p = hashmap_get_next(srcs, &p->entry)) { + p = hashmap_get_entry_from_hash(srcs, hash, NULL, + struct file_similarity, entry); + hashmap_for_each_entry_from(srcs, p, struct file_similarity, entry) { int score; struct diff_filespec *source = p->filespec; diff --git a/git-compat-util.h b/git-compat-util.h index 4cc2c8283a..e24510452a 100644 --- a/git-compat-util.h +++ b/git-compat-util.h @@ -1322,4 +1322,20 @@ void unleak_memory(const void *ptr, size_t len); #define container_of(ptr, type, member) \ ((type *) ((char *)(ptr) - offsetof(type, member))) + +/* + * helper function for `container_of_or_null' to avoid multiple + * evaluation of @ptr + */ +static inline void *container_of_or_null_offset(void *ptr, size_t offset) +{ + return ptr ? (char *)ptr - offset : NULL; +} + +/* + * like `container_of', but allows returned value to be NULL + */ +#define container_of_or_null(ptr, type, member) \ + (type *)container_of_or_null_offset(ptr, offsetof(type, member)) + #endif diff --git a/hashmap.c b/hashmap.c index 9b83e73d03..22bc7c5b3b 100644 --- a/hashmap.c +++ b/hashmap.c @@ -192,7 +192,7 @@ void *hashmap_get(const struct hashmap *map, const struct hashmap_entry *key, return *find_entry_ptr(map, key, keydata); } -void *hashmap_get_next(const struct hashmap *map, +struct hashmap_entry *hashmap_get_next(const struct hashmap *map, const struct hashmap_entry *entry) { struct hashmap_entry *e = entry->next; diff --git a/hashmap.h b/hashmap.h index cb630447bb..6d5f8685a8 100644 --- a/hashmap.h +++ b/hashmap.h @@ -59,11 +59,13 @@ * k.key = key; * * flags &= ~COMPARE_VALUE; - * e = hashmap_get(&map, &k, NULL); + * e = hashmap_get_entry(&map, &k, NULL, struct long2string, ent); * if (e) { * printf("first: %ld %s\n", e->key, e->value); - * while ((e = hashmap_get_next(&map, e))) + * while ((e = hashmap_get_next_entry(&map, e, + * struct long2string, ent))) { * printf("found more: %ld %s\n", e->key, e->value); + * } * } * } * @@ -320,7 +322,7 @@ static inline void *hashmap_get_from_hash(const struct hashmap *map, * `entry` is the hashmap_entry to start the search from, obtained via a previous * call to `hashmap_get` or `hashmap_get_next`. */ -void *hashmap_get_next(const struct hashmap *map, +struct hashmap_entry *hashmap_get_next(const struct hashmap *map, const struct hashmap_entry *entry); /* @@ -383,6 +385,36 @@ static inline void *hashmap_iter_first(struct hashmap *map, return hashmap_iter_next(iter); } +/* + * returns a @pointer of @type matching @keyvar, or NULL if nothing found. + * @keyvar is a pointer of @type + * @member is the name of the "struct hashmap_entry" field in @type + */ +#define hashmap_get_entry(map, keyvar, keydata, type, member) \ + container_of_or_null(hashmap_get(map, &(keyvar)->member, keydata), \ + type, member) + +#define hashmap_get_entry_from_hash(map, hash, keydata, type, member) \ + container_of_or_null(hashmap_get_from_hash(map, hash, keydata), \ + type, member) +/* + * returns the next equal @type pointer to @var, or NULL if not found. + * @var is a pointer of @type + * @member is the name of the "struct hashmap_entry" field in @type + */ +#define hashmap_get_next_entry(map, var, type, member) \ + container_of_or_null(hashmap_get_next(map, &(var)->member), \ + type, member) + +/* + * iterate @map starting from @var, where @var is a pointer of @type + * and @member is the name of the "struct hashmap_entry" field in @type + */ +#define hashmap_for_each_entry_from(map, var, type, member) \ + for (; \ + var; \ + var = hashmap_get_next_entry(map, var, type, member)) + /* * Disable item counting and automatic rehashing when adding/removing items. * diff --git a/name-hash.c b/name-hash.c index 44d788f1ce..73b83adf3d 100644 --- a/name-hash.c +++ b/name-hash.c @@ -702,15 +702,16 @@ void adjust_dirname_case(struct index_state *istate, char *name) struct cache_entry *index_file_exists(struct index_state *istate, const char *name, int namelen, int icase) { struct cache_entry *ce; + unsigned int hash = memihash(name, namelen); lazy_init_name_hash(istate); - ce = hashmap_get_from_hash(&istate->name_hash, - memihash(name, namelen), NULL); - while (ce) { + ce = hashmap_get_entry_from_hash(&istate->name_hash, hash, NULL, + struct cache_entry, ent); + hashmap_for_each_entry_from(&istate->name_hash, ce, + struct cache_entry, ent) { if (same_name(ce, name, namelen, icase)) return ce; - ce = hashmap_get_next(&istate->name_hash, &ce->ent); } return NULL; } diff --git a/t/helper/test-hashmap.c b/t/helper/test-hashmap.c index de2bd083b9..e82cbfdee2 100644 --- a/t/helper/test-hashmap.c +++ b/t/helper/test-hashmap.c @@ -194,16 +194,16 @@ int cmd__hashmap(int argc, const char **argv) free(entry); } else if (!strcmp("get", cmd) && p1) { - /* lookup entry in hashmap */ - entry = hashmap_get_from_hash(&map, hash, p1); + entry = hashmap_get_entry_from_hash(&map, hash, p1, + struct test_entry, ent); /* print result */ if (!entry) puts("NULL"); - while (entry) { + hashmap_for_each_entry_from(&map, entry, + struct test_entry, ent) { puts(get_value(entry)); - entry = hashmap_get_next(&map, &entry->ent); } } else if (!strcmp("remove", cmd) && p1) {
diff --git a/diff.c b/diff.c index 663b5d01f8..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 = &match->ent; - 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) { 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) { diff --git a/diffcore-rename.c b/diffcore-rename.c index 71aa240a68..611b08f463 100644 --- a/diffcore-rename.c +++ b/diffcore-rename.c @@ -274,23 +274,19 @@ static int find_identical_files(struct hashmap *srcs, struct diff_options *options) { int renames = 0; - struct hashmap_entry *ent; struct diff_filespec *target = rename_dst[dst_index].two; struct file_similarity *p, *best = NULL; int i = 100, best_score = -1; + unsigned int hash = hash_filespec(options->repo, target); /* * Find the best source match for specified destination. */ - ent = hashmap_get_from_hash(srcs, - hash_filespec(options->repo, target), - NULL); - for (; ent; ent = hashmap_get_next(srcs, ent)) { + p = hashmap_get_entry_from_hash(srcs, hash, NULL, + struct file_similarity, entry); + hashmap_for_each_entry_from(srcs, p, struct file_similarity, entry) { int score; - struct diff_filespec *source; - - p = container_of(ent, struct file_similarity, entry); - source = p->filespec; + struct diff_filespec *source = p->filespec; /* False hash collision? */ if (!oideq(&source->oid, &target->oid)) diff --git a/git-compat-util.h b/git-compat-util.h index 4cc2c8283a..e24510452a 100644 --- a/git-compat-util.h +++ b/git-compat-util.h @@ -1322,4 +1322,20 @@ void unleak_memory(const void *ptr, size_t len); #define container_of(ptr, type, member) \ ((type *) ((char *)(ptr) - offsetof(type, member))) + +/* + * helper function for `container_of_or_null' to avoid multiple + * evaluation of @ptr + */ +static inline void *container_of_or_null_offset(void *ptr, size_t offset) +{ + return ptr ? (char *)ptr - offset : NULL; +} + +/* + * like `container_of', but allows returned value to be NULL + */ +#define container_of_or_null(ptr, type, member) \ + (type *)container_of_or_null_offset(ptr, offsetof(type, member)) + #endif diff --git a/hashmap.h b/hashmap.h index eb38587a63..6d5f8685a8 100644 --- a/hashmap.h +++ b/hashmap.h @@ -55,17 +55,15 @@ * * if (!strcmp("print_all_by_key", action)) { * struct long2string k, *e; - * struct hashmap_entry *ent; * hashmap_entry_init(&k->ent, memhash(&key, sizeof(long))); * k.key = key; * * flags &= ~COMPARE_VALUE; - * ent = hashmap_get(&map, &k, NULL); - * if (ent) { - * e = container_of(ent, struct long2string, ent); + * e = hashmap_get_entry(&map, &k, NULL, struct long2string, ent); + * if (e) { * printf("first: %ld %s\n", e->key, e->value); - * while ((ent = hashmap_get_next(&map, ent))) { - * e = container_of(ent, struct long2string, ent); + * while ((e = hashmap_get_next_entry(&map, e, + * struct long2string, ent))) { * printf("found more: %ld %s\n", e->key, e->value); * } * } @@ -387,6 +385,36 @@ static inline void *hashmap_iter_first(struct hashmap *map, return hashmap_iter_next(iter); } +/* + * returns a @pointer of @type matching @keyvar, or NULL if nothing found. + * @keyvar is a pointer of @type + * @member is the name of the "struct hashmap_entry" field in @type + */ +#define hashmap_get_entry(map, keyvar, keydata, type, member) \ + container_of_or_null(hashmap_get(map, &(keyvar)->member, keydata), \ + type, member) + +#define hashmap_get_entry_from_hash(map, hash, keydata, type, member) \ + container_of_or_null(hashmap_get_from_hash(map, hash, keydata), \ + type, member) +/* + * returns the next equal @type pointer to @var, or NULL if not found. + * @var is a pointer of @type + * @member is the name of the "struct hashmap_entry" field in @type + */ +#define hashmap_get_next_entry(map, var, type, member) \ + container_of_or_null(hashmap_get_next(map, &(var)->member), \ + type, member) + +/* + * iterate @map starting from @var, where @var is a pointer of @type + * and @member is the name of the "struct hashmap_entry" field in @type + */ +#define hashmap_for_each_entry_from(map, var, type, member) \ + for (; \ + var; \ + var = hashmap_get_next_entry(map, var, type, member)) + /* * Disable item counting and automatic rehashing when adding/removing items. * diff --git a/name-hash.c b/name-hash.c index dbacb34f50..73b83adf3d 100644 --- a/name-hash.c +++ b/name-hash.c @@ -702,17 +702,16 @@ void adjust_dirname_case(struct index_state *istate, char *name) struct cache_entry *index_file_exists(struct index_state *istate, const char *name, int namelen, int icase) { struct cache_entry *ce; - struct hashmap_entry *ent; + unsigned int hash = memihash(name, namelen); lazy_init_name_hash(istate); - ent = hashmap_get_from_hash(&istate->name_hash, - memihash(name, namelen), NULL); - while (ent) { - ce = container_of(ent, struct cache_entry, ent); + ce = hashmap_get_entry_from_hash(&istate->name_hash, hash, NULL, + struct cache_entry, ent); + hashmap_for_each_entry_from(&istate->name_hash, ce, + struct cache_entry, ent) { if (same_name(ce, name, namelen, icase)) return ce; - ent = hashmap_get_next(&istate->name_hash, ent); } return NULL; } diff --git a/t/helper/test-hashmap.c b/t/helper/test-hashmap.c index d85b8dc58e..e82cbfdee2 100644 --- a/t/helper/test-hashmap.c +++ b/t/helper/test-hashmap.c @@ -194,18 +194,16 @@ int cmd__hashmap(int argc, const char **argv) free(entry); } else if (!strcmp("get", cmd) && p1) { - struct hashmap_entry *e; - /* lookup entry in hashmap */ - e = hashmap_get_from_hash(&map, hash, p1); + entry = hashmap_get_entry_from_hash(&map, hash, p1, + struct test_entry, ent); /* print result */ - if (!e) + if (!entry) puts("NULL"); - while (e) { - entry = container_of(e, struct test_entry, ent); + hashmap_for_each_entry_from(&map, entry, + struct test_entry, ent) { puts(get_value(entry)); - e = hashmap_get_next(&map, e); } } else if (!strcmp("remove", cmd) && p1) {
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 <e@80x24.org> --- diff.c | 21 +++++++++------------ diffcore-rename.c | 14 +++++--------- git-compat-util.h | 16 ++++++++++++++++ hashmap.h | 40 ++++++++++++++++++++++++++++++++++------ name-hash.c | 11 +++++------ t/helper/test-hashmap.c | 12 +++++------- 6 files changed, 74 insertions(+), 40 deletions(-)