From 33b9585d68e6f084b214985c2beb2887bf9d929a Mon Sep 17 00:00:00 2001 From: Warren Dukes Date: Mon, 15 Nov 2004 17:24:57 +0000 Subject: insert stuff in tagTracker in sorted order, hopefully this makes it faster git-svn-id: https://svn.musicpd.org/mpd/trunk@2672 09075e82-0dd4-0310-85a5-a0d7c8717e4f --- TODO | 2 +- autogen.sh | 2 +- src/list.c | 101 +++++++++++++++++++++++++++++++++---------------------- src/list.h | 10 ++++-- src/tagTracker.c | 22 ++++++------ 5 files changed, 80 insertions(+), 57 deletions(-) diff --git a/TODO b/TODO index b5beab7b..895e5621 100644 --- a/TODO +++ b/TODO @@ -1,6 +1,6 @@ 0.12 ---- -*) better handle streams so they don't use TagTracker +*) cleanup list code and sorting *) parsing of lame tags (including getting replaygain info) diff --git a/autogen.sh b/autogen.sh index e71ab7bf..49125530 100755 --- a/autogen.sh +++ b/autogen.sh @@ -96,7 +96,7 @@ fi echo "Generating configuration files for $package, please wait...." -ACLOCAL_FLAGS="$ACLOCAL_FLAGS -I ./m4" +ACLOCAL_FLAGS="$ACLOCAL_FLAGS -I $PWD/m4" if [ -d /usr/local/share/aclocal ]; then ACLOCAL_FLAGS="$ACLOCAL_FLAGS -I /usr/local/share/aclocal" fi diff --git a/src/list.c b/src/list.c index f0d30d80..7db1ee14 100644 --- a/src/list.c +++ b/src/list.c @@ -29,6 +29,8 @@ void makeListNodesArray(List * list) { ListNode * node = list->firstNode; long i; + if(!list->numberOfNodes) return; + list->nodesArray = malloc(sizeof(ListNode *)*list->numberOfNodes); for(i=0;inumberOfNodes;i++) { @@ -38,6 +40,7 @@ void makeListNodesArray(List * list) { } void freeListNodesArray(List * list) { + if(!list->nodesArray) return; free(list->nodesArray); list->nodesArray = NULL; } @@ -57,8 +60,7 @@ List * makeList(ListFreeDataFunc * freeDataFunc, int strdupKeys) { return list; } -int insertInListBeforeNode(List * list, ListNode * beforeNode, char * key, - void * data) +ListNode * insertInListBeforeNode(List * list, ListNode * beforeNode, char * key, void * data) { ListNode * node; @@ -69,42 +71,44 @@ int insertInListBeforeNode(List * list, ListNode * beforeNode, char * key, node = malloc(sizeof(ListNode)); assert(node!=NULL); - if(list->nodesArray) freeListNodesArray(list); - - if(beforeNode==NULL) beforeNode = list->firstNode; - - node->nextNode = beforeNode; - if(beforeNode==list->firstNode) { - if(list->firstNode==NULL) { - assert(list->lastNode==NULL); - list->lastNode = node; + if(beforeNode==NULL) node = insertInList(list, key, data); + else { + 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 { - assert(list->lastNode!=NULL); - assert(list->lastNode->nextNode==NULL); - list->firstNode->prevNode = node; - } - node->prevNode = NULL; - list->firstNode = node; - } - else { - node->prevNode = beforeNode->prevNode; - if(node->prevNode) { - node->prevNode->nextNode = node; + node->prevNode = beforeNode->prevNode; + if(node->prevNode) { + node->prevNode->nextNode = node; + } + beforeNode->prevNode = node; } - beforeNode->prevNode = node; - } - - if(list->strdupKeys) node->key = strdup(key); - else node->key = key; - assert(node->key!=NULL); + if(list->strdupKeys) node->key = strdup(key); + else node->key = key; - node->data = data; + assert(node->key!=NULL); - list->numberOfNodes++; + node->data = data; - return 1; + list->numberOfNodes++; + } + + freeListNodesArray(list); + if(list->sorted) makeListNodesArray(list); + + return node; } ListNode * insertInList(List * list, char * key, void * data) { @@ -176,7 +180,7 @@ int insertInListWithoutKey(List * list, void * data) { return 1; } -ListNode * findNodeInList(List * list, char * key) { +int findNodeInList(List * list, char * key, ListNode ** node) { static long high; static long low; static long cur; @@ -185,7 +189,7 @@ ListNode * findNodeInList(List * list, char * key) { assert(list!=NULL); - if(list->nodesArray) { + if(list->sorted && list->nodesArray) { high = list->numberOfNodes-1; low = 0; cur = high; @@ -194,7 +198,10 @@ ListNode * findNodeInList(List * list, char * key) { cur = (high+low)/2; tmpNode = list->nodesArray[cur]; cmp = strcmp(tmpNode->key,key); - if(cmp==0) return tmpNode; + if(cmp==0) { + *node = tmpNode; + return 1; + } else if(cmp>0) high = cur; else { if(low==cur) break; @@ -205,7 +212,18 @@ ListNode * findNodeInList(List * list, char * key) { cur = high; if(cur>=0) { tmpNode = list->nodesArray[cur]; - if(strcmp(tmpNode->key,key)==0) return tmpNode; + cmp = strcmp(tmpNode->key,key); + *node = tmpNode; + if( 0 == cmp ) return 1; + else if( cmp < 0) return 0; + else { + *node = NULL; + return 0; + } + } + else { + *node = list->firstNode; + return 0; } } else { @@ -215,16 +233,17 @@ ListNode * findNodeInList(List * list, char * key) { tmpNode = tmpNode->nextNode; } - return tmpNode; + *node = tmpNode; + if(tmpNode) return 1; } - return NULL; + return 0; } int findInList(List * list, char * key, void ** data) { - ListNode * node = findNodeInList(list, key); + ListNode * node; - if(node) { + if(findNodeInList(list, key, &node)) { if(data) *data = node->data; return 1; } @@ -277,7 +296,7 @@ void deleteNodeFromList(List * list,ListNode * node) { if(list->nodesArray) { freeListNodesArray(list); - makeListNodesArray(list); + if(list->sorted) makeListNodesArray(list); } } @@ -481,6 +500,8 @@ void quickSort(ListNode ** nodesArray, long start, long end) { void sortList(List * list) { assert(list!=NULL); + list->sorted = 1; + if(list->numberOfNodes<2) return; if(list->nodesArray) freeListNodesArray(list); diff --git a/src/list.h b/src/list.h index 6ea43fbe..9a2a0748 100644 --- a/src/list.h +++ b/src/list.h @@ -52,6 +52,8 @@ typedef struct _List { long numberOfNodes; /* array for searching when list is sorted */ ListNode ** nodesArray; + /* sorted */ + int sorted; /* weather to strdup() key's on insertion */ int strdupKeys; } List; @@ -71,8 +73,8 @@ List * makeList(ListFreeDataFunc * freeDataFunc, int strdupKeys); */ ListNode * insertInList(List * list,char * key,void * data); -int insertInListBeforeNode(List * list, ListNode * beforeNode, char * key, - void * data); +ListNode * insertInListBeforeNode(List * list, ListNode * beforeNode, + char * key, void * data); int insertInListWithoutKey(List * list,void * data); @@ -95,7 +97,9 @@ void deleteNodeFromList(List * list,ListNode * node); */ int findInList(List * list, char * key, void ** data); -ListNode * findNodeInList(List * list, char * key); +/* if _key_ is not found, *_node_ is assigned to the node before which + the info would be found */ +int findNodeInList(List * list, char * key, ListNode ** node); /* frees memory malloc'd for list and its nodes * _list_ -> List to be free'd diff --git a/src/tagTracker.c b/src/tagTracker.c index 68124c9e..b6160e2a 100644 --- a/src/tagTracker.c +++ b/src/tagTracker.c @@ -28,18 +28,23 @@ char * getTagItemString(int type, char * string) { if(tagLists[type] == NULL) { tagLists[type] = makeList(free, 1); + sortList(tagLists[type]); } - if((node = findNodeInList(tagLists[type], string))) { + if(findNodeInList(tagLists[type], string, &node)) { + DEBUG("found\n"); ((TagTrackerItem *)node->data)->count++; } else { + DEBUG("not found\n"); TagTrackerItem * item = malloc(sizeof(TagTrackerItem)); item->count = 1; item->visited = 0; - node = insertInList(tagLists[type], string, item); + node = insertInListBeforeNode(tagLists[type], node, string, + item); } + DEBUG("key: %s:%s\n", string, node->key); return node->key; } @@ -51,15 +56,12 @@ void removeTagItemString(int type, char * string) { assert(tagLists[type]); if(tagLists[type] == NULL) return; - node = findNodeInList(tagLists[type], string); - assert(node); - /*if(!node) { free(string); return; }*/ - if(node) { + if(findNodeInList(tagLists[type], string, &node)) { TagTrackerItem * item = node->data; item->count--; if(item->count <= 0) deleteNodeFromList(tagLists[type], node); @@ -131,9 +133,7 @@ int wasVisitedInTagTracker(int type, char * str) { if(!tagLists[type]) return 0; - node = findNodeInList(tagLists[type], str); - - if(!node) return 0; + if(!findNodeInList(tagLists[type], str, &node)) return 0; return ((TagTrackerItem *)node->data)->visited; } @@ -143,9 +143,7 @@ void visitInTagTracker(int type, char * str) { if(!tagLists[type]) return; - node = findNodeInList(tagLists[type], str); - - if(!node) return; + if(!findNodeInList(tagLists[type], str, &node)) return; ((TagTrackerItem *)node->data)->visited = 1; } -- cgit v1.2.3