From 7c847fd7d4fee0fa5e0314f409eb06cfda2c289b Mon Sep 17 00:00:00 2001 From: Aurelien Foret Date: Fri, 25 Mar 2005 22:09:14 +0000 Subject: Backport from pacman 2.9.5 - list_remove, list_check and list_reverse - sortbydeps(mode) --- lib/libalpm/add.c | 2 +- lib/libalpm/deps.c | 20 +++++-- lib/libalpm/deps.h | 2 +- lib/libalpm/list.c | 148 +++++++++++++++++++++++++++++++++++++-------------- lib/libalpm/list.h | 4 +- lib/libalpm/remove.c | 12 ++++- 6 files changed, 140 insertions(+), 48 deletions(-) (limited to 'lib') diff --git a/lib/libalpm/add.c b/lib/libalpm/add.c index f80fe9f0..880b4dc3 100644 --- a/lib/libalpm/add.c +++ b/lib/libalpm/add.c @@ -189,7 +189,7 @@ int add_prepare(pmdb_t *db, pmtrans_t *trans, PMList **data) /* re-order w.r.t. dependencies */ _alpm_log(PM_LOG_FLOW2, "sorting by dependencies..."); - lp = sortbydeps(trans->packages); + lp = sortbydeps(trans->packages, PM_TRANS_TYPE_ADD); /* free the old alltargs */ for(j = trans->packages; j; j = j->next) { j->data = NULL; diff --git a/lib/libalpm/deps.c b/lib/libalpm/deps.c index eb9a983d..0e210b4e 100644 --- a/lib/libalpm/deps.c +++ b/lib/libalpm/deps.c @@ -35,17 +35,20 @@ /* Re-order a list of target packages with respect to their dependencies. * - * Example: + * Example (PM_TRANS_TYPE_ADD): * A depends on C * B depends on A * Target order is A,B,C,D * * Should be re-ordered to C,A,B,D * + * mode should be either PM_TRANS_TYPE_ADD or PM_TRANS_TYPE_REMOVE. This + * affects the dependency order sortbydeps() will use. + * * This function returns the new PMList* target list. * */ -PMList *sortbydeps(PMList *targets) +PMList *sortbydeps(PMList *targets, int mode) { PMList *newtargs = NULL; PMList *i, *j, *k; @@ -104,11 +107,22 @@ PMList *sortbydeps(PMList *targets) for(i = targets; i; i = i->next) { i->data = NULL; } - pm_list_free(targets); + FREELIST(targets); } targets = newtargs; clean = 1; } + if(mode == PM_TRANS_TYPE_REMOVE) { + /* we're removing packages, so reverse the order */ + newtargs = _alpm_list_reverse(targets); + /* free the old one */ + for(i = targets; i; i = i->next) { + i->data = NULL; + } + FREELIST(targets); + targets = newtargs; + } + return(targets); } diff --git a/lib/libalpm/deps.h b/lib/libalpm/deps.h index 60b3a6d8..3a895cbd 100644 --- a/lib/libalpm/deps.h +++ b/lib/libalpm/deps.h @@ -24,7 +24,7 @@ #include "db.h" #include "sync.h" -PMList *sortbydeps(PMList *targets); +PMList *sortbydeps(PMList *targets, int mode); PMList *checkdeps(pmdb_t *db, unsigned short op, PMList *packages); void splitdep(char *depstr, pmdepend_t *depend); PMList *removedeps(pmdb_t *db, PMList *targs); diff --git a/lib/libalpm/list.c b/lib/libalpm/list.c index 286076d9..9b3b11e9 100644 --- a/lib/libalpm/list.c +++ b/lib/libalpm/list.c @@ -23,9 +23,34 @@ #include #include #include +#include /* pacman */ #include "list.h" +/* Check PMList sanity + * + * 1: List seems to be OK. + * 0: We're in deep ... + */ +int _alpm_list_check(PMList* list) +{ + PMList* it = NULL; + + if(list == NULL) { + return(1); + } + if(list->last == NULL) { + return(0); + } + + for(it = list; it && it->next; it = it->next); + if(it != list->last) { + return(0); + } + + return(1); +} + PMList* pm_list_new() { PMList *list = NULL; @@ -37,6 +62,7 @@ PMList* pm_list_new() list->data = NULL; list->prev = NULL; list->next = NULL; + list->last = list; return(list); } @@ -74,9 +100,13 @@ PMList* pm_list_add(PMList *list, void *data) return(NULL); } lp->next->prev = lp; + lp->last = NULL; lp = lp->next; } + lp->data = data; + ptr->last = lp; + return(ptr); } @@ -102,63 +132,78 @@ PMList* pm_list_add_sorted(PMList *list, void *data, pm_fn_cmp fn) /* Insert node before insertion point. */ add->prev = prev; add->next = iter; + if(iter != NULL) { - /* Not at end. */ - iter->prev = add; + iter->prev = add; /* Not at end. */ + } else { + if (list != NULL) { + list->last = add; /* Added new to end, so update the link to last. */ + } } + if(prev != NULL) { - /* In middle. */ - prev->next = add; + prev->next = add; /* In middle. */ } else { - /* Start or empty, new list head. */ - list = add; + if(list == NULL) { + add->last = add; + } else { + add->last = list->last; + list->last = NULL; + } + list = add; /* Start or empty, new list head. */ } return(list); } -/* Remove an item in a list. Use the given comparaison function to find the - * item. - * If found, 'ptr' is set to point to the removed element, so that the caller - * can free it. Otherwise, ptr is NULL. - * Return the new list (without the removed element). +/* list: the beginning of the list + * item: the item in the list to be removed + * + * returns: + * list with item removed */ -PMList *_alpm_list_remove(PMList *list, void *data, pm_fn_cmp fn, void **ptr) + +PMList* list_remove(PMList* list, PMList* item) { - PMList *i = list; + assert(_alpm_list_check(list)); - while(i) { - if(fn(data, i->data) == 0) { - break; + if(list == NULL || item == NULL) { + return(NULL); + } + + /* Remove first item in list. */ + if(item == list) { + if(list->next == NULL) { /* Only item in list. */ + pm_list_free(item); + return(NULL); + } else { + list->next->prev = NULL; + list->next->last = list->last; + list = list->next; + item->prev = item->next = NULL; + pm_list_free(item); + return(list); } - i = i->next; } - if(ptr) { - *ptr = NULL; + /* Remove last item in list. */ + if(list->last == item) { + list->last = item->prev; + item->prev->next = NULL; + item->prev = item->next = NULL; + pm_list_free(item); + return(list); } - if(i) { - /* we found a matching item */ - if(i->next) { - i->next->prev = i->prev; - } - if(i->prev) { - i->prev->next = i->next; - } - if(i == list) { - /* The item found is the first in the chain, - * so we move the header to the next element. - */ - list = list->next; - } + /* Remove middle item in list. */ + assert(item->prev != NULL && item->next != NULL); - if(ptr) { - *ptr = i->data; - } + item->prev->next = item->next; + item->next->prev = item->prev; + item->prev = item->next = NULL; + pm_list_free(item); - free(i); - } + assert(_alpm_list_check(list)); return(list); } @@ -201,10 +246,31 @@ PMList *pm_list_is_strin(char *needle, PMList *haystack) PMList* pm_list_last(PMList *list) { - PMList *ptr; + if (list == NULL) + return(NULL); - for(ptr = list; ptr && ptr->next; ptr = ptr->next); - return(ptr); + assert(list->last != NULL); + + return(list->last); +} + +/* Reverse the order of a list + * + * The caller is responsible for freeing the old list + */ +PMList* _alpm_list_reverse(PMList *list) +{ + /* simple but functional -- we just build a new list, starting + * with the old list's tail + */ + PMList *newlist = NULL; + PMList *lp; + + for(lp = list->last; lp; lp = lp->prev) { + newlist = pm_list_add(newlist, lp->data); + } + + return(newlist); } /* vim: set ts=2 sw=2 noet: */ diff --git a/lib/libalpm/list.h b/lib/libalpm/list.h index c5de46d0..fe0d6738 100644 --- a/lib/libalpm/list.h +++ b/lib/libalpm/list.h @@ -26,6 +26,7 @@ typedef struct __pmlist_t { void *data; struct __pmlist_t *prev; struct __pmlist_t *next; + struct __pmlist_t *last; } pmlist_t; typedef struct __pmlist_t PMList; @@ -39,11 +40,12 @@ PMList *pm_list_new(); void pm_list_free(PMList *list); PMList *pm_list_add(PMList *list, void *data); PMList *pm_list_add_sorted(PMList *list, void *data, pm_fn_cmp fn); -PMList *_alpm_list_remove(PMList *list, void *data, pm_fn_cmp fn, void **ptr); +PMList* _alpm_list_remove(PMList* list, PMList* item); int pm_list_count(PMList *list); int pm_list_is_ptrin(PMList *haystack, void *needle); PMList *pm_list_is_strin(char *needle, PMList *haystack); PMList *pm_list_last(PMList *list); +PMList *_alpm_list_reverse(PMList *list); #endif /* _ALPM_LIST_H */ diff --git a/lib/libalpm/remove.c b/lib/libalpm/remove.c index 619dd913..e361fc70 100644 --- a/lib/libalpm/remove.c +++ b/lib/libalpm/remove.c @@ -65,7 +65,7 @@ int remove_loadtarget(pmdb_t *db, pmtrans_t *trans, char *name) int remove_prepare(pmdb_t *db, pmtrans_t *trans, PMList **data) { pmpkg_t *info; - PMList *lp; + PMList *lp, *i; ASSERT(db != NULL, RET_ERR(PM_ERR_DB_NULL, -1)); ASSERT(trans != NULL, RET_ERR(PM_ERR_TRANS_NULL, -1)); @@ -99,6 +99,16 @@ int remove_prepare(pmdb_t *db, pmtrans_t *trans, PMList **data) trans->packages = removedeps(db, trans->packages); } + /* re-order w.r.t. dependencies */ + _alpm_log(PM_LOG_FLOW2, "sorting by dependencies..."); + lp = sortbydeps(trans->packages, PM_TRANS_TYPE_REMOVE); + /* free the old alltargs */ + for(i = trans->packages; i; i = i->next) { + i->data = NULL; + } + FREELIST(trans->packages); + trans->packages = lp; + TRANS_CB(trans, PM_TRANS_EVT_DEPS_DONE, NULL, NULL); } -- cgit v1.2.3-24-g4f1b