path: root/lib/libalpm/alpm_list.c

/*
 *  alpm_list.c
 *
 *  Copyright (c) 2006-2017 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>

/* Note: alpm_list.{c,h} are intended to be standalone files. Do not include
 * any other libalpm headers.
 */

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

        if(fn) {
                while(it) {
                        if(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_append(&list, data);
        return list;
}

/**
 * @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 newly added item
 */
alpm_list_t SYMEXPORT *alpm_list_append(alpm_list_t **list, void *data)
{
        alpm_list_t *ptr;

        ptr = malloc(sizeof(alpm_list_t));
        if(ptr == NULL) {
                return NULL;
        }

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

        /* Special case: the input list is empty */
        if(*list == NULL) {
                *list = ptr;
                ptr->prev = ptr;
        } else {
                alpm_list_t *lp = alpm_list_last(*list);
                lp->next = ptr;
                ptr->prev = lp;
                (*list)->prev = ptr;
        }

        return ptr;
}

/**
 * @brief Duplicate and append a string to a list.
 *
 * @param list the list to append to
 * @param data the string to duplicate and append
 *
 * @return the newly added item
 */
alpm_list_t SYMEXPORT *alpm_list_append_strdup(alpm_list_t **list, const char *data)
{
        alpm_list_t *ret;
        char *dup;
        if((dup = strdup(data)) && (ret = alpm_list_append(list, dup))) {
                return ret;
        } else {
                free(dup);
                return NULL;
        }
}

/**
 * @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 = malloc(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;

        return first;
}

/**
 * @brief 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
 *
 * @return the resultant list
 */
alpm_list_t SYMEXPORT *alpm_list_mmerge(alpm_list_t *left, alpm_list_t *right,
                alpm_list_fn_cmp fn)
{
        alpm_list_t *newlist, *lp, *tail_ptr, *left_tail_ptr, *right_tail_ptr;

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

        /* Save tail node pointers for future use */
        left_tail_ptr = left->prev;
        right_tail_ptr = right->prev;

        if(fn(left->data, right->data) <= 0) {
                newlist = left;
                left = left->next;