From d35747a40c7dea12de95f78a4f283a45ef687597 Mon Sep 17 00:00:00 2001 From: Warren Dukes Date: Mon, 23 Feb 2004 23:41:20 +0000 Subject: import from SF CVS git-svn-id: https://svn.musicpd.org/mpd/trunk@1 09075e82-0dd4-0310-85a5-a0d7c8717e4f --- src/list.c | 436 +++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++ 1 file changed, 436 insertions(+) create mode 100644 src/list.c (limited to 'src/list.c') diff --git a/src/list.c b/src/list.c new file mode 100644 index 000000000..8ce872fc2 --- /dev/null +++ b/src/list.c @@ -0,0 +1,436 @@ +/* the Music Player Daemon (MPD) + * (c)2003-2004 by Warren Dukes (shank@mercury.chem.pitt.edu) + * 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 +#include +#include +#include +#include + +void makeListNodesArray(List * list) { + ListNode * node = list->firstNode; + long i; + + list->nodesArray = malloc(sizeof(ListNode *)*list->numberOfNodes); + + for(i=0;inumberOfNodes;i++) { + list->nodesArray[i] = node; + node = node->nextNode; + } +} + +void freeListNodesArray(List * list) { + free(list->nodesArray); + list->nodesArray = NULL; +} + +List * makeList(ListFreeDataFunc * freeDataFunc) { + List * list = malloc(sizeof(List)); + + assert(list!=NULL); + + list->firstNode = NULL; + list->lastNode = NULL; + list->freeDataFunc = freeDataFunc; + list->numberOfNodes = 0; + list->nodesArray = NULL; + + return list; +} + +int insertInList(List * list,char * key,void * data) { + ListNode * node; + + assert(list!=NULL); + assert(key!=NULL); + /*assert(data!=NULL);*/ + + node = malloc(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 = malloc((strlen(key)+1)*sizeof(char)); + assert(node->key!=NULL); + strcpy(node->key,key); + node->data = data; + node->nextNode = NULL; + node->prevNode = list->lastNode; + + list->lastNode = node; + + list->numberOfNodes++; + + return 1; +} + +int insertInListWithoutKey(List * list, void * data) { + ListNode * node; + + assert(list!=NULL); + assert(data!=NULL); + + node = malloc(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; +} + +int findInList(List * list,char * key,void ** data) { + static long high; + static long low; + static long cur; + static ListNode * tmpNode; + static int cmp; + + assert(list!=NULL); + + if(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) { + (*data) = tmpNode->data; + return 1; + } + else if(cmp>0) high = cur; + else { + if(low==cur) break; + low = cur; + } + } + + cur = high; + if(cur>=0) { + tmpNode = list->nodesArray[cur]; + if(strcmp(tmpNode->key,key)==0) { + (*data) = tmpNode->data; + return 1; + } + } + } + else { + tmpNode = list->firstNode; + + while(tmpNode!=NULL && strcmp(tmpNode->key,key)!=0) { + tmpNode = tmpNode->nextNode; + } + + if(tmpNode!=NULL) { + (*data) = tmpNode->data; + return 1; + } + } + + return 0; +} + +int deleteFromList(List * list,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); + } + free(node->key); + free(node); + list->numberOfNodes--; + + if(list->nodesArray) { + freeListNodesArray(list); + 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; + free(tmpNode->key); + if(((List *)list)->freeDataFunc) { + ((List *)list)->freeDataFunc(tmpNode->data); + } + free(tmpNode); + tmpNode = tmpNode2; + } + + free(list); +} + +void clearList(List * list) { + ListNode * tmpNode; + ListNode * tmpNode2; + + assert(list!=NULL); + + tmpNode = ((List *)list)->firstNode; + + while(tmpNode!=NULL) { + tmpNode2 = tmpNode->nextNode; + free(tmpNode->key); + if(((List *)list)->freeDataFunc) { + ((List *)list)->freeDataFunc(tmpNode->data); + } + free(tmpNode); + tmpNode = tmpNode2; + } + + if(list->nodesArray) freeListNodesArray(list); + + list->firstNode = NULL; + list->lastNode = NULL; + list->numberOfNodes = 0; +} + +void swapNodes(ListNode * nodeA, ListNode * nodeB) { + 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; +} + +void moveNodeAfter(List * list, ListNode * moveNode, ListNode * beforeNode) { + ListNode * prev; + ListNode * next; + + assert(moveNode!=NULL); + + prev = moveNode->prevNode; + next = moveNode->nextNode; + + if(prev) prev->nextNode = next; + else list->firstNode = next; + if(next) next->prevNode = prev; + else list->lastNode = prev; + + if(beforeNode) { + next = beforeNode->nextNode; + moveNode->nextNode = next; + moveNode->prevNode = beforeNode; + next->prevNode = moveNode; + beforeNode->nextNode = moveNode; + if(beforeNode==list->lastNode) list->lastNode = moveNode; + } + else { + moveNode->prevNode = NULL; + moveNode->nextNode = list->firstNode; + list->firstNode = moveNode; + if(list->lastNode==NULL) list->lastNode = moveNode; + } +} + +void bubbleSort(ListNode ** nodesArray, long start, long end) { + long i; + long j; + ListNode * node; + + if(start>=end) return; + + for(j=start;j=start;i--) { + node = nodesArray[i]; + if(strcmp(node->key,node->nextNode->key)>0) { + swapNodes(node,node->nextNode); + } + } + } +} + +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; + char * pivotKey; + + List * startList = makeList(free); + List * endList = makeList(free); + long * startPtr = malloc(sizeof(long)); + long * endPtr = malloc(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(pivotlastNode); + deleteNodeFromList(endList,endList->lastNode); + + if(pivot-1-start>0) { + startPtr = malloc(sizeof(long)); + endPtr = malloc(sizeof(long)); + *startPtr = start; + *endPtr = pivot-1; + insertInListWithoutKey(startList,(void *)startPtr); + insertInListWithoutKey(endList,(void *)endPtr); + } + + if(end-pivot-1>0) { + startPtr = malloc(sizeof(long)); + endPtr = malloc(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); + + if(list->numberOfNodes<2) return; + + if(list->nodesArray) freeListNodesArray(list); + makeListNodesArray(list); + + quickSort(list->nodesArray,0,list->numberOfNodes-1); +} -- cgit v1.2.3