/src/gnutls/gl/gl_rbtree_list.c
Line | Count | Source |
1 | | /* Sequential list data type implemented by a binary tree. |
2 | | Copyright (C) 2006, 2008-2026 Free Software Foundation, Inc. |
3 | | Written by Bruno Haible <bruno@clisp.org>, 2006. |
4 | | |
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. |
9 | | |
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. |
14 | | |
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/>. */ |
17 | | |
18 | | #include <config.h> |
19 | | |
20 | | /* Specification. */ |
21 | | #include "gl_rbtree_list.h" |
22 | | |
23 | | #include <stdlib.h> |
24 | | |
25 | | /* -------------------------- gl_list_t Data Type -------------------------- */ |
26 | | |
27 | | /* Generic red-black tree code. */ |
28 | | #include "gl_anyrbtree_list1.h" |
29 | | |
30 | | /* Generic binary tree code. */ |
31 | | #include "gl_anytree_list1.h" |
32 | | |
33 | | /* Generic red-black tree code. */ |
34 | | #include "gl_anyrbtree_list2.h" |
35 | | |
36 | | /* Generic binary tree code. */ |
37 | | #include "gl_anytree_list2.h" |
38 | | |
39 | | /* For debugging. */ |
40 | | static unsigned int |
41 | | check_invariants (gl_list_node_t node, gl_list_node_t parent) |
42 | 0 | { |
43 | 0 | unsigned int left_blackheight = |
44 | 0 | (node->left != NULL ? check_invariants (node->left, node) : 0); |
45 | 0 | unsigned int right_blackheight = |
46 | 0 | (node->right != NULL ? check_invariants (node->right, node) : 0); |
47 | |
|
48 | 0 | if (!(node->parent == parent)) |
49 | 0 | abort (); |
50 | 0 | if (!(node->branch_size |
51 | 0 | == (node->left != NULL ? node->left->branch_size : 0) |
52 | 0 | + 1 + (node->right != NULL ? node->right->branch_size : 0))) |
53 | 0 | abort (); |
54 | 0 | if (!(node->color == BLACK || node->color == RED)) |
55 | 0 | abort (); |
56 | 0 | if (parent == NULL && !(node->color == BLACK)) |
57 | 0 | abort (); |
58 | 0 | if (!(left_blackheight == right_blackheight)) |
59 | 0 | abort (); |
60 | | |
61 | 0 | return left_blackheight + (node->color == BLACK ? 1 : 0); |
62 | 0 | } |
63 | | extern void gl_rbtree_list_check_invariants (gl_list_t list); |
64 | | void |
65 | | gl_rbtree_list_check_invariants (gl_list_t list) |
66 | 0 | { |
67 | 0 | if (list->root != NULL) |
68 | 0 | (void) check_invariants (list->root, NULL); |
69 | 0 | } |
70 | | |
71 | | const struct gl_list_implementation gl_rbtree_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 | | }; |