aboutsummaryrefslogtreecommitdiffstats
path: root/src/tree.c
diff options
context:
space:
mode:
Diffstat (limited to 'src/tree.c')
-rw-r--r--src/tree.c712
1 files changed, 712 insertions, 0 deletions
diff --git a/src/tree.c b/src/tree.c
new file mode 100644
index 000000000..9462d2a2c
--- /dev/null
+++ b/src/tree.c
@@ -0,0 +1,712 @@
+/* the Music Player Daemon (MPD)
+ * (c)2006 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 <assert.h>
+#include <stdlib.h>
+#include <string.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()
+{
+ TreeNode * ret = malloc(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, 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, 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)
+{
+ assert(node->count == DATA_PER_NODE);
+
+ TreeNode * newNode = _MakeNode();
+
+ int i = DATA_PER_NODE/2;
+ int j = 0;
+ 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(Tree * tree,
+ TreeNode * node,
+ int pos,
+ TreeNode * newNode,
+ TreeKeyData keyData)
+{
+ assert(node->count < DATA_PER_NODE);
+
+ int j = node->count;
+ 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(Tree * tree,
+ TreeNode * lessNode,
+ TreeNode * moreNode,
+ int pos,
+ TreeNode * newNode,
+ TreeKeyData keyData)
+{
+ assert(moreNode->children[0] == NULL);
+
+ TreeKeyData retKeyData;
+
+ if (pos <= lessNode->count)
+ {
+ _InsertNodeAndData(tree, 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
+ {
+ pos -= lessNode->count;
+ retKeyData = moreNode->keyData[0];
+ assert(!moreNode->children[0]);
+
+ int j = 0;
+ for (; 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(iter->tree,
+ 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(iter->tree,
+ 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);
+}
+
+void
+_DeleteAt(TreeIterator * iter)
+{
+ TreeNode * node = iter->node;
+ int pos = iter->which - 1;
+ TreeKeyData * keyData = &(node->keyData[pos]);
+ TreeKeyData keyDataToFree = *keyData;
+
+ {
+ // 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
+ int 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];
+ int 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--;
+ int 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;
+ }
+
+ int 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 = malloc(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)
+ {
+ TreeNode * childNode = iter->node;
+ iter->node = childNode->parent;
+ if (iter->node)
+ {
+ for (iter->which = 0;
+ childNode !=
+ iter->node->children[iter->which];
+ iter->which++)
+ {
+ assert(iter->which <=
+ iter->node->count);
+ }
+ iter->which++;
+ }
+ }
+
+ if (iter->node &&
+ iter->which > 0 && iter->which <= iter->node->count)
+ {
+ return;
+ }
+ }
+}
+
+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 = {key, data};
+ TreeIterator iter;
+ _SetIteratorToRoot(tree, &iter);
+
+ if (_Find(&iter, key))
+ {
+ return 0;
+ }
+
+ _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, void * key, TreeIterator * iter)
+{
+ TreeIterator i;
+
+ if (iter == NULL)
+ {
+ iter = &i;
+ }
+
+ _SetIteratorToRoot(tree, iter);
+ if (_Find(iter, key))
+ {
+ return 1;
+ }
+
+ return 0;
+}
generated by cgit v1.2.3 (git 2.25.1) at 2024-11-02 03:33:45 +0000