aboutsummaryrefslogtreecommitdiffstats
path: root/src/tree.c
diff options
context:
space:
mode:
Diffstat (limited to 'src/tree.c')
-rw-r--r--src/tree.c62
1 files changed, 34 insertions, 28 deletions
diff --git a/src/tree.c b/src/tree.c
index 9462d2a2c..d7eaf4428 100644
--- a/src/tree.c
+++ b/src/tree.c
@@ -57,7 +57,7 @@ struct _Tree
static
TreeNode *
-_MakeNode()
+_MakeNode(void)
{
TreeNode * ret = malloc(sizeof(TreeNode));
memset(ret, 0, sizeof(TreeNode));
@@ -147,12 +147,12 @@ static
TreeNode *
_SplitNode(TreeNode * node)
{
- assert(node->count == DATA_PER_NODE);
-
- TreeNode * newNode = _MakeNode();
-
+ 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];
@@ -179,9 +179,10 @@ _InsertNodeAndData(Tree * tree,
TreeNode * newNode,
TreeKeyData keyData)
{
+ int j = node->count;
+
assert(node->count < DATA_PER_NODE);
- int j = node->count;
for (; j > pos; j--)
{
node->keyData[j] = node->keyData[j-1];
@@ -212,10 +213,10 @@ _AddDataToSplitNodes(Tree * tree,
TreeNode * newNode,
TreeKeyData keyData)
{
- assert(moreNode->children[0] == NULL);
-
TreeKeyData retKeyData;
+ assert(moreNode->children[0] == NULL);
+
if (pos <= lessNode->count)
{
_InsertNodeAndData(tree, lessNode, pos, newNode, keyData);
@@ -233,12 +234,13 @@ _AddDataToSplitNodes(Tree * tree,
}
else
{
+ int j;
+
pos -= lessNode->count;
retKeyData = moreNode->keyData[0];
assert(!moreNode->children[0]);
- int j = 0;
- for (; j < pos; j++)
+ for (j = 0; j < pos; j++)
{
moreNode->keyData[j] = moreNode->keyData[j+1];
moreNode->children[j] = moreNode->children[j+1];
@@ -270,13 +272,13 @@ _InsertAt(TreeIterator * iter, TreeKeyData keyData)
while (node != NULL)
{
- // see if there's any NULL data in the current node
+ /* see if there's any NULL data in the current node */
if (node->count == DATA_PER_NODE)
{
- // no open data slots, split this node!
+ /* no open data slots, split this node! */
TreeNode * newNode = _SplitNode(node);
- // insert data in split nodes
+ /* insert data in split nodes */
keyData = _AddDataToSplitNodes(iter->tree,
node,
newNode,
@@ -305,7 +307,7 @@ _InsertAt(TreeIterator * iter, TreeKeyData keyData)
}
else
{
- // insert the data and newNode
+ /* insert the data and newNode */
_InsertNodeAndData(iter->tree,
node,
pos,
@@ -355,9 +357,10 @@ _DeleteAt(TreeIterator * iter)
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!
+ /* find the least greater than data to fill the whole! */
if (node->children[pos+1])
{
TreeNode * child = node->children[++pos];
@@ -371,7 +374,7 @@ _DeleteAt(TreeIterator * iter)
keyData = &(child->keyData[0]);
node = child;
}
- // or the greatest lesser than data to fill the whole!
+ /* or the greatest lesser than data to fill the whole! */
else if (node->children[pos])
{
TreeNode * child = node->children[pos];
@@ -391,25 +394,25 @@ _DeleteAt(TreeIterator * iter)
}
}
- // move data nodes over, we're at a leaf node, so we can ignore
- // children
- int i = keyData - node->keyData;;
+ /* 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
+ /* 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 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
+ /* check siblings for extra data */
if (pos < node->parent->count &&
(*(child+1))->count > (DATA_PER_NODE/2))
{
@@ -427,7 +430,7 @@ _DeleteAt(TreeIterator * iter)
}
node->parent->keyData[pos] =
(*child)->keyData[0];
- int i = 0;
+ i = 0;
for(; i < (*child)->count-1; i++)
{
(*child)->keyData[i] =
@@ -453,7 +456,7 @@ _DeleteAt(TreeIterator * iter)
(*(child-1))->count>(DATA_PER_NODE/2))
{
child--;
- int i = node->count++;
+ i = node->count++;
for(; i > 0; i--)
{
node->keyData[i] = node->keyData[i-1];
@@ -484,7 +487,7 @@ _DeleteAt(TreeIterator * iter)
_ClearKeyData(
&((*child)->keyData[(*child)->count]));
}
- // merge with one of our siblings
+ /* merge with one of our siblings */
else
{
if (pos < node->parent->count)
@@ -511,7 +514,7 @@ _DeleteAt(TreeIterator * iter)
node = *child;
}
- int i = pos;
+ i = pos;
for(; i < node->parent->count-1; i++)
{
node->parent->keyData[i] =
@@ -532,7 +535,7 @@ _DeleteAt(TreeIterator * iter)
pos = node->parentPos;
}
}
- // this is a root node
+ /* this is a root node */
else
{
if (node->count == 0)
@@ -654,8 +657,9 @@ GetTreeKeyData(TreeIterator * iter)
int
InsertInTree(Tree * tree, void * key, void * data)
{
- TreeKeyData keyData = {key, data};
+ TreeKeyData keyData;
TreeIterator iter;
+
_SetIteratorToRoot(tree, &iter);
if (_Find(&iter, key))
@@ -663,6 +667,8 @@ InsertInTree(Tree * tree, void * key, void * data)
return 0;
}
+ keyData.key = key;
+ keyData.data = data;
_InsertAt(&iter, keyData);
tree->size++;