1/* Balanced binary trees using treaps.
2   Copyright (C) 2000-2015 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->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
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 (n, *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.  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
170static gfc_bbt *
171delete_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
191void
192gfc_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}
199