OpenCores
URL https://opencores.org/ocsvn/openrisc_me/openrisc_me/trunk

Subversion Repositories openrisc_me

[/] [openrisc/] [trunk/] [gnu-src/] [gcc-4.5.1/] [gcc/] [fortran/] [bbt.c] - Blame information for rev 329

Go to most recent revision | Details | Compare with Previous | View Log

Line No. Rev Author Line
1 285 jeremybenn
/* Balanced binary trees using treaps.
2
   Copyright (C) 2000, 2002, 2003, 2007, 2008
3
   Free Software Foundation, Inc.
4
   Contributed by Andy Vaught
5
 
6
This file is part of GCC.
7
 
8
GCC is free software; you can redistribute it and/or modify it under
9
the terms of the GNU General Public License as published by the Free
10
Software Foundation; either version 3, or (at your option) any later
11
version.
12
 
13
GCC is distributed in the hope that it will be useful, but WITHOUT ANY
14
WARRANTY; without even the implied warranty of MERCHANTABILITY or
15
FITNESS FOR A PARTICULAR PURPOSE.  See the GNU General Public License
16
for more details.
17
 
18
You should have received a copy of the GNU General Public License
19
along with GCC; see the file COPYING3.  If not see
20
<http://www.gnu.org/licenses/>.  */
21
 
22
/* The idea is to balance the tree using pseudorandom numbers.  The
23
   main constraint on this implementation is that we have several
24
   distinct structures that have to be arranged in a binary tree.
25
   These structures all contain a BBT_HEADER() in front that gives the
26
   treap-related information.  The key and value are assumed to reside
27
   in the rest of the structure.
28
 
29
   When calling, we are also passed a comparison function that
30
   compares two nodes.  We don't implement a separate 'find' function
31
   here, but rather use separate functions for each variety of tree.
32
   We are also restricted to not copy treap structures, which most
33
   implementations find convenient, because we otherwise would need to
34
   know how long the structure is.
35
 
36
   This implementation is based on Stefan Nilsson's article in the
37
   July 1997 Doctor Dobb's Journal, "Treaps in Java".  */
38
 
39
#include "config.h"
40
#include "gfortran.h"
41
 
42
typedef struct gfc_treap
43
{
44
  BBT_HEADER (gfc_treap);
45
}
46
gfc_bbt;
47
 
48
/* Simple linear congruential pseudorandom number generator.  The
49
   period of this generator is 44071, which is plenty for our
50
   purposes.  */
51
 
52
static int
53
pseudo_random (void)
54
{
55
  static int x0 = 5341;
56
 
57
  x0 = (22611 * x0 + 10) % 44071;
58
  return x0;
59
}
60
 
61
 
62
/* Rotate the treap left.  */
63
 
64
static gfc_bbt *
65
rotate_left (gfc_bbt *t)
66
{
67
  gfc_bbt *temp;
68
 
69
  temp = t->right;
70
  t->right = t->right->left;
71
  temp->left = t;
72
 
73
  return temp;
74
}
75
 
76
 
77
/* Rotate the treap right.  */
78
 
79
static gfc_bbt *
80
rotate_right (gfc_bbt *t)
81
{
82
  gfc_bbt *temp;
83
 
84
  temp = t->left;
85
  t->left = t->left->right;
86
  temp->right = t;
87
 
88
  return temp;
89
}
90
 
91
 
92
/* Recursive insertion function.  Returns the updated treap, or
93
   aborts if we find a duplicate key.  */
94
 
95
static gfc_bbt *
96
insert (gfc_bbt *new_bbt, gfc_bbt *t, compare_fn compare)
97
{
98
  int c;
99
 
100
  if (t == NULL)
101
    return new_bbt;
102
 
103
  c = (*compare) (new_bbt, t);
104
 
105
  if (c < 0)
106
    {
107
      t->left = insert (new_bbt, t->left, compare);
108
      if (t->priority < t->left->priority)
109
        t = rotate_right (t);
110
    }
111
  else if (c > 0)
112
    {
113
      t->right = insert (new_bbt, t->right, compare);
114
      if (t->priority < t->right->priority)
115
        t = rotate_left (t);
116
    }
117
  else /* if (c == 0)  */
118
    gfc_internal_error("insert_bbt(): Duplicate key found!");
119
 
120
  return t;
121
}
122
 
123
 
124
/* Given root pointer, a new node and a comparison function, insert
125
   the new node into the treap.  It is an error to insert a key that
126
   already exists.  */
127
 
128
void
129
gfc_insert_bbt (void *root, void *new_node, compare_fn compare)
130
{
131
  gfc_bbt **r, *n;
132
 
133
  r = (gfc_bbt **) root;
134
  n = (gfc_bbt *) new_node;
135
  n->priority = pseudo_random ();
136
  *r = insert (n, *r, compare);
137
}
138
 
139
static gfc_bbt *
140
delete_root (gfc_bbt *t)
141
{
142
  gfc_bbt *temp;
143
 
144
  if (t->left == NULL)
145
    return t->right;
146
  if (t->right == NULL)
147
    return t->left;
148
 
149
  if (t->left->priority > t->right->priority)
150
    {
151
      temp = rotate_right (t);
152
      temp->right = delete_root (t);
153
    }
154
  else
155
    {
156
      temp = rotate_left (t);
157
      temp->left = delete_root (t);
158
    }
159
 
160
  return temp;
161
}
162
 
163
 
164
/* Delete an element from a tree.  The 'old' value does not
165
   necessarily have to point to the element to be deleted, it must
166
   just point to a treap structure with the key to be deleted.
167
   Returns the new root node of the tree.  */
168
 
169
static gfc_bbt *
170
delete_treap (gfc_bbt *old, gfc_bbt *t, compare_fn compare)
171
{
172
  int c;
173
 
174
  if (t == NULL)
175
    return NULL;
176
 
177
  c = (*compare) (old, t);
178
 
179
  if (c < 0)
180
    t->left = delete_treap (old, t->left, compare);
181
  if (c > 0)
182
    t->right = delete_treap (old, t->right, compare);
183
  if (c == 0)
184
    t = delete_root (t);
185
 
186
  return t;
187
}
188
 
189
 
190
void
191
gfc_delete_bbt (void *root, void *old, compare_fn compare)
192
{
193
  gfc_bbt **t;
194
 
195
  t = (gfc_bbt **) root;
196
  *t = delete_treap ((gfc_bbt *) old, *t, compare);
197
}

powered by: WebSVN 2.1.0

© copyright 1999-2024 OpenCores.org, equivalent to Oliscience, all rights reserved. OpenCores®, registered trademark.