aboutsummaryrefslogtreecommitdiffstats
path: root/src/tree.c
diff options
context:
space:
mode:
Diffstat (limited to '')
-rw-r--r--src/tree.c673
1 files changed, 0 insertions, 673 deletions
diff --git a/src/tree.c b/src/tree.c
deleted file mode 100644
index f5a804a92..000000000
--- a/src/tree.c
+++ /dev/null
@@ -1,673 +0,0 @@
-/* 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 3
-#endif
-
-#define DATA_PER_NODE (CHILDREN_PER_NODE-1)
-
-#if CHILDREN_PER_NODE > 7
-#define USE_BINARY_SEARCH 1
-#endif
-
-
-/************************* DATA STRUCTURES **********************************/
-
-struct _TreeNode
-{
- void * data[DATA_PER_NODE];
- struct _TreeNode * parent;
- short parentPos;
- struct _TreeNode * children[CHILDREN_PER_NODE];
- short dataCount;
-};
-
-struct _Tree
-{
- TreeCompareDataFunction compareData;
- TreeFreeDataFunction freeData;
- TreeNode * rootNode;
-};
-
-/************************* STATIC METHODS ***********************************/
-
-static
-TreeNode *
-_MakeNode()
-{
- TreeNode * ret = malloc(sizeof(TreeNode));
- memset(ret, 0, sizeof(TreeNode));
- return ret;
-}
-
-static
-int
-_FindPosition(Tree * tree, TreeNode * node, void * data, int * pos)
-{
-#ifdef USE_BINARY_SEARCH
- int low = 0;
- int high = node->dataCount;
- int cmp = -1;
-
- while (high > low)
- {
- int cur = (high + low) >> 1;
- cmp = tree->compareData(data, node->data[cur]);
- 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->dataCount &&
- (cmp = tree->compareData(data, node->data[i])) > 0;
- i++);
- *pos = i;
- return (cmp == 0);
-#endif
-}
-
-static
-int
-_Find(TreeIterator * iter, void * data)
-{
- while (1)
- {
- if (_FindPosition(iter->tree, iter->node, data, &iter->which))
- {
- return 1;
- }
-
- if (iter->node->children[iter->which])
- {
- iter->node = iter->node->children[iter->which];
- }
- else
- {
- return 0;
- }
- }
-}
-
-static void _SetTreeIteratorToRoot(TreeIterator * iter, Tree * tree)
-{
- iter->tree = tree;
- iter->node = tree->rootNode;
- iter->which = 0;
-}
-
-static
-TreeNode *
-_SplitNode(TreeNode * node)
-{
- assert(node->dataCount == DATA_PER_NODE);
-
- TreeNode * newNode = _MakeNode();
-
- int i = DATA_PER_NODE/2;
- int j = 0;
- for (; i < DATA_PER_NODE; i++, j++)
- {
- newNode->data[j] = node->data[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;
- }
- node->data[i] = NULL;
- node->children[i+1] = NULL;
- }
- newNode->dataCount = (DATA_PER_NODE-DATA_PER_NODE/2);
- node->dataCount -= (DATA_PER_NODE-DATA_PER_NODE/2);
-
- return newNode;
-}
-
-static
-void
-_InsertNodeAndData(Tree * tree,
- TreeNode * node,
- int pos,
- TreeNode * newNode,
- void * data)
-{
- assert(node->dataCount < DATA_PER_NODE);
-#ifdef TREE_DEBUG
- assert(!newNode || tree->compareData(data, newNode->data[0]) < 0);
-#endif
-
- int j = node->dataCount;
- for (; j > pos; j--)
- {
- node->data[j] = node->data[j-1];
- node->children[j+1] = node->children[j];
- if (node->children[j+1])
- {
- node->children[j+1]->parentPos = j+1;
- }
- }
-
-#ifdef TREE_DEBUG
- assert(!node->children[pos] ||
- tree->compareData(data, node->children[pos]->data[0]) > 0);
-#endif
-
- node->data[pos] = data;
- node->dataCount++;
-
- node->children[pos+1] = newNode;
- if (newNode)
- {
- newNode->parent = node;
- newNode->parentPos = pos+1;
- }
-}
-
-static
-void *
-_AddDataToSplitNodes(Tree * tree,
- TreeNode * lessNode,
- TreeNode * moreNode,
- int pos,
- TreeNode * newNode,
- void * data)
-{
-#ifdef TREE_DEBUG
- assert(newNode == NULL ||
- tree->compareData(data, newNode->data[0]) < 0);
-#endif
- assert(moreNode->children[0] == NULL);
-
- void * retData;
-
- if (pos <= lessNode->dataCount)
- {
- _InsertNodeAndData(tree, lessNode, pos, newNode, data);
- lessNode->dataCount--;
- retData = lessNode->data[lessNode->dataCount];
- lessNode->data[lessNode->dataCount] = NULL;
- moreNode->children[0] =
- lessNode->children[lessNode->dataCount+1];
- if (moreNode->children[0])
- {
- moreNode->children[0]->parent = moreNode;
- moreNode->children[0]->parentPos = 0;
- }
- lessNode->children[lessNode->dataCount+1] = NULL;
- }
- else
- {
- pos -= lessNode->dataCount;
- retData = moreNode->data[0];
- assert(!moreNode->children[0]);
- assert(!moreNode->data[moreNode->dataCount]);
-
- int j = 0;
- for (; j < pos; j++)
- {
- moreNode->data[j] = moreNode->data[j+1];
- moreNode->children[j] = moreNode->children[j+1];
- if (moreNode->children[j])
- {
- moreNode->children[j]->parentPos = j;
- }
- }
-
- assert(!moreNode->children[pos-1] ||
- tree->compareData(data,
- moreNode->children[pos-1]->data[0]) > 0);
-
- moreNode->data[pos-1] = data;
- moreNode->children[pos] = newNode;
- if (newNode)
- {
- newNode->parent = moreNode;
- newNode->parentPos = pos;
- }
- }
-
- return retData;
-}
-
-static
-void
-_InsertAt(TreeIterator * iter, void * data)
-{
- TreeNode * node = iter->node;
- TreeNode * insertNode = NULL;
- int pos = iter->which;
-
- while (node != NULL)
- {
-#ifdef TREE_DEBUG
- assert((pos == node->dataCount ||
- iter->tree->compareData(data, node->data[pos]) < 0));
-#endif
-
- // see if there's any NULL data in the current node
- if (node->dataCount == DATA_PER_NODE)
- {
- // no open data slots, split this node!
- TreeNode * newNode = _SplitNode(node);
-
- // insert data in split nodes
- data = _AddDataToSplitNodes(iter->tree,
- node,
- newNode,
- pos,
- insertNode,
- data);
-
- 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->data[0] = data;
- iter->tree->rootNode->dataCount = 1;
- return;
- }
-
- pos = node->parentPos;
- node = node->parent;
- insertNode = newNode;
- }
- else
- {
- // insert the data and newNode
- _InsertNodeAndData(iter->tree,
- node,
- pos,
- insertNode,
- data);
- return;
- }
- }
-}
-
-static
-void
-_MergeNodes(TreeNode * lessNode, TreeNode * moreNode)
-{
- int i = 0;
- int j = lessNode->dataCount;
-
- assert((lessNode->dataCount + moreNode->dataCount) <= DATA_PER_NODE);
- assert(lessNode->children[j] == NULL);
-
- for(; i < moreNode->dataCount; i++,j++)
- {
- assert(!lessNode->children[j]);
- assert(!lessNode->data[j]);
- lessNode->data[j] = moreNode->data[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->dataCount += i;
-
- free(moreNode);
-}
-
-void
-_DeleteAt(TreeIterator * iter)
-{
- TreeNode * node = iter->node;
- int pos = iter->which;
- void ** data = &(node->data[pos]);
- void * dataToFree = *data;
-
- {
- // 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];
- }
-
- *data = child->data[0];
- data = &(child->data[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->dataCount])
- {
- pos = child->dataCount;
- child = child->children[child->dataCount];
- }
-
- *data = child->data[child->dataCount-1];
- data = &(child->data[child->dataCount-1]);
- node = child;
- }
- else
- {
- pos = node->parentPos;
- }
- }
-
- // move data nodes over, we're at a leaf node, so we can ignore
- // children
- int i = data - node->data;;
- for (; i < node->dataCount-1; i++)
- {
- node->data[i] = node->data[i+1];
- }
- node->data[--node->dataCount] = NULL;
-
- // merge the nodes from the bottom up which have too few data
- while (node->dataCount < (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->dataCount &&
- (*(child+1))->dataCount > (DATA_PER_NODE/2))
- {
- child++;
- node->data[node->dataCount++] =
- node->parent->data[pos];
- node->children[node->dataCount] =
- (*child)->children[0];
- if (node->children[node->dataCount])
- {
- node->children[node->dataCount]->
- parent = node;
- node->children[node->dataCount]->
- parentPos = node->dataCount;
- }
- node->parent->data[pos] =
- (*child)->data[0];
- int i = 0;
- for(; i < (*child)->dataCount-1; i++)
- {
- (*child)->data[i] = (*child)->data[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;
- (*child)->data[i] = NULL;
- (*child)->dataCount--;
- }
- else if (pos > 0 &&
- (*(child-1))->dataCount>(DATA_PER_NODE/2))
- {
- child--;
- int i = node->dataCount++;
- for(; i > 0; i--)
- {
- node->data[i] = node->data[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->data[0] = node->parent->data[pos-1];
- node->children[0] =
- (*child)->children[(*child)->dataCount];
- if (node->children[0])
- {
- node->children[0]->parent = node;
- node->children[0]->parentPos = 0;
- }
- node->parent->data[pos-1] =
- (*child)->data[(*child)->dataCount-1];
- (*child)->children[(*child)->dataCount--] =
- NULL;
- (*child)->data[(*child)->dataCount] = NULL;
- }
- // merge with one of our siblings
- else
- {
- if (pos < node->parent->dataCount)
- {
- child++;
- assert(*child);
-
- node->data[node->dataCount++] =
- node->parent->data[pos];
-
- _MergeNodes(node, *child);
- }
- else
- {
- assert(pos > 0);
- child--;
- assert(*child);
- pos--;
-
- (*child)->data[(*child)->dataCount++] =
- node->parent->data[pos];
-
- _MergeNodes(*child, node);
- node = *child;
- }
-
- int i = pos;
- for(; i < node->parent->dataCount-1; i++)
- {
- node->parent->data[i] =
- node->parent->data[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;
- }
- }
- node->parent->data[i] = NULL;
- node->parent->children[i+1] = NULL;
- node->parent->dataCount--;
-
- node = node->parent;
- pos = node->parentPos;
- }
- }
- // this is a root node
- else
- {
- if (node->dataCount == 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->freeData)
- {
- iter->tree->freeData(dataToFree);
- }
-}
-
-/************************* PUBLIC METHODS ***********************************/
-
-Tree *
-MakeTree(TreeCompareDataFunction compareData, TreeFreeDataFunction freeData)
-{
- Tree * ret = malloc(sizeof(Tree));
- ret->compareData = compareData;
- ret->freeData = freeData;
- ret->rootNode = _MakeNode();
- return ret;
-}
-
-void SetTreeIteratorToBegin(TreeIterator * iter, Tree * tree)
-{
- _SetTreeIteratorToRoot(iter, tree);
- 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->dataCount)
- {
- 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->dataCount);
- }
- iter->which++;
- }
- }
-
- if (iter->node &&
- iter->which > 0 && iter->which <= iter->node->dataCount)
- {
- return;
- }
- }
-}
-
-void *
-GetDataFromTreeIterator(TreeIterator * iter)
-{
- assert(iter->node &&
- iter->which > 0 &&
- iter->which <= iter->node->dataCount);
- return iter->node->data[iter->which-1];
-}
-
-int
-InsertIntoTree(Tree * tree, void * data)
-{
- TreeIterator iter;
- _SetTreeIteratorToRoot(&iter, tree);
-
- if (_Find(&iter, data))
- {
- return 0;
- }
-
- _InsertAt(&iter, data);
-
- return 1;
-}
-
-int
-DeleteFromTree(Tree * tree, void * data)
-{
- TreeIterator iter;
- _SetTreeIteratorToRoot(&iter, tree);
-
- if (_Find(&iter, data))
- {
- _DeleteAt(&iter);
- return 1;
- }
-
- return 0;
-}
generated by cgit v1.2.3 (git 2.25.1) at 2024-11-11 05:23:09 +0000