This source file includes following definitions.
- check_invariants
- gl_avltreehash_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_avltreehash_list.h"
22
23 #include <stdint.h>
24 #include <stdlib.h>
25
26 #include "gl_avltree_oset.h"
27 #include "xsize.h"
28
29 #define WITH_HASHTABLE 1
30
31
32 #define OSET_TREE_FLAVOR GL_AVLTREE_OSET
33
34
35
36
37 #include "gl_anyhash1.h"
38
39
40 #include "gl_anyavltree_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_anyavltree_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_height =
68 (node->left != NULL ? check_invariants (node->left, node) : 0);
69 unsigned int right_height =
70 (node->right != NULL ? check_invariants (node->right, node) : 0);
71 int balance = (int)right_height - (int)left_height;
72
73 if (!(node->parent == parent))
74 abort ();
75 if (!(node->branch_size
76 == (node->left != NULL ? node->left->branch_size : 0)
77 + 1 + (node->right != NULL ? node->right->branch_size : 0)))
78 abort ();
79 if (!(balance >= -1 && balance <= 1))
80 abort ();
81 if (!(node->balance == balance))
82 abort ();
83
84 return 1 + (left_height > right_height ? left_height : right_height);
85 }
86 void
87 gl_avltreehash_list_check_invariants (gl_list_t list)
88 {
89 if (list->root != NULL)
90 check_invariants (list->root, NULL);
91 }
92
93
94 const struct gl_list_implementation gl_avltreehash_list_implementation =
95 {
96 gl_tree_nx_create_empty,
97 gl_tree_nx_create,
98 gl_tree_size,
99 gl_tree_node_value,
100 gl_tree_node_nx_set_value,
101 gl_tree_next_node,
102 gl_tree_previous_node,
103 gl_tree_first_node,
104 gl_tree_last_node,
105 gl_tree_get_at,
106 gl_tree_nx_set_at,
107 gl_tree_search_from_to,
108 gl_tree_indexof_from_to,
109 gl_tree_nx_add_first,
110 gl_tree_nx_add_last,
111 gl_tree_nx_add_before,
112 gl_tree_nx_add_after,
113 gl_tree_nx_add_at,
114 gl_tree_remove_node,
115 gl_tree_remove_at,
116 gl_tree_remove,
117 gl_tree_list_free,
118 gl_tree_iterator,
119 gl_tree_iterator_from_to,
120 gl_tree_iterator_next,
121 gl_tree_iterator_free,
122 gl_tree_sortedlist_search,
123 gl_tree_sortedlist_search_from_to,
124 gl_tree_sortedlist_indexof,
125 gl_tree_sortedlist_indexof_from_to,
126 gl_tree_sortedlist_nx_add,
127 gl_tree_sortedlist_remove
128 };