{"thread":{"id":"47650","subject":"[PATCH v3] mru: Replace mru.[ch] with list.h implementation","startedAt":"2018-01-19T23:36:45Z","lastAt":"2018-01-21T22:55:50Z","messageCount":7,"participants":["Gargi Sharma","Eric Sunshine","Eric Wong","René Scharfe"],"isPatch":true,"patchVersion":3,"patchTotal":null},"messages":[{"id":"336958","messageId":"1516404987-3420-1-git-send-email-gs051095@gmail.com","threadId":"47650","inReplyTo":null,"subject":"[PATCH v3] mru: Replace mru.[ch] with list.h implementation","fromName":"Gargi Sharma","fromEmail":"gs051095@gmail.com","sentAt":"2018-01-19T23:36:27Z","receivedAt":"2018-01-19T23:36:45Z","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\nthe final step in removing the mru API completely and inlining the logic.\nThis patch leads to significant code reduction and the mru API hence, is\nnot a useful abstraction anymore.\n\nSigned-off-by: Gargi Sharma <gs051095@gmail.com>\n---\nChanges in v3:\n\t- Make the commit message more descriptive.\n\t- Remove braces after if statement.\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\nA future improvement could be removing/changing the\ntype of nect pointer or dropping it entirely. See discussion\nhere:\nhttps://public-inbox.org/git/CAOCi2DGYQr4jFf5ObY2buyhNJeaAPQKF8tbojn2W0b18Eo+Wgw@mail.gmail.com/\n---\n Makefile               |  1 -\n builtin/pack-objects.c |  9 ++++-----\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, 25 insertions(+), 87 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..188ba3e 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@@ -1031,7 +1030,7 @@ static int want_object_in_pack(const unsigned char *sha1,\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\t\tlist_move_to_front(&p->mru, &packed_git_mru);\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":"336965","messageId":"CAPig+cQ9mMVvMLKSQOKxinc5iuRK61yTDQ511ZdNqEOtbCGoAQ@mail.gmail.com","threadId":"47650","inReplyTo":"1516404987-3420-1-git-send-email-gs051095@gmail.com","subject":"Re: [PATCH v3] mru: Replace mru.[ch] with list.h implementation","fromName":"Eric Sunshine","fromEmail":"sunshine@sunshineco.com","sentAt":"2018-01-20T00:59:47Z","receivedAt":"2018-01-20T00:59:53Z","isPatch":true,"sender":{"key":"sunshine@sunshineco.com","avatar":"https://avatars.githubusercontent.com/u/163641?v=4"},"body":"On Fri, Jan 19, 2018 at 6:36 PM, Gargi Sharma <gs051095@gmail.com> wrote:\n> Replace the custom calls to mru.[ch] with calls to list.h. This patch is\n> the final step in removing the mru API completely and inlining the logic.\n> This patch leads to significant code reduction and the mru API hence, is\n> not a useful abstraction anymore.\n\nA couple minor style nits below... (may not be worth a re-roll)\n\n> Signed-off-by: Gargi Sharma <gs051095@gmail.com>\n> ---\n> diff --git a/cache.h b/cache.h\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\nUnnecessary extra blank line.\n\n>  struct pack_entry {\n>         off_t offset;\n> diff --git a/packfile.c b/packfile.c\n> @@ -859,9 +859,9 @@ static void prepare_packed_git_mru(void)\n>  {\n>         struct packed_git *p;\n>\n> -       mru_clear(&packed_git_mru);\n> -       for (p = packed_git; p; p = p->next)\n> -               mru_append(&packed_git_mru, p);\n> +       for (p = packed_git; p; p = p->next) {\n> +               list_add_tail(&p->mru, &packed_git_mru);\n> +       }\n\nUnnecessary braces on for-loop.\n\n>  }\n"},{"id":"336966","messageId":"20180120010228.hhyvirqp44taf3cz@dcvr.yhbt.net","threadId":"47650","inReplyTo":"1516404987-3420-1-git-send-email-gs051095@gmail.com","subject":"Re: [PATCH v3] mru: Replace mru.[ch] with list.h implementation","fromName":"Eric Wong","fromEmail":"e@80x24.org","sentAt":"2018-01-20T01:02:28Z","receivedAt":"2018-01-20T01:02:36Z","isPatch":true,"sender":{"key":"e@80x24.org","avatar":null},"body":"Gargi Sharma <gs051095@gmail.com> wrote:\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\nSince we already have list_move and it does the same thing,\nI don't think we need a new function, here.\n\nHackers coming from other projects (glibc/urcu/Linux kernel)\nmight appreciate having fewer differences from what they're used\nto.\n\nAnyways thanks for working on this!\n"},{"id":"336997","messageId":"CAOCi2DGKkLnY_=-7pMr9VyP7TVsj0b8w-msdNn9ZtXKK8g7u9g@mail.gmail.com","threadId":"47650","inReplyTo":"20180120010228.hhyvirqp44taf3cz@dcvr.yhbt.net","subject":"Re: [PATCH v3] mru: Replace mru.[ch] with list.h implementation","fromName":"Gargi Sharma","fromEmail":"gs051095@gmail.com","sentAt":"2018-01-20T22:24:42Z","receivedAt":"2018-01-20T22:25:17Z","isPatch":true,"sender":{"key":"gs051095@gmail.com","avatar":"https://avatars.githubusercontent.com/u/8718814?v=4"},"body":"On Sat, Jan 20, 2018 at 1:02 AM, Eric Wong <e@80x24.org> wrote:\n> Gargi Sharma <gs051095@gmail.com> wrote:\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>>       list_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>> +     list_del(elem);\n>> +     list_add(elem, head);\n>> +}\n>> +\n>\n> Since we already have list_move and it does the same thing,\n> I don't think we need a new function, here.\n>\n> Hackers coming from other projects (glibc/urcu/Linux kernel)\n> might appreciate having fewer differences from what they're used\n> to.\n\nI think the idea behind this function was that it is already being used in two\nplaces in the code and might be used in other places in the future. I agree\nwith your stance, but a list_move_to_front is pretty self explanatory and not\ntoo different, so it should be alright.\n\n>\n> Anyways thanks for working on this!\n"},{"id":"336998","messageId":"CAOCi2DGOkotCb+4SUCZShOp=r_=QMhMYBq4GUq-ATe=OE0XM3w@mail.gmail.com","threadId":"47650","inReplyTo":"CAPig+cQ9mMVvMLKSQOKxinc5iuRK61yTDQ511ZdNqEOtbCGoAQ@mail.gmail.com","subject":"Re: [PATCH v3] mru: Replace mru.[ch] with list.h implementation","fromName":"Gargi Sharma","fromEmail":"gs051095@gmail.com","sentAt":"2018-01-20T22:26:10Z","receivedAt":"2018-01-20T22:26:45Z","isPatch":true,"sender":{"key":"gs051095@gmail.com","avatar":"https://avatars.githubusercontent.com/u/8718814?v=4"},"body":"On Sat, Jan 20, 2018 at 12:59 AM, Eric Sunshine <sunshine@sunshineco.com> wrote:\n> On Fri, Jan 19, 2018 at 6:36 PM, Gargi Sharma <gs051095@gmail.com> wrote:\n>> Replace the custom calls to mru.[ch] with calls to list.h. This patch is\n>> the final step in removing the mru API completely and inlining the logic.\n>> This patch leads to significant code reduction and the mru API hence, is\n>> not a useful abstraction anymore.\n>\n> A couple minor style nits below... (may not be worth a re-roll)\n\nI can send a v4, it shouldn't be a problem. :)\n\n>\n>> Signed-off-by: Gargi Sharma <gs051095@gmail.com>\n>> ---\n>> diff --git a/cache.h b/cache.h\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> Unnecessary extra blank line.\n>\n>>  struct pack_entry {\n>>         off_t offset;\n>> diff --git a/packfile.c b/packfile.c\n>> @@ -859,9 +859,9 @@ static void prepare_packed_git_mru(void)\n>>  {\n>>         struct packed_git *p;\n>>\n>> -       mru_clear(&packed_git_mru);\n>> -       for (p = packed_git; p; p = p->next)\n>> -               mru_append(&packed_git_mru, p);\n>> +       for (p = packed_git; p; p = p->next) {\n>> +               list_add_tail(&p->mru, &packed_git_mru);\n>> +       }\n>\n> Unnecessary braces on for-loop.\n>\n>>  }\n"},{"id":"337017","messageId":"75c9bdc5-1c81-1e03-e865-5e74014bd590@web.de","threadId":"47650","inReplyTo":"CAOCi2DGKkLnY_=-7pMr9VyP7TVsj0b8w-msdNn9ZtXKK8g7u9g@mail.gmail.com","subject":"Re: [PATCH v3] mru: Replace mru.[ch] with list.h implementation","fromName":"René Scharfe","fromEmail":"l.s.r@web.de","sentAt":"2018-01-21T04:38:57Z","receivedAt":"2018-01-21T04:39:16Z","isPatch":true,"sender":{"key":"l.s.r@web.de","avatar":"https://avatars.githubusercontent.com/u/26122331?v=4"},"body":"Am 20.01.2018 um 23:24 schrieb Gargi Sharma:\n> On Sat, Jan 20, 2018 at 1:02 AM, Eric Wong <e@80x24.org> wrote:\n>> Gargi Sharma <gs051095@gmail.com> wrote:\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>>>        list_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>>> +     list_del(elem);\n>>> +     list_add(elem, head);\n>>> +}\n>>> +\n>>\n>> Since we already have list_move and it does the same thing,\n>> I don't think we need a new function, here.\n>>\n>> Hackers coming from other projects (glibc/urcu/Linux kernel)\n>> might appreciate having fewer differences from what they're used\n>> to.\n> \n> I think the idea behind this function was that it is already being used in two\n> places in the code and might be used in other places in the future. I agree\n> with your stance, but a list_move_to_front is pretty self explanatory and not\n> too different, so it should be alright.\n\nNot sure I understand the point about the function being already used as\nan argument for adding it, but if there is already one which has the\nexact sane behavior (list_move() in this case) then that should be used\ninstead of adding a duplicate.\n\nRené\n\n"},{"id":"337037","messageId":"CAOCi2DFjz=WD7kma5XUqAOKuPuTBg6OwnO2WjmKyn0gF1z7Cgg@mail.gmail.com","threadId":"47650","inReplyTo":"75c9bdc5-1c81-1e03-e865-5e74014bd590@web.de","subject":"Re: [PATCH v3] mru: Replace mru.[ch] with list.h implementation","fromName":"Gargi Sharma","fromEmail":"gs051095@gmail.com","sentAt":"2018-01-21T22:55:12Z","receivedAt":"2018-01-21T22:55:50Z","isPatch":true,"sender":{"key":"gs051095@gmail.com","avatar":"https://avatars.githubusercontent.com/u/8718814?v=4"},"body":"On Sun, Jan 21, 2018 at 4:38 AM, René Scharfe <l.s.r@web.de> wrote:\n>\n> Am 20.01.2018 um 23:24 schrieb Gargi Sharma:\n> > On Sat, Jan 20, 2018 at 1:02 AM, Eric Wong <e@80x24.org> wrote:\n> >> Gargi Sharma <gs051095@gmail.com> wrote:\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> >>>        list_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> >>> +     list_del(elem);\n> >>> +     list_add(elem, head);\n> >>> +}\n> >>> +\n> >>\n> >> Since we already have list_move and it does the same thing,\n> >> I don't think we need a new function, here.\n> >>\n> >> Hackers coming from other projects (glibc/urcu/Linux kernel)\n> >> might appreciate having fewer differences from what they're used\n> >> to.\n> >\n> > I think the idea behind this function was that it is already being used in two\n> > places in the code and might be used in other places in the future. I agree\n> > with your stance, but a list_move_to_front is pretty self explanatory and not\n> > too different, so it should be alright.\n>\n> Not sure I understand the point about the function being already used as\n> an argument for adding it, but if there is already one which has the\n> exact sane behavior (list_move() in this case) then that should be used\n> instead of adding a duplicate.\n\nThanks for bringing this to my attention, René. I can use list_move()\nto do the exact\nsame thing as list_move_to_front(). Will send another version.\n\nThanks,\nGargi\n>\n> René\n>\n"}]}