LCOV - code coverage report
Current view: top level - gcc/fortran - bbt.c (source / functions) Hit Total Coverage
Test: gcc.info Lines: 60 61 98.4 %
Date: 2020-03-28 11:57:23 Functions: 5 8 62.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-2020 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                 :    4768980 : pseudo_random (void)
      55                 :            : {
      56                 :    4768980 :   static int x0 = 5341;
      57                 :            : 
      58                 :    4768980 :   x0 = (22611 * x0 + 10) % 44071;
      59                 :    4768980 :   return x0;
      60                 :            : }
      61                 :            : 
      62                 :            : 
      63                 :            : /* Rotate the treap left.  */
      64                 :            : 
      65                 :            : static gfc_bbt *
      66                 :    3200420 : rotate_left (gfc_bbt *t)
      67                 :            : {
      68                 :    3200420 :   gfc_bbt *temp;
      69                 :            : 
      70                 :    3200420 :   temp = t->right;
      71                 :    3200420 :   t->right = t->right->left;
      72                 :    3200420 :   temp->left = t;
      73                 :            : 
      74                 :    3200420 :   return temp;
      75                 :            : }
      76                 :            : 
      77                 :            : 
      78                 :            : /* Rotate the treap right.  */
      79                 :            : 
      80                 :            : static gfc_bbt *
      81                 :    2571400 : rotate_right (gfc_bbt *t)
      82                 :            : {
      83                 :    2571400 :   gfc_bbt *temp;
      84                 :            : 
      85                 :    2571400 :   temp = t->left;
      86                 :    2571400 :   t->left = t->left->right;
      87                 :    2571400 :   temp->right = t;
      88                 :            : 
      89                 :    2571400 :   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                 :   21756400 : insert (gfc_bbt *new_bbt, gfc_bbt *t, compare_fn compare)
      98                 :            : {
      99                 :   21756400 :   int c;
     100                 :            : 
     101                 :   21756400 :   if (t == NULL)
     102                 :            :     return new_bbt;
     103                 :            : 
     104                 :   16987500 :   c = (*compare) (new_bbt, t);
     105                 :            : 
     106                 :   16987500 :   if (c < 0)
     107                 :            :     {
     108                 :    7216190 :       t->left = insert (new_bbt, t->left, compare);
     109                 :    7216190 :       if (t->priority < t->left->priority)
     110                 :    2146480 :         t = rotate_right (t);
     111                 :            :     }
     112                 :    9771260 :   else if (c > 0)
     113                 :            :     {
     114                 :    9771260 :       t->right = insert (new_bbt, t->right, compare);
     115                 :    9771260 :       if (t->priority < t->right->priority)
     116                 :    2772170 :         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                 :    4768980 : gfc_insert_bbt (void *root, void *new_node, compare_fn compare)
     131                 :            : {
     132                 :    4768980 :   gfc_bbt **r, *n;
     133                 :            : 
     134                 :    4768980 :   r = (gfc_bbt **) root;
     135                 :    4768980 :   n = (gfc_bbt *) new_node;
     136                 :    4768980 :   n->priority = pseudo_random ();
     137                 :    4768980 :   *r = insert (n, *r, compare);
     138                 :    4768980 : }
     139                 :            : 
     140                 :            : static gfc_bbt *
     141                 :    3555300 : delete_root (gfc_bbt *t)
     142                 :            : {
     143                 :    3555300 :   gfc_bbt *temp;
     144                 :            : 
     145                 :    3555300 :   if (t->left == NULL)
     146                 :    1984250 :     return t->right;
     147                 :    1571050 :   if (t->right == NULL)
     148                 :            :     return t->left;
     149                 :            : 
     150                 :     853162 :   if (t->left->priority > t->right->priority)
     151                 :            :     {
     152                 :     424917 :       temp = rotate_right (t);
     153                 :     424917 :       temp->right = delete_root (t);
     154                 :            :     }
     155                 :            :   else
     156                 :            :     {
     157                 :     428245 :       temp = rotate_left (t);
     158                 :     428245 :       temp->left = delete_root (t);
     159                 :            :     }
     160                 :            : 
     161                 :            :   return temp;
     162                 :            : }
     163                 :            : 
     164                 :            : 
     165                 :            : /* Delete an element from a tree.  The 'old' value does not
     166                 :            :    necessarily have to point to the element to be deleted, it must
     167                 :            :    just point to a treap structure with the key to be deleted.
     168                 :            :    Returns the new root node of the tree.  */
     169                 :            : 
     170                 :            : static gfc_bbt *
     171                 :    8307270 : delete_treap (gfc_bbt *old, gfc_bbt *t, compare_fn compare)
     172                 :            : {
     173                 :    8307270 :   int c;
     174                 :            : 
     175                 :    8307270 :   if (t == NULL)
     176                 :            :     return NULL;
     177                 :            : 
     178                 :    8307270 :   c = (*compare) (old, t);
     179                 :            : 
     180                 :    8307270 :   if (c < 0)
     181                 :    2658100 :     t->left = delete_treap (old, t->left, compare);
     182                 :    8307270 :   if (c > 0)
     183                 :    2947030 :     t->right = delete_treap (old, t->right, compare);
     184                 :    8307270 :   if (c == 0)
     185                 :    2702140 :     t = delete_root (t);
     186                 :            : 
     187                 :            :   return t;
     188                 :            : }
     189                 :            : 
     190                 :            : 
     191                 :            : void
     192                 :    2702140 : gfc_delete_bbt (void *root, void *old, compare_fn compare)
     193                 :            : {
     194                 :    2702140 :   gfc_bbt **t;
     195                 :            : 
     196                 :    2702140 :   t = (gfc_bbt **) root;
     197                 :    2702140 :   *t = delete_treap ((gfc_bbt *) old, *t, compare);
     198                 :    2702140 : }

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.