HelenOSHelenOS-docHelenOS-historic

Català-Valencià – Catalan中文 – Chinese (Simplified)中文 – Chinese (Traditional)Česky – CzechDansk – DanishNederlands – DutchEnglish – EnglishSuomi – FinnishFrançais – FrenchDeutsch – Germanעברית – Hebrewहिंदी – HindiMagyar – HungarianBahasa Indonesia – IndonesianItaliano – Italian日本語 – Japanese한국어 – KoreanМакедонски – Macedonianमराठी – MarathiNorsk – NorwegianPolski – PolishPortuguês – PortuguesePortuguês – Portuguese (Brazil)Русский – RussianSlovenčina – SlovakSlovenščina – SlovenianEspañol – SpanishSvenska – SwedishTürkçe – TurkishУкраїнська – UkrainianOëzbekcha – Uzbek

Compare Revisions

• This comparison shows the changes necessary to convert path

  → /branches/rcu/ @ 2495

  → /branches/rcu/ @ 2496

  ↔ Reverse comparison

• Compare Path:	Rev

  With Path:	Rev

Ignore whitespace Rev 2495 → Rev 2496

/branches/rcu/kernel/generic/include/adt/avl.h
38,15 → 38,16
#include <arch/types.h>
/*
* Makro for getting pointer to structure which enclosure avltree structure.
/**
* Macro for getting a pointer to the structure which contains the avltree
* structure.
*
* @param link Pointer to avltree structure.
* @param type Name of outer structure.
* @param member Name of avltree atribute in outer structure.
* @param link Pointer to the avltree structure.
* @param type Name of the outer structure.
* @param member Name of avltree attribute in the outer structure.
*/
#define avltree_get_instance(link,type,member) \
((type *)(((uint8_t *)(link)) - ((uint8_t *)&(((type *)NULL)->member))))
#define avltree_get_instance(link, type, member) \
((type *)(((uint8_t *)(link)) - ((uint8_t *) &(((type *) NULL)->member))))
typedef struct avltree_node avltree_node_t;
57,26 → 58,31
struct avltree_node
{
/**
* Pointer to left descendand of this node.
* Pointer to the left descendant of this node.
*
* All keys of nodes in the left subtree are less then key of this node.
* All keys of nodes in the left subtree are less than the key of this
* node.
*/
struct avltree_node *lft;
/**
* Pointer to right descendand of this node.
* Pointer to the right descendant of this node.
*
* All keys of nodes in the right subtree are greater then key of this node.
* All keys of nodes in the right subtree are greater than the key of
* this node.
*/
struct avltree_node *rgt;
/** Pointer to parent node. Root node has NULL parent. */
/** Pointer to the parent node. Root node has NULL parent. */
struct avltree_node *par;
/** Nodes key. */
/** Node's key. */
uint64_t key;
/** Difference between heights of left and right subtree of this node.*/
/**
* Difference between the heights of the left and the right subtree of
* this node.
*/
int8_t balance;
};
87,12 → 93,12
struct avltree_node *root;
/**
* Base of tree is value that is smaller or equal then every value in tree
* (valid for positive keys otherwise ignore this atribute).
* Base of the tree is a value that is smaller or equal than every value
* in the tree (valid for positive keys otherwise ignore this atribute).
*
* Base is added to current key when new node is inserted into tree.
* Base is changed to the key of node which is deleted with function
* avltree_delete_min.
* The base is added to the current key when a new node is inserted into
* the tree. The base is changed to the key of the node which is deleted
* with avltree_delete_min().
*/
uint64_t base;
};
110,7 → 116,7
/** Initialize node.
*
* @param Node which is initialized.
* @param node Node which is initialized.
*/
static inline void avltree_node_initialize(avltree_node_t *node)
{
121,11 → 127,11
node->balance = 0;
}
avltree_node_t *avltree_find_min(avltree_t *t);
avltree_node_t *avltree_search(avltree_t *t, uint64_t key);
void avltree_insert(avltree_t *t, avltree_node_t *newnode);
void avltree_delete(avltree_t *t, avltree_node_t *node);
bool avltree_delete_min(avltree_t *t);
extern avltree_node_t *avltree_find_min(avltree_t *t);
extern avltree_node_t *avltree_search(avltree_t *t, uint64_t key);
extern void avltree_insert(avltree_t *t, avltree_node_t *newnode);
extern void avltree_delete(avltree_t *t, avltree_node_t *node);
extern bool avltree_delete_min(avltree_t *t);
#endif

/branches/rcu/kernel/generic/src/adt/avl.c
37,14 → 37,16
* This file implements AVL tree type and operations.
*
* Implemented AVL tree has the following properties:
* @li It is binary search tree with non-unique keys.
* @li Difference of heights of left and right subtree of every node is max 1.
* @li It is a binary search tree with non-unique keys.
* @li Difference of heights of the left and the right subtree of every node is
* one at maximum.
*
* Every node has pointer to its parent which allows insertion of multiple identical keys
* into tree.
* Every node has a pointer to its parent which allows insertion of multiple
* identical keys into the tree.
*
* Be careful of using this tree because of base atribute, which is added to every inserted
* node key. There is no rule in which order nodes with the same key are visited.
* Be careful when using this tree because of the base atribute which is added
* to every inserted node key. There is no rule in which order nodes with the
* same key are visited.
*/
#include <adt/avl.h>
51,16 → 53,16
#include <debug.h>
#define AVLTREE_LEFT 0
#define AVLTREE_RIGHT 1
#define LEFT 0
#define RIGHT 1
/** Search first occurence of given key in AVL tree.
/** Search for the first occurence of the given key in an AVL tree.
*
* @param t AVL tree.
* @param key Key to be searched.
*
* @return Pointer to node or NULL if there is no such key.
* @return Pointer to a node or NULL if there is no such key.
*/
avltree_node_t *avltree_search(avltree_t *t, uint64_t key)
{
75,19 → 77,18
p = p->lft;
else if (p->key < key)
p = p->rgt;
else {
else
return p;
}
}
return NULL;
}
/** Find node with smallest key in AVL tree.
/** Find the node with the smallest key in an AVL tree.
*
* @param t AVL tree.
*
* @return Pointer to node or NULL if there is no node in the tree.
* @return Pointer to a node or NULL if there is no node in the tree.
*/
avltree_node_t *avltree_find_min(avltree_t *t)
{
94,9 → 95,10
avltree_node_t *p = t->root;
/*
* Check whether tree is empty.
* Check whether the tree is empty.
*/
if (!p) return NULL;
if (!p)
return NULL;
/*
* Iteratively descend to the leftmost leaf in the tree.
128,11 → 130,10
*/
key = newnode->key + t->base;
/*
* Iteratively descend to the leaf that can contain new node.
* Iteratively descend to the leaf that can contain the new node.
* Last node with non-zero balance in the way to leaf is stored as top -
* it si place of possible balance fault.
* it is a place of possible inbalance.
*/
dpc = &t->root;
gpa = NULL;
142,7 → 143,7
top = par;
}
gpa = par;
dpc = par->key > key? &par->lft: &par->rgt;
dpc = par->key > key ? &par->lft: &par->rgt;
}
/*
155,7 → 156,7
newnode->balance = 0;
/*
* Insert first node into empty tree.
* Insert first node into the empty tree.
*/
if (t->root == NULL) {
*dpc = newnode;
168,24 → 169,27
*dpc = newnode;
/*
* If tree contains one node - end.
* If the tree contains one node - end.
*/
if (top == NULL) return;
if (top == NULL)
return;
/*
* Store pointer of top's father which points to the node with potentialy broken
* balance (top).
* Store pointer of top's father which points to the node with
* potentially broken balance (top).
*/
if (top->par == NULL)
if (top->par == NULL) {
dpc = &t->root;
else
} else {
if (top->par->lft == top)
dpc = &(top->par->lft);
dpc = &top->par->lft;
else
dpc = &(top->par->rgt);
dpc = &top->par->rgt;
}
/*
* Repair all balances on the way from top node to newly inserted node.
* Repair all balances on the way from top node to the newly inserted
* node.
*/
par = top;
while (par != newnode) {
199,7 → 203,7
}
/*
* To balance tree we must check and balance top node.
* To balance the tree, we must check and balance top node.
*/
if (top->balance == -2) {
par = top->lft;
208,7 → 212,8
* LL rotation.
*/
top->lft = par->rgt;
if (top->lft != NULL) top->lft->par = top;
if (top->lft != NULL)
top->lft->par = top;
par->par = top->par;
top->par = par;
par->rgt = top;
222,11 → 227,13
gpa = par->rgt;
par->rgt = gpa->lft;
if (gpa->lft != NULL) gpa->lft->par = par;
if (gpa->lft != NULL)
gpa->lft->par = par;
gpa->lft = par;
par->par = gpa;
top->lft = gpa->rgt;
if (gpa->rgt != NULL) gpa->rgt->par = top;
if (gpa->rgt != NULL)
gpa->rgt->par = top;
gpa->rgt = top;
gpa->par = top->par;
top->par = gpa;
250,7 → 257,8
* RR rotation.
*/
top->rgt = par->lft;
if (top->rgt != NULL) top->rgt->par = top;
if (top->rgt != NULL)
top->rgt->par = top;
par->par = top->par;
top->par = par;
par->lft = top;
264,11 → 272,13
gpa = par->lft;
par->lft = gpa->rgt;
if (gpa->rgt != NULL) gpa->rgt->par = par;
if (gpa->rgt != NULL)
gpa->rgt->par = par;
gpa->rgt = par;
par->par = gpa;
top->rgt = gpa->lft;
if (gpa->lft != NULL) gpa->lft->par = top;
if (gpa->lft != NULL)
gpa->lft->par = top;
gpa->lft = top;
gpa->par = top->par;
top->par = gpa;
294,13 → 304,13
}
/** Delete node from AVL tree.
/** Delete a node from the AVL tree.
*
* Because of allowed multiple identical keys parent pointers are essential
* during deletition.
* Because multiple identical keys are allowed, the parent pointers are
* essential during deletion.
*
* @param t AVL tree structure.
* @param node Address of node which will be deleted.
* @param node Address of the node which will be deleted.
*/
void avltree_delete(avltree_t *t, avltree_node_t *node)
{
312,60 → 322,62
ASSERT(t);
ASSERT(node);
if (node->lft == NULL) {
if (node->rgt) {
/*
* Replace node with its only right son.
* Replace the node with its only right son.
*
* Balance of right son will be repaired in balancing cycle.
* Balance of the right son will be repaired in the
* balancing cycle.
*/
cur = node->rgt;
cur->par = node->par;
gpa = cur;
dir = AVLTREE_RIGHT;
dir = RIGHT;
cur->balance = node->balance;
} else {
if (node->par == NULL) {
/*
* Tree has only one node - it will be empty tree and balancing can end.
* The tree has only one node - it will become
* an empty tree and the balancing can end.
*/
t->root = NULL;
return;
}
/*
* Node has no child, will be deleted with no substitution.
* The node has no child, it will be deleted with no
* substitution.
*/
gpa = node->par;
cur = NULL;
dir = (gpa->lft == node)? AVLTREE_LEFT: AVLTREE_RIGHT;
dir = (gpa->lft == node) ? LEFT: RIGHT;
}
} else {
/*
* Node has left and right son. Find a node with smallest key in left subtree
* and replace deleted node with that node.
* 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.
*/
for (cur = node->lft; cur->rgt != NULL; cur = cur->rgt)
;
//cur obsahuje uzel, ktery vlozim misto uzlu node
if (cur != node->lft) {
/*
* The most right node of deleted node's left subtree was found. Replace
* deleted node with this node. Cutting founded node has two cases in
* dependence on its left son.
* The rightmost node of the deleted node's left subtree
* was found. Replace the deleted node with this node.
* Cutting off of the found node has two cases that
* depend on its left son.
*/
if (cur->lft) {
/*
* Founded node has left son.
* The found node has a left son.
*/
gpa = cur->lft;
gpa->par = cur->par;
dir = AVLTREE_LEFT;
dir = LEFT;
gpa->balance = cur->balance;
} else {
dir = AVLTREE_RIGHT;
dir = RIGHT;
gpa = cur->par;
}
cur->par->rgt = cur->lft;
373,12 → 385,14
cur->lft->par = cur;
} else {
/*
* Left son of node hasn't got right son. Left son will take deleted node's place.
* The left son of the node hasn't got a right son. The
* left son will take the deleted node's place.
*/
dir = AVLTREE_LEFT;
dir = LEFT;
gpa = cur;
}
if (node->rgt) node->rgt->par = cur;
if (node->rgt)
node->rgt->par = cur;
cur->rgt = node->rgt;
cur->balance = node->balance;
cur->par = node->par;
385,7 → 399,8
}
/*
* Repair parent nodes pointer which pointed previously to deleted node.
* Repair the parent node's pointer which pointed previously to the
* deleted node.
*/
if (node->par == NULL) {
t->root = cur;
398,22 → 413,24
}
/*
* Repair cycle which repairs balances of nodes in way from cutted noded down to root.
* Repair cycle which repairs balances of nodes on the way from from the
* cut-off node up to the root.
*/
for(;;) {
if (dir == AVLTREE_LEFT) {
for (;;) {
if (dir == LEFT) {
/*
* Deletition was made in left subtree.
* Deletion was made in the left subtree.
*/
gpa->balance++;
if (gpa->balance == +1) {
if (gpa->balance == 1) {
/*
* Stop balancing, tree is balanced.
* Stop balancing, the tree is balanced.
*/
break;
} else if (gpa->balance == +2) {
} else if (gpa->balance == 2) {
/*
* Bad balance, heights of left and right subtrees differs more then is allowed.
* Bad balance, heights of left and right
* subtrees differ more than by one.
*/
par = gpa->rgt;
429,22 → 446,27
cur->lft = gpa;
/*
* Repair balances and paternity of childs in dependence on
* balance factor of grand child (cur).
* Repair balances and paternity of
* children, depending on the balance
* factor of the grand child (cur).
*/
if (cur->balance == +1) {
if (cur->balance == 1) {
par->balance = 0;
gpa->balance = -1;
if (gpa->rgt) gpa->rgt->par = gpa;
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;
if (gpa->rgt)
gpa->rgt->par = gpa;
if (par->lft)
par->lft->par = par;
} else {
par->balance = +1;
par->balance = 1;
gpa->balance = 0;
if (par->lft) par->lft->par = par;
if (par->lft)
par->lft->par = par;
gpa->rgt->par = gpa;
}
cur->balance = 0;
457,20 → 479,24
par->par = cur;
/*
* Repair pointer which pointed to balanced node. If it was root then balancing
* is finished else continue in next iteration (parent node).
* 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;
break;
} else
} else {
if (cur->par->lft == gpa) {
cur->par->lft = cur;
dir = AVLTREE_LEFT;
dir = LEFT;
} else {
cur->par->rgt = cur;
dir = AVLTREE_RIGHT;
dir = RIGHT;
}
}
gpa = cur->par;
} else {
/*
478,7 → 504,8
*/
gpa->rgt = par->lft;
if (par->lft) par->lft->par = gpa;
if (par->lft)
par->lft->par = gpa;
par->lft = gpa;
/*
489,41 → 516,56
if (par->balance == 0) {
/*
* Right child of balanced node is balanced, after RR rotation is done, whole
* tree will be balanced.
* The right child of the
* balanced node is balanced,
* after RR rotation is done,
* the whole tree will be
* balanced.
*/
par->balance = -1;
gpa->balance = +1;
gpa->balance = 1;
/*
* Repair pointer which pointed to balanced node and finish balancing.
* 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 {
if (par->par->lft ==
gpa) {
par->par->lft =
par;
} else {
par->par->rgt = par;
par->par->rgt =
par;
}
}
break;
} else {
par->balance = gpa->balance = 0;
/*
* Repair pointer which pointed to balanced node. If it was root then balancing
* is finished else continue in next iteration (parent node).
* 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;
break;
} else {
if (par->par->lft == gpa) {
par->par->lft = par;
dir = AVLTREE_LEFT;
} else {
if (par->par->lft ==
gpa) {
par->par->lft =
par;
dir = LEFT;
} else {
par->par->rgt = par;
dir = AVLTREE_RIGHT;
par->par->rgt =
par;
dir = RIGHT;
}
}
}
531,35 → 573,39
}
} else {
/*
* Repair pointer which pointed to balanced node. If it was root then balancing
* is finished else continue in next iteration (parent node).
* Repair the pointer which pointed to the
* balanced node. If it was root then balancing
* is finished else continue with the next
* iteration (parent node).
*/
if (!gpa->par) break;
if (!gpa->par)
break;
if (gpa->par->lft == gpa) {
dir = AVLTREE_LEFT;
dir = LEFT;
} else {
dir = AVLTREE_RIGHT;
dir = RIGHT;
}
gpa = gpa->par;
}
} else {
/*
* Deletition was made in right subtree.
* Deletion was made in the right subtree.
*/
gpa->balance--;
if (gpa->balance == -1) {
/*
* Stop balancing, tree is balanced.
* Stop balancing, the tree is balanced.
*/
break;
} else if (gpa->balance == -2) {
/*
* Bad balance, heights of left and right subtrees differs more then is allowed.
* Bad balance, heights of left and right
* subtrees differ more than by one.
*/
par = gpa->lft;
if (par->balance == +1) {
if (par->balance == 1) {
/*
* LR rotation.
*/
571,22 → 617,27
cur->rgt = gpa;
/*
* Repair balances and paternity of childs in dependence on
* balance factor of grand child (cur).
* Repair balances and paternity of
* 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;
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;
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;
if (par->rgt)
par->rgt->par = par;
gpa->lft->par = gpa;
}
cur->balance = 0;
599,20 → 650,24
par->par = cur;
/*
* Repair pointer which pointed to balanced node. If it was root then balancing
* is finished else continue in next iteration (parent node).
* 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
} else {
if (cur->par->lft == gpa) {
cur->par->lft = cur;
dir = AVLTREE_LEFT;
dir = LEFT;
} else {
cur->par->rgt = cur;
dir = AVLTREE_RIGHT;
dir = RIGHT;
}
}
gpa = cur->par;
} else {
/*
620,7 → 675,8
*/
gpa->lft = par->rgt;
if (par->rgt) par->rgt->par = gpa;
if (par->rgt)
par->rgt->par = gpa;
par->rgt = gpa;
/*
* Repair paternity.
630,41 → 686,57
if (par->balance == 0) {
/*
* Left child of balanced node is balanced, after RR rotation is done, whole
* tree will be balanced.
* The left child of the
* balanced node is balanced,
* after LL rotation is done,
* the whole tree will be
* balanced.
*/
par->balance = +1;
par->balance = 1;
gpa->balance = -1;
/*
* Repair pointer which pointed to balanced node and finish balancing.
* 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 {
if (par->par->lft ==
gpa) {
par->par->lft =
par;
} else {
par->par->rgt = par;
par->par->rgt =
par;
}
}
break;
} else {
par->balance = gpa->balance = 0;
/*
* Repair pointer which pointed to balanced node. If it was root then balancing
* is finished else continue in next iteration (parent node).
* 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;
break;
} else {
if (par->par->lft == gpa) { //v cyklu jsem ani jednou neskocil - cur nema praveho syna
par->par->lft = par;
dir = AVLTREE_LEFT;
if (par->par->lft ==
gpa) {
par->par->lft =
par;
dir = LEFT;
} else {
par->par->rgt = par;
dir = AVLTREE_RIGHT;
par->par->rgt =
par;
dir = RIGHT;
}
}
}
672,15 → 744,18
}
} else {
/*
* Repair pointer which pointed to balanced node. If it was root then balancing
* is finished else continue in next iteration (parent node).
* 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 (!gpa->par) break;
if (!gpa->par)
break;
if (gpa->par->lft == gpa) {
dir = AVLTREE_LEFT;
dir = LEFT;
} else {
dir = AVLTREE_RIGHT;
dir = RIGHT;
}
gpa = gpa->par;
}
689,7 → 764,7
}
/** Delete node from AVL tree with the smallest key.
/** Delete a node with the smallest key from the AVL tree.
*
* @param t AVL tree structure.
*/
698,20 → 773,22
avltree_node_t *node;
/*
* Start search of smallest key in tree in the root node and
* continue in cycle to the most left node in the tree which
* must have smallest key.
* Start searching for the smallest key in the tree starting in the root
* node and continue in cycle to the leftmost node in the tree (which
* must have the smallest key).
*/
node = t->root;
if (!node) return false;
if (!node)
return false;
while (node->lft != NULL)
node = node->lft;
/*
* Use avltree_delete function to delete node from tree.
*/
avltree_delete(t,node);
avltree_delete(t, node);
return true;
}
/** @}
*/