OSDN Git Service
(root)
/
pf3gnuchains
/
gcc-fork.git
/ blobdiff
commit
grep
author
committer
pickaxe
?
search:
re
summary
|
shortlog
|
log
|
commit
|
commitdiff
|
tree
raw
|
inline
| side by side
doc: fix deftypefn markup in gccint manual.
[pf3gnuchains/gcc-fork.git]
/
gcc
/
et-forest.c
diff --git
a/gcc/et-forest.c
b/gcc/et-forest.c
index
f193afd
..
d106316
100644
(file)
--- a/
gcc/et-forest.c
+++ b/
gcc/et-forest.c
@@
-1,12
+1,13
@@
/* ET-trees data structure implementation.
Contributed by Pavel Nejedly
/* ET-trees data structure implementation.
Contributed by Pavel Nejedly
- Copyright (C) 2002, 2003, 2004, 2005 Free Software Foundation, Inc.
+ Copyright (C) 2002, 2003, 2004, 2005, 2007, 2008, 2010 Free Software
+ Foundation, Inc.
This file is part of the libiberty library.
Libiberty is free software; you can redistribute it and/or
modify it under the terms of the GNU Library General Public
License as published by the Free Software Foundation; either
This file is part of the libiberty library.
Libiberty is free software; you can redistribute it and/or
modify it under the terms of the GNU Library General Public
License as published by the Free Software Foundation; either
-version
2
of the License, or (at your option) any later version.
+version
3
of the License, or (at your option) any later version.
Libiberty is distributed in the hope that it will be useful,
but WITHOUT ANY WARRANTY; without even the implied warranty of
Libiberty is distributed in the hope that it will be useful,
but WITHOUT ANY WARRANTY; without even the implied warranty of
@@
-14,9
+15,8
@@
MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
Library General Public License for more details.
You should have received a copy of the GNU Library General Public
Library General Public License for more details.
You should have received a copy of the GNU Library General Public
-License along with libiberty; see the file COPYING.LIB. If
-not, write to the Free Software Foundation, Inc., 51 Franklin Street, Fifth Floor,
-Boston, MA 02110-1301, USA.
+License along with libiberty; see the file COPYING3. If not see
+<http://www.gnu.org/licenses/>.
The ET-forest structure is described in:
D. D. Sleator and R. E. Tarjan. A data structure for dynamic trees.
The ET-forest structure is described in:
D. D. Sleator and R. E. Tarjan. A data structure for dynamic trees.
@@
-26,7
+26,6
@@
Boston, MA 02110-1301, USA.
#include "config.h"
#include "system.h"
#include "coretypes.h"
#include "config.h"
#include "system.h"
#include "coretypes.h"
-#include "tm.h"
#include "et-forest.h"
#include "alloc-pool.h"
#include "et-forest.h"
#include "alloc-pool.h"
@@
-210,7
+209,7
@@
record_path_before_1 (struct et_occ *occ, int depth)
if (occ->prev)
{
if (occ->prev)
{
- m = record_path_before_1 (occ->prev, depth);
+ m = record_path_before_1 (occ->prev, depth);
if (m < mn)
mn = m;
}
if (m < mn)
mn = m;
}
@@
-261,7
+260,7
@@
check_path_after_1 (struct et_occ *occ, int depth)
if (occ->next)
{
if (occ->next)
{
- m = check_path_after_1 (occ->next, depth);
+ m = check_path_after_1 (occ->next, depth);
if (m < mn)
mn = m;
}
if (m < mn)
mn = m;
}
@@
-308,7
+307,7
@@
et_splay (struct et_occ *occ)
record_path_before (occ);
et_check_tree_sanity (occ);
#endif
record_path_before (occ);
et_check_tree_sanity (occ);
#endif
-
+
while (occ->parent)
{
occ_depth = occ->depth;
while (occ->parent)
{
occ_depth = occ->depth;
@@
-444,10
+443,10
@@
static struct et_occ *
et_new_occ (struct et_node *node)
{
struct et_occ *nw;
et_new_occ (struct et_node *node)
{
struct et_occ *nw;
-
+
if (!et_occurrences)
et_occurrences = create_alloc_pool ("et_occ pool", sizeof (struct et_occ), 300);
if (!et_occurrences)
et_occurrences = create_alloc_pool ("et_occ pool", sizeof (struct et_occ), 300);
- nw = pool_alloc (et_occurrences);
+ nw =
(struct et_occ *)
pool_alloc (et_occurrences);
nw->of = node;
nw->parent = NULL;
nw->of = node;
nw->parent = NULL;
@@
-467,10
+466,10
@@
struct et_node *
et_new_tree (void *data)
{
struct et_node *nw;
et_new_tree (void *data)
{
struct et_node *nw;
-
+
if (!et_nodes)
et_nodes = create_alloc_pool ("et_node pool", sizeof (struct et_node), 300);
if (!et_nodes)
et_nodes = create_alloc_pool ("et_node pool", sizeof (struct et_node), 300);
- nw = pool_alloc (et_nodes);
+ nw =
(struct et_node *)
pool_alloc (et_nodes);
nw->data = data;
nw->father = NULL;
nw->data = data;
nw->father = NULL;
@@
-505,9
+504,20
@@
void
et_free_tree_force (struct et_node *t)
{
pool_free (et_occurrences, t->rightmost_occ);
et_free_tree_force (struct et_node *t)
{
pool_free (et_occurrences, t->rightmost_occ);
+ if (t->parent_occ)
+ pool_free (et_occurrences, t->parent_occ);
pool_free (et_nodes, t);
}
pool_free (et_nodes, t);
}
+/* Release the alloc pools, if they are empty. */
+
+void
+et_free_pools (void)
+{
+ free_alloc_pool_if_empty (&et_occurrences);
+ free_alloc_pool_if_empty (&et_nodes);
+}
+
/* Sets father of et tree T to FATHER. */
void
/* Sets father of et tree T to FATHER. */
void
@@
-579,7
+589,7
@@
et_split (struct et_node *t)
for (r = rmost->next; r->prev; r = r->prev)
continue;
for (r = rmost->next; r->prev; r = r->prev)
continue;
- et_splay (r);
+ et_splay (r);
r->prev->parent = NULL;
p_occ = t->parent_occ;
r->prev->parent = NULL;
p_occ = t->parent_occ;
@@
-650,7
+660,7
@@
et_nca (struct et_node *n1, struct et_node *n2)
if (r)
r->parent = o1;
}
if (r)
r->parent = o1;
}
- else
+ else
if (r == o2 || (r && r->parent != NULL))
{
ret = o2->prev;
{
ret = o2->prev;
@@
-658,6
+668,15
@@
et_nca (struct et_node *n1, struct et_node *n2)
if (l)
l->parent = o1;
}
if (l)
l->parent = o1;
}
+ else
+ {
+ /* O1 and O2 are in different components of the forest. */
+ if (l)
+ l->parent = o1;
+ if (r)
+ r->parent = o1;
+ return NULL;
+ }
if (0 < o2->depth)
{
if (0 < o2->depth)
{
@@
-736,3
+755,20
@@
et_below (struct et_node *down, struct et_node *up)
return !d->next || d->next->min + d->depth >= 0;
}
return !d->next || d->next->min + d->depth >= 0;
}
+
+/* Returns the root of the tree that contains NODE. */
+
+struct et_node *
+et_root (struct et_node *node)
+{
+ struct et_occ *occ = node->rightmost_occ, *r;
+
+ /* The root of the tree corresponds to the rightmost occurrence in the
+ represented path. */
+ et_splay (occ);
+ for (r = occ; r->next; r = r->next)
+ continue;
+ et_splay (r);
+
+ return r->of;
+}