From 71fe871908db4317e5afd4308a044909a1799c9e Mon Sep 17 00:00:00 2001 From: Warren Dukes Date: Sun, 30 Jul 2006 18:43:13 +0000 Subject: tree updates: *) when CHILDREN_PER_NODE is large, use binary search *) add a iterator implementation *) some code cleanup git-svn-id: https://svn.musicpd.org/mpd/trunk@4492 09075e82-0dd4-0310-85a5-a0d7c8717e4f --- src/tree.c | 253 +++++++++++++++++++++++++++++++++++++++++++++++++------------ src/tree.h | 41 +++++----- 2 files changed, 221 insertions(+), 73 deletions(-) diff --git a/src/tree.c b/src/tree.c index 0696f4b13..58e8a221f 100644 --- a/src/tree.c +++ b/src/tree.c @@ -5,6 +5,36 @@ #include #include +#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() @@ -14,33 +44,65 @@ _MakeNode() return ret; } +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 737f914d2..c47b15144 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 -- cgit v1.2.3