diff options
Diffstat (limited to 'src')
-rw-r--r-- | src/Makefile.am | 2 | ||||
-rw-r--r-- | src/tagTracker.c | 160 | ||||
-rw-r--r-- | src/tree.c | 699 | ||||
-rw-r--r-- | src/tree.h | 63 |
4 files changed, 67 insertions, 857 deletions
diff --git a/src/Makefile.am b/src/Makefile.am index d7deb1190..d7049cd99 100644 --- a/src/Makefile.am +++ b/src/Makefile.am @@ -83,7 +83,6 @@ mpd_headers = \ tag.h \ tag_id3.h \ tagTracker.h \ - tree.h \ utf8.h \ utils.h \ volume.h \ @@ -141,7 +140,6 @@ mpd_SOURCES = \ tag.c \ tag_id3.c \ tagTracker.c \ - tree.c \ utils.c \ volume.c \ utf8.c \ diff --git a/src/tagTracker.c b/src/tagTracker.c index 892cc2955..fdc535823 100644 --- a/src/tagTracker.c +++ b/src/tagTracker.c @@ -19,137 +19,111 @@ #include "tagTracker.h" #include "tag.h" -#include "tree.h" #include "utils.h" #include "myfprintf.h" #include "os_compat.h" +#include "directory.h" -static Tree *tagTrees[TAG_NUM_OF_ITEM_TYPES]; +struct visited { + struct visited *next; -typedef struct tagTrackerItem { - int count; - mpd_sint8 visited; -} TagTrackerItem; + /** + * this is the original pointer passed to visitInTagTracker(), + * i.e. the caller must not invalidate it until he calls + * resetVisitedFlagsInTagTracker(). + */ + const char *value; +} mpd_packed; -static pthread_mutex_t tag_item_lock = PTHREAD_MUTEX_INITIALIZER; +static struct visited *visited_heads[TAG_NUM_OF_ITEM_TYPES]; +static unsigned num_visited[TAG_NUM_OF_ITEM_TYPES]; -char *getTagItemString(int type, char *string) +char *getTagItemString(int type mpd_unused, char *string) { - TreeIterator iter; - char *ret; + return xstrdup(string); +} - pthread_mutex_lock(&tag_item_lock); +void removeTagItemString(int type mpd_unused, char *string) +{ + free(string); +} - if (tagTrees[type] == NULL) - { - tagTrees[type] = MakeTree((TreeCompareKeyFunction)strcmp, - (TreeFreeFunction)free, - (TreeFreeFunction)free); - } +static int visit_tag_items(int fd mpd_unused, Song *song, void *data) +{ + enum tag_type type = (enum tag_type)(size_t)data; + unsigned i; - if (FindInTree(tagTrees[type], string, &iter)) - { - ((TagTrackerItem *)GetTreeKeyData(&iter)->data)->count++; - ret = (char *)GetTreeKeyData(&iter)->key; - } - else - { - TagTrackerItem *item = xmalloc(sizeof(TagTrackerItem)); - char *key = xstrdup(string); - item->count = 1; - item->visited = 0; - InsertInTree(tagTrees[type], key, item); - ret = key; + if (song->tag == NULL) + return 0; + + for (i = 0; i < (unsigned)song->tag->numOfItems; ++i) { + const struct tag_item *item = song->tag->items[i]; + if (item->type == type) + visitInTagTracker(type, item->value); } - pthread_mutex_unlock(&tag_item_lock); - return ret; + return 0; } -void removeTagItemString(int type, char *string) +int getNumberOfTagItems(int type) { - TreeIterator iter; + int ret; - assert(string); + resetVisitedFlagsInTagTracker(type); - assert(tagTrees[type]); - if (tagTrees[type] == NULL) - return; + traverseAllIn(-1, NULL, visit_tag_items, NULL, (void*)(size_t)type); - pthread_mutex_lock(&tag_item_lock); - if (FindInTree(tagTrees[type], string, &iter)) - { - TagTrackerItem * item = - (TagTrackerItem *)GetTreeKeyData(&iter)->data; - item->count--; - if (item->count <= 0) - RemoveFromTreeByIterator(tagTrees[type], &iter); - } - - if (GetTreeSize(tagTrees[type]) == 0) - { - FreeTree(tagTrees[type]); - tagTrees[type] = NULL; - } - pthread_mutex_unlock(&tag_item_lock); + ret = (int)num_visited[type]; + resetVisitedFlagsInTagTracker(type); + return ret; } -int getNumberOfTagItems(int type) +void resetVisitedFlagsInTagTracker(int type) { - if (tagTrees[type] == NULL) - return 0; + while (visited_heads[type] != NULL) { + struct visited *v = visited_heads[type]; + visited_heads[type] = v->next; + free(v); + } - return GetTreeSize(tagTrees[type]); + num_visited[type] = 0; } -void resetVisitedFlagsInTagTracker(int type) +static struct visited * +find_visit(int type, const char *p) { - TreeIterator iter; + struct visited *v; - if (!tagTrees[type]) - return; + for (v = visited_heads[type]; v != NULL; v = v->next) + if (strcmp(v->value, p) == 0) + return v; - for (SetTreeIteratorToBegin(tagTrees[type], &iter); - !IsTreeIteratorAtEnd(&iter); - IncrementTreeIterator(&iter)) - { - ((TagTrackerItem *)GetTreeKeyData(&iter)->data)->visited = 0; - } + return NULL; } void visitInTagTracker(int type, const char *str) { - TreeIterator iter; - - if (!tagTrees[type]) - return; + struct visited *v = find_visit(type, str); + size_t length; - if (!FindInTree(tagTrees[type], str, &iter)) + if (v != NULL) return; - ((TagTrackerItem *)GetTreeKeyData(&iter)->data)->visited = 1; + length = strlen(str); + v = xmalloc(sizeof(*v)); + v->value = str; + v->next = visited_heads[type]; + visited_heads[type] = v; + ++num_visited[type]; } void printVisitedInTagTracker(int fd, int type) { - TreeIterator iter; - TagTrackerItem * item; + struct visited *v; - if (!tagTrees[type]) - return; - - for (SetTreeIteratorToBegin(tagTrees[type], &iter); - !IsTreeIteratorAtEnd(&iter); - IncrementTreeIterator(&iter)) - { - item = ((TagTrackerItem *)GetTreeKeyData(&iter)->data); - - if (item->visited) - { - fdprintf(fd, - "%s: %s\n", - mpdTagItemKeys[type], - (char *)GetTreeKeyData(&iter)->key); - } - } + for (v = visited_heads[type]; v != NULL; v = v->next) + fdprintf(fd, + "%s: %s\n", + mpdTagItemKeys[type], + v->value); } diff --git a/src/tree.c b/src/tree.c deleted file mode 100644 index d583aee7c..000000000 --- a/src/tree.c +++ /dev/null @@ -1,699 +0,0 @@ -/* the Music Player Daemon (MPD) - * Copyright (C) 2006-2007 by Warren Dukes (warren.dukes@gmail.com) - * This project's homepage is: http://www.musicpd.org - * - * This program is free software; you can redistribute it and/or modify - * it under the terms of the GNU General Public License as published by - * the Free Software Foundation; either version 2 of the License, or - * (at your option) any later version. - * - * This program is distributed in the hope that it will be useful, - * but WITHOUT ANY WARRANTY; without even the implied warranty of - * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the - * GNU General Public License for more details. - * You should have received a copy of the GNU General Public License - * along with this program; if not, write to the Free Software - * Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA - */ - -#include "tree.h" -#include "utils.h" -#include "os_compat.h" - -#ifndef CHILDREN_PER_NODE -#define CHILDREN_PER_NODE 25 -#endif - -#define DATA_PER_NODE (CHILDREN_PER_NODE-1) - -#if CHILDREN_PER_NODE > 7 -#define USE_BINARY_SEARCH 1 -#endif - - -/************************* DATA STRUCTURES **********************************/ - -struct _TreeNode -{ - TreeKeyData keyData[DATA_PER_NODE]; - struct _TreeNode * parent; - short parentPos; - struct _TreeNode * children[CHILDREN_PER_NODE]; - short count; -}; - -struct _Tree -{ - TreeCompareKeyFunction compareKey; - TreeFreeFunction freeKey; - TreeFreeFunction freeData; - TreeNode * rootNode; - int size; -}; - -/************************* STATIC METHODS ***********************************/ - -static -TreeNode * -_MakeNode(void) -{ - TreeNode * ret = xmalloc(sizeof(TreeNode)); - memset(ret, 0, sizeof(TreeNode)); - return ret; -} - -static -void -_ClearKeyData(TreeKeyData * keyData) -{ - memset(keyData, 0, sizeof(TreeKeyData)); -} - -static -int -_FindPosition(Tree * tree, TreeNode * node, const void * key, int * pos) -{ -#ifdef USE_BINARY_SEARCH - int low = 0; - int high = node->count; - int cmp = -1; - - while (high > low) - { - int cur = (high + low) >> 1; - cmp = tree->compareKey(key, node->keyData[cur].key); - if (cmp > 0) - { - low = cur+1; - } - else if (cmp < 0) - { - high = cur; - } - else - { - low = cur; - break; - } - } - - *pos = low; - return (cmp == 0); -#else - int i = 0; - int cmp = -1; - for (; - i < node->count && - (cmp = tree->compareKey(key, node->keyData[i].key)) > 0; - i++); - *pos = i; - return (cmp == 0); -#endif -} - -static -int -_Find(TreeIterator * iter, const void * key) -{ - while (1) - { - if (_FindPosition(iter->tree, iter->node, key, &iter->which)) - { - iter->which++; - return 1; - } - - if (iter->node->children[iter->which]) - { - iter->node = iter->node->children[iter->which]; - } - else - { - return 0; - } - } -} - -static void _SetIteratorToRoot(Tree * tree, TreeIterator * iter) -{ - iter->tree = tree; - iter->node = tree->rootNode; - iter->which = 0; -} - -static -TreeNode * -_SplitNode(TreeNode * node) -{ - TreeNode *newNode = _MakeNode(); - int i = DATA_PER_NODE/2; - int j = 0; - - assert(node->count == DATA_PER_NODE); - - for (; i < DATA_PER_NODE; i++, j++) - { - newNode->keyData[j] = node->keyData[i]; - newNode->children[j+1] = node->children[i+1]; - if (newNode->children[j+1]) - { - newNode->children[j+1]->parent = newNode; - newNode->children[j+1]->parentPos = j+1; - } - _ClearKeyData(&(node->keyData[i])); - node->children[i+1] = NULL; - } - newNode->count = (DATA_PER_NODE-DATA_PER_NODE/2); - node->count -= (DATA_PER_NODE-DATA_PER_NODE/2); - - return newNode; -} - -static -void -_InsertNodeAndData(TreeNode * node, - int pos, - TreeNode * newNode, - TreeKeyData keyData) -{ - int j = node->count; - - assert(node->count < DATA_PER_NODE); - - for (; j > pos; j--) - { - node->keyData[j] = node->keyData[j-1]; - node->children[j+1] = node->children[j]; - if (node->children[j+1]) - { - node->children[j+1]->parentPos = j+1; - } - } - - node->keyData[pos] = keyData; - node->count++; - - node->children[pos+1] = newNode; - if (newNode) - { - newNode->parent = node; - newNode->parentPos = pos+1; - } -} - -static -TreeKeyData -_AddDataToSplitNodes(TreeNode * lessNode, - TreeNode * moreNode, - int pos, - TreeNode * newNode, - TreeKeyData keyData) -{ - TreeKeyData retKeyData; - - assert(moreNode->children[0] == NULL); - - if (pos <= lessNode->count) - { - _InsertNodeAndData(lessNode, pos, newNode, keyData); - lessNode->count--; - retKeyData = lessNode->keyData[lessNode->count]; - _ClearKeyData(&(lessNode->keyData[lessNode->count])); - moreNode->children[0] = - lessNode->children[lessNode->count+1]; - if (moreNode->children[0]) - { - moreNode->children[0]->parent = moreNode; - moreNode->children[0]->parentPos = 0; - } - lessNode->children[lessNode->count+1] = NULL; - } - else - { - int j; - - pos -= lessNode->count; - retKeyData = moreNode->keyData[0]; - assert(!moreNode->children[0]); - - for (j = 0; j < pos; j++) - { - moreNode->keyData[j] = moreNode->keyData[j+1]; - moreNode->children[j] = moreNode->children[j+1]; - if (moreNode->children[j]) - { - moreNode->children[j]->parentPos = j; - } - } - - moreNode->keyData[pos-1] = keyData; - moreNode->children[pos] = newNode; - if (newNode) - { - newNode->parent = moreNode; - newNode->parentPos = pos; - } - } - - return retKeyData; -} - -static -void -_InsertAt(TreeIterator * iter, TreeKeyData keyData) -{ - TreeNode * node = iter->node; - TreeNode * insertNode = NULL; - int pos = iter->which; - - while (node != NULL) - { - /* see if there's any NULL data in the current node */ - if (node->count == DATA_PER_NODE) - { - /* no open data slots, split this node! */ - TreeNode * newNode = _SplitNode(node); - - /* insert data in split nodes */ - keyData = _AddDataToSplitNodes(node, - newNode, - pos, - insertNode, - keyData); - - if (node->parent == NULL) - { - assert(node == iter->tree->rootNode); - iter->tree->rootNode = _MakeNode(); - iter->tree->rootNode->children[0] = node; - node->parent = iter->tree->rootNode; - node->parentPos = 0; - iter->tree->rootNode->children[1] = newNode; - newNode->parent = iter->tree->rootNode; - newNode->parentPos = 1; - iter->tree->rootNode->keyData[0] = keyData; - iter->tree->rootNode->count = 1; - return; - } - - pos = node->parentPos; - node = node->parent; - insertNode = newNode; - } - else - { - /* insert the data and newNode */ - _InsertNodeAndData(node, - pos, - insertNode, - keyData); - return; - } - } -} - -static -void -_MergeNodes(TreeNode * lessNode, TreeNode * moreNode) -{ - int i = 0; - int j = lessNode->count; - - assert((lessNode->count + moreNode->count) <= DATA_PER_NODE); - assert(lessNode->children[j] == NULL); - - for(; i < moreNode->count; i++,j++) - { - assert(!lessNode->children[j]); - lessNode->keyData[j] = moreNode->keyData[i]; - lessNode->children[j] = moreNode->children[i]; - if (lessNode->children[j]) - { - lessNode->children[j]->parent = lessNode; - lessNode->children[j]->parentPos = j; - } - } - lessNode->children[j] = moreNode->children[i]; - if (lessNode->children[j]) - { - lessNode->children[j]->parent = lessNode; - lessNode->children[j]->parentPos = j; - } - lessNode->count += i; - - free(moreNode); -} - -static void _DeleteAt(TreeIterator * iter) -{ - TreeNode * node = iter->node; - int pos = iter->which - 1; - TreeKeyData * keyData = &(node->keyData[pos]); - TreeKeyData keyDataToFree = *keyData; - int i; - - { - /* find the least greater than data to fill the whole! */ - if (node->children[pos+1]) - { - TreeNode * child = node->children[++pos]; - while (child->children[0]) - { - pos = 0; - child = child->children[0]; - } - - *keyData = child->keyData[0]; - keyData = &(child->keyData[0]); - node = child; - } - /* or the greatest lesser than data to fill the whole! */ - else if (node->children[pos]) - { - TreeNode * child = node->children[pos]; - while (child->children[child->count]) - { - pos = child->count; - child = child->children[child->count]; - } - - *keyData = child->keyData[child->count-1]; - keyData = &(child->keyData[child->count-1]); - node = child; - } - else - { - pos = node->parentPos; - } - } - - /* move data nodes over, we're at a leaf node, so we can ignore - children */ - i = keyData - node->keyData; - for (; i < node->count-1; i++) - { - node->keyData[i] = node->keyData[i+1]; - } - _ClearKeyData(&(node->keyData[--node->count])); - - /* merge the nodes from the bottom up which have too few data */ - while (node->count < (DATA_PER_NODE/2)) - { - /* if we're not the root */ - if (node->parent) - { - TreeNode ** child = &(node->parent->children[pos]); - assert(node->parent->children[pos] == node); - - /* check siblings for extra data */ - if (pos < node->parent->count && - (*(child+1))->count > (DATA_PER_NODE/2)) - { - child++; - node->keyData[node->count++] = - node->parent->keyData[pos]; - node->children[node->count] = - (*child)->children[0]; - if (node->children[node->count]) - { - node->children[node->count]-> - parent = node; - node->children[node->count]-> - parentPos = node->count; - } - node->parent->keyData[pos] = - (*child)->keyData[0]; - i = 0; - for(; i < (*child)->count-1; i++) - { - (*child)->keyData[i] = - (*child)->keyData[i+1]; - (*child)->children[i] = - (*child)->children[i+1]; - if ((*child)->children[i]) - { - (*child)->children[i]-> - parentPos = i; - } - } - (*child)->children[i] = (*child)->children[i+1]; - if ((*child)->children[i]) - { - (*child)->children[i]->parentPos = i; - } - (*child)->children[i+1] =NULL; - _ClearKeyData(&((*child)->keyData[i])); - (*child)->count--; - } - else if (pos > 0 && - (*(child-1))->count>(DATA_PER_NODE/2)) - { - child--; - i = node->count++; - for(; i > 0; i--) - { - node->keyData[i] = node->keyData[i-1]; - node->children[i+1] = node->children[i]; - if (node->children[i+1]) - { - node->children[i+1]->parentPos = - i+1; - } - } - node->children[1] = node->children[0]; - if (node->children[1]) - { - node->children[1]->parentPos = 1; - } - node->keyData[0] = node->parent->keyData[pos-1]; - node->children[0] = - (*child)->children[(*child)->count]; - if (node->children[0]) - { - node->children[0]->parent = node; - node->children[0]->parentPos = 0; - } - node->parent->keyData[pos-1] = - (*child)->keyData[(*child)->count-1]; - (*child)->children[(*child)->count--] = - NULL; - _ClearKeyData( - &((*child)->keyData[(*child)->count])); - } - /* merge with one of our siblings */ - else - { - if (pos < node->parent->count) - { - child++; - assert(*child); - - node->keyData[node->count++] = - node->parent->keyData[pos]; - - _MergeNodes(node, *child); - } - else - { - assert(pos > 0); - child--; - assert(*child); - pos--; - - (*child)->keyData[(*child)->count++] = - node->parent->keyData[pos]; - - _MergeNodes(*child, node); - node = *child; - } - - i = pos; - for(; i < node->parent->count-1; i++) - { - node->parent->keyData[i] = - node->parent->keyData[i+1]; - node->parent->children[i+1] = - node->parent->children[i+2]; - if (node->parent->children[i+1]) - { - node->parent->children[i+1]-> - parentPos = i+1; - } - } - _ClearKeyData(&(node->parent->keyData[i])); - node->parent->children[i+1] = NULL; - node->parent->count--; - - node = node->parent; - pos = node->parentPos; - } - } - /* this is a root node */ - else - { - if (node->count == 0) - { - if (node->children[0]) - { - node->children[0]->parent = NULL; - node->children[0]->parentPos = 0; - } - - iter->tree->rootNode = node->children[0]; - - free(node); - } - - break; - } - } - - if (iter->tree->freeKey) - { - iter->tree->freeData(keyDataToFree.key); - } - if (iter->tree->freeData) - { - iter->tree->freeData(keyDataToFree.data); - } -} - -/************************* PUBLIC METHODS ***********************************/ - -Tree * -MakeTree(TreeCompareKeyFunction compareKey, - TreeFreeFunction freeKey, - TreeFreeFunction freeData) -{ - Tree * ret = xmalloc(sizeof(Tree)); - ret->compareKey = compareKey; - ret->freeKey = freeKey; - ret->freeData = freeData; - ret->rootNode = _MakeNode(); - ret->size = 0; - return ret; -} - -void -FreeTree(Tree * tree) -{ - assert(tree->rootNode == NULL); - free(tree); -} - -int -GetTreeSize(Tree * tree) -{ - return tree->size; -} - -void SetTreeIteratorToBegin(Tree * tree, TreeIterator * iter) -{ - _SetIteratorToRoot(tree, iter); - IncrementTreeIterator(iter); -} - -int IsTreeIteratorAtEnd(const TreeIterator * iter) -{ - return (iter->node == NULL); -} - -void IncrementTreeIterator(TreeIterator * iter) -{ - while(iter->node) - { - if (iter->node->children[iter->which]) - { - iter->node = iter->node->children[iter->which]; - iter->which = 0; - } - else - { - iter->which++; - } - - while (iter->node && iter->which > iter->node->count) - { - iter->which = iter->node->parentPos + 1; - iter->node = iter->node->parent; - } - - if (iter->node && - iter->which > 0 && iter->which <= iter->node->count) - { - return; - } - } -} - -const TreeKeyData * -GetTreeKeyData(TreeIterator * iter) -{ - assert(iter->node && - iter->which > 0 && - iter->which <= iter->node->count); - return &iter->node->keyData[iter->which-1]; -} - -int -InsertInTree(Tree * tree, void * key, void * data) -{ - TreeKeyData keyData; - TreeIterator iter; - - _SetIteratorToRoot(tree, &iter); - - if (_Find(&iter, key)) - { - return 0; - } - - keyData.key = key; - keyData.data = data; - _InsertAt(&iter, keyData); - tree->size++; - - return 1; -} - -int -RemoveFromTreeByKey(Tree * tree, void * key) -{ - TreeIterator iter; - _SetIteratorToRoot(tree, &iter); - - if (_Find(&iter, key)) - { - _DeleteAt(&iter); - tree->size--; - return 1; - } - - return 0; -} - -void -RemoveFromTreeByIterator(Tree * tree, TreeIterator * iter) -{ - _DeleteAt(iter); - tree->size--; -} - -int -FindInTree(Tree * tree, const void * key, TreeIterator * iter) -{ - TreeIterator i; - - if (iter == NULL) - { - iter = &i; - } - - _SetIteratorToRoot(tree, iter); - if (_Find(iter, key)) - { - return 1; - } - - return 0; -} diff --git a/src/tree.h b/src/tree.h deleted file mode 100644 index ef397bbd4..000000000 --- a/src/tree.h +++ /dev/null @@ -1,63 +0,0 @@ -/* the Music Player Daemon (MPD) - * Copyright (C) 2006-2007 by Warren Dukes (warren.dukes@gmail.com) - * This project's homepage is: http://www.musicpd.org - * - * This program is free software; you can redistribute it and/or modify - * it under the terms of the GNU General Public License as published by - * the Free Software Foundation; either version 2 of the License, or - * (at your option) any later version. - * - * This program is distributed in the hope that it will be useful, - * but WITHOUT ANY WARRANTY; without even the implied warranty of - * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the - * GNU General Public License for more details. - * You should have received a copy of the GNU General Public License - * along with this program; if not, write to the Free Software - * Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA - */ - -#ifndef TREE_H -#define TREE_H - -typedef struct _Tree Tree; -typedef struct _TreeNode TreeNode; -typedef struct _TreeIterator TreeIterator; -typedef struct _TreeKeyData TreeKeyData; - -struct _TreeIterator -{ - Tree * tree; - TreeNode * node; - int which; -}; - -struct _TreeKeyData -{ - void * key; - void * data; -}; - -typedef int (*TreeCompareKeyFunction)(const void * key1, const void * key2); -typedef void (*TreeFreeFunction)(void * data); - -Tree * MakeTree(TreeCompareKeyFunction compareFunc, - TreeFreeFunction freeKey, - TreeFreeFunction freeData); -void FreeTree(Tree * tree); - -int GetTreeSize(Tree * tree); - -void SetTreeIteratorToBegin(Tree * tree, TreeIterator * iter); -int IsTreeIteratorAtEnd(const TreeIterator * iter); -void IncrementTreeIterator(TreeIterator * iter); - -const TreeKeyData *GetTreeKeyData(TreeIterator * iter); - -int InsertInTree(Tree * tree, void * key, void * data); -int RemoveFromTreeByKey(Tree * tree, void * key); -void RemoveFromTreeByIterator(Tree * tree, TreeIterator * iter); - -int FindInTree(Tree * tree, const void * key, - TreeIterator * iter /* can be NULL */); - -#endif |