From: Eric Wong <e@80x24.org>
To: Junio C Hamano <gitster@pobox.com>
Cc: git@vger.kernel.org, Derrick Stolee <stolee@gmail.com>,
Johannes Schindelin <Johannes.Schindelin@gmx.de>,
Phillip Wood <phillip.wood123@gmail.com>
Subject: [PATCH v3 00/20] hashmap bug/safety/ease-of-use fixes
Date: Sun, 6 Oct 2019 23:30:23 +0000 [thread overview]
Message-ID: <20191006233043.3516-1-e@80x24.org> (raw)
v3 changes:
- use __typeof__ to avoid invalid clang warning on uninitialized var
- formatting fixes recommended by Stolee
- add Reviewed-by for Stolee
- add patch 20 to update docs to drop first member requirement
v2 here:
https://public-inbox.org/git/20190924010324.22619-1-e@80x24.org/
The following changes since commit 745f6812895b31c02b29bdfe4ae8e5498f776c26:
First batch after Git 2.23 (2019-08-22 12:41:04 -0700)
are available in the Git repository at:
https://80x24.org/git-svn.git hashmap-wip-v3
for you to fetch changes up to 4ec5200646d6b9363e64e2002eb374aa888a6c88:
hashmap_entry: remove first member requirement from docs (2019-10-06 23:05:22 +0000)
----------------------------------------------------------------
Eric Wong (20):
diff: use hashmap_entry_init on moved_entry.ent
coccicheck: detect hashmap_entry.hash assignment
packfile: use hashmap_entry in delta_base_cache_entry
hashmap_entry_init takes "struct hashmap_entry *"
hashmap_get_next takes "const struct hashmap_entry *"
hashmap_add takes "struct hashmap_entry *"
hashmap_get takes "const struct hashmap_entry *"
hashmap_remove takes "const struct hashmap_entry *"
hashmap_put takes "struct hashmap_entry *"
introduce container_of macro
hashmap_get_next returns "struct hashmap_entry *"
hashmap: use *_entry APIs to wrap container_of
hashmap_get{,_from_hash} return "struct hashmap_entry *"
hashmap_cmp_fn takes hashmap_entry params
hashmap: use *_entry APIs for iteration
hashmap: hashmap_{put,remove} return hashmap_entry *
hashmap: introduce hashmap_free_entries
OFFSETOF_VAR macro to simplify hashmap iterators
hashmap: remove type arg from hashmap_{get,put,remove}_entry
hashmap_entry: remove first member requirement from docs
attr.c | 24 ++---
blame.c | 25 ++---
builtin/describe.c | 21 +++--
builtin/difftool.c | 56 +++++++-----
builtin/fast-export.c | 15 ++-
builtin/fetch.c | 32 ++++---
config.c | 24 ++---
contrib/coccinelle/hashmap.cocci | 16 ++++
diff.c | 31 ++++---
diffcore-rename.c | 15 ++-
git-compat-util.h | 38 ++++++++
hashmap.c | 58 +++++++-----
hashmap.h | 176 +++++++++++++++++++++++++++++-------
merge-recursive.c | 87 ++++++++++--------
merge-recursive.h | 4 +-
name-hash.c | 57 ++++++------
oidmap.c | 20 ++--
oidmap.h | 6 +-
packfile.c | 22 +++--
patch-ids.c | 18 ++--
range-diff.c | 10 +-
ref-filter.c | 33 ++++---
refs.c | 25 +++--
remote.c | 21 +++--
remote.h | 2 +-
revision.c | 28 +++---
sequencer.c | 44 ++++++---
sub-process.c | 20 ++--
sub-process.h | 6 +-
submodule-config.c | 52 ++++++-----
t/helper/test-hashmap.c | 50 +++++-----
t/helper/test-lazy-init-name-hash.c | 12 +--
32 files changed, 667 insertions(+), 381 deletions(-)
create mode 100644 contrib/coccinelle/hashmap.cocci
Range-diff against v2:
1: 51ba91d2f9 ! 1: 0f530552de diff: use hashmap_entry_init on moved_entry.ent
@@ -10,6 +10,7 @@
hashmap_add callers to take "struct hashmap_entry *".
Signed-off-by: Eric Wong <e@80x24.org>
+ Reviewed-by: Derrick Stolee <stolee@gmail.com>
diff --git a/diff.c b/diff.c
--- a/diff.c
2: be4071d33d ! 2: d12ddb4327 coccicheck: detect hashmap_entry.hash assignment
@@ -8,6 +8,7 @@
hashmap_entry_init, instead.
Signed-off-by: Eric Wong <e@80x24.org>
+ Reviewed-by: Derrick Stolee <stolee@gmail.com>
diff --git a/contrib/coccinelle/hashmap.cocci b/contrib/coccinelle/hashmap.cocci
new file mode 100644
3: ff40a39bad ! 3: 624b89fbb4 packfile: use hashmap_entry in delta_base_cache_entry
@@ -15,6 +15,7 @@
systems.
Signed-off-by: Eric Wong <e@80x24.org>
+ Reviewed-by: Derrick Stolee <stolee@gmail.com>
diff --git a/packfile.c b/packfile.c
--- a/packfile.c
4: d1db0f6472 ! 4: 7512f2f2f7 hashmap_entry_init takes "struct hashmap_entry *"
@@ -8,6 +8,7 @@
safety and readability.
Signed-off-by: Eric Wong <e@80x24.org>
+ Reviewed-by: Derrick Stolee <stolee@gmail.com>
diff --git a/attr.c b/attr.c
--- a/attr.c
@@ -212,8 +213,8 @@
* and if it is on stack, you can just let it go out of scope).
*/
-static inline void hashmap_entry_init(void *entry, unsigned int hash)
-+static inline void
-+hashmap_entry_init(struct hashmap_entry *e, unsigned int hash)
++static inline void hashmap_entry_init(struct hashmap_entry *e,
++ unsigned int hash)
{
- struct hashmap_entry *e = entry;
e->hash = hash;
5: a293445e97 ! 5: dd167a1113 hashmap_get_next takes "const struct hashmap_entry *"
@@ -6,6 +6,7 @@
now detects invalid types being passed.
Signed-off-by: Eric Wong <e@80x24.org>
+ Reviewed-by: Derrick Stolee <stolee@gmail.com>
diff --git a/diff.c b/diff.c
--- a/diff.c
6: beabdab6fe ! 6: 53f429ef6f hashmap_add takes "struct hashmap_entry *"
@@ -6,6 +6,7 @@
detects invalid types being passed.
Signed-off-by: Eric Wong <e@80x24.org>
+ Reviewed-by: Derrick Stolee <stolee@gmail.com>
diff --git a/attr.c b/attr.c
--- a/attr.c
7: 99970934c7 ! 7: 87739268dc hashmap_get takes "const struct hashmap_entry *"
@@ -6,6 +6,7 @@
now detects invalid types being passed.
Signed-off-by: Eric Wong <e@80x24.org>
+ Reviewed-by: Derrick Stolee <stolee@gmail.com>
diff --git a/attr.c b/attr.c
--- a/attr.c
8: 8148ed70eb ! 8: 22226b3bb4 hashmap_remove takes "const struct hashmap_entry *"
@@ -6,6 +6,7 @@
now detects invalid types being passed.
Signed-off-by: Eric Wong <e@80x24.org>
+ Reviewed-by: Derrick Stolee <stolee@gmail.com>
diff --git a/blame.c b/blame.c
--- a/blame.c
9: 3756dcc34e ! 9: 0b64282a1f hashmap_put takes "struct hashmap_entry *"
@@ -6,6 +6,7 @@
detects invalid types being passed.
Signed-off-by: Eric Wong <e@80x24.org>
+ Reviewed-by: Derrick Stolee <stolee@gmail.com>
diff --git a/builtin/fast-export.c b/builtin/fast-export.c
--- a/builtin/fast-export.c
10: ff586aa43c ! 10: c2e9201838 introduce container_of macro
@@ -7,15 +7,16 @@
and chained hash tables while allowing the compiler to do
type checking.
- I intend to use this to remove the limitation of "hashmap_entry"
- being location-dependent and to allow more compile-time type
- checking.
+ Later patches will use container_of() to remove the limitation
+ of "hashmap_entry" being location-dependent. This will complete
+ the transition to compile-time type checking for the hashmap API.
This macro already exists in our source as "list_entry" in
list.h and making "list_entry" an alias to "container_of"
as the Linux kernel has done is a possibility.
Signed-off-by: Eric Wong <e@80x24.org>
+ Reviewed-by: Derrick Stolee <stolee@gmail.com>
diff --git a/git-compat-util.h b/git-compat-util.h
--- a/git-compat-util.h
11: 931356f061 ! 11: c709e607b1 hashmap_get_next returns "struct hashmap_entry *"
@@ -6,6 +6,7 @@
hashmap_entry being the first field of a struct.
Signed-off-by: Eric Wong <e@80x24.org>
+ Reviewed-by: Derrick Stolee <stolee@gmail.com>
diff --git a/diff.c b/diff.c
--- a/diff.c
@@ -14,10 +15,10 @@
{
int i;
char *got_match = xcalloc(1, pmb_nr);
-+ struct hashmap_entry *ent = &match->ent;
++ struct hashmap_entry *ent;
- for (; match; match = hashmap_get_next(hm, &match->ent)) {
-+ for (; ent; ent = hashmap_get_next(hm, 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;
12: a748b9b0c4 ! 12: 27ba68a7b8 hashmap: use *_entry APIs to wrap container_of
@@ -11,6 +11,7 @@
extra parameter to specify the type.
Signed-off-by: Eric Wong <e@80x24.org>
+ Reviewed-by: Derrick Stolee <stolee@gmail.com>
diff --git a/diff.c b/diff.c
--- a/diff.c
@@ -19,9 +20,9 @@
{
int i;
char *got_match = xcalloc(1, pmb_nr);
-- struct hashmap_entry *ent = &match->ent;
+- struct hashmap_entry *ent;
-- for (; ent; ent = hashmap_get_next(hm, 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++) {
@@ -125,7 +126,6 @@
#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
13: e8faa5e12e ! 13: 222b1f07f3 hashmap_get{,_from_hash} return "struct hashmap_entry *"
@@ -9,6 +9,7 @@
hashmap_entry being the first field in a struct.
Signed-off-by: Eric Wong <e@80x24.org>
+ Reviewed-by: Derrick Stolee <stolee@gmail.com>
diff --git a/attr.c b/attr.c
--- a/attr.c
@@ -152,11 +153,13 @@
}
-void *hashmap_get(const struct hashmap *map, const struct hashmap_entry *key,
-+struct hashmap_entry *
-+hashmap_get(const struct hashmap *map, const struct hashmap_entry *key,
- const void *keydata)
+- const void *keydata)
++struct hashmap_entry *hashmap_get(const struct hashmap *map,
++ const struct hashmap_entry *key,
++ const void *keydata)
{
return *find_entry_ptr(map, key, keydata);
+ }
@@
/* lookup interned string in pool */
hashmap_entry_init(&key.ent, memhash(data, len));
@@ -175,21 +178,27 @@
* to `hashmap_cmp_fn` to decide whether the entry matches the key.
*/
-void *hashmap_get(const struct hashmap *map, const struct hashmap_entry *key,
-+struct hashmap_entry *
-+hashmap_get(const struct hashmap *map, const struct hashmap_entry *key,
- const void *keydata);
+- const void *keydata);
++struct hashmap_entry *hashmap_get(const struct hashmap *map,
++ const struct hashmap_entry *key,
++ const void *keydata);
/*
+ * Returns the hashmap entry for the specified hash code and key data,
@@
* `entry_or_key` parameter of `hashmap_cmp_fn` points to a hashmap_entry
* structure that should not be used in the comparison.
*/
-static inline void *hashmap_get_from_hash(const struct hashmap *map,
-+static inline struct hashmap_entry *
-+hashmap_get_from_hash(const struct hashmap *map,
- unsigned int hash,
- const void *keydata)
+- unsigned int hash,
+- const void *keydata)
++static inline struct hashmap_entry *hashmap_get_from_hash(
++ const struct hashmap *map,
++ unsigned int hash,
++ const void *keydata)
{
+ struct hashmap_entry key;
+ hashmap_entry_init(&key, hash);
diff --git a/merge-recursive.c b/merge-recursive.c
--- a/merge-recursive.c
14: f84bd96b8e ! 14: c789f98c81 hashmap_cmp_fn takes hashmap_entry params
@@ -6,6 +6,7 @@
being the first member of a struct.
Signed-off-by: Eric Wong <e@80x24.org>
+ Reviewed-by: Derrick Stolee <stolee@gmail.com>
diff --git a/attr.c b/attr.c
--- a/attr.c
15: 23fbd888d9 ! 15: 57ae5b5142 hashmap: use *_entry APIs for iteration
@@ -7,6 +7,7 @@
by compilers lacking __typeof__ support.
Signed-off-by: Eric Wong <e@80x24.org>
+ Reviewed-by: Derrick Stolee <stolee@gmail.com>
diff --git a/attr.c b/attr.c
--- a/attr.c
16: 6908364381 ! 16: f1e35ba094 hashmap: hashmap_{put,remove} return hashmap_entry *
@@ -6,6 +6,7 @@
to simplify most callers.
Signed-off-by: Eric Wong <e@80x24.org>
+ Reviewed-by: Derrick Stolee <stolee@gmail.com>
diff --git a/hashmap.c b/hashmap.c
--- a/hashmap.c
@@ -15,18 +16,20 @@
}
-void *hashmap_remove(struct hashmap *map, const struct hashmap_entry *key,
-+struct hashmap_entry *
-+hashmap_remove(struct hashmap *map, const struct hashmap_entry *key,
- const void *keydata)
+- const void *keydata)
++struct hashmap_entry *hashmap_remove(struct hashmap *map,
++ const struct hashmap_entry *key,
++ const void *keydata)
{
struct hashmap_entry *old;
+ struct hashmap_entry **e = find_entry_ptr(map, key, keydata);
@@
return old;
}
-void *hashmap_put(struct hashmap *map, struct hashmap_entry *entry)
-+struct hashmap_entry *
-+hashmap_put(struct hashmap *map, struct hashmap_entry *entry)
++struct hashmap_entry *hashmap_put(struct hashmap *map,
++ struct hashmap_entry *entry)
{
struct hashmap_entry *old = hashmap_remove(map, entry, NULL);
hashmap_add(map, entry);
@@ -39,8 +42,8 @@
* Returns the replaced entry, or NULL if not found (i.e. the entry was added).
*/
-void *hashmap_put(struct hashmap *map, struct hashmap_entry *entry);
-+struct hashmap_entry *
-+hashmap_put(struct hashmap *map, struct hashmap_entry *entry);
++struct hashmap_entry *hashmap_put(struct hashmap *map,
++ struct hashmap_entry *entry);
+
+#define hashmap_put_entry(map, keyvar, type, member) \
+ container_of_or_null(hashmap_put(map, &(keyvar)->member), type, member)
@@ -52,17 +55,17 @@
* Argument explanation is the same as in `hashmap_get`.
*/
-void *hashmap_remove(struct hashmap *map, const struct hashmap_entry *key,
-+struct hashmap_entry *
-+hashmap_remove(struct hashmap *map, const struct hashmap_entry *key,
- const void *keydata);
-
+- const void *keydata);
++struct hashmap_entry *hashmap_remove(struct hashmap *map,
++ const struct hashmap_entry *key,
++ const void *keydata);
++
+#define hashmap_remove_entry(map, keyvar, keydata, type, member) \
+ container_of_or_null(hashmap_remove(map, &(keyvar)->member, keydata), \
+ type, member)
-+
+
/*
* Returns the `bucket` an entry is stored in.
- * Useful for multithreaded read access.
diff --git a/range-diff.c b/range-diff.c
--- a/range-diff.c
17: 150944128b ! 17: adc7cb5516 hashmap: introduce hashmap_free_entries
@@ -12,6 +12,7 @@
the hashmap itself.
Signed-off-by: Eric Wong <e@80x24.org>
+ Reviewed-by: Derrick Stolee <stolee@gmail.com>
diff --git a/blame.c b/blame.c
--- a/blame.c
18: de212aa6d6 ! 18: 1a68e1645d OFFSETOF_VAR macro to simplify hashmap iterators
@@ -5,7 +5,7 @@
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.
+ 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
@@ -16,7 +16,10 @@
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 <e@80x24.org>
+ Reviewed-by: Derrick Stolee <stolee@gmail.com>
diff --git a/attr.c b/attr.c
--- a/attr.c
@@ -141,11 +144,17 @@
(type *)container_of_or_null_offset(ptr, offsetof(type, member))
+/*
-+ * like offsetof(), but takes a pointer to type instead of the type
-+ * @ptr is subject to multiple evaluation since we can't rely on TYPEOF()
++ * like offsetof(), but takes a pointer to a a variable of type which
++ * contains @member, instead of a specified type.
++ * @ptr is subject to multiple evaluation since we can't rely on __typeof__
++ * everywhere.
+ */
++#if defined(__GNUC__) /* clang sets this, too */
++#define OFFSETOF_VAR(ptr, member) offsetof(__typeof__(*ptr), member)
++#else /* !__GNUC__ */
+#define OFFSETOF_VAR(ptr, member) \
+ ((uintptr_t)&(ptr)->member - (uintptr_t)(ptr))
++#endif /* !__GNUC__ */
+
#endif
19: 212a596edd ! 19: fe02b9f839 hashmap: remove type arg from hashmap_{get,put,remove}_entry
@@ -10,6 +10,7 @@
sequential as they are used as: `keyvar->member'
Signed-off-by: Eric Wong <e@80x24.org>
+ Reviewed-by: Derrick Stolee <stolee@gmail.com>
diff --git a/attr.c b/attr.c
--- a/attr.c
@@ -147,8 +148,8 @@
* printf("first: %ld %s\n", e->key, e->value);
* while ((e = hashmap_get_next_entry(&map, e,
@@
- struct hashmap_entry *
- hashmap_put(struct hashmap *map, struct hashmap_entry *entry);
+ struct hashmap_entry *hashmap_put(struct hashmap *map,
+ struct hashmap_entry *entry);
-#define hashmap_put_entry(map, keyvar, type, member) \
- container_of_or_null(hashmap_put(map, &(keyvar)->member), type, member)
@@ -167,8 +168,8 @@
/*
* Removes a hashmap entry matching the specified key. If the hashmap contains
@@
- hashmap_remove(struct hashmap *map, const struct hashmap_entry *key,
- const void *keydata);
+ const struct hashmap_entry *key,
+ const void *keydata);
-#define hashmap_remove_entry(map, keyvar, keydata, type, member) \
- container_of_or_null(hashmap_remove(map, &(keyvar)->member, keydata), \
-: ---------- > 20: 4ec5200646 hashmap_entry: remove first member requirement from docs
next reply other threads:[~2019-10-06 23:30 UTC|newest]
Thread overview: 30+ messages / expand[flat|nested] mbox.gz Atom feed top
2019-10-06 23:30 Eric Wong [this message]
2019-10-06 23:30 ` [PATCH v3 01/20] diff: use hashmap_entry_init on moved_entry.ent Eric Wong
2019-10-06 23:30 ` [PATCH v3 02/20] coccicheck: detect hashmap_entry.hash assignment Eric Wong
2019-10-06 23:30 ` [PATCH v3 03/20] packfile: use hashmap_entry in delta_base_cache_entry Eric Wong
2019-10-06 23:30 ` [PATCH v3 04/20] hashmap_entry_init takes "struct hashmap_entry *" Eric Wong
2019-10-06 23:30 ` [PATCH v3 05/20] hashmap_get_next takes "const struct " Eric Wong
2019-10-06 23:30 ` [PATCH v3 06/20] hashmap_add takes "struct " Eric Wong
2019-10-06 23:30 ` [PATCH v3 07/20] hashmap_get takes "const struct " Eric Wong
2019-10-06 23:30 ` [PATCH v3 08/20] hashmap_remove " Eric Wong
2019-10-06 23:30 ` [PATCH v3 09/20] hashmap_put takes "struct " Eric Wong
2019-10-06 23:30 ` [PATCH v3 10/20] introduce container_of macro Eric Wong
2019-10-06 23:30 ` [PATCH v3 11/20] hashmap_get_next returns "struct hashmap_entry *" Eric Wong
2019-10-06 23:30 ` [PATCH v3 12/20] hashmap: use *_entry APIs to wrap container_of Eric Wong
2019-10-06 23:30 ` [PATCH v3 13/20] hashmap_get{,_from_hash} return "struct hashmap_entry *" Eric Wong
2019-10-06 23:30 ` [PATCH v3 14/20] hashmap_cmp_fn takes hashmap_entry params Eric Wong
2019-10-06 23:30 ` [PATCH v3 15/20] hashmap: use *_entry APIs for iteration Eric Wong
2019-10-06 23:30 ` [PATCH v3 16/20] hashmap: hashmap_{put,remove} return hashmap_entry * Eric Wong
2019-10-06 23:30 ` [PATCH v3 17/20] hashmap: introduce hashmap_free_entries Eric Wong
2019-10-06 23:30 ` [PATCH v3 18/20] OFFSETOF_VAR macro to simplify hashmap iterators Eric Wong
2019-10-06 23:30 ` [PATCH v3 19/20] hashmap: remove type arg from hashmap_{get,put,remove}_entry Eric Wong
2019-10-06 23:30 ` [PATCH v3 20/20] hashmap_entry: remove first member requirement from docs Eric Wong
2019-10-07 1:52 ` Junio C Hamano
2019-10-07 8:43 ` [PATCH v3 21/20] convert: drop invalid comment for subprocess_entry Eric Wong
2019-10-08 2:15 ` Junio C Hamano
2019-10-08 2:56 ` Eric Wong
2019-10-07 1:24 ` [PATCH v3 00/20] hashmap bug/safety/ease-of-use fixes Junio C Hamano
2019-10-08 8:58 ` Johannes Schindelin
2019-10-08 13:56 ` Derrick Stolee
2019-10-08 13:59 ` Derrick Stolee
2019-10-09 1:20 ` Junio C Hamano
Reply instructions:
You may reply publicly to this message via plain-text email
using any one of the following methods:
* Save the following mbox file, import it into your mail client,
and reply-to-all from there: mbox
Avoid top-posting and favor interleaved quoting:
https://en.wikipedia.org/wiki/Posting_style#Interleaved_style
* Reply using the --to, --cc, and --in-reply-to
switches of git-send-email(1):
git send-email \
--in-reply-to=20191006233043.3516-1-e@80x24.org \
--to=e@80x24.org \
--cc=Johannes.Schindelin@gmx.de \
--cc=git@vger.kernel.org \
--cc=gitster@pobox.com \
--cc=phillip.wood123@gmail.com \
--cc=stolee@gmail.com \
/path/to/YOUR_REPLY
https://kernel.org/pub/software/scm/git/docs/git-send-email.html
* If your mail client supports setting the In-Reply-To header
via mailto: links, try the mailto: link
Be sure your reply has a Subject: header at the top and a blank line
before the message body.
This is an external index of several public inboxes,
see mirroring instructions on how to clone and mirror
all data and code used by this external index.