1/* Balanced binary trees using treaps.
2 Copyright (C) 2000-2023 Free Software Foundation, Inc.
3 Contributed by Andy Vaught
4
5This file is part of GCC.
6
7GCC is free software; you can redistribute it and/or modify it under
8the terms of the GNU General Public License as published by the Free
9Software Foundation; either version 3, or (at your option) any later
10version.
11
12GCC is distributed in the hope that it will be useful, but WITHOUT ANY
13WARRANTY; without even the implied warranty of MERCHANTABILITY or
14FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License
15for more details.
16
17You should have received a copy of the GNU General Public License
18along 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
43typedef struct gfc_treap
44{
45 BBT_HEADER (gfc_treap);
46}
47gfc_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
53static int
54pseudo_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
65static gfc_bbt *
66rotate_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
80static gfc_bbt *
81rotate_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
96static gfc_bbt *
97insert (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: 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: 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
129void
130gfc_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 (new_bbt: n, t: *r, compare);
138}
139
140static gfc_bbt *
141delete_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, 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
171static gfc_bbt *
172delete_treap (gfc_bbt *old, gfc_bbt *t, compare_fn compare, gfc_bbt **removed)
173{
174 int c;
175
176 if (t == nullptr)
177 {
178 if (removed)
179 *removed = nullptr;
180 return nullptr;
181 }
182
183 c = (*compare) (old, t);
184
185 if (c < 0)
186 t->left = delete_treap (old, t: t->left, compare, removed);
187 if (c > 0)
188 t->right = delete_treap (old, t: t->right, compare, removed);
189 if (c == 0)
190 {
191 if (removed)
192 *removed = t;
193 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
205void *
206gfc_delete_bbt (void *root, void *old, compare_fn compare)
207{
208 gfc_bbt **t;
209 gfc_bbt *removed;
210
211 t = (gfc_bbt **) root;
212 *t = delete_treap (old: (gfc_bbt *) old, t: *t, compare, removed: &removed);
213
214 return (void *) removed;
215}
216

source code of gcc/fortran/bbt.cc