Branch data Line data Source code
1 : : /* Balanced binary trees using treaps.
2 : : Copyright (C) 2000-2025 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 : 8029484 : pseudo_random (void)
55 : : {
56 : 8029484 : static int x0 = 5341;
57 : :
58 : 8029484 : x0 = (22611 * x0 + 10) % 44071;
59 : 8029484 : return x0;
60 : : }
61 : :
62 : :
63 : : /* Rotate the treap left. */
64 : :
65 : : static gfc_bbt *
66 : 5767037 : rotate_left (gfc_bbt *t)
67 : : {
68 : 5767037 : gfc_bbt *temp;
69 : :
70 : 5767037 : temp = t->right;
71 : 5767037 : t->right = t->right->left;
72 : 5767037 : temp->left = t;
73 : :
74 : 5767037 : return temp;
75 : : }
76 : :
77 : :
78 : : /* Rotate the treap right. */
79 : :
80 : : static gfc_bbt *
81 : 4364836 : rotate_right (gfc_bbt *t)
82 : : {
83 : 4364836 : gfc_bbt *temp;
84 : :
85 : 4364836 : temp = t->left;
86 : 4364836 : t->left = t->left->right;
87 : 4364836 : temp->right = t;
88 : :
89 : 4364836 : 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 : 42173740 : insert (gfc_bbt *new_bbt, gfc_bbt *t, compare_fn compare)
98 : : {
99 : 42173740 : int c;
100 : :
101 : 42173740 : if (t == NULL)
102 : : return new_bbt;
103 : :
104 : 34144256 : c = (*compare) (new_bbt, t);
105 : :
106 : 34144256 : if (c < 0)
107 : : {
108 : 13483702 : t->left = insert (new_bbt, t->left, compare);
109 : 13483702 : if (t->priority < t->left->priority)
110 : 3731954 : t = rotate_right (t);
111 : : }
112 : 20660554 : else if (c > 0)
113 : : {
114 : 20660554 : t->right = insert (new_bbt, t->right, compare);
115 : 20660554 : if (t->priority < t->right->priority)
116 : 5126474 : t = rotate_left (t);
117 : : }
118 : : else /* if (c == 0) */
119 : 0 : 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 : 8029484 : gfc_insert_bbt (void *root, void *new_node, compare_fn compare)
131 : : {
132 : 8029484 : gfc_bbt **r, *n;
133 : :
134 : 8029484 : r = (gfc_bbt **) root;
135 : 8029484 : n = (gfc_bbt *) new_node;
136 : 8029484 : n->priority = pseudo_random ();
137 : 8029484 : *r = insert (n, *r, compare);
138 : 8029484 : }
139 : :
140 : : static gfc_bbt *
141 : 5124672 : delete_root (gfc_bbt *t)
142 : : {
143 : 5124672 : gfc_bbt *temp;
144 : :
145 : 5124672 : if (t->left == NULL)
146 : 2803711 : return t->right;
147 : 2320961 : if (t->right == NULL)
148 : : return t->left;
149 : :
150 : 1273445 : if (t->left->priority > t->right->priority)
151 : : {
152 : 632882 : temp = rotate_right (t);
153 : 632882 : temp->right = delete_root (t);
154 : : }
155 : : else
156 : : {
157 : 640563 : temp = rotate_left (t);
158 : 640563 : 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 : 12484652 : delete_treap (gfc_bbt *old, gfc_bbt *t, compare_fn compare, gfc_bbt **removed)
173 : : {
174 : 12484652 : int c;
175 : :
176 : 12484652 : if (t == nullptr)
177 : : {
178 : 0 : if (removed)
179 : 0 : *removed = nullptr;
180 : 0 : return nullptr;
181 : : }
182 : :
183 : 12484652 : c = (*compare) (old, t);
184 : :
185 : 12484652 : if (c < 0)
186 : 4009278 : t->left = delete_treap (old, t->left, compare, removed);
187 : 12484652 : if (c > 0)
188 : 4624147 : t->right = delete_treap (old, t->right, compare, removed);
189 : 12484652 : if (c == 0)
190 : : {
191 : 3851227 : if (removed)
192 : 3851227 : *removed = t;
193 : 3851227 : 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 : 3851227 : gfc_delete_bbt (void *root, void *old, compare_fn compare)
207 : : {
208 : 3851227 : gfc_bbt **t;
209 : 3851227 : gfc_bbt *removed;
210 : :
211 : 3851227 : t = (gfc_bbt **) root;
212 : 3851227 : *t = delete_treap ((gfc_bbt *) old, *t, compare, &removed);
213 : :
214 : 3851227 : return (void *) removed;
215 : : }
|
