WebSVN – HelenOS – Diff – /trunk/kernel/generic/include/adt/avl.h



 * @{
 */
/** @file
 */
 
 
#ifndef KERN_AVLTREE_H_
#define KERN_AVLTREE_H_ 
 
#include <arch/types.h>
 

 *
 * @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(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
{
    /**

   
    /** Pointer to the parent node. Root node has NULL parent. */
    struct avltree_node *par;
   
    /** Node's key. */
    avltree_key_t key;
   
    /**
     * Difference between the heights of the left and the right subtree of
     * this node.
     */

     *  
     * 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().
     */
    avltree_key_t base;
};
 
 
/** Create empty AVL tree.
 *
 * @param t AVL tree.
 */
static inline void avltree_create(avltree_t *t)
{
    t->root = NULL;
    t->base = 0;
}
 

    node->par = NULL;
    node->balance = 0;
}
 
extern avltree_node_t *avltree_find_min(avltree_t *t);
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
 
/** @}
 */

Rev 2499	Rev 2501
Line 30...	Line 30...
30	* @{	30	* @{
31	*/	31	*/
32	/** @file	32	/** @file
33	*/	33	*/
34		34
35		-
36	#ifndef KERN_AVLTREE_H_	35	#ifndef KERN_AVLTREE_H_
37	#define KERN_AVLTREE_H_	36	#define KERN_AVLTREE_H_
38		37
39	#include <arch/types.h>	38	#include <arch/types.h>
40		39
Line 44...	Line 43...
44	*	43	*
45	* @param link Pointer to the avltree structure.	44	* @param link Pointer to the avltree structure.
46	* @param type Name of the outer structure.	45	* @param type Name of the outer structure.
47	* @param member Name of avltree attribute in the outer structure.	46	* @param member Name of avltree attribute in the outer structure.
48	*/	47	*/
49	#define avltree_get_instance(link, type, member) \	48	#define avltree_get_instance(node, type, member) \
50	((type )(((uint8_t )(link)) - ((uint8_t ) &(((type ) NULL)->member))))	49	((type )(((uint8_t )(node)) - ((uint8_t ) &(((type ) NULL)->member))))
51		-
52		50
53	typedef struct avltree_node avltree_node_t;	51	typedef struct avltree_node avltree_node_t;
54	typedef struct avltree avltree_t;	52	typedef struct avltree avltree_t;
55		53
-		54	typedef uint64_t avltree_key_t;
-		55
-		56	typedef void (* avltree_walker_t)(avltree_node_t *);
56		57
57	/** AVL tree node structure. */	58	/** AVL tree node structure. */
58	struct avltree_node	59	struct avltree_node
59	{	60	{
60	/**	61	/**
Line 75...	Line 76...
75		76
76	/** Pointer to the parent node. Root node has NULL parent. */	77	/** Pointer to the parent node. Root node has NULL parent. */
77	struct avltree_node *par;	78	struct avltree_node *par;
78		79
79	/** Node's key. */	80	/** Node's key. */
80	uint64_t key;	81	avltree_key_t key;
81		82
82	/**	83	/**
83	* Difference between the heights of the left and the right subtree of	84	* Difference between the heights of the left and the right subtree of
84	* this node.	85	* this node.
85	*/	86	*/
Line 98...	Line 99...
98	*	99	*
99	* The base is added to the current key when a new node is inserted into	100	* The base is added to the current key when a new node is inserted into
100	* the tree. The base is changed to the key of the node which is deleted	101	* the tree. The base is changed to the key of the node which is deleted
101	* with avltree_delete_min().	102	* with avltree_delete_min().
102	*/	103	*/
103	uint64_t base;	104	avltree_key_t base;
104	};	105	};
105		106
106		107
107	/** Create empty AVL tree.	108	/** Create empty AVL tree.
108	*	109	*
109	* @param t AVL tree.	110	* @param t AVL tree.
110	*/	111	*/
111	static inline void avltree_create (avltree_t *t)	112	static inline void avltree_create(avltree_t *t)
112	{	113	{
113	t->root = NULL;	114	t->root = NULL;
114	t->base = 0;	115	t->base = 0;
115	}	116	}
116		117
Line 126...	Line 127...
126	node->par = NULL;	127	node->par = NULL;
127	node->balance = 0;	128	node->balance = 0;
128	}	129	}
129		130
130	extern avltree_node_t avltree_find_min(avltree_t t);	131	extern avltree_node_t avltree_find_min(avltree_t t);
131	extern avltree_node_t avltree_search(avltree_t t, uint64_t key);	132	extern avltree_node_t avltree_search(avltree_t t, avltree_key_t key);
132	extern void avltree_insert(avltree_t t, avltree_node_t newnode);	133	extern void avltree_insert(avltree_t t, avltree_node_t newnode);
133	extern void avltree_delete(avltree_t t, avltree_node_t node);	134	extern void avltree_delete(avltree_t t, avltree_node_t node);
134	extern bool avltree_delete_min(avltree_t *t);	135	extern bool avltree_delete_min(avltree_t *t);
-		136	extern void avltree_walk(avltree_t *t, avltree_walker_t walker);
135		137
136	#endif	138	#endif
137		139
138	/** @}	140	/** @}
139	*/	141	*/

Subversion Repositories HelenOS

(root)/trunk/kernel/generic/include/adt/avl.h – Rev 2499 → 2501