summaryrefslogtreecommitdiffstats
path: root/lib
diff options
context:
space:
mode:
authorAurelien Foret <aurelien@archlinux.org>2005-03-25 22:09:14 +0000
committerAurelien Foret <aurelien@archlinux.org>2005-03-25 22:09:14 +0000
commit7c847fd7d4fee0fa5e0314f409eb06cfda2c289b (patch)
tree0e9d02aaf7284066f506fef81a758276ba466b56 /lib
parent6e63ccfd0fdd19b6d710eb8dc84c85aaf25c3006 (diff)
downloadpacman-7c847fd7d4fee0fa5e0314f409eb06cfda2c289b.tar.xz
Backport from pacman 2.9.5
- list_remove, list_check and list_reverse - sortbydeps(mode)
Diffstat (limited to 'lib')
-rw-r--r--lib/libalpm/add.c2
-rw-r--r--lib/libalpm/deps.c20
-rw-r--r--lib/libalpm/deps.h2
-rw-r--r--lib/libalpm/list.c148
-rw-r--r--lib/libalpm/list.h4
-rw-r--r--lib/libalpm/remove.c12
6 files changed, 140 insertions, 48 deletions
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 <stdlib.h>
#include <string.h>
#include <stdio.h>
+#include <assert.h>
/* 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);
}