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