path: root/lib/libalpm/alpm_list.c

/*
 *  alpm_list.c
 *
 *  Copyright (c) 2006-2011 Pacman Development Team <pacman-dev@archlinux.org>
 *  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, see <http://www.gnu.org/licenses/>.
 */

#include <stdlib.h>
#include <string.h>

/* libalpm */
#include "alpm_list.h"

/* check exported library symbols with: nm -C -D <lib> */
#define SYMEXPORT __attribute__((visibility("default")))
#define SYMHIDDEN __attribute__((visibility("internal")))

/**
 * @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 */

/**
 * @brief 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;
  }
}

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

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


/* Mutators */

/**
 * @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)
{
  alpm_list_t *ptr, *lp;

  ptr = calloc(1, sizeof(alpm_list_t));
  if(ptr == NULL) {
    return list;
  }

  ptr->data = data;
  ptr->next = NULL;

  /* Special case: the input list is empty */
  if(list == NULL) {
    ptr->prev = ptr;
    return ptr;
  }

  lp = alpm_list_last(list);
  lp->next = ptr;
  ptr->prev = lp;
  list->prev = ptr;

  return list;
}

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

    add = calloc(1, sizeof(alpm_list_t));
    if(add == NULL) {
      return list;
    }
    add->data = data;

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

    /* Insert the add node to the list */
    if(prev == NULL) { /* special case: we insert add as the first element */
      add->prev = list->prev; /* list != NULL */
      add->next = list;
      list->prev = add;
      return add;
    } else if(next == NULL) { /* another special case: add last element */
      add->prev = prev;
      add->next = NULL;
      prev->next = add;
      list->prev = add;
      return list;
    } else {
      add->prev = prev;
      add->next = next;
      next->prev = add;
      prev->next = add;
      return 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;