This source file includes following definitions.
- check_invariants
- gl_avltree_list_check_invariants
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18 #include <config.h>
19
20
21 #include "gl_avltree_list.h"
22
23 #include <stdlib.h>
24
25
26
27
28 #include "gl_anyavltree_list1.h"
29
30
31 #include "gl_anytree_list1.h"
32
33
34 #include "gl_anyavltree_list2.h"
35
36
37 #include "gl_anytree_list2.h"
38
39
40 extern void gl_avltree_list_check_invariants (gl_list_t list);
41
42 static unsigned int _GL_ATTRIBUTE_PURE
43 check_invariants (gl_list_node_t node, gl_list_node_t parent)
44 {
45 unsigned int left_height =
46 (node->left != NULL ? check_invariants (node->left, node) : 0);
47 unsigned int right_height =
48 (node->right != NULL ? check_invariants (node->right, node) : 0);
49 int balance = (int)right_height - (int)left_height;
50
51 if (!(node->parent == parent))
52 abort ();
53 if (!(node->branch_size
54 == (node->left != NULL ? node->left->branch_size : 0)
55 + 1 + (node->right != NULL ? node->right->branch_size : 0)))
56 abort ();
57 if (!(balance >= -1 && balance <= 1))
58 abort ();
59 if (!(node->balance == balance))
60 abort ();
61
62 return 1 + (left_height > right_height ? left_height : right_height);
63 }
64 void
65 gl_avltree_list_check_invariants (gl_list_t list)
66 {
67 if (list->root != NULL)
68 (void) check_invariants (list->root, NULL);
69 }
70
71 const struct gl_list_implementation gl_avltree_list_implementation =
72 {
73 gl_tree_nx_create_empty,
74 gl_tree_nx_create,
75 gl_tree_size,
76 gl_tree_node_value,
77 gl_tree_node_nx_set_value,
78 gl_tree_next_node,
79 gl_tree_previous_node,
80 gl_tree_first_node,
81 gl_tree_last_node,
82 gl_tree_get_at,
83 gl_tree_nx_set_at,
84 gl_tree_search_from_to,
85 gl_tree_indexof_from_to,
86 gl_tree_nx_add_first,
87 gl_tree_nx_add_last,
88 gl_tree_nx_add_before,
89 gl_tree_nx_add_after,
90 gl_tree_nx_add_at,
91 gl_tree_remove_node,
92 gl_tree_remove_at,
93 gl_tree_remove,
94 gl_tree_list_free,
95 gl_tree_iterator,
96 gl_tree_iterator_from_to,
97 gl_tree_iterator_next,
98 gl_tree_iterator_free,
99 gl_tree_sortedlist_search,
100 gl_tree_sortedlist_search_from_to,
101 gl_tree_sortedlist_indexof,
102 gl_tree_sortedlist_indexof_from_to,
103 gl_tree_sortedlist_nx_add,
104 gl_tree_sortedlist_remove
105 };