/*
* Copyright (c) 2007 Vojtech Mencl
* All rights reserved.
*
* Redistribution and use in source and binary forms, with or without
* modification, are permitted provided that the following conditions
* are met:
*
* - Redistributions of source code must retain the above copyright
* notice, this list of conditions and the following disclaimer.
* - Redistributions in binary form must reproduce the above copyright
* notice, this list of conditions and the following disclaimer in the
* documentation and/or other materials provided with the distribution.
* - The name of the author may not be used to endorse or promote products
* derived from this software without specific prior written permission.
*
* THIS SOFTWARE IS PROVIDED BY THE AUTHOR ``AS IS'' AND ANY EXPRESS OR
* IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES
* OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED.
* IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY DIRECT, INDIRECT,
* INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT
* NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
* DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
* THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
* (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF
* THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
*/
/** @addtogroup genericadt
* @{
*/
/**
* @file
* @brief Extended AVL tree with relative keys implementation.
*
* This file implements Extended AVL tree with relative keys type and operations.
*
* Extended AVL tree with relative keys (ExtAvlrel tree) has the following properties:
* @li it is binary search tree with unique real keys
* @li right subtree of every node is Avl tree
* @li height of left subtree of every node is not greater then height of right subtree + 1
* @li nodes with the same real keys are linked to the tree nodes of the same key, they are not tree nodes
* @li every node is part of doubly linked list with head
* @li nodes are connected in the list ascendentaly according to their real keys, node key is
* only difference between previous real node's key and its real node's key
* @li real key is either equal node key if node is leftmost node in tree or sum of all
* node keys with smaller real key
*
* Be careful of using this tree because node keys are not equal real keys (except leftmost node).
*/
#include <adt/extavlrel.h>
#include <debug.h>
#include <panic.h>
#define AVLTREE_LEFT 0
#define AVLTREE_RIGHT 1
/* Returns height of tree -1 */
#define extavlreltree_tree_height(node) (((node) == NULL) ? (-1) : (((node)->lft_height>(node)->rgt_height)?(node)->lft_height:(node)->rgt_height))
/** Search first occurence (oldest node with this real key) of given key in ExtAVLrel tree.
*
* @param t ExtAVLrel tree.
* @param key Key to be searched.
*
* @return Pointer to node or NULL if there is no such key.
*/
extavlreltree_node_t *extavlreltree_search(extavlreltree_t *t, uint64_t key)
{
extavlreltree_node_t *cur;
uint64_t sum, s;
/*
* Find right subtree in way up to the root where can be node with given key.
* Root node is the last node in the way up, when we reach root, it means,
* that searched node belongs to the right subtree of root.
*/
sum = 0;
cur = t->head.next;
while (1) {
sum += cur->key + cur->rgt_sum;
if ((key <= sum) || (cur == t->root))
break;
else
cur = cur->par;
}
/*
* Sorting for cycle.
* Search for key in choosen subtree. Searching start at cur node which we have found
* in previous step. It is common search algorithm for binary search tree.
*/
while (cur != NULL) {
s = sum - cur->rgt_sum;
if (key < s) {
/*
* Left subtree. Find max value in left subtree of cur.
*/
sum -= cur->key + cur->rgt_sum;
cur = cur->lft;
} else if (key > s) {
/*
* Right subtree. sum has still max value in the right subtree of cur.
*/
cur = cur->rgt;
} else {
/*
* Equal values. We have found node with given key.
*/
return cur;
}
}
return NULL;
}
/** Insert new node into ExtAVL tree.
*
* New node's key must be set.
*
* @param t ExtAVL tree structure.
* @param newnode New node to be inserted.
*/
void extavlreltree_insert(extavlreltree_t *t, extavlreltree_node_t *newnode)
{
extavlreltree_node_t *cur;
extavlreltree_node_t *son;
extavlreltree_node_t *gpa;
extavlreltree_node_t *par;
uint64_t sum, s;
uint8_t dir;
/*
* Condition var - all rgt_sums in the way down to root must be repaired in condition
* that we came there from right and on the way from repaired node to new node we
* never turn to the left. Reparation is done in the reparation cycle.
*/
bool repair_rgt_sum;
ASSERT(t);
ASSERT(newnode);
/*
* Insert first node into empty tree. Key is left without change (according to definition).
*/
cur = t->head.next;
if (cur == &t->head) {
newnode->lft = NULL;
newnode->rgt = NULL;
newnode->lft_height = 0;
newnode->rgt_height = 0;
newnode->par = NULL;
newnode->next = &t->head;
newnode->prev = &t->head;
newnode->rgt_sum = 0;
t->head.prev = newnode;
t->head.next = newnode;
t->root = newnode;
return;
}
/*
* Find right subtree in way up to the root where newnode will be placed.
* Root node is the last node in the way up, when we reach root, it means,
* that newnode belongs to the right subtree of root.
*
* When max key of cur's right subtree is inserted, while cycle overjumps
* right node and stops. But in the next sorting for cycle is this situation
* solved (for cycle jumps back to the left child).
*/
sum = 0;
while (1) {
sum += cur->key + cur->rgt_sum;
if ((newnode->key <= sum) || (cur == t->root))
break;
else
cur = cur->par;
}
/*
* Sorting for cycle.
* Find a place for newnode. Searching start at cur node which we have found
* in previous step. It is common search algorithm for binary search tree.
*/
for (;;) {
s = sum - cur->rgt_sum;
if (newnode->key < s) {
/*
* Left subtree. Find max value in left subtree of cur.
*/
sum -= cur->key + cur->rgt_sum;
if (!cur->lft) {
/*
* Insert new node to the left.
*/
cur->lft = newnode;
newnode->lft = NULL;
newnode->rgt = NULL;
newnode->lft_height = 0;
newnode->rgt_height = 0;
newnode->par = cur;
/*
* Insert newnode to list.
*/
newnode->next = cur;
newnode->prev = cur->prev;
cur->prev->next = newnode;
cur->prev = newnode;
newnode->key -= sum;
newnode->rgt_sum = 0;
/*
* Repair key of next value (next node always exists). newnode->key
* has been already set. Needn't check whether newnode->next is head
* beacause newnode is left child (next node is his father).
*/
newnode->next->key -= newnode->key;
repair_rgt_sum = false;
dir = AVLTREE_LEFT;
break;
}
cur = cur->lft;
} else if (newnode->key > s) {
/*
* Right subtree. sum has still max value in the right subtree of cur.
*/
if (!cur->rgt) {
cur->rgt = newnode;
newnode->lft = NULL;
newnode->rgt = NULL;
newnode->lft_height = 0;
newnode->rgt_height = 0;
newnode->par = cur;
/*
* Find last node in the chain with the same key as cur node.
*/
gpa = cur->next;
while (gpa != &t->head && gpa->key == 0)
gpa = gpa->next;
/*
* Insert new node to list. Right place in the list was found in
* previous cycle.
*/
newnode->prev = gpa->prev;
newnode->next = gpa;
gpa->prev->next = newnode;
gpa->prev = newnode;
newnode->key -= sum;
newnode->rgt_sum = 0;
/*
* Repair key of next value (next node always exists). newnode->key
* has been already set.
*/
if (newnode->next != &t->head)
newnode->next->key -= newnode->key;
/*
* All rgt_sums in the way down to root must be repaired in condition
* that we came there from right and on the way from node to new node we
* never turn left.
*/
repair_rgt_sum = true;
dir = AVLTREE_RIGHT;
break;
}
cur = cur->rgt;
} else {
/*
* Equal values. Give newnode to the last position of chain with the cur head and
* end insertion.
*/
gpa = cur->next;
while (gpa != &t->head && gpa->key == 0)
gpa = gpa->next;
/*
* Insert new node to list in right place.
*/
newnode->prev = gpa->prev;
newnode->next = gpa;
gpa->prev->next = newnode;
gpa->prev = newnode;
newnode->par = NULL;
newnode->lft = NULL;
newnode->rgt = NULL;
newnode->lft_height = 0;
newnode->rgt_height = 0;
/*
* Nodes in chains has key equal 0, because difference between previous node and them is 0.
*/
newnode->key = 0;
newnode->rgt_sum = 0;
return;
}
}
/*
* Balancing all nodes from newnode's parent down to root.
*/
cur = newnode->par;
while (true) {
if (dir == AVLTREE_LEFT) {
/*
* Insertion was made in the left subtree - repair left height, stop
* repairing rgt_sum and check balance of current node.
*/
cur->lft_height = extavlreltree_tree_height(cur->lft) + 1;
repair_rgt_sum = false;
if ((cur->rgt_height - cur->lft_height) <= -2) {
/*
* Balance was corrupted, must be repaired through LL or LR rotation.
*/
par = cur->par;
son = cur->lft;
if ((son->rgt_height - son->lft_height) != 1) {
/*
* LL rotation.
*/
gpa = son;
cur->lft = son->rgt;
if (cur->lft != NULL) cur->lft->par = cur;
cur->par = son;
son->rgt = cur;
/*
* Repair heights.
*/
cur->lft_height = son->rgt_height;
son->rgt_height = extavlreltree_tree_height(cur) + 1;
/*
* Repair rgt_sum.
*/
son->rgt_sum += cur->key + cur->rgt_sum;
} else {
/*
* LR rotation.
*/
gpa = son->rgt;
son->rgt = gpa->lft;
if (gpa->lft != NULL) gpa->lft->par = son;
gpa->lft = son;
son->par = gpa;
cur->lft = gpa->rgt;
if (gpa->rgt != NULL) gpa->rgt->par = cur;
gpa->rgt = cur;
cur->par = gpa;
/*
* Repair heights.
*/
cur->lft_height = gpa->rgt_height;
son->rgt_height = gpa->lft_height;
gpa->rgt_height = extavlreltree_tree_height(cur) + 1;
gpa->lft_height = extavlreltree_tree_height(son) + 1;
/*
* Repair rgt_sums.
*/
son->rgt_sum -= gpa->key + gpa->rgt_sum;
gpa->rgt_sum += cur->key + cur->rgt_sum;
}
/*
* Repair parent of current node.
*/
gpa->par = par;
} else {
/*
* Balance is correct, continue balancing at parent node.
*/
par = cur->par;
gpa = cur;
}
} else {
/*
* Insertion was made in the right subtree - repair right height, try to
* repair rgt_sum and check balance of current node.
*/
cur->rgt_height = extavlreltree_tree_height(cur->rgt) + 1;
if (repair_rgt_sum) {
cur->rgt_sum += newnode->key;
}
if ((cur->rgt_height - cur->lft_height) >= 2) {
/*
* Balance was corrupted, must be repaired through RL or RR rotation.
*/
par = cur->par;
son = cur->rgt;
if ((son->rgt_height - son->lft_height) != -1) {
/*
* RR rotation.
*/
gpa = son;
cur->rgt = son->lft;
if (cur->rgt != NULL) cur->rgt->par = cur;
cur->par = son;
son->lft = cur;
/*
* Repair heights.
*/
cur->rgt_height = son->lft_height;
son->lft_height = extavlreltree_tree_height(cur) + 1;
/*
* Repair rgt_sum.
*/
cur->rgt_sum -= son->rgt_sum + son->key;
} else {
/*
* RL rotation.
*/
gpa = son->lft;
son->lft = gpa->rgt;
if (gpa->rgt != NULL) gpa->rgt->par = son;
gpa->rgt = son;
son->par = gpa;
cur->rgt = gpa->lft;
if (gpa->lft != NULL) gpa->lft->par = cur;
gpa->lft = cur;
cur->par = gpa;
/*
* Repair heights.
*/
cur->rgt_height = gpa->lft_height;
son->lft_height = gpa->rgt_height;
gpa->lft_height = extavlreltree_tree_height(cur) + 1;
gpa->rgt_height = extavlreltree_tree_height(son) + 1;
/*
* Repair rgt_sums.
*/
cur->rgt_sum -= son->key + son->rgt_sum + gpa->key + gpa->rgt_sum;
gpa->rgt_sum += son->key + son->rgt_sum;
}
/*
* Repair parent of current node.
*/
gpa->par = par;
} else {
/*
* Balance is correct, continue balancing at parent node.
*/
par = cur->par;
gpa = cur;
}
}
/*
* Change parent pointers, set direction where is newnode and
* continue balancing at parent node or if current node
* is root then change root atribute pointer and stop
*/
if (par) {
if (par->lft == cur) {
par->lft = gpa;
dir = AVLTREE_LEFT;
} else {
par->rgt = gpa;
dir = AVLTREE_RIGHT;
}
} else {
t->root = gpa;
break;
}
cur = par;
}
}
/** Delete node from ExtAVLrel tree.
*
* @param t ExtAVLrel tree structure.
* @param node Address of node which will be deleted.
*/
void extavlreltree_delete(extavlreltree_t *t, extavlreltree_node_t *node)
{
extavlreltree_node_t **gpapar;
extavlreltree_node_t *cur;
extavlreltree_node_t *par;
extavlreltree_node_t *gpa;
int8_t dir;
int8_t dir2=0;
uint64_t key=0;
int16_t balance;
/*
* Condition var - if true then all rgt_sums in the way down to root must be repaired in condition
* that we came there from right and on the way from repaired node to new node we
* never turn to the left. Reparation is done in the reparation cycle.
*/
bool repair_rgt_sum;
ASSERT(t);
ASSERT(node);
/*
* Delete node from list.
*/
node->next->prev = node->prev;
node->prev->next = node->next;
if (!node->par) {
if (t->root != node) {
/*
* It is list node (not a tree node). Needn't repair tree or anything else.
*/
return;
}
repair_rgt_sum = false;
gpapar = &(t->root);
} else {
/*
* Find tree pointer which points to node.
*/
if (node->par->lft == node) {
gpapar = &(node->par->lft);
repair_rgt_sum = false;
} else {
gpapar = &(node->par->rgt);
/*
* Node is right child - rgt_sum might be repaired.
*/
repair_rgt_sum = true;
}
}
if (&t->head != node->next && node->next->key == 0) {
/*
* Deleted node has at least one node node with the same key which is closest next
* neighbor in the list, copy node atributes into next node and end.
*/
cur = node->next;
cur->lft = node->lft;
cur->rgt = node->rgt;
cur->par = node->par;
cur->lft_height = node->lft_height;
cur->rgt_height = node->rgt_height;
*gpapar = cur;
if (node->lft) node->lft->par = cur;
if (node->rgt) node->rgt->par = cur;
cur->key = node->key;
cur->rgt_sum = node->rgt_sum;
return;
}
/*
* Repair next node's key (it must be difference between previous key and its key).
*/
if (node->next != &t->head) {
node->next->key += node->key;
}
/*
* Check situation in the tree around deleted node.
*/
if (!node->lft) {
/*
* Deleted node has not left son. Right son will take deleted node's place.
*/
gpa = node->par;
if (node->rgt) {
/*
* rgt_sum is not corrupted because the biggest key is in right subtree of node
*/
node->rgt->par = gpa;
repair_rgt_sum = false;
} else {
/*
* node is the biggest key and rgt_sum might be repaired according to which
* child is node.
*/
key = node->key;
}
if (!gpa) {
/*
* Deleted node is root node. Balancing is finished, change only
* root pointer in extavltree structure.
*/
*gpapar = node->rgt;
return;
}
dir = (gpa->lft == node)? AVLTREE_LEFT: AVLTREE_RIGHT;
*gpapar = node->rgt;
} else {
/*
* Node has left son.
*/
cur = node->lft;
if (!cur->rgt) {
/*
* Left son of node hasn't got right son. Left son will take deleted node's place.
*/
*gpapar = cur;
cur->par = node->par;
dir = AVLTREE_LEFT;
cur->rgt = node->rgt;
if (node->rgt) node->rgt->par = cur;
gpa = cur;
cur->rgt_height = node->rgt_height;
cur->lft_height = node->lft_height;
/*
* cur->lft_height will be decreased in repair cycle.
*/
if (repair_rgt_sum == false && node->rgt_sum == 0) {
/*
* node hasn't got right son so right sum is 0.
*/
cur->rgt_sum = 0;
} else {
cur->rgt_sum = node->rgt_sum + node->key; //pri node->rgt_sum == 0 bude opraveno v cyklu
if (repair_rgt_sum == true && node->rgt_sum != 0) {
/*
* node has got right son so node's key is not the biggest key in any subtree.
*/
repair_rgt_sum = false;
} else {
/*
* node is the biggest key and predecessors might be repaired.
*/
key = node->key;
}
}
} else {
/*
* Node has left and right son. Find a node with smallest key in left subtree
* and change that node with deleted node.
*/
while (cur->rgt != NULL)
cur = cur->rgt;
*gpapar = cur;
cur->rgt = node->rgt;
if (node->rgt) node->rgt->par = cur;
gpa = cur->par;
gpa->rgt = cur->lft;
if (cur->lft) cur->lft->par = gpa;
cur->lft = node->lft;
cur->lft->par = cur;
cur->par = node->par;
dir = AVLTREE_RIGHT;
cur->lft_height = node->lft_height;
cur->rgt_height = node->rgt_height;
/*
* gpa->rgt_height and cur->lft_height will be repaired in repair cycle.
*/
/*
* node must have always rgt child otherwise its malfunction of extavltree definition
* so we can add node->key. If it was to the contrary, we wouldn't know where
*/
cur->rgt_sum = node->rgt_sum + node->key;
/*
* The biggest key in at least one subtree was changed - rgt_sum must be repaired.
*/
repair_rgt_sum = true;
key = cur->key;
}
/*
* Deleted node is root node. Balancing is finished.
*/
if (!gpa) return;
}
/*
* Repair cycle which goes from gpa node down to root.
*/
for(;;) {
if (repair_rgt_sum) {
/*
* The biggest key in right subtree was deleted so rgt_sum must be changed.
*/
gpa->rgt_sum -= key;
}
/*
* Find tree pointer which points to the currently balanced node. When balanced
* node is root, root pointer from extavltree structure is taken.
*/
if (!gpa->par)
gpapar = &(t->root);
else {
if (gpa->par->lft == gpa) {
gpapar = &(gpa->par->lft);
dir2 = AVLTREE_LEFT;
repair_rgt_sum = false;
} else {
gpapar = &(gpa->par->rgt);
dir2 = AVLTREE_RIGHT;
}
}
if (dir == AVLTREE_LEFT) {
/*
* Deletition was made in left subtree.
*/
gpa->lft_height--;
balance = gpa->rgt_height - gpa->lft_height;
if (balance == 1) {
/*
* Stop balancing, tree is balanced.
*/
break;
} else if (balance == 2) {
/*
* Bad balance, heights of left and right subtrees differs more then is allowed.
*/
par = gpa->rgt;
if ((par->rgt_height - par->lft_height) == -1) {
/*
* RL rotation
*/
cur = par->lft;
par->lft = cur->rgt;
cur->rgt = par;
gpa->rgt = cur->lft;
cur->lft = gpa;
/*
* Repair balances.
*/
par->lft_height = cur->rgt_height;
gpa->rgt_height = cur->lft_height;
cur->lft_height = extavlreltree_tree_height(gpa) + 1;
cur->rgt_height = par->rgt_height + 1;
/*
* Repair paternity.
*/
if (gpa->rgt) gpa->rgt->par = gpa;
if (par->lft) par->lft->par = par;
cur->par = gpa->par;
gpa->par = cur;
par->par = cur;
/*
* Repair tree pointer which points to the current node.
*/
*gpapar = cur;
/*
* Repair rgt_sums after rotation was done.
*/
gpa->rgt_sum -= par->key + par->rgt_sum + cur->key + cur->rgt_sum;
cur->rgt_sum += par->key + par->rgt_sum;
/*
* Next balancing at parent node.
*/
gpa = cur->par;
} else {
/*
* RR rotation
*/
gpa->rgt = par->lft;
gpa->rgt_height = par->lft_height;
if (par->lft) par->lft->par = gpa;
par->lft = gpa;
/*
* Repair paternity.
*/
par->par = gpa->par;
gpa->par = par;
/*
* Repair heights and tree pointer which points to the current node.
*/
balance = par->rgt_height - par->lft_height;
par->lft_height++;
*gpapar = par;
/*
* Repair rgt_sums after rotation was done.
*/
gpa->rgt_sum -= par->key + par->rgt_sum;
/*
* Ends when tree is balanced or do the next step.
*/
if (balance == 0) return;
gpa = par->par;
}
} else {
/*
* Current node is balanced - perform balance check of its parent.
*/
gpa = gpa->par;
}
} else {
/*
* Balance right son.
*/
gpa->rgt_height--;
balance = gpa->rgt_height - gpa->lft_height;
if (balance == -1) {
/*
* Stop balancing, tree might be balanced or not, whole tree is repaired only during insertion.
*/
break;
} else if (balance == -2) {
/*
* Balance was corrupted - must be repaired.
*/
par = gpa->lft;
if ((par->rgt_height - par->lft_height) >= +1) {
/*
* If balance is -2 then par node always exists.
*/
if ((gpa->lft_height - (extavlreltree_tree_height(par))) == 1) {
/*
* LR rotation. Height of par subtree is not decreased due to timeout operation.
*/
cur = par->rgt;
par->rgt = cur->lft;
cur->lft = par;
gpa->lft = cur->rgt;
cur->rgt = gpa;
/*
* Repair balances.
*/
par->rgt_height = cur->lft_height;
gpa->lft_height = cur->rgt_height;
cur->rgt_height = gpa->rgt_height + 1;
cur->lft_height = extavlreltree_tree_height(par) + 1;
/*
* Repair paternity.
*/
if (gpa->lft) gpa->lft->par = gpa;
if (par->rgt) par->rgt->par = par;
cur->par = gpa->par;
gpa->par = cur;
par->par = cur;
/*
* Repair tree pointer which points to the current node.
*/
*gpapar = cur;
/*
* Repair rgt_sums after rotation was done.
*/
par->rgt_sum -= cur->key + cur->rgt_sum;
cur->rgt_sum += gpa->key + gpa->rgt_sum;
/*
* Next balancing at parent node.
*/
gpa = cur->par;
} else {
/*
* Left subtree of cur has been already decreased by timeout operation.
*/
gpa = gpa->par;
}
} else {
/*
* LL rotation.
*/
int prevlftheight = gpa->lft_height;
gpa->lft = par->rgt;
gpa->lft_height = par->rgt_height;
if (par->rgt) par->rgt->par = gpa;
par->rgt = gpa;
/*
* Repair paternity.
*/
par->par = gpa->par;
gpa->par = par;
/*
* Repair heights and tree pointer which points to the current node.
*/
balance = par->rgt_height - par->lft_height;
par->rgt_height = extavlreltree_tree_height(gpa) + 1;
*gpapar = par;
/*
* Repair rgt_sums after rotation was done.
*/
par->rgt_sum += gpa->key + gpa->rgt_sum;
/*
* Ends balancing when heights in par nodes are balanced and height
* of par subtree wasn't decreased due to timeout operation or do
* the next step.
*/
if (balance == 0 && par->rgt_height == prevlftheight) {
gpa = par;
break;
}
gpa = par->par;
}
} else {
/*
* Current node is balanced - perform balance check of its parent.
*/
gpa = gpa->par;
}
}
/*
* When root is reached then end balancing.
*/
if (!gpa) return;
dir = dir2;
}
/*
* End balancing. We must continue in repairing rgt_sum until we
* reach first left child.
*/
if (repair_rgt_sum) {
cur = gpa;
gpa = gpa->par;
while (gpa) {
if (gpa->lft == cur)
break;
gpa->rgt_sum -= key;
cur = gpa;
gpa = gpa->par;
}
}
}
/** Delete node from ExtAVLirel tree with the smallest key.
*
* Be careful deleted node must have key equal 0 to perform regular timeout.
*
* @param t ExtAVLrel tree structure.
*/
bool extavlreltree_delete_min(extavlreltree_t *t)
{
extavlreltree_node_t *expnode;
extavlreltree_node_t *nextnode;
ASSERT(t);
expnode = t->head.next;
nextnode = expnode->next;
if (&t->head == expnode) return false;
if (nextnode != &t->head) {
/*
* Only first node in the list can be tree node and its key can be 0 (nextnode is the second).
*/
if (nextnode->key == 0) {
/*
* Next node of expnode is its chain node. Copy expnode into nextnode.
*/
nextnode->lft = expnode->lft;
nextnode->rgt = expnode->rgt;
nextnode->par = expnode->par;
nextnode->lft_height = expnode->lft_height;
nextnode->rgt_height = expnode->rgt_height;
if (t->root == expnode)
t->root = nextnode;
else
if (expnode->par->lft == expnode)
expnode->par->lft = nextnode;
else
expnode->par->rgt = nextnode;
if (expnode->lft) expnode->lft->par = nextnode;
if (expnode->rgt) expnode->rgt->par = nextnode;
nextnode->rgt_sum = expnode->rgt_sum;
} else if (!expnode->par) {
/*
* Delete root node which musn't have left son.
*/
t->root = expnode->rgt;
if (expnode->rgt) expnode->rgt->par = NULL;
} else if (expnode->rgt) {
/*
* Always delete parent of left son.
*/
expnode->rgt->par = expnode->par;
expnode->par->lft = expnode->rgt;
expnode->par->lft_height = expnode->rgt_height;
} else {
/*
* Deleted node doesn't have right son.
*/
expnode->par->lft = NULL;
expnode->par->lft_height = 0;
}
nextnode->key += expnode->key;
}
/*
* Delete node from the list.
*/
t->head.next = nextnode;
nextnode->prev = &t->head;
return true;
}