Subversion Repositories HelenOS

Compare Revisions

Ignore whitespace Rev 2496 → Rev 2497

/branches/rcu/kernel/generic/src/adt/avl.c
217,7 → 217,8
par->par = top->par;
top->par = par;
par->rgt = top;
par->balance = top->balance = 0;
par->balance = 0;
top->balance = 0;
*dpc = par;
} else {
/*
242,7 → 243,8
par->balance = 0;
top->balance = 1;
} else if (gpa->balance == 0) {
par->balance = top->balance = 0;
par->balance = 0;
top->balance = 0;
} else {
par->balance = -1;
top->balance = 0;
262,7 → 264,8
par->par = top->par;
top->par = par;
par->lft = top;
par->balance = top->balance = 0;
par->balance = 0;
top->balance = 0;
*dpc = par;
} else {
/*
287,7 → 290,8
par->balance = 0;
top->balance = -1;
} else if (gpa->balance == 0) {
par->balance = top->balance = 0;
par->balance = 0;
top->balance = 0;
} else {
par->balance = 1;
top->balance = 0;
304,6 → 308,77
 
}
 
/** Repair the tree after reparenting node u.
*
* If node u has no parent, mark it as the root of the whole tree. Otherwise
* node v represents stale address of one of the children of node u's parent.
* Replace v with w as node u parent's child (for most uses, u and w will be the
* same).
*
* @param t AVL tree.
* @param u Node whose new parent has a stale child pointer.
* @param v Stale child of node u's new parent.
* @param w New child of node u's new parent.
* @param dir If not NULL, address of the variable where to store information
* about whether w replaced v in the left or the right subtree of
* u's new parent.
* @param ro Read only operation; do not modify any tree pointers. This is
* useful for tracking direction via the dir pointer.
*
* @return Zero if w became the new root of the tree, otherwise return
* non-zero.
*/
static int
repair(avltree_t *t, avltree_node_t *u, avltree_node_t *v, avltree_node_t *w,
int *dir, int ro)
{
if (u->par == NULL) {
if (!ro)
t->root = w;
return 0;
} else {
if (u->par->lft == v) {
if (!ro)
u->par->lft = w;
if (dir)
*dir = LEFT;
} else {
ASSERT(u->par->rgt == v);
if (!ro)
u->par->rgt = w;
if (dir)
*dir = RIGHT;
}
}
return 1;
}
 
#define REBALANCE(DIR1, DIR2, SIGN) \
if (cur->balance == -1 * SIGN) { \
par->balance = 0; \
gpa->balance = 1 * SIGN; \
if (gpa->DIR1) \
gpa->DIR1->par = gpa; \
par->DIR2->par = par; \
} else if (cur->balance == 0) { \
par->balance = 0; \
gpa->balance = 0; \
if (gpa->DIR1) \
gpa->DIR1->par = gpa; \
if (par->DIR2) \
par->DIR2->par = par; \
} else { \
par->balance = -1 * SIGN; \
gpa->balance = 0; \
if (par->DIR2) \
par->DIR2->par = par; \
gpa->DIR1->par = gpa; \
} \
cur->balance = 0;
 
#define REBALANCE_LR() REBALANCE(lft, rgt, 1)
#define REBALANCE_RL() REBALANCE(rgt, lft, -1)
 
/** Delete a node from the AVL tree.
*
* Because multiple identical keys are allowed, the parent pointers are
317,12 → 392,12
avltree_node_t *cur;
avltree_node_t *par;
avltree_node_t *gpa;
uint8_t dir;
int dir;
 
ASSERT(t);
ASSERT(node);
if (node->lft == NULL) {
if (node->lft == NULL) {
if (node->rgt) {
/*
* Replace the node with its only right son.
354,9 → 429,9
}
} else {
/*
* The node has left and right son. Find a node with the
* smallest key in the left subtree and replace the deleted node
* with that node.
* The node has the left son. Find a node with the smallest key
* in the left subtree and replace the deleted node with that
* node.
*/
for (cur = node->lft; cur->rgt != NULL; cur = cur->rgt)
;
402,15 → 477,7
* Repair the parent node's pointer which pointed previously to the
* deleted node.
*/
if (node->par == NULL) {
t->root = cur;
} else {
if (node->par->lft == node) {
node->par->lft = cur;
} else {
node->par->rgt = cur;
}
}
(void) repair(t, node, node, cur, NULL, false);
/*
* Repair cycle which repairs balances of nodes on the way from from the
450,26 → 517,7
* children, depending on the balance
* factor of the grand child (cur).
*/
if (cur->balance == 1) {
par->balance = 0;
gpa->balance = -1;
if (gpa->rgt)
gpa->rgt->par = gpa;
par->lft->par = par;
} else if (cur->balance == 0) {
par->balance = gpa->balance = 0;
if (gpa->rgt)
gpa->rgt->par = gpa;
if (par->lft)
par->lft->par = par;
} else {
par->balance = 1;
gpa->balance = 0;
if (par->lft)
par->lft->par = par;
gpa->rgt->par = gpa;
}
cur->balance = 0;
REBALANCE_RL();
/*
* Repair paternity.
478,25 → 526,9
gpa->par = cur;
par->par = cur;
 
/*
* Repair the pointer which pointed to
* the balanced node. If it was root
* then the balancing is finished.
* Otherwise continue with the next
* iteration (parent node).
*/
if (cur->par == NULL) {
t->root = cur;
if (!repair(t, cur, gpa, cur, &dir,
false))
break;
} else {
if (cur->par->lft == gpa) {
cur->par->lft = cur;
dir = LEFT;
} else {
cur->par->rgt = cur;
dir = RIGHT;
}
}
gpa = cur->par;
} else {
/*
525,49 → 557,15
par->balance = -1;
gpa->balance = 1;
 
/*
* Repair the pointer which
* pointed to the balanced node
* and finish balancing.
*/
if (par->par == NULL) {
t->root = par;
} else {
if (par->par->lft ==
gpa) {
par->par->lft =
par;
} else {
par->par->rgt =
par;
}
}
(void) repair(t, par, gpa, par,
NULL, false);
break;
} else {
par->balance = gpa->balance = 0;
/*
* Repair the pointer which
* pointed to the balanced node.
* If it was root then balancing
* is finished. Otherwise
* continue with the next
* iteration (parent node).
*/
if (par->par == NULL) {
t->root = par;
par->balance = 0;
gpa->balance = 0;
if (!repair(t, par, gpa, par,
&dir, false))
break;
} else {
if (par->par->lft ==
gpa) {
par->par->lft =
par;
dir = LEFT;
} else {
par->par->rgt =
par;
dir = RIGHT;
}
}
}
gpa = par->par;
}
578,14 → 576,8
* is finished else continue with the next
* iteration (parent node).
*/
if (!gpa->par)
if (!repair(t, gpa, gpa, NULL, &dir, true))
break;
 
if (gpa->par->lft == gpa) {
dir = LEFT;
} else {
dir = RIGHT;
}
gpa = gpa->par;
}
} else {
621,26 → 613,7
* children, depending on the balance
* factor of the grand child (cur).
*/
if (cur->balance == -1) {
par->balance = 0;
gpa->balance = 1;
if (gpa->lft)
gpa->lft->par = gpa;
par->rgt->par = par;
} else if (cur->balance == 0) {
par->balance = gpa->balance = 0;
if (gpa->lft)
gpa->lft->par = gpa;
if (par->rgt)
par->rgt->par = par;
} else {
par->balance = -1;
gpa->balance = 0;
if (par->rgt)
par->rgt->par = par;
gpa->lft->par = gpa;
}
cur->balance = 0;
REBALANCE_LR();
 
/*
* Repair paternity.
649,31 → 622,15
gpa->par = cur;
par->par = cur;
 
/*
* Repair the pointer which pointed to
* the balanced node. If it was root
* then balancing is finished. Otherwise
* continue with the next iteration
* (parent node).
*/
if (cur->par == NULL) {
t->root = cur;
break;
} else {
if (cur->par->lft == gpa) {
cur->par->lft = cur;
dir = LEFT;
} else {
cur->par->rgt = cur;
dir = RIGHT;
}
}
if (!repair(t, cur, gpa, cur, &dir,
false))
break;
gpa = cur->par;
} else {
/*
* LL rotation.
*/
 
gpa->lft = par->rgt;
if (par->rgt)
par->rgt->par = gpa;
695,50 → 652,16
par->balance = 1;
gpa->balance = -1;
/*
* Repair the pointer which
* pointed to the balanced node
* and finish balancing.
*/
if (par->par == NULL) {
t->root = par;
} else {
if (par->par->lft ==
gpa) {
par->par->lft =
par;
} else {
par->par->rgt =
par;
}
}
(void) repair(t, par, gpa, par,
NULL, false);
break;
} else {
par->balance = gpa->balance = 0;
par->balance = 0;
gpa->balance = 0;
/*
* Repair the pointer which
* pointed to the balanced node.
* If it was root then balancing
* is finished. Otherwise
* continue with the next
* iteration (parent node).
*/
if (par->par == NULL) {
t->root = par;
if (!repair(t, par, gpa, par,
&dir, false))
break;
} else {
if (par->par->lft ==
gpa) {
par->par->lft =
par;
dir = LEFT;
} else {
par->par->rgt =
par;
dir = RIGHT;
}
}
}
gpa = par->par;
}
749,14 → 672,8
* is finished. Otherwise continue with the next
* iteration (parent node).
*/
if (!gpa->par)
if (!repair(t, gpa, gpa, NULL, &dir, true))
break;
 
if (gpa->par->lft == gpa) {
dir = LEFT;
} else {
dir = RIGHT;
}
gpa = gpa->par;
}
}
792,3 → 709,4
 
/** @}
*/