{"thread":{"id":"47616","subject":"[PATCH] mru: Replace mru.[ch] with list.h implementation","startedAt":"2018-01-16T01:46:38Z","lastAt":"2018-01-19T23:39:38Z","messageCount":5,"participants":["Gargi Sharma","Christian Couder","Junio C Hamano","Jeff King"],"isPatch":true,"patchVersion":1,"patchTotal":null},"messages":[{"id":"336640","messageId":"1516067185-1087-1-git-send-email-gs051095@gmail.com","threadId":"47616","inReplyTo":null,"subject":"[PATCH] mru: Replace mru.[ch] with list.h implementation","fromName":"Gargi Sharma","fromEmail":"gs051095@gmail.com","sentAt":"2018-01-16T01:46:25Z","receivedAt":"2018-01-16T01:46:38Z","isPatch":true,"sender":{"key":"gs051095@gmail.com","avatar":"https://avatars.githubusercontent.com/u/8718814?v=4"},"body":"Replace the custom calls to mru.[ch] with calls to list.h. This patch is the\nfinal step in removing the mru API completely and inlining the logic.\n\nAnother discussion, here\n(https://public-inbox.org/git/CAOCi2DGYQr4jFf5ObY2buyhNJeaAPQKF8tbojn2W0b18Eo+Wgw@mail.gmail.com/)\nwas on what has to be done with the next pointer of packed git type\ninside the\npacked_git structure. It can be removed _given_ that no one needs to\naccess the list in order and can be sent as another patch.\n\n---\nChanges in v2:\n        - Add a move to front function to the list API.\n        - Remove memory leak.\n        - Remove redundant remove operations on the list.\n\nThe commit has been built on top of ot/mru-on-list branch.\n\n Makefile               |  1 -\n builtin/pack-objects.c | 12 ++++++------\n cache.h                |  9 +++++----\n list.h                 |  7 +++++++\n mru.c                  | 27 ---------------------------\n mru.h                  | 40 ----------------------------------------\n packfile.c             | 18 +++++++++---------\n sha1_file.c            |  1 -\n 8 files changed, 27 insertions(+), 88 deletions(-)\n delete mode 100644 mru.c\n delete mode 100644 mru.h\n\ndiff --git a/Makefile b/Makefile\nindex ed4ca43..4a79ec5 100644\n--- a/Makefile\n+++ b/Makefile\n@@ -814,7 +814,6 @@ LIB_OBJS += merge.o\n LIB_OBJS += merge-blobs.o\n LIB_OBJS += merge-recursive.o\n LIB_OBJS += mergesort.o\n-LIB_OBJS += mru.o\n LIB_OBJS += name-hash.o\n LIB_OBJS += notes.o\n LIB_OBJS += notes-cache.o\ndiff --git a/builtin/pack-objects.c b/builtin/pack-objects.c\nindex ba81234..4064e35 100644\n--- a/builtin/pack-objects.c\n+++ b/builtin/pack-objects.c\n@@ -24,7 +24,7 @@\n #include \"reachable.h\"\n #include \"sha1-array.h\"\n #include \"argv-array.h\"\n-#include \"mru.h\"\n+#include \"list.h\"\n #include \"packfile.h\"\n \n static const char *pack_usage[] = {\n@@ -1012,9 +1012,8 @@ static int want_object_in_pack(const unsigned char *sha1,\n \t\t\treturn want;\n \t}\n \n-\tlist_for_each(pos, &packed_git_mru.list) {\n-\t\tstruct mru *entry = list_entry(pos, struct mru, list);\n-\t\tstruct packed_git *p = entry->item;\n+\tlist_for_each(pos, &packed_git_mru) {\n+\t\tstruct packed_git *p = list_entry(pos, struct packed_git, mru);\n \t\toff_t offset;\n \n \t\tif (p == *found_pack)\n@@ -1030,8 +1029,9 @@ static int want_object_in_pack(const unsigned char *sha1,\n \t\t\t\t*found_pack = p;\n \t\t\t}\n \t\t\twant = want_found_object(exclude, p);\n-\t\t\tif (!exclude && want > 0)\n-\t\t\t\tmru_mark(&packed_git_mru, entry);\n+\t\t\tif (!exclude && want > 0) {\n+\t\t\t\tlist_move_to_front(&p->mru, &packed_git_mru);\n+\t\t\t}\n \t\t\tif (want != -1)\n \t\t\t\treturn want;\n \t\t}\ndiff --git a/cache.h b/cache.h\nindex 49b083e..1a275ae 100644\n--- a/cache.h\n+++ b/cache.h\n@@ -4,7 +4,7 @@\n #include \"git-compat-util.h\"\n #include \"strbuf.h\"\n #include \"hashmap.h\"\n-#include \"mru.h\"\n+#include \"list.h\"\n #include \"advice.h\"\n #include \"gettext.h\"\n #include \"convert.h\"\n@@ -1566,6 +1566,7 @@ struct pack_window {\n \n extern struct packed_git {\n \tstruct packed_git *next;\n+\tstruct list_head mru;\n \tstruct pack_window *windows;\n \toff_t pack_size;\n \tconst void *index_data;\n@@ -1587,10 +1588,10 @@ extern struct packed_git {\n } *packed_git;\n \n /*\n- * A most-recently-used ordered version of the packed_git list, which can\n- * be iterated instead of packed_git (and marked via mru_mark).\n+ * A most-recently-used ordered version of the packed_git list.\n  */\n-extern struct mru packed_git_mru;\n+extern struct list_head packed_git_mru;\n+\n \n struct pack_entry {\n \toff_t offset;\ndiff --git a/list.h b/list.h\nindex eb60119..5129b0a 100644\n--- a/list.h\n+++ b/list.h\n@@ -93,6 +93,13 @@ static inline void list_move(struct list_head *elem, struct list_head *head)\n \tlist_add(elem, head);\n }\n \n+/* Move to the front of the list. */\n+static inline void list_move_to_front(struct list_head *elem, struct list_head *head)\n+{\n+\tlist_del(elem);\n+\tlist_add(elem, head);\n+}\n+\n /* Replace an old entry. */\n static inline void list_replace(struct list_head *old, struct list_head *newp)\n {\ndiff --git a/mru.c b/mru.c\ndeleted file mode 100644\nindex 8f3f34c..0000000\n--- a/mru.c\n+++ /dev/null\n@@ -1,27 +0,0 @@\n-#include \"cache.h\"\n-#include \"mru.h\"\n-\n-void mru_append(struct mru *head, void *item)\n-{\n-\tstruct mru *cur = xmalloc(sizeof(*cur));\n-\tcur->item = item;\n-\tlist_add_tail(&cur->list, &head->list);\n-}\n-\n-void mru_mark(struct mru *head, struct mru *entry)\n-{\n-\t/* To mark means to put at the front of the list. */\n-\tlist_del(&entry->list);\n-\tlist_add(&entry->list, &head->list);\n-}\n-\n-void mru_clear(struct mru *head)\n-{\n-\tstruct list_head *pos;\n-\tstruct list_head *tmp;\n-\n-\tlist_for_each_safe(pos, tmp, &head->list) {\n-\t\tfree(list_entry(pos, struct mru, list));\n-\t}\n-\tINIT_LIST_HEAD(&head->list);\n-}\ndiff --git a/mru.h b/mru.h\ndeleted file mode 100644\nindex 80a589e..0000000\n--- a/mru.h\n+++ /dev/null\n@@ -1,40 +0,0 @@\n-#ifndef MRU_H\n-#define MRU_H\n-\n-#include \"list.h\"\n-\n-/**\n- * A simple most-recently-used cache, backed by a doubly-linked list.\n- *\n- * Usage is roughly:\n- *\n- *   // Create a list.  Zero-initialization is required.\n- *   static struct mru cache;\n- *   INIT_LIST_HEAD(&cache.list);\n- *\n- *   // Add new item to the end of the list.\n- *   void *item;\n- *   ...\n- *   mru_append(&cache, item);\n- *\n- *   // Mark an item as used, moving it to the front of the list.\n- *   mru_mark(&cache, item);\n- *\n- *   // Reset the list to empty, cleaning up all resources.\n- *   mru_clear(&cache);\n- *\n- * Note that you SHOULD NOT call mru_mark() and then continue traversing the\n- * list; it reorders the marked item to the front of the list, and therefore\n- * you will begin traversing the whole list again.\n- */\n-\n-struct mru {\n-\tstruct list_head list;\n-\tvoid *item;\n-};\n-\n-void mru_append(struct mru *head, void *item);\n-void mru_mark(struct mru *head, struct mru *entry);\n-void mru_clear(struct mru *head);\n-\n-#endif /* MRU_H */\ndiff --git a/packfile.c b/packfile.c\nindex 502d915..0a25cf2 100644\n--- a/packfile.c\n+++ b/packfile.c\n@@ -1,5 +1,5 @@\n #include \"cache.h\"\n-#include \"mru.h\"\n+#include \"list.h\"\n #include \"pack.h\"\n #include \"dir.h\"\n #include \"mergesort.h\"\n@@ -40,7 +40,7 @@ static unsigned int pack_max_fds;\n static size_t peak_pack_mapped;\n static size_t pack_mapped;\n struct packed_git *packed_git;\n-struct mru packed_git_mru = {{&packed_git_mru.list, &packed_git_mru.list}};\n+LIST_HEAD(packed_git_mru);\n \n #define SZ_FMT PRIuMAX\n static inline uintmax_t sz_fmt(size_t s) { return s; }\n@@ -859,9 +859,9 @@ static void prepare_packed_git_mru(void)\n {\n \tstruct packed_git *p;\n \n-\tmru_clear(&packed_git_mru);\n-\tfor (p = packed_git; p; p = p->next)\n-\t\tmru_append(&packed_git_mru, p);\n+\tfor (p = packed_git; p; p = p->next) {\n+\t\tlist_add_tail(&p->mru, &packed_git_mru);\n+\t}\n }\n \n static int prepare_packed_git_run_once = 0;\n@@ -1830,10 +1830,10 @@ int find_pack_entry(const unsigned char *sha1, struct pack_entry *e)\n \tif (!packed_git)\n \t\treturn 0;\n \n-\tlist_for_each(pos, &packed_git_mru.list) {\n-\t\tstruct mru *p = list_entry(pos, struct mru, list);\n-\t\tif (fill_pack_entry(sha1, e, p->item)) {\n-\t\t\tmru_mark(&packed_git_mru, p);\n+\tlist_for_each(pos, &packed_git_mru) {\n+\t\tstruct packed_git *p = list_entry(pos, struct packed_git, mru);\n+\t\tif (fill_pack_entry(sha1, e, p)) {\n+\t\t\tlist_move_to_front(&p->mru, &packed_git_mru);\n \t\t\treturn 1;\n \t\t}\n \t}\ndiff --git a/sha1_file.c b/sha1_file.c\nindex 5a20148..e664f2d 100644\n--- a/sha1_file.c\n+++ b/sha1_file.c\n@@ -24,7 +24,6 @@\n #include \"bulk-checkin.h\"\n #include \"streaming.h\"\n #include \"dir.h\"\n-#include \"mru.h\"\n #include \"list.h\"\n #include \"mergesort.h\"\n #include \"quote.h\"\n-- \n2.7.4\n\n"},{"id":"336916","messageId":"CAP8UFD0oBfmwx6r8rFMLzCyhEoy6QMQ-5RHJv=2WavYgE9FSMQ@mail.gmail.com","threadId":"47616","inReplyTo":"1516067185-1087-1-git-send-email-gs051095@gmail.com","subject":"Re: [PATCH] mru: Replace mru.[ch] with list.h implementation","fromName":"Christian Couder","fromEmail":"christian.couder@gmail.com","sentAt":"2018-01-19T18:26:37Z","receivedAt":"2018-01-19T18:26:45Z","isPatch":true,"sender":{"key":"christian.couder@gmail.com","avatar":"https://avatars.githubusercontent.com/u/208954?v=4"},"body":"On Tue, Jan 16, 2018 at 2:46 AM, Gargi Sharma <gs051095@gmail.com> wrote:\n> Replace the custom calls to mru.[ch] with calls to list.h. This patch is the\n> final step in removing the mru API completely and inlining the logic.\n\nYou might want to say that this provides a significant code reduction\nwhich shows that the mru API is not a very useful abstraction anymore.\n\n> Another discussion, here\n> (https://public-inbox.org/git/CAOCi2DGYQr4jFf5ObY2buyhNJeaAPQKF8tbojn2W0b18Eo+Wgw@mail.gmail.com/)\n> was on what has to be done with the next pointer of packed git type\n\nI think using \"pointer to a 'struct packed_git'\" instead of \"pointer\nof packed git type\" would be clearer here, but anyway see below.\n\n> inside the\n> packed_git structure. It can be removed _given_ that no one needs to\n> access the list in order and can be sent as another patch.\n\nI don't think it's worth pointing to a discussion about a future\nimprovement in the commit message. You could perhaps even remove all\nthe above paragraph as this commit is valuable and self contained\nenough by itself.\n\n> ---\n> Changes in v2:\n>         - Add a move to front function to the list API.\n>         - Remove memory leak.\n>         - Remove redundant remove operations on the list.\n>\n> The commit has been built on top of ot/mru-on-list branch.\n\nNice!\n\n>  Makefile               |  1 -\n>  builtin/pack-objects.c | 12 ++++++------\n>  cache.h                |  9 +++++----\n>  list.h                 |  7 +++++++\n>  mru.c                  | 27 ---------------------------\n>  mru.h                  | 40 ----------------------------------------\n>  packfile.c             | 18 +++++++++---------\n>  sha1_file.c            |  1 -\n>  8 files changed, 27 insertions(+), 88 deletions(-)\n>  delete mode 100644 mru.c\n>  delete mode 100644 mru.h\n\nVery nice!\n\n[...]\n\n> @@ -1030,8 +1029,9 @@ static int want_object_in_pack(const unsigned char *sha1,\n>                                 *found_pack = p;\n>                         }\n>                         want = want_found_object(exclude, p);\n> -                       if (!exclude && want > 0)\n> -                               mru_mark(&packed_git_mru, entry);\n> +                       if (!exclude && want > 0) {\n> +                               list_move_to_front(&p->mru, &packed_git_mru);\n> +                       }\n\nStyle: we usually remove brackets when there is one line after the\nif(...) line. (See the 2 lines that you delete.)\n\nOtherwise the patch looks good to me.\n\nThanks,\nChristian.\n"},{"id":"336934","messageId":"xmqqefmlpnpj.fsf@gitster.mtv.corp.google.com","threadId":"47616","inReplyTo":"CAP8UFD0oBfmwx6r8rFMLzCyhEoy6QMQ-5RHJv=2WavYgE9FSMQ@mail.gmail.com","subject":"Re: [PATCH] mru: Replace mru.[ch] with list.h implementation","fromName":"Junio C Hamano","fromEmail":"gitster@pobox.com","sentAt":"2018-01-19T21:01:44Z","receivedAt":"2018-01-19T21:01:51Z","isPatch":true,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"Christian Couder <christian.couder@gmail.com> writes:\n\n> On Tue, Jan 16, 2018 at 2:46 AM, Gargi Sharma <gs051095@gmail.com> wrote:\n>> Replace the custom calls to mru.[ch] with calls to list.h. This patch is the\n>> final step in removing the mru API completely and inlining the logic.\n>\n> You might want to say that this provides a significant code reduction\n> which shows that the mru API is not a very useful abstraction anymore.\n>\n>> Another discussion, here\n>> (https://public-inbox.org/git/CAOCi2DGYQr4jFf5ObY2buyhNJeaAPQKF8tbojn2W0b18Eo+Wgw@mail.gmail.com/)\n>> was on what has to be done with the next pointer of packed git type\n>\n> I think using \"pointer to a 'struct packed_git'\" instead of \"pointer\n> of packed git type\" would be clearer here, but anyway see below.\n>\n>> inside the\n>> packed_git structure. It can be removed _given_ that no one needs to\n>> access the list in order and can be sent as another patch.\n>\n> I don't think it's worth pointing to a discussion about a future\n> improvement in the commit message. You could perhaps even remove all\n> the above paragraph as this commit is valuable and self contained\n> enough by itself.\n\nTrue. \n\nIf it is summarizing conclusion of the earlier discussion, that is a\ndifferent matter, though.\n\nIt is perfectly OK to have it under \"---\" line, even if it is merely\nvoicing author's opinion, by the way.  It can serve as a good\ndiscussion (re-)starter.\n\n\n>> ---\n\nMissing sign-off?\n\n>> Changes in v2:\n>>         - Add a move to front function to the list API.\n>>         - Remove memory leak.\n>>         - Remove redundant remove operations on the list.\n>>\n>> The commit has been built on top of ot/mru-on-list branch.\n>\n> Nice!\n>\n>>  Makefile               |  1 -\n>>  builtin/pack-objects.c | 12 ++++++------\n>>  cache.h                |  9 +++++----\n>>  list.h                 |  7 +++++++\n>>  mru.c                  | 27 ---------------------------\n>>  mru.h                  | 40 ----------------------------------------\n>>  packfile.c             | 18 +++++++++---------\n>>  sha1_file.c            |  1 -\n>>  8 files changed, 27 insertions(+), 88 deletions(-)\n>>  delete mode 100644 mru.c\n>>  delete mode 100644 mru.h\n>\n> Very nice!\n\nYes, nice reduction.\n\n>\n> [...]\n>\n>> @@ -1030,8 +1029,9 @@ static int want_object_in_pack(const unsigned char *sha1,\n>>                                 *found_pack = p;\n>>                         }\n>>                         want = want_found_object(exclude, p);\n>> -                       if (!exclude && want > 0)\n>> -                               mru_mark(&packed_git_mru, entry);\n>> +                       if (!exclude && want > 0) {\n>> +                               list_move_to_front(&p->mru, &packed_git_mru);\n>> +                       }\n>\n> Style: we usually remove brackets when there is one line after the\n> if(...) line. (See the 2 lines that you delete.)\n>\n> Otherwise the patch looks good to me.\n>\n> Thanks,\n> Christian.\n"},{"id":"336941","messageId":"20180119214655.GB12074@sigill.intra.peff.net","threadId":"47616","inReplyTo":"1516067185-1087-1-git-send-email-gs051095@gmail.com","subject":"Re: [PATCH] mru: Replace mru.[ch] with list.h implementation","fromName":"Jeff King","fromEmail":"peff@peff.net","sentAt":"2018-01-19T21:46:55Z","receivedAt":"2018-01-19T21:47:01Z","isPatch":true,"sender":{"key":"peff@peff.net","avatar":"https://avatars.githubusercontent.com/u/45925?v=4"},"body":"On Mon, Jan 15, 2018 at 08:46:25PM -0500, Gargi Sharma wrote:\n\n> Replace the custom calls to mru.[ch] with calls to list.h. This patch is the\n> final step in removing the mru API completely and inlining the logic.\n> \n> Another discussion, here\n> (https://public-inbox.org/git/CAOCi2DGYQr4jFf5ObY2buyhNJeaAPQKF8tbojn2W0b18Eo+Wgw@mail.gmail.com/)\n> was on what has to be done with the next pointer of packed git type\n> inside the\n> packed_git structure. It can be removed _given_ that no one needs to\n> access the list in order and can be sent as another patch.\n\nThanks for picking this up again. I agree that this is probably a good\nstopping point for now, as I think just combining this with the 'next'\npointer may carry more side effects.\n\nAside from the braces thing that Christian mentioned (and the missing\nsignoff), this all looks good to me.\n\n-Peff\n"},{"id":"336959","messageId":"CAOCi2DE_t_ppRZjiZm6CKJByL0nErTci1D7EL5U3KeCRNMyc+Q@mail.gmail.com","threadId":"47616","inReplyTo":"20180119214655.GB12074@sigill.intra.peff.net","subject":"Re: [PATCH] mru: Replace mru.[ch] with list.h implementation","fromName":"Gargi Sharma","fromEmail":"gs051095@gmail.com","sentAt":"2018-01-19T23:39:03Z","receivedAt":"2018-01-19T23:39:38Z","isPatch":true,"sender":{"key":"gs051095@gmail.com","avatar":"https://avatars.githubusercontent.com/u/8718814?v=4"},"body":"On Fri, Jan 19, 2018 at 9:46 PM, Jeff King <peff@peff.net> wrote:\n>\n> On Mon, Jan 15, 2018 at 08:46:25PM -0500, Gargi Sharma wrote:\n>\n> > Replace the custom calls to mru.[ch] with calls to list.h. This patch is the\n> > final step in removing the mru API completely and inlining the logic.\n> >\n> > Another discussion, here\n> > (https://public-inbox.org/git/CAOCi2DGYQr4jFf5ObY2buyhNJeaAPQKF8tbojn2W0b18Eo+Wgw@mail.gmail.com/)\n> > was on what has to be done with the next pointer of packed git type\n> > inside the\n> > packed_git structure. It can be removed _given_ that no one needs to\n> > access the list in order and can be sent as another patch.\n>\n> Thanks for picking this up again. I agree that this is probably a good\n> stopping point for now, as I think just combining this with the 'next'\n> pointer may carry more side effects.\nAgreed, hence just thought that if the discussion is started again, we\ncan point them\nto the email thread.\n>\n> Aside from the braces thing that Christian mentioned (and the missing\n> signoff), this all looks good to me.\nThanks, made the changes and sent a v3,\n\nBest,\nGargi\n>\n> -Peff\n"}]}