From 32e5f4ca2b43c310ff6639320dec2dd52f159f50 Mon Sep 17 00:00:00 2001 From: Qball Cow Date: Wed, 16 Nov 2005 14:43:04 +0000 Subject: DJWLindenaar balanced tree and master process patch git-svn-id: https://svn.musicpd.org/mpd/trunk@3669 09075e82-0dd4-0310-85a5-a0d7c8717e4f --- src/tagTracker.c | 134 ++++++++++++++++++++++++++++--------------------------- 1 file changed, 69 insertions(+), 65 deletions(-) (limited to 'src/tagTracker.c') diff --git a/src/tagTracker.c b/src/tagTracker.c index 57a96c70b..4fb326535 100644 --- a/src/tagTracker.c +++ b/src/tagTracker.c @@ -1,11 +1,12 @@ #include "tagTracker.h" -#include "list.h" #include "log.h" +#include #include +#include -static List * tagLists[TAG_NUM_OF_ITEM_TYPES] = +static GTree * tagLists[TAG_NUM_OF_ITEM_TYPES] = { NULL, NULL, @@ -21,89 +22,96 @@ typedef struct tagTrackerItem { mpd_sint8 visited; } TagTrackerItem; +int keyCompare(const void *a, const void *b, void *data) { + return strcmp(a,b); +} + char * getTagItemString(int type, char * string) { - ListNode * node; - int pos; + TagTrackerItem * item; + TagTrackerItem ** itemPointer = &item; + char *key; + char **keyPointer = &key; + /*if(type == TAG_ITEM_TITLE) return strdup(string);*/ if(tagLists[type] == NULL) { - tagLists[type] = makeList(free, 1); - sortList(tagLists[type]); + tagLists[type] = g_tree_new_full(keyCompare, NULL, free, free); } - if(findNodeInList(tagLists[type], string, &node, &pos)) { - ((TagTrackerItem *)node->data)->count++; + if((TagTrackerItem *)g_tree_lookup_extended(tagLists[type], string, (void**)keyPointer, (void**)itemPointer )) { + item->count++; } else { - TagTrackerItem * item = malloc(sizeof(TagTrackerItem)); + item = malloc(sizeof(TagTrackerItem)); item->count = 1; item->visited = 0; - node = insertInListBeforeNode(tagLists[type], node, pos, - string, item); + key = strdup(string); + g_tree_insert(tagLists[type], key, item); + } - return node->key; + return key; } + void removeTagItemString(int type, char * string) { - ListNode * node; - int pos; + TagTrackerItem *item; assert(string); assert(tagLists[type]); if(tagLists[type] == NULL) return; - /*if(!node) { - free(string); - return; - }*/ - - if(findNodeInList(tagLists[type], string, &node, &pos)) { - TagTrackerItem * item = node->data; + if((item = g_tree_lookup(tagLists[type], string))) { item->count--; - if(item->count <= 0) deleteNodeFromList(tagLists[type], node); + if(item->count <= 0) g_tree_remove(tagLists[type], string); } - if(tagLists[type]->numberOfNodes == 0) { +/* why would this be done??? free it when mpd quits... + if(tagLists[type]->numberOfNodes == 0) { freeList(tagLists[type]); tagLists[type] = NULL; } +*/ +} + +void destroyTagTracker() { + int type; + for (type=0; type < TAG_NUM_OF_ITEM_TYPES; type ++) + if (tagLists[type]) + g_tree_destroy(tagLists[type]); } int getNumberOfTagItems(int type) { if(tagLists[type] == NULL) return 0; - return tagLists[type]->numberOfNodes; + return g_tree_nnodes(tagLists[type]); } - +int calcSavedMemory(char *key, TagTrackerItem* value, int* sum) { + *sum -= sizeof(int) + 4*sizeof(void*); //sizeof(_GTreeNode) + *sum -= sizeof(TagTrackerItem); + *sum += (strlen(key)+1)*value->count; + return FALSE; +} + void printMemorySavedByTagTracker() { int i; - ListNode * node; size_t sum = 0; for(i = 0; i < TAG_NUM_OF_ITEM_TYPES; i++) { if(!tagLists[i]) continue; - sum -= sizeof(List); - - node = tagLists[i]->firstNode; - - while(node != NULL) { - sum -= sizeof(ListNode); - sum -= sizeof(TagTrackerItem); - sum -= sizeof(node->key); - sum += (strlen(node->key)+1)*(*((int *)node->data)); - node = node->nextNode; - } + sum -= 5*sizeof(void*);//sizeof(_GTree) + g_tree_foreach(tagLists[i], (GTraverseFunc)calcSavedMemory, &sum); } DEBUG("saved memory from tags: %li\n", (long)sum); } void sortTagTrackerInfo() { + /* implicit sorting int i; for(i = 0; i < TAG_NUM_OF_ITEM_TYPES; i++) { @@ -112,56 +120,52 @@ void sortTagTrackerInfo() { DEBUG("sorting %s info\n", mpdTagItemKeys[i]); sortList(tagLists[i]); - } + }*/ } +int resetVisitedFlag(char *key, TagTrackerItem *value, void *data) { + value->visited = 0; + return FALSE; +} void resetVisitedFlagsInTagTracker(int type) { - ListNode * node; if(!tagLists[type]) return; - node = tagLists[type]->firstNode; - - while(node) { - ((TagTrackerItem *)node->data)->visited = 0; - node = node->nextNode; - } + g_tree_foreach(tagLists[type], (GTraverseFunc)resetVisitedFlag, NULL); } int wasVisitedInTagTracker(int type, char * str) { - void * item; + TagTrackerItem * item; if(!tagLists[type]) return 0; - if(!findInList(tagLists[type], str, &item)) return 0; + if(!(item = g_tree_lookup(tagLists[type], str))) return 0; - return ((TagTrackerItem *)item)->visited; + return item->visited; } void visitInTagTracker(int type, char * str) { - void * item; + TagTrackerItem * item; if(!tagLists[type]) return; - if(!findInList(tagLists[type], str, &item)) return; + if(!(item = g_tree_lookup(tagLists[type], str))) return; - ((TagTrackerItem *)item)->visited = 1; + item->visited = 1; } -void printVisitedInTagTracker(FILE * fp, int type) { - ListNode * node; - TagTrackerItem * item; - - if(!tagLists[type]) return; +struct _PrintVisitedUserdata { + FILE *fp; + char *type; +}; - node = tagLists[type]->firstNode; +int printVisitedFlag(char *key, TagTrackerItem* value, struct _PrintVisitedUserdata *data) { + if(value->visited) myfprintf(data->fp, "%s: %s\n", data->type, key); + return FALSE; +} - while(node) { - item = node->data; - if(item->visited) { - myfprintf(fp, "%s: %s\n", mpdTagItemKeys[type], - node->key); - } - node = node->nextNode; - } +void printVisitedInTagTracker(FILE * fp, int type) { + struct _PrintVisitedUserdata data = {fp, mpdTagItemKeys[type]}; + if(!tagLists[type]) return; + g_tree_foreach( tagLists[type], (GTraverseFunc)printVisitedFlag, (void*)&data); } -- cgit v1.2.3