URL https://opencores.org/ocsvn/scarts/scarts/trunk

Subversion Repositories scarts

[/] [scarts/] [trunk/] [toolchain/] [scarts-gcc/] [gcc-4.1.1/] [gcc/] [et-forest.c] - Blame information for rev 16

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


/* ET-trees data structure implementation.
   Contributed by Pavel Nejedly
   Copyright (C) 2002, 2003, 2004, 2005 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
version 2 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
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
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.
 
  The ET-forest structure is described in:
    D. D. Sleator and R. E. Tarjan. A data structure for dynamic trees.
    J.  G'omput. System Sci., 26(3):362 381, 1983.
*/
 
#include "config.h"
#include "system.h"
#include "coretypes.h"
#include "tm.h"
#include "et-forest.h"
#include "alloc-pool.h"
 
/* We do not enable this with ENABLE_CHECKING, since it is awfully slow.  */
#undef DEBUG_ET
 
#ifdef DEBUG_ET
#include "basic-block.h"
#endif
 
/* The occurrence of a node in the et tree.  */
struct et_occ
{
  struct et_node *of;           /* The node.  */
 
  struct et_occ *parent;        /* Parent in the splay-tree.  */
  struct et_occ *prev;          /* Left son in the splay-tree.  */
  struct et_occ *next;          /* Right son in the splay-tree.  */
 
  int depth;                    /* The depth of the node is the sum of depth
                                   fields on the path to the root.  */
  int min;                      /* The minimum value of the depth in the subtree
                                   is obtained by adding sum of depth fields
                                   on the path to the root.  */
  struct et_occ *min_occ;       /* The occurrence in the subtree with the minimal
                                   depth.  */
};
 
static alloc_pool et_nodes;
static alloc_pool et_occurrences;
 
/* Changes depth of OCC to D.  */
 
static inline void
set_depth (struct et_occ *occ, int d)
{
  if (!occ)
    return;
 
  occ->min += d - occ->depth;
  occ->depth = d;
}
 
/* Adds D to the depth of OCC.  */
 
static inline void
set_depth_add (struct et_occ *occ, int d)
{
  if (!occ)
    return;
 
  occ->min += d;
  occ->depth += d;
}
 
/* Sets prev field of OCC to P.  */
 
static inline void
set_prev (struct et_occ *occ, struct et_occ *t)
{
#ifdef DEBUG_ET
  gcc_assert (occ != t);
#endif
 
  occ->prev = t;
  if (t)
    t->parent = occ;
}
 
/* Sets next field of OCC to P.  */
 
static inline void
set_next (struct et_occ *occ, struct et_occ *t)
{
#ifdef DEBUG_ET
  gcc_assert (occ != t);
#endif
 
  occ->next = t;
  if (t)
    t->parent = occ;
}
 
/* Recompute minimum for occurrence OCC.  */
 
static inline void
et_recomp_min (struct et_occ *occ)
{
  struct et_occ *mson = occ->prev;
 
  if (!mson
      || (occ->next
          && mson->min > occ->next->min))
      mson = occ->next;
 
  if (mson && mson->min < 0)
    {
      occ->min = mson->min + occ->depth;
      occ->min_occ = mson->min_occ;
    }
  else
    {
      occ->min = occ->depth;
      occ->min_occ = occ;
    }
}
 
#ifdef DEBUG_ET
/* Checks whether neighborhood of OCC seems sane.  */
 
static void
et_check_occ_sanity (struct et_occ *occ)
{
  if (!occ)
    return;
 
  gcc_assert (occ->parent != occ);
  gcc_assert (occ->prev != occ);
  gcc_assert (occ->next != occ);
  gcc_assert (!occ->next || occ->next != occ->prev);
 
  if (occ->next)
    {
      gcc_assert (occ->next != occ->parent);
      gcc_assert (occ->next->parent == occ);
    }
 
  if (occ->prev)
    {
      gcc_assert (occ->prev != occ->parent);
      gcc_assert (occ->prev->parent == occ);
    }
 
  gcc_assert (!occ->parent
              || occ->parent->prev == occ
              || occ->parent->next == occ);
}
 
/* Checks whether tree rooted at OCC is sane.  */
 
static void
et_check_sanity (struct et_occ *occ)
{
  et_check_occ_sanity (occ);
  if (occ->prev)
    et_check_sanity (occ->prev);
  if (occ->next)
    et_check_sanity (occ->next);
}
 
/* Checks whether tree containing OCC is sane.  */
 
static void
et_check_tree_sanity (struct et_occ *occ)
{
  while (occ->parent)
    occ = occ->parent;
 
  et_check_sanity (occ);
}
 
/* For recording the paths.  */
 
/* An ad-hoc constant; if the function has more blocks, this won't work,
   but since it is used for debugging only, it does not matter.  */
#define MAX_NODES 100000
 
static int len;
static void *datas[MAX_NODES];
static int depths[MAX_NODES];
 
/* Records the path represented by OCC, with depth incremented by DEPTH.  */
 
static int
record_path_before_1 (struct et_occ *occ, int depth)
{
  int mn, m;
 
  depth += occ->depth;
  mn = depth;
 
  if (occ->prev)
    {
      m = record_path_before_1 (occ->prev, depth);
      if (m < mn)
        mn = m;
    }
 
  fprintf (stderr, "%d (%d); ", ((basic_block) occ->of->data)->index, depth);
 
  gcc_assert (len < MAX_NODES);
 
  depths[len] = depth;
  datas[len] = occ->of;
  len++;
 
  if (occ->next)
    {
      m = record_path_before_1 (occ->next, depth);
      if (m < mn)
        mn = m;
    }
 
  gcc_assert (mn == occ->min + depth - occ->depth);
 
  return mn;
}
 
/* Records the path represented by a tree containing OCC.  */
 
static void
record_path_before (struct et_occ *occ)
{
  while (occ->parent)
    occ = occ->parent;
 
  len = 0;
  record_path_before_1 (occ, 0);
  fprintf (stderr, "\n");
}
 
/* Checks whether the path represented by OCC, with depth incremented by DEPTH,
   was not changed since the last recording.  */
 
static int
check_path_after_1 (struct et_occ *occ, int depth)
{
  int mn, m;
 
  depth += occ->depth;
  mn = depth;
 
  if (occ->next)
    {
      m = check_path_after_1 (occ->next, depth);
      if (m < mn)
        mn =  m;
    }
 
  len--;
  gcc_assert (depths[len] == depth && datas[len] == occ->of);
 
  if (occ->prev)
    {
      m = check_path_after_1 (occ->prev, depth);
      if (m < mn)
        mn =  m;
    }
 
  gcc_assert (mn == occ->min + depth - occ->depth);
 
  return mn;
}
 
/* Checks whether the path represented by a tree containing OCC was
   not changed since the last recording.  */
 
static void
check_path_after (struct et_occ *occ)
{
  while (occ->parent)
    occ = occ->parent;
 
  check_path_after_1 (occ, 0);
  gcc_assert (!len);
}
 
#endif
 
/* Splay the occurrence OCC to the root of the tree.  */
 
static void
et_splay (struct et_occ *occ)
{
  struct et_occ *f, *gf, *ggf;
  int occ_depth, f_depth, gf_depth;
 
#ifdef DEBUG_ET
  record_path_before (occ);
  et_check_tree_sanity (occ);
#endif
 
  while (occ->parent)
    {
      occ_depth = occ->depth;
 
      f = occ->parent;
      f_depth = f->depth;
 
      gf = f->parent;
 
      if (!gf)
        {
          set_depth_add (occ, f_depth);
          occ->min_occ = f->min_occ;
          occ->min = f->min;
 
          if (f->prev == occ)
            {
              /* zig */
              set_prev (f, occ->next);
              set_next (occ, f);
              set_depth_add (f->prev, occ_depth);
            }
          else
            {
              /* zag */
              set_next (f, occ->prev);
              set_prev (occ, f);
              set_depth_add (f->next, occ_depth);
            }
          set_depth (f, -occ_depth);
          occ->parent = NULL;
 
          et_recomp_min (f);
#ifdef DEBUG_ET
          et_check_tree_sanity (occ);
          check_path_after (occ);
#endif
          return;
        }
 
      gf_depth = gf->depth;
 
      set_depth_add (occ, f_depth + gf_depth);
      occ->min_occ = gf->min_occ;
      occ->min = gf->min;
 
      ggf = gf->parent;
 
      if (gf->prev == f)
        {
          if (f->prev == occ)
            {
              /* zig zig */
              set_prev (gf, f->next);
              set_prev (f, occ->next);
              set_next (occ, f);
              set_next (f, gf);
 
              set_depth (f, -occ_depth);
              set_depth_add (f->prev, occ_depth);
              set_depth (gf, -f_depth);
              set_depth_add (gf->prev, f_depth);
            }
          else
            {
              /* zag zig */
              set_prev (gf, occ->next);
              set_next (f, occ->prev);
              set_prev (occ, f);
              set_next (occ, gf);
 
              set_depth (f, -occ_depth);
              set_depth_add (f->next, occ_depth);
              set_depth (gf, -occ_depth - f_depth);
              set_depth_add (gf->prev, occ_depth + f_depth);
            }
        }
      else
        {
          if (f->prev == occ)
            {
              /* zig zag */
              set_next (gf, occ->prev);
              set_prev (f, occ->next);
              set_prev (occ, gf);
              set_next (occ, f);
 
              set_depth (f, -occ_depth);
              set_depth_add (f->prev, occ_depth);
              set_depth (gf, -occ_depth - f_depth);
              set_depth_add (gf->next, occ_depth + f_depth);
            }
          else
            {
              /* zag zag */
              set_next (gf, f->prev);
              set_next (f, occ->prev);
              set_prev (occ, f);
              set_prev (f, gf);
 
              set_depth (f, -occ_depth);
              set_depth_add (f->next, occ_depth);
              set_depth (gf, -f_depth);
              set_depth_add (gf->next, f_depth);
            }
        }
 
      occ->parent = ggf;
      if (ggf)
        {
          if (ggf->prev == gf)
            ggf->prev = occ;
          else
            ggf->next = occ;
        }
 
      et_recomp_min (gf);
      et_recomp_min (f);
#ifdef DEBUG_ET
      et_check_tree_sanity (occ);
#endif
    }
 
#ifdef DEBUG_ET
  et_check_sanity (occ);
  check_path_after (occ);
#endif
}
 
/* Create a new et tree occurrence of NODE.  */
 
static struct et_occ *
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);
  nw = pool_alloc (et_occurrences);
 
  nw->of = node;
  nw->parent = NULL;
  nw->prev = NULL;
  nw->next = NULL;
 
  nw->depth = 0;
  nw->min_occ = nw;
  nw->min = 0;
 
  return nw;
}
 
/* Create a new et tree containing DATA.  */
 
struct et_node *
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);
  nw = pool_alloc (et_nodes);
 
  nw->data = data;
  nw->father = NULL;
  nw->left = NULL;
  nw->right = NULL;
  nw->son = NULL;
 
  nw->rightmost_occ = et_new_occ (nw);
  nw->parent_occ = NULL;
 
  return nw;
}
 
/* Releases et tree T.  */
 
void
et_free_tree (struct et_node *t)
{
  while (t->son)
    et_split (t->son);
 
  if (t->father)
    et_split (t);
 
  pool_free (et_occurrences, t->rightmost_occ);
  pool_free (et_nodes, t);
}
 
/* Releases et tree T without maintaining other nodes.  */
 
void
et_free_tree_force (struct et_node *t)
{
  pool_free (et_occurrences, t->rightmost_occ);
  pool_free (et_nodes, t);
}
 
/* Sets father of et tree T to FATHER.  */
 
void
et_set_father (struct et_node *t, struct et_node *father)
{
  struct et_node *left, *right;
  struct et_occ *rmost, *left_part, *new_f_occ, *p;
 
  /* Update the path represented in the splay tree.  */
  new_f_occ = et_new_occ (father);
 
  rmost = father->rightmost_occ;
  et_splay (rmost);
 
  left_part = rmost->prev;
 
  p = t->rightmost_occ;
  et_splay (p);
 
  set_prev (new_f_occ, left_part);
  set_next (new_f_occ, p);
 
  p->depth++;
  p->min++;
  et_recomp_min (new_f_occ);
 
  set_prev (rmost, new_f_occ);
 
  if (new_f_occ->min + rmost->depth < rmost->min)
    {
      rmost->min = new_f_occ->min + rmost->depth;
      rmost->min_occ = new_f_occ->min_occ;
    }
 
  t->parent_occ = new_f_occ;
 
  /* Update the tree.  */
  t->father = father;
  right = father->son;
  if (right)
    left = right->left;
  else
    left = right = t;
 
  left->right = t;
  right->left = t;
  t->left = left;
  t->right = right;
 
  father->son = t;
 
#ifdef DEBUG_ET
  et_check_tree_sanity (rmost);
  record_path_before (rmost);
#endif
}
 
/* Splits the edge from T to its father.  */
 
void
et_split (struct et_node *t)
{
  struct et_node *father = t->father;
  struct et_occ *r, *l, *rmost, *p_occ;
 
  /* Update the path represented by the splay tree.  */
  rmost = t->rightmost_occ;
  et_splay (rmost);
 
  for (r = rmost->next; r->prev; r = r->prev)
    continue;
  et_splay (r);
 
  r->prev->parent = NULL;
  p_occ = t->parent_occ;
  et_splay (p_occ);
  t->parent_occ = NULL;
 
  l = p_occ->prev;
  p_occ->next->parent = NULL;
 
  set_prev (r, l);
 
  et_recomp_min (r);
 
  et_splay (rmost);
  rmost->depth = 0;
  rmost->min = 0;
 
  pool_free (et_occurrences, p_occ);
 
  /* Update the tree.  */
  if (father->son == t)
    father->son = t->right;
  if (father->son == t)
    father->son = NULL;
  else
    {
      t->left->right = t->right;
      t->right->left = t->left;
    }
  t->left = t->right = NULL;
  t->father = NULL;
 
#ifdef DEBUG_ET
  et_check_tree_sanity (rmost);
  record_path_before (rmost);
 
  et_check_tree_sanity (r);
  record_path_before (r);
#endif
}
 
/* Finds the nearest common ancestor of the nodes N1 and N2.  */
 
struct et_node *
et_nca (struct et_node *n1, struct et_node *n2)
{
  struct et_occ *o1 = n1->rightmost_occ, *o2 = n2->rightmost_occ, *om;
  struct et_occ *l, *r, *ret;
  int mn;
 
  if (n1 == n2)
    return n1;
 
  et_splay (o1);
  l = o1->prev;
  r = o1->next;
  if (l)
    l->parent = NULL;
  if (r)
    r->parent = NULL;
  et_splay (o2);
 
  if (l == o2 || (l && l->parent != NULL))
    {
      ret = o2->next;
 
      set_prev (o1, o2);
      if (r)
        r->parent = o1;
    }
  else
    {
      ret = o2->prev;
 
      set_next (o1, o2);
      if (l)
        l->parent = o1;
    }
 
  if (0 < o2->depth)
    {
      om = o1;
      mn = o1->depth;
    }
  else
    {
      om = o2;
      mn = o2->depth + o1->depth;
    }
 
#ifdef DEBUG_ET
  et_check_tree_sanity (o2);
#endif
 
  if (ret && ret->min + o1->depth + o2->depth < mn)
    return ret->min_occ->of;
  else
    return om->of;
}
 
/* Checks whether the node UP is an ancestor of the node DOWN.  */
 
bool
et_below (struct et_node *down, struct et_node *up)
{
  struct et_occ *u = up->rightmost_occ, *d = down->rightmost_occ;
  struct et_occ *l, *r;
 
  if (up == down)
    return true;
 
  et_splay (u);
  l = u->prev;
  r = u->next;
 
  if (!l)
    return false;
 
  l->parent = NULL;
 
  if (r)
    r->parent = NULL;
 
  et_splay (d);
 
  if (l == d || l->parent != NULL)
    {
      if (r)
        r->parent = u;
      set_prev (u, d);
#ifdef DEBUG_ET
      et_check_tree_sanity (u);
#endif
    }
  else
    {
      l->parent = u;
 
      /* In case O1 and O2 are in two different trees, we must just restore the
         original state.  */
      if (r && r->parent != NULL)
        set_next (u, d);
      else
        set_next (u, r);
 
#ifdef DEBUG_ET
      et_check_tree_sanity (u);
#endif
      return false;
    }
 
  if (0 >= d->depth)
    return false;
 
  return !d->next || d->next->min + d->depth >= 0;
}

Browse

Tools

Subversion Repositories scarts

[/] [scarts/] [trunk/] [toolchain/] [scarts-gcc/] [gcc-4.1.1/] [gcc/] [et-forest.c] - Blame information for rev 16

Line No.	Rev	Author	Line
1	12	jlechner	`/* ET-trees data structure implementation.`
2			`Contributed by Pavel Nejedly`
3			`Copyright (C) 2002, 2003, 2004, 2005 Free Software Foundation, Inc.`
4
5			`This file is part of the libiberty library.`
6			`Libiberty is free software; you can redistribute it and/or`
7			`modify it under the terms of the GNU Library General Public`
8			`License as published by the Free Software Foundation; either`
9			`version 2 of the License, or (at your option) any later version.`
10
11			`Libiberty is distributed in the hope that it will be useful,`
12			`but WITHOUT ANY WARRANTY; without even the implied warranty of`
13			`MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU`
14			`Library General Public License for more details.`
15
16			`You should have received a copy of the GNU Library General Public`
17			`License along with libiberty; see the file COPYING.LIB. If`
18			`not, write to the Free Software Foundation, Inc., 51 Franklin Street, Fifth Floor,`
19			`Boston, MA 02110-1301, USA.`
20
21			`The ET-forest structure is described in:`
22			`D. D. Sleator and R. E. Tarjan. A data structure for dynamic trees.`
23			`J. G'omput. System Sci., 26(3):362 381, 1983.`
24			`*/`
25
26			`#include "config.h"`
27			`#include "system.h"`
28			`#include "coretypes.h"`
29			`#include "tm.h"`
30			`#include "et-forest.h"`
31			`#include "alloc-pool.h"`
32
33			`/* We do not enable this with ENABLE_CHECKING, since it is awfully slow. */`
34			`#undef DEBUG_ET`
35
36			`#ifdef DEBUG_ET`
37			`#include "basic-block.h"`
38			`#endif`
39
40			`/* The occurrence of a node in the et tree. */`
41			`struct et_occ`
42			`{`
43			`struct et_node of; / The node. */`
44
45			`struct et_occ parent; / Parent in the splay-tree. */`
46			`struct et_occ prev; / Left son in the splay-tree. */`
47			`struct et_occ next; / Right son in the splay-tree. */`
48
49			`int depth; /* The depth of the node is the sum of depth`
50			`fields on the path to the root. */`
51			`int min; /* The minimum value of the depth in the subtree`
52			`is obtained by adding sum of depth fields`
53			`on the path to the root. */`
54			`struct et_occ min_occ; / The occurrence in the subtree with the minimal`
55			`depth. */`
56			`};`
57
58			`static alloc_pool et_nodes;`
59			`static alloc_pool et_occurrences;`
60
61			`/* Changes depth of OCC to D. */`
62
63			`static inline void`
64			`set_depth (struct et_occ *occ, int d)`
65			`{`
66			`if (!occ)`
67			`return;`
68
69			`occ->min += d - occ->depth;`
70			`occ->depth = d;`
71			`}`
72
73			`/* Adds D to the depth of OCC. */`
74
75			`static inline void`
76			`set_depth_add (struct et_occ *occ, int d)`
77			`{`
78			`if (!occ)`
79			`return;`
80
81			`occ->min += d;`
82			`occ->depth += d;`
83			`}`
84
85			`/* Sets prev field of OCC to P. */`
86
87			`static inline void`
88			`set_prev (struct et_occ occ, struct et_occ t)`
89			`{`
90			`#ifdef DEBUG_ET`
91			`gcc_assert (occ != t);`
92			`#endif`
93
94			`occ->prev = t;`
95			`if (t)`
96			`t->parent = occ;`
97			`}`
98
99			`/* Sets next field of OCC to P. */`
100
101			`static inline void`
102			`set_next (struct et_occ occ, struct et_occ t)`
103			`{`
104			`#ifdef DEBUG_ET`
105			`gcc_assert (occ != t);`
106			`#endif`
107
108			`occ->next = t;`
109			`if (t)`
110			`t->parent = occ;`
111			`}`
112
113			`/* Recompute minimum for occurrence OCC. */`
114
115			`static inline void`
116			`et_recomp_min (struct et_occ *occ)`
117			`{`
118			`struct et_occ *mson = occ->prev;`
119
120			`if (!mson`
121			`\|\| (occ->next`
122			`&& mson->min > occ->next->min))`
123			`mson = occ->next;`
124
125			`if (mson && mson->min < 0)`
126			`{`
127			`occ->min = mson->min + occ->depth;`
128			`occ->min_occ = mson->min_occ;`
129			`}`
130			`else`
131			`{`
132			`occ->min = occ->depth;`
133			`occ->min_occ = occ;`
134			`}`
135			`}`
136
137			`#ifdef DEBUG_ET`
138			`/* Checks whether neighborhood of OCC seems sane. */`
139
140			`static void`
141			`et_check_occ_sanity (struct et_occ *occ)`
142			`{`
143			`if (!occ)`
144			`return;`
145
146			`gcc_assert (occ->parent != occ);`
147			`gcc_assert (occ->prev != occ);`
148			`gcc_assert (occ->next != occ);`
149			`gcc_assert (!occ->next \|\| occ->next != occ->prev);`
150
151			`if (occ->next)`
152			`{`
153			`gcc_assert (occ->next != occ->parent);`
154			`gcc_assert (occ->next->parent == occ);`
155			`}`
156
157			`if (occ->prev)`
158			`{`
159			`gcc_assert (occ->prev != occ->parent);`
160			`gcc_assert (occ->prev->parent == occ);`
161			`}`
162
163			`gcc_assert (!occ->parent`
164			`\|\| occ->parent->prev == occ`
165			`\|\| occ->parent->next == occ);`
166			`}`
167
168			`/* Checks whether tree rooted at OCC is sane. */`
169
170			`static void`
171			`et_check_sanity (struct et_occ *occ)`
172			`{`
173			`et_check_occ_sanity (occ);`
174			`if (occ->prev)`
175			`et_check_sanity (occ->prev);`
176			`if (occ->next)`
177			`et_check_sanity (occ->next);`
178			`}`
179
180			`/* Checks whether tree containing OCC is sane. */`
181
182			`static void`
183			`et_check_tree_sanity (struct et_occ *occ)`
184			`{`
185			`while (occ->parent)`
186			`occ = occ->parent;`
187
188			`et_check_sanity (occ);`
189			`}`
190
191			`/* For recording the paths. */`
192
193			`/* An ad-hoc constant; if the function has more blocks, this won't work,`
194			`but since it is used for debugging only, it does not matter. */`
195			`#define MAX_NODES 100000`
196
197			`static int len;`
198			`static void *datas[MAX_NODES];`
199			`static int depths[MAX_NODES];`
200
201			`/* Records the path represented by OCC, with depth incremented by DEPTH. */`
202
203			`static int`
204			`record_path_before_1 (struct et_occ *occ, int depth)`
205			`{`
206			`int mn, m;`
207
208			`depth += occ->depth;`
209			`mn = depth;`
210
211			`if (occ->prev)`
212			`{`
213			`m = record_path_before_1 (occ->prev, depth);`
214			`if (m < mn)`
215			`mn = m;`
216			`}`
217
218			`fprintf (stderr, "%d (%d); ", ((basic_block) occ->of->data)->index, depth);`
219
220			`gcc_assert (len < MAX_NODES);`
221
222			`depths[len] = depth;`
223			`datas[len] = occ->of;`
224			`len++;`
225
226			`if (occ->next)`
227			`{`
228			`m = record_path_before_1 (occ->next, depth);`
229			`if (m < mn)`
230			`mn = m;`
231			`}`
232
233			`gcc_assert (mn == occ->min + depth - occ->depth);`
234
235			`return mn;`
236			`}`
237
238			`/* Records the path represented by a tree containing OCC. */`
239
240			`static void`
241			`record_path_before (struct et_occ *occ)`
242			`{`
243			`while (occ->parent)`
244			`occ = occ->parent;`
245
246			`len = 0;`
247			`record_path_before_1 (occ, 0);`
248			`fprintf (stderr, "\n");`
249			`}`
250
251			`/* Checks whether the path represented by OCC, with depth incremented by DEPTH,`
252			`was not changed since the last recording. */`
253
254			`static int`
255			`check_path_after_1 (struct et_occ *occ, int depth)`
256			`{`
257			`int mn, m;`
258
259			`depth += occ->depth;`
260			`mn = depth;`
261
262			`if (occ->next)`
263			`{`
264			`m = check_path_after_1 (occ->next, depth);`
265			`if (m < mn)`
266			`mn = m;`
267			`}`
268
269			`len--;`
270			`gcc_assert (depths[len] == depth && datas[len] == occ->of);`
271
272			`if (occ->prev)`
273			`{`
274			`m = check_path_after_1 (occ->prev, depth);`
275			`if (m < mn)`
276			`mn = m;`
277			`}`
278
279			`gcc_assert (mn == occ->min + depth - occ->depth);`
280
281			`return mn;`
282			`}`
283
284			`/* Checks whether the path represented by a tree containing OCC was`
285			`not changed since the last recording. */`
286
287			`static void`
288			`check_path_after (struct et_occ *occ)`
289			`{`
290			`while (occ->parent)`
291			`occ = occ->parent;`
292
293			`check_path_after_1 (occ, 0);`
294			`gcc_assert (!len);`
295			`}`
296
297			`#endif`
298
299			`/* Splay the occurrence OCC to the root of the tree. */`
300
301			`static void`
302			`et_splay (struct et_occ *occ)`
303			`{`
304			`struct et_occ f, gf, *ggf;`
305			`int occ_depth, f_depth, gf_depth;`
306
307			`#ifdef DEBUG_ET`
308			`record_path_before (occ);`
309			`et_check_tree_sanity (occ);`
310			`#endif`
311
312			`while (occ->parent)`
313			`{`
314			`occ_depth = occ->depth;`
315
316			`f = occ->parent;`
317			`f_depth = f->depth;`
318
319			`gf = f->parent;`
320
321			`if (!gf)`
322			`{`
323			`set_depth_add (occ, f_depth);`
324			`occ->min_occ = f->min_occ;`
325			`occ->min = f->min;`
326
327			`if (f->prev == occ)`
328			`{`
329			`/* zig */`
330			`set_prev (f, occ->next);`
331			`set_next (occ, f);`
332			`set_depth_add (f->prev, occ_depth);`
333			`}`
334			`else`
335			`{`
336			`/* zag */`
337			`set_next (f, occ->prev);`
338			`set_prev (occ, f);`
339			`set_depth_add (f->next, occ_depth);`
340			`}`
341			`set_depth (f, -occ_depth);`
342			`occ->parent = NULL;`
343
344			`et_recomp_min (f);`
345			`#ifdef DEBUG_ET`
346			`et_check_tree_sanity (occ);`
347			`check_path_after (occ);`
348			`#endif`
349			`return;`
350			`}`
351
352			`gf_depth = gf->depth;`
353
354			`set_depth_add (occ, f_depth + gf_depth);`
355			`occ->min_occ = gf->min_occ;`
356			`occ->min = gf->min;`
357
358			`ggf = gf->parent;`
359
360			`if (gf->prev == f)`
361			`{`
362			`if (f->prev == occ)`
363			`{`
364			`/* zig zig */`
365			`set_prev (gf, f->next);`
366			`set_prev (f, occ->next);`
367			`set_next (occ, f);`
368			`set_next (f, gf);`
369
370			`set_depth (f, -occ_depth);`
371			`set_depth_add (f->prev, occ_depth);`
372			`set_depth (gf, -f_depth);`
373			`set_depth_add (gf->prev, f_depth);`
374			`}`
375			`else`
376			`{`
377			`/* zag zig */`
378			`set_prev (gf, occ->next);`
379			`set_next (f, occ->prev);`
380			`set_prev (occ, f);`
381			`set_next (occ, gf);`
382
383			`set_depth (f, -occ_depth);`
384			`set_depth_add (f->next, occ_depth);`
385			`set_depth (gf, -occ_depth - f_depth);`
386			`set_depth_add (gf->prev, occ_depth + f_depth);`
387			`}`
388			`}`
389			`else`
390			`{`
391			`if (f->prev == occ)`
392			`{`
393			`/* zig zag */`
394			`set_next (gf, occ->prev);`
395			`set_prev (f, occ->next);`
396			`set_prev (occ, gf);`
397			`set_next (occ, f);`
398
399			`set_depth (f, -occ_depth);`
400			`set_depth_add (f->prev, occ_depth);`
401			`set_depth (gf, -occ_depth - f_depth);`
402			`set_depth_add (gf->next, occ_depth + f_depth);`
403			`}`
404			`else`
405			`{`
406			`/* zag zag */`
407			`set_next (gf, f->prev);`
408			`set_next (f, occ->prev);`
409			`set_prev (occ, f);`
410			`set_prev (f, gf);`
411
412			`set_depth (f, -occ_depth);`
413			`set_depth_add (f->next, occ_depth);`
414			`set_depth (gf, -f_depth);`
415			`set_depth_add (gf->next, f_depth);`
416			`}`
417			`}`
418
419			`occ->parent = ggf;`
420			`if (ggf)`
421			`{`
422			`if (ggf->prev == gf)`
423			`ggf->prev = occ;`
424			`else`
425			`ggf->next = occ;`
426			`}`
427
428			`et_recomp_min (gf);`
429			`et_recomp_min (f);`
430			`#ifdef DEBUG_ET`
431			`et_check_tree_sanity (occ);`
432			`#endif`
433			`}`
434
435			`#ifdef DEBUG_ET`
436			`et_check_sanity (occ);`
437			`check_path_after (occ);`
438			`#endif`
439			`}`
440
441			`/* Create a new et tree occurrence of NODE. */`
442
443			`static struct et_occ *`
444			`et_new_occ (struct et_node *node)`
445			`{`
446			`struct et_occ *nw;`
447
448			`if (!et_occurrences)`
449			`et_occurrences = create_alloc_pool ("et_occ pool", sizeof (struct et_occ), 300);`
450			`nw = pool_alloc (et_occurrences);`
451
452			`nw->of = node;`
453			`nw->parent = NULL;`
454			`nw->prev = NULL;`
455			`nw->next = NULL;`
456
457			`nw->depth = 0;`
458			`nw->min_occ = nw;`
459			`nw->min = 0;`
460
461			`return nw;`
462			`}`
463
464			`/* Create a new et tree containing DATA. */`
465
466			`struct et_node *`
467			`et_new_tree (void *data)`
468			`{`
469			`struct et_node *nw;`
470
471			`if (!et_nodes)`
472			`et_nodes = create_alloc_pool ("et_node pool", sizeof (struct et_node), 300);`
473			`nw = pool_alloc (et_nodes);`
474
475			`nw->data = data;`
476			`nw->father = NULL;`
477			`nw->left = NULL;`
478			`nw->right = NULL;`
479			`nw->son = NULL;`
480
481			`nw->rightmost_occ = et_new_occ (nw);`
482			`nw->parent_occ = NULL;`
483
484			`return nw;`
485			`}`
486
487			`/* Releases et tree T. */`
488
489			`void`
490			`et_free_tree (struct et_node *t)`
491			`{`
492			`while (t->son)`
493			`et_split (t->son);`
494
495			`if (t->father)`
496			`et_split (t);`
497
498			`pool_free (et_occurrences, t->rightmost_occ);`
499			`pool_free (et_nodes, t);`
500			`}`
501
502			`/* Releases et tree T without maintaining other nodes. */`
503
504			`void`
505			`et_free_tree_force (struct et_node *t)`
506			`{`
507			`pool_free (et_occurrences, t->rightmost_occ);`
508			`pool_free (et_nodes, t);`
509			`}`
510
511			`/* Sets father of et tree T to FATHER. */`
512
513			`void`
514			`et_set_father (struct et_node t, struct et_node father)`
515			`{`
516			`struct et_node left, right;`
517			`struct et_occ rmost, left_part, new_f_occ, p;`
518
519			`/* Update the path represented in the splay tree. */`
520			`new_f_occ = et_new_occ (father);`
521
522			`rmost = father->rightmost_occ;`
523			`et_splay (rmost);`
524
525			`left_part = rmost->prev;`
526
527			`p = t->rightmost_occ;`
528			`et_splay (p);`
529
530			`set_prev (new_f_occ, left_part);`
531			`set_next (new_f_occ, p);`
532
533			`p->depth++;`
534			`p->min++;`
535			`et_recomp_min (new_f_occ);`
536
537			`set_prev (rmost, new_f_occ);`
538
539			`if (new_f_occ->min + rmost->depth < rmost->min)`
540			`{`
541			`rmost->min = new_f_occ->min + rmost->depth;`
542			`rmost->min_occ = new_f_occ->min_occ;`
543			`}`
544
545			`t->parent_occ = new_f_occ;`
546
547			`/* Update the tree. */`
548			`t->father = father;`
549			`right = father->son;`
550			`if (right)`
551			`left = right->left;`
552			`else`
553			`left = right = t;`
554
555			`left->right = t;`
556			`right->left = t;`
557			`t->left = left;`
558			`t->right = right;`
559
560			`father->son = t;`
561
562			`#ifdef DEBUG_ET`
563			`et_check_tree_sanity (rmost);`
564			`record_path_before (rmost);`
565			`#endif`
566			`}`
567
568			`/* Splits the edge from T to its father. */`
569
570			`void`
571			`et_split (struct et_node *t)`
572			`{`
573			`struct et_node *father = t->father;`
574			`struct et_occ r, l, rmost, p_occ;`
575
576			`/* Update the path represented by the splay tree. */`
577			`rmost = t->rightmost_occ;`
578			`et_splay (rmost);`
579
580			`for (r = rmost->next; r->prev; r = r->prev)`
581			`continue;`
582			`et_splay (r);`
583
584			`r->prev->parent = NULL;`
585			`p_occ = t->parent_occ;`
586			`et_splay (p_occ);`
587			`t->parent_occ = NULL;`
588
589			`l = p_occ->prev;`
590			`p_occ->next->parent = NULL;`
591
592			`set_prev (r, l);`
593
594			`et_recomp_min (r);`
595
596			`et_splay (rmost);`
597			`rmost->depth = 0;`
598			`rmost->min = 0;`
599
600			`pool_free (et_occurrences, p_occ);`
601
602			`/* Update the tree. */`
603			`if (father->son == t)`
604			`father->son = t->right;`
605			`if (father->son == t)`
606			`father->son = NULL;`
607			`else`
608			`{`
609			`t->left->right = t->right;`
610			`t->right->left = t->left;`
611			`}`
612			`t->left = t->right = NULL;`
613			`t->father = NULL;`
614
615			`#ifdef DEBUG_ET`
616			`et_check_tree_sanity (rmost);`
617			`record_path_before (rmost);`
618
619			`et_check_tree_sanity (r);`
620			`record_path_before (r);`
621			`#endif`
622			`}`
623
624			`/* Finds the nearest common ancestor of the nodes N1 and N2. */`
625
626			`struct et_node *`
627			`et_nca (struct et_node n1, struct et_node n2)`
628			`{`
629			`struct et_occ o1 = n1->rightmost_occ, o2 = n2->rightmost_occ, *om;`
630			`struct et_occ l, r, *ret;`
631			`int mn;`
632
633			`if (n1 == n2)`
634			`return n1;`
635
636			`et_splay (o1);`
637			`l = o1->prev;`
638			`r = o1->next;`
639			`if (l)`
640			`l->parent = NULL;`
641			`if (r)`
642			`r->parent = NULL;`
643			`et_splay (o2);`
644
645			`if (l == o2 \|\| (l && l->parent != NULL))`
646			`{`
647			`ret = o2->next;`
648
649			`set_prev (o1, o2);`
650			`if (r)`
651			`r->parent = o1;`
652			`}`
653			`else`
654			`{`
655			`ret = o2->prev;`
656
657			`set_next (o1, o2);`
658			`if (l)`
659			`l->parent = o1;`
660			`}`
661
662			`if (0 < o2->depth)`
663			`{`
664			`om = o1;`
665			`mn = o1->depth;`
666			`}`
667			`else`
668			`{`
669			`om = o2;`
670			`mn = o2->depth + o1->depth;`
671			`}`
672
673			`#ifdef DEBUG_ET`
674			`et_check_tree_sanity (o2);`
675			`#endif`
676
677			`if (ret && ret->min + o1->depth + o2->depth < mn)`
678			`return ret->min_occ->of;`
679			`else`
680			`return om->of;`
681			`}`
682
683			`/* Checks whether the node UP is an ancestor of the node DOWN. */`
684
685			`bool`
686			`et_below (struct et_node down, struct et_node up)`
687			`{`
688			`struct et_occ u = up->rightmost_occ, d = down->rightmost_occ;`
689			`struct et_occ l, r;`
690
691			`if (up == down)`
692			`return true;`
693
694			`et_splay (u);`
695			`l = u->prev;`
696			`r = u->next;`
697
698			`if (!l)`
699			`return false;`
700
701			`l->parent = NULL;`
702
703			`if (r)`
704			`r->parent = NULL;`
705
706			`et_splay (d);`
707
708			`if (l == d \|\| l->parent != NULL)`
709			`{`
710			`if (r)`
711			`r->parent = u;`
712			`set_prev (u, d);`
713			`#ifdef DEBUG_ET`
714			`et_check_tree_sanity (u);`
715			`#endif`
716			`}`
717			`else`
718			`{`
719			`l->parent = u;`
720
721			`/* In case O1 and O2 are in two different trees, we must just restore the`
722			`original state. */`
723			`if (r && r->parent != NULL)`
724			`set_next (u, d);`
725			`else`
726			`set_next (u, r);`
727
728			`#ifdef DEBUG_ET`
729			`et_check_tree_sanity (u);`
730			`#endif`
731			`return false;`
732			`}`
733
734			`if (0 >= d->depth)`
735			`return false;`
736
737			`return !d->next \|\| d->next->min + d->depth >= 0;`
738			`}`