Rev 2416 | Rev 2461 | Go to most recent revision | Only display areas with differences | Ignore whitespace | Details | Blame | Last modification | View Log | RSS feed
Rev 2416 | Rev 2421 | ||
---|---|---|---|
1 | /* |
1 | /* |
2 | * Copyright (C) 2006 Vojtech Mencl |
2 | * Copyright (C) 2006 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_AVLTREE_H_ |
36 | #ifndef KERN_AVLTREE_H_ |
37 | #define KERN_AVLTREE_H_ |
37 | #define KERN_AVLTREE_H_ |
38 | 38 | ||
39 | #include <arch/types.h> |
39 | #include <arch/types.h> |
40 | 40 | ||
41 | /* |
41 | /* |
42 | * Makro for getting pointer to structure which enclosure avltree structure. |
42 | * Makro for getting pointer to structure which enclosure avltree structure. |
43 | * |
43 | * |
44 | * @param link Pointer to avltree structure. |
44 | * @param link Pointer to avltree structure. |
45 | * @param type Name of outer structure. |
45 | * @param type Name of outer structure. |
46 | * @param member Name of avltree atribute in outer structure. |
46 | * @param member Name of avltree atribute in outer structure. |
47 | */ |
47 | */ |
48 | #define avltree_get_instance(link,type,member) \ |
48 | #define avltree_get_instance(link,type,member) \ |
49 | ((type *)(((uint8_t *)(link)) - ((uint8_t *)&(((type *)NULL)->member)))) |
49 | ((type *)(((uint8_t *)(link)) - ((uint8_t *)&(((type *)NULL)->member)))) |
50 | 50 | ||
51 | 51 | ||
52 | typedef struct avltree_node avltree_node_t; |
52 | typedef struct avltree_node avltree_node_t; |
53 | typedef struct avltree avltree_t; |
53 | typedef struct avltree avltree_t; |
54 | 54 | ||
55 | 55 | ||
56 | /** AVL tree node structure. */ |
56 | /** AVL tree node structure. */ |
57 | struct avltree_node |
57 | struct avltree_node |
58 | { |
58 | { |
59 | /** |
59 | /** |
60 | * Pointer to left descendand of this node. |
60 | * Pointer to left descendand of this node. |
61 | * |
61 | * |
62 | * All keys of nodes in the left subtree are less then key of this node. |
62 | * All keys of nodes in the left subtree are less then key of this node. |
63 | */ |
63 | */ |
64 | struct avltree_node *lft; |
64 | struct avltree_node *lft; |
65 | 65 | ||
66 | /** |
66 | /** |
67 | * Pointer to right descendand of this node. |
67 | * Pointer to right descendand of this node. |
68 | * |
68 | * |
69 | * All keys of nodes in the right subtree are greater then key of this node. |
69 | * All keys of nodes in the right subtree are greater then key of this node. |
70 | */ |
70 | */ |
71 | struct avltree_node *rgt; |
71 | struct avltree_node *rgt; |
72 | 72 | ||
73 | /** Pointer to parent node. Root node has NULL parent. */ |
73 | /** Pointer to parent node. Root node has NULL parent. */ |
74 | struct avltree_node *par; |
74 | struct avltree_node *par; |
75 | 75 | ||
76 | /** Nodes key. */ |
76 | /** Nodes key. */ |
77 | uint64_t key; |
77 | uint64_t key; |
78 | 78 | ||
79 | /** Difference between heights of left and right subtree of this node.*/ |
79 | /** Difference between heights of left and right subtree of this node.*/ |
80 | short balance; |
80 | short balance; |
81 | }; |
81 | }; |
82 | 82 | ||
83 | /** AVL tree structure. */ |
83 | /** AVL tree structure. */ |
84 | struct avltree |
84 | struct avltree |
85 | { |
85 | { |
86 | /** AVL root node pointer */ |
86 | /** AVL root node pointer */ |
87 | struct avltree_node *root; |
87 | struct avltree_node *root; |
88 | 88 | ||
89 | /** |
89 | /** |
90 | * Base of tree is value that is smaller or equal then every value in tree. |
90 | * Base of tree is value that is smaller or equal then every value in tree. |
91 | * |
91 | * |
92 | * Base is added to current key when new node is inserted into tree. |
92 | * Base is added to current key when new node is inserted into tree. |
93 | * Base is changed to the key of node which is deleted with function |
93 | * Base is changed to the key of node which is deleted with function |
94 | * avltree_delete_min. |
94 | * avltree_delete_min. |
95 | */ |
95 | */ |
96 | uint64_t base; /**< POZOR: Base time for inserting new nodes */ |
96 | uint64_t base; /**< POZOR: Base time for inserting new nodes */ |
97 | }; |
97 | }; |
98 | 98 | ||
99 | 99 | ||
100 | /** Create empty AVL tree. |
100 | /** Create empty AVL tree. |
101 | * |
101 | * |
102 | * @param t AVL tree. |
102 | * @param t AVL tree. |
103 | */ |
103 | */ |
104 | static inline void avltree_create (avltree_t *t) |
104 | static inline void avltree_create (avltree_t *t) |
105 | { |
105 | { |
106 | t->root = NULL; |
106 | t->root = NULL; |
107 | t->base = 0; |
107 | t->base = 0; |
108 | } |
108 | } |
109 | 109 | ||
110 | /** Initialize node. |
110 | /** Initialize node. |
111 | * |
111 | * |
112 | * @param Node which is initialized. |
112 | * @param Node which is initialized. |
113 | */ |
113 | */ |
114 | static inline void avltree_node_initialize(avltree_node_t *node) |
114 | static inline void avltree_node_initialize(avltree_node_t *node) |
115 | { |
115 | { |
116 | node->key = 0; |
116 | node->key = 0; |
117 | node->lft = NULL; |
117 | node->lft = NULL; |
118 | node->rgt = NULL; |
118 | node->rgt = NULL; |
119 | node->par = NULL; |
119 | node->par = NULL; |
120 | node->balance = 0; |
120 | node->balance = 0; |
121 | } |
121 | } |
122 | 122 | ||
- | 123 | avltree_node_t *avltree_find_min(avltree_t *t); |
|
123 | avltree_node_t *avltree_search(avltree_t *t, uint64_t key); |
124 | avltree_node_t *avltree_search(avltree_t *t, uint64_t key); |
124 | void avltree_insert(avltree_t *t, avltree_node_t *newnode); |
125 | void avltree_insert(avltree_t *t, avltree_node_t *newnode); |
125 | void avltree_delete(avltree_t *t, avltree_node_t *node); |
126 | void avltree_delete(avltree_t *t, avltree_node_t *node); |
126 | avltree_node_t *avltree_delete_min(avltree_t *t); |
127 | bool avltree_delete_min(avltree_t *t); |
127 | 128 | ||
128 | #endif |
129 | #endif |
129 | 130 | ||
130 | /** @} |
131 | /** @} |
131 | */ |
132 | */ |
132 | 133 |