Re: [PATCH Outreachy] mru: use double-linked list from list.h

[Jeff King <peff@peff.net>]

On Thu, Sep 28, 2017 at 08:38:39AM +0000, Olga Telezhnaya wrote:

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

The commit message is a good reason to talk about why we want to do
this. In this case, the answer may be fairly obvious. But I sometimes
find that things that are obvious to me as the patch author are not
quite as obvious to people reading it later (either reviewing, or six
months from now when they are hunting the cause of a bug).

> -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);
>  }

Nice, this hunk is very satisfying. :)

> -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);

Two minor style comments here:

  - Perhaps "tmp" is a better name than "p2" for the second argument of
    a list_for_each_safe, as it makes it less likely to confuse p1 and
    p2 (though admittedly the whole function is short enough that it
    probably doesn't matter much either way).

  - It's a good practice to declare variables in the smallest scope
    possible. So I think the declaration of to_free could go inside the
    loop.

    You could actually get rid of it entirely with:

      free(list_entry(p1, struct mru, list));

    but I certainly don't mind using a variable for better readability.

> @@ -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;
>  };

The decision to get rid of the "mru versus mru_entry" distinction
surprised me a little. In the original, a "struct mru" represented the
whole list. In the list.h implementation, a "struct list_head" serves
that purpose, as a sentinel value. But that sentinel doesn't need to
have an "item", right? I.e., we could have:

  struct mru {
          struct list_head head;
  };

  struct mru_entry {
          void *item;
	  struct list_head list;
  };

As I said in my response to Junio (and as we discussed a little
off-list), I think we can eventually move to having no structs at all
(just list_heads embedded inside the existing packfile objects). At
which point the user of the API would just declare:

  LIST_HEAD(packed_git_mru);

themselves. So I'm actually fine with this direction if we're using it
as the "middle step" that I mentioned there.

>  struct mru {
> -	struct mru_entry *head, *tail;
> +	struct list_head list;
> +        void *item;
>  };

The funny indentation in this diff shows that "void *item" is indented
with spaces, not a tab.

> [...]

I pointed out a few minor bits, but overall this is looking very strong.
Great work!

-Peff