LCOV - code coverage report
Current view: top level - gcc/fortran - bbt.cc (source / functions) Coverage Total Hit
Test: gcc.info Lines: 94.0 % 67 63
Test Date: 2024-03-23 14:05:01 Functions: 62.5 % 8 5
Legend: Lines: hit not hit | Branches: + taken - not taken # not executed Branches: - 0 0

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

Generated by: LCOV version 2.0-1

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,rust,m2 --enable-host-shared. GCC test suite is run with the built compiler.