From 8865859dfc346c61f0e75fa429c5d307bd27368c Mon Sep 17 00:00:00 2001 From: Olga Telezhnaya Date: Sat, 30 Sep 2017 17:51:01 +0000 Subject: mru: use double-linked list from list.h Simplify mru.[ch] and related code by reusing the double-linked list implementation from list.h instead of a custom one. This commit is an intermediate step. Our final goal is to get rid of mru.[ch] at all and inline all logic. Mentored-by: Christian Couder Mentored by: Jeff King Signed-off-by: Olga Telezhnaia Signed-off-by: Junio C Hamano diff --git a/builtin/pack-objects.c b/builtin/pack-objects.c index f721137..ba81234 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; diff --git a/mru.c b/mru.c index 9dedae0..8f3f34c 100644 --- a/mru.c +++ b/mru.c @@ -1,50 +1,27 @@ #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; + struct list_head *pos; + struct list_head *tmp; - while (p) { - struct mru_entry *to_free = p; - p = p->next; - free(to_free); + list_for_each_safe(pos, tmp, &head->list) { + free(list_entry(pos, struct mru, list)); } - mru->head = mru->tail = NULL; + INIT_LIST_HEAD(&head->list); } diff --git a/mru.h b/mru.h index 42e4aea..80a589e 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); * - * // Iterate in MRU order. - * struct mru_entry *p; - * for (p = cache.head; p; p = p->next) { - * if (matches(p->item)) - * break; - * } + * // 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 f69a5c8..502d915 100644 --- a/packfile.c +++ b/packfile.c @@ -40,7 +40,7 @@ static unsigned int pack_max_fds; static size_t peak_pack_mapped; static size_t pack_mapped; struct packed_git *packed_git; -struct mru packed_git_mru; +struct mru packed_git_mru = {{&packed_git_mru.list, &packed_git_mru.list}}; #define SZ_FMT PRIuMAX static inline uintmax_t sz_fmt(size_t s) { return s; } @@ -1824,13 +1824,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; -- cgit v0.10.2-6-g49f6