/* * alpm_list.c * * Copyright (c) 2002-2006 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> #include "alpm_list.h" #include "util.h" /** \defgroup alpm_list functions */ /*\@{*/ /* Allocation */ /** Allocate a new alpm_list_t * @return a new alpm_list_t item, or NULL on failure */ alpm_list_t *alpm_list_new() { alpm_list_t *list = NULL; list = (alpm_list_t *)malloc(sizeof(alpm_list_t)); if(list) { list->data = NULL; list->prev = NULL; list->next = NULL; } return(list); } /** Free a list, but not the contained data * @param list the list to free */ void SYMEXPORT alpm_list_free(alpm_list_t *list) { alpm_list_t *it = list; while(it) { alpm_list_t *tmp = it->next; free(it); it = tmp; } } /** Free the internal data of a list structure * @param list the list to free * @param fn a free function for the internal data */ void SYMEXPORT alpm_list_free_inner(alpm_list_t *list, alpm_list_fn_free fn) { alpm_list_t *it = list; while(it) { if(fn && it->data) { fn(it->data); } it = it->next; } } /* Mutators */ /** Add a new item to the list * @param list the list to add to * @param data the new item to be added to the list * @return the resultant list, or NULL on failure */ alpm_list_t SYMEXPORT *alpm_list_add(alpm_list_t *list, void *data) { alpm_list_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 = lp->next; } lp->data = data; return(ptr); } /** Add items to a list in sorted order. * @param list the list to add to * @param data the new item to be added to the list * @param fn the comparison function to use to determine order * @return the resultant list, or NULL on failure */ alpm_list_t *alpm_list_add_sorted(alpm_list_t *list, void *data, alpm_list_fn_cmp fn) { if(!fn) { return alpm_list_add(list, data); } else { alpm_list_t *add = NULL, *prev = NULL, *next = list; add = alpm_list_new(); add->data = data; /* Find insertion point. */ while(next) { if(fn(add->data, next->data) <= 0) break; prev = next; next = next->next; } /* Insert node before insertion point. */ add->prev = prev; add->next = next; if(next != NULL) { next->prev = add; /* Not at end. */ } if(prev != NULL) { prev->next = add; /* In middle. */ } else { list = add; /* At beginning, or new list */ } return(list); } } /** Merge the two sorted sublists into one sorted list * @param left the first list * @param right the second list * @param fn comparison function for determining merge order */ alpm_list_t *alpm_list_mmerge(alpm_list_t *left, alpm_list_t *right, alpm_list_fn_cmp fn) { alpm_list_t *newlist, *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; 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; } if (left != NULL) { lp->next = left; left->prev = lp; } else if (right != NULL) { lp->next = right; right->prev = lp; } return(newlist); } /** Sort a list of size `n` using mergesort algorithm * @param list the list to sort * @param n the size of the list * @param fn the comparison function for determining order */ alpm_list_t* alpm_list_msort(alpm_list_t *list, int n, alpm_list_fn_cmp fn) { if (n > 1) { alpm_list_t *left = list; alpm_list_t *lastleft = alpm_list_nth(list, n/2 - 1); alpm_list_t *right = lastleft->next; /* terminate first list */ lastleft->next = NULL; left = alpm_list_msort(left, n/2, fn); right = alpm_list_msort(right, n - (n/2), fn); list = alpm_list_mmerge(left, right, fn); } return(list); } /** Remove an item from the list * @param haystack the list to remove the item from * @param needle the data member of the item we're removing * @param fn the comparison function for searching * @param data output parameter containing the data member of the item removed * @return the resultant list, or NULL on failure */ alpm_list_t *alpm_list_remove(alpm_list_t *haystack, const void *needle, alpm_list_fn_cmp fn, void **data) { /* TODO I modified this to remove ALL matching items. Do we need a remove_first? */ alpm_list_t *i = haystack, *tmp = NULL; if(data) { *data = NULL; } while(i) { if(i->data == NULL) { continue; } tmp = i->next; if(fn(needle, i->data) == 0) { /* 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 */ haystack = haystack->next; } if(data) { *data = i->data; } i->data = NULL; free(i); } i = tmp; } return(haystack); } /** Remove the passed in node from the list that it is a part of * @note this DOES NOT free the node * @param node the list node we're removing * @return the node which took the place of this one */ alpm_list_t *alpm_list_remove_node(alpm_list_t *node) { if(!node) return(NULL); alpm_list_t *ret = NULL; if(node->prev) { node->prev->next = node->next; ret = node->prev; node->prev = NULL; } if(node->next) { node->next->prev = node->prev; ret = node->next; node->next = NULL; } return(ret); } /** Create a new list without any duplicates * @note DOES NOT copy data members * @param list the list to copy * @return a NEW list containing non-duplicated items */ alpm_list_t SYMEXPORT *alpm_list_remove_dupes(alpm_list_t *list) { /* TODO does removing the strdup here cause invalid free's anywhere? */ alpm_list_t *lp = list, *newlist = NULL; while(lp) { if(!alpm_list_find(newlist, lp->data)) { newlist = alpm_list_add(newlist, lp->data); } lp = lp->next; } return(newlist); } /** Copy a string list, including data * @note this is gross, assumes string data members * @param list the list to copy * @return a copy of the original list */ alpm_list_t *alpm_list_strdup(alpm_list_t *list) { alpm_list_t *lp = list, *newlist = NULL; while(lp) { newlist = alpm_list_add(newlist, strdup(lp->data)); lp = lp->next; } return(newlist); } /** Create a new list in reverse order * @param list the list to copy * @return a NEW list in reverse order of the first */ alpm_list_t *alpm_list_reverse(alpm_list_t *list) { /* TODO any invalid free's from NOT duplicating data here? */ alpm_list_t *lp, *newlist = NULL; lp = alpm_list_last(list); while(lp) { newlist = alpm_list_add(newlist, lp->data); lp = lp->prev; } return(newlist); } /* Accessors */ /** Get the first element of a list. * @param list the list * @return the first element in the list */ alpm_list_t SYMEXPORT *alpm_list_first(alpm_list_t *list) { return(list); } /** Return nth element from list (starting with 0) * @param list the list to access * @param n the index of the item to find * @return an alpm_list_t node for index `n` */ alpm_list_t *alpm_list_nth(alpm_list_t *list, int n) { alpm_list_t *i = list; while(n--) { i = i->next; } return(i); } /** Get the next element of a list. * @param entry the list entry * @return the next element, or NULL when no more elements exist */ alpm_list_t SYMEXPORT *alpm_list_next(alpm_list_t *entry) { return(entry->next); } /** Get the last item in the list. * @param list the list to operate on * @return the last element in the list */ alpm_list_t *alpm_list_last(alpm_list_t *list) { alpm_list_t *i = list; while(i && i->next) { i = i->next; } return(i); } /** Get the data member of a list entry. * @param entry the list entry * @return the contained data, or NULL if none */ void SYMEXPORT *alpm_list_getdata(const alpm_list_t *entry) { if(entry == NULL) return(NULL); return(entry->data); } /* Misc */ /** Count the list items * @param list the list to operate on * @return the number of list items */ int SYMEXPORT alpm_list_count(const alpm_list_t *list) { unsigned int i = 0; const alpm_list_t *lp = list; while(lp) { ++i; lp = lp->next; } return(i); } /** Is an item in the list * @param needle the data to compare to (== comparison) * @param haystack the list to search * @return 1 if `needle` is found, 0 otherwise */ int alpm_list_find(alpm_list_t *haystack, const void *needle) { alpm_list_t *lp = haystack; while(lp) { if(lp->data == needle) { return(1); } lp = lp->next; } return(0); } /* Test for existence of a string in a alpm_list_t */ /** Is a _string_ in the list (optimization of alpm_list_find for strings) * @param needle the string to compare * @param haystack the list to search * @return 1 if `needle` is found, 0 otherwise */ int alpm_list_find_str(alpm_list_t *haystack, const char *needle) { alpm_list_t *lp = haystack; while(lp) { if(lp->data && strcmp((const char *)lp->data, needle) == 0) { return(1); } lp = lp->next; } return(0); } /** * Calculate the items in list `lhs` that are not present in list `rhs` * @note Entries are not duplicated * @param lhs the first list * @param rhs the second list * @param fn the comparison function * @return a list containing all items in lhs not present in rhs */ alpm_list_t *alpm_list_diff(alpm_list_t *lhs, alpm_list_t *rhs, alpm_list_fn_cmp fn) { alpm_list_t *i, *j, *ret = NULL; for(i = lhs; i; i = i->next) { int found = 0; for(j = rhs; j; j = j->next) { if(fn(i->data, j->data) == 0) { found = 1; break; } } if(!found) { ret = alpm_list_add(ret, i->data); } } return(ret); } /** @} */ /* vim: set ts=2 sw=2 noet: */