aboutsummaryrefslogtreecommitdiffstats
path: root/src/list.c
diff options
context:
space:
mode:
Diffstat (limited to 'src/list.c')
-rw-r--r--src/list.c516
1 files changed, 0 insertions, 516 deletions
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 <assert.h>
-#include <string.h>
-
-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);
-}
generated by cgit v1.2.3 (git 2.25.1) at 2024-07-10 01:45:36 +0000