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 --git a/diff.c b/diff.c index 0978814..66cdf4e 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) { diff --git a/diffcore-rename.c b/diffcore-rename.c index 71aa240..611b08f 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 4cc2c82..4a23b90 100644 --- a/git-compat-util.h +++ b/git-compat-util.h @@ -1322,4 +1322,19 @@ 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 21bc8af..cd42dcc 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); * } * } @@ -388,6 +386,36 @@ static inline void *hashmap_iter_first(struct hashmap *map, } /* + * 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. * * Normally, the hashmap keeps track of the number of items in the map diff --git a/name-hash.c b/name-hash.c index dbacb34..73b83ad 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 d85b8dc..e82cbfd 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) { -- cgit v0.10.2-6-g49f6