diff options
Diffstat (limited to 'lib/libalpm/alpm_list.c')
| -rw-r--r-- | lib/libalpm/alpm_list.c | 498 |
1 files changed, 338 insertions, 160 deletions
diff --git a/lib/libalpm/alpm_list.c b/lib/libalpm/alpm_list.c index 54027455..a1e8861b 100644 --- a/lib/libalpm/alpm_list.c +++ b/lib/libalpm/alpm_list.c @@ -1,8 +1,8 @@ /* * 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 @@ -15,7 +15,7 @@ * * 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, + * Foundation, Inc., 59 Temple Place - Suite 330, Boston, MA 02111-1307, * USA. */ @@ -29,29 +29,41 @@ #include "alpm_list.h" #include "util.h" -/** \defgroup alpm_list functions */ -/*\@{*/ +/** + * @addtogroup alpm_list List Functions + * @brief Functions to manipulate alpm_list_t lists. + * + * These functions are designed to create, destroy, and modify lists of + * type alpm_list_t. This is an internal list type used by libalpm that is + * publicly exposed for use by frontends if desired. + * + * @{ */ /* Allocation */ -/** Allocate a new alpm_list_t - * @return a new alpm_list_t item, or NULL on failure +/** + * @brief 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 SYMEXPORT *alpm_list_new() { alpm_list_t *list = NULL; - list = (alpm_list_t *)malloc(sizeof(alpm_list_t)); + list = malloc(sizeof(alpm_list_t)); if(list) { list->data = NULL; - list->prev = NULL; + list->prev = list; /* maintain a back reference to the tail pointer */ list->next = NULL; } + return(list); } -/** Free a list, but not the contained data - * @param list the list to free +/** + * @brief Free a list, but not the contained data. + * + * @param list the list to free */ void SYMEXPORT alpm_list_free(alpm_list_t *list) { @@ -64,9 +76,11 @@ void SYMEXPORT alpm_list_free(alpm_list_t *list) } } -/** Free the internal data of a list structure - * @param list the list to free - * @param fn a free function for the internal data +/** + * @brief 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) { @@ -83,10 +97,13 @@ void SYMEXPORT alpm_list_free_inner(alpm_list_t *list, alpm_list_fn_free fn) /* 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 +/** + * @brief Add a new item to the end of the list. + * + * @param list the list to add to + * @param data the new item to be added to the list + * + * @return the resultant list */ alpm_list_t SYMEXPORT *alpm_list_add(alpm_list_t *list, void *data) { @@ -110,6 +127,7 @@ alpm_list_t SYMEXPORT *alpm_list_add(alpm_list_t *list, void *data) } lp->next->prev = lp; lp = lp->next; + list->prev = lp; } lp->data = data; @@ -117,13 +135,16 @@ alpm_list_t SYMEXPORT *alpm_list_add(alpm_list_t *list, void *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 +/** + * @brief 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 */ -alpm_list_t *alpm_list_add_sorted(alpm_list_t *list, void *data, alpm_list_fn_cmp fn) +alpm_list_t SYMEXPORT *alpm_list_add_sorted(alpm_list_t *list, void *data, alpm_list_fn_cmp fn) { if(!fn) { return alpm_list_add(list, data); @@ -153,21 +174,63 @@ alpm_list_t *alpm_list_add_sorted(alpm_list_t *list, void *data, alpm_list_fn_cm } else { list = add; /* At beginning, or new list */ } - + + if(next == NULL) { + /* At end, adjust tail pointer on head node */ + list->prev = add; + } + return(list); } } -/** Merge the two sorted sublists into one sorted list - * @param left the first list +/** + * @brief Join two lists. + * The two lists must be independent. Do not free the original lists after + * calling this function, as this is not a copy operation. The list pointers + * passed in should be considered invalid after calling this function. + * + * @param first the first list + * @param second the second list + * + * @return the resultant joined list + */ +alpm_list_t SYMEXPORT *alpm_list_join(alpm_list_t *first, alpm_list_t *second) +{ + alpm_list_t *tmp; + + if (first == NULL) { + return second; + } + if (second == NULL) { + return first; + } + /* tmp is the last element of the first list */ + tmp = first->prev; + /* link the first list to the second */ + tmp->next = second; + /* link the second list to the first */ + first->prev = second->prev; + /* set the back reference to the tail */ + second->prev = tmp; + + return(first); +} + +/** + * @brief 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 + * @param fn comparison function for determining merge order + * + * @return the resultant list */ -alpm_list_t *alpm_list_mmerge(alpm_list_t *left, alpm_list_t *right, alpm_list_fn_cmp fn) +alpm_list_t SYMEXPORT *alpm_list_mmerge(alpm_list_t *left, alpm_list_t *right, alpm_list_fn_cmp fn) { alpm_list_t *newlist, *lp; - if (left == NULL) + if (left == NULL) return right; if (right == NULL) return left; @@ -189,7 +252,7 @@ alpm_list_t *alpm_list_mmerge(alpm_list_t *left, alpm_list_t *right, alpm_list_f lp->next = left; left->prev = lp; left = left->next; - } + } else { lp->next = right; right->prev = lp; @@ -206,22 +269,35 @@ alpm_list_t *alpm_list_mmerge(alpm_list_t *left, alpm_list_t *right, alpm_list_f lp->next = right; right->prev = lp; } + + /* Find our tail pointer + * TODO maintain this in the algorithm itself */ + lp = newlist; + while(lp && lp->next) { + lp = lp->next; + } + newlist->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 +/** + * @brief 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 + * + * @return the resultant list */ -alpm_list_t* alpm_list_msort(alpm_list_t *list, int n, alpm_list_fn_cmp fn) +alpm_list_t SYMEXPORT *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; + lastleft->next = NULL; left = alpm_list_msort(left, n/2, fn); right = alpm_list_msort(right, n - (n/2), fn); @@ -230,15 +306,18 @@ alpm_list_t* alpm_list_msort(alpm_list_t *list, int n, alpm_list_fn_cmp 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 +/** + * @brief 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 data of the removed item + * + * @return the resultant list */ -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 SYMEXPORT *alpm_list_remove(alpm_list_t *haystack, const void *needle, alpm_list_fn_cmp fn, void **data) +{ alpm_list_t *i = haystack, *tmp = NULL; if(data) { @@ -252,16 +331,31 @@ alpm_list_t *alpm_list_remove(alpm_list_t *haystack, const void *needle, alpm_li 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; + /* Special case: removing the head node which has a back reference to + * the tail node */ + haystack = i->next; + if(haystack) { + haystack->prev = i->prev; + } + i->prev = NULL; + } else if(i == haystack->prev) { + /* Special case: removing the tail node, so we need to fix the back + * reference on the head node. We also know tail != head. */ + if(i->prev) { + /* i->next should always be null */ + i->prev->next = i->next; + haystack->prev = i->prev; + i->prev = NULL; + } + } else { + /* Normal case, non-head and non-tail node */ + if(i->next) { + i->next->prev = i->prev; + } + if(i->prev) { + i->prev->next = i->next; + } } if(data) { @@ -269,79 +363,117 @@ alpm_list_t *alpm_list_remove(alpm_list_t *haystack, const void *needle, alpm_li } i->data = NULL; free(i); + i = NULL; + } else { + i = tmp; } - 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 +/** + * @brief Create a new list without any duplicates. + * + * This does NOT copy data members. + * + * @param list the list to copy + * + * @return a new list containing non-duplicate items */ -alpm_list_t *alpm_list_remove_node(alpm_list_t *node) +alpm_list_t SYMEXPORT *alpm_list_remove_dupes(const alpm_list_t *list) { - 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; + const alpm_list_t *lp = list; + alpm_list_t *newlist = NULL; + while(lp) { + if(!alpm_list_find_ptr(newlist, lp->data)) { + newlist = alpm_list_add(newlist, lp->data); + } + lp = lp->next; } - - return(ret); + return(newlist); } -/** 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 +/** + * @brief Copy a string list, including data. + * + * @param list the list to copy + * + * @return a copy of the original list */ -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; +alpm_list_t SYMEXPORT *alpm_list_strdup(const alpm_list_t *list) +{ + const alpm_list_t *lp = list; + alpm_list_t *newlist = NULL; while(lp) { - if(!alpm_list_find(newlist, lp->data)) { - newlist = alpm_list_add(newlist, lp->data); - } + newlist = alpm_list_add(newlist, strdup(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 +/** + * @brief Copy a list, without copying data. + * + * @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 SYMEXPORT *alpm_list_copy(const alpm_list_t *list) { - alpm_list_t *lp = list, *newlist = NULL; + const alpm_list_t *lp = list; + alpm_list_t *newlist = NULL; while(lp) { - newlist = alpm_list_add(newlist, strdup(lp->data)); + newlist = alpm_list_add(newlist, 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 +/** + * @brief Copy a list and copy the data. + * Note that the data elements to be copied should not contain pointers + * and should also be of constant size. + * + * @param list the list to copy + * @param size the size of each data element + * + * @return a copy of the original list, data copied as well */ -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; +alpm_list_t SYMEXPORT *alpm_list_copy_data(const alpm_list_t *list, + size_t size) +{ + const alpm_list_t *lp = list; + alpm_list_t *newlist = NULL; + while(lp) { + void *newdata = calloc(1, size); + if(newdata) { + memcpy(newdata, lp->data, size); + newlist = alpm_list_add(newlist, newdata); + lp = lp->next; + } + } + return(newlist); +} + +/** + * @brief Create a new list in reverse order. + * + * @param list the list to copy + * + * @return a new list in reverse order + */ +alpm_list_t SYMEXPORT *alpm_list_reverse(alpm_list_t *list) +{ + const alpm_list_t *lp; + alpm_list_t *newlist = NULL; lp = alpm_list_last(list); + if(list) { + /* break our reverse circular list */ + list->prev = NULL; + } + while(lp) { newlist = alpm_list_add(newlist, lp->data); lp = lp->prev; @@ -351,65 +483,84 @@ alpm_list_t *alpm_list_reverse(alpm_list_t *list) /* Accessors */ -/** Get the first element of a list. +/** + * @brief 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) +inline alpm_list_t SYMEXPORT *alpm_list_first(const alpm_list_t *list) { - return(list); + return((alpm_list_t*)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` +/** + * @brief Return nth element from list (starting from 0). + * + * @param list the list + * @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 SYMEXPORT *alpm_list_nth(const alpm_list_t *list, int n) { - alpm_list_t *i = list; + const alpm_list_t *i = list; while(n--) { i = i->next; } - return(i); + return((alpm_list_t*)i); } -/** Get the next element of a list. - * @param entry the list entry +/** + * @brief Get the next element of a list. + * + * @param node the list node + * * @return the next element, or NULL when no more elements exist */ -alpm_list_t SYMEXPORT *alpm_list_next(alpm_list_t *entry) +inline alpm_list_t SYMEXPORT *alpm_list_next(const alpm_list_t *node) { - return(entry->next); + return(node->next); } -/** Get the last item in the list. - * @param list the list to operate on - * @return the last element in the list + +/** + * @brief Get the last item in the list. + * + * @param list the list + * + * @return the last element in the list */ -alpm_list_t *alpm_list_last(alpm_list_t *list) +alpm_list_t SYMEXPORT *alpm_list_last(const alpm_list_t *list) { - alpm_list_t *i = list; - while(i && i->next) { - i = i->next; + if(list) { + return(list->prev); + } else { + return(NULL); } - return(i); } -/** Get the data member of a list entry. - * @param entry the list entry +/** + * @brief Get the data member of a list node. + * + * @param node the list node + * * @return the contained data, or NULL if none */ -void SYMEXPORT *alpm_list_getdata(const alpm_list_t *entry) +void SYMEXPORT *alpm_list_getdata(const alpm_list_t *node) { - if(entry == NULL) return(NULL); - return(entry->data); + if(node == NULL) return(NULL); + return(node->data); } /* Misc */ -/** Count the list items - * @param list the list to operate on - * @return the number of list items +/** + * @brief Get the number of items in a list. + * + * @param list the list + * + * @return the number of list items */ int SYMEXPORT alpm_list_count(const alpm_list_t *list) { @@ -422,53 +573,80 @@ int SYMEXPORT alpm_list_count(const alpm_list_t *list) 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 +/** + * @brief Find an item in a list. + * + * @param needle the item to search + * @param haystack the list + * @param fn the comparison function for searching (!= NULL) + * + * @return `needle` if found, NULL otherwise */ -int SYMEXPORT alpm_list_find(alpm_list_t *haystack, const void *needle) +void SYMEXPORT *alpm_list_find(const alpm_list_t *haystack, const void *needle, + alpm_list_fn_cmp fn) { - alpm_list_t *lp = haystack; + const alpm_list_t *lp = haystack; while(lp) { - if(lp->data == needle) { - return(1); + if(lp->data && fn(lp->data, needle) == 0) { + return(lp->data); } lp = lp->next; } - return(0); + return(NULL); +} + +/* trivial helper function for alpm_list_find_ptr */ +static int ptrcmp(const void *p, const void *q) +{ + return(p != q); +} + +/** + * @brief Find an item in a list. + * + * Search for the item whos data matches that of the `needle`. + * + * @param needle the data to search for (== comparison) + * @param haystack the list + * + * @return `needle` if found, NULL otherwise + */ +void SYMEXPORT *alpm_list_find_ptr(const alpm_list_t *haystack, const void *needle) +{ + return(alpm_list_find(haystack, needle, ptrcmp)); } -/* 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 +/** + * @brief Find a string in a list. + * + * @param needle the string to search for + * @param haystack the list + * + * @return `needle` if found, NULL otherwise */ -int SYMEXPORT alpm_list_find_str(alpm_list_t *haystack, const char *needle) +char SYMEXPORT *alpm_list_find_str(const 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); + return((char *)alpm_list_find(haystack, (const void*)needle, (alpm_list_fn_cmp)strcmp)); } -/** - * Calculate the items in list `lhs` that are not present in list `rhs` - * @note Entries are not duplicated +/** + * @brief Find the items in list `lhs` that are not present in list `rhs`. + * + * Entries are not duplicated. Operation is O(m*n). The first list is stepped + * through one node at a time, and for each node in the first list, each node + * in the second list is compared to it. + * * @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 + * @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 SYMEXPORT *alpm_list_diff(const alpm_list_t *lhs, + const alpm_list_t *rhs, alpm_list_fn_cmp fn) { - alpm_list_t *i, *j, *ret = NULL; + const alpm_list_t *i, *j; + alpm_list_t *ret = NULL; for(i = lhs; i; i = i->next) { int found = 0; for(j = rhs; j; j = j->next) { |