[pacman-dev] mmerge with dupe removal
dave reisner
d at falconindy.com
Tue Mar 30 06:22:52 CEST 2010
Hey all. I've been working on a AUR agent in C, and I ended up modifying
some of the alpm_list methods for my own purposes. At toofishes' request,
I'm posting them here to see if anyone finds them useful.
The first finds and deletes duplicate entries during a mergesort. The latter
is implemented by the modified merge to remove a specific node in a list,
given that you already have a pointer to it.
As I noticed there was a recent discussion regarding something of this
nature, I hope it proves useful. It should be easily modifiable to allow for
populating a new duplicate list if you choose to go that route.
-dave reisner
/**
* @brief merge sort with duplicate deletion
*
* @param left left side of merge
* @param right right side of merge
* @param fn callback function for comparing data
* @param fnf callback function for deleting data
*
* @return the merged list
*/
alpm_list_t *alpm_list_mmerge_dedupe(alpm_list_t *left, alpm_list_t *right,
alpm_list_fn_cmp fn, alpm_list_fn_free fnf) {
alpm_list_t *lp, *newlist;
int compare;
if (left == NULL)
return right;
if (right == NULL)
return left;
do {
compare = fn(left->data, right->data);
if (compare > 0) {
newlist = right;
right = right->next;
}
else if (compare < 0) {
newlist = left;
left = left->next;
} else {
left = alpm_list_remove_item(left, left, fnf);
}
} while (compare == 0);
newlist->prev = NULL;
newlist->next = NULL;
lp = newlist;
while ((left != NULL) && (right != NULL)) {
compare = fn(left->data, right->data);
if (compare < 0) {
lp->next = left;
left->prev = lp;
left = left->next;
}
else if (compare > 0) {
lp->next = right;
right->prev = lp;
right = right->next;
} else {
left = alpm_list_remove_item(left, left, fnf);
continue;
}
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;
}
while(lp && lp->next) {
lp = lp->next;
}
newlist->prev = lp;
return(newlist);
}
/**
* @brief Remove a specific node from a list
*
* @param listhead list to remove from
* @param target node within list to remove
* @param fn comparison function
*
* @return the node following the removed node
*/
alpm_list_t *alpm_list_remove_item(alpm_list_t *listhead, alpm_list_t
*target, alpm_list_fn_free fn) {
alpm_list_t *next = NULL;
if (target == listhead) {
listhead = target->next;
if (listhead) {
listhead->prev = target->prev;
}
target->prev = NULL;
} else if (target == listhead->prev) {
if (target->prev) {
target->prev->next = target->next;
listhead->prev = target->prev;
target->prev = NULL;
}
} else {
if (target->next) {
target->next->prev = target->prev;
}
if (target->prev) {
target->prev->next = target->next;
}
}
next = target->next;
if (target->data) {
fn(target->data);
}
free(target);
return next;
}
More information about the pacman-dev
mailing list