git@vger.kernel.org mailing list mirror (one of many)
 help / color / mirror / code / Atom feed
From: Junio C Hamano <gitster@pobox.com>
To: Olga Telezhnaya <olyatelezhnaya@gmail.com>
Cc: git@vger.kernel.org
Subject: Re: [PATCH Outreachy] mru: use double-linked list from list.h
Date: Thu, 28 Sep 2017 20:03:00 +0900	[thread overview]
Message-ID: <xmqq8tgz13x7.fsf@gitster.mtv.corp.google.com> (raw)
In-Reply-To: <0102015ec7a3424b-529be659-bdb6-42c4-a48f-db264f33d53a-000000@eu-west-1.amazonses.com> (Olga Telezhnaya's message of "Thu, 28 Sep 2017 08:38:39 +0000")

Olga Telezhnaya <olyatelezhnaya@gmail.com> writes:

> Simplify mru.c, mru.h and related code by reusing the double-linked list implementation from list.h instead of a custom one.

An overlong line (I can locally wrap it, so the patch does not have
to be re-sent only to fix this alone).

> Signed-off-by: Olga Telezhnaia <olyatelezhnaya@gmail.com>

Thanks for making your "From:" name match the "Signed-off-by:" name;
anglicising like you did is probably more friendly to the readers
than writing both in Cyrillic, which is another valid way to make
them match.

> Mentored-by: Christian Couder <christian.couder@gmail.com>
> Mentored by: Jeff King <peff@peff.net>
> ---
>  builtin/pack-objects.c |  5 +++--
>  mru.c                  | 51 +++++++++++++++-----------------------------------
>  mru.h                  | 31 +++++++++++++-----------------
>  packfile.c             |  6 ++++--
>  4 files changed, 35 insertions(+), 58 deletions(-)

As Christian mentioned earlier, nice line reduction ;-)

> diff --git a/builtin/pack-objects.c b/builtin/pack-objects.c
> index f721137eaf881..ba812349e0aab 100644
> --- a/builtin/pack-objects.c
%> +++ b/builtin/pack-objects.c
> @@ -995,8 +995,8 @@ static int want_object_in_pack(const unsigned char *sha1,
>  			       struct packed_git **found_pack,
>  			       off_t *found_offset)
>  {
> -	struct mru_entry *entry;
>  	int want;
> +	struct list_head *pos;
>  
>  	if (!exclude && local && has_loose_object_nonlocal(sha1))
>  		return 0;
> @@ -1012,7 +1012,8 @@ static int want_object_in_pack(const unsigned char *sha1,
>  			return want;
>  	}
>  
> -	for (entry = packed_git_mru.head; entry; entry = entry->next) {
> +	list_for_each(pos, &packed_git_mru.list) {
> +		struct mru *entry = list_entry(pos, struct mru, list);
>  		struct packed_git *p = entry->item;
>  		off_t offset;

I was a bit surprised to see a change outside mru.[ch] like this
one.  The reason why I was surprised was because I expected mru.[ch]
would offer its own API that encapsulates enumeration like this one
and this patch would just be reimplementing that API using the list
API, instead of rewriting the users of mru API to directly access
the list API.

Alas, there is no such mru API that lets a mru user to iterate over
elements, so the original of the above code were using mru's
implementation detail directly.

We probably want to invent mru_for_each() that hides the fact that
mru is implemented in terms of list_head from the users of mru API
and use it here.

> diff --git a/mru.c b/mru.c
> index 9dedae0287ed2..8b6ba3d9b7fad 100644
> --- a/mru.c
> +++ b/mru.c
> @@ -1,50 +1,29 @@
>  #include "cache.h"
>  #include "mru.h"
>  
> -void mru_append(struct mru *mru, void *item)
> +void mru_append(struct mru *head, void *item)
>  {
> -	struct mru_entry *cur = xmalloc(sizeof(*cur));
> +	struct mru *cur = xmalloc(sizeof(*cur));
>  	cur->item = item;
> -	cur->prev = mru->tail;
> -	cur->next = NULL;
> -
> -	if (mru->tail)
> -		mru->tail->next = cur;
> -	else
> -		mru->head = cur;
> -	mru->tail = cur;
> +	list_add_tail(&cur->list, &head->list);
>  }
>  
> -void mru_mark(struct mru *mru, struct mru_entry *entry)
> +void mru_mark(struct mru *head, struct mru *entry)
>  {
> -	/* If we're already at the front of the list, nothing to do */
> -	if (mru->head == entry)
> -		return;
> -
> -	/* Otherwise, remove us from our current slot... */
> -	if (entry->prev)
> -		entry->prev->next = entry->next;
> -	if (entry->next)
> -		entry->next->prev = entry->prev;
> -	else
> -		mru->tail = entry->prev;
> -
> -	/* And insert us at the beginning. */
> -	entry->prev = NULL;
> -	entry->next = mru->head;
> -	if (mru->head)
> -		mru->head->prev = entry;
> -	mru->head = entry;
> +	/* To mark means to put at the front of the list. */
> +	list_del(&entry->list);
> +	list_add(&entry->list, &head->list);
>  }
>  
> -void mru_clear(struct mru *mru)
> +void mru_clear(struct mru *head)
>  {
> -	struct mru_entry *p = mru->head;
> -
> -	while (p) {
> -		struct mru_entry *to_free = p;
> -		p = p->next;
> +	struct list_head *p1;
> +	struct list_head *p2;
> +	struct mru *to_free;
> +	
> +	list_for_each_safe(p1, p2, &head->list) {
> +		to_free = list_entry(p1, struct mru, list);
>  		free(to_free);
>  	}
> -	mru->head = mru->tail = NULL;
> +	INIT_LIST_HEAD(&head->list);
>  }
> diff --git a/mru.h b/mru.h
> index 42e4aeaa1098a..36a332af0bf88 100644
> --- a/mru.h
> +++ b/mru.h
> @@ -1,6 +1,8 @@
>  #ifndef MRU_H
>  #define MRU_H
>  
> +#include "list.h"
> +
>  /**
>   * A simple most-recently-used cache, backed by a doubly-linked list.
>   *
> @@ -8,18 +10,15 @@
>   *
>   *   // Create a list.  Zero-initialization is required.
>   *   static struct mru cache;
> - *   mru_append(&cache, item);
> - *   ...
> + *   INIT_LIST_HEAD(&cache.list);

"Zero-initialization is required." is no longer true, it seems, and
the comment above needs to be updated, right?

More importantly, this leaks to the user of the API the fact that
mru is internally implemented in terms of the list API, which is
not necessary (when we want to update the implementation later, we'd
need to update all the users again).  Perhaps you'd want

	INIT_MRU(cache);

which is #define'd in this file, perhaps like so:

	#define INIT_MRU(mru)	INIT_LIST_HEAD(&((mru).list))



> - *   // Iterate in MRU order.
> - *   struct mru_entry *p;
> - *   for (p = cache.head; p; p = p->next) {
> - *	if (matches(p->item))
> - *		break;
> - *   }

Ah, here is a good piece that illustrates what I meant earlier.
This could have been something like:

	// Iterate in MRU order.
	struct mru *item;
	mru_for_each(item, &cache) {
		if (matches(item))
			break;
	}

and then the user would not have to know mru is implemented in terms
of the list API.

> + *   // Add new item to the end of the list.
> + *   void *item;
> + *   ...
> + *   mru_append(&cache, item);
>   *
>   *   // Mark an item as used, moving it to the front of the list.
> - *   mru_mark(&cache, p);
> + *   mru_mark(&cache, item);
>   *
>   *   // Reset the list to empty, cleaning up all resources.
>   *   mru_clear(&cache);
> @@ -29,17 +28,13 @@
>   * you will begin traversing the whole list again.
>   */
>  
> -struct mru_entry {
> -	void *item;
> -	struct mru_entry *prev, *next;
> -};
> -
>  struct mru {
> -	struct mru_entry *head, *tail;
> +	struct list_head list;
> +        void *item;
>  };
>  
> -void mru_append(struct mru *mru, void *item);
> -void mru_mark(struct mru *mru, struct mru_entry *entry);
> -void mru_clear(struct mru *mru);
> +void mru_append(struct mru *head, void *item);
> +void mru_mark(struct mru *head, struct mru *entry);
> +void mru_clear(struct mru *head);
>  
>  #endif /* MRU_H */
> diff --git a/packfile.c b/packfile.c
> index f69a5c8d607af..ae3b0b2e9c09a 100644
> --- a/packfile.c
> +++ b/packfile.c
> @@ -876,6 +876,7 @@ void prepare_packed_git(void)
>  	for (alt = alt_odb_list; alt; alt = alt->next)
>  		prepare_packed_git_one(alt->path, 0);
>  	rearrange_packed_git();
> +	INIT_LIST_HEAD(&packed_git_mru.list);
>  	prepare_packed_git_mru();
>  	prepare_packed_git_run_once = 1;
>  }
> @@ -1824,13 +1825,14 @@ static int fill_pack_entry(const unsigned char *sha1,
>   */
>  int find_pack_entry(const unsigned char *sha1, struct pack_entry *e)
>  {
> -	struct mru_entry *p;
> +	struct list_head *pos;
>  
>  	prepare_packed_git();
>  	if (!packed_git)
>  		return 0;
>  
> -	for (p = packed_git_mru.head; p; p = p->next) {
> +	list_for_each(pos, &packed_git_mru.list) {
> +		struct mru *p = list_entry(pos, struct mru, list);
>  		if (fill_pack_entry(sha1, e, p->item)) {
>  			mru_mark(&packed_git_mru, p);
>  			return 1;

The same comment as the first hunk applies here, too.

Thanks.

  reply	other threads:[~2017-09-28 11:03 UTC|newest]

Thread overview: 26+ messages / expand[flat|nested]  mbox.gz  Atom feed  top
2017-09-27 10:18 [PATCH] [Outreachy] cleanup: use list.h in mru.h and mru.c Оля Тележная
2017-09-27 11:30 ` Christian Couder
2017-09-28  8:38   ` [PATCH Outreachy] mru: use double-linked list from list.h Olga Telezhnaya
2017-09-28 11:03     ` Junio C Hamano [this message]
2017-09-28 20:47       ` Jeff King
2017-09-28 21:56         ` Junio C Hamano
2017-09-28 22:19           ` Jeff King
2017-09-28 21:04     ` Jeff King
2017-09-28 22:42     ` Jeff King
2017-09-29  7:18       ` Christian Couder
2017-09-29  7:23         ` Jeff King
2017-09-29 11:50           ` Christian Couder
2017-09-29 16:08             ` Оля Тележная
2017-09-29 20:38               ` Оля Тележная
2017-09-29 23:40                 ` Jeff King
2017-09-30 18:09                   ` Оля Тележная
2017-10-02  8:22                     ` Jeff King
2017-09-29 23:37               ` Jeff King
2017-09-30  0:07                 ` Junio C Hamano
2017-09-30 17:51     ` [PATCH v2 " Olga Telezhnaya
2017-10-02  8:20       ` Jeff King
2017-10-02  9:37         ` Оля Тележная
2017-10-03 10:10           ` Jeff King
2017-11-08  1:44         ` Junio C Hamano
2017-11-08  4:22           ` Jeff King
2017-11-10 11:51             ` Оля Тележная

Reply instructions:

You may reply publicly to this message via plain-text email
using any one of the following methods:

* Save the following mbox file, import it into your mail client,
  and reply-to-all from there: mbox

  Avoid top-posting and favor interleaved quoting:
  https://en.wikipedia.org/wiki/Posting_style#Interleaved_style

  List information: http://vger.kernel.org/majordomo-info.html

* Reply using the --to, --cc, and --in-reply-to
  switches of git-send-email(1):

  git send-email \
    --in-reply-to=xmqq8tgz13x7.fsf@gitster.mtv.corp.google.com \
    --to=gitster@pobox.com \
    --cc=git@vger.kernel.org \
    --cc=olyatelezhnaya@gmail.com \
    /path/to/YOUR_REPLY

  https://kernel.org/pub/software/scm/git/docs/git-send-email.html

* If your mail client supports setting the In-Reply-To header
  via mailto: links, try the mailto: link
Be sure your reply has a Subject: header at the top and a blank line before the message body.
Code repositories for project(s) associated with this public inbox

	https://80x24.org/mirrors/git.git

This is a public inbox, see mirroring instructions
for how to clone and mirror all data and code used for this inbox;
as well as URLs for read-only IMAP folder(s) and NNTP newsgroup(s).