aboutsummaryrefslogtreecommitdiff
diff options
context:
space:
mode:
Diffstat
-rw-r--r--src/tree.c253
-rw-r--r--src/tree.h41
2 files changed, 221 insertions, 73 deletions
diff --git a/src/tree.c b/src/tree.c
index 0696f4b1..58e8a221 100644
--- a/src/tree.c
+++ b/src/tree.c
@@ -5,6 +5,36 @@
#include <string.h>
#include <stdio.h>
+#ifndef CHILDREN_PER_NODE
+#define CHILDREN_PER_NODE 3
+#endif
+
+#define DATA_PER_NODE (CHILDREN_PER_NODE-1)
+
+#if CHILDREN_PER_NODE > 11
+#define USE_BINARY_SEARCH 1
+#endif
+
+
+/************************* DATA STRUCTURES **********************************/
+
+struct _TreeNode
+{
+ void * data[DATA_PER_NODE];
+ struct _TreeNode * parent;
+ struct _TreeNode * children[CHILDREN_PER_NODE];
+ int dataCount;
+};
+
+struct _Tree
+{
+ TreeCompareDataFunction compareData;
+ TreeFreeDataFunction freeData;
+ TreeNode * rootNode;
+};
+
+/************************* STATIC METHODS ***********************************/
+
static
TreeNode *
_MakeNode()
@@ -16,31 +46,63 @@ _MakeNode()
static
int
+_FindPositionInNode(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)
{
- for (; iter->which < iter->node->dataCount; iter->which++)
+ if (_FindPositionInNode(iter->tree,
+ iter->node,
+ data,
+ &iter->which))
{
- int comp = iter->tree->
- compareData(data,iter->node->data[iter->which]);
-
- if (comp == 0)
- {
- return 1;
- }
- else if (comp < 0)
- {
- break;
- }
+ return 1;
}
- assert(iter->which < CHILDREN_PER_NODE);
-
if (iter->node->children[iter->which])
{
iter->node = iter->node->children[iter->which];
- iter->which = 0;
}
else
{
@@ -49,16 +111,6 @@ _Find(TreeIterator * iter, void * data)
}
}
-Tree *
-MakeTree(TreeCompareDataFunction compareData, TreeFreeDataFunction freeData)
-{
- Tree * ret = malloc(sizeof(Tree));
- ret->compareData = compareData;
- ret->freeData = freeData;
- ret->rootNode = _MakeNode();
- return ret;
-}
-
static
TreeNode *
_SplitNode(TreeNode * node)
@@ -67,21 +119,38 @@ _SplitNode(TreeNode * node)
TreeNode * newNode = _MakeNode();
- unsigned i = DATA_PER_NODE/2;
- unsigned j = 0;
+#ifdef USE_MEM_FUNC
+ memcpy(&(newNode->data[0]),
+ &(node->data[DATA_PER_NODE/2]),
+ (DATA_PER_NODE-DATA_PER_NODE/2)*sizeof(void *));
+ memset(&(node->data[DATA_PER_NODE/2]),
+ 0,
+ (DATA_PER_NODE-DATA_PER_NODE/2)*sizeof(void *));
+ memcpy(&(newNode->children[1]),
+ &(node->children[DATA_PER_NODE/2+1]),
+ (DATA_PER_NODE-DATA_PER_NODE/2)*sizeof(TreeNode *));
+ memset(&(node->children[DATA_PER_NODE/2+1]),
+ 0,
+ (DATA_PER_NODE-DATA_PER_NODE/2)*sizeof(TreeNode *));
+#endif
+
+ int i = DATA_PER_NODE/2;
+ int j = 0;
for (; i < DATA_PER_NODE; i++, j++)
{
+#ifndef USE_MEM_FUNC
newNode->data[j] = node->data[i];
newNode->children[j+1] = node->children[i+1];
+ node->data[i] = NULL;
+ node->children[i+1] = NULL;
+#endif
if (newNode->children[j+1])
{
newNode->children[j+1]->parent = newNode;
}
- node->data[i] = NULL;
- node->children[i+1] = NULL;
}
- newNode->dataCount = j;
- node->dataCount -= j;
+ newNode->dataCount = (DATA_PER_NODE-DATA_PER_NODE/2);
+ node->dataCount -= (DATA_PER_NODE-DATA_PER_NODE/2);
return newNode;
}
@@ -102,23 +171,29 @@ _InsertNodeAndData(Tree * tree,
}
int i = 0;
- for (;
- i < node->dataCount &&
- tree->compareData(data, node->data[i]) > 0;
- i++);
-
+ _FindPositionInNode(tree, node, data, &i);
+
+#ifdef USE_MEM_FUNC
+ memmove(&(node->data[i+1]),
+ &(node->data[i]),
+ (node->dataCount-i)*sizeof(void *));
+ memmove(&(node->children[i+2]),
+ &(node->children[i+1]),
+ (node->dataCount-i)*sizeof(TreeNode *));
+#else
int j = node->dataCount;
for (; j > i; j--)
{
node->data[j] = node->data[j-1];
node->children[j+1] = node->children[j];
}
+#endif
- assert(!node->children[j] ||
- tree->compareData(data, node->children[j]->data[0]) > 0);
+ assert(!node->children[i] ||
+ tree->compareData(data, node->children[i]->data[0]) > 0);
- node->data[j] = data;
- node->children[j+1] = newNode;
+ node->data[i] = data;
+ node->children[i+1] = newNode;
node->dataCount++;
}
@@ -150,10 +225,7 @@ _AddDataToSplitNodes(Tree * tree,
}
int i = 0;
- for (;
- i < moreNode->dataCount &&
- tree->compareData(data, moreNode->data[i]) > 0;
- i++);
+ _FindPositionInNode(tree, moreNode, data, &i);
if (i == 0)
{
@@ -165,19 +237,28 @@ _AddDataToSplitNodes(Tree * tree,
retData = moreNode->data[0];
}
+#ifdef USE_MEM_FUNC
+ memmove(&(moreNode->data[0]),
+ &(moreNode->data[1]),
+ i*sizeof(void *));
+ memmove(&(moreNode->children[0]),
+ &(moreNode->children[1]),
+ i*sizeof(TreeNode *));
+#else
int j = 0;
for (; j < i; j++)
{
moreNode->data[j] = moreNode->data[j+1];
moreNode->children[j] = moreNode->children[j+1];
}
+#endif
- assert(!moreNode->children[j-1] ||
+ assert(!moreNode->children[i-1] ||
tree->compareData(data,
- moreNode->children[j]->data[0]) > 0);
+ moreNode->children[i]->data[0]) > 0);
- moreNode->data[j-1] = data;
- moreNode->children[j] = newNode;
+ moreNode->data[i-1] = data;
+ moreNode->children[i] = newNode;
}
return retData;
@@ -236,18 +317,90 @@ _InsertAt(TreeIterator * iter, void * data)
return;
}
-void SetIteratorToBegin(TreeIterator * iter, Tree * tree)
+static void _SetTreeIteratorToRoot(TreeIterator * iter, Tree * tree)
{
iter->tree = tree;
iter->node = tree->rootNode;
iter->which = 0;
}
+/************************* 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;
- SetIteratorToBegin(&iter, tree);
+ _SetTreeIteratorToRoot(&iter, tree);
if (_Find(&iter, data))
{
diff --git a/src/tree.h b/src/tree.h
index 737f914d..c47b1514 100644
--- a/src/tree.h
+++ b/src/tree.h
@@ -1,36 +1,31 @@
-#define CHILDREN_PER_NODE 3
-#define DATA_PER_NODE 2
+#ifndef TREE_H
+#define TREE_H
-typedef struct _TreeNode
-{
- void * data[DATA_PER_NODE];
- struct _TreeNode * parent;
- struct _TreeNode * children[CHILDREN_PER_NODE];
- unsigned dataCount;
-} TreeNode;
-
-typedef int (*TreeCompareDataFunction)(void * data1, void * data2);
-typedef void (*TreeFreeDataFunction)(void * data);
-
-typedef struct _Tree
-{
- TreeCompareDataFunction compareData;
- TreeFreeDataFunction freeData;
- TreeNode * rootNode;
-} Tree;
+typedef struct _Tree Tree;
+typedef struct _TreeNode TreeNode;
+typedef struct _TreeIterator TreeIterator;
-typedef struct _TreeIterator
+struct _TreeIterator
{
Tree * tree;
TreeNode * node;
- unsigned which;
-} TreeIterator;
+ int which;
+};
+
+typedef int (*TreeCompareDataFunction)(const void * data1, const void * data2);
+typedef void (*TreeFreeDataFunction)(void * data);
Tree * MakeTree(TreeCompareDataFunction compareFunc,
TreeFreeDataFunction freeData);
-void SetIteratorToBegin(TreeIterator * iter, Tree * tree);
+void SetTreeIteratorToBegin(TreeIterator * iter, Tree * tree);
+int IsTreeIteratorAtEnd(const TreeIterator * iter);
+void IncrementTreeIterator(TreeIterator * iter);
+
+void * GetDataFromTreeIterator(TreeIterator * iter);
int InsertIntoTree(Tree * tree, void * data);
void DeleteFromTree(Tree * tree, void * data);
+
+#endif
generated by cgit v1.2.3 (git 2.39.1) at 2024-07-02 13:56:39 +0000