Mercurial > hg > CbC > CbC_gcc

comparison gcc/fortran/bbt.c @ 111:04ced10e8804

Find changesets by keywords (author, files, the commit message), revision number or hash, or revset expression.
gcc 7
author kono
date Fri, 27 Oct 2017 22:46:09 +0900
parents
children 84e7813d76e9
comparison
equal deleted inserted replaced
68:561a7518be6b 111:04ced10e8804
1 /* Balanced binary trees using treaps.
2 Copyright (C) 2000-2017 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 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 }