1 /* Ordered set data type implemented by a binary tree.
2 Copyright (C) 2006-2007, 2009-2021 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 /* Common code of gl_avltree_oset.c and gl_rbtree_oset.c. */
19
20 /* An item on the stack used for iterating across the elements. */
21 typedef struct
22 {
23 gl_oset_node_t node;
24 bool rightp;
25 } iterstack_item_t;
26
27 /* A stack used for iterating across the elements. */
28 typedef iterstack_item_t iterstack_t[MAXHEIGHT];
29
30 static gl_oset_t
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)
34 {
35 struct gl_oset_impl *set =
36 (struct gl_oset_impl *) malloc (sizeof (struct gl_oset_impl));
37
38 if (set == NULL)
39 return NULL;
40
41 set->base.vtable = implementation;
42 set->base.compar_fn = compar_fn;
43 set->base.dispose_fn = dispose_fn;
44 set->root = NULL;
45 set->count = 0;
46
47 return set;
48 }
49
50 static size_t _GL_ATTRIBUTE_PURE
51 gl_tree_size (gl_oset_t set)
52 {
53 return set->count;
54 }
55
56 /* Returns the next node in the tree, or NULL if there is none. */
57 static inline gl_oset_node_t _GL_ATTRIBUTE_PURE
58 gl_tree_next_node (gl_oset_node_t node)
59 {
60 if (node->right != NULL)
61 {
62 node = node->right;
63 while (node->left != NULL)
64 node = node->left;
65 }
66 else
67 {
68 while (node->parent != NULL && node->parent->right == node)
69 node = node->parent;
70 node = node->parent;
71 }
72 return node;
73 }
74
75 /* Returns the previous node in the tree, or NULL if there is none. */
76 static inline gl_oset_node_t _GL_ATTRIBUTE_PURE
77 gl_tree_prev_node (gl_oset_node_t node)
78 {
79 if (node->left != NULL)
80 {
81 node = node->left;
82 while (node->right != NULL)
83 node = node->right;
84 }
85 else
86 {
87 while (node->parent != NULL && node->parent->left == node)
88 node = node->parent;
89 node = node->parent;
90 }
91 return node;
92 }
93
94 static bool
95 gl_tree_search (gl_oset_t set, const void *elt)
96 {
97 gl_setelement_compar_fn compar = set->base.compar_fn;
98 gl_oset_node_t node;
99
100 for (node = set->root; node != NULL; )
101 {
102 int cmp = (compar != NULL
103 ? compar (node->value, elt)
104 : (node->value > elt ? 1 :
105 node->value < elt ? -1 : 0));
106
107 if (cmp < 0)
108 node = node->right;
109 else if (cmp > 0)
110 node = node->left;
111 else /* cmp == 0 */
112 /* We have an element equal to ELT. */
113 return true;
114 }
115 return false;
116 }
117
118 static bool
119 gl_tree_search_atleast (gl_oset_t set,
120 gl_setelement_threshold_fn threshold_fn,
121 const void *threshold,
122 const void **eltp)
123 {
124 gl_oset_node_t node;
125
126 for (node = set->root; node != NULL; )
127 {
128 if (! threshold_fn (node->value, threshold))
129 node = node->right;
130 else
131 {
132 /* We have an element >= THRESHOLD. But we need the leftmost such
133 element. */
134 gl_oset_node_t found = node;
135 node = node->left;
136 for (; node != NULL; )
137 {
138 if (! threshold_fn (node->value, threshold))
139 node = node->right;
140 else
141 {
142 found = node;
143 node = node->left;
144 }
145 }
146 *eltp = found->value;
147 return true;
148 }
149 }
150 return false;
151 }
152
153 static gl_oset_node_t
154 gl_tree_search_node (gl_oset_t set, const void *elt)
155 {
156 gl_setelement_compar_fn compar = set->base.compar_fn;
157 gl_oset_node_t node;
158
159 for (node = set->root; node != NULL; )
160 {
161 int cmp = (compar != NULL
162 ? compar (node->value, elt)
163 : (node->value > elt ? 1 :
164 node->value < elt ? -1 : 0));
165
166 if (cmp < 0)
167 node = node->right;
168 else if (cmp > 0)
169 node = node->left;
170 else /* cmp == 0 */
171 /* We have an element equal to ELT. */
172 return node;
173 }
174 return NULL;
175 }
176
177 static int
178 gl_tree_nx_add (gl_oset_t set, const void *elt)
179 {
180 gl_setelement_compar_fn compar;
181 gl_oset_node_t node = set->root;
182
183 if (node == NULL)
184 {
185 if (gl_tree_nx_add_first (set, elt) == NULL)
186 return -1;
187 return true;
188 }
189
190 compar = set->base.compar_fn;
191
192 for (;;)
193 {
194 int cmp = (compar != NULL
195 ? compar (node->value, elt)
196 : (node->value > elt ? 1 :
197 node->value < elt ? -1 : 0));
198
199 if (cmp < 0)
200 {
201 if (node->right == NULL)
202 {
203 if (gl_tree_nx_add_after (set, node, elt) == NULL)
204 return -1;
205 return true;
206 }
207 node = node->right;
208 }
209 else if (cmp > 0)
210 {
211 if (node->left == NULL)
212 {
213 if (gl_tree_nx_add_before (set, node, elt) == NULL)
214 return -1;
215 return true;
216 }
217 node = node->left;
218 }
219 else /* cmp == 0 */
220 return false;
221 }
222 }
223
224 static bool
225 gl_tree_remove (gl_oset_t set, const void *elt)
226 {
227 gl_oset_node_t node = gl_tree_search_node (set, elt);
228
229 if (node != NULL)
230 return gl_tree_remove_node (set, node);
231 else
232 return false;
233 }
234
235 static int
236 gl_tree_update (gl_oset_t set, const void *elt,
237 void (*action) (const void * /*elt*/, void * /*action_data*/),
238 void *action_data)
239 {
240 /* Like gl_tree_remove, action (...), gl_tree_nx_add, except that we don't
241 actually remove ELT. */
242 /* Remember the old node. Don't free it. */
243 gl_oset_node_t old_node = gl_tree_search_node (set, elt);
244 /* Invoke ACTION. */
245 action (elt, action_data);
246 /* Determine where to put the node now. */
247 if (old_node != NULL)
248 {
249 if (set->count > 1)
250 {
251 gl_setelement_compar_fn compar = set->base.compar_fn;
252
253 gl_oset_node_t prev_node = gl_tree_prev_node (old_node);
254 gl_oset_node_t next_node = gl_tree_next_node (old_node);
255 if (!(compar != NULL
256 ? (prev_node == NULL || compar (prev_node->value, elt) < 0)
257 && (next_node == NULL || compar (next_node->value, elt) > 0)
258 : (prev_node == NULL || prev_node->value < elt)
259 && (next_node == NULL || next_node->value > elt)))
260 {
261 /* old_node needs to move in the tree. */
262 gl_oset_node_t node;
263
264 /* Remove the node from the tree. Don't free it. */
265 gl_tree_remove_node_no_free (set, old_node);
266
267 node = set->root;
268
269 for (;;)
270 {
271 int cmp = (compar != NULL
272 ? compar (node->value, elt)
273 : (node->value > elt ? 1 :
274 node->value < elt ? -1 : 0));
275
276 if (cmp < 0)
277 {
278 if (node->right == NULL)
279 {
280 gl_tree_add_node_after (set, node, old_node);
281 return true;
282 }
283 node = node->right;
284 }
285 else if (cmp > 0)
286 {
287 if (node->left == NULL)
288 {
289 gl_tree_add_node_before (set, node, old_node);
290 return true;
291 }
292 node = node->left;
293 }
294 else /* cmp == 0 */
295 {
296 /* Two elements are the same. */
297 NODE_PAYLOAD_DISPOSE (set, old_node)
298 free (old_node);
299 return -1;
300 }
301 }
302 }
303 }
304 }
305 return 0;
306 }
307
308 static void
309 gl_tree_oset_free (gl_oset_t set)
310 {
311 /* Iterate across all elements in post-order. */
312 gl_oset_node_t node = set->root;
313 iterstack_t stack;
314 iterstack_item_t *stack_ptr = &stack[0];
315
316 for (;;)
317 {
318 /* Descend on left branch. */
319 for (;;)
320 {
321 if (node == NULL)
322 break;
323 stack_ptr->node = node;
324 stack_ptr->rightp = false;
325 node = node->left;
326 stack_ptr++;
327 }
328 /* Climb up again. */
329 for (;;)
330 {
331 if (stack_ptr == &stack[0])
332 goto done_iterate;
333 stack_ptr--;
334 node = stack_ptr->node;
335 if (!stack_ptr->rightp)
336 break;
337 /* Free the current node. */
338 if (set->base.dispose_fn != NULL)
339 set->base.dispose_fn (node->value);
340 free (node);
341 }
342 /* Descend on right branch. */
343 stack_ptr->rightp = true;
344 node = node->right;
345 stack_ptr++;
346 }
347 done_iterate:
348 free (set);
349 }
350
351 /* --------------------- gl_oset_iterator_t Data Type --------------------- */
352
353 static gl_oset_iterator_t _GL_ATTRIBUTE_PURE
354 gl_tree_iterator (gl_oset_t set)
355 {
356 gl_oset_iterator_t result;
357 gl_oset_node_t node;
358
359 result.vtable = set->base.vtable;
360 result.set = set;
361 /* Start node is the leftmost node. */
362 node = set->root;
363 if (node != NULL)
364 while (node->left != NULL)
365 node = node->left;
366 result.p = node;
367 /* End point is past the rightmost node. */
368 result.q = NULL;
369 #if defined GCC_LINT || defined lint
370 result.i = 0;
371 result.j = 0;
372 result.count = 0;
373 #endif
374
375 return result;
376 }
377
378 static gl_oset_iterator_t
379 gl_tree_iterator_atleast (gl_oset_t set,
380 gl_setelement_threshold_fn threshold_fn,
381 const void *threshold)
382 {
383 gl_oset_iterator_t result;
384 gl_oset_node_t node;
385
386 result.vtable = set->base.vtable;
387 result.set = set;
388 /* End point is past the rightmost node. */
389 result.q = NULL;
390 #if defined GCC_LINT || defined lint
391 result.i = 0;
392 result.j = 0;
393 result.count = 0;
394 #endif
395
396 for (node = set->root; node != NULL; )
397 {
398 if (! threshold_fn (node->value, threshold))
399 node = node->right;
400 else
401 {
402 /* We have an element >= THRESHOLD. But we need the leftmost such
403 element. */
404 gl_oset_node_t found = node;
405 node = node->left;
406 for (; node != NULL; )
407 {
408 if (! threshold_fn (node->value, threshold))
409 node = node->right;
410 else
411 {
412 found = node;
413 node = node->left;
414 }
415 }
416 result.p = found;
417 return result;
418 }
419 }
420 result.p = NULL;
421 return result;
422 }
423
424 static bool
425 gl_tree_iterator_next (gl_oset_iterator_t *iterator, const void **eltp)
426 {
427 if (iterator->p != iterator->q)
428 {
429 gl_oset_node_t node = (gl_oset_node_t) iterator->p;
430 *eltp = node->value;
431 /* Advance to the next node. */
432 node = gl_tree_next_node (node);
433 iterator->p = node;
434 return true;
435 }
436 else
437 return false;
438 }
439
440 static void
441 gl_tree_iterator_free (_GL_ATTRIBUTE_MAYBE_UNUSED gl_oset_iterator_t *iterator)
442 {
443 }