Olga Telezhnaya <olyatelezhnaya@xxxxxxxxx> 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@xxxxxxxxx>
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@xxxxxxxxx>
> Mentored by: Jeff King <peff@xxxxxxxx>
> ---
> 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.
