From 616701726425417989ef1dca145b805deae6fe93 Mon Sep 17 00:00:00 2001 From: Aaron Griffin Date: Fri, 19 Jan 2007 09:28:44 +0000 Subject: Preliminary checkin for alpm_list conversion * renamed pmlist_t -> alpm_list_t * made alpm_list_t a public type (alpm_list.h header) * removed additional storage for registered DBs in pacman source * some code cleanup * removed duplicate (pm)list_display functions from pacman source * misc code cleanup --- lib/libalpm/list.c | 361 ----------------------------------------------------- 1 file changed, 361 deletions(-) delete mode 100644 lib/libalpm/list.c (limited to 'lib/libalpm/list.c') diff --git a/lib/libalpm/list.c b/lib/libalpm/list.c deleted file mode 100644 index b6797073..00000000 --- a/lib/libalpm/list.c +++ /dev/null @@ -1,361 +0,0 @@ -/* - * list.c - * - * Copyright (c) 2002-2006 by Judd Vinet - * - * 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 -#include -#include -/* pacman */ -#include "list.h" -#include "util.h" - -pmlist_t *_alpm_list_new() -{ - pmlist_t *list = NULL; - - list = (pmlist_t *)malloc(sizeof(pmlist_t)); - if(list == NULL) { - return(NULL); - } - list->data = NULL; - list->prev = NULL; - list->next = NULL; - list->last = list; - return(list); -} - -void _alpm_list_free(pmlist_t *list, _alpm_fn_free fn) -{ - pmlist_t *ptr, *it = list; - - while(it) { - ptr = it->next; - if(fn && it->data) { - fn(it->data); - } - FREE(it); - it = ptr; - } -} - -pmlist_t *_alpm_list_add(pmlist_t *list, void *data) -{ - pmlist_t *ptr, *lp; - - ptr = list; - if(ptr == NULL) { - ptr = _alpm_list_new(); - if(ptr == NULL) { - return(NULL); - } - } - - lp = _alpm_list_last(ptr); - if(lp == ptr && lp->data == NULL) { - /* nada */ - } else { - lp->next = _alpm_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_t *_alpm_list_add_sorted(pmlist_t *list, void *data, _alpm_fn_cmp fn) -{ - pmlist_t *add; - pmlist_t *prev = NULL; - pmlist_t *iter = list; - - add = _alpm_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); -} - -/* return nth element from list (starting with 0) */ -pmlist_t* _alpm_list_nth(pmlist_t *list, int n) { - while (n--) - list = list->next; - return list; -} - -/* merge the two sorted sublists into one sorted list */ -pmlist_t* _alpm_list_mmerge(pmlist_t *left, pmlist_t *right, _alpm_fn_cmp fn) { - pmlist_t *newlist; - pmlist_t *lp; - - if (left == NULL) - return right; - if (right == NULL) - return left; - - if (fn(left->data, right->data) <= 0) { - newlist = left; - left = left->next; - } - else { - newlist = right; - right = right->next; - } - newlist->prev = NULL; - newlist->next = NULL; - newlist->last = NULL; - lp = newlist; - - while ((left != NULL) && (right != NULL)) { - if (fn(left->data, right->data) <= 0) { - lp->next = left; - left->prev = lp; - left = left->next; - } - else { - lp->next = right; - right->prev = lp; - right = right->next; - } - lp = lp->next; - lp->next = NULL; - newlist->last = lp; - } - if (left != NULL) { - lp->next = left; - left->prev = lp; - newlist->last = left->last; - } - else if (right != NULL) { - lp->next = right; - right->prev = lp; - newlist->last = right->last; - } - return newlist; -} - -/* sort an list of size n using mergesort algorithm */ -pmlist_t* _alpm_list_msort(pmlist_t *list, int len, _alpm_fn_cmp fn) { - if (len > 1 ) { - pmlist_t *left = list; - pmlist_t *lastleft = _alpm_list_nth(list, len/2 - 1); - pmlist_t *right = lastleft->next; - /* update rights last element, to previous last element*/ - right->last = left->last; - /* update lefts last element */ - left->last = lastleft; - /* terminate first list */ - lastleft->next = NULL; - - left = _alpm_list_msort(left, len/2, fn); - right = _alpm_list_msort(right, len - (len/2), fn); - list = _alpm_list_mmerge(left, right, fn); - } - 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_t *_alpm_list_remove(pmlist_t *haystack, void *needle, _alpm_fn_cmp fn, void **data) -{ - pmlist_t *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 _alpm_list_count(const pmlist_t *list) -{ - int i; - const pmlist_t *lp; - - for(lp = list, i = 0; lp; lp = lp->next, i++); - - return(i); -} - -int _alpm_list_is_in(void *needle, pmlist_t *haystack) -{ - pmlist_t *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_t -*/ -int _alpm_list_is_strin(char *needle, pmlist_t *haystack) -{ - pmlist_t *lp; - - for(lp = haystack; lp; lp = lp->next) { - if(lp->data && !strcmp(lp->data, needle)) { - return(1); - } - } - return(0); -} - -pmlist_t *_alpm_list_last(pmlist_t *list) -{ - if(list == NULL) { - return(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_t *_alpm_list_remove_dupes(pmlist_t *list) -{ - pmlist_t *i, *newlist = NULL; - - for(i = list; i; i = i->next) { - if(!_alpm_list_is_strin(i->data, newlist)) { - newlist = _alpm_list_add(newlist, strdup(i->data)); - } - } - return newlist; -} - -/* Reverse the order of a list - * - * The caller is responsible for freeing the old list - */ -pmlist_t *_alpm_list_reverse(pmlist_t *list) -{ - /* simple but functional -- we just build a new list, starting - * with the old list's tail - */ - pmlist_t *newlist = NULL; - pmlist_t *lp; - - for(lp = list->last; lp; lp = lp->prev) { - newlist = _alpm_list_add(newlist, lp->data); - } - - return(newlist); -} - -pmlist_t *_alpm_list_strdup(pmlist_t *list) -{ - pmlist_t *newlist = NULL; - pmlist_t *lp; - - for(lp = list; lp; lp = lp->next) { - newlist = _alpm_list_add(newlist, strdup(lp->data)); - } - - return(newlist); -} - -/* vim: set ts=2 sw=2 noet: */ -- cgit v1.2.3