path: root/lib/libalpm/alpm_list.c

/*
 *  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
 *  (at your option) any later version.
 *
 *  This program is distributed in the hope that it will be useful,
 *  but WITHOUT ANY WARRANTY; without even the implied warranty of
 *  MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
 *  GNU General Public License for more details.
 *
 *  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, 
 *  USA.
 */

#include "config.h"
#include <stdlib.h>
#include <string.h>
#include <stdio.h>
#include <assert.h>

#include "alpm_list.h"
#include "util.h"

/** \defgroup alpm_list functions */
/*\@{*/

/* Allocation */

/** 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 *list = NULL;

  list = (alpm_list_t *)malloc(sizeof(alpm_list_t));
  if(list) {
    list->data = NULL;
    list->prev = NULL;
    list->next = NULL;
  }
  return(list);
}

/** Free a list, but not the contained data
 *  @param list the list to free
 */
void SYMEXPORT alpm_list_free(alpm_list_t *list)
{
  alpm_list_t *it = list;

  while(it) {
    alpm_list_t *tmp = it->next;
    free(it);
    it = tmp;
  }
}

/** 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)
{
  alpm_list_t *it = list;

  while(it) {
    if(fn && it->data) {
      fn(it->data);
    }
    it = it->next;
  }
}


/* 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
 */
alpm_list_t SYMEXPORT *alpm_list_add(alpm_list_t *list, void *data)
{
  alpm_list_t *ptr, *lp;

  ptr = list;
  if(ptr == NULL) {
    ptr = alpm_list_new();
    if(ptr == NULL) {
      return(NULL);
    }
  }

  lp = alpm_list_last(ptr);
  if(lp == ptr && lp->data == NULL) {
    /* nada */
  } else {
    lp->next = alpm_list_new();
    if(lp->next == NULL) {
      return(NULL);
    }
    lp->next->prev = lp;
    lp = lp->next;
  }

  lp->data = 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
 */
alpm_list_t *alpm_list_add_sorted(alpm_list_t *list, void *data, alpm_list_fn_cmp fn)
{
  if(!fn) {
    return alpm_list_add(list, data);
  } else {
    alpm_list_t *add = NULL, *prev = NULL, *next = list;

    add = alpm_list_new();
    add->data = data;

    /* Find insertion point. */
    while(next) {
      if(fn(add->data, next->data) <= 0) break;
      prev = next;
      next = next->next;
    }

    /*  Insert node before insertion point. */
    add->prev = prev;
    add->next = next;

    if(next != NULL) {
      next->prev = add;   /*  Not at end.  */
    }

    if(prev != NULL) {
      prev->next = add;       /*  In middle.  */
    } else {
      list = add; /* At beginning, or new list */
    }
    
    return(list);
  }
}

/** 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
 */
alpm_list_t *alpm_list_mmerge(alpm_list_t *left, alpm_list_t *right, alpm_list_fn_cmp fn)
{
  alpm_list_t *newlist, *lp;

  if (left == NULL) 
    return right;
  if (right == NULL)
    return left;

  if (fn(left->data, right->data) <= 0) {
    newlist = left;
    left = left->next;
  }
  else {
    newlist = right;
    right = right->next;
  }
  newlist->prev = NULL;
  newlist->next = NULL;
  lp = newlist;

  while ((left != NULL) && (right != NULL)) {
    if (fn(left->data, right->data) <= 0) {
      lp->next = left;
      left->prev = lp;
      left = left->next;
    } 
    else {
      lp->next = right;
      right->prev = lp;
      right = right->next;
    }
    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;
  }
  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
 */
alpm_list_t* 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;  

    left = alpm_list_msort(left, n/2, fn);
    right = alpm_list_msort(right, n - (n/2), fn);
    list = alpm_list_mmerge(left, right, 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
 */
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 *i = haystack, *tmp = NULL;

  if(data) {
    *data = NULL;
  }

  while(i) {
    if(i->data == NULL) {
      continue;
    }
    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;
      }

      if(data) {
        *data = i->data;
      }
      i->data = NULL;
      free(i);
    }
    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
 */
alpm_list_t *alpm_list_remove_node(alpm_list_t *node)
{
  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;
  }

  return(ret);
}

/** 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
 */
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;
  while(lp) {
    if(!alpm_list_find(newlist, lp->data)) {
      newlist = alpm_list_add(newlist, 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
 */
alpm_list_t *alpm_list_strdup(alpm_list_t *list)
{
  alpm_list_t *lp = list, *newlist = NULL;
  while(lp) {
    newlist = alpm_list_add(newlist, strdup(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
 */
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;

  lp = alpm_list_last(list);
  while(lp) {
    newlist = alpm_list_add(newlist, lp->data);
    lp = lp->prev;
  }
  return(newlist);
}

/* Accessors */

/** 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)
{
  return(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`
 */
alpm_list_t *alpm_list_nth(alpm_list_t *list, int n)
{
  alpm_list_t *i = list;
  while(n--) {
    i = i->next;
  }
  return(i);
}

/** Get the next element of a list.
 * @param entry the list entry
 * @return the next element, or NULL when no more elements exist
 */
alpm_list_t SYMEXPORT *alpm_list_next(alpm_list_t *entry)
{
  return(entry->next);
}
/** Get the last item in the list.
 *  @param list the list to operate on
 *  @return the last element in the list
 */
alpm_list_t *alpm_list_last(alpm_list_t *list)
{
  alpm_list_t *i = list;
  while(i && i->next) {
    i = i->next;
  }
  return(i);
}

/** Get the data member of a list entry.
 * @param entry the list entry
 * @return the contained data, or NULL if none
 */
void SYMEXPORT *alpm_list_getdata(const alpm_list_t *entry)
{
  if(entry == NULL) return(NULL);
  return(entry->data);
}

/* Misc */

/** Count the list items
 *  @param list the list to operate on
 *  @return the number of list items
 */
int SYMEXPORT alpm_list_count(const alpm_list_t *list)
{
  unsigned int i = 0;
  const alpm_list_t *lp = list;
  while(lp) {
    ++i;
    lp = lp->next;
  }
  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
 */
int alpm_list_find(alpm_list_t *haystack, const void *needle)
{
  alpm_list_t *lp = haystack;
  while(lp) {
    if(lp->data == needle) {
      return(1);
    }
    lp = lp->next;
  }
  return(0);
}

/* 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
 */
int alpm_list_find_str(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);
}

/** 
 * Calculate the items in list `lhs` that are not present in list `rhs`
 * @note Entries are not duplicated
 * @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
 */
alpm_list_t *alpm_list_diff(alpm_list_t *lhs, alpm_list_t *rhs, alpm_list_fn_cmp fn)
{
  alpm_list_t *i, *j, *ret = NULL;
  for(i = lhs; i; i = i->next) {
    int found = 0;
    for(j = rhs; j; j = j->next) {
      if(fn(i->data, j->data) == 0) {
        found = 1;
        break;
      }
    }
    if(!found) {
      ret = alpm_list_add(ret, i->data);
    }
  }

  return(ret);
}

/** @} */

/* vim: set ts=2 sw=2 noet: */