WebSVN – HelenOS – Diff – /branches/rcu/kernel/generic/include/adt/extavlrel.h


/*
 * Copyright (C) 2007 Vojtech Mencl
 * All rights reserved.
 *
 * Redistribution and use in source and binary forms, with or without
 * modification, are permitted provided that the following conditions
 * are met:
 *
 * - Redistributions of source code must retain the above copyright
 *   notice, this list of conditions and the following disclaimer.
 * - Redistributions in binary form must reproduce the above copyright
 *   notice, this list of conditions and the following disclaimer in the
 *   documentation and/or other materials provided with the distribution.
 * - The name of the author may not be used to endorse or promote products
 *   derived from this software without specific prior written permission.
 *
 * THIS SOFTWARE IS PROVIDED BY THE AUTHOR ``AS IS'' AND ANY EXPRESS OR
 * IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES
 * OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED.
 * IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY DIRECT, INDIRECT,
 * INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT
 * NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
 * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
 * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
 * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF
 * THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
 */
 
/** @addtogroup genericadt
 * @{
 */
/** @file
 */
 
 
#ifndef KERN_EXTAVLRELTREE_H_
#define KERN_EXTAVLRELTREE_H_
 
#include <arch/types.h>
 
typedef struct extavlreltree_node extavlreltree_node_t;
typedef struct extavlreltree extavlreltree_t;
 
 
/*
 * Makro for getting pointer to structure which enclosure extavlreltree structure.
 *
 * @param link Pointer to extavlreltree structure.
 * @param type Name of outer structure.
 * @param member Name of extavlreltree atribute in outer structure.
 */
#define extavlreltree_get_instance(link,type,member) \
    ((type *)(((uint8_t *)(link)) - ((uint8_t *)&(((type *)NULL)->member))))
 
 
 
/** Relative key Extended AVL tree node structure. */
struct extavlreltree_node
{
    /**
     * Pointer to left descendand of this node.
     *
     * All keys of nodes in the left subtree are less then key of this node.
     */
    extavlreltree_node_t *lft;
 
    /**
     * Pointer to right descendand of this node.
     *
     * All keys of nodes in the right subtree are greater then key of this node.
     */
    extavlreltree_node_t *rgt;  
   
    /** Pointer to parent node. Root node has NULL parent. */
    extavlreltree_node_t *par;  
 
    /** Pointer to next node which has equal or the closest greater key or head. */
    extavlreltree_node_t *next;
   
    /** Pointer to previous node which has equal or the closest lesser key or head. */
    extavlreltree_node_t *prev;
   
    /** Height of left subtree. */
    int16_t lft_height;
 
    /** Height of right subtree. */
    int16_t rgt_height;    
 
    /** Nodes key. */
    uint64_t key;
 
    /** Sum of all keys in the right subtree. */
    uint64_t rgt_sum;
};
 
/** Relative key Extended AVL tree structure (ExtAvlrel). */
 
struct extavlreltree
{
    /*
     * ExtAvlrel root node pointer.
     *
     * Important only for recognition of non tree node.
     */
    extavlreltree_node_t *root;
 
    /** Head of doubly linked list of nodes. It is entrance point to the tree. */
    extavlreltree_node_t head;
};
 
 
 
/** Create empty Extended AVL tree.
 *
 * @param t Extended AVL tree structure.
 */
static inline void extavlreltree_create (extavlreltree_t *t)
{
    t->root = NULL;
 
    t->head.next = &t->head;
    t->head.prev = &t->head;
}
 
/** Initialize node.
 *
 * @param node Node which is initialized.
 */
static inline void extavlreltree_node_initialize(extavlreltree_node_t *node)
{
    node->lft = NULL;
    node->rgt = NULL;
    node->lft_height = 0;
    node->rgt_height = 0;
    node->par = NULL;
    node->next = node;
    node->prev = node;
    node->rgt_sum = 0;
}
 
extavlreltree_node_t *extavlreltree_search(extavlreltree_t *t, uint64_t key);
void extavlreltree_insert(extavlreltree_t *t, extavlreltree_node_t *newnode);
void extavlreltree_delete(extavlreltree_t *t, extavlreltree_node_t *node);
bool extavlreltree_delete_min(extavlreltree_t *t);
 
#endif
 
/** @}
 */
 

Rev 2416	Rev 2421
1	/*	1	/*
2	* Copyright (C) 2006 Vojtech Mencl	2	* Copyright (C) 2007 Vojtech Mencl
3	* All rights reserved.	3	* All rights reserved.
4	*	4	*
5	* Redistribution and use in source and binary forms, with or without	5	* Redistribution and use in source and binary forms, with or without
6	* modification, are permitted provided that the following conditions	6	* modification, are permitted provided that the following conditions
7	* are met:	7	* are met:
8	*	8	*
9	* - Redistributions of source code must retain the above copyright	9	* - Redistributions of source code must retain the above copyright
10	* notice, this list of conditions and the following disclaimer.	10	* notice, this list of conditions and the following disclaimer.
11	* - Redistributions in binary form must reproduce the above copyright	11	* - Redistributions in binary form must reproduce the above copyright
12	* notice, this list of conditions and the following disclaimer in the	12	* notice, this list of conditions and the following disclaimer in the
13	* documentation and/or other materials provided with the distribution.	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	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.	15	* derived from this software without specific prior written permission.
16	*	16	*
17	* THIS SOFTWARE IS PROVIDED BY THE AUTHOR ``AS IS'' AND ANY EXPRESS OR	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	18	* IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES
19	* OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED.	19	* OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED.
20	* IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY DIRECT, INDIRECT,	20	* IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY DIRECT, INDIRECT,
21	* INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT	21	* INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT
22	* NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,	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	23	* DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
24	* THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT	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	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.	26	* THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
27	*/	27	*/
28		28
29	/** @addtogroup genericadt	29	/** @addtogroup genericadt
30	* @{	30	* @{
31	*/	31	*/
32	/** @file	32	/** @file
33	*/	33	*/
34		34
35		35
36	#ifndef KERN_EXTAVLRELTREE_H_	36	#ifndef KERN_EXTAVLRELTREE_H_
37	#define KERN_EXTAVLRELTREE_H_	37	#define KERN_EXTAVLRELTREE_H_
38		38
39	#include <arch/types.h>	39	#include <arch/types.h>
40		40
41	typedef struct extavlreltree_node extavlreltree_node_t;	41	typedef struct extavlreltree_node extavlreltree_node_t;
42	typedef struct extavlreltree extavlreltree_t;	42	typedef struct extavlreltree extavlreltree_t;
43		43
44		44
45	/*	45	/*
46	* Makro for getting pointer to structure which enclosure extavlreltree structure.	46	* Makro for getting pointer to structure which enclosure extavlreltree structure.
47	*	47	*
48	* @param link Pointer to extavlreltree structure.	48	* @param link Pointer to extavlreltree structure.
49	* @param type Name of outer structure.	49	* @param type Name of outer structure.
50	* @param member Name of extavlreltree atribute in outer structure.	50	* @param member Name of extavlreltree atribute in outer structure.
51	*/	51	*/
52	#define extavlreltree_get_instance(link,type,member) \	52	#define extavlreltree_get_instance(link,type,member) \
53	((type )(((uint8_t )(link)) - ((uint8_t )&(((type )NULL)->member))))	53	((type )(((uint8_t )(link)) - ((uint8_t )&(((type )NULL)->member))))
54		54
55		55
56		56
57	/** Relative key Extended AVL tree node structure. */	57	/** Relative key Extended AVL tree node structure. */
58	struct extavlreltree_node	58	struct extavlreltree_node
59	{	59	{
60	/**	60	/**
61	* Pointer to left descendand of this node.	61	* Pointer to left descendand of this node.
62	*	62	*
63	* All keys of nodes in the left subtree are less then key of this node.	63	* All keys of nodes in the left subtree are less then key of this node.
64	*/	64	*/
65	extavlreltree_node_t *lft;	65	extavlreltree_node_t *lft;
66		66
67	/**	67	/**
68	* Pointer to right descendand of this node.	68	* Pointer to right descendand of this node.
69	*	69	*
70	* All keys of nodes in the right subtree are greater then key of this node.	70	* All keys of nodes in the right subtree are greater then key of this node.
71	*/	71	*/
72	extavlreltree_node_t *rgt;	72	extavlreltree_node_t *rgt;
73		73
74	/** Pointer to parent node. Root node has NULL parent. */	74	/** Pointer to parent node. Root node has NULL parent. */
75	extavlreltree_node_t *par;	75	extavlreltree_node_t *par;
76		76
77	/** Pointer to next node which has equal or the closest greater key or head. */	77	/** Pointer to next node which has equal or the closest greater key or head. */
78	extavlreltree_node_t *next;	78	extavlreltree_node_t *next;
79		79
80	/** Pointer to previous node which has equal or the closest lesser key or head. */	80	/** Pointer to previous node which has equal or the closest lesser key or head. */
81	extavlreltree_node_t *prev;	81	extavlreltree_node_t *prev;
82		82
83	/** Height of left subtree. */	83	/** Height of left subtree. */
84	int16_t lft_height;	84	int16_t lft_height;
85		85
86	/** Height of right subtree. */	86	/** Height of right subtree. */
87	int16_t rgt_height;	87	int16_t rgt_height;
88		88
89	/** Nodes key. */	89	/** Nodes key. */
90	uint64_t key;	90	uint64_t key;
91		91
92	/** Sum of all keys in the right subtree. */	92	/** Sum of all keys in the right subtree. */
93	uint64_t rgt_sum;	93	uint64_t rgt_sum;
94	};	94	};
95		95
96	/** Relative key Extended AVL tree structure (ExtAvlrel). */	96	/** Relative key Extended AVL tree structure (ExtAvlrel). */
97	#ifdef AVLTREE_TEST	-
98	struct extavlreltree	97	struct extavlreltree
99	{	98	{
100	/*	99	/*
101	* ExtAvlrel root node pointer.	100	* ExtAvlrel root node pointer.
102	*	101	*
103	* Important only for recognition of non tree node.	102	* Important only for recognition of non tree node.
104	*/	103	*/
105	extavlreltree_node_t *root;	104	extavlreltree_node_t *root;
106		105
107	/** Head of doubly linked list of nodes. It is entrance point to the tree. */	106	/** Head of doubly linked list of nodes. It is entrance point to the tree. */
108	extavlreltree_node_t head;	107	extavlreltree_node_t head;
109	};	108	};
110		109
111		110
112		111
113	/** Create empty Extended AVL tree.	112	/** Create empty Extended AVL tree.
114	*	113	*
115	* @param t Extended AVL tree structure.	114	* @param t Extended AVL tree structure.
116	*/	115	*/
117	void extavlreltree_create (extavlreltree_t *t)	116	static inline void extavlreltree_create (extavlreltree_t *t)
118	{	117	{
119	t->root = NULL;	118	t->root = NULL;
120		119
121	t->head.next = &t->head;	120	t->head.next = &t->head;
122	t->head.prev = &t->head;	121	t->head.prev = &t->head;
123	}	122	}
124		123
125	/** Initialize node.	124	/** Initialize node.
126	*	125	*
127	* @param node Node which is initialized.	126	* @param node Node which is initialized.
128	*/	127	*/
129	void extavlreltree_node_initialize(extavlreltree_node_t *node)	128	static inline void extavlreltree_node_initialize(extavlreltree_node_t *node)
130	{	129	{
131	node->lft = NULL;	130	node->lft = NULL;
132	node->rgt = NULL;	131	node->rgt = NULL;
133	node->lft_height = 0;	132	node->lft_height = 0;
134	node->rgt_height = 0;	133	node->rgt_height = 0;
135	node->par = NULL;	134	node->par = NULL;
136	node->next = node;	135	node->next = node;
137	node->prev = node;	136	node->prev = node;
138	node->rgt_sum = 0;	137	node->rgt_sum = 0;
139	}	138	}
140		139
141	extavlreltree_node_t extavlreltree_search(extavlreltree_t t, uint64_t key);	140	extavlreltree_node_t extavlreltree_search(extavlreltree_t t, uint64_t key);
142	void extavlreltree_insert(extavlreltree_t t, extavlreltree_node_t newnode);	141	void extavlreltree_insert(extavlreltree_t t, extavlreltree_node_t newnode);
143	void extavlreltree_delete(extavlreltree_t t, extavlreltree_node_t node);	142	void extavlreltree_delete(extavlreltree_t t, extavlreltree_node_t node);
144	bool extavlreltree_delete_min(extavlreltree_t *t);	143	bool extavlreltree_delete_min(extavlreltree_t *t);
145		144
146	#endif	145	#endif
147		146
148	/** @}	147	/** @}
149	*/	148	*/
150		149

Subversion Repositories HelenOS

(root)/branches/rcu/kernel/generic/include/adt/extavlrel.h – Rev 2416 → 2421