1 /* Ordered set data type implemented by a binary tree.
2 Copyright (C) 2006-2007, 2009-2020 Free Software Foundation, Inc.
3 Written by Bruno Haible <bruno@clisp.org>, 2006.
5 This program is free software: you can redistribute it and/or modify
6 it under the terms of the GNU General Public License as published by
7 the Free Software Foundation; either version 3 of the License, or
8 (at your option) any later version.
10 This program 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 General Public License for more details.
15 You should have received a copy of the GNU General Public License
16 along with this program. If not, see <https://www.gnu.org/licenses/>. */
18 /* Common code of gl_avltree_oset.c and gl_rbtree_oset.c. */
20 /* An item on the stack used for iterating across the elements. */
27 /* A stack used for iterating across the elements. */
28 typedef iterstack_item_t iterstack_t
[MAXHEIGHT
];
31 gl_tree_nx_create_empty (gl_oset_implementation_t implementation
,
32 gl_setelement_compar_fn compar_fn
,
33 gl_setelement_dispose_fn dispose_fn
)
35 struct gl_oset_impl
*set
=
36 (struct gl_oset_impl
*) malloc (sizeof (struct gl_oset_impl
));
41 set
->base
.vtable
= implementation
;
42 set
->base
.compar_fn
= compar_fn
;
43 set
->base
.dispose_fn
= dispose_fn
;
51 gl_tree_size (gl_oset_t set
)
57 gl_tree_search (gl_oset_t set
, const void *elt
)
59 gl_setelement_compar_fn compar
= set
->base
.compar_fn
;
62 for (node
= set
->root
; node
!= NULL
; )
64 int cmp
= (compar
!= NULL
65 ? compar (node
->value
, elt
)
66 : (node
->value
> elt
? 1 :
67 node
->value
< elt
? -1 : 0));
74 /* We have an element equal to ELT. */
81 gl_tree_search_atleast (gl_oset_t set
,
82 gl_setelement_threshold_fn threshold_fn
,
83 const void *threshold
,
88 for (node
= set
->root
; node
!= NULL
; )
90 if (! threshold_fn (node
->value
, threshold
))
94 /* We have an element >= THRESHOLD. But we need the leftmost such
96 gl_oset_node_t found
= node
;
98 for (; node
!= NULL
; )
100 if (! threshold_fn (node
->value
, threshold
))
108 *eltp
= found
->value
;
115 static gl_oset_node_t
116 gl_tree_search_node (gl_oset_t set
, const void *elt
)
118 gl_setelement_compar_fn compar
= set
->base
.compar_fn
;
121 for (node
= set
->root
; node
!= NULL
; )
123 int cmp
= (compar
!= NULL
124 ? compar (node
->value
, elt
)
125 : (node
->value
> elt
? 1 :
126 node
->value
< elt
? -1 : 0));
133 /* We have an element equal to ELT. */
140 gl_tree_nx_add (gl_oset_t set
, const void *elt
)
142 gl_setelement_compar_fn compar
;
143 gl_oset_node_t node
= set
->root
;
147 if (gl_tree_nx_add_first (set
, elt
) == NULL
)
152 compar
= set
->base
.compar_fn
;
156 int cmp
= (compar
!= NULL
157 ? compar (node
->value
, elt
)
158 : (node
->value
> elt
? 1 :
159 node
->value
< elt
? -1 : 0));
163 if (node
->right
== NULL
)
165 if (gl_tree_nx_add_after (set
, node
, elt
) == NULL
)
173 if (node
->left
== NULL
)
175 if (gl_tree_nx_add_before (set
, node
, elt
) == NULL
)
187 gl_tree_remove (gl_oset_t set
, const void *elt
)
189 gl_oset_node_t node
= gl_tree_search_node (set
, elt
);
192 return gl_tree_remove_node (set
, node
);
198 gl_tree_oset_free (gl_oset_t set
)
200 /* Iterate across all elements in post-order. */
201 gl_oset_node_t node
= set
->root
;
203 iterstack_item_t
*stack_ptr
= &stack
[0];
207 /* Descend on left branch. */
212 stack_ptr
->node
= node
;
213 stack_ptr
->rightp
= false;
217 /* Climb up again. */
220 if (stack_ptr
== &stack
[0])
223 node
= stack_ptr
->node
;
224 if (!stack_ptr
->rightp
)
226 /* Free the current node. */
227 if (set
->base
.dispose_fn
!= NULL
)
228 set
->base
.dispose_fn (node
->value
);
231 /* Descend on right branch. */
232 stack_ptr
->rightp
= true;
240 /* --------------------- gl_oset_iterator_t Data Type --------------------- */
242 static gl_oset_iterator_t
243 gl_tree_iterator (gl_oset_t set
)
245 gl_oset_iterator_t result
;
248 result
.vtable
= set
->base
.vtable
;
250 /* Start node is the leftmost node. */
253 while (node
->left
!= NULL
)
256 /* End point is past the rightmost node. */
258 #if defined GCC_LINT || defined lint
268 gl_tree_iterator_next (gl_oset_iterator_t
*iterator
, const void **eltp
)
270 if (iterator
->p
!= iterator
->q
)
272 gl_oset_node_t node
= (gl_oset_node_t
) iterator
->p
;
274 /* Advance to the next node. */
275 if (node
->right
!= NULL
)
278 while (node
->left
!= NULL
)
283 while (node
->parent
!= NULL
&& node
->parent
->right
== node
)
295 gl_tree_iterator_free (gl_oset_iterator_t
*iterator
)