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

Rev	Author	Line No.	Line
2416	mencl	1	/*
2461	mencl	2	* Copyright (C) 2007 Vojtech Mencl
2416	mencl	3	* All rights reserved.
		4	*
		5	* Redistribution and use in source and binary forms, with or without
		6	* modification, are permitted provided that the following conditions
		7	* are met:
		8	*
		9	* - Redistributions of source code must retain the above copyright
		10	* notice, this list of conditions and the following disclaimer.
		11	* - Redistributions in binary form must reproduce the above copyright
		12	* notice, this list of conditions and the following disclaimer in the
		13	* documentation and/or other materials provided with the distribution.
		14	* - The name of the author may not be used to endorse or promote products
		15	* derived from this software without specific prior written permission.
		16	*
		17	* THIS SOFTWARE IS PROVIDED BY THE AUTHOR ``AS IS'' AND ANY EXPRESS OR
		18	* IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES
		19	* OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED.
		20	* IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY DIRECT, INDIRECT,
		21	* INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT
		22	* NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
		23	* DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
		24	* THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
		25	* (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF
		26	* THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
		27	*/
		28
		29	/** @addtogroup genericadt
		30	* @{
		31	*/
		32	/** @file
		33	*/
		34
		35	#ifndef KERN_AVLTREE_H_
		36	#define KERN_AVLTREE_H_
		37
		38	#include <arch/types.h>
		39
2496	jermar	40	/**
		41	* Macro for getting a pointer to the structure which contains the avltree
		42	* structure.
2416	mencl	43	*
2496	jermar	44	* @param link Pointer to the avltree structure.
		45	* @param type Name of the outer structure.
		46	* @param member Name of avltree attribute in the outer structure.
2416	mencl	47	*/
2501	jermar	48	#define avltree_get_instance(node, type, member) \
		49	((type )(((uint8_t )(node)) - ((uint8_t ) &(((type ) NULL)->member))))
2416	mencl	50
		51	typedef struct avltree_node avltree_node_t;
		52	typedef struct avltree avltree_t;
		53
2501	jermar	54	typedef uint64_t avltree_key_t;
2416	mencl	55
2504	jermar	56	typedef bool (* avltree_walker_t)(avltree_node_t , void );
2501	jermar	57
2416	mencl	58	/** AVL tree node structure. */
		59	struct avltree_node
		60	{
		61	/**
2496	jermar	62	* Pointer to the left descendant of this node.
2416	mencl	63	*
2496	jermar	64	* All keys of nodes in the left subtree are less than the key of this
		65	* node.
2416	mencl	66	*/
		67	struct avltree_node *lft;
		68
		69	/**
2496	jermar	70	* Pointer to the right descendant of this node.
2416	mencl	71	*
2496	jermar	72	* All keys of nodes in the right subtree are greater than the key of
		73	* this node.
2416	mencl	74	*/
		75	struct avltree_node *rgt;
		76
2496	jermar	77	/** Pointer to the parent node. Root node has NULL parent. */
2416	mencl	78	struct avltree_node *par;
		79
2496	jermar	80	/** Node's key. */
2501	jermar	81	avltree_key_t key;
2416	mencl	82
2496	jermar	83	/**
		84	* Difference between the heights of the left and the right subtree of
		85	* this node.
		86	*/
2466	mencl	87	int8_t balance;
2416	mencl	88	};
		89
		90	/** AVL tree structure. */
		91	struct avltree
		92	{
		93	/** AVL root node pointer */
		94	struct avltree_node *root;
		95
		96	/**
2496	jermar	97	* Base of the tree is a value that is smaller or equal than every value
		98	* in the tree (valid for positive keys otherwise ignore this atribute).
2416	mencl	99	*
2496	jermar	100	* The base is added to the current key when a new node is inserted into
		101	* the tree. The base is changed to the key of the node which is deleted
		102	* with avltree_delete_min().
2416	mencl	103	*/
2501	jermar	104	avltree_key_t base;
2416	mencl	105	};
		106
		107
		108	/** Create empty AVL tree.
		109	*
		110	* @param t AVL tree.
		111	*/
2501	jermar	112	static inline void avltree_create(avltree_t *t)
2416	mencl	113	{
		114	t->root = NULL;
		115	t->base = 0;
		116	}
		117
		118	/** Initialize node.
		119	*
2496	jermar	120	* @param node Node which is initialized.
2416	mencl	121	*/
		122	static inline void avltree_node_initialize(avltree_node_t *node)
		123	{
		124	node->key = 0;
		125	node->lft = NULL;
		126	node->rgt = NULL;
		127	node->par = NULL;
		128	node->balance = 0;
		129	}
		130
2496	jermar	131	extern avltree_node_t avltree_find_min(avltree_t t);
2501	jermar	132	extern avltree_node_t avltree_search(avltree_t t, avltree_key_t key);
2496	jermar	133	extern void avltree_insert(avltree_t t, avltree_node_t newnode);
		134	extern void avltree_delete(avltree_t t, avltree_node_t node);
		135	extern bool avltree_delete_min(avltree_t *t);
2504	jermar	136	extern void avltree_walk(avltree_t t, avltree_walker_t walker, void arg);
2416	mencl	137
		138	#endif
		139
		140	/** @}
		141	*/

Subversion Repositories HelenOS

(root)/trunk/kernel/generic/include/adt/avl.h – Rev 2504