Mercurial > hg > CbC > CbC_gcc
comparison libgomp/splay-tree.c @ 111:04ced10e8804
gcc 7
author | kono |
---|---|
date | Fri, 27 Oct 2017 22:46:09 +0900 |
parents | |
children | 84e7813d76e9 |
comparison
equal
deleted
inserted
replaced
68:561a7518be6b | 111:04ced10e8804 |
---|---|
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 } |