threads / rfc / 51441

RFC patch, 5 partsoidmap: handle entries with the same key

Subject: [RFC PATCH 0/5] oidmap: handle entries with the same key

## tl;dr

9 messages between Jul 7, 2019 and Jul 12, 2019. Diffs are folded; open one to read it.

replies: 8people: 3as markdown or json

Christian Couder· Jul 7, 2019, 08:29 UTC · lore

This is an RFC patch series that is not intended to be merged for now, as it looks like we don't need oidmaps that can handle several entries with the same key yet.

As I needed this for my work on reftable, I thought that I might as well post it, to get early feedback and to avoid duplicating work in case someone else needs it before I start sending my reftable work (hopefully in a few months).

Christian Couder (5):
  oidmap: add oidmap_add()
  oidmap: add oidmap_get_next()
  test-oidmap: add back proper 'add' subcommand
  test-oidmap: add 'get_all' subcommand
  t0016: add 'add' and 'get_all' subcommand test
 oidmap.c               | 20 ++++++++++++++++++++
 oidmap.h               | 12 ++++++++++++
 t/helper/test-oidmap.c | 34 ++++++++++++++++++++++++++++++++++
 t/t0016-oidmap.sh      | 26 ++++++++++++++++++++++++++
 4 files changed, 92 insertions(+)
-- 
2.22.0.514.g3228928bce.dirty
Christian Couder· Jul 7, 2019, 08:29 UTC · re: Christian Couder · lore

[RFC PATCH 1/5] oidmap: add oidmap_add()

We will need to have more than one entry with the same oid key in an oidmap, which is not supported yet, as oipmap_put() replaces an existing entry with the same oid key. So let's add oidmap_add().

Signed-off-by: Christian Couder <chriscool@tuxfamily.org>
---
 oidmap.c | 12 ++++++++++++
 oidmap.h |  6 ++++++
 2 files changed, 18 insertions(+)
Show changes to 2 files +18 −0

oidmap.c, oidmap.h

diff --git a/oidmap.c b/oidmap.c
index 6d6e840d03..bfb290ee01 100644
--- a/oidmap.c
+++ b/oidmap.c
@@ -43,6 +43,17 @@ void *oidmap_remove(struct oidmap *map, const struct object_id *key)
 	return hashmap_remove(&map->map, &entry, key);
 }
 
+void oidmap_add(struct oidmap *map, void *entry)
+{
+	struct oidmap_entry *to_put = entry;
+
+	if (!map->map.cmpfn)
+		oidmap_init(map, 0);
+
+	hashmap_entry_init(&to_put->internal_entry, oidhash(&to_put->oid));
+	hashmap_add(&map->map, to_put);
+}
+
 void *oidmap_put(struct oidmap *map, void *entry)
 {
 	struct oidmap_entry *to_put = entry;
@@ -53,3 +64,4 @@ void *oidmap_put(struct oidmap *map, void *entry)
 	hashmap_entry_init(&to_put->internal_entry, oidhash(&to_put->oid));
 	return hashmap_put(&map->map, to_put);
 }
+
diff --git a/oidmap.h b/oidmap.h
index 7a939461ff..21d929ad79 100644
--- a/oidmap.h
+++ b/oidmap.h
@@ -49,6 +49,12 @@ void oidmap_free(struct oidmap *map, int free_entries);
 void *oidmap_get(const struct oidmap *map,
 		 const struct object_id *key);
 
+/*
+ * Adds an oidmap entry. This allows to add duplicate entries (i.e.
+ * separate values with the same oid key).
+ */
+void oidmap_add(struct oidmap *map, void *entry);
+
 /*
  * Adds or replaces an oidmap entry.
  *

-- 
2.22.0.514.g3228928bce.dirty
Christian Couder· Jul 7, 2019, 08:29 UTC · re: Christian Couder · lore

[RFC PATCH 2/5] oidmap: add oidmap_get_next()

For now "oidmap.h" gives us no way to get all the entries that have the same oid key from an oidmap, as oidmap_get() will always return the first entry. So let's add oidmap_get_next() for this purpose.

Signed-off-by: Christian Couder <chriscool@tuxfamily.org>
---
 oidmap.c | 8 ++++++++
 oidmap.h | 6 ++++++
 2 files changed, 14 insertions(+)
Show changes to 2 files +14 −0

oidmap.c, oidmap.h

diff --git a/oidmap.c b/oidmap.c
index bfb290ee01..9cf9dfd533 100644
--- a/oidmap.c
+++ b/oidmap.c
@@ -32,6 +32,14 @@ void *oidmap_get(const struct oidmap *map, const struct object_id *key)
 	return hashmap_get_from_hash(&map->map, oidhash(key), key);
 }
 
+void *oidmap_get_next(const struct oidmap *map, const void *entry)
+{
+	if (!map->map.cmpfn)
+		return NULL;
+
+	return hashmap_get_next(&map->map, entry);
+}
+
 void *oidmap_remove(struct oidmap *map, const struct object_id *key)
 {
 	struct hashmap_entry entry;
diff --git a/oidmap.h b/oidmap.h
index 21d929ad79..5aad22784a 100644
--- a/oidmap.h
+++ b/oidmap.h
@@ -49,6 +49,12 @@ void oidmap_free(struct oidmap *map, int free_entries);
 void *oidmap_get(const struct oidmap *map,
 		 const struct object_id *key);
 
+/*
+ * Returns the next equal oidmap entry, or NULL if not found. This can be
+ * used to iterate over duplicate entries (see `oidmap_add`).
+ */
+void *oidmap_get_next(const struct oidmap *map, const void *entry);
+
 /*
  * Adds an oidmap entry. This allows to add duplicate entries (i.e.
  * separate values with the same oid key).

-- 
2.22.0.514.g3228928bce.dirty
Christian Couder· Jul 7, 2019, 08:30 UTC · re: Christian Couder · lore

[RFC PATCH 3/5] test-oidmap: add back proper 'add' subcommand

Let's making it ppossible to test oidmap_add() by adding an 'add' subcommand.

Signed-off-by: Christian Couder <chriscool@tuxfamily.org>
---
 t/helper/test-oidmap.c | 17 +++++++++++++++++
 1 file changed, 17 insertions(+)
Show changes to t/helper/test-oidmap.c +17 −0
diff --git a/t/helper/test-oidmap.c b/t/helper/test-oidmap.c
index 0acf99931e..c19b41aa4f 100644
--- a/t/helper/test-oidmap.c
+++ b/t/helper/test-oidmap.c
@@ -65,6 +65,23 @@ int cmd__oidmap(int argc, const char **argv)
 			puts(entry ? entry->name : "NULL");
 			free(entry);
 
+		} else if (!strcmp("add", cmd) && p1 && p2) {
+
+			if (get_oid(p1, &oid)) {
+				printf("Unknown oid: %s\n", p1);
+				continue;
+			}
+
+			/* create entry with oid_key = p1, name_value = p2 */
+			FLEX_ALLOC_STR(entry, name, p2);
+			oidcpy(&entry->entry.oid, &oid);
+
+			/* add entry */
+			oidmap_add(&map, entry);
+
+			/* print added entry */
+			puts(entry->name);
+
 		} else if (!strcmp("get", cmd) && p1) {
 
 			if (get_oid(p1, &oid)) {

-- 
2.22.0.514.g3228928bce.dirty
Christian Couder· Jul 7, 2019, 08:30 UTC · re: Christian Couder · lore

[RFC PATCH 4/5] test-oidmap: add 'get_all' subcommand

Let's make it possible to test oidmap_get_next() by adding a 'get_all' subcommand that calls oidmap_get() once first and then oidmap_get_next() several times until there is no more entry with the same oid key.

Signed-off-by: Christian Couder <chriscool@tuxfamily.org>
---
 t/helper/test-oidmap.c | 17 +++++++++++++++++
 1 file changed, 17 insertions(+)
Show changes to t/helper/test-oidmap.c +17 −0
diff --git a/t/helper/test-oidmap.c b/t/helper/test-oidmap.c
index c19b41aa4f..5c4897ce59 100644
--- a/t/helper/test-oidmap.c
+++ b/t/helper/test-oidmap.c
@@ -95,6 +95,23 @@ int cmd__oidmap(int argc, const char **argv)
 			/* print result */
 			puts(entry ? entry->name : "NULL");
 
+		} else if (!strcmp("get_all", cmd) && p1) {
+
+			if (get_oid(p1, &oid)) {
+				printf("Unknown oid: %s\n", p1);
+				continue;
+			}
+
+			/* lookup entry in oidmap */
+			entry = oidmap_get(&map, &oid);
+
+			/* print result */
+			puts(entry ? entry->name : "NULL");
+
+			if (entry)
+				while ((entry = oidmap_get_next(&map, entry)))
+					puts(entry ? entry->name : "NULL");
+
 		} else if (!strcmp("remove", cmd) && p1) {
 
 			if (get_oid(p1, &oid)) {

-- 
2.22.0.514.g3228928bce.dirty
Christian Couder· Jul 7, 2019, 08:30 UTC · re: Christian Couder · lore

[RFC PATCH 5/5] t0016: add 'add' and 'get_all' subcommand test

Let's add a test case to test both the 'add' and 'get_all' subcommand from "test-oidmap.c", and through them oidmap_add() and oidmap_get_next() from "oidmap.{c,h}".

Signed-off-by: Christian Couder <chriscool@tuxfamily.org>
---
 t/t0016-oidmap.sh | 26 ++++++++++++++++++++++++++
 1 file changed, 26 insertions(+)
Show changes to t/t0016-oidmap.sh +26 −0
diff --git a/t/t0016-oidmap.sh b/t/t0016-oidmap.sh
index bbe719e950..1d3196d624 100755
--- a/t/t0016-oidmap.sh
+++ b/t/t0016-oidmap.sh
@@ -67,6 +67,32 @@ Unknown oid: invalidOid
 
 '
 
+test_expect_success 'add and get_all' '
+
+test_oidmap "add one 1
+add one un
+add two 2
+add two deux
+add three 3
+get_all two
+get_all four
+get_all invalidOid
+get_all three
+get_all one" "1
+un
+2
+deux
+3
+deux
+2
+NULL
+Unknown oid: invalidOid
+3
+un
+1"
+
+'
+
 test_expect_success 'remove' '
 
 test_oidmap "put one 1

-- 
2.22.0.514.g3228928bce.dirty
Junio C Hamano· Jul 8, 2019, 20:24 UTC · re: Christian Couder · lore

Re: [RFC PATCH 0/5] oidmap: handle entries with the same key

Christian Couder <christian.couder@gmail.com> writes:
> This is an RFC patch series that is not intended to be merged for now,
> as it looks like we don't need oidmaps that can handle several entries
> with the same key yet.

What does it even mean for a map to allow multiple entries per key? When you have a key and its value, you must retrieve all existing entries for the key and see their values before deciding if you want to add yet another entry to the already existing set? When you have a key, you must retrieve all existing entries to see if any of them is what you want?

What I am wondering is if people usually do "a single list/set of values that is associated with each key" for such an application. Obviously you do not need a map that allows multiple entries per key if you did so---is there an advantage of a map that allows multiple entries per key?

> As I needed this for my work on reftable, I thought that...

I actually think that showing how it is used in the real application (reftable?) is the best way to illustrate why this is useful and to get opinions from others.

Junio C Hamano· Jul 12, 2019, 18:21 UTC · re: Junio C Hamano · lore

Re: [RFC PATCH 0/5] oidmap: handle entries with the same key

Junio C Hamano <gitster@pobox.com> writes:
Show 7 quoted lines
> Christian Couder <christian.couder@gmail.com> writes:
>
>> This is an RFC patch series that is not intended to be merged for now,
>> as it looks like we don't need oidmaps that can handle several entries
>> with the same key yet.
>
> What does it even mean for a map to allow multiple entries per key?

Ah, one thing that I was missing (perhaps it was obvious to everybody else but me X-<) was that this is merely to expose what is already available in the underlying hashmap API, so let's not bother with the "don't people usually do a single key to a value, which happens to be a bag of stuff (not just a single stuff)?" question.

And from that "a generic hashmap can do this, and an upcoming code needs to use a hashmap keyed with oid in the same fashion" point of view, the new wrappers the patches add all made sense to me.

Show 5 quoted lines
>> As I needed this for my work on reftable, I thought that...
>
> I actually think that showing how it is used in the real application
> (reftable?) is the best way to illustrate why this is useful and to
> get opinions from others.
This part still stands, though.
Thanks.
Jeff King· Jul 12, 2019, 21:58 UTC · re: Junio C Hamano · lore

Re: [RFC PATCH 0/5] oidmap: handle entries with the same key

On Fri, Jul 12, 2019 at 11:21:47AM -0700, Junio C Hamano wrote:
Show 17 quoted lines
> > Christian Couder <christian.couder@gmail.com> writes:
> >
> >> This is an RFC patch series that is not intended to be merged for now,
> >> as it looks like we don't need oidmaps that can handle several entries
> >> with the same key yet.
> >
> > What does it even mean for a map to allow multiple entries per key?
> 
> Ah, one thing that I was missing (perhaps it was obvious to
> everybody else but me X-<) was that this is merely to expose what is
> already available in the underlying hashmap API, so let's not bother
> with the "don't people usually do a single key to a value, which
> happens to be a bag of stuff (not just a single stuff)?" question.
> 
> And from that "a generic hashmap can do this, and an upcoming code
> needs to use a hashmap keyed with oid in the same fashion" point of
> view, the new wrappers the patches add all made sense to me.
FWIW, I went through the same thought process. :)

One devil's advocate point against, though: we found recently that khash performs much better than hashmap.[ch] for the oidset data structure. AFAIK nobody has looked at whether the same is true for oidmap. But if it is, then this strategy may make it harder to switch.

(OTOH, we already have kh_oid_map, so the two could probably co-exist and we could just convert particular callers from one to the other).

Show 5 quoted lines
> > I actually think that showing how it is used in the real application
> > (reftable?) is the best way to illustrate why this is useful and to
> > get opinions from others.
> 
> This part still stands, though.
Agreed.
-Peff

← back to recent threads