{"thread":{"id":"51441","subject":"[RFC PATCH 0/5] oidmap: handle entries with the same key","startedAt":"2019-07-07T08:30:33Z","lastAt":"2019-07-12T21:58:27Z","messageCount":9,"participants":["Christian Couder","Junio C Hamano","Jeff King"],"isPatch":true,"patchVersion":1,"patchTotal":5},"messages":[{"id":"378664","messageId":"20190707083002.7037-1-chriscool@tuxfamily.org","threadId":"51441","inReplyTo":null,"subject":"[RFC PATCH 0/5] oidmap: handle entries with the same key","fromName":"Christian Couder","fromEmail":"christian.couder@gmail.com","sentAt":"2019-07-07T08:29:57Z","receivedAt":"2019-07-07T08:30:33Z","isPatch":true,"sender":{"key":"christian.couder@gmail.com","avatar":"https://avatars.githubusercontent.com/u/208954?v=4"},"body":"This is an RFC patch series that is not intended to be merged for now,\nas it looks like we don't need oidmaps that can handle several entries\nwith the same key yet.\n\nAs I needed this for my work on reftable, I thought that I might as\nwell post it, to get early feedback and to avoid duplicating work in\ncase someone else needs it before I start sending my reftable work\n(hopefully in a few months).\n\nChristian Couder (5):\n oidmap: add oidmap_add()\n oidmap: add oidmap_get_next()\n test-oidmap: add back proper 'add' subcommand\n test-oidmap: add 'get_all' subcommand\n t0016: add 'add' and 'get_all' subcommand test\n\n oidmap.c | 20 ++++++++++++++++++++\n oidmap.h | 12 ++++++++++++\n t/helper/test-oidmap.c | 34 ++++++++++++++++++++++++++++++++++\n t/t0016-oidmap.sh | 26 ++++++++++++++++++++++++++\n 4 files changed, 92 insertions(+)\n\n-- \n2.22.0.514.g3228928bce.dirty\n\n"},{"id":"378665","messageId":"20190707083002.7037-2-chriscool@tuxfamily.org","threadId":"51441","inReplyTo":"20190707083002.7037-1-chriscool@tuxfamily.org","subject":"[RFC PATCH 1/5] oidmap: add oidmap_add()","fromName":"Christian Couder","fromEmail":"christian.couder@gmail.com","sentAt":"2019-07-07T08:29:58Z","receivedAt":"2019-07-07T08:30:36Z","isPatch":true,"sender":{"key":"christian.couder@gmail.com","avatar":"https://avatars.githubusercontent.com/u/208954?v=4"},"body":"We will need to have more than one entry with the same oid key\nin an oidmap, which is not supported yet, as oipmap_put()\nreplaces an existing entry with the same oid key. So let's add\noidmap_add().\n\nSigned-off-by: Christian Couder \n---\n oidmap.c | 12 ++++++++++++\n oidmap.h | 6 ++++++\n 2 files changed, 18 insertions(+)\n\ndiff --git a/oidmap.c b/oidmap.c\nindex 6d6e840d03..bfb290ee01 100644\n--- a/oidmap.c\n+++ b/oidmap.c\n@@ -43,6 +43,17 @@ void *oidmap_remove(struct oidmap *map, const struct object_id *key)\n \treturn hashmap_remove(&map->map, &entry, key);\n }\n \n+void oidmap_add(struct oidmap *map, void *entry)\n+{\n+\tstruct oidmap_entry *to_put = entry;\n+\n+\tif (!map->map.cmpfn)\n+\t\toidmap_init(map, 0);\n+\n+\thashmap_entry_init(&to_put->internal_entry, oidhash(&to_put->oid));\n+\thashmap_add(&map->map, to_put);\n+}\n+\n void *oidmap_put(struct oidmap *map, void *entry)\n {\n \tstruct oidmap_entry *to_put = entry;\n@@ -53,3 +64,4 @@ void *oidmap_put(struct oidmap *map, void *entry)\n \thashmap_entry_init(&to_put->internal_entry, oidhash(&to_put->oid));\n \treturn hashmap_put(&map->map, to_put);\n }\n+\ndiff --git a/oidmap.h b/oidmap.h\nindex 7a939461ff..21d929ad79 100644\n--- a/oidmap.h\n+++ b/oidmap.h\n@@ -49,6 +49,12 @@ void oidmap_free(struct oidmap *map, int free_entries);\n void *oidmap_get(const struct oidmap *map,\n \t\t const struct object_id *key);\n \n+/*\n+ * Adds an oidmap entry. This allows to add duplicate entries (i.e.\n+ * separate values with the same oid key).\n+ */\n+void oidmap_add(struct oidmap *map, void *entry);\n+\n /*\n * Adds or replaces an oidmap entry.\n *\n-- \n2.22.0.514.g3228928bce.dirty\n\n"},{"id":"378666","messageId":"20190707083002.7037-3-chriscool@tuxfamily.org","threadId":"51441","inReplyTo":"20190707083002.7037-1-chriscool@tuxfamily.org","subject":"[RFC PATCH 2/5] oidmap: add oidmap_get_next()","fromName":"Christian Couder","fromEmail":"christian.couder@gmail.com","sentAt":"2019-07-07T08:29:59Z","receivedAt":"2019-07-07T08:30:36Z","isPatch":true,"sender":{"key":"christian.couder@gmail.com","avatar":"https://avatars.githubusercontent.com/u/208954?v=4"},"body":"For now \"oidmap.h\" gives us no way to get all the entries that have the\nsame oid key from an oidmap, as oidmap_get() will always return the first\nentry. So let's add oidmap_get_next() for this purpose.\n\nSigned-off-by: Christian Couder \n---\n oidmap.c | 8 ++++++++\n oidmap.h | 6 ++++++\n 2 files changed, 14 insertions(+)\n\ndiff --git a/oidmap.c b/oidmap.c\nindex bfb290ee01..9cf9dfd533 100644\n--- a/oidmap.c\n+++ b/oidmap.c\n@@ -32,6 +32,14 @@ void *oidmap_get(const struct oidmap *map, const struct object_id *key)\n \treturn hashmap_get_from_hash(&map->map, oidhash(key), key);\n }\n \n+void *oidmap_get_next(const struct oidmap *map, const void *entry)\n+{\n+\tif (!map->map.cmpfn)\n+\t\treturn NULL;\n+\n+\treturn hashmap_get_next(&map->map, entry);\n+}\n+\n void *oidmap_remove(struct oidmap *map, const struct object_id *key)\n {\n \tstruct hashmap_entry entry;\ndiff --git a/oidmap.h b/oidmap.h\nindex 21d929ad79..5aad22784a 100644\n--- a/oidmap.h\n+++ b/oidmap.h\n@@ -49,6 +49,12 @@ void oidmap_free(struct oidmap *map, int free_entries);\n void *oidmap_get(const struct oidmap *map,\n \t\t const struct object_id *key);\n \n+/*\n+ * Returns the next equal oidmap entry, or NULL if not found. This can be\n+ * used to iterate over duplicate entries (see `oidmap_add`).\n+ */\n+void *oidmap_get_next(const struct oidmap *map, const void *entry);\n+\n /*\n * Adds an oidmap entry. This allows to add duplicate entries (i.e.\n * separate values with the same oid key).\n-- \n2.22.0.514.g3228928bce.dirty\n\n"},{"id":"378667","messageId":"20190707083002.7037-4-chriscool@tuxfamily.org","threadId":"51441","inReplyTo":"20190707083002.7037-1-chriscool@tuxfamily.org","subject":"[RFC PATCH 3/5] test-oidmap: add back proper 'add' subcommand","fromName":"Christian Couder","fromEmail":"christian.couder@gmail.com","sentAt":"2019-07-07T08:30:00Z","receivedAt":"2019-07-07T08:30:39Z","isPatch":true,"sender":{"key":"christian.couder@gmail.com","avatar":"https://avatars.githubusercontent.com/u/208954?v=4"},"body":"Let's making it ppossible to test oidmap_add() by adding an 'add'\nsubcommand.\n\nSigned-off-by: Christian Couder \n---\n t/helper/test-oidmap.c | 17 +++++++++++++++++\n 1 file changed, 17 insertions(+)\n\ndiff --git a/t/helper/test-oidmap.c b/t/helper/test-oidmap.c\nindex 0acf99931e..c19b41aa4f 100644\n--- a/t/helper/test-oidmap.c\n+++ b/t/helper/test-oidmap.c\n@@ -65,6 +65,23 @@ int cmd__oidmap(int argc, const char **argv)\n \t\t\tputs(entry ? entry->name : \"NULL\");\n \t\t\tfree(entry);\n \n+\t\t} else if (!strcmp(\"add\", cmd) && p1 && p2) {\n+\n+\t\t\tif (get_oid(p1, &oid)) {\n+\t\t\t\tprintf(\"Unknown oid: %s\\n\", p1);\n+\t\t\t\tcontinue;\n+\t\t\t}\n+\n+\t\t\t/* create entry with oid_key = p1, name_value = p2 */\n+\t\t\tFLEX_ALLOC_STR(entry, name, p2);\n+\t\t\toidcpy(&entry->entry.oid, &oid);\n+\n+\t\t\t/* add entry */\n+\t\t\toidmap_add(&map, entry);\n+\n+\t\t\t/* print added entry */\n+\t\t\tputs(entry->name);\n+\n \t\t} else if (!strcmp(\"get\", cmd) && p1) {\n \n \t\t\tif (get_oid(p1, &oid)) {\n-- \n2.22.0.514.g3228928bce.dirty\n\n"},{"id":"378668","messageId":"20190707083002.7037-5-chriscool@tuxfamily.org","threadId":"51441","inReplyTo":"20190707083002.7037-1-chriscool@tuxfamily.org","subject":"[RFC PATCH 4/5] test-oidmap: add 'get_all' subcommand","fromName":"Christian Couder","fromEmail":"christian.couder@gmail.com","sentAt":"2019-07-07T08:30:01Z","receivedAt":"2019-07-07T08:30:39Z","isPatch":true,"sender":{"key":"christian.couder@gmail.com","avatar":"https://avatars.githubusercontent.com/u/208954?v=4"},"body":"Let's make it possible to test oidmap_get_next() by adding a 'get_all'\nsubcommand that calls oidmap_get() once first and then oidmap_get_next()\nseveral times until there is no more entry with the same oid key.\n\nSigned-off-by: Christian Couder \n---\n t/helper/test-oidmap.c | 17 +++++++++++++++++\n 1 file changed, 17 insertions(+)\n\ndiff --git a/t/helper/test-oidmap.c b/t/helper/test-oidmap.c\nindex c19b41aa4f..5c4897ce59 100644\n--- a/t/helper/test-oidmap.c\n+++ b/t/helper/test-oidmap.c\n@@ -95,6 +95,23 @@ int cmd__oidmap(int argc, const char **argv)\n \t\t\t/* print result */\n \t\t\tputs(entry ? entry->name : \"NULL\");\n \n+\t\t} else if (!strcmp(\"get_all\", cmd) && p1) {\n+\n+\t\t\tif (get_oid(p1, &oid)) {\n+\t\t\t\tprintf(\"Unknown oid: %s\\n\", p1);\n+\t\t\t\tcontinue;\n+\t\t\t}\n+\n+\t\t\t/* lookup entry in oidmap */\n+\t\t\tentry = oidmap_get(&map, &oid);\n+\n+\t\t\t/* print result */\n+\t\t\tputs(entry ? entry->name : \"NULL\");\n+\n+\t\t\tif (entry)\n+\t\t\t\twhile ((entry = oidmap_get_next(&map, entry)))\n+\t\t\t\t\tputs(entry ? entry->name : \"NULL\");\n+\n \t\t} else if (!strcmp(\"remove\", cmd) && p1) {\n \n \t\t\tif (get_oid(p1, &oid)) {\n-- \n2.22.0.514.g3228928bce.dirty\n\n"},{"id":"378669","messageId":"20190707083002.7037-6-chriscool@tuxfamily.org","threadId":"51441","inReplyTo":"20190707083002.7037-1-chriscool@tuxfamily.org","subject":"[RFC PATCH 5/5] t0016: add 'add' and 'get_all' subcommand test","fromName":"Christian Couder","fromEmail":"christian.couder@gmail.com","sentAt":"2019-07-07T08:30:02Z","receivedAt":"2019-07-07T08:30:41Z","isPatch":true,"sender":{"key":"christian.couder@gmail.com","avatar":"https://avatars.githubusercontent.com/u/208954?v=4"},"body":"Let's add a test case to test both the 'add' and 'get_all' subcommand\nfrom \"test-oidmap.c\", and through them oidmap_add() and\noidmap_get_next() from \"oidmap.{c,h}\".\n\nSigned-off-by: Christian Couder \n---\n t/t0016-oidmap.sh | 26 ++++++++++++++++++++++++++\n 1 file changed, 26 insertions(+)\n\ndiff --git a/t/t0016-oidmap.sh b/t/t0016-oidmap.sh\nindex bbe719e950..1d3196d624 100755\n--- a/t/t0016-oidmap.sh\n+++ b/t/t0016-oidmap.sh\n@@ -67,6 +67,32 @@ Unknown oid: invalidOid\n \n '\n \n+test_expect_success 'add and get_all' '\n+\n+test_oidmap \"add one 1\n+add one un\n+add two 2\n+add two deux\n+add three 3\n+get_all two\n+get_all four\n+get_all invalidOid\n+get_all three\n+get_all one\" \"1\n+un\n+2\n+deux\n+3\n+deux\n+2\n+NULL\n+Unknown oid: invalidOid\n+3\n+un\n+1\"\n+\n+'\n+\n test_expect_success 'remove' '\n \n test_oidmap \"put one 1\n-- \n2.22.0.514.g3228928bce.dirty\n\n"},{"id":"378706","messageId":"xmqqd0ikxok6.fsf@gitster-ct.c.googlers.com","threadId":"51441","inReplyTo":"20190707083002.7037-1-chriscool@tuxfamily.org","subject":"Re: [RFC PATCH 0/5] oidmap: handle entries with the same key","fromName":"Junio C Hamano","fromEmail":"gitster@pobox.com","sentAt":"2019-07-08T20:24:09Z","receivedAt":"2019-07-08T20:24:14Z","isPatch":true,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"Christian Couder writes:\n\n> This is an RFC patch series that is not intended to be merged for now,\n> as it looks like we don't need oidmaps that can handle several entries\n> with the same key yet.\n\nWhat does it even mean for a map to allow multiple entries per key?\nWhen you have a key and its value, you must retrieve all existing\nentries for the key and see their values before deciding if you want\nto add yet another entry to the already existing set? When you have\na key, you must retrieve all existing entries to see if any of them\nis what you want?\n\nWhat I am wondering is if people usually do \"a single list/set of\nvalues that is associated with each key\" for such an application.\nObviously you do not need a map that allows multiple entries per key\nif you did so---is there an advantage of a map that allows multiple\nentries per key?\n\n> As I needed this for my work on reftable, I thought that...\n\nI actually think that showing how it is used in the real application\n(reftable?) is the best way to illustrate why this is useful and to\nget opinions from others.\n"},{"id":"378899","messageId":"xmqqlfx3p0zo.fsf@gitster-ct.c.googlers.com","threadId":"51441","inReplyTo":"xmqqd0ikxok6.fsf@gitster-ct.c.googlers.com","subject":"Re: [RFC PATCH 0/5] oidmap: handle entries with the same key","fromName":"Junio C Hamano","fromEmail":"gitster@pobox.com","sentAt":"2019-07-12T18:21:47Z","receivedAt":"2019-07-12T18:22:24Z","isPatch":true,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"Junio C Hamano writes:\n\n> Christian Couder writes:\n>\n>> This is an RFC patch series that is not intended to be merged for now,\n>> as it looks like we don't need oidmaps that can handle several entries\n>> with the same key yet.\n>\n> What does it even mean for a map to allow multiple entries per key?\n\nAh, one thing that I was missing (perhaps it was obvious to\neverybody else but me X-<) was that this is merely to expose what is\nalready available in the underlying hashmap API, so let's not bother\nwith the \"don't people usually do a single key to a value, which\nhappens to be a bag of stuff (not just a single stuff)?\" question.\n\nAnd from that \"a generic hashmap can do this, and an upcoming code\nneeds to use a hashmap keyed with oid in the same fashion\" point of\nview, the new wrappers the patches add all made sense to me.\n\n>> As I needed this for my work on reftable, I thought that...\n>\n> I actually think that showing how it is used in the real application\n> (reftable?) is the best way to illustrate why this is useful and to\n> get opinions from others.\n\nThis part still stands, though.\n\nThanks.\n"},{"id":"378910","messageId":"20190712215815.GB3593@sigill.intra.peff.net","threadId":"51441","inReplyTo":"xmqqlfx3p0zo.fsf@gitster-ct.c.googlers.com","subject":"Re: [RFC PATCH 0/5] oidmap: handle entries with the same key","fromName":"Jeff King","fromEmail":"peff@peff.net","sentAt":"2019-07-12T21:58:16Z","receivedAt":"2019-07-12T21:58:27Z","isPatch":true,"sender":{"key":"peff@peff.net","avatar":"https://avatars.githubusercontent.com/u/45925?v=4"},"body":"On Fri, Jul 12, 2019 at 11:21:47AM -0700, Junio C Hamano wrote:\n\n> > Christian Couder writes:\n> >\n> >> This is an RFC patch series that is not intended to be merged for now,\n> >> as it looks like we don't need oidmaps that can handle several entries\n> >> with the same key yet.\n> >\n> > What does it even mean for a map to allow multiple entries per key?\n> \n> Ah, one thing that I was missing (perhaps it was obvious to\n> everybody else but me X-<) was that this is merely to expose what is\n> already available in the underlying hashmap API, so let's not bother\n> with the \"don't people usually do a single key to a value, which\n> happens to be a bag of stuff (not just a single stuff)?\" question.\n> \n> And from that \"a generic hashmap can do this, and an upcoming code\n> needs to use a hashmap keyed with oid in the same fashion\" point of\n> view, the new wrappers the patches add all made sense to me.\n\nFWIW, I went through the same thought process. :)\n\nOne devil's advocate point against, though: we found recently that khash\nperforms much better than hashmap.[ch] for the oidset data structure.\nAFAIK nobody has looked at whether the same is true for oidmap. But if\nit is, then this strategy may make it harder to switch.\n\n(OTOH, we already have kh_oid_map, so the two could probably co-exist\nand we could just convert particular callers from one to the other).\n\n> > I actually think that showing how it is used in the real application\n> > (reftable?) is the best way to illustrate why this is useful and to\n> > get opinions from others.\n> \n> This part still stands, though.\n\nAgreed.\n\n-Peff\n"}]}