From 7a8ef820a4c76c83ad1d0e8eb59c1a186d9fa448 Mon Sep 17 00:00:00 2001 From: Max Kellermann Date: Fri, 2 Jan 2009 18:41:35 +0100 Subject: list: removed linked list library It's been superseded by GLib's GSList. --- src/list.c | 516 ------------------------------------------------------------- 1 file changed, 516 deletions(-) delete mode 100644 src/list.c (limited to 'src/list.c') diff --git a/src/list.c b/src/list.c deleted file mode 100644 index e6c91c0c2..000000000 --- a/src/list.c +++ /dev/null @@ -1,516 +0,0 @@ -/* the Music Player Daemon (MPD) - * Copyright (C) 2003-2007 by Warren Dukes (warren.dukes@gmail.com) - * This project's homepage is: http://www.musicpd.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 "list.h" -#include "utils.h" - -#include -#include - -static void makeListNodesArray(List * list) -{ - ListNode *node = list->firstNode; - long i; - - if (!list->numberOfNodes) - return; - - list->nodesArray = xrealloc(list->nodesArray, - sizeof(ListNode *) * list->numberOfNodes); - - for (i = 0; i < list->numberOfNodes; i++) { - list->nodesArray[i] = node; - node = node->nextNode; - } -} - -static void freeListNodesArray(List * list) -{ - if (!list->nodesArray) - return; - free(list->nodesArray); - list->nodesArray = NULL; -} - -List *makeList(ListFreeDataFunc * freeDataFunc, int strdupKeys) -{ - List *list = xmalloc(sizeof(List)); - - assert(list != NULL); - - list->sorted = 0; - list->firstNode = NULL; - list->lastNode = NULL; - list->freeDataFunc = freeDataFunc; - list->numberOfNodes = 0; - list->nodesArray = NULL; - list->strdupKeys = strdupKeys; - - return list; -} - -ListNode *insertInListBeforeNode(List * list, ListNode * beforeNode, int pos, - const char *key, void *data) -{ - ListNode *node; - - assert(list != NULL); - assert(key != NULL); - /*assert(data!=NULL); */ - - node = xmalloc(sizeof(ListNode)); - assert(node != NULL); - - node->nextNode = beforeNode; - if (beforeNode == list->firstNode) { - if (list->firstNode == NULL) { - assert(list->lastNode == NULL); - list->lastNode = node; - } else { - assert(list->lastNode != NULL); - assert(list->lastNode->nextNode == NULL); - list->firstNode->prevNode = node; - } - node->prevNode = NULL; - list->firstNode = node; - } else { - if (beforeNode) { - node->prevNode = beforeNode->prevNode; - beforeNode->prevNode = node; - } else { - node->prevNode = list->lastNode; - list->lastNode = node; - } - node->prevNode->nextNode = node; - } - - if (list->strdupKeys) - node->key = xstrdup(key); - else - node->key = key; - - node->data = data; - - list->numberOfNodes++; - - if (list->sorted) { - list->nodesArray = xrealloc(list->nodesArray, - list->numberOfNodes * - sizeof(ListNode *)); - if (node == list->lastNode) { - list->nodesArray[list->numberOfNodes - 1] = node; - } else if (pos < 0) - makeListNodesArray(list); - else { - memmove(list->nodesArray + pos + 1, - list->nodesArray + pos, - sizeof(ListNode *) * (list->numberOfNodes - - pos - 1)); - list->nodesArray[pos] = node; - } - } - - return node; -} - -ListNode *insertInList(List * list, const char *key, void *data) -{ - ListNode *node; - - assert(list != NULL); - assert(key != NULL); - /*assert(data!=NULL); */ - - node = xmalloc(sizeof(ListNode)); - assert(node != NULL); - - if (list->nodesArray) - freeListNodesArray(list); - - if (list->firstNode == NULL) { - assert(list->lastNode == NULL); - list->firstNode = node; - } else { - assert(list->lastNode != NULL); - assert(list->lastNode->nextNode == NULL); - list->lastNode->nextNode = node; - } - - if (list->strdupKeys) - node->key = xstrdup(key); - else - node->key = key; - - node->data = data; - node->nextNode = NULL; - node->prevNode = list->lastNode; - - list->lastNode = node; - - list->numberOfNodes++; - - return node; -} - -int insertInListWithoutKey(List * list, void *data) -{ - ListNode *node; - - assert(list != NULL); - assert(data != NULL); - - node = xmalloc(sizeof(ListNode)); - assert(node != NULL); - - if (list->nodesArray) - freeListNodesArray(list); - - if (list->firstNode == NULL) { - assert(list->lastNode == NULL); - list->firstNode = node; - } else { - assert(list->lastNode != NULL); - assert(list->lastNode->nextNode == NULL); - list->lastNode->nextNode = node; - } - - node->key = NULL; - node->data = data; - node->nextNode = NULL; - node->prevNode = list->lastNode; - - list->lastNode = node; - - list->numberOfNodes++; - - return 1; -} - -/* if _key_ is not found, *_node_ is assigned to the node before which - the info would be found */ -int findNodeInList(List * list, const char *key, ListNode ** node, int *pos) -{ - long high; - long low; - long cur; - ListNode *tmpNode; - int cmp; - - assert(list != NULL); - - if (list->sorted && list->nodesArray) { - high = list->numberOfNodes - 1; - low = 0; - cur = high; - - while (high > low) { - cur = (high + low) / 2; - tmpNode = list->nodesArray[cur]; - cmp = strcmp(tmpNode->key, key); - if (cmp == 0) { - *node = tmpNode; - *pos = cur; - return 1; - } else if (cmp > 0) - high = cur; - else { - if (low == cur) - break; - low = cur; - } - } - - cur = high; - if (cur >= 0) { - tmpNode = list->nodesArray[cur]; - *node = tmpNode; - *pos = high; - cmp = tmpNode ? strcmp(tmpNode->key, key) : -1; - if (0 == cmp) - return 1; - else if (cmp > 0) - return 0; - else { - *pos = -1; - *node = NULL; - return 0; - } - } else { - *pos = 0; - *node = list->firstNode; - return 0; - } - } else { - tmpNode = list->firstNode; - - while (tmpNode != NULL && strcmp(tmpNode->key, key) != 0) { - tmpNode = tmpNode->nextNode; - } - - *node = tmpNode; - if (tmpNode) - return 1; - } - - return 0; -} - -int findInList(List * list, const char *key, void **data) -{ - ListNode *node; - int pos; - - if (findNodeInList(list, key, &node, &pos)) { - if (data) - *data = node->data; - return 1; - } - - return 0; -} - -int deleteFromList(List * list, const char *key) -{ - ListNode *tmpNode; - - assert(list != NULL); - - tmpNode = list->firstNode; - - while (tmpNode != NULL && strcmp(tmpNode->key, key) != 0) { - tmpNode = tmpNode->nextNode; - } - - if (tmpNode != NULL) - deleteNodeFromList(list, tmpNode); - else - return 0; - - return 1; -} - -void deleteNodeFromList(List * list, ListNode * node) -{ - assert(list != NULL); - assert(node != NULL); - - if (node->prevNode == NULL) { - list->firstNode = node->nextNode; - } else { - node->prevNode->nextNode = node->nextNode; - } - if (node->nextNode == NULL) { - list->lastNode = node->prevNode; - } else { - node->nextNode->prevNode = node->prevNode; - } - if (list->freeDataFunc) { - list->freeDataFunc(node->data); - } - - if (list->strdupKeys) - xfree(node->key); - free(node); - list->numberOfNodes--; - - if (list->nodesArray) { - freeListNodesArray(list); - if (list->sorted) - makeListNodesArray(list); - } - -} - -void freeList(void *list) -{ - ListNode *tmpNode; - ListNode *tmpNode2; - - assert(list != NULL); - - tmpNode = ((List *) list)->firstNode; - - if (((List *) list)->nodesArray) - free(((List *) list)->nodesArray); - - while (tmpNode != NULL) { - tmpNode2 = tmpNode->nextNode; - if (((List *) list)->strdupKeys) - xfree(tmpNode->key); - if (((List *) list)->freeDataFunc) { - ((List *) list)->freeDataFunc(tmpNode->data); - } - free(tmpNode); - tmpNode = tmpNode2; - } - - free(list); -} - -static void swapNodes(ListNode * nodeA, ListNode * nodeB) -{ - const char *key; - void *data; - - assert(nodeA != NULL); - assert(nodeB != NULL); - - key = nodeB->key; - data = nodeB->data; - - nodeB->key = nodeA->key; - nodeB->data = nodeA->data; - - nodeA->key = key; - nodeA->data = data; -} - -static void bubbleSort(ListNode ** nodesArray, long start, long end) -{ - long i; - long j; - ListNode *node; - - if (start >= end) - return; - - for (j = start; j < end; j++) { - for (i = end - 1; i >= start; i--) { - node = nodesArray[i]; - if (strcmp(node->key, node->nextNode->key) > 0) { - swapNodes(node, node->nextNode); - } - } - } -} - -static void quickSort(ListNode ** nodesArray, long start, long end) -{ - if (start >= end) - return; - else if (end - start < 5) - bubbleSort(nodesArray, start, end); - else { - long i; - ListNode *node; - long pivot; - ListNode *pivotNode; - const char *pivotKey; - - List *startList = makeList(free, 0); - List *endList = makeList(free, 0); - long *startPtr = xmalloc(sizeof(long)); - long *endPtr = xmalloc(sizeof(long)); - *startPtr = start; - *endPtr = end; - insertInListWithoutKey(startList, (void *)startPtr); - insertInListWithoutKey(endList, (void *)endPtr); - - while (startList->numberOfNodes) { - start = *((long *)startList->lastNode->data); - end = *((long *)endList->lastNode->data); - - if (end - start < 5) { - bubbleSort(nodesArray, start, end); - deleteNodeFromList(startList, - startList->lastNode); - deleteNodeFromList(endList, endList->lastNode); - } else { - pivot = (start + end) / 2; - pivotNode = nodesArray[pivot]; - pivotKey = pivotNode->key; - - for (i = pivot - 1; i >= start; i--) { - node = nodesArray[i]; - if (strcmp(node->key, pivotKey) > 0) { - pivot--; - if (pivot > i) { - swapNodes(node, - nodesArray - [pivot]); - } - swapNodes(pivotNode, - nodesArray[pivot]); - pivotNode = nodesArray[pivot]; - } - } - for (i = pivot + 1; i <= end; i++) { - node = nodesArray[i]; - if (strcmp(pivotKey, node->key) > 0) { - pivot++; - if (pivot < i) { - swapNodes(node, - nodesArray - [pivot]); - } - swapNodes(pivotNode, - nodesArray[pivot]); - pivotNode = nodesArray[pivot]; - } - } - - deleteNodeFromList(startList, - startList->lastNode); - deleteNodeFromList(endList, endList->lastNode); - - if (pivot - 1 - start > 0) { - startPtr = xmalloc(sizeof(long)); - endPtr = xmalloc(sizeof(long)); - *startPtr = start; - *endPtr = pivot - 1; - insertInListWithoutKey(startList, - (void *) - startPtr); - insertInListWithoutKey(endList, - (void *)endPtr); - } - - if (end - pivot - 1 > 0) { - startPtr = xmalloc(sizeof(long)); - endPtr = xmalloc(sizeof(long)); - *startPtr = pivot + 1; - *endPtr = end; - insertInListWithoutKey(startList, - (void *) - startPtr); - insertInListWithoutKey(endList, - (void *)endPtr); - } - } - } - - freeList(startList); - freeList(endList); - } -} - -void sortList(List * list) -{ - assert(list != NULL); - - list->sorted = 1; - - if (list->numberOfNodes < 2) - return; - - if (list->nodesArray) - freeListNodesArray(list); - makeListNodesArray(list); - - quickSort(list->nodesArray, 0, list->numberOfNodes - 1); -} -- cgit v1.2.3