/* * list.c * * Copyright (c) 2002-2005 by Judd Vinet <jvinet@zeroflux.org> * * This program is free software; you can redistribute it and/or modify * it under the terms of the GNU General Public License as published by * the Free Software Foundation; either version 2 of the License, or * (at your option) any later version. * * This program is distributed in the hope that it will be useful, * but WITHOUT ANY WARRANTY; without even the implied warranty of * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the * GNU General Public License for more details. * * You should have received a copy of the GNU General Public License * along with this program; if not, write to the Free Software * Foundation, Inc., 59 Temple Place - Suite 330, Boston, MA 02111-1307, * USA. */ #include "config.h" #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; list = (PMList *)malloc(sizeof(PMList)); if(list == NULL) { return(NULL); } list->data = NULL; list->prev = NULL; list->next = NULL; list->last = list; return(list); } void pm_list_free(PMList *list) { PMList *ptr, *it = list; while(it) { ptr = it->next; free(it->data); free(it); it = ptr; } } PMList* pm_list_add(PMList *list, void *data) { PMList *ptr, *lp; ptr = list; if(ptr == NULL) { ptr = pm_list_new(); if(ptr == NULL) { return(NULL); } } lp = pm_list_last(ptr); if(lp == ptr && lp->data == NULL) { /* nada */ } else { lp->next = pm_list_new(); if(lp->next == NULL) { return(NULL); } lp->next->prev = lp; lp->last = NULL; lp = lp->next; } lp->data = data; ptr->last = lp; return(ptr); } /* Add items to a list in sorted order. Use the given comparision func to * determine order. */ PMList* pm_list_add_sorted(PMList *list, void *data, pm_fn_cmp fn) { PMList *add; PMList *prev = NULL; PMList *iter = list; add = pm_list_new(); add->data = data; /* Find insertion point. */ while(iter) { if(fn(add->data, iter->data) <= 0) break; prev = iter; iter = iter->next; } /* Insert node before insertion point. */ add->prev = prev; add->next = iter; if(iter != NULL) { 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) { prev->next = add; /* In middle. */ } else { 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 the item is found, 'data' is pointing to the removed element. * Otherwise, it is set to NULL. * Return the new list (without the removed element). */ PMList *_alpm_list_remove(PMList *haystack, void *needle, pm_fn_cmp fn, void **data) { PMList *i = haystack; if(data) { *data = NULL; } while(i) { if(i->data == NULL) { continue; } if(fn(needle, i->data) == 0) { break; } i = i->next; } 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 == haystack) { /* The item found is the first in the chain */ if(haystack->next) { haystack->next->last = haystack->last; } haystack = haystack->next; } else if(i == haystack->last) { /* The item found is the last in the chain */ haystack->last = i->prev; } if(data) { *data = i->data; } i->data = NULL; free(i); } return(haystack); } int pm_list_count(PMList *list) { int i; PMList *lp; for(lp = list, i = 0; lp; lp = lp->next, i++); return(i); } int pm_list_is_in(void *needle, PMList *haystack) { PMList *lp; for(lp = haystack; lp; lp = lp->next) { if(lp->data == needle) { return(1); } } return(0); } /* Test for existence of a string in a PMList */ PMList *pm_list_is_strin(char *needle, PMList *haystack) { PMList *lp; for(lp = haystack; lp; lp = lp->next) { if(lp->data && !strcmp(lp->data, needle)) { return(lp); } } return(NULL); } PMList* pm_list_last(PMList *list) { if(list == NULL) { return(NULL); } assert(list->last != NULL); return(list->last); } /* Filter out any duplicate strings in a list. * * Not the most efficient way, but simple to implement -- we assemble * a new list, using is_in() to check for dupes at each iteration. * */ PMList *_alpm_list_remove_dupes(PMList *list) { PMList *i, *newlist = NULL; for(i = list; i; i = i->next) { if(!pm_list_is_strin(i->data, newlist)) { newlist = pm_list_add(newlist, strdup(i->data)); } } return newlist; } /* 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); } PMList *_alpm_list_strdup(PMList *list) { PMList *newlist = NULL; PMList *lp; for(lp = list; lp; lp = lp->next) { newlist = pm_list_add(newlist, strdup(lp->data)); } return(newlist); } /* vim: set ts=2 sw=2 noet: */