1 /* A splay-tree datatype.
2 Copyright (C) 1998-2023 Free Software Foundation, Inc.
3 Contributed by Mark Mitchell (mark@markmitchell.com).
4
5 This file is part of the GNU Offloading and Multi Processing Library
6 (libgomp).
7
8 Libgomp is free software; you can redistribute it and/or modify it
9 under the terms of the GNU General Public License as published by
10 the Free Software Foundation; either version 3, or (at your option)
11 any later version.
12
13 Libgomp is distributed in the hope that it will be useful, but WITHOUT ANY
14 WARRANTY; without even the implied warranty of MERCHANTABILITY or FITNESS
15 FOR A PARTICULAR PURPOSE. See the GNU General Public License for
16 more details.
17
18 Under Section 7 of GPL version 3, you are granted additional
19 permissions described in the GCC Runtime Library Exception, version
20 3.1, as published by the Free Software Foundation.
21
22 You should have received a copy of the GNU General Public License and
23 a copy of the GCC Runtime Library Exception along with this program;
24 see the files COPYING3 and COPYING.RUNTIME respectively. If not, see
25 <http://www.gnu.org/licenses/>. */
26
27 /* The splay tree code copied from include/splay-tree.h and adjusted,
28 so that all the data lives directly in splay_tree_node_s structure
29 and no extra allocations are needed. */
30
31 /* For an easily readable description of splay-trees, see:
32
33 Lewis, Harry R. and Denenberg, Larry. Data Structures and Their
34 Algorithms. Harper-Collins, Inc. 1991.
35
36 The major feature of splay trees is that all basic tree operations
37 are amortized O(log n) time for a tree with n nodes. */
38
39 #include "libgomp.h"
40
41 /* Rotate the edge joining the left child N with its parent P. PP is the
42 grandparents' pointer to P. */
43
44 static inline void
45 rotate_left (splay_tree_node *pp, splay_tree_node p, splay_tree_node n)
46 {
47 splay_tree_node tmp;
48 tmp = n->right;
49 n->right = p;
50 p->left = tmp;
51 *pp = n;
52 }
53
54 /* Rotate the edge joining the right child N with its parent P. PP is the
55 grandparents' pointer to P. */
56
57 static inline void
58 rotate_right (splay_tree_node *pp, splay_tree_node p, splay_tree_node n)
59 {
60 splay_tree_node tmp;
61 tmp = n->left;
62 n->left = p;
63 p->right = tmp;
64 *pp = n;
65 }
66
67 /* Bottom up splay of KEY. */
68
69 static void
70 splay_tree_splay (splay_tree sp, splay_tree_key key)
71 {
72 if (sp->root == NULL)
73 return;
74
75 do {
76 int cmp1, cmp2;
77 splay_tree_node n, c;
78
79 n = sp->root;
80 cmp1 = splay_compare (key, &n->key);
81
82 /* Found. */
83 if (cmp1 == 0)
84 return;
85
86 /* Left or right? If no child, then we're done. */
87 if (cmp1 < 0)
88 c = n->left;
89 else
90 c = n->right;
91 if (!c)
92 return;
93
94 /* Next one left or right? If found or no child, we're done
95 after one rotation. */
96 cmp2 = splay_compare (key, &c->key);
97 if (cmp2 == 0
98 || (cmp2 < 0 && !c->left)
99 || (cmp2 > 0 && !c->right))
100 {
101 if (cmp1 < 0)
102 rotate_left (&sp->root, n, c);
103 else
104 rotate_right (&sp->root, n, c);
105 return;
106 }
107
108 /* Now we have the four cases of double-rotation. */
109 if (cmp1 < 0 && cmp2 < 0)
110 {
111 rotate_left (&n->left, c, c->left);
112 rotate_left (&sp->root, n, n->left);
113 }
114 else if (cmp1 > 0 && cmp2 > 0)
115 {
116 rotate_right (&n->right, c, c->right);
117 rotate_right (&sp->root, n, n->right);
118 }
119 else if (cmp1 < 0 && cmp2 > 0)
120 {
121 rotate_right (&n->left, c, c->right);
122 rotate_left (&sp->root, n, n->left);
123 }
124 else if (cmp1 > 0 && cmp2 < 0)
125 {
126 rotate_left (&n->right, c, c->left);
127 rotate_right (&sp->root, n, n->right);
128 }
129 } while (1);
130 }
131
132 /* Insert a new NODE into SP. The NODE shouldn't exist in the tree. */
133
134 attribute_hidden void
135 splay_tree_insert (splay_tree sp, splay_tree_node node)
136 {
137 int comparison = 0;
138
139 splay_tree_splay (sp, &node->key);
140
141 if (sp->root)
142 comparison = splay_compare (&sp->root->key, &node->key);
143
144 if (sp->root && comparison == 0)
145 gomp_fatal ("Duplicate node");
146 else
147 {
148 /* Insert it at the root. */
149 if (sp->root == NULL)
150 node->left = node->right = NULL;
151 else if (comparison < 0)
152 {
153 node->left = sp->root;
154 node->right = node->left->right;
155 node->left->right = NULL;
156 }
157 else
158 {
159 node->right = sp->root;
160 node->left = node->right->left;
161 node->right->left = NULL;
162 }
163
164 sp->root = node;
165 }
166 }
167
168 /* Remove node with KEY from SP. It is not an error if it did not exist. */
169
170 attribute_hidden void
171 splay_tree_remove (splay_tree sp, splay_tree_key key)
172 {
173 splay_tree_splay (sp, key);
174
175 if (sp->root && splay_compare (&sp->root->key, key) == 0)
176 {
177 splay_tree_node left, right;
178
179 left = sp->root->left;
180 right = sp->root->right;
181
182 /* One of the children is now the root. Doesn't matter much
183 which, so long as we preserve the properties of the tree. */
184 if (left)
185 {
186 sp->root = left;
187
188 /* If there was a right child as well, hang it off the
189 right-most leaf of the left child. */
190 if (right)
191 {
192 while (left->right)
193 left = left->right;
194 left->right = right;
195 }
196 }
197 else
198 sp->root = right;
199 }
200 }
201
202 /* Lookup KEY in SP, returning NODE if present, and NULL
203 otherwise. */
204
205 attribute_hidden splay_tree_key
206 splay_tree_lookup (splay_tree sp, splay_tree_key key)
207 {
208 splay_tree_splay (sp, key);
209
210 if (sp->root && splay_compare (&sp->root->key, key) == 0)
211 return &sp->root->key;
212 else
213 return NULL;
214 }
215
216 /* Helper function for splay_tree_foreach.
217
218 Run FUNC on every node in KEY. */
219
220 static void
221 splay_tree_foreach_internal (splay_tree_node node, splay_tree_callback func,
222 void *data)
223 {
224 if (!node)
225 return;
226 func (&node->key, data);
227 splay_tree_foreach_internal (node->left, func, data);
228 /* Yeah, whatever. GCC can fix my tail recursion. */
229 splay_tree_foreach_internal (node->right, func, data);
230 }
231
232 /* Run FUNC on each of the nodes in SP. */
233
234 attribute_hidden void
235 splay_tree_foreach (splay_tree sp, splay_tree_callback func, void *data)
236 {
237 splay_tree_foreach_internal (sp->root, func, data);
238 }
239
240 /* Like above, except when func returns != 0, stop early. */
241
242 static int
243 splay_tree_foreach_internal_lazy (splay_tree_node node,
244 splay_tree_callback_stop func, void *data)
245 {
246 if (!node)
247 return 0;
248 if (func (&node->key, data))
249 return 1;
250 if (splay_tree_foreach_internal_lazy (node->left, func, data))
251 return 1;
252 /* Yeah, whatever. GCC can fix my tail recursion. */
253 return splay_tree_foreach_internal_lazy (node->right, func, data);
254 }
255
256 attribute_hidden void
257 splay_tree_foreach_lazy (splay_tree sp, splay_tree_callback_stop func, void *data)
258 {
259 splay_tree_foreach_internal_lazy (sp->root, func, data);
260 }