Branch data Line data Source code
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 : 7025330 : pseudo_random (void)
55 : : {
56 : 7025330 : static int x0 = 5341;
57 : :
58 : 7025330 : x0 = (22611 * x0 + 10) % 44071;
59 : 7025330 : return x0;
60 : : }
61 : :
62 : :
63 : : /* Rotate the treap left. */
64 : :
65 : : static gfc_bbt *
66 : 5007377 : rotate_left (gfc_bbt *t)
67 : : {
68 : 5007377 : gfc_bbt *temp;
69 : :
70 : 5007377 : temp = t->right;
71 : 5007377 : t->right = t->right->left;
72 : 5007377 : temp->left = t;
73 : :
74 : 5007377 : return temp;
75 : : }
76 : :
77 : :
78 : : /* Rotate the treap right. */
79 : :
80 : : static gfc_bbt *
81 : 3847530 : rotate_right (gfc_bbt *t)
82 : : {
83 : 3847530 : gfc_bbt *temp;
84 : :
85 : 3847530 : temp = t->left;
86 : 3847530 : t->left = t->left->right;
87 : 3847530 : temp->right = t;
88 : :
89 : 3847530 : 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 : 36423794 : insert (gfc_bbt *new_bbt, gfc_bbt *t, compare_fn compare)
98 : : {
99 : 36423794 : int c;
100 : :
101 : 36423794 : if (t == NULL)
102 : : return new_bbt;
103 : :
104 : 29398464 : c = (*compare) (new_bbt, t);
105 : :
106 : 29398464 : if (c < 0)
107 : : {
108 : 11939530 : t->left = insert (new_bbt, t->left, compare);
109 : 11939530 : if (t->priority < t->left->priority)
110 : 3271215 : t = rotate_right (t);
111 : : }
112 : 17458934 : else if (c > 0)
113 : : {
114 : 17458934 : t->right = insert (new_bbt, t->right, compare);
115 : 17458934 : if (t->priority < t->right->priority)
116 : 4431572 : 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 : 7025330 : gfc_insert_bbt (void *root, void *new_node, compare_fn compare)
131 : : {
132 : 7025330 : gfc_bbt **r, *n;
133 : :
134 : 7025330 : r = (gfc_bbt **) root;
135 : 7025330 : n = (gfc_bbt *) new_node;
136 : 7025330 : n->priority = pseudo_random ();
137 : 7025330 : *r = insert (n, *r, compare);
138 : 7025330 : }
139 : :
140 : : static gfc_bbt *
141 : 4630674 : delete_root (gfc_bbt *t)
142 : : {
143 : 4630674 : gfc_bbt *temp;
144 : :
145 : 4630674 : if (t->left == NULL)
146 : 2537690 : return t->right;
147 : 2092984 : if (t->right == NULL)
148 : : return t->left;
149 : :
150 : 1152120 : if (t->left->priority > t->right->priority)
151 : : {
152 : 576315 : temp = rotate_right (t);
153 : 576315 : temp->right = delete_root (t);
154 : : }
155 : : else
156 : : {
157 : 575805 : temp = rotate_left (t);
158 : 575805 : 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 *
171 : 11382703 : delete_treap (gfc_bbt *old, gfc_bbt *t, compare_fn compare)
172 : : {
173 : 11382703 : int c;
174 : :
175 : 11382703 : if (t == NULL)
176 : : return NULL;
177 : :
178 : 11382703 : c = (*compare) (old, t);
179 : :
180 : 11382703 : if (c < 0)
181 : 3672871 : t->left = delete_treap (old, t->left, compare);
182 : 11382703 : if (c > 0)
183 : 4231278 : t->right = delete_treap (old, t->right, compare);
184 : 11382703 : if (c == 0)
185 : 3478554 : t = delete_root (t);
186 : :
187 : : return t;
188 : : }
189 : :
190 : :
191 : : void
192 : 3478554 : gfc_delete_bbt (void *root, void *old, compare_fn compare)
193 : : {
194 : 3478554 : gfc_bbt **t;
195 : :
196 : 3478554 : t = (gfc_bbt **) root;
197 : 3478554 : *t = delete_treap ((gfc_bbt *) old, *t, compare);
198 : 3478554 : }
|
