]>
Commit | Line | Data |
---|---|---|
41dbbb37 | 1 | /* A splay-tree datatype. |
83ffe9cd | 2 | Copyright (C) 1998-2023 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 | ||
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 | } | |
e4606348 JJ |
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 | } | |
ea4b23d9 TB |
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 | } |