|
111
|
1 /* Balanced binary trees using treaps.
|
|
145
|
2 Copyright (C) 2000-2020 Free Software Foundation, Inc.
|
|
111
|
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->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->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 (n, *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. 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 delete_treap (gfc_bbt *old, gfc_bbt *t, compare_fn compare)
|
|
|
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;
|
|
|
197 *t = delete_treap ((gfc_bbt *) old, *t, compare);
|
|
|
198 }
|
