From 03fdf503f41edfcc1c4f710fefa8d0955d06b668 Mon Sep 17 00:00:00 2001 From: Warren Dukes Date: Mon, 31 Jul 2006 06:54:49 +0000 Subject: some tree bugfixes git-svn-id: https://svn.musicpd.org/mpd/trunk@4498 09075e82-0dd4-0310-85a5-a0d7c8717e4f --- src/tree.c | 115 +++++++++++++++++++++++++++++++++++++++++-------------------- 1 file changed, 78 insertions(+), 37 deletions(-) (limited to 'src') diff --git a/src/tree.c b/src/tree.c index d1f07f74b..5006e5362 100644 --- a/src/tree.c +++ b/src/tree.c @@ -231,6 +231,7 @@ _AddDataToSplitNodes(Tree * tree, { assert(newNode == NULL || tree->compareData(data, newNode->data[0]) < 0); + assert(moreNode->children[0] == NULL); void * retData; @@ -240,6 +241,13 @@ _AddDataToSplitNodes(Tree * tree, 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; + } + lessNode->children[lessNode->dataCount+1] = NULL; } else { @@ -350,18 +358,25 @@ _MergeNodes(TreeNode * lessNode, TreeNode * moreNode) 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]; - lessNode->children[j]->parent = lessNode; + if (lessNode->children[j]) + { + lessNode->children[j]->parent = lessNode; + } } lessNode->children[j] = moreNode->children[i]; - lessNode->children[j]->parent = lessNode; - lessNode->dataCount = j; + if (lessNode->children[j]) + { + lessNode->children[j]->parent = lessNode; + } + lessNode->dataCount += i; free(moreNode); } -static void _DeleteAt(TreeIterator * iter) { @@ -369,47 +384,57 @@ _DeleteAt(TreeIterator * iter) void ** data = &(node->data[iter->which]); void * dataToFree = *data; - // perculate up data to fill the whole! - while (1) { - TreeNode ** child = &(node->children[iter->which+1]); - void ** childData = NULL; + int dir = 0; + TreeNode * child = NULL; - if (*child) + // find the least greater than data to fill the whole! + if (node->children[iter->which+1]) { - assert((*child)->dataCount); - childData = &((*child)->data[0]); + dir = -1; + child = node->children[iter->which+1]; } - else if (*(--child)) + // or the greatest lesser than data to fill the whole! + else if (node->children[iter->which]) { - assert((*child)->dataCount); - childData = &((*child)->data[(*child)->dataCount-1]); + dir = 1; + child = node->children[iter->which]; } - else + + if (dir > 0) { - // no children! - break; - } + while (child->children[child->dataCount]) + { + child = child->children[child->dataCount]; + } - // move childData up to parent node - *data = *childData; + *data = child->data[child->dataCount-1]; + data = &(child->data[child->dataCount-1]); + node = child; + } + else if (dir < 0) + { + while (child->children[0]) + { + child = child->children[0]; + } - // set data and node for next iteration - data = childData; - node = *child; + *data = child->data[0]; + data = &(child->data[0]); + node = child; + } } void * tempData = *data; // move data nodes over, we're at a leaf node, so we can ignore // children - void ** leftData = node->data[node->dataCount-1]; - while (data != leftData) + int i = --node->dataCount; + for (; data != &(node->data[i]); i--) { - *(leftData-1) = *leftData; - leftData--; + node->data[i-1] = node->data[i]; } - node->data[--(node->dataCount)] = NULL; + node->data[node->dataCount] = NULL; // merge the nodes from the bottom up which have too few data while (node->dataCount < (CHILDREN_PER_NODE/2)) @@ -419,10 +444,16 @@ _DeleteAt(TreeIterator * iter) { TreeNode ** child; int pos; - _FindPositionInNode(iter->tree, - node->parent, - tempData, - &pos); + if (_FindPositionInNode(iter->tree, + node->parent, + tempData, + &pos)) + { + if (node->parent->children[pos] != node) + { + pos++; + } + } assert(node->parent->children[pos] == node); child = &(node->parent->children[pos]); @@ -435,7 +466,11 @@ _DeleteAt(TreeIterator * iter) node->parent->data[pos]; node->children[node->dataCount] = (*child)->children[0]; - node->children[node->dataCount]->parent = node; + if (node->children[node->dataCount]) + { + node->children[node->dataCount]-> + parent = node; + } node->parent->data[pos] = (*child)->data[0]; int i = 0; @@ -461,20 +496,23 @@ _DeleteAt(TreeIterator * iter) node->data[0] = node->parent->data[pos-1]; node->children[0] = (*child)->children[(*child)->dataCount]; - node->children[0]->parent = node; + if (node->children[0]) + { + node->children[0]->parent = node; + } node->parent->data[pos-1] = (*child)->data[(*child)->dataCount-1]; - (*child)->children[(*child)->dataCount--] =NULL; + (*child)->children[(*child)->dataCount--] = + NULL; (*child)->data[(*child)->dataCount] = NULL; } else { // merge with one of our siblings - if(pos < node->parent->dataCount-1) + if (pos < node->parent->dataCount) { child++; assert(*child); - pos--; tempData = node->parent->data[pos]; node->data[node->dataCount++] = @@ -487,12 +525,14 @@ _DeleteAt(TreeIterator * iter) assert(pos > 0); child--; assert(*child); + pos--; tempData = node->parent->data[pos]; (*child)->data[(*child)->dataCount++] = tempData; _MergeNodes(*child, node); + node = *child; } int i = pos; @@ -505,6 +545,7 @@ _DeleteAt(TreeIterator * iter) } node->parent->data[i] = NULL; node->parent->children[i+1] = NULL; + node->parent->dataCount--; node = node->parent; } -- cgit v1.2.3