Subversion Repositories HelenOS

Compare Revisions

Ignore whitespace Rev 2500 → Rev 2501

/trunk/kernel/generic/include/adt/avl.h
32,7 → 32,6
/** @file
*/
 
 
#ifndef KERN_AVLTREE_H_
#define KERN_AVLTREE_H_
 
46,14 → 45,16
* @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(node, type, member) \
((type *)(((uint8_t *)(node)) - ((uint8_t *) &(((type *) NULL)->member))))
 
 
typedef struct avltree_node avltree_node_t;
typedef struct avltree avltree_t;
 
typedef uint64_t avltree_key_t;
 
typedef void (* avltree_walker_t)(avltree_node_t *);
 
/** AVL tree node structure. */
struct avltree_node
{
77,7 → 78,7
struct avltree_node *par;
/** Node's key. */
uint64_t key;
avltree_key_t key;
/**
* Difference between the heights of the left and the right subtree of
100,7 → 101,7
* the tree. The base is changed to the key of the node which is deleted
* with avltree_delete_min().
*/
uint64_t base;
avltree_key_t base;
};
 
 
108,7 → 109,7
*
* @param t AVL tree.
*/
static inline void avltree_create (avltree_t *t)
static inline void avltree_create(avltree_t *t)
{
t->root = NULL;
t->base = 0;
128,10 → 129,11
}
 
extern avltree_node_t *avltree_find_min(avltree_t *t);
extern avltree_node_t *avltree_search(avltree_t *t, uint64_t key);
extern avltree_node_t *avltree_search(avltree_t *t, avltree_key_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);
extern void avltree_walk(avltree_t *t, avltree_walker_t walker);
 
#endif
 
/trunk/kernel/generic/src/adt/avl.c
52,11 → 52,9
#include <adt/avl.h>
#include <debug.h>
 
 
#define LEFT 0
#define RIGHT 1
 
 
/** Search for the first occurence of the given key in an AVL tree.
*
* @param t AVL tree.
64,7 → 62,7
*
* @return Pointer to a node or NULL if there is no such key.
*/
avltree_node_t *avltree_search(avltree_t *t, uint64_t key)
avltree_node_t *avltree_search(avltree_t *t, avltree_key_t key)
{
avltree_node_t *p;
120,7 → 118,7
avltree_node_t *gpa;
avltree_node_t *top;
avltree_node_t **dpc;
uint64_t key;
avltree_key_t key;
 
ASSERT(t);
ASSERT(newnode);
707,6 → 705,26
return true;
}
 
static void _avltree_walk(avltree_node_t *node, avltree_walker_t walker)
{
if (node->lft)
_avltree_walk(node->lft, walker);
walker(node);
if (node->rgt)
_avltree_walk(node->rgt, walker);
}
 
/** Walk the AVL tree and apply the walker function on each visited node.
*
* @param t AVL tree to be walked.
* @param walker Walker function that will be called on each visited
* node.
*/
void avltree_walk(avltree_t *t, avltree_walker_t walker)
{
_avltree_walk(t->root, walker);
}
 
/** @}
*/