Backport from pacman 2.9.5

- list_remove, list_check and list_reverse
- sortbydeps(mode)

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