WebSVN – HelenOS – Blame – //branches/rcu/kernel/generic/include/adt/favl.h

Rev	Author	Line No.	Line
2466	mencl	1	/*
		2	* Copyright (C) 2007 Vojtech 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
		36	#ifndef KERN_FAVLTREE_H_
		37	#define KERN_FAVLTREE_H_
		38
		39	#include <arch/types.h>
		40
		41	/*
		42	* Makro for getting pointer to structure which enclosure favltree structure.
		43	*
		44	* @param link Pointer to avltree structure.
		45	* @param type Name of outer structure.
		46	* @param member Name of avltree atribute in outer structure.
		47	*/
		48	#define favltree_get_instance(link,type,member) \
		49	((type )(((uint8_t )(link)) - ((uint8_t )&(((type )NULL)->member))))
		50
		51
		52	typedef struct favltree_node favltree_node_t;
		53	typedef struct favltree favltree_t;
		54
		55
		56	/** FAVL tree node structure. */
		57	struct favltree_node
		58	{
		59	/**
		60	* Pointer to left descendand of this node.
		61	*
		62	* All keys of nodes in the left subtree are less then key of this node.
		63	*/
		64	struct favltree_node *lft;
		65
		66	/**
		67	* Pointer to right descendand of this node.
		68	*
		69	* All keys of nodes in the right subtree are greater then key of this node.
		70	*/
		71	struct favltree_node *rgt;
		72
		73	/** Pointer to parent node. Root node has NULL parent. */
		74	struct favltree_node *par;
		75
		76	/** Nodes key. */
		77	uint64_t key;
		78
		79	/** Difference between heights of left and right subtree of this node.*/
		80	int8_t balance;
		81	};
		82
		83	/** FAVL tree structure. */
		84	struct favltree
		85	{
		86	/** FAVL root node pointer */
		87	struct favltree_node *root;
		88
		89	/** Pointer to node with minimal key. */
		90	struct favltree_node *first;
		91
		92	/**
		93	* Base of tree is value that is smaller or equal then every value in tree
		94	* (valid for positive keys otherwise ignore this atribute).
		95	*
		96	* Base is added to current key when new node is inserted into tree.
		97	* Base is changed to the key of node which is deleted with function
		98	* avltree_delete_min.
		99	*/
		100	uint64_t base;
		101	};
		102
		103
		104	/** Create empty FAVL tree.
		105	*
		106	* @param t FAVL tree.
		107	*/
		108	static inline void favltree_create (favltree_t *t)
		109	{
		110	t->root = NULL;
		111	t->first = NULL;
		112	t->base = 0;
		113	}
		114
		115	/** Initialize node.
		116	*
		117	* @param Node which is initialized.
		118	*/
		119	static inline void favltree_node_initialize(favltree_node_t *node)
		120	{
		121	node->key = 0;
		122	node->lft = NULL;
		123	node->rgt = NULL;
		124	node->par = NULL;
		125	node->balance = 0;
		126	}
		127
		128	/** Find node with smallest key in tree.
		129	*
		130	* @param t FAVL tree.
		131	* @return Pointer to node with smallest key or if tree is empty then returns NULL.
		132	*/
		133	static inline favltree_node_t favltree_find_min(favltree_t t)
		134	{
		135	return t->first;
		136	}
		137
		138	favltree_node_t favltree_search(favltree_t t, uint64_t key);
		139	void favltree_insert(favltree_t t, favltree_node_t newnode);
		140	void favltree_delete(favltree_t t, favltree_node_t node);
		141	bool favltree_delete_min(favltree_t *t);
		142
		143	#endif
		144
		145	/** @}
		146	*/

Subversion Repositories HelenOS

(root)//branches/rcu/kernel/generic/include/adt/favl.h – Rev 2466