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/kernel/generic/src/adt @ 2416

  → /branches/rcu/kernel/generic/src/adt/ @ 2421

  ↔ Reverse comparison

• Compare Path:	Rev

  With Path:	Rev

Ignore whitespace Rev 2416 → Rev 2421

/branches/rcu/kernel/generic/src/adt/avl.c
1,5 → 1,5
/*
* Copyright (c) 2006 Vojtech Mencl
* Copyright (c) 2007 Vojtech Mencl
* All rights reserved.
*
* Redistribution and use in source and binary forms, with or without
61,7 → 61,7
* @param t AVL tree.
* @param key Key to be searched.
*
* @return Pointer to value or NULL if there is no such key.
* @return Pointer to node or NULL if there is no such key.
*/
avltree_node_t *avltree_search(avltree_t *t, uint64_t key)
{
84,6 → 84,30
}
/** Find node with smallest key in AVL tree.
*
* @param t AVL tree.
*
* @return Pointer to node or NULL if there is no node in the tree.
*/
avltree_node_t *avltree_find_min(avltree_t *t)
{
avltree_node_t *p = t->root;
/*
* Check whether tree is empty.
*/
if (!p) return NULL;
/*
* Iteratively descend to the leftmost leaf in the tree.
*/
while (p->lft != NULL)
p = p->lft;
return p;
}
/** Insert new node into AVL tree.
*
* @param t AVL tree.
114,7 → 138,7
dpc = &t->root;
gpa = NULL;
top = t->root;
while (par = *dpc) {
while ((par = (*dpc)) != NULL) {
if (par->balance != 0) {
top = par;
}
670,7 → 694,7
*
* @param t AVL tree structure.
*/
avltree_node_t *avltree_delete_min(avltree_t *t)
bool avltree_delete_min(avltree_t *t)
{
avltree_node_t *node;
uint64_t key;

/branches/rcu/kernel/generic/src/adt/extavl.c
63,7 → 63,7
* @param t Extended AVL tree.
* @param key Key to be searched.
*
* @return Pointer to value or NULL if there is no such key.
* @return Pointer to node or NULL if there is no such key.
*/
extavltree_node_t *extavltree_search(extavltree_t *t, uint64_t key)
{

/branches/rcu/kernel/generic/src/adt/extavlrel.c
60,7 → 60,7
/* Returns height of tree -1 */
#define extavlreltree_tree_height(node) ((node) == NULL) ? (-1) : max(((node)->lft_height),((node)->rgt_height))
#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.
*
67,9 → 67,9
* @param t ExtAVLrel tree.
* @param key Key to be searched.
*
* @return Pointer to value or NULL if there is no such key.
* @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 *extavlreltree_search(extavlreltree_t *t, uint64_t key)
{
extavlreltree_node_t *cur;
uint64_t sum, s;
492,7 → 492,7
extavlreltree_node_t *gpa;
int8_t dir;
int8_t dir2=0;
uint64_t key;
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
700,7 → 700,7
if (gpa->par->lft == gpa) {
gpapar = &(gpa->par->lft);
dir2 = AVLTREE_LEFT;
repair_rgt_sum = falsi;
repair_rgt_sum = false;
} else {
gpapar = &(gpa->par->rgt);
dir2 = AVLTREE_RIGHT;