git@vger.kernel.org list mirror (unofficial, one of many)
 help / color / Atom feed
* [RFC PATCH 0/5] oidmap: handle entries with the same key
@ 2019-07-07  8:29 Christian Couder
  2019-07-07  8:29 ` [RFC PATCH 1/5] oidmap: add oidmap_add() Christian Couder
                   ` (5 more replies)
  0 siblings, 6 replies; 9+ messages in thread
From: Christian Couder @ 2019-07-07  8:29 UTC (permalink / raw)
  To: git
  Cc: Junio C Hamano, Ævar Arnfjörð Bjarmason,
	Jonathan Tan, SZEDER Gábor, Jeff King, Derrick Stolee,
	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


^ permalink raw reply	[flat|nested] 9+ messages in thread

* [RFC PATCH 1/5] oidmap: add oidmap_add()
  2019-07-07  8:29 [RFC PATCH 0/5] oidmap: handle entries with the same key Christian Couder
@ 2019-07-07  8:29 ` Christian Couder
  2019-07-07  8:29 ` [RFC PATCH 2/5] oidmap: add oidmap_get_next() Christian Couder
                   ` (4 subsequent siblings)
  5 siblings, 0 replies; 9+ messages in thread
From: Christian Couder @ 2019-07-07  8:29 UTC (permalink / raw)
  To: git
  Cc: Junio C Hamano, Ævar Arnfjörð Bjarmason,
	Jonathan Tan, SZEDER Gábor, Jeff King, Derrick Stolee,
	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


^ permalink raw reply	[flat|nested] 9+ messages in thread

* [RFC PATCH 2/5] oidmap: add oidmap_get_next()
  2019-07-07  8:29 [RFC PATCH 0/5] oidmap: handle entries with the same key Christian Couder
  2019-07-07  8:29 ` [RFC PATCH 1/5] oidmap: add oidmap_add() Christian Couder
@ 2019-07-07  8:29 ` Christian Couder
  2019-07-07  8:30 ` [RFC PATCH 3/5] test-oidmap: add back proper 'add' subcommand Christian Couder
                   ` (3 subsequent siblings)
  5 siblings, 0 replies; 9+ messages in thread
From: Christian Couder @ 2019-07-07  8:29 UTC (permalink / raw)
  To: git
  Cc: Junio C Hamano, Ævar Arnfjörð Bjarmason,
	Jonathan Tan, SZEDER Gábor, Jeff King, Derrick Stolee,
	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


^ permalink raw reply	[flat|nested] 9+ messages in thread

* [RFC PATCH 3/5] test-oidmap: add back proper 'add' subcommand
  2019-07-07  8:29 [RFC PATCH 0/5] oidmap: handle entries with the same key Christian Couder
  2019-07-07  8:29 ` [RFC PATCH 1/5] oidmap: add oidmap_add() Christian Couder
  2019-07-07  8:29 ` [RFC PATCH 2/5] oidmap: add oidmap_get_next() Christian Couder
@ 2019-07-07  8:30 ` Christian Couder
  2019-07-07  8:30 ` [RFC PATCH 4/5] test-oidmap: add 'get_all' subcommand Christian Couder
                   ` (2 subsequent siblings)
  5 siblings, 0 replies; 9+ messages in thread
From: Christian Couder @ 2019-07-07  8:30 UTC (permalink / raw)
  To: git
  Cc: Junio C Hamano, Ævar Arnfjörð Bjarmason,
	Jonathan Tan, SZEDER Gábor, Jeff King, Derrick Stolee,
	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


^ permalink raw reply	[flat|nested] 9+ messages in thread

* [RFC PATCH 4/5] test-oidmap: add 'get_all' subcommand
  2019-07-07  8:29 [RFC PATCH 0/5] oidmap: handle entries with the same key Christian Couder
                   ` (2 preceding siblings ...)
  2019-07-07  8:30 ` [RFC PATCH 3/5] test-oidmap: add back proper 'add' subcommand Christian Couder
@ 2019-07-07  8:30 ` Christian Couder
  2019-07-07  8:30 ` [RFC PATCH 5/5] t0016: add 'add' and 'get_all' subcommand test Christian Couder
  2019-07-08 20:24 ` [RFC PATCH 0/5] oidmap: handle entries with the same key Junio C Hamano
  5 siblings, 0 replies; 9+ messages in thread
From: Christian Couder @ 2019-07-07  8:30 UTC (permalink / raw)
  To: git
  Cc: Junio C Hamano, Ævar Arnfjörð Bjarmason,
	Jonathan Tan, SZEDER Gábor, Jeff King, Derrick Stolee,
	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


^ permalink raw reply	[flat|nested] 9+ messages in thread

* [RFC PATCH 5/5] t0016: add 'add' and 'get_all' subcommand test
  2019-07-07  8:29 [RFC PATCH 0/5] oidmap: handle entries with the same key Christian Couder
                   ` (3 preceding siblings ...)
  2019-07-07  8:30 ` [RFC PATCH 4/5] test-oidmap: add 'get_all' subcommand Christian Couder
@ 2019-07-07  8:30 ` Christian Couder
  2019-07-08 20:24 ` [RFC PATCH 0/5] oidmap: handle entries with the same key Junio C Hamano
  5 siblings, 0 replies; 9+ messages in thread
From: Christian Couder @ 2019-07-07  8:30 UTC (permalink / raw)
  To: git
  Cc: Junio C Hamano, Ævar Arnfjörð Bjarmason,
	Jonathan Tan, SZEDER Gábor, Jeff King, Derrick Stolee,
	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


^ permalink raw reply	[flat|nested] 9+ messages in thread

* Re: [RFC PATCH 0/5] oidmap: handle entries with the same key
  2019-07-07  8:29 [RFC PATCH 0/5] oidmap: handle entries with the same key Christian Couder
                   ` (4 preceding siblings ...)
  2019-07-07  8:30 ` [RFC PATCH 5/5] t0016: add 'add' and 'get_all' subcommand test Christian Couder
@ 2019-07-08 20:24 ` Junio C Hamano
  2019-07-12 18:21   ` Junio C Hamano
  5 siblings, 1 reply; 9+ messages in thread
From: Junio C Hamano @ 2019-07-08 20:24 UTC (permalink / raw)
  To: Christian Couder
  Cc: git, Ævar Arnfjörð Bjarmason, Jonathan Tan,
	SZEDER Gábor, Jeff King, Derrick Stolee, Christian Couder

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.

^ permalink raw reply	[flat|nested] 9+ messages in thread

* Re: [RFC PATCH 0/5] oidmap: handle entries with the same key
  2019-07-08 20:24 ` [RFC PATCH 0/5] oidmap: handle entries with the same key Junio C Hamano
@ 2019-07-12 18:21   ` Junio C Hamano
  2019-07-12 21:58     ` Jeff King
  0 siblings, 1 reply; 9+ messages in thread
From: Junio C Hamano @ 2019-07-12 18:21 UTC (permalink / raw)
  To: Christian Couder
  Cc: git, Ævar Arnfjörð Bjarmason, Jonathan Tan,
	SZEDER Gábor, Jeff King, Derrick Stolee, Christian Couder

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.

^ permalink raw reply	[flat|nested] 9+ messages in thread

* Re: [RFC PATCH 0/5] oidmap: handle entries with the same key
  2019-07-12 18:21   ` Junio C Hamano
@ 2019-07-12 21:58     ` Jeff King
  0 siblings, 0 replies; 9+ messages in thread
From: Jeff King @ 2019-07-12 21:58 UTC (permalink / raw)
  To: Junio C Hamano
  Cc: Christian Couder, git, Ævar Arnfjörð Bjarmason,
	Jonathan Tan, SZEDER Gábor, Derrick Stolee,
	Christian Couder

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

^ permalink raw reply	[flat|nested] 9+ messages in thread

end of thread, back to index

Thread overview: 9+ messages (download: mbox.gz / follow: Atom feed)
-- links below jump to the message on this page --
2019-07-07  8:29 [RFC PATCH 0/5] oidmap: handle entries with the same key Christian Couder
2019-07-07  8:29 ` [RFC PATCH 1/5] oidmap: add oidmap_add() Christian Couder
2019-07-07  8:29 ` [RFC PATCH 2/5] oidmap: add oidmap_get_next() Christian Couder
2019-07-07  8:30 ` [RFC PATCH 3/5] test-oidmap: add back proper 'add' subcommand Christian Couder
2019-07-07  8:30 ` [RFC PATCH 4/5] test-oidmap: add 'get_all' subcommand Christian Couder
2019-07-07  8:30 ` [RFC PATCH 5/5] t0016: add 'add' and 'get_all' subcommand test Christian Couder
2019-07-08 20:24 ` [RFC PATCH 0/5] oidmap: handle entries with the same key Junio C Hamano
2019-07-12 18:21   ` Junio C Hamano
2019-07-12 21:58     ` Jeff King

git@vger.kernel.org list mirror (unofficial, one of many)

Archives are clonable:
	git clone --mirror https://public-inbox.org/git
	git clone --mirror http://ou63pmih66umazou.onion/git
	git clone --mirror http://czquwvybam4bgbro.onion/git
	git clone --mirror http://hjrcffqmbrq6wope.onion/git

Newsgroups are available over NNTP:
	nntp://news.public-inbox.org/inbox.comp.version-control.git
	nntp://ou63pmih66umazou.onion/inbox.comp.version-control.git
	nntp://czquwvybam4bgbro.onion/inbox.comp.version-control.git
	nntp://hjrcffqmbrq6wope.onion/inbox.comp.version-control.git
	nntp://news.gmane.org/gmane.comp.version-control.git

 note: .onion URLs require Tor: https://www.torproject.org/

AGPL code for this site: git clone https://public-inbox.org/ public-inbox