[pacman-dev] mmerge with dupe removal
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; }
participants (1)
-
dave reisner