Mercurial > gnulib

annotate lib/gl_anytree_oset.h @ 40186:8964917f9574

Find changesets by keywords (author, files, the commit message), revision number or hash, or revset expression.
autoupdate
author Karl Berry <karl@freefriends.org>
date Mon, 18 Feb 2019 08:02:49 -0800
parents b06060465f09
children
Ignore whitespace changes - Everywhere: Within whitespace: At end of lines:
rev   line source
6974
c7d0a3879b08 Common code of several ordered list implementations.
Bruno Haible <bruno@clisp.org>
parents:
diff changeset
1 /* Ordered set data type implemented by a binary tree.
40057
b06060465f09 maint: Run 'make update-copyright'
Paul Eggert <eggert@cs.ucla.edu>
parents: 39999
diff changeset
2 Copyright (C) 2006-2007, 2009-2019 Free Software Foundation, Inc.
6974
c7d0a3879b08 Common code of several ordered list implementations.
Bruno Haible <bruno@clisp.org>
parents:
diff changeset
3 Written by Bruno Haible <bruno@clisp.org>, 2006.
c7d0a3879b08 Common code of several ordered list implementations.
Bruno Haible <bruno@clisp.org>
parents:
diff changeset
4
9309
bbbbbf4cd1c5 Change copyright notice from GPLv2+ to GPLv3+.
Bruno Haible <bruno@clisp.org>
parents: 8436
diff changeset
5 This program is free software: you can redistribute it and/or modify
6974
c7d0a3879b08 Common code of several ordered list implementations.
Bruno Haible <bruno@clisp.org>
parents:
diff changeset
6 it under the terms of the GNU General Public License as published by
9309
bbbbbf4cd1c5 Change copyright notice from GPLv2+ to GPLv3+.
Bruno Haible <bruno@clisp.org>
parents: 8436
diff changeset
7 the Free Software Foundation; either version 3 of the License, or
bbbbbf4cd1c5 Change copyright notice from GPLv2+ to GPLv3+.
Bruno Haible <bruno@clisp.org>
parents: 8436
diff changeset
8 (at your option) any later version.
6974
c7d0a3879b08 Common code of several ordered list implementations.
Bruno Haible <bruno@clisp.org>
parents:
diff changeset
9
c7d0a3879b08 Common code of several ordered list implementations.
Bruno Haible <bruno@clisp.org>
parents:
diff changeset
10 This program is distributed in the hope that it will be useful,
c7d0a3879b08 Common code of several ordered list implementations.
Bruno Haible <bruno@clisp.org>
parents:
diff changeset
11 but WITHOUT ANY WARRANTY; without even the implied warranty of
c7d0a3879b08 Common code of several ordered list implementations.
Bruno Haible <bruno@clisp.org>
parents:
diff changeset
12 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
c7d0a3879b08 Common code of several ordered list implementations.
Bruno Haible <bruno@clisp.org>
parents:
diff changeset
13 GNU General Public License for more details.
c7d0a3879b08 Common code of several ordered list implementations.
Bruno Haible <bruno@clisp.org>
parents:
diff changeset
14
c7d0a3879b08 Common code of several ordered list implementations.
Bruno Haible <bruno@clisp.org>
parents:
diff changeset
15 You should have received a copy of the GNU General Public License
19190
9759915b2aca all: prefer https: URLs
Paul Eggert <eggert@cs.ucla.edu>
parents: 18626
diff changeset
16 along with this program. If not, see <https://www.gnu.org/licenses/>. */
6974
c7d0a3879b08 Common code of several ordered list implementations.
Bruno Haible <bruno@clisp.org>
parents:
diff changeset
17
c7d0a3879b08 Common code of several ordered list implementations.
Bruno Haible <bruno@clisp.org>
parents:
diff changeset
18 /* Common code of gl_avltree_oset.c and gl_rbtree_oset.c. */
c7d0a3879b08 Common code of several ordered list implementations.
Bruno Haible <bruno@clisp.org>
parents:
diff changeset
19
c7d0a3879b08 Common code of several ordered list implementations.
Bruno Haible <bruno@clisp.org>
parents:
diff changeset
20 /* An item on the stack used for iterating across the elements. */
c7d0a3879b08 Common code of several ordered list implementations.
Bruno Haible <bruno@clisp.org>
parents:
diff changeset
21 typedef struct
c7d0a3879b08 Common code of several ordered list implementations.
Bruno Haible <bruno@clisp.org>
parents:
diff changeset
22 {
c7d0a3879b08 Common code of several ordered list implementations.
Bruno Haible <bruno@clisp.org>
parents:
diff changeset
23 gl_oset_node_t node;
c7d0a3879b08 Common code of several ordered list implementations.
Bruno Haible <bruno@clisp.org>
parents:
diff changeset
24 bool rightp;
c7d0a3879b08 Common code of several ordered list implementations.
Bruno Haible <bruno@clisp.org>
parents:
diff changeset
25 } iterstack_item_t;
c7d0a3879b08 Common code of several ordered list implementations.
Bruno Haible <bruno@clisp.org>
parents:
diff changeset
26
c7d0a3879b08 Common code of several ordered list implementations.
Bruno Haible <bruno@clisp.org>
parents:
diff changeset
27 /* A stack used for iterating across the elements. */
c7d0a3879b08 Common code of several ordered list implementations.
Bruno Haible <bruno@clisp.org>
parents:
diff changeset
28 typedef iterstack_item_t iterstack_t[MAXHEIGHT];
c7d0a3879b08 Common code of several ordered list implementations.
Bruno Haible <bruno@clisp.org>
parents:
diff changeset
29
c7d0a3879b08 Common code of several ordered list implementations.
Bruno Haible <bruno@clisp.org>
parents:
diff changeset
30 static gl_oset_t
12444
29d240cb21b2 Move the malloc checking from module 'oset' to new module 'xoset'.
Bruno Haible <bruno@clisp.org>
parents: 12421
diff changeset
31 gl_tree_nx_create_empty (gl_oset_implementation_t implementation,
29d240cb21b2 Move the malloc checking from module 'oset' to new module 'xoset'.
Bruno Haible <bruno@clisp.org>
parents: 12421
diff changeset
32 gl_setelement_compar_fn compar_fn,
29d240cb21b2 Move the malloc checking from module 'oset' to new module 'xoset'.
Bruno Haible <bruno@clisp.org>
parents: 12421
diff changeset
33 gl_setelement_dispose_fn dispose_fn)
6974
c7d0a3879b08 Common code of several ordered list implementations.
Bruno Haible <bruno@clisp.org>
parents:
diff changeset
34 {
12444
29d240cb21b2 Move the malloc checking from module 'oset' to new module 'xoset'.
Bruno Haible <bruno@clisp.org>
parents: 12421
diff changeset
35 struct gl_oset_impl *set =
29d240cb21b2 Move the malloc checking from module 'oset' to new module 'xoset'.
Bruno Haible <bruno@clisp.org>
parents: 12421
diff changeset
36 (struct gl_oset_impl *) malloc (sizeof (struct gl_oset_impl));
29d240cb21b2 Move the malloc checking from module 'oset' to new module 'xoset'.
Bruno Haible <bruno@clisp.org>
parents: 12421
diff changeset
37
29d240cb21b2 Move the malloc checking from module 'oset' to new module 'xoset'.
Bruno Haible <bruno@clisp.org>
parents: 12421
diff changeset
38 if (set == NULL)
29d240cb21b2 Move the malloc checking from module 'oset' to new module 'xoset'.
Bruno Haible <bruno@clisp.org>
parents: 12421
diff changeset
39 return NULL;
6974
c7d0a3879b08 Common code of several ordered list implementations.
Bruno Haible <bruno@clisp.org>
parents:
diff changeset
40
c7d0a3879b08 Common code of several ordered list implementations.
Bruno Haible <bruno@clisp.org>
parents:
diff changeset
41 set->base.vtable = implementation;
c7d0a3879b08 Common code of several ordered list implementations.
Bruno Haible <bruno@clisp.org>
parents:
diff changeset
42 set->base.compar_fn = compar_fn;
8436
36bbb949160c Add an element disposal function.
Bruno Haible <bruno@clisp.org>
parents: 7645
diff changeset
43 set->base.dispose_fn = dispose_fn;
6974
c7d0a3879b08 Common code of several ordered list implementations.
Bruno Haible <bruno@clisp.org>
parents:
diff changeset
44 set->root = NULL;
c7d0a3879b08 Common code of several ordered list implementations.
Bruno Haible <bruno@clisp.org>
parents:
diff changeset
45 set->count = 0;
c7d0a3879b08 Common code of several ordered list implementations.
Bruno Haible <bruno@clisp.org>
parents:
diff changeset
46
c7d0a3879b08 Common code of several ordered list implementations.
Bruno Haible <bruno@clisp.org>
parents:
diff changeset
47 return set;
c7d0a3879b08 Common code of several ordered list implementations.
Bruno Haible <bruno@clisp.org>
parents:
diff changeset
48 }
c7d0a3879b08 Common code of several ordered list implementations.
Bruno Haible <bruno@clisp.org>
parents:
diff changeset
49
c7d0a3879b08 Common code of several ordered list implementations.
Bruno Haible <bruno@clisp.org>
parents:
diff changeset
50 static size_t
c7d0a3879b08 Common code of several ordered list implementations.
Bruno Haible <bruno@clisp.org>
parents:
diff changeset
51 gl_tree_size (gl_oset_t set)
c7d0a3879b08 Common code of several ordered list implementations.
Bruno Haible <bruno@clisp.org>
parents:
diff changeset
52 {
c7d0a3879b08 Common code of several ordered list implementations.
Bruno Haible <bruno@clisp.org>
parents:
diff changeset
53 return set->count;
c7d0a3879b08 Common code of several ordered list implementations.
Bruno Haible <bruno@clisp.org>
parents:
diff changeset
54 }
c7d0a3879b08 Common code of several ordered list implementations.
Bruno Haible <bruno@clisp.org>
parents:
diff changeset
55
c7d0a3879b08 Common code of several ordered list implementations.
Bruno Haible <bruno@clisp.org>
parents:
diff changeset
56 static bool
c7d0a3879b08 Common code of several ordered list implementations.
Bruno Haible <bruno@clisp.org>
parents:
diff changeset
57 gl_tree_search (gl_oset_t set, const void *elt)
c7d0a3879b08 Common code of several ordered list implementations.
Bruno Haible <bruno@clisp.org>
parents:
diff changeset
58 {
c7d0a3879b08 Common code of several ordered list implementations.
Bruno Haible <bruno@clisp.org>
parents:
diff changeset
59 gl_setelement_compar_fn compar = set->base.compar_fn;
c7d0a3879b08 Common code of several ordered list implementations.
Bruno Haible <bruno@clisp.org>
parents:
diff changeset
60 gl_oset_node_t node;
c7d0a3879b08 Common code of several ordered list implementations.
Bruno Haible <bruno@clisp.org>
parents:
diff changeset
61
c7d0a3879b08 Common code of several ordered list implementations.
Bruno Haible <bruno@clisp.org>
parents:
diff changeset
62 for (node = set->root; node != NULL; )
c7d0a3879b08 Common code of several ordered list implementations.
Bruno Haible <bruno@clisp.org>
parents:
diff changeset
63 {
c7d0a3879b08 Common code of several ordered list implementations.
Bruno Haible <bruno@clisp.org>
parents:
diff changeset
64 int cmp = (compar != NULL
12421
e8d2c6fc33ad Use spaces for indentation, not tabs.
Bruno Haible <bruno@clisp.org>
parents: 9309
diff changeset
65 ? compar (node->value, elt)
e8d2c6fc33ad Use spaces for indentation, not tabs.
Bruno Haible <bruno@clisp.org>
parents: 9309
diff changeset
66 : (node->value > elt ? 1 :
e8d2c6fc33ad Use spaces for indentation, not tabs.
Bruno Haible <bruno@clisp.org>
parents: 9309
diff changeset
67 node->value < elt ? -1 : 0));
6974
c7d0a3879b08 Common code of several ordered list implementations.
Bruno Haible <bruno@clisp.org>
parents:
diff changeset
68
c7d0a3879b08 Common code of several ordered list implementations.
Bruno Haible <bruno@clisp.org>
parents:
diff changeset
69 if (cmp < 0)
12421
e8d2c6fc33ad Use spaces for indentation, not tabs.
Bruno Haible <bruno@clisp.org>
parents: 9309
diff changeset
70 node = node->right;
6974
c7d0a3879b08 Common code of several ordered list implementations.
Bruno Haible <bruno@clisp.org>
parents:
diff changeset
71 else if (cmp > 0)
12421
e8d2c6fc33ad Use spaces for indentation, not tabs.
Bruno Haible <bruno@clisp.org>
parents: 9309
diff changeset
72 node = node->left;
6974
c7d0a3879b08 Common code of several ordered list implementations.
Bruno Haible <bruno@clisp.org>
parents:
diff changeset
73 else /* cmp == 0 */
12421
e8d2c6fc33ad Use spaces for indentation, not tabs.
Bruno Haible <bruno@clisp.org>
parents: 9309
diff changeset
74 /* We have an element equal to ELT. */
e8d2c6fc33ad Use spaces for indentation, not tabs.
Bruno Haible <bruno@clisp.org>
parents: 9309
diff changeset
75 return true;
6974
c7d0a3879b08 Common code of several ordered list implementations.
Bruno Haible <bruno@clisp.org>
parents:
diff changeset
76 }
c7d0a3879b08 Common code of several ordered list implementations.
Bruno Haible <bruno@clisp.org>
parents:
diff changeset
77 return false;
c7d0a3879b08 Common code of several ordered list implementations.
Bruno Haible <bruno@clisp.org>
parents:
diff changeset
78 }
c7d0a3879b08 Common code of several ordered list implementations.
Bruno Haible <bruno@clisp.org>
parents:
diff changeset
79
7403
2fbd1f779c5f Add a search_atleast operation.
Bruno Haible <bruno@clisp.org>
parents: 7352
diff changeset
80 static bool
2fbd1f779c5f Add a search_atleast operation.
Bruno Haible <bruno@clisp.org>
parents: 7352
diff changeset
81 gl_tree_search_atleast (gl_oset_t set,
12421
e8d2c6fc33ad Use spaces for indentation, not tabs.
Bruno Haible <bruno@clisp.org>
parents: 9309
diff changeset
82 gl_setelement_threshold_fn threshold_fn,
e8d2c6fc33ad Use spaces for indentation, not tabs.
Bruno Haible <bruno@clisp.org>
parents: 9309
diff changeset
83 const void *threshold,
e8d2c6fc33ad Use spaces for indentation, not tabs.
Bruno Haible <bruno@clisp.org>
parents: 9309
diff changeset
84 const void **eltp)
7403
2fbd1f779c5f Add a search_atleast operation.
Bruno Haible <bruno@clisp.org>
parents: 7352
diff changeset
85 {
2fbd1f779c5f Add a search_atleast operation.
Bruno Haible <bruno@clisp.org>
parents: 7352
diff changeset
86 gl_oset_node_t node;
2fbd1f779c5f Add a search_atleast operation.
Bruno Haible <bruno@clisp.org>
parents: 7352
diff changeset
87
2fbd1f779c5f Add a search_atleast operation.
Bruno Haible <bruno@clisp.org>
parents: 7352
diff changeset
88 for (node = set->root; node != NULL; )
2fbd1f779c5f Add a search_atleast operation.
Bruno Haible <bruno@clisp.org>
parents: 7352
diff changeset
89 {
2fbd1f779c5f Add a search_atleast operation.
Bruno Haible <bruno@clisp.org>
parents: 7352
diff changeset
90 if (! threshold_fn (node->value, threshold))
12421
e8d2c6fc33ad Use spaces for indentation, not tabs.
Bruno Haible <bruno@clisp.org>
parents: 9309
diff changeset
91 node = node->right;
7403
2fbd1f779c5f Add a search_atleast operation.
Bruno Haible <bruno@clisp.org>
parents: 7352
diff changeset
92 else
12421
e8d2c6fc33ad Use spaces for indentation, not tabs.
Bruno Haible <bruno@clisp.org>
parents: 9309
diff changeset
93 {
39999
d8b00b7465aa Fix comments.
Bruno Haible <bruno@clisp.org>
parents: 19484
diff changeset
94 /* We have an element >= THRESHOLD. But we need the leftmost such
12421
e8d2c6fc33ad Use spaces for indentation, not tabs.
Bruno Haible <bruno@clisp.org>
parents: 9309
diff changeset
95 element. */
e8d2c6fc33ad Use spaces for indentation, not tabs.
Bruno Haible <bruno@clisp.org>
parents: 9309
diff changeset
96 gl_oset_node_t found = node;
e8d2c6fc33ad Use spaces for indentation, not tabs.
Bruno Haible <bruno@clisp.org>
parents: 9309
diff changeset
97 node = node->left;
e8d2c6fc33ad Use spaces for indentation, not tabs.
Bruno Haible <bruno@clisp.org>
parents: 9309
diff changeset
98 for (; node != NULL; )
e8d2c6fc33ad Use spaces for indentation, not tabs.
Bruno Haible <bruno@clisp.org>
parents: 9309
diff changeset
99 {
e8d2c6fc33ad Use spaces for indentation, not tabs.
Bruno Haible <bruno@clisp.org>
parents: 9309
diff changeset
100 if (! threshold_fn (node->value, threshold))
e8d2c6fc33ad Use spaces for indentation, not tabs.
Bruno Haible <bruno@clisp.org>
parents: 9309
diff changeset
101 node = node->right;
e8d2c6fc33ad Use spaces for indentation, not tabs.
Bruno Haible <bruno@clisp.org>
parents: 9309
diff changeset
102 else
e8d2c6fc33ad Use spaces for indentation, not tabs.
Bruno Haible <bruno@clisp.org>
parents: 9309
diff changeset
103 {
e8d2c6fc33ad Use spaces for indentation, not tabs.
Bruno Haible <bruno@clisp.org>
parents: 9309
diff changeset
104 found = node;
e8d2c6fc33ad Use spaces for indentation, not tabs.
Bruno Haible <bruno@clisp.org>
parents: 9309
diff changeset
105 node = node->left;
e8d2c6fc33ad Use spaces for indentation, not tabs.
Bruno Haible <bruno@clisp.org>
parents: 9309
diff changeset
106 }
e8d2c6fc33ad Use spaces for indentation, not tabs.
Bruno Haible <bruno@clisp.org>
parents: 9309
diff changeset
107 }
e8d2c6fc33ad Use spaces for indentation, not tabs.
Bruno Haible <bruno@clisp.org>
parents: 9309
diff changeset
108 *eltp = found->value;
e8d2c6fc33ad Use spaces for indentation, not tabs.
Bruno Haible <bruno@clisp.org>
parents: 9309
diff changeset
109 return true;
e8d2c6fc33ad Use spaces for indentation, not tabs.
Bruno Haible <bruno@clisp.org>
parents: 9309
diff changeset
110 }
7403
2fbd1f779c5f Add a search_atleast operation.
Bruno Haible <bruno@clisp.org>
parents: 7352
diff changeset
111 }
2fbd1f779c5f Add a search_atleast operation.
Bruno Haible <bruno@clisp.org>
parents: 7352
diff changeset
112 return false;
2fbd1f779c5f Add a search_atleast operation.
Bruno Haible <bruno@clisp.org>
parents: 7352
diff changeset
113 }
2fbd1f779c5f Add a search_atleast operation.
Bruno Haible <bruno@clisp.org>
parents: 7352
diff changeset
114
6974
c7d0a3879b08 Common code of several ordered list implementations.
Bruno Haible <bruno@clisp.org>
parents:
diff changeset
115 static gl_oset_node_t
c7d0a3879b08 Common code of several ordered list implementations.
Bruno Haible <bruno@clisp.org>
parents:
diff changeset
116 gl_tree_search_node (gl_oset_t set, const void *elt)
c7d0a3879b08 Common code of several ordered list implementations.
Bruno Haible <bruno@clisp.org>
parents:
diff changeset
117 {
c7d0a3879b08 Common code of several ordered list implementations.
Bruno Haible <bruno@clisp.org>
parents:
diff changeset
118 gl_setelement_compar_fn compar = set->base.compar_fn;
c7d0a3879b08 Common code of several ordered list implementations.
Bruno Haible <bruno@clisp.org>
parents:
diff changeset
119 gl_oset_node_t node;
c7d0a3879b08 Common code of several ordered list implementations.
Bruno Haible <bruno@clisp.org>
parents:
diff changeset
120
c7d0a3879b08 Common code of several ordered list implementations.
Bruno Haible <bruno@clisp.org>
parents:
diff changeset
121 for (node = set->root; node != NULL; )
c7d0a3879b08 Common code of several ordered list implementations.
Bruno Haible <bruno@clisp.org>
parents:
diff changeset
122 {
c7d0a3879b08 Common code of several ordered list implementations.
Bruno Haible <bruno@clisp.org>
parents:
diff changeset
123 int cmp = (compar != NULL
12421
e8d2c6fc33ad Use spaces for indentation, not tabs.
Bruno Haible <bruno@clisp.org>
parents: 9309
diff changeset
124 ? compar (node->value, elt)
e8d2c6fc33ad Use spaces for indentation, not tabs.
Bruno Haible <bruno@clisp.org>
parents: 9309
diff changeset
125 : (node->value > elt ? 1 :
e8d2c6fc33ad Use spaces for indentation, not tabs.
Bruno Haible <bruno@clisp.org>
parents: 9309
diff changeset
126 node->value < elt ? -1 : 0));
6974
c7d0a3879b08 Common code of several ordered list implementations.
Bruno Haible <bruno@clisp.org>
parents:
diff changeset
127
c7d0a3879b08 Common code of several ordered list implementations.
Bruno Haible <bruno@clisp.org>
parents:
diff changeset
128 if (cmp < 0)
12421
e8d2c6fc33ad Use spaces for indentation, not tabs.
Bruno Haible <bruno@clisp.org>
parents: 9309
diff changeset
129 node = node->right;
6974
c7d0a3879b08 Common code of several ordered list implementations.
Bruno Haible <bruno@clisp.org>
parents:
diff changeset
130 else if (cmp > 0)
12421
e8d2c6fc33ad Use spaces for indentation, not tabs.
Bruno Haible <bruno@clisp.org>
parents: 9309
diff changeset
131 node = node->left;
6974
c7d0a3879b08 Common code of several ordered list implementations.
Bruno Haible <bruno@clisp.org>
parents:
diff changeset
132 else /* cmp == 0 */
12421
e8d2c6fc33ad Use spaces for indentation, not tabs.
Bruno Haible <bruno@clisp.org>
parents: 9309
diff changeset
133 /* We have an element equal to ELT. */
e8d2c6fc33ad Use spaces for indentation, not tabs.
Bruno Haible <bruno@clisp.org>
parents: 9309
diff changeset
134 return node;
6974
c7d0a3879b08 Common code of several ordered list implementations.
Bruno Haible <bruno@clisp.org>
parents:
diff changeset
135 }
c7d0a3879b08 Common code of several ordered list implementations.
Bruno Haible <bruno@clisp.org>
parents:
diff changeset
136 return NULL;
c7d0a3879b08 Common code of several ordered list implementations.
Bruno Haible <bruno@clisp.org>
parents:
diff changeset
137 }
c7d0a3879b08 Common code of several ordered list implementations.
Bruno Haible <bruno@clisp.org>
parents:
diff changeset
138
12444
29d240cb21b2 Move the malloc checking from module 'oset' to new module 'xoset'.
Bruno Haible <bruno@clisp.org>
parents: 12421
diff changeset
139 static int
29d240cb21b2 Move the malloc checking from module 'oset' to new module 'xoset'.
Bruno Haible <bruno@clisp.org>
parents: 12421
diff changeset
140 gl_tree_nx_add (gl_oset_t set, const void *elt)
6974
c7d0a3879b08 Common code of several ordered list implementations.
Bruno Haible <bruno@clisp.org>
parents:
diff changeset
141 {
c7d0a3879b08 Common code of several ordered list implementations.
Bruno Haible <bruno@clisp.org>
parents:
diff changeset
142 gl_setelement_compar_fn compar;
c7d0a3879b08 Common code of several ordered list implementations.
Bruno Haible <bruno@clisp.org>
parents:
diff changeset
143 gl_oset_node_t node = set->root;
c7d0a3879b08 Common code of several ordered list implementations.
Bruno Haible <bruno@clisp.org>
parents:
diff changeset
144
c7d0a3879b08 Common code of several ordered list implementations.
Bruno Haible <bruno@clisp.org>
parents:
diff changeset
145 if (node == NULL)
c7d0a3879b08 Common code of several ordered list implementations.
Bruno Haible <bruno@clisp.org>
parents:
diff changeset
146 {
12444
29d240cb21b2 Move the malloc checking from module 'oset' to new module 'xoset'.
Bruno Haible <bruno@clisp.org>
parents: 12421
diff changeset
147 if (gl_tree_nx_add_first (set, elt) == NULL)
29d240cb21b2 Move the malloc checking from module 'oset' to new module 'xoset'.
Bruno Haible <bruno@clisp.org>
parents: 12421
diff changeset
148 return -1;
6974
c7d0a3879b08 Common code of several ordered list implementations.
Bruno Haible <bruno@clisp.org>
parents:
diff changeset
149 return true;
c7d0a3879b08 Common code of several ordered list implementations.
Bruno Haible <bruno@clisp.org>
parents:
diff changeset
150 }
c7d0a3879b08 Common code of several ordered list implementations.
Bruno Haible <bruno@clisp.org>
parents:
diff changeset
151
c7d0a3879b08 Common code of several ordered list implementations.
Bruno Haible <bruno@clisp.org>
parents:
diff changeset
152 compar = set->base.compar_fn;
c7d0a3879b08 Common code of several ordered list implementations.
Bruno Haible <bruno@clisp.org>
parents:
diff changeset
153
c7d0a3879b08 Common code of several ordered list implementations.
Bruno Haible <bruno@clisp.org>
parents:
diff changeset
154 for (;;)
c7d0a3879b08 Common code of several ordered list implementations.
Bruno Haible <bruno@clisp.org>
parents:
diff changeset
155 {
c7d0a3879b08 Common code of several ordered list implementations.
Bruno Haible <bruno@clisp.org>
parents:
diff changeset
156 int cmp = (compar != NULL
12421
e8d2c6fc33ad Use spaces for indentation, not tabs.
Bruno Haible <bruno@clisp.org>
parents: 9309
diff changeset
157 ? compar (node->value, elt)
e8d2c6fc33ad Use spaces for indentation, not tabs.
Bruno Haible <bruno@clisp.org>
parents: 9309
diff changeset
158 : (node->value > elt ? 1 :
e8d2c6fc33ad Use spaces for indentation, not tabs.
Bruno Haible <bruno@clisp.org>
parents: 9309
diff changeset
159 node->value < elt ? -1 : 0));
6974
c7d0a3879b08 Common code of several ordered list implementations.
Bruno Haible <bruno@clisp.org>
parents:
diff changeset
160
c7d0a3879b08 Common code of several ordered list implementations.
Bruno Haible <bruno@clisp.org>
parents:
diff changeset
161 if (cmp < 0)
12421
e8d2c6fc33ad Use spaces for indentation, not tabs.
Bruno Haible <bruno@clisp.org>
parents: 9309
diff changeset
162 {
e8d2c6fc33ad Use spaces for indentation, not tabs.
Bruno Haible <bruno@clisp.org>
parents: 9309
diff changeset
163 if (node->right == NULL)
e8d2c6fc33ad Use spaces for indentation, not tabs.
Bruno Haible <bruno@clisp.org>
parents: 9309
diff changeset
164 {
12444
29d240cb21b2 Move the malloc checking from module 'oset' to new module 'xoset'.
Bruno Haible <bruno@clisp.org>
parents: 12421
diff changeset
165 if (gl_tree_nx_add_after (set, node, elt) == NULL)
29d240cb21b2 Move the malloc checking from module 'oset' to new module 'xoset'.
Bruno Haible <bruno@clisp.org>
parents: 12421
diff changeset
166 return -1;
12421
e8d2c6fc33ad Use spaces for indentation, not tabs.
Bruno Haible <bruno@clisp.org>
parents: 9309
diff changeset
167 return true;
e8d2c6fc33ad Use spaces for indentation, not tabs.
Bruno Haible <bruno@clisp.org>
parents: 9309
diff changeset
168 }
e8d2c6fc33ad Use spaces for indentation, not tabs.
Bruno Haible <bruno@clisp.org>
parents: 9309
diff changeset
169 node = node->right;
e8d2c6fc33ad Use spaces for indentation, not tabs.
Bruno Haible <bruno@clisp.org>
parents: 9309
diff changeset
170 }
6974
c7d0a3879b08 Common code of several ordered list implementations.
Bruno Haible <bruno@clisp.org>
parents:
diff changeset
171 else if (cmp > 0)
12421
e8d2c6fc33ad Use spaces for indentation, not tabs.
Bruno Haible <bruno@clisp.org>
parents: 9309
diff changeset
172 {
e8d2c6fc33ad Use spaces for indentation, not tabs.
Bruno Haible <bruno@clisp.org>
parents: 9309
diff changeset
173 if (node->left == NULL)
e8d2c6fc33ad Use spaces for indentation, not tabs.
Bruno Haible <bruno@clisp.org>
parents: 9309
diff changeset
174 {
12444
29d240cb21b2 Move the malloc checking from module 'oset' to new module 'xoset'.
Bruno Haible <bruno@clisp.org>
parents: 12421
diff changeset
175 if (gl_tree_nx_add_before (set, node, elt) == NULL)
29d240cb21b2 Move the malloc checking from module 'oset' to new module 'xoset'.
Bruno Haible <bruno@clisp.org>
parents: 12421
diff changeset
176 return -1;
12421
e8d2c6fc33ad Use spaces for indentation, not tabs.
Bruno Haible <bruno@clisp.org>
parents: 9309
diff changeset
177 return true;
e8d2c6fc33ad Use spaces for indentation, not tabs.
Bruno Haible <bruno@clisp.org>
parents: 9309
diff changeset
178 }
e8d2c6fc33ad Use spaces for indentation, not tabs.
Bruno Haible <bruno@clisp.org>
parents: 9309
diff changeset
179 node = node->left;
e8d2c6fc33ad Use spaces for indentation, not tabs.
Bruno Haible <bruno@clisp.org>
parents: 9309
diff changeset
180 }
6974
c7d0a3879b08 Common code of several ordered list implementations.
Bruno Haible <bruno@clisp.org>
parents:
diff changeset
181 else /* cmp == 0 */
12421
e8d2c6fc33ad Use spaces for indentation, not tabs.
Bruno Haible <bruno@clisp.org>
parents: 9309
diff changeset
182 return false;
6974
c7d0a3879b08 Common code of several ordered list implementations.
Bruno Haible <bruno@clisp.org>
parents:
diff changeset
183 }
c7d0a3879b08 Common code of several ordered list implementations.
Bruno Haible <bruno@clisp.org>
parents:
diff changeset
184 }
c7d0a3879b08 Common code of several ordered list implementations.
Bruno Haible <bruno@clisp.org>
parents:
diff changeset
185
c7d0a3879b08 Common code of several ordered list implementations.
Bruno Haible <bruno@clisp.org>
parents:
diff changeset
186 static bool
c7d0a3879b08 Common code of several ordered list implementations.
Bruno Haible <bruno@clisp.org>
parents:
diff changeset
187 gl_tree_remove (gl_oset_t set, const void *elt)
c7d0a3879b08 Common code of several ordered list implementations.
Bruno Haible <bruno@clisp.org>
parents:
diff changeset
188 {
c7d0a3879b08 Common code of several ordered list implementations.
Bruno Haible <bruno@clisp.org>
parents:
diff changeset
189 gl_oset_node_t node = gl_tree_search_node (set, elt);
c7d0a3879b08 Common code of several ordered list implementations.
Bruno Haible <bruno@clisp.org>
parents:
diff changeset
190
c7d0a3879b08 Common code of several ordered list implementations.
Bruno Haible <bruno@clisp.org>
parents:
diff changeset
191 if (node != NULL)
c7d0a3879b08 Common code of several ordered list implementations.
Bruno Haible <bruno@clisp.org>
parents:
diff changeset
192 return gl_tree_remove_node (set, node);
c7d0a3879b08 Common code of several ordered list implementations.
Bruno Haible <bruno@clisp.org>
parents:
diff changeset
193 else
c7d0a3879b08 Common code of several ordered list implementations.
Bruno Haible <bruno@clisp.org>
parents:
diff changeset
194 return false;
c7d0a3879b08 Common code of several ordered list implementations.
Bruno Haible <bruno@clisp.org>
parents:
diff changeset
195 }
c7d0a3879b08 Common code of several ordered list implementations.
Bruno Haible <bruno@clisp.org>
parents:
diff changeset
196
c7d0a3879b08 Common code of several ordered list implementations.
Bruno Haible <bruno@clisp.org>
parents:
diff changeset
197 static void
c7d0a3879b08 Common code of several ordered list implementations.
Bruno Haible <bruno@clisp.org>
parents:
diff changeset
198 gl_tree_oset_free (gl_oset_t set)
c7d0a3879b08 Common code of several ordered list implementations.
Bruno Haible <bruno@clisp.org>
parents:
diff changeset
199 {
c7d0a3879b08 Common code of several ordered list implementations.
Bruno Haible <bruno@clisp.org>
parents:
diff changeset
200 /* Iterate across all elements in post-order. */
c7d0a3879b08 Common code of several ordered list implementations.
Bruno Haible <bruno@clisp.org>
parents:
diff changeset
201 gl_oset_node_t node = set->root;
c7d0a3879b08 Common code of several ordered list implementations.
Bruno Haible <bruno@clisp.org>
parents:
diff changeset
202 iterstack_t stack;
c7d0a3879b08 Common code of several ordered list implementations.
Bruno Haible <bruno@clisp.org>
parents:
diff changeset
203 iterstack_item_t *stack_ptr = &stack[0];
c7d0a3879b08 Common code of several ordered list implementations.
Bruno Haible <bruno@clisp.org>
parents:
diff changeset
204
c7d0a3879b08 Common code of several ordered list implementations.
Bruno Haible <bruno@clisp.org>
parents:
diff changeset
205 for (;;)
c7d0a3879b08 Common code of several ordered list implementations.
Bruno Haible <bruno@clisp.org>
parents:
diff changeset
206 {
c7d0a3879b08 Common code of several ordered list implementations.
Bruno Haible <bruno@clisp.org>
parents:
diff changeset
207 /* Descend on left branch. */
c7d0a3879b08 Common code of several ordered list implementations.
Bruno Haible <bruno@clisp.org>
parents:
diff changeset
208 for (;;)
12421
e8d2c6fc33ad Use spaces for indentation, not tabs.
Bruno Haible <bruno@clisp.org>
parents: 9309
diff changeset
209 {
e8d2c6fc33ad Use spaces for indentation, not tabs.
Bruno Haible <bruno@clisp.org>
parents: 9309
diff changeset
210 if (node == NULL)
e8d2c6fc33ad Use spaces for indentation, not tabs.
Bruno Haible <bruno@clisp.org>
parents: 9309
diff changeset
211 break;
e8d2c6fc33ad Use spaces for indentation, not tabs.
Bruno Haible <bruno@clisp.org>
parents: 9309
diff changeset
212 stack_ptr->node = node;
e8d2c6fc33ad Use spaces for indentation, not tabs.
Bruno Haible <bruno@clisp.org>
parents: 9309
diff changeset
213 stack_ptr->rightp = false;
e8d2c6fc33ad Use spaces for indentation, not tabs.
Bruno Haible <bruno@clisp.org>
parents: 9309
diff changeset
214 node = node->left;
e8d2c6fc33ad Use spaces for indentation, not tabs.
Bruno Haible <bruno@clisp.org>
parents: 9309
diff changeset
215 stack_ptr++;
e8d2c6fc33ad Use spaces for indentation, not tabs.
Bruno Haible <bruno@clisp.org>
parents: 9309
diff changeset
216 }
6974
c7d0a3879b08 Common code of several ordered list implementations.
Bruno Haible <bruno@clisp.org>
parents:
diff changeset
217 /* Climb up again. */
c7d0a3879b08 Common code of several ordered list implementations.
Bruno Haible <bruno@clisp.org>
parents:
diff changeset
218 for (;;)
12421
e8d2c6fc33ad Use spaces for indentation, not tabs.
Bruno Haible <bruno@clisp.org>
parents: 9309
diff changeset
219 {
e8d2c6fc33ad Use spaces for indentation, not tabs.
Bruno Haible <bruno@clisp.org>
parents: 9309
diff changeset
220 if (stack_ptr == &stack[0])
e8d2c6fc33ad Use spaces for indentation, not tabs.
Bruno Haible <bruno@clisp.org>
parents: 9309
diff changeset
221 goto done_iterate;
e8d2c6fc33ad Use spaces for indentation, not tabs.
Bruno Haible <bruno@clisp.org>
parents: 9309
diff changeset
222 stack_ptr--;
e8d2c6fc33ad Use spaces for indentation, not tabs.
Bruno Haible <bruno@clisp.org>
parents: 9309
diff changeset
223 node = stack_ptr->node;
e8d2c6fc33ad Use spaces for indentation, not tabs.
Bruno Haible <bruno@clisp.org>
parents: 9309
diff changeset
224 if (!stack_ptr->rightp)
e8d2c6fc33ad Use spaces for indentation, not tabs.
Bruno Haible <bruno@clisp.org>
parents: 9309
diff changeset
225 break;
e8d2c6fc33ad Use spaces for indentation, not tabs.
Bruno Haible <bruno@clisp.org>
parents: 9309
diff changeset
226 /* Free the current node. */
e8d2c6fc33ad Use spaces for indentation, not tabs.
Bruno Haible <bruno@clisp.org>
parents: 9309
diff changeset
227 if (set->base.dispose_fn != NULL)
e8d2c6fc33ad Use spaces for indentation, not tabs.
Bruno Haible <bruno@clisp.org>
parents: 9309
diff changeset
228 set->base.dispose_fn (node->value);
e8d2c6fc33ad Use spaces for indentation, not tabs.
Bruno Haible <bruno@clisp.org>
parents: 9309
diff changeset
229 free (node);
e8d2c6fc33ad Use spaces for indentation, not tabs.
Bruno Haible <bruno@clisp.org>
parents: 9309
diff changeset
230 }
6974
c7d0a3879b08 Common code of several ordered list implementations.
Bruno Haible <bruno@clisp.org>
parents:
diff changeset
231 /* Descend on right branch. */
c7d0a3879b08 Common code of several ordered list implementations.
Bruno Haible <bruno@clisp.org>
parents:
diff changeset
232 stack_ptr->rightp = true;
c7d0a3879b08 Common code of several ordered list implementations.
Bruno Haible <bruno@clisp.org>
parents:
diff changeset
233 node = node->right;
c7d0a3879b08 Common code of several ordered list implementations.
Bruno Haible <bruno@clisp.org>
parents:
diff changeset
234 stack_ptr++;
c7d0a3879b08 Common code of several ordered list implementations.
Bruno Haible <bruno@clisp.org>
parents:
diff changeset
235 }
c7d0a3879b08 Common code of several ordered list implementations.
Bruno Haible <bruno@clisp.org>
parents:
diff changeset
236 done_iterate:
c7d0a3879b08 Common code of several ordered list implementations.
Bruno Haible <bruno@clisp.org>
parents:
diff changeset
237 free (set);
c7d0a3879b08 Common code of several ordered list implementations.
Bruno Haible <bruno@clisp.org>
parents:
diff changeset
238 }
c7d0a3879b08 Common code of several ordered list implementations.
Bruno Haible <bruno@clisp.org>
parents:
diff changeset
239
c7d0a3879b08 Common code of several ordered list implementations.
Bruno Haible <bruno@clisp.org>
parents:
diff changeset
240 /* --------------------- gl_oset_iterator_t Data Type --------------------- */
c7d0a3879b08 Common code of several ordered list implementations.
Bruno Haible <bruno@clisp.org>
parents:
diff changeset
241
c7d0a3879b08 Common code of several ordered list implementations.
Bruno Haible <bruno@clisp.org>
parents:
diff changeset
242 static gl_oset_iterator_t
c7d0a3879b08 Common code of several ordered list implementations.
Bruno Haible <bruno@clisp.org>
parents:
diff changeset
243 gl_tree_iterator (gl_oset_t set)
c7d0a3879b08 Common code of several ordered list implementations.
Bruno Haible <bruno@clisp.org>
parents:
diff changeset
244 {
c7d0a3879b08 Common code of several ordered list implementations.
Bruno Haible <bruno@clisp.org>
parents:
diff changeset
245 gl_oset_iterator_t result;
c7d0a3879b08 Common code of several ordered list implementations.
Bruno Haible <bruno@clisp.org>
parents:
diff changeset
246 gl_oset_node_t node;
c7d0a3879b08 Common code of several ordered list implementations.
Bruno Haible <bruno@clisp.org>
parents:
diff changeset
247
c7d0a3879b08 Common code of several ordered list implementations.
Bruno Haible <bruno@clisp.org>
parents:
diff changeset
248 result.vtable = set->base.vtable;
c7d0a3879b08 Common code of several ordered list implementations.
Bruno Haible <bruno@clisp.org>
parents:
diff changeset
249 result.set = set;
c7d0a3879b08 Common code of several ordered list implementations.
Bruno Haible <bruno@clisp.org>
parents:
diff changeset
250 /* Start node is the leftmost node. */
c7d0a3879b08 Common code of several ordered list implementations.
Bruno Haible <bruno@clisp.org>
parents:
diff changeset
251 node = set->root;
c7d0a3879b08 Common code of several ordered list implementations.
Bruno Haible <bruno@clisp.org>
parents:
diff changeset
252 if (node != NULL)
c7d0a3879b08 Common code of several ordered list implementations.
Bruno Haible <bruno@clisp.org>
parents:
diff changeset
253 while (node->left != NULL)
c7d0a3879b08 Common code of several ordered list implementations.
Bruno Haible <bruno@clisp.org>
parents:
diff changeset
254 node = node->left;
c7d0a3879b08 Common code of several ordered list implementations.
Bruno Haible <bruno@clisp.org>
parents:
diff changeset
255 result.p = node;
c7d0a3879b08 Common code of several ordered list implementations.
Bruno Haible <bruno@clisp.org>
parents:
diff changeset
256 /* End point is past the rightmost node. */
c7d0a3879b08 Common code of several ordered list implementations.
Bruno Haible <bruno@clisp.org>
parents:
diff changeset
257 result.q = NULL;
18325
33db65a13e67 Use GCC_LINT, not lint
Paul Eggert <eggert@cs.ucla.edu>
parents: 18189
diff changeset
258 #if defined GCC_LINT || defined lint
7352
3d5bd6899004 * gl_anylinked_list2.h [lint] (gl_linked_iterator)
Ralf Wildenhues <Ralf.Wildenhues@gmx.de>
parents: 6974
diff changeset
259 result.i = 0;
3d5bd6899004 * gl_anylinked_list2.h [lint] (gl_linked_iterator)
Ralf Wildenhues <Ralf.Wildenhues@gmx.de>
parents: 6974
diff changeset
260 result.j = 0;
3d5bd6899004 * gl_anylinked_list2.h [lint] (gl_linked_iterator)
Ralf Wildenhues <Ralf.Wildenhues@gmx.de>
parents: 6974
diff changeset
261 result.count = 0;
3d5bd6899004 * gl_anylinked_list2.h [lint] (gl_linked_iterator)
Ralf Wildenhues <Ralf.Wildenhues@gmx.de>
parents: 6974
diff changeset
262 #endif
6974
c7d0a3879b08 Common code of several ordered list implementations.
Bruno Haible <bruno@clisp.org>
parents:
diff changeset
263
c7d0a3879b08 Common code of several ordered list implementations.
Bruno Haible <bruno@clisp.org>
parents:
diff changeset
264 return result;
c7d0a3879b08 Common code of several ordered list implementations.
Bruno Haible <bruno@clisp.org>
parents:
diff changeset
265 }
c7d0a3879b08 Common code of several ordered list implementations.
Bruno Haible <bruno@clisp.org>
parents:
diff changeset
266
c7d0a3879b08 Common code of several ordered list implementations.
Bruno Haible <bruno@clisp.org>
parents:
diff changeset
267 static bool
c7d0a3879b08 Common code of several ordered list implementations.
Bruno Haible <bruno@clisp.org>
parents:
diff changeset
268 gl_tree_iterator_next (gl_oset_iterator_t *iterator, const void **eltp)
c7d0a3879b08 Common code of several ordered list implementations.
Bruno Haible <bruno@clisp.org>
parents:
diff changeset
269 {
c7d0a3879b08 Common code of several ordered list implementations.
Bruno Haible <bruno@clisp.org>
parents:
diff changeset
270 if (iterator->p != iterator->q)
c7d0a3879b08 Common code of several ordered list implementations.
Bruno Haible <bruno@clisp.org>
parents:
diff changeset
271 {
c7d0a3879b08 Common code of several ordered list implementations.
Bruno Haible <bruno@clisp.org>
parents:
diff changeset
272 gl_oset_node_t node = (gl_oset_node_t) iterator->p;
c7d0a3879b08 Common code of several ordered list implementations.
Bruno Haible <bruno@clisp.org>
parents:
diff changeset
273 *eltp = node->value;
c7d0a3879b08 Common code of several ordered list implementations.
Bruno Haible <bruno@clisp.org>
parents:
diff changeset
274 /* Advance to the next node. */
c7d0a3879b08 Common code of several ordered list implementations.
Bruno Haible <bruno@clisp.org>
parents:
diff changeset
275 if (node->right != NULL)
12421
e8d2c6fc33ad Use spaces for indentation, not tabs.
Bruno Haible <bruno@clisp.org>
parents: 9309
diff changeset
276 {
e8d2c6fc33ad Use spaces for indentation, not tabs.
Bruno Haible <bruno@clisp.org>
parents: 9309
diff changeset
277 node = node->right;
e8d2c6fc33ad Use spaces for indentation, not tabs.
Bruno Haible <bruno@clisp.org>
parents: 9309
diff changeset
278 while (node->left != NULL)
e8d2c6fc33ad Use spaces for indentation, not tabs.
Bruno Haible <bruno@clisp.org>
parents: 9309
diff changeset
279 node = node->left;
e8d2c6fc33ad Use spaces for indentation, not tabs.
Bruno Haible <bruno@clisp.org>
parents: 9309
diff changeset
280 }
6974
c7d0a3879b08 Common code of several ordered list implementations.
Bruno Haible <bruno@clisp.org>
parents:
diff changeset
281 else
12421
e8d2c6fc33ad Use spaces for indentation, not tabs.
Bruno Haible <bruno@clisp.org>
parents: 9309
diff changeset
282 {
e8d2c6fc33ad Use spaces for indentation, not tabs.
Bruno Haible <bruno@clisp.org>
parents: 9309
diff changeset
283 while (node->parent != NULL && node->parent->right == node)
e8d2c6fc33ad Use spaces for indentation, not tabs.
Bruno Haible <bruno@clisp.org>
parents: 9309
diff changeset
284 node = node->parent;
e8d2c6fc33ad Use spaces for indentation, not tabs.
Bruno Haible <bruno@clisp.org>
parents: 9309
diff changeset
285 node = node->parent;
e8d2c6fc33ad Use spaces for indentation, not tabs.
Bruno Haible <bruno@clisp.org>
parents: 9309
diff changeset
286 }
6974
c7d0a3879b08 Common code of several ordered list implementations.
Bruno Haible <bruno@clisp.org>
parents:
diff changeset
287 iterator->p = node;
c7d0a3879b08 Common code of several ordered list implementations.
Bruno Haible <bruno@clisp.org>
parents:
diff changeset
288 return true;
c7d0a3879b08 Common code of several ordered list implementations.
Bruno Haible <bruno@clisp.org>
parents:
diff changeset
289 }
c7d0a3879b08 Common code of several ordered list implementations.
Bruno Haible <bruno@clisp.org>
parents:
diff changeset
290 else
c7d0a3879b08 Common code of several ordered list implementations.
Bruno Haible <bruno@clisp.org>
parents:
diff changeset
291 return false;
c7d0a3879b08 Common code of several ordered list implementations.
Bruno Haible <bruno@clisp.org>
parents:
diff changeset
292 }
c7d0a3879b08 Common code of several ordered list implementations.
Bruno Haible <bruno@clisp.org>
parents:
diff changeset
293
c7d0a3879b08 Common code of several ordered list implementations.
Bruno Haible <bruno@clisp.org>
parents:
diff changeset
294 static void
c7d0a3879b08 Common code of several ordered list implementations.
Bruno Haible <bruno@clisp.org>
parents:
diff changeset
295 gl_tree_iterator_free (gl_oset_iterator_t *iterator)
c7d0a3879b08 Common code of several ordered list implementations.
Bruno Haible <bruno@clisp.org>
parents:
diff changeset
296 {
c7d0a3879b08 Common code of several ordered list implementations.
Bruno Haible <bruno@clisp.org>
parents:
diff changeset
297 }