aboutsummaryrefslogtreecommitdiffstats
diff options
context:
space:
mode:
Diffstat
-rw-r--r--src/Makefile.am2
-rw-r--r--src/tagTracker.c160
-rw-r--r--src/tree.c699
-rw-r--r--src/tree.h63
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
generated by cgit v1.2.3 (git 2.25.1) at 2024-07-03 14:29:41 +0000