git/list[1] front-page[2] threads[3] people[4] search[5] about
 

Re: [PATCH v2 12/19] hashmap: use *_entry APIs to wrap container_of

From
Derrick Stolee <stolee@gmail.com>
Date
Sep 25, 2019, 13:15 UTC
Message-ID
<610f3f40-ebff-c2e5-a210-ef3628193e81@gmail.com>
In-Reply-To
<20190924010324.22619-13-e@80x24.org>
On 9/23/2019 9:03 PM, Eric Wong wrote:
Show 31 quoted lines
> 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.
Show 9 quoted lines
> +/*
> + * 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) {
Previous: Eric WongNext: Eric Wong
Message 52 of 71 in “hashmap: bugfixes, safety fixes, and WIP improvements”
  1. 00/11 hashmap: bugfixes, safety fixes, and WIP improvementsEric Wong, Aug 26, 2019
  2. 01/11 diff: use hashmap_entry_init on moved_entry.entEric Wong, Aug 26, 2019
  3. Derrick StoleeAug 27, 2019
  4. 02/11 packfile: use hashmap_entry in delta_base_cache_entryEric Wong, Aug 26, 2019
  5. 03/11 hashmap_entry_init takes "struct hashmap_entry *"Eric Wong, Aug 26, 2019
  6. Derrick StoleeAug 27, 2019
  7. Johannes SchindelinAug 28, 2019
  8. Eric WongAug 30, 2019
  9. Johannes SchindelinSep 2, 2019
  10. 04/11 hashmap_entry: detect improper initializationEric Wong, Aug 26, 2019
  11. Johannes SchindelinAug 27, 2019
  12. Eric WongAug 27, 2019
  13. Junio C HamanoAug 27, 2019
  14. Johannes SchindelinAug 28, 2019
  15. Phillip WoodAug 28, 2019
  16. Eric WongAug 30, 2019
  17. 04/11 coccicheck: detect hashmap_entry.hash assignmentEric Wong, Sep 8, 2019
  18. Junio C HamanoSep 9, 2019
  19. 05/11 hashmap_get_next takes "const struct hashmap_entry *"Eric Wong, Aug 26, 2019
  20. 06/11 hashmap_add takes "struct hashmap_entry *"Eric Wong, Aug 26, 2019
  21. 07/11 hashmap_get takes "const struct hashmap_entry *"Eric Wong, Aug 26, 2019
  22. 08/11 hashmap_remove takes "const struct hashmap_entry *"Eric Wong, Aug 26, 2019
  23. 09/11 hashmap_put takes "struct hashmap_entry *"Eric Wong, Aug 26, 2019
  24. 10/11 introduce container_of macroEric Wong, Aug 26, 2019
  25. Derrick StoleeAug 27, 2019
  26. Phillip WoodAug 28, 2019
  27. Eric WongAug 30, 2019
  28. 11/11 hashmap_get_next returns "struct hashmap_entry *"Eric Wong, Aug 26, 2019
  29. Derrick StoleeAug 27, 2019
  30. Eric WongAug 30, 2019
  31. 00/19 hashmap bug/safety/ease-of-use fixesEric Wong, Sep 24, 2019
  32. 01/19 diff: use hashmap_entry_init on moved_entry.entEric Wong, Sep 24, 2019
  33. 02/19 coccicheck: detect hashmap_entry.hash assignmentEric Wong, Sep 24, 2019
  34. Derrick StoleeSep 25, 2019
  35. 03/19 packfile: use hashmap_entry in delta_base_cache_entryEric Wong, Sep 24, 2019
  36. 04/19 hashmap_entry_init takes "struct hashmap_entry *"Eric Wong, Sep 24, 2019
  37. Derrick StoleeSep 25, 2019
  38. 05/19 hashmap_get_next takes "const struct hashmap_entry *"Eric Wong, Sep 24, 2019
  39. 06/19 hashmap_add takes "struct hashmap_entry *"Eric Wong, Sep 24, 2019
  40. 07/19 hashmap_get takes "const struct hashmap_entry *"Eric Wong, Sep 24, 2019
  41. Derrick StoleeSep 25, 2019
  42. Eric WongSep 30, 2019
  43. 08/19 hashmap_remove takes "const struct hashmap_entry *"Eric Wong, Sep 24, 2019
  44. Derrick StoleeSep 25, 2019
  45. 09/19 hashmap_put takes "struct hashmap_entry *"Eric Wong, Sep 24, 2019
  46. 10/19 introduce container_of macroEric Wong, Sep 24, 2019
  47. Derrick StoleeSep 25, 2019
  48. Eric WongSep 30, 2019
  49. 11/19 hashmap_get_next returns "struct hashmap_entry *"Eric Wong, Sep 24, 2019
  50. Derrick StoleeSep 25, 2019
  51. 12/19 hashmap: use *_entry APIs to wrap container_ofEric Wong, Sep 24, 2019
  52. Derrick StoleeSep 25, 2019
  53. 13/19 hashmap_get{,_from_hash} return "struct hashmap_entry *"Eric Wong, Sep 24, 2019
  54. 14/19 hashmap_cmp_fn takes hashmap_entry paramsEric Wong, Sep 24, 2019
  55. 15/19 hashmap: use *_entry APIs for iterationEric Wong, Sep 24, 2019
  56. 16/19 hashmap: hashmap_{put,remove} return hashmap_entry *Eric Wong, Sep 24, 2019
  57. 17/19 hashmap: introduce hashmap_free_entriesEric Wong, Sep 24, 2019
  58. 18/19 OFFSETOF_VAR macro to simplify hashmap iteratorsEric Wong, Sep 24, 2019
  59. Junio C HamanoSep 30, 2019
  60. Junio C HamanoOct 4, 2019
  61. Eric WongOct 4, 2019
  62. Junio C HamanoOct 4, 2019
  63. Eric WongOct 4, 2019
  64. Junio C HamanoOct 6, 2019
  65. 19/19 hashmap: remove type arg from hashmap_{get,put,remove}_entryEric Wong, Sep 24, 2019
  66. Derrick StoleeSep 25, 2019
  67. Derrick StoleeSep 25, 2019
  68. Johannes SchindelinSep 26, 2019
  69. Eric WongSep 30, 2019
  70. Phillip WoodSep 26, 2019
  71. Junio C HamanoSep 29, 2019

Read the whole thread, see it on lore, or plain text.

$ cat FOOTERMessages come from the public archive at lore.kernel.org/git, fetched every hour. The front page is chosen and written each morning by an AI editor and can be wrong; the threads themselves are the record. About and API. For agents: an MCP server at https://gitlist.dev/mcp, and any thread, story or person page as Markdown by adding .md to its URL (or sending Accept: text/markdown). Details in /llms.txt.