[pacman-dev] mmerge with dupe removal

30 Mar 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;
}