From b00555667522f812440572016f3c1237941a63b2 Mon Sep 17 00:00:00 2001 From: Warren Dukes Date: Mon, 15 Nov 2004 19:29:20 +0000 Subject: this shit really needs to be cleaned up, but its good enough for testing, intelligently use memmove, when inserting nodes in a sorted list git-svn-id: https://svn.musicpd.org/mpd/trunk@2677 09075e82-0dd4-0310-85a5-a0d7c8717e4f --- src/directory.c | 1 + src/list.c | 39 ++++++++++++++++++++++++++++----------- src/list.h | 4 ++-- src/song.c | 2 +- src/tagTracker.c | 23 +++++++++++++---------- 5 files changed, 45 insertions(+), 24 deletions(-) diff --git a/src/directory.c b/src/directory.c index 56fcdd009..d7163be41 100644 --- a/src/directory.c +++ b/src/directory.c @@ -938,6 +938,7 @@ void readDirectoryInfo(FILE * fp,Directory * directory) { insertInListBeforeNode( directory->subDirectories, nextDirNode, + -1, key, (void *)subDirectory); } diff --git a/src/list.c b/src/list.c index a777562d4..9161acdf2 100644 --- a/src/list.c +++ b/src/list.c @@ -61,7 +61,7 @@ List * makeList(ListFreeDataFunc * freeDataFunc, int strdupKeys) { return list; } -ListNode * insertInListBeforeNode(List * list, ListNode * beforeNode, char * key, void * data) +ListNode * insertInListBeforeNode(List * list, ListNode * beforeNode, int pos, char * key, void * data) { ListNode * node; @@ -105,8 +105,20 @@ ListNode * insertInListBeforeNode(List * list, ListNode * beforeNode, char * list->numberOfNodes++; - /*freeListNodesArray(list);*/ - if(list->sorted) makeListNodesArray(list); + if(list->sorted) { + list->nodesArray = realloc(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; } @@ -180,12 +192,12 @@ int insertInListWithoutKey(List * list, void * data) { return 1; } -int findNodeInList(List * list, char * key, ListNode ** node) { - static long high; - static long low; - static long cur; - static ListNode * tmpNode; - static int cmp; +int findNodeInList(List * list, char * key, ListNode ** node, int * pos) { + long high; + long low; + long cur; + ListNode * tmpNode; + int cmp; assert(list!=NULL); @@ -200,6 +212,7 @@ int findNodeInList(List * list, char * key, ListNode ** node) { cmp = strcmp(tmpNode->key,key); if(cmp==0) { *node = tmpNode; + *pos = cur; return 1; } else if(cmp>0) high = cur; @@ -212,16 +225,19 @@ int findNodeInList(List * list, char * key, ListNode ** node) { cur = high; if(cur>=0) { tmpNode = list->nodesArray[cur]; - cmp = strcmp(tmpNode->key,key); *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; } @@ -242,8 +258,9 @@ int findNodeInList(List * list, char * key, ListNode ** node) { int findInList(List * list, char * key, void ** data) { ListNode * node; + int pos; - if(findNodeInList(list, key, &node)) { + if(findNodeInList(list, key, &node, &pos)) { if(data) *data = node->data; return 1; } diff --git a/src/list.h b/src/list.h index 9a2a07484..ed54a3b02 100644 --- a/src/list.h +++ b/src/list.h @@ -74,7 +74,7 @@ List * makeList(ListFreeDataFunc * freeDataFunc, int strdupKeys); ListNode * insertInList(List * list,char * key,void * data); ListNode * insertInListBeforeNode(List * list, ListNode * beforeNode, - char * key, void * data); + int pos, char * key, void * data); int insertInListWithoutKey(List * list,void * data); @@ -99,7 +99,7 @@ int findInList(List * list, char * key, void ** data); /* 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); +int findNodeInList(List * list, char * key, ListNode ** node, int * pos); /* frees memory malloc'd for list and its nodes * _list_ -> List to be free'd diff --git a/src/song.c b/src/song.c index a54c71735..91714f01c 100644 --- a/src/song.c +++ b/src/song.c @@ -189,7 +189,7 @@ void insertSongIntoList(SongList * list, ListNode ** nextSongNode, char * key, *nextSongNode = (*nextSongNode)->nextNode; } else { - insertInListBeforeNode(list, *nextSongNode, song->url, + insertInListBeforeNode(list, *nextSongNode, -1, song->url, (void *)song); } } diff --git a/src/tagTracker.c b/src/tagTracker.c index be25751b0..4e310d8b3 100644 --- a/src/tagTracker.c +++ b/src/tagTracker.c @@ -23,6 +23,7 @@ typedef struct tagTrackerItem { char * getTagItemString(int type, char * string) { ListNode * node; + int pos; /*if(type == TAG_ITEM_TITLE) return strdup(string);*/ @@ -31,15 +32,16 @@ char * getTagItemString(int type, char * string) { sortList(tagLists[type]); } - if(findNodeInList(tagLists[type], string, &node)) { + if(findNodeInList(tagLists[type], string, &node, &pos)) { ((TagTrackerItem *)node->data)->count++; } else { TagTrackerItem * item = malloc(sizeof(TagTrackerItem)); item->count = 1; item->visited = 0; - node = insertInListBeforeNode(tagLists[type], node, string, - item); + node = insertInListBeforeNode(tagLists[type], node, pos, + string, item); + } return node->key; @@ -47,6 +49,7 @@ char * getTagItemString(int type, char * string) { void removeTagItemString(int type, char * string) { ListNode * node; + int pos; assert(string); @@ -58,7 +61,7 @@ void removeTagItemString(int type, char * string) { return; }*/ - if(findNodeInList(tagLists[type], string, &node)) { + if(findNodeInList(tagLists[type], string, &node, &pos)) { TagTrackerItem * item = node->data; item->count--; if(item->count <= 0) deleteNodeFromList(tagLists[type], node); @@ -126,23 +129,23 @@ void resetVisitedFlagsInTagTracker(int type) { } int wasVisitedInTagTracker(int type, char * str) { - ListNode * node; + TagTrackerItem * item; if(!tagLists[type]) return 0; - if(!findNodeInList(tagLists[type], str, &node)) return 0; + if(!findInList(tagLists[type], str, &item)) return 0; - return ((TagTrackerItem *)node->data)->visited; + return item->visited; } void visitInTagTracker(int type, char * str) { - ListNode * node; + TagTrackerItem * item; if(!tagLists[type]) return; - if(!findNodeInList(tagLists[type], str, &node)) return; + if(!findInList(tagLists[type], str, &item)) return; - ((TagTrackerItem *)node->data)->visited = 1; + item->visited = 1; } void printVisitedInTagTracker(FILE * fp, int type) { -- cgit v1.2.3