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

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) {