blob: e0d4811dfd7690c4746dcf751f060e6415248909 (
plain)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
|
/*
* Copyright (c) 2006-2020, RT-Thread Development Team
*
* SPDX-License-Identifier: Apache-2.0
*
* Change Logs:
* Date Author Notes
* 2019-10-12 Jesven first version
* 2022-11-14 WangXiaoyao Optimize for generic use case
* and performance
*/
#ifndef __UTIL_TREE_AVL_H__
#define __UTIL_TREE_AVL_H__
#include <rtdef.h>
#include <stdint.h>
struct util_avl_struct
{
struct util_avl_struct *avl_left;
struct util_avl_struct *avl_right;
struct util_avl_struct *parent;
size_t height;
};
#define AVL_ROOT ((struct util_avl_struct *)0)
struct util_avl_root
{
struct util_avl_struct *root_node;
};
void util_avl_rebalance(struct util_avl_struct *node,
struct util_avl_root *root);
void util_avl_remove(struct util_avl_struct *node, struct util_avl_root *root);
static inline void util_avl_link(struct util_avl_struct *new_node,
struct util_avl_struct *parent,
struct util_avl_struct **nodeplace)
{
new_node->avl_left = AVL_ROOT;
new_node->avl_right = AVL_ROOT;
new_node->parent = parent;
new_node->height = 1;
*nodeplace = new_node;
}
static inline struct util_avl_struct *util_avl_next(
struct util_avl_struct *node)
{
struct util_avl_struct *successor = 0;
if (node)
{
if (node->avl_right)
{
node = node->avl_right;
while (node->avl_left)
node = node->avl_left;
successor = node;
}
else
{
while ((successor = node->parent) && (node == successor->avl_right))
node = successor;
}
}
return successor;
}
static inline struct util_avl_struct *util_avl_prev(
struct util_avl_struct *node)
{
struct util_avl_struct *predecessor = 0;
if (node)
{
if (node->avl_left)
{
node = node->avl_left;
while (node->avl_right)
node = node->avl_right;
predecessor = node;
}
else
{
while ((predecessor = node->parent) &&
(node == predecessor->avl_left))
node = predecessor;
}
}
return predecessor;
}
static inline struct util_avl_struct *util_avl_first(struct util_avl_root *root)
{
struct util_avl_struct *first = root->root_node;
if (first)
{
while (first->avl_left)
first = first->avl_left;
}
return first;
}
static inline struct util_avl_struct *util_avl_last(struct util_avl_root *root)
{
struct util_avl_struct *last = root->root_node;
if (last)
{
while (last->avl_right)
last = last->avl_right;
}
return last;
}
#endif /* __UTIL_TREE_AVL_H__ */
|
