This source file includes following definitions.
- check_invariants
- gl_rbtreehash_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_rbtreehash_list.h"
22
23 #include <stdint.h>
24 #include <stdlib.h>
25
26 #include "gl_rbtree_oset.h"
27 #include "xsize.h"
28
29 #define WITH_HASHTABLE 1
30
31
32 #define OSET_TREE_FLAVOR GL_RBTREE_OSET
33
34
35
36
37 #include "gl_anyhash1.h"
38
39
40 #include "gl_anyrbtree_list1.h"
41
42
43 #define CONTAINER_T gl_list_t
44 #define CONTAINER_COUNT(list) \
45 ((list)->root != NULL ? (list)->root->branch_size : 0)
46 #include "gl_anyhash2.h"
47
48
49 #include "gl_anytree_list1.h"
50
51
52 #include "gl_anytreehash_list1.h"
53
54
55 #include "gl_anyrbtree_list2.h"
56
57
58 #include "gl_anytreehash_list2.h"
59
60
61 #include "gl_anytree_list2.h"
62
63
64 static unsigned int
65 check_invariants (gl_list_node_t node, gl_list_node_t parent)
66 {
67 unsigned int left_blackheight =
68 (node->left != NULL ? check_invariants (node->left, node) : 0);
69 unsigned int right_blackheight =
70 (node->right != NULL ? check_invariants (node->right, node) : 0);
71
72 if (!(node->parent == parent))
73 abort ();
74 if (!(node->branch_size
75 == (node->left != NULL ? node->left->branch_size : 0)
76 + 1 + (node->right != NULL ? node->right->branch_size : 0)))
77 abort ();
78 if (!(node->color == BLACK || node->color == RED))
79 abort ();
80 if (parent == NULL && !(node->color == BLACK))
81 abort ();
82 if (!(left_blackheight == right_blackheight))
83 abort ();
84
85 return left_blackheight + (node->color == BLACK ? 1 : 0);
86 }
87 void
88 gl_rbtreehash_list_check_invariants (gl_list_t list)
89 {
90 if (list->root != NULL)
91 check_invariants (list->root, NULL);
92 }
93
94
95 const struct gl_list_implementation gl_rbtreehash_list_implementation =
96 {
97 gl_tree_nx_create_empty,
98 gl_tree_nx_create,
99 gl_tree_size,
100 gl_tree_node_value,
101 gl_tree_node_nx_set_value,
102 gl_tree_next_node,
103 gl_tree_previous_node,
104 gl_tree_first_node,
105 gl_tree_last_node,
106 gl_tree_get_at,
107 gl_tree_nx_set_at,
108 gl_tree_search_from_to,
109 gl_tree_indexof_from_to,
110 gl_tree_nx_add_first,
111 gl_tree_nx_add_last,
112 gl_tree_nx_add_before,
113 gl_tree_nx_add_after,
114 gl_tree_nx_add_at,
115 gl_tree_remove_node,
116 gl_tree_remove_at,
117 gl_tree_remove,
118 gl_tree_list_free,
119 gl_tree_iterator,
120 gl_tree_iterator_from_to,
121 gl_tree_iterator_next,
122 gl_tree_iterator_free,
123 gl_tree_sortedlist_search,
124 gl_tree_sortedlist_search_from_to,
125 gl_tree_sortedlist_indexof,
126 gl_tree_sortedlist_indexof_from_to,
127 gl_tree_sortedlist_nx_add,
128 gl_tree_sortedlist_remove
129 };