From 954dcec27308529e17e09cb229a0807ed12fe874 Mon Sep 17 00:00:00 2001 From: Warren Dukes Date: Wed, 2 Aug 2006 02:06:00 +0000 Subject: tree optimization: reduce the number of compares required for insertion and deletion by storing the position in the parent node of each child git-svn-id: https://svn.musicpd.org/mpd/trunk@4532 09075e82-0dd4-0310-85a5-a0d7c8717e4f --- src/tree.c | 204 +++++++++++++++++++++++++++++++------------------------------ 1 file changed, 103 insertions(+), 101 deletions(-) diff --git a/src/tree.c b/src/tree.c index e352aebc8..f5a804a92 100644 --- a/src/tree.c +++ b/src/tree.c @@ -28,7 +28,7 @@ #define DATA_PER_NODE (CHILDREN_PER_NODE-1) -#if CHILDREN_PER_NODE > 11 +#if CHILDREN_PER_NODE > 7 #define USE_BINARY_SEARCH 1 #endif @@ -39,8 +39,9 @@ struct _TreeNode { void * data[DATA_PER_NODE]; struct _TreeNode * parent; + short parentPos; struct _TreeNode * children[CHILDREN_PER_NODE]; - int dataCount; + short dataCount; }; struct _Tree @@ -140,35 +141,19 @@ _SplitNode(TreeNode * node) TreeNode * newNode = _MakeNode(); -#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; + 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); @@ -179,43 +164,41 @@ _SplitNode(TreeNode * node) static void _InsertNodeAndData(Tree * tree, - TreeNode * node, + 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 - if (newNode) - { - newNode->parent = node; - } - - int i = 0; - _FindPosition(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--) + 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; + } } -#endif - assert(!node->children[i] || - tree->compareData(data, node->children[i]->data[0]) > 0); +#ifdef TREE_DEBUG + assert(!node->children[pos] || + tree->compareData(data, node->children[pos]->data[0]) > 0); +#endif - node->data[i] = data; - node->children[i+1] = newNode; + node->data[pos] = data; node->dataCount++; + + node->children[pos+1] = newNode; + if (newNode) + { + newNode->parent = node; + newNode->parentPos = pos+1; + } } static @@ -223,18 +206,21 @@ 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 (tree->compareData(data, moreNode->data[0]) < 0) + if (pos <= lessNode->dataCount) { - _InsertNodeAndData(tree, lessNode, newNode, data); + _InsertNodeAndData(tree, lessNode, pos, newNode, data); lessNode->dataCount--; retData = lessNode->data[lessNode->dataCount]; lessNode->data[lessNode->dataCount] = NULL; @@ -243,51 +229,39 @@ _AddDataToSplitNodes(Tree * tree, if (moreNode->children[0]) { moreNode->children[0]->parent = moreNode; + moreNode->children[0]->parentPos = 0; } lessNode->children[lessNode->dataCount+1] = NULL; } else { - if (newNode) - { - newNode->parent = moreNode; - } - - int i = 0; - _FindPosition(tree, moreNode, data, &i); + pos -= lessNode->dataCount; + retData = moreNode->data[0]; + assert(!moreNode->children[0]); + assert(!moreNode->data[moreNode->dataCount]); - if (i == 0) - { - moreNode->children[0] = newNode; - return data; - } - else - { - 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++) + 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; + } } -#endif - assert(!moreNode->children[i-1] || + assert(!moreNode->children[pos-1] || tree->compareData(data, - moreNode->children[i]->data[0]) > 0); + moreNode->children[pos-1]->data[0]) > 0); - moreNode->data[i-1] = data; - moreNode->children[i] = newNode; + moreNode->data[pos-1] = data; + moreNode->children[pos] = newNode; + if (newNode) + { + newNode->parent = moreNode; + newNode->parentPos = pos; + } } return retData; @@ -299,9 +273,15 @@ _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) { @@ -311,35 +291,39 @@ _InsertAt(TreeIterator * iter, void * data) // insert data in split nodes data = _AddDataToSplitNodes(iter->tree, node, - newNode, + newNode, + pos, insertNode, data); - insertNode = newNode; - 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->children[0] = node; - iter->tree->rootNode->children[1] = newNode; iter->tree->rootNode->dataCount = 1; return; } + pos = node->parentPos; node = node->parent; + insertNode = newNode; } else { // insert the data and newNode - _InsertNodeAndData( iter->tree, - node, - insertNode, - data ); - node = NULL; + _InsertNodeAndData(iter->tree, + node, + pos, + insertNode, + data); + return; } } } @@ -363,12 +347,14 @@ _MergeNodes(TreeNode * lessNode, TreeNode * moreNode) 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; @@ -412,14 +398,9 @@ _DeleteAt(TreeIterator * iter) data = &(child->data[child->dataCount-1]); node = child; } - else if (node->parent) + else { - // if there are no children, we need to set _pos_ - // to the correct node of the parent - _FindPosition(iter->tree, - node->parent, - node->data[0], - &pos); + pos = node->parentPos; } } @@ -454,6 +435,8 @@ _DeleteAt(TreeIterator * iter) { node->children[node->dataCount]-> parent = node; + node->children[node->dataCount]-> + parentPos = node->dataCount; } node->parent->data[pos] = (*child)->data[0]; @@ -463,8 +446,17 @@ _DeleteAt(TreeIterator * iter) (*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--; @@ -478,14 +470,24 @@ _DeleteAt(TreeIterator * iter) { 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]; @@ -527,19 +529,18 @@ _DeleteAt(TreeIterator * iter) 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--; - if (node->parent->parent) - { - _FindPosition(iter->tree, - node->parent->parent, - node->data[0], - &pos); - } node = node->parent; + pos = node->parentPos; } } // this is a root node @@ -550,6 +551,7 @@ _DeleteAt(TreeIterator * iter) if (node->children[0]) { node->children[0]->parent = NULL; + node->children[0]->parentPos = 0; } iter->tree->rootNode = node->children[0]; -- cgit v1.2.3