summaryrefslogtreecommitdiffstats
path: root/lib/libalpm/list.c
diff options
context:
space:
mode:
authorAurelien Foret <aurelien@archlinux.org>2005-03-25 23:09:14 +0100
committerAurelien Foret <aurelien@archlinux.org>2005-03-25 23:09:14 +0100
commit7c847fd7d4fee0fa5e0314f409eb06cfda2c289b (patch)
tree0e9d02aaf7284066f506fef81a758276ba466b56 /lib/libalpm/list.c
parent6e63ccfd0fdd19b6d710eb8dc84c85aaf25c3006 (diff)
downloadpacman-7c847fd7d4fee0fa5e0314f409eb06cfda2c289b.tar.gz
pacman-7c847fd7d4fee0fa5e0314f409eb06cfda2c289b.tar.xz
Backport from pacman 2.9.5
- list_remove, list_check and list_reverse - sortbydeps(mode)
Diffstat (limited to 'lib/libalpm/list.c')
-rw-r--r--lib/libalpm/list.c148
1 files changed, 107 insertions, 41 deletions
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: */