1 /* Sequential list data type implemented by a binary tree.
2 Copyright (C) 2006, 2008-2024 Free Software Foundation, Inc.
3 Written by Bruno Haible <bruno@clisp.org>, 2006.
5 This file is free software: you can redistribute it and/or modify
6 it under the terms of the GNU Lesser General Public License as
7 published by the Free Software Foundation; either version 2.1 of the
8 License, or (at your option) any later version.
10 This file is distributed in the hope that it will be useful,
11 but WITHOUT ANY WARRANTY; without even the implied warranty of
12 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
13 GNU Lesser General Public License for more details.
15 You should have received a copy of the GNU Lesser General Public License
16 along with this program. If not, see <https://www.gnu.org/licenses/>. */
21 #include "gl_avltree_list.h"
25 /* -------------------------- gl_list_t Data Type -------------------------- */
27 /* Generic AVL tree code. */
28 #include "gl_anyavltree_list1.h"
30 /* Generic binary tree code. */
31 #include "gl_anytree_list1.h"
33 /* Generic AVL tree code. */
34 #include "gl_anyavltree_list2.h"
36 /* Generic binary tree code. */
37 #include "gl_anytree_list2.h"
40 static unsigned int _GL_ATTRIBUTE_PURE
41 check_invariants (gl_list_node_t node
, gl_list_node_t parent
)
43 unsigned int left_height
=
44 (node
->left
!= NULL
? check_invariants (node
->left
, node
) : 0);
45 unsigned int right_height
=
46 (node
->right
!= NULL
? check_invariants (node
->right
, node
) : 0);
47 int balance
= (int)right_height
- (int)left_height
;
49 if (!(node
->parent
== parent
))
51 if (!(node
->branch_size
52 == (node
->left
!= NULL
? node
->left
->branch_size
: 0)
53 + 1 + (node
->right
!= NULL
? node
->right
->branch_size
: 0)))
55 if (!(balance
>= -1 && balance
<= 1))
57 if (!(node
->balance
== balance
))
60 return 1 + (left_height
> right_height
? left_height
: right_height
);
62 extern void gl_avltree_list_check_invariants (gl_list_t list
);
64 gl_avltree_list_check_invariants (gl_list_t list
)
66 if (list
->root
!= NULL
)
67 (void) check_invariants (list
->root
, NULL
);
70 const struct gl_list_implementation gl_avltree_list_implementation
=
72 gl_tree_nx_create_empty
,
76 gl_tree_node_nx_set_value
,
78 gl_tree_previous_node
,
83 gl_tree_search_from_to
,
84 gl_tree_indexof_from_to
,
87 gl_tree_nx_add_before
,
95 gl_tree_iterator_from_to
,
96 gl_tree_iterator_next
,
97 gl_tree_iterator_free
,
98 gl_tree_sortedlist_search
,
99 gl_tree_sortedlist_search_from_to
,
100 gl_tree_sortedlist_indexof
,
101 gl_tree_sortedlist_indexof_from_to
,
102 gl_tree_sortedlist_nx_add
,
103 gl_tree_sortedlist_remove