1 | /* Balanced binary trees using treaps. |
2 | Copyright (C) 2000-2023 Free Software Foundation, Inc. |
3 | Contributed by Andy Vaught |
4 | |
5 | This file is part of GCC. |
6 | |
7 | GCC is free software; you can redistribute it and/or modify it under |
8 | the terms of the GNU General Public License as published by the Free |
9 | Software Foundation; either version 3, or (at your option) any later |
10 | version. |
11 | |
12 | GCC is distributed in the hope that it will be useful, but WITHOUT ANY |
13 | WARRANTY; without even the implied warranty of MERCHANTABILITY or |
14 | FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License |
15 | for more details. |
16 | |
17 | You should have received a copy of the GNU General Public License |
18 | along with GCC; see the file COPYING3. If not see |
19 | <http://www.gnu.org/licenses/>. */ |
20 | |
21 | /* The idea is to balance the tree using pseudorandom numbers. The |
22 | main constraint on this implementation is that we have several |
23 | distinct structures that have to be arranged in a binary tree. |
24 | These structures all contain a BBT_HEADER() in front that gives the |
25 | treap-related information. The key and value are assumed to reside |
26 | in the rest of the structure. |
27 | |
28 | When calling, we are also passed a comparison function that |
29 | compares two nodes. We don't implement a separate 'find' function |
30 | here, but rather use separate functions for each variety of tree. |
31 | We are also restricted to not copy treap structures, which most |
32 | implementations find convenient, because we otherwise would need to |
33 | know how long the structure is. |
34 | |
35 | This implementation is based on Stefan Nilsson's article in the |
36 | July 1997 Doctor Dobb's Journal, "Treaps in Java". */ |
37 | |
38 | #include "config.h" |
39 | #include "system.h" |
40 | #include "coretypes.h" |
41 | #include "gfortran.h" |
42 | |
43 | typedef struct gfc_treap |
44 | { |
45 | BBT_HEADER (gfc_treap); |
46 | } |
47 | gfc_bbt; |
48 | |
49 | /* Simple linear congruential pseudorandom number generator. The |
50 | period of this generator is 44071, which is plenty for our |
51 | purposes. */ |
52 | |
53 | static int |
54 | pseudo_random (void) |
55 | { |
56 | static int x0 = 5341; |
57 | |
58 | x0 = (22611 * x0 + 10) % 44071; |
59 | return x0; |
60 | } |
61 | |
62 | |
63 | /* Rotate the treap left. */ |
64 | |
65 | static gfc_bbt * |
66 | rotate_left (gfc_bbt *t) |
67 | { |
68 | gfc_bbt *temp; |
69 | |
70 | temp = t->right; |
71 | t->right = t->right->left; |
72 | temp->left = t; |
73 | |
74 | return temp; |
75 | } |
76 | |
77 | |
78 | /* Rotate the treap right. */ |
79 | |
80 | static gfc_bbt * |
81 | rotate_right (gfc_bbt *t) |
82 | { |
83 | gfc_bbt *temp; |
84 | |
85 | temp = t->left; |
86 | t->left = t->left->right; |
87 | temp->right = t; |
88 | |
89 | return temp; |
90 | } |
91 | |
92 | |
93 | /* Recursive insertion function. Returns the updated treap, or |
94 | aborts if we find a duplicate key. */ |
95 | |
96 | static gfc_bbt * |
97 | insert (gfc_bbt *new_bbt, gfc_bbt *t, compare_fn compare) |
98 | { |
99 | int c; |
100 | |
101 | if (t == NULL) |
102 | return new_bbt; |
103 | |
104 | c = (*compare) (new_bbt, t); |
105 | |
106 | if (c < 0) |
107 | { |
108 | t->left = insert (new_bbt, t: t->left, compare); |
109 | if (t->priority < t->left->priority) |
110 | t = rotate_right (t); |
111 | } |
112 | else if (c > 0) |
113 | { |
114 | t->right = insert (new_bbt, t: t->right, compare); |
115 | if (t->priority < t->right->priority) |
116 | t = rotate_left (t); |
117 | } |
118 | else /* if (c == 0) */ |
119 | gfc_internal_error("insert_bbt(): Duplicate key found" ); |
120 | |
121 | return t; |
122 | } |
123 | |
124 | |
125 | /* Given root pointer, a new node and a comparison function, insert |
126 | the new node into the treap. It is an error to insert a key that |
127 | already exists. */ |
128 | |
129 | void |
130 | gfc_insert_bbt (void *root, void *new_node, compare_fn compare) |
131 | { |
132 | gfc_bbt **r, *n; |
133 | |
134 | r = (gfc_bbt **) root; |
135 | n = (gfc_bbt *) new_node; |
136 | n->priority = pseudo_random (); |
137 | *r = insert (new_bbt: n, t: *r, compare); |
138 | } |
139 | |
140 | static gfc_bbt * |
141 | delete_root (gfc_bbt *t) |
142 | { |
143 | gfc_bbt *temp; |
144 | |
145 | if (t->left == NULL) |
146 | return t->right; |
147 | if (t->right == NULL) |
148 | return t->left; |
149 | |
150 | if (t->left->priority > t->right->priority) |
151 | { |
152 | temp = rotate_right (t); |
153 | temp->right = delete_root (t); |
154 | } |
155 | else |
156 | { |
157 | temp = rotate_left (t); |
158 | temp->left = delete_root (t); |
159 | } |
160 | |
161 | return temp; |
162 | } |
163 | |
164 | |
165 | /* Delete an element from a tree, returning the new root node of the tree. |
166 | The OLD value does not necessarily have to point to the element to be |
167 | deleted, it must just point to a treap structure with the key to be deleted. |
168 | The REMOVED argument, if non-null, is set to the removed element from the |
169 | tree upon return. */ |
170 | |
171 | static gfc_bbt * |
172 | delete_treap (gfc_bbt *old, gfc_bbt *t, compare_fn compare, gfc_bbt **removed) |
173 | { |
174 | int c; |
175 | |
176 | if (t == nullptr) |
177 | { |
178 | if (removed) |
179 | *removed = nullptr; |
180 | return nullptr; |
181 | } |
182 | |
183 | c = (*compare) (old, t); |
184 | |
185 | if (c < 0) |
186 | t->left = delete_treap (old, t: t->left, compare, removed); |
187 | if (c > 0) |
188 | t->right = delete_treap (old, t: t->right, compare, removed); |
189 | if (c == 0) |
190 | { |
191 | if (removed) |
192 | *removed = t; |
193 | t = delete_root (t); |
194 | } |
195 | |
196 | return t; |
197 | } |
198 | |
199 | |
200 | /* Delete the element from the tree at *ROOT that matches the OLD element |
201 | according to the COMPARE_FN function. This updates the *ROOT pointer to |
202 | point to the new tree root (if different from the original) and returns the |
203 | deleted element. */ |
204 | |
205 | void * |
206 | gfc_delete_bbt (void *root, void *old, compare_fn compare) |
207 | { |
208 | gfc_bbt **t; |
209 | gfc_bbt *removed; |
210 | |
211 | t = (gfc_bbt **) root; |
212 | *t = delete_treap (old: (gfc_bbt *) old, t: *t, compare, removed: &removed); |
213 | |
214 | return (void *) removed; |
215 | } |
216 | |