liba 0.1.15
An algorithm library based on C/C++
Loading...
Searching...
No Matches
avl.h
Go to the documentation of this file.
1
6#ifndef LIBA_AVL_H
7#define LIBA_AVL_H
8
9#include "a.h"
10
17// clang-format off
18#define A_AVL_ROOT {A_NULL}
19// clang-format on
20
24typedef struct a_avl_node
25{
26 struct a_avl_node *left;
27 struct a_avl_node *right;
38#if defined(A_SIZE_POINTER) && (A_SIZE_POINTER + 0 > 3)
40#else /* !A_SIZE_POINTER */
41 struct a_avl_node *parent;
42 int factor;
43#endif /* A_SIZE_POINTER */
45
52A_INTERN a_avl_node *a_avl_parent(a_avl_node const *node)
53{
54#if defined(A_SIZE_POINTER) && (A_SIZE_POINTER + 0 > 3)
55 return a_cast_r(a_avl_node *, node->parent_ & ~a_uptr_c(3));
56#else /* !A_SIZE_POINTER */
57 return node->parent;
58#endif /* A_SIZE_POINTER */
59}
60
67A_INTERN a_avl_node *a_avl_init(a_avl_node *node, a_avl_node *parent)
68{
69#if defined(A_SIZE_POINTER) && (A_SIZE_POINTER + 0 > 3)
70 node->parent_ = a_cast_r(a_uptr, parent) | 1;
71#else /* !A_SIZE_POINTER */
72 node->parent = parent;
73 node->factor = 0;
74#endif /* A_SIZE_POINTER */
75 node->right = A_NULL;
76 node->left = A_NULL;
77 return node;
78}
79
83typedef union a_avl
84{
85 struct a_avl_node *node;
87
92A_INTERN void a_avl_root(a_avl *root) { root->node = A_NULL; }
93
94#if defined(__cplusplus)
95extern "C" {
96#endif /* __cplusplus */
97
103A_EXTERN a_avl_node *a_avl_head(a_avl const *root);
104
110A_EXTERN a_avl_node *a_avl_tail(a_avl const *root);
111
118
125
132
139
145A_EXTERN a_avl_node *a_avl_post_head(a_avl const *root);
146
152A_EXTERN a_avl_node *a_avl_post_tail(a_avl const *root);
153
160
167
175A_EXTERN a_avl_node *a_avl_tear(a_avl *root, a_avl_node **next);
176
187A_EXTERN a_avl_node *a_avl_search(a_avl const *root, void const *ctx, int (*cmp)(void const *, void const *));
188
199A_EXTERN a_avl_node *a_avl_insert(a_avl *root, a_avl_node *node, int (*cmp)(void const *, void const *));
200
206A_EXTERN void a_avl_insert_adjust(a_avl *root, a_avl_node *node);
207
213A_EXTERN void a_avl_remove(a_avl *root, a_avl_node *node);
214
215#if defined(__cplusplus)
216} /* extern "C" */
217#endif /* __cplusplus */
218
225#define a_avl_entry(ptr, type, member) a_container_of(ptr, type, member)
226
243#define a_avl_foreach(cur, root) \
244 for (a_avl_node *cur = a_avl_head(root); cur; cur = a_avl_next(cur))
245
262#define a_avl_foreach_reverse(cur, root) \
263 for (a_avl_node *cur = a_avl_tail(root); cur; cur = a_avl_prev(cur))
264
281#define a_avl_pre_foreach(cur, root) \
282 for (a_avl_node *cur = (root)->node; cur; cur = a_avl_pre_next(cur))
283
300#define a_avl_pre_foreach_reverse(cur, root) \
301 for (a_avl_node *cur = (root)->node; cur; cur = a_avl_pre_prev(cur))
302
319#define a_avl_post_foreach(cur, root) \
320 for (a_avl_node *cur = a_avl_post_head(root); cur; cur = a_avl_post_next(cur))
321
338#define a_avl_post_foreach_reverse(cur, root) \
339 for (a_avl_node *cur = a_avl_post_tail(root); cur; cur = a_avl_post_prev(cur))
340
358#define a_avl_fortear(cur, next, root) \
359 for (a_avl_node *next = A_NULL, *cur = a_avl_tear(root, &next); cur; cur = a_avl_tear(root, &next))
360
363#endif /* a/avl.h */
algorithm library
struct a_avl_node a_avl_node
instance structure for AVL binary search tree node
a_avl_node * a_avl_insert(a_avl *root, a_avl_node *node, int(*cmp)(void const *, void const *))
insert specified node into AVL binary search tree
a_avl_node * a_avl_tear(a_avl *root, a_avl_node **next)
tear a node from AVL binary search tree
a_avl_node * a_avl_post_prev(a_avl_node *node)
access prev node of AVL binary search tree node postorder
a_avl_node * a_avl_post_next(a_avl_node *node)
access next node of AVL binary search tree node postorder
a_avl_node * a_avl_prev(a_avl_node *node)
access prev node of AVL binary search tree node in-order
union a_avl a_avl
instance structure for AVL binary search tree root
a_avl_node * a_avl_init(a_avl_node *node, a_avl_node *parent)
initialize for AVL binary search tree node
Definition avl.h:67
a_avl_node * a_avl_head(a_avl const *root)
access head node of AVL binary search tree in-order
a_avl_node * a_avl_pre_next(a_avl_node *node)
access next node of AVL binary search tree node preorder
a_avl_node * a_avl_pre_prev(a_avl_node *node)
access prev node of AVL binary search tree node preorder
a_avl_node * a_avl_tail(a_avl const *root)
access tail node of AVL binary search tree in-order
a_avl_node * a_avl_search(a_avl const *root, void const *ctx, int(*cmp)(void const *, void const *))
search specified content from AVL binary search tree
void a_avl_insert_adjust(a_avl *root, a_avl_node *node)
rebalance the tree after insertion of the specified node
a_avl_node * a_avl_post_head(a_avl const *root)
access head node of AVL binary search tree postorder
void a_avl_root(a_avl *root)
initialize for AVL binary search tree root
Definition avl.h:92
a_avl_node * a_avl_post_tail(a_avl const *root)
access tail node of AVL binary search tree postorder
a_avl_node * a_avl_parent(a_avl_node const *node)
access parent of AVL binary search tree node
Definition avl.h:52
void a_avl_remove(a_avl *root, a_avl_node *node)
remove specified node from AVL binary search tree
a_avl_node * a_avl_next(a_avl_node *node)
access next node of AVL binary search tree node in-order
#define a_uptr_c(x)
Definition a.h:580
#define a_uptr
Definition a.h:583
instance structure for AVL binary search tree node
Definition avl.h:25
uintptr_t parent_
Definition avl.h:39
struct a_avl_node * right
Definition avl.h:27
struct a_avl_node * left
Definition avl.h:26
instance structure for AVL binary search tree root
Definition avl.h:84
struct a_avl_node * node
root node
Definition avl.h:85