Send patches - preferably formatted by git format-patch - to patches at archlinux32 dot org.
summaryrefslogtreecommitdiff
path: root/lib/libalpm/alpm_list.c
diff options
context:
space:
mode:
Diffstat (limited to 'lib/libalpm/alpm_list.c')
-rw-r--r--lib/libalpm/alpm_list.c498
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) {