LCOV - code coverage report
Current view: top level - gcc - et-forest.c (source / functions) Hit Total Coverage
Test: gcc.info Lines: 322 330 97.6 %
Date: 2020-04-04 11:58:09 Functions: 15 16 93.8 %
Legend: Lines: hit not hit | Branches: + taken - not taken # not executed Branches: 0 0 -

           Branch data     Line data    Source code
       1                 :            : /* ET-trees data structure implementation.
       2                 :            :    Contributed by Pavel Nejedly
       3                 :            :    Copyright (C) 2002-2020 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 3 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 COPYING3.  If not see
      18                 :            : <http://www.gnu.org/licenses/>.
      19                 :            : 
      20                 :            :   The ET-forest structure is described in:
      21                 :            :     D. D. Sleator and R. E. Tarjan. A data structure for dynamic trees.
      22                 :            :     J.  G'omput. System Sci., 26(3):362 381, 1983.
      23                 :            : */
      24                 :            : 
      25                 :            : #include "config.h"
      26                 :            : #include "system.h"
      27                 :            : #include "coretypes.h"
      28                 :            : #include "alloc-pool.h"
      29                 :            : #include "et-forest.h"
      30                 :            : #include "selftest.h"
      31                 :            : 
      32                 :            : /* We do not enable this with CHECKING_P, since it is awfully slow.  */
      33                 :            : #undef DEBUG_ET
      34                 :            : 
      35                 :            : #ifdef DEBUG_ET
      36                 :            : #include "backend.h"
      37                 :            : #include "hard-reg-set.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 object_allocator<et_node> et_nodes ("et_nodes pool");
      59                 :            : static object_allocator<et_occ> et_occurrences ("et_occ pool");
      60                 :            : 
      61                 :            : /* Changes depth of OCC to D.  */
      62                 :            : 
      63                 :            : static inline void
      64                 : 3515440000 : set_depth (struct et_occ *occ, int d)
      65                 :            : {
      66                 : 3515440000 :   if (!occ)
      67                 :            :     return;
      68                 :            : 
      69                 : 3515440000 :   occ->min += d - occ->depth;
      70                 : 3515440000 :   occ->depth = d;
      71                 :            : }
      72                 :            : 
      73                 :            : /* Adds D to the depth of OCC.  */
      74                 :            : 
      75                 :            : static inline void
      76                 : 5474800000 : set_depth_add (struct et_occ *occ, int d)
      77                 :            : {
      78                 : 5474800000 :   if (!occ)
      79                 :            :     return;
      80                 :            : 
      81                 : 3692820000 :   occ->min += d;
      82                 : 1733470000 :   occ->depth += d;
      83                 :            : }
      84                 :            : 
      85                 :            : /* Sets prev field of OCC to P.  */
      86                 :            : 
      87                 :            : static inline void
      88                 : 5450540000 : set_prev (struct et_occ *occ, struct et_occ *t)
      89                 :            : {
      90                 :            : #ifdef DEBUG_ET
      91                 :            :   gcc_assert (occ != t);
      92                 :            : #endif
      93                 :            : 
      94                 : 5450540000 :   occ->prev = t;
      95                 : 5450540000 :   if (t)
      96                 : 1955380000 :     t->parent = occ;
      97                 :            : }
      98                 :            : 
      99                 :            : /* Sets next field of OCC to P.  */
     100                 :            : 
     101                 :            : static inline void
     102                 : 4321330000 : set_next (struct et_occ *occ, struct et_occ *t)
     103                 :            : {
     104                 :            : #ifdef DEBUG_ET
     105                 :            :   gcc_assert (occ != t);
     106                 :            : #endif
     107                 :            : 
     108                 : 4321330000 :   occ->next = t;
     109                 : 4321330000 :   if (t)
     110                 : 2017930000 :     t->parent = occ;
     111                 :            : }
     112                 :            : 
     113                 :            : /* Recompute minimum for occurrence OCC.  */
     114                 :            : 
     115                 :            : static inline void
     116                 : 4590000000 : et_recomp_min (struct et_occ *occ)
     117                 :            : {
     118                 : 4590000000 :   struct et_occ *mson = occ->prev;
     119                 :            : 
     120                 : 4590000000 :   if (!mson
     121                 : 3339800000 :       || (occ->next
     122                 : 2464210000 :           && mson->min > occ->next->min))
     123                 : 1881820000 :       mson = occ->next;
     124                 :            : 
     125                 : 4590000000 :   if (mson && mson->min < 0)
     126                 :            :     {
     127                 : 3684220000 :       occ->min = mson->min + occ->depth;
     128                 : 3684220000 :       occ->min_occ = mson->min_occ;
     129                 :            :     }
     130                 :            :   else
     131                 :            :     {
     132                 :  905783000 :       occ->min = occ->depth;
     133                 :  905783000 :       occ->min_occ = occ;
     134                 :            :     }
     135                 : 4590000000 : }
     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                 : 2969550000 : et_splay (struct et_occ *occ)
     303                 :            : {
     304                 : 4525630000 :   struct et_occ *f, *gf, *ggf;
     305                 : 4525630000 :   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                 : 4525630000 :   while (occ->parent)
     313                 :            :     {
     314                 : 1959360000 :       occ_depth = occ->depth;
     315                 :            : 
     316                 : 1959360000 :       f = occ->parent;
     317                 : 1959360000 :       f_depth = f->depth;
     318                 :            : 
     319                 : 1959360000 :       gf = f->parent;
     320                 :            : 
     321                 : 1959360000 :       if (!gf)
     322                 :            :         {
     323                 :  403279000 :           set_depth_add (occ, f_depth);
     324                 :  403279000 :           occ->min_occ = f->min_occ;
     325                 :  403279000 :           occ->min = f->min;
     326                 :            : 
     327                 :  403279000 :           if (f->prev == occ)
     328                 :            :             {
     329                 :            :               /* zig */
     330                 :  169861000 :               set_prev (f, occ->next);
     331                 :  169861000 :               set_next (occ, f);
     332                 :  169861000 :               set_depth_add (f->prev, occ_depth);
     333                 :            :             }
     334                 :            :           else
     335                 :            :             {
     336                 :            :               /* zag */
     337                 :  233417000 :               set_next (f, occ->prev);
     338                 :  233417000 :               set_prev (occ, f);
     339                 :  233417000 :               set_depth_add (f->next, occ_depth);
     340                 :            :             }
     341                 :  403279000 :           set_depth (f, -occ_depth);
     342                 :  403279000 :           occ->parent = NULL;
     343                 :            : 
     344                 :  403279000 :           et_recomp_min (f);
     345                 :            : #ifdef DEBUG_ET
     346                 :            :           et_check_tree_sanity (occ);
     347                 :            :           check_path_after (occ);
     348                 :            : #endif
     349                 :  403279000 :           return;
     350                 :            :         }
     351                 :            : 
     352                 : 1556080000 :       gf_depth = gf->depth;
     353                 :            : 
     354                 : 1556080000 :       set_depth_add (occ, f_depth + gf_depth);
     355                 : 1556080000 :       occ->min_occ = gf->min_occ;
     356                 : 1556080000 :       occ->min = gf->min;
     357                 :            : 
     358                 : 1556080000 :       ggf = gf->parent;
     359                 :            : 
     360                 : 1556080000 :       if (gf->prev == f)
     361                 :            :         {
     362                 : 1010630000 :           if (f->prev == occ)
     363                 :            :             {
     364                 :            :               /* zig zig */
     365                 :  381418000 :               set_prev (gf, f->next);
     366                 :  381418000 :               set_prev (f, occ->next);
     367                 :  381418000 :               set_next (occ, f);
     368                 :  381418000 :               set_next (f, gf);
     369                 :            : 
     370                 :  381418000 :               set_depth (f, -occ_depth);
     371                 :  381418000 :               set_depth_add (f->prev, occ_depth);
     372                 :  381418000 :               set_depth (gf, -f_depth);
     373                 :  381418000 :               set_depth_add (gf->prev, f_depth);
     374                 :            :             }
     375                 :            :           else
     376                 :            :             {
     377                 :            :               /* zag zig */
     378                 :  629210000 :               set_prev (gf, occ->next);
     379                 :  629210000 :               set_next (f, occ->prev);
     380                 :  629210000 :               set_prev (occ, f);
     381                 :  629210000 :               set_next (occ, gf);
     382                 :            : 
     383                 :  629210000 :               set_depth (f, -occ_depth);
     384                 :  629210000 :               set_depth_add (f->next, occ_depth);
     385                 :  629210000 :               set_depth (gf, -occ_depth - f_depth);
     386                 :  629210000 :               set_depth_add (gf->prev, occ_depth + f_depth);
     387                 :            :             }
     388                 :            :         }
     389                 :            :       else
     390                 :            :         {
     391                 :  545451000 :           if (f->prev == occ)
     392                 :            :             {
     393                 :            :               /* zig zag */
     394                 :  165963000 :               set_next (gf, occ->prev);
     395                 :  165963000 :               set_prev (f, occ->next);
     396                 :  165963000 :               set_prev (occ, gf);
     397                 :  165963000 :               set_next (occ, f);
     398                 :            : 
     399                 :  165963000 :               set_depth (f, -occ_depth);
     400                 :  165963000 :               set_depth_add (f->prev, occ_depth);
     401                 :  165963000 :               set_depth (gf, -occ_depth - f_depth);
     402                 :  165963000 :               set_depth_add (gf->next, occ_depth + f_depth);
     403                 :            :             }
     404                 :            :           else
     405                 :            :             {
     406                 :            :               /* zag zag */
     407                 :  379488000 :               set_next (gf, f->prev);
     408                 :  379488000 :               set_next (f, occ->prev);
     409                 :  379488000 :               set_prev (occ, f);
     410                 :  379488000 :               set_prev (f, gf);
     411                 :            : 
     412                 :  379488000 :               set_depth (f, -occ_depth);
     413                 :  379488000 :               set_depth_add (f->next, occ_depth);
     414                 :  379488000 :               set_depth (gf, -f_depth);
     415                 :  379488000 :               set_depth_add (gf->next, f_depth);
     416                 :            :             }
     417                 :            :         }
     418                 :            : 
     419                 : 1556080000 :       occ->parent = ggf;
     420                 : 1556080000 :       if (ggf)
     421                 :            :         {
     422                 :  832048000 :           if (ggf->prev == gf)
     423                 :  446374000 :             ggf->prev = occ;
     424                 :            :           else
     425                 :  385674000 :             ggf->next = occ;
     426                 :            :         }
     427                 :            : 
     428                 : 1556080000 :       et_recomp_min (gf);
     429                 : 1556080000 :       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                 : 2303370000 : et_new_occ (struct et_node *node)
     445                 :            : {
     446                 :          0 :   et_occ *nw = et_occurrences.allocate ();
     447                 :            : 
     448                 : 2303370000 :   nw->of = node;
     449                 : 2303370000 :   nw->parent = NULL;
     450                 : 2303370000 :   nw->prev = NULL;
     451                 : 2303370000 :   nw->next = NULL;
     452                 :            : 
     453                 : 2303370000 :   nw->depth = 0;
     454                 : 2303370000 :   nw->min_occ = nw;
     455                 : 2303370000 :   nw->min = 0;
     456                 :            : 
     457                 : 2303370000 :   return nw;
     458                 :            : }
     459                 :            : 
     460                 :            : /* Create a new et tree containing DATA.  */
     461                 :            : 
     462                 :            : struct et_node *
     463                 : 1271480000 : et_new_tree (void *data)
     464                 :            : {
     465                 : 1271480000 :   et_node *nw = et_nodes.allocate ();
     466                 :            : 
     467                 : 1271480000 :   nw->data = data;
     468                 : 1271480000 :   nw->father = NULL;
     469                 : 1271480000 :   nw->left = NULL;
     470                 : 1271480000 :   nw->right = NULL;
     471                 : 1271480000 :   nw->son = NULL;
     472                 :            : 
     473                 : 1271480000 :   nw->rightmost_occ = et_new_occ (nw);
     474                 : 1271480000 :   nw->parent_occ = NULL;
     475                 :            : 
     476                 : 1271480000 :   return nw;
     477                 :            : }
     478                 :            : 
     479                 :            : /* Releases et tree T.  */
     480                 :            : 
     481                 :            : void
     482                 :   25331400 : et_free_tree (struct et_node *t)
     483                 :            : {
     484                 :   25906400 :   while (t->son)
     485                 :     574983 :     et_split (t->son);
     486                 :            : 
     487                 :   25331400 :   if (t->father)
     488                 :   24912400 :     et_split (t);
     489                 :            : 
     490                 :   25331400 :   et_occurrences.remove (t->rightmost_occ);
     491                 :   25331400 :   et_nodes.remove (t);
     492                 :   25331400 : }
     493                 :            : 
     494                 :            : /* Releases et tree T without maintaining other nodes.  */
     495                 :            : 
     496                 :            : void
     497                 : 1245820000 : et_free_tree_force (struct et_node *t)
     498                 :            : {
     499                 : 1245820000 :   et_occurrences.remove (t->rightmost_occ);
     500                 : 1245820000 :   if (t->parent_occ)
     501                 :  988988000 :     et_occurrences.remove (t->parent_occ);
     502                 : 1245820000 :   et_nodes.remove (t);
     503                 : 1245820000 : }
     504                 :            : 
     505                 :            : /* Release the alloc pools, if they are empty.  */
     506                 :            : 
     507                 :            : void
     508                 :  127902000 : et_free_pools (void)
     509                 :            : {
     510                 :  127902000 :   et_occurrences.release_if_empty ();
     511                 :  127902000 :   et_nodes.release_if_empty ();
     512                 :  127902000 : }
     513                 :            : 
     514                 :            : /* Sets father of et tree T to FATHER.  */
     515                 :            : 
     516                 :            : void
     517                 : 1031890000 : et_set_father (struct et_node *t, struct et_node *father)
     518                 :            : {
     519                 : 1031890000 :   struct et_node *left, *right;
     520                 : 1031890000 :   struct et_occ *rmost, *left_part, *new_f_occ, *p;
     521                 :            : 
     522                 :            :   /* Update the path represented in the splay tree.  */
     523                 : 1031890000 :   new_f_occ = et_new_occ (father);
     524                 :            : 
     525                 : 1031890000 :   rmost = father->rightmost_occ;
     526                 : 1031890000 :   et_splay (rmost);
     527                 :            : 
     528                 : 1031890000 :   left_part = rmost->prev;
     529                 :            : 
     530                 : 1031890000 :   p = t->rightmost_occ;
     531                 : 1031890000 :   et_splay (p);
     532                 :            : 
     533                 : 1031890000 :   set_prev (new_f_occ, left_part);
     534                 : 1031890000 :   set_next (new_f_occ, p);
     535                 :            : 
     536                 : 1031890000 :   p->depth++;
     537                 : 1031890000 :   p->min++;
     538                 : 1031890000 :   et_recomp_min (new_f_occ);
     539                 :            : 
     540                 : 1031890000 :   set_prev (rmost, new_f_occ);
     541                 :            : 
     542                 : 1031890000 :   if (new_f_occ->min + rmost->depth < rmost->min)
     543                 :            :     {
     544                 :          0 :       rmost->min = new_f_occ->min + rmost->depth;
     545                 :          0 :       rmost->min_occ = new_f_occ->min_occ;
     546                 :            :     }
     547                 :            : 
     548                 : 1031890000 :   t->parent_occ = new_f_occ;
     549                 :            : 
     550                 :            :   /* Update the tree.  */
     551                 : 1031890000 :   t->father = father;
     552                 : 1031890000 :   right = father->son;
     553                 : 1031890000 :   if (right)
     554                 :  422861000 :     left = right->left;
     555                 :            :   else
     556                 :            :     left = right = t;
     557                 :            : 
     558                 : 1031890000 :   left->right = t;
     559                 : 1031890000 :   right->left = t;
     560                 : 1031890000 :   t->left = left;
     561                 : 1031890000 :   t->right = right;
     562                 :            : 
     563                 : 1031890000 :   father->son = t;
     564                 :            : 
     565                 :            : #ifdef DEBUG_ET
     566                 :            :   et_check_tree_sanity (rmost);
     567                 :            :   record_path_before (rmost);
     568                 :            : #endif
     569                 : 1031890000 : }
     570                 :            : 
     571                 :            : /* Splits the edge from T to its father.  */
     572                 :            : 
     573                 :            : void
     574                 :   42674500 : et_split (struct et_node *t)
     575                 :            : {
     576                 :   42674500 :   struct et_node *father = t->father;
     577                 :   42674500 :   struct et_occ *r, *l, *rmost, *p_occ;
     578                 :            : 
     579                 :            :   /* Update the path represented by the splay tree.  */
     580                 :   42674500 :   rmost = t->rightmost_occ;
     581                 :   42674500 :   et_splay (rmost);
     582                 :            : 
     583                 :   83829500 :   for (r = rmost->next; r->prev; r = r->prev)
     584                 :   41155100 :     continue;
     585                 :   42674500 :   et_splay (r);
     586                 :            : 
     587                 :   42674500 :   r->prev->parent = NULL;
     588                 :   42674500 :   p_occ = t->parent_occ;
     589                 :   42674500 :   et_splay (p_occ);
     590                 :   42674500 :   t->parent_occ = NULL;
     591                 :            : 
     592                 :   42674500 :   l = p_occ->prev;
     593                 :   42674500 :   p_occ->next->parent = NULL;
     594                 :            : 
     595                 :   42674500 :   set_prev (r, l);
     596                 :            : 
     597                 :   42674500 :   et_recomp_min (r);
     598                 :            : 
     599                 :   42674500 :   et_splay (rmost);
     600                 :   42674500 :   rmost->depth = 0;
     601                 :   42674500 :   rmost->min = 0;
     602                 :            : 
     603                 :   42674500 :   et_occurrences.remove (p_occ);
     604                 :            : 
     605                 :            :   /* Update the tree.  */
     606                 :   42674500 :   if (father->son == t)
     607                 :   25810800 :     father->son = t->right;
     608                 :   42674500 :   if (father->son == t)
     609                 :   16773800 :     father->son = NULL;
     610                 :            :   else
     611                 :            :     {
     612                 :   25900700 :       t->left->right = t->right;
     613                 :   25900700 :       t->right->left = t->left;
     614                 :            :     }
     615                 :   42674500 :   t->left = t->right = NULL;
     616                 :   42674500 :   t->father = NULL;
     617                 :            : 
     618                 :            : #ifdef DEBUG_ET
     619                 :            :   et_check_tree_sanity (rmost);
     620                 :            :   record_path_before (rmost);
     621                 :            : 
     622                 :            :   et_check_tree_sanity (r);
     623                 :            :   record_path_before (r);
     624                 :            : #endif
     625                 :   42674500 : }
     626                 :            : 
     627                 :            : /* Finds the nearest common ancestor of the nodes N1 and N2.  */
     628                 :            : 
     629                 :            : struct et_node *
     630                 :   60833100 : et_nca (struct et_node *n1, struct et_node *n2)
     631                 :            : {
     632                 :   60833100 :   struct et_occ *o1 = n1->rightmost_occ, *o2 = n2->rightmost_occ, *om;
     633                 :   60833100 :   struct et_occ *l, *r, *ret;
     634                 :   60833100 :   int mn;
     635                 :            : 
     636                 :   60833100 :   if (n1 == n2)
     637                 :            :     return n1;
     638                 :            : 
     639                 :   54054900 :   et_splay (o1);
     640                 :   54054900 :   l = o1->prev;
     641                 :   54054900 :   r = o1->next;
     642                 :   54054900 :   if (l)
     643                 :   54054900 :     l->parent = NULL;
     644                 :   54054900 :   if (r)
     645                 :   54049200 :     r->parent = NULL;
     646                 :   54054900 :   et_splay (o2);
     647                 :            : 
     648                 :   54054900 :   if (l == o2 || (l && l->parent != NULL))
     649                 :            :     {
     650                 :   49485600 :       ret = o2->next;
     651                 :            : 
     652                 :   49485600 :       set_prev (o1, o2);
     653                 :   49485600 :       if (r)
     654                 :   49479900 :         r->parent = o1;
     655                 :            :     }
     656                 :    4569340 :   else if (r == o2 || (r && r->parent != NULL))
     657                 :            :     {
     658                 :    4569340 :       ret = o2->prev;
     659                 :            : 
     660                 :    4569340 :       set_next (o1, o2);
     661                 :    4569340 :       if (l)
     662                 :    4569340 :         l->parent = o1;
     663                 :            :     }
     664                 :            :   else
     665                 :            :     {
     666                 :            :       /* O1 and O2 are in different components of the forest.  */
     667                 :          0 :       if (l)
     668                 :          0 :         l->parent = o1;
     669                 :          0 :       if (r)
     670                 :          0 :         r->parent = o1;
     671                 :          0 :       return NULL;
     672                 :            :     }
     673                 :            : 
     674                 :   54054900 :   if (o2->depth > 0)
     675                 :            :     {
     676                 :   49199700 :       om = o1;
     677                 :   49199700 :       mn = o1->depth;
     678                 :            :     }
     679                 :            :   else
     680                 :            :     {
     681                 :    4855240 :       om = o2;
     682                 :    4855240 :       mn = o2->depth + o1->depth;
     683                 :            :     }
     684                 :            : 
     685                 :            : #ifdef DEBUG_ET
     686                 :            :   et_check_tree_sanity (o2);
     687                 :            : #endif
     688                 :            : 
     689                 :   54054900 :   if (ret && ret->min + o1->depth + o2->depth < mn)
     690                 :    3476320 :     return ret->min_occ->of;
     691                 :            :   else
     692                 :   50578600 :     return om->of;
     693                 :            : }
     694                 :            : 
     695                 :            : /* Checks whether the node UP is an ancestor of the node DOWN.  */
     696                 :            : 
     697                 :            : bool
     698                 :  322744000 : et_below (struct et_node *down, struct et_node *up)
     699                 :            : {
     700                 :  322744000 :   struct et_occ *u = up->rightmost_occ, *d = down->rightmost_occ;
     701                 :  322744000 :   struct et_occ *l, *r;
     702                 :            : 
     703                 :  322744000 :   if (up == down)
     704                 :            :     return true;
     705                 :            : 
     706                 :  309687000 :   et_splay (u);
     707                 :  309687000 :   l = u->prev;
     708                 :  309687000 :   r = u->next;
     709                 :            : 
     710                 :  309687000 :   if (!l)
     711                 :            :     return false;
     712                 :            : 
     713                 :  309497000 :   l->parent = NULL;
     714                 :            : 
     715                 :  309497000 :   if (r)
     716                 :  309012000 :     r->parent = NULL;
     717                 :            : 
     718                 :  309497000 :   et_splay (d);
     719                 :            : 
     720                 :  309497000 :   if (l == d || l->parent != NULL)
     721                 :            :     {
     722                 :  158646000 :       if (r)
     723                 :  158497000 :         r->parent = u;
     724                 :  158646000 :       set_prev (u, d);
     725                 :            : #ifdef DEBUG_ET
     726                 :            :       et_check_tree_sanity (u);
     727                 :            : #endif
     728                 :            :     }
     729                 :            :   else
     730                 :            :     {
     731                 :  150852000 :       l->parent = u;
     732                 :            : 
     733                 :            :       /* In case O1 and O2 are in two different trees, we must just restore the
     734                 :            :          original state.  */
     735                 :  150852000 :       if (r && r->parent != NULL)
     736                 :   59447000 :         set_next (u, d);
     737                 :            :       else
     738                 :   91404500 :         set_next (u, r);
     739                 :            : 
     740                 :            : #ifdef DEBUG_ET
     741                 :            :       et_check_tree_sanity (u);
     742                 :            : #endif
     743                 :  150852000 :       return false;
     744                 :            :     }
     745                 :            : 
     746                 :  158646000 :   if (d->depth <= 0)
     747                 :            :     return false;
     748                 :            : 
     749                 :  140124000 :   return !d->next || d->next->min + d->depth >= 0;
     750                 :            : }
     751                 :            : 
     752                 :            : /* Returns the root of the tree that contains NODE.  */
     753                 :            : 
     754                 :            : struct et_node *
     755                 :    3889010 : et_root (struct et_node *node)
     756                 :            : {
     757                 :    3889010 :   struct et_occ *occ = node->rightmost_occ, *r;
     758                 :            : 
     759                 :            :   /* The root of the tree corresponds to the rightmost occurrence in the
     760                 :            :      represented path.  */
     761                 :    3889010 :   et_splay (occ);
     762                 :   10775500 :   for (r = occ; r->next; r = r->next)
     763                 :    6886470 :     continue;
     764                 :    3889010 :   et_splay (r);
     765                 :            : 
     766                 :    3889010 :   return r->of;
     767                 :            : }
     768                 :            : 
     769                 :            : #if CHECKING_P
     770                 :            : 
     771                 :            : namespace selftest {
     772                 :            : 
     773                 :            : /* Selftests for et-forest.c.  */
     774                 :            : 
     775                 :            : /* Perform sanity checks for a tree consisting of a single node.  */
     776                 :            : 
     777                 :            : static void
     778                 :          2 : test_single_node ()
     779                 :            : {
     780                 :          2 :   void *test_data = (void *)0xcafebabe;
     781                 :            : 
     782                 :          2 :   et_node *n = et_new_tree (test_data);
     783                 :          2 :   ASSERT_EQ (n->data, test_data);
     784                 :          2 :   ASSERT_EQ (n, et_root (n));
     785                 :          2 :   et_free_tree (n);
     786                 :          2 : }
     787                 :            : 
     788                 :            : /* Test of this tree:
     789                 :            :        a
     790                 :            :       / \
     791                 :            :      /   \
     792                 :            :     b     c
     793                 :            :    / \    |
     794                 :            :   d   e   f.  */
     795                 :            : 
     796                 :            : static void
     797                 :          2 : test_simple_tree ()
     798                 :            : {
     799                 :          2 :   et_node *a = et_new_tree (NULL);
     800                 :          2 :   et_node *b = et_new_tree (NULL);
     801                 :          2 :   et_node *c = et_new_tree (NULL);
     802                 :          2 :   et_node *d = et_new_tree (NULL);
     803                 :          2 :   et_node *e = et_new_tree (NULL);
     804                 :          2 :   et_node *f = et_new_tree (NULL);
     805                 :            : 
     806                 :          2 :   et_set_father (b, a);
     807                 :          2 :   et_set_father (c, a);
     808                 :          2 :   et_set_father (d, b);
     809                 :          2 :   et_set_father (e, b);
     810                 :          2 :   et_set_father (f, c);
     811                 :            : 
     812                 :          2 :   ASSERT_TRUE (et_below (a, a));
     813                 :          2 :   ASSERT_TRUE (et_below (b, a));
     814                 :          2 :   ASSERT_TRUE (et_below (c, a));
     815                 :          2 :   ASSERT_TRUE (et_below (d, a));
     816                 :          2 :   ASSERT_TRUE (et_below (e, a));
     817                 :          2 :   ASSERT_TRUE (et_below (f, a));
     818                 :            : 
     819                 :          2 :   ASSERT_FALSE (et_below (a, b));
     820                 :          2 :   ASSERT_TRUE (et_below (b, b));
     821                 :          2 :   ASSERT_FALSE (et_below (c, b));
     822                 :          2 :   ASSERT_TRUE (et_below (d, b));
     823                 :          2 :   ASSERT_TRUE (et_below (e, b));
     824                 :          2 :   ASSERT_FALSE (et_below (f, b));
     825                 :            : 
     826                 :          2 :   ASSERT_FALSE (et_below (a, c));
     827                 :          2 :   ASSERT_FALSE (et_below (b, c));
     828                 :          2 :   ASSERT_TRUE (et_below (c, c));
     829                 :          2 :   ASSERT_FALSE (et_below (d, c));
     830                 :          2 :   ASSERT_FALSE (et_below (e, c));
     831                 :          2 :   ASSERT_TRUE (et_below (f, c));
     832                 :            : 
     833                 :          2 :   ASSERT_FALSE (et_below (a, d));
     834                 :          2 :   ASSERT_FALSE (et_below (b, d));
     835                 :          2 :   ASSERT_FALSE (et_below (c, d));
     836                 :          2 :   ASSERT_TRUE (et_below (d, d));
     837                 :          2 :   ASSERT_FALSE (et_below (e, d));
     838                 :          2 :   ASSERT_FALSE (et_below (f, d));
     839                 :            : 
     840                 :          2 :   ASSERT_FALSE (et_below (a, e));
     841                 :          2 :   ASSERT_FALSE (et_below (b, e));
     842                 :          2 :   ASSERT_FALSE (et_below (c, e));
     843                 :          2 :   ASSERT_FALSE (et_below (d, e));
     844                 :          2 :   ASSERT_TRUE (et_below (e, e));
     845                 :          2 :   ASSERT_FALSE (et_below (f, e));
     846                 :            : 
     847                 :          2 :   ASSERT_FALSE (et_below (a, f));
     848                 :          2 :   ASSERT_FALSE (et_below (b, f));
     849                 :          2 :   ASSERT_FALSE (et_below (c, f));
     850                 :          2 :   ASSERT_FALSE (et_below (d, f));
     851                 :          2 :   ASSERT_FALSE (et_below (e, f));
     852                 :          2 :   ASSERT_TRUE (et_below (f, f));
     853                 :            : 
     854                 :          2 :   et_free_tree_force (a);
     855                 :          2 : }
     856                 :            : 
     857                 :            : /* Verify that two disconnected nodes are unrelated.  */
     858                 :            : 
     859                 :            : static void
     860                 :          2 : test_disconnected_nodes ()
     861                 :            : {
     862                 :          2 :   et_node *a = et_new_tree (NULL);
     863                 :          2 :   et_node *b = et_new_tree (NULL);
     864                 :            : 
     865                 :          2 :   ASSERT_FALSE (et_below (a, b));
     866                 :          2 :   ASSERT_FALSE (et_below (b, a));
     867                 :            : 
     868                 :          2 :   et_free_tree (a);
     869                 :          2 :   et_free_tree (b);
     870                 :          2 : }
     871                 :            : 
     872                 :            : /* Run all of the selftests within this file.  */
     873                 :            : 
     874                 :            : void
     875                 :          2 : et_forest_c_tests ()
     876                 :            : {
     877                 :          2 :   test_single_node ();
     878                 :          2 :   test_simple_tree ();
     879                 :          2 :   test_disconnected_nodes ();
     880                 :          2 : }
     881                 :            : 
     882                 :            : } // namespace selftest
     883                 :            : 
     884                 :            : #endif /* CHECKING_P */

Generated by: LCOV version 1.0

LCOV profile is generated on x86_64 machine using following configure options: configure --disable-bootstrap --enable-coverage=opt --enable-languages=c,c++,fortran,go,jit,lto --enable-host-shared. GCC test suite is run with the built compiler.