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

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

[Christian Couder]

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

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

[Christian Couder]

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(+)

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

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

[Christian Couder]

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(+)

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

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

[Christian Couder]

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(+)

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

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

[Christian Couder]

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(+)

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

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

[Christian Couder]

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(+)

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

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

[Junio C Hamano]

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.

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

[Junio C Hamano]

Junio C Hamano <gitster@pobox.com> writes:

> 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.

>> 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.

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

[Jeff King]

On Fri, Jul 12, 2019 at 11:21:47AM -0700, Junio C Hamano wrote:

> > 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).

> > 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