|
111
|
1 /* A splay-tree datatype.
|
|
|
2 Copyright (C) 1998-2017 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 }
|
