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

5 files changed, 80 insertions, 57 deletions

diff --git a/TODO b/TODO
index b5beab7b5..895e56216 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 e71ab7bfe..491255306 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 f0d30d802..7db1ee145 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;i<list->numberOfNodes;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 6ea43fbef..9a2a07484 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 68124c9e2..b6160e2a1 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;
 }