This source file includes following definitions.
- check_invariants
- gl_rbtree_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_rbtree_list.h"
22
23 #include <stdlib.h>
24
25
26
27
28 #include "gl_anyrbtree_list1.h"
29
30
31 #include "gl_anytree_list1.h"
32
33
34 #include "gl_anyrbtree_list2.h"
35
36
37 #include "gl_anytree_list2.h"
38
39
40 extern void gl_rbtree_list_check_invariants (gl_list_t list);
41
42 static unsigned int
43 check_invariants (gl_list_node_t node, gl_list_node_t parent)
44 {
45 unsigned int left_blackheight =
46 (node->left != NULL ? check_invariants (node->left, node) : 0);
47 unsigned int right_blackheight =
48 (node->right != NULL ? check_invariants (node->right, node) : 0);
49
50 if (!(node->parent == parent))
51 abort ();
52 if (!(node->branch_size
53 == (node->left != NULL ? node->left->branch_size : 0)
54 + 1 + (node->right != NULL ? node->right->branch_size : 0)))
55 abort ();
56 if (!(node->color == BLACK || node->color == RED))
57 abort ();
58 if (parent == NULL && !(node->color == BLACK))
59 abort ();
60 if (!(left_blackheight == right_blackheight))
61 abort ();
62
63 return left_blackheight + (node->color == BLACK ? 1 : 0);
64 }
65 void
66 gl_rbtree_list_check_invariants (gl_list_t list)
67 {
68 if (list->root != NULL)
69 (void) check_invariants (list->root, NULL);
70 }
71
72 const struct gl_list_implementation gl_rbtree_list_implementation =
73 {
74 gl_tree_nx_create_empty,
75 gl_tree_nx_create,
76 gl_tree_size,
77 gl_tree_node_value,
78 gl_tree_node_nx_set_value,
79 gl_tree_next_node,
80 gl_tree_previous_node,
81 gl_tree_first_node,
82 gl_tree_last_node,
83 gl_tree_get_at,
84 gl_tree_nx_set_at,
85 gl_tree_search_from_to,
86 gl_tree_indexof_from_to,
87 gl_tree_nx_add_first,
88 gl_tree_nx_add_last,
89 gl_tree_nx_add_before,
90 gl_tree_nx_add_after,
91 gl_tree_nx_add_at,
92 gl_tree_remove_node,
93 gl_tree_remove_at,
94 gl_tree_remove,
95 gl_tree_list_free,
96 gl_tree_iterator,
97 gl_tree_iterator_from_to,
98 gl_tree_iterator_next,
99 gl_tree_iterator_free,
100 gl_tree_sortedlist_search,
101 gl_tree_sortedlist_search_from_to,
102 gl_tree_sortedlist_indexof,
103 gl_tree_sortedlist_indexof_from_to,
104 gl_tree_sortedlist_nx_add,
105 gl_tree_sortedlist_remove
106 };