]>
Commit | Line | Data |
---|---|---|
41dbbb37 | 1 | /* A splay-tree datatype. |
a945c346 | 2 | Copyright (C) 1998-2024 Free Software Foundation, Inc. |
41dbbb37 TS |
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" | |
41dbbb37 TS |
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 | ||
d4b6d147 TB |
134 | #ifdef splay_tree_static |
135 | __attribute__((unused)) static void | |
136 | #else | |
41dbbb37 | 137 | attribute_hidden void |
d4b6d147 | 138 | #endif |
41dbbb37 TS |
139 | splay_tree_insert (splay_tree sp, splay_tree_node node) |
140 | { | |
141 | int comparison = 0; | |
142 | ||
143 | splay_tree_splay (sp, &node->key); | |
144 | ||
145 | if (sp->root) | |
146 | comparison = splay_compare (&sp->root->key, &node->key); | |
147 | ||
148 | if (sp->root && comparison == 0) | |
149 | gomp_fatal ("Duplicate node"); | |
150 | else | |
151 | { | |
152 | /* Insert it at the root. */ | |
153 | if (sp->root == NULL) | |
154 | node->left = node->right = NULL; | |
155 | else if (comparison < 0) | |
156 | { | |
157 | node->left = sp->root; | |
158 | node->right = node->left->right; | |
159 | node->left->right = NULL; | |
160 | } | |
161 | else | |
162 | { | |
163 | node->right = sp->root; | |
164 | node->left = node->right->left; | |
165 | node->right->left = NULL; | |
166 | } | |
167 | ||
168 | sp->root = node; | |
169 | } | |
170 | } | |
171 | ||
172 | /* Remove node with KEY from SP. It is not an error if it did not exist. */ | |
173 | ||
d4b6d147 TB |
174 | #ifdef splay_tree_static |
175 | __attribute__((unused)) static void | |
176 | #else | |
41dbbb37 | 177 | attribute_hidden void |
d4b6d147 | 178 | #endif |
41dbbb37 TS |
179 | splay_tree_remove (splay_tree sp, splay_tree_key key) |
180 | { | |
181 | splay_tree_splay (sp, key); | |
182 | ||
183 | if (sp->root && splay_compare (&sp->root->key, key) == 0) | |
184 | { | |
185 | splay_tree_node left, right; | |
186 | ||
187 | left = sp->root->left; | |
188 | right = sp->root->right; | |
189 | ||
190 | /* One of the children is now the root. Doesn't matter much | |
191 | which, so long as we preserve the properties of the tree. */ | |
192 | if (left) | |
193 | { | |
194 | sp->root = left; | |
195 | ||
196 | /* If there was a right child as well, hang it off the | |
197 | right-most leaf of the left child. */ | |
198 | if (right) | |
199 | { | |
200 | while (left->right) | |
201 | left = left->right; | |
202 | left->right = right; | |
203 | } | |
204 | } | |
205 | else | |
206 | sp->root = right; | |
207 | } | |
208 | } | |
209 | ||
210 | /* Lookup KEY in SP, returning NODE if present, and NULL | |
211 | otherwise. */ | |
212 | ||
d4b6d147 TB |
213 | #ifdef splay_tree_static |
214 | __attribute__((unused)) static splay_tree_node | |
215 | #else | |
216 | attribute_hidden splay_tree_node | |
217 | #endif | |
218 | splay_tree_lookup_node (splay_tree sp, splay_tree_key key) | |
219 | { | |
220 | splay_tree_splay (sp, key); | |
221 | ||
222 | if (sp->root && splay_compare (&sp->root->key, key) == 0) | |
223 | return sp->root; | |
224 | else | |
225 | return NULL; | |
226 | } | |
227 | ||
228 | /* Likewise but return the key. */ | |
229 | ||
230 | #ifdef splay_tree_static | |
231 | __attribute__((unused)) static splay_tree_key | |
232 | #else | |
41dbbb37 | 233 | attribute_hidden splay_tree_key |
d4b6d147 | 234 | #endif |
41dbbb37 TS |
235 | splay_tree_lookup (splay_tree sp, splay_tree_key key) |
236 | { | |
237 | splay_tree_splay (sp, key); | |
238 | ||
239 | if (sp->root && splay_compare (&sp->root->key, key) == 0) | |
240 | return &sp->root->key; | |
241 | else | |
242 | return NULL; | |
243 | } | |
e4606348 JJ |
244 | |
245 | /* Helper function for splay_tree_foreach. | |
246 | ||
247 | Run FUNC on every node in KEY. */ | |
248 | ||
249 | static void | |
250 | splay_tree_foreach_internal (splay_tree_node node, splay_tree_callback func, | |
251 | void *data) | |
252 | { | |
253 | if (!node) | |
254 | return; | |
255 | func (&node->key, data); | |
256 | splay_tree_foreach_internal (node->left, func, data); | |
257 | /* Yeah, whatever. GCC can fix my tail recursion. */ | |
258 | splay_tree_foreach_internal (node->right, func, data); | |
259 | } | |
260 | ||
261 | /* Run FUNC on each of the nodes in SP. */ | |
262 | ||
d4b6d147 TB |
263 | #ifdef splay_tree_static |
264 | __attribute__((unused)) static void | |
265 | #else | |
e4606348 | 266 | attribute_hidden void |
d4b6d147 | 267 | #endif |
e4606348 JJ |
268 | splay_tree_foreach (splay_tree sp, splay_tree_callback func, void *data) |
269 | { | |
270 | splay_tree_foreach_internal (sp->root, func, data); | |
271 | } | |
ea4b23d9 TB |
272 | |
273 | /* Like above, except when func returns != 0, stop early. */ | |
274 | ||
275 | static int | |
276 | splay_tree_foreach_internal_lazy (splay_tree_node node, | |
277 | splay_tree_callback_stop func, void *data) | |
278 | { | |
279 | if (!node) | |
280 | return 0; | |
281 | if (func (&node->key, data)) | |
282 | return 1; | |
283 | if (splay_tree_foreach_internal_lazy (node->left, func, data)) | |
284 | return 1; | |
285 | /* Yeah, whatever. GCC can fix my tail recursion. */ | |
286 | return splay_tree_foreach_internal_lazy (node->right, func, data); | |
287 | } | |
288 | ||
d4b6d147 TB |
289 | #ifdef splay_tree_static |
290 | __attribute__((unused)) static void | |
291 | #else | |
ea4b23d9 | 292 | attribute_hidden void |
d4b6d147 TB |
293 | #endif |
294 | splay_tree_foreach_lazy (splay_tree sp, splay_tree_callback_stop func, | |
295 | void *data) | |
ea4b23d9 TB |
296 | { |
297 | splay_tree_foreach_internal_lazy (sp->root, func, data); | |
298 | } |