]>
Commit | Line | Data |
---|---|---|
6de9cd9a | 1 | /* Balanced binary trees using treaps. |
83ffe9cd | 2 | Copyright (C) 2000-2023 Free Software Foundation, Inc. |
6de9cd9a DN |
3 | Contributed by Andy Vaught |
4 | ||
9fc4d79b | 5 | This file is part of GCC. |
6de9cd9a | 6 | |
9fc4d79b TS |
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 | |
d234d788 | 9 | Software Foundation; either version 3, or (at your option) any later |
9fc4d79b | 10 | version. |
6de9cd9a | 11 | |
9fc4d79b TS |
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. | |
6de9cd9a DN |
16 | |
17 | You should have received a copy of the GNU General Public License | |
d234d788 NC |
18 | along with GCC; see the file COPYING3. If not see |
19 | <http://www.gnu.org/licenses/>. */ | |
6de9cd9a DN |
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" | |
7274feea | 39 | #include "system.h" |
953bee7c | 40 | #include "coretypes.h" |
6de9cd9a DN |
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 * | |
65f8144a | 66 | rotate_left (gfc_bbt *t) |
6de9cd9a DN |
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 * | |
65f8144a | 81 | rotate_right (gfc_bbt *t) |
6de9cd9a DN |
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 * | |
7b901ac4 | 97 | insert (gfc_bbt *new_bbt, gfc_bbt *t, compare_fn compare) |
6de9cd9a DN |
98 | { |
99 | int c; | |
100 | ||
101 | if (t == NULL) | |
7b901ac4 | 102 | return new_bbt; |
6de9cd9a | 103 | |
7b901ac4 | 104 | c = (*compare) (new_bbt, t); |
6de9cd9a DN |
105 | |
106 | if (c < 0) | |
107 | { | |
7b901ac4 | 108 | t->left = insert (new_bbt, t->left, compare); |
6de9cd9a DN |
109 | if (t->priority < t->left->priority) |
110 | t = rotate_right (t); | |
111 | } | |
6de9cd9a DN |
112 | else if (c > 0) |
113 | { | |
7b901ac4 | 114 | t->right = insert (new_bbt, t->right, compare); |
6de9cd9a DN |
115 | if (t->priority < t->right->priority) |
116 | t = rotate_left (t); | |
117 | } | |
6de9cd9a | 118 | else /* if (c == 0) */ |
546c8974 | 119 | gfc_internal_error("insert_bbt(): Duplicate key found"); |
6de9cd9a DN |
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 | |
7b901ac4 | 130 | gfc_insert_bbt (void *root, void *new_node, compare_fn compare) |
6de9cd9a DN |
131 | { |
132 | gfc_bbt **r, *n; | |
133 | ||
134 | r = (gfc_bbt **) root; | |
7b901ac4 | 135 | n = (gfc_bbt *) new_node; |
6de9cd9a DN |
136 | n->priority = pseudo_random (); |
137 | *r = insert (n, *r, compare); | |
138 | } | |
139 | ||
140 | static gfc_bbt * | |
65f8144a | 141 | delete_root (gfc_bbt *t) |
6de9cd9a DN |
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. The 'old' value does not | |
166 | necessarily have to point to the element to be deleted, it must | |
167 | just point to a treap structure with the key to be deleted. | |
168 | Returns the new root node of the tree. */ | |
169 | ||
170 | static gfc_bbt * | |
65f8144a | 171 | delete_treap (gfc_bbt *old, gfc_bbt *t, compare_fn compare) |
6de9cd9a DN |
172 | { |
173 | int c; | |
174 | ||
175 | if (t == NULL) | |
176 | return NULL; | |
177 | ||
178 | c = (*compare) (old, t); | |
179 | ||
180 | if (c < 0) | |
181 | t->left = delete_treap (old, t->left, compare); | |
182 | if (c > 0) | |
183 | t->right = delete_treap (old, t->right, compare); | |
184 | if (c == 0) | |
185 | t = delete_root (t); | |
186 | ||
187 | return t; | |
188 | } | |
189 | ||
190 | ||
191 | void | |
192 | gfc_delete_bbt (void *root, void *old, compare_fn compare) | |
193 | { | |
194 | gfc_bbt **t; | |
195 | ||
196 | t = (gfc_bbt **) root; | |
6de9cd9a DN |
197 | *t = delete_treap ((gfc_bbt *) old, *t, compare); |
198 | } |