aboutsummaryrefslogtreecommitdiffstats
diff options
context:
space:
mode:
authorWarren Dukes <warren.dukes@gmail.com>2004-11-15 19:29:20 +0000
committerWarren Dukes <warren.dukes@gmail.com>2004-11-15 19:29:20 +0000
commitb00555667522f812440572016f3c1237941a63b2 (patch)
tree59e5acb5ab6c27bf2807d57d36ea53b7c5409b21
parentf3e8d59d5c584f5925a8b23919aaa5b5c954cf85 (diff)
downloadmpd-b00555667522f812440572016f3c1237941a63b2.tar.gz
mpd-b00555667522f812440572016f3c1237941a63b2.tar.xz
mpd-b00555667522f812440572016f3c1237941a63b2.zip
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
Diffstat (limited to '')
-rw-r--r--src/directory.c1
-rw-r--r--src/list.c39
-rw-r--r--src/list.h4
-rw-r--r--src/song.c2
-rw-r--r--src/tagTracker.c23
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) {