Send patches - preferably formatted by git format-patch - to patches at archlinux32 dot org.
summaryrefslogtreecommitdiff
path: root/lib/libalpm/list.c
diff options
context:
space:
mode:
Diffstat (limited to 'lib/libalpm/list.c')
-rw-r--r--lib/libalpm/list.c361
1 files changed, 0 insertions, 361 deletions
diff --git a/lib/libalpm/list.c b/lib/libalpm/list.c
deleted file mode 100644
index b6797073..00000000
--- a/lib/libalpm/list.c
+++ /dev/null
@@ -1,361 +0,0 @@
-/*
- * 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>
-/* pacman */
-#include "list.h"
-#include "util.h"
-
-pmlist_t *_alpm_list_new()
-{
- pmlist_t *list = NULL;
-
- list = (pmlist_t *)malloc(sizeof(pmlist_t));
- if(list == NULL) {
- return(NULL);
- }
- list->data = NULL;
- list->prev = NULL;
- list->next = NULL;
- list->last = list;
- return(list);
-}
-
-void _alpm_list_free(pmlist_t *list, _alpm_fn_free fn)
-{
- pmlist_t *ptr, *it = list;
-
- while(it) {
- ptr = it->next;
- if(fn && it->data) {
- fn(it->data);
- }
- FREE(it);
- it = ptr;
- }
-}
-
-pmlist_t *_alpm_list_add(pmlist_t *list, void *data)
-{
- pmlist_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->last = NULL;
- lp = lp->next;
- }
-
- lp->data = data;
- ptr->last = lp;
-
- return(ptr);
-}
-
-/* Add items to a list in sorted order. Use the given comparision func to
- * determine order.
- */
-pmlist_t *_alpm_list_add_sorted(pmlist_t *list, void *data, _alpm_fn_cmp fn)
-{
- pmlist_t *add;
- pmlist_t *prev = NULL;
- pmlist_t *iter = list;
-
- add = _alpm_list_new();
- add->data = data;
-
- /* Find insertion point. */
- while(iter) {
- if(fn(add->data, iter->data) <= 0) break;
- prev = iter;
- iter = iter->next;
- }
-
- /* Insert node before insertion point. */
- add->prev = prev;
- add->next = iter;
-
- if(iter != NULL) {
- iter->prev = add; /* Not at end. */
- } else {
- if (list != NULL) {
- list->last = add; /* Added new to end, so update the link to last. */
- }
- }
-
- if(prev != NULL) {
- prev->next = add; /* In middle. */
- } else {
- if(list == NULL) {
- add->last = add;
- } else {
- add->last = list->last;
- list->last = NULL;
- }
- list = add; /* Start or empty, new list head. */
- }
-
- return(list);
-}
-
-/* return nth element from list (starting with 0) */
-pmlist_t* _alpm_list_nth(pmlist_t *list, int n) {
- while (n--)
- list = list->next;
- return list;
-}
-
-/* merge the two sorted sublists into one sorted list */
-pmlist_t* _alpm_list_mmerge(pmlist_t *left, pmlist_t *right, _alpm_fn_cmp fn) {
- pmlist_t *newlist;
- pmlist_t *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;
- newlist->last = 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;
- newlist->last = lp;
- }
- if (left != NULL) {
- lp->next = left;
- left->prev = lp;
- newlist->last = left->last;
- }
- else if (right != NULL) {
- lp->next = right;
- right->prev = lp;
- newlist->last = right->last;
- }
- return newlist;
-}
-
-/* sort an list of size n using mergesort algorithm */
-pmlist_t* _alpm_list_msort(pmlist_t *list, int len, _alpm_fn_cmp fn) {
- if (len > 1 ) {
- pmlist_t *left = list;
- pmlist_t *lastleft = _alpm_list_nth(list, len/2 - 1);
- pmlist_t *right = lastleft->next;
- /* update rights last element, to previous last element*/
- right->last = left->last;
- /* update lefts last element */
- left->last = lastleft;
- /* terminate first list */
- lastleft->next = NULL;
-
- left = _alpm_list_msort(left, len/2, fn);
- right = _alpm_list_msort(right, len - (len/2), fn);
- list = _alpm_list_mmerge(left, right, fn);
- }
- return list;
-}
-
-/* Remove an item in a list. Use the given comparaison function to find the
- * item.
- * If the item is found, 'data' is pointing to the removed element.
- * Otherwise, it is set to NULL.
- * Return the new list (without the removed element).
- */
-pmlist_t *_alpm_list_remove(pmlist_t *haystack, void *needle, _alpm_fn_cmp fn, void **data)
-{
- pmlist_t *i = haystack;
-
- if(data) {
- *data = NULL;
- }
-
- while(i) {
- if(i->data == NULL) {
- continue;
- }
- if(fn(needle, i->data) == 0) {
- break;
- }
- i = i->next;
- }
-
- if(i) {
- /* 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 */
- if(haystack->next) {
- haystack->next->last = haystack->last;
- }
- haystack = haystack->next;
- } else if(i == haystack->last) {
- /* The item found is the last in the chain */
- haystack->last = i->prev;
- }
-
- if(data) {
- *data = i->data;
- }
- i->data = NULL;
- FREE(i);
- }
-
- return(haystack);
-}
-
-int _alpm_list_count(const pmlist_t *list)
-{
- int i;
- const pmlist_t *lp;
-
- for(lp = list, i = 0; lp; lp = lp->next, i++);
-
- return(i);
-}
-
-int _alpm_list_is_in(void *needle, pmlist_t *haystack)
-{
- pmlist_t *lp;
-
- for(lp = haystack; lp; lp = lp->next) {
- if(lp->data == needle) {
- return(1);
- }
- }
- return(0);
-}
-
-/* Test for existence of a string in a pmlist_t
-*/
-int _alpm_list_is_strin(char *needle, pmlist_t *haystack)
-{
- pmlist_t *lp;
-
- for(lp = haystack; lp; lp = lp->next) {
- if(lp->data && !strcmp(lp->data, needle)) {
- return(1);
- }
- }
- return(0);
-}
-
-pmlist_t *_alpm_list_last(pmlist_t *list)
-{
- if(list == NULL) {
- return(NULL);
- }
-
- return(list->last);
-}
-
-/* Filter out any duplicate strings in a list.
- *
- * Not the most efficient way, but simple to implement -- we assemble
- * a new list, using is_in() to check for dupes at each iteration.
- *
- */
-pmlist_t *_alpm_list_remove_dupes(pmlist_t *list)
-{
- pmlist_t *i, *newlist = NULL;
-
- for(i = list; i; i = i->next) {
- if(!_alpm_list_is_strin(i->data, newlist)) {
- newlist = _alpm_list_add(newlist, strdup(i->data));
- }
- }
- return newlist;
-}
-
-/* Reverse the order of a list
- *
- * The caller is responsible for freeing the old list
- */
-pmlist_t *_alpm_list_reverse(pmlist_t *list)
-{
- /* simple but functional -- we just build a new list, starting
- * with the old list's tail
- */
- pmlist_t *newlist = NULL;
- pmlist_t *lp;
-
- for(lp = list->last; lp; lp = lp->prev) {
- newlist = _alpm_list_add(newlist, lp->data);
- }
-
- return(newlist);
-}
-
-pmlist_t *_alpm_list_strdup(pmlist_t *list)
-{
- pmlist_t *newlist = NULL;
- pmlist_t *lp;
-
- for(lp = list; lp; lp = lp->next) {
- newlist = _alpm_list_add(newlist, strdup(lp->data));
- }
-
- return(newlist);
-}
-
-/* vim: set ts=2 sw=2 noet: */

Copyright © 2002-2022 Judd Vinet and Aaron Griffin. Copyright © 2022 Erich Eckner.
The Arch Linux name and logo are recognized trademarks. Some rights reserved. The registered trademark Linux® is used pursuant to a sublicense from LMI, the exclusive licensee of Linus Torvalds, owner of the mark on a world-wide basis.