LCOV - code coverage report
Current view: top level - gcc - typed-splay-tree.h (source / functions) Coverage Total Hit
Test: gcc.info Lines: 95.6 % 180 172
Test Date: 2024-11-02 13:25:42 Functions: 100.0 % 24 24
Legend: Lines: hit not hit | Branches: + taken - not taken # not executed Branches: - 0 0

             Branch data     Line data    Source code
       1                 :             : /* A typesafe wrapper around libiberty's splay-tree.h.
       2                 :             :    Copyright (C) 2015-2024 Free Software Foundation, Inc.
       3                 :             : 
       4                 :             : This file is part of GCC.
       5                 :             : 
       6                 :             : GCC is free software; you can redistribute it and/or modify it under
       7                 :             : the terms of the GNU General Public License as published by the Free
       8                 :             : Software Foundation; either version 3, or (at your option) any later
       9                 :             : version.
      10                 :             : 
      11                 :             : GCC is distributed in the hope that it will be useful, but WITHOUT ANY
      12                 :             : WARRANTY; without even the implied warranty of MERCHANTABILITY or
      13                 :             : FITNESS FOR A PARTICULAR PURPOSE.  See the GNU General Public License
      14                 :             : for more details.
      15                 :             : 
      16                 :             : You should have received a copy of the GNU General Public License
      17                 :             : along with GCC; see the file COPYING3.  If not see
      18                 :             : <http://www.gnu.org/licenses/>.  */
      19                 :             : 
      20                 :             : #ifndef GCC_TYPED_SPLAY_TREE_H
      21                 :             : #define GCC_TYPED_SPLAY_TREE_H
      22                 :             : 
      23                 :             : /* Typesafe wrapper around libiberty's splay-tree.h.  */
      24                 :             : template <typename KEY_TYPE, typename VALUE_TYPE>
      25                 :             : class typed_splay_tree
      26                 :             : {
      27                 :             :  public:
      28                 :             :   typedef KEY_TYPE key_type;
      29                 :             :   typedef VALUE_TYPE value_type;
      30                 :             : 
      31                 :             :   typedef int (*compare_fn) (key_type, key_type);
      32                 :             :   typedef void (*delete_key_fn) (key_type);
      33                 :             :   typedef void (*delete_value_fn) (value_type);
      34                 :             :   typedef int (*foreach_fn) (key_type, value_type, void *);
      35                 :             : 
      36                 :             :   typed_splay_tree (compare_fn,
      37                 :             :                     delete_key_fn,
      38                 :             :                     delete_value_fn);
      39                 :             :   ~typed_splay_tree ();
      40                 :             : 
      41                 :             :   value_type lookup (key_type k);
      42                 :             :   value_type predecessor (key_type k);
      43                 :             :   value_type successor (key_type k);
      44                 :             :   void insert (key_type k, value_type v);
      45                 :             :   void remove (key_type k);
      46                 :             :   value_type max ();
      47                 :             :   value_type min ();
      48                 :             :   int foreach (foreach_fn, void *);
      49                 :             : 
      50                 :             :  private:
      51                 :             :   /* Copy and assignment ops are not supported.  */
      52                 :             :   typed_splay_tree (const typed_splay_tree &);
      53                 :             :   typed_splay_tree & operator = (const typed_splay_tree &);
      54                 :             : 
      55                 :             :   typedef key_type splay_tree_key;
      56                 :             :   typedef value_type splay_tree_value;
      57                 :             : 
      58                 :             :   /* The nodes in the splay tree.  */
      59                 :             :   struct splay_tree_node_s {
      60                 :             :     /* The key.  */
      61                 :             :     splay_tree_key key;
      62                 :             : 
      63                 :             :     /* The value.  */
      64                 :             :     splay_tree_value value;
      65                 :             : 
      66                 :             :     /* The left and right children, respectively.  */
      67                 :             :     splay_tree_node_s *left, *right;
      68                 :             : 
      69                 :             :     /* Used as temporary value for tree traversals.  */
      70                 :             :     splay_tree_node_s *back;
      71                 :             :   };
      72                 :             :   typedef splay_tree_node_s *splay_tree_node;
      73                 :             : 
      74                 :             :   inline void KDEL (splay_tree_key);
      75                 :             :   inline void VDEL (splay_tree_value);
      76                 :             :   void splay_tree_delete_helper (splay_tree_node);
      77                 :             :   static inline void rotate_left (splay_tree_node *,
      78                 :             :                                   splay_tree_node, splay_tree_node);
      79                 :             :   static inline void rotate_right (splay_tree_node *,
      80                 :             :                                    splay_tree_node, splay_tree_node);
      81                 :             :   void splay_tree_splay (splay_tree_key);
      82                 :             :   static int splay_tree_foreach_helper (splay_tree_node,
      83                 :             :                                         foreach_fn, void*);
      84                 :             :   splay_tree_node splay_tree_insert (splay_tree_key, splay_tree_value);
      85                 :             :   void splay_tree_remove (splay_tree_key key);
      86                 :             :   splay_tree_node splay_tree_lookup (splay_tree_key key);
      87                 :             :   splay_tree_node splay_tree_predecessor (splay_tree_key);
      88                 :             :   splay_tree_node splay_tree_successor (splay_tree_key);
      89                 :             :   splay_tree_node splay_tree_max ();
      90                 :             :   splay_tree_node splay_tree_min ();
      91                 :             : 
      92                 :             :   static value_type node_to_value (splay_tree_node node);
      93                 :             : 
      94                 :             :   /* The root of the tree.  */
      95                 :             :   splay_tree_node root;
      96                 :             : 
      97                 :             :   /* The comparision function.  */
      98                 :             :   compare_fn comp;
      99                 :             : 
     100                 :             :   /* The deallocate-key function.  NULL if no cleanup is necessary.  */
     101                 :             :   delete_key_fn delete_key;
     102                 :             : 
     103                 :             :   /* The deallocate-value function.  NULL if no cleanup is necessary.  */
     104                 :             :   delete_value_fn delete_value;
     105                 :             : };
     106                 :             : 
     107                 :             : /* Constructor for typed_splay_tree <K, V>.  */
     108                 :             : 
     109                 :             : template <typename KEY_TYPE, typename VALUE_TYPE>
     110                 :       85612 : inline typed_splay_tree<KEY_TYPE, VALUE_TYPE>::
     111                 :             :   typed_splay_tree (compare_fn compare_fn,
     112                 :             :                     delete_key_fn delete_key_fn,
     113                 :             :                     delete_value_fn delete_value_fn)
     114                 :             : {
     115                 :       85612 :   root = NULL;
     116                 :       85612 :   comp = compare_fn;
     117                 :       85612 :   delete_key = delete_key_fn;
     118                 :       85612 :   delete_value = delete_value_fn;
     119                 :             : }
     120                 :             : 
     121                 :             : /* Destructor for typed_splay_tree <K, V>.  */
     122                 :             : 
     123                 :             : template <typename KEY_TYPE, typename VALUE_TYPE>
     124                 :       13612 : inline typed_splay_tree<KEY_TYPE, VALUE_TYPE>::
     125                 :             :   ~typed_splay_tree ()
     126                 :             : {
     127                 :       13612 :   splay_tree_delete_helper (root);
     128                 :           4 : }
     129                 :             : 
     130                 :             : /* Lookup KEY, returning a value if present, and NULL
     131                 :             :    otherwise.  */
     132                 :             : 
     133                 :             : template <typename KEY_TYPE, typename VALUE_TYPE>
     134                 :             : inline VALUE_TYPE
     135                 :       91088 : typed_splay_tree<KEY_TYPE, VALUE_TYPE>::lookup (key_type key)
     136                 :             : {
     137                 :       91088 :   splay_tree_node node = splay_tree_lookup (key);
     138                 :       91076 :   return node_to_value (node);
     139                 :             : }
     140                 :             : 
     141                 :             : /* Return the immediate predecessor of KEY, or NULL if there is no
     142                 :             :    predecessor.  KEY need not be present in the tree.  */
     143                 :             : 
     144                 :             : template <typename KEY_TYPE, typename VALUE_TYPE>
     145                 :             : inline VALUE_TYPE
     146                 :          94 : typed_splay_tree<KEY_TYPE, VALUE_TYPE>::predecessor (key_type key)
     147                 :             : {
     148                 :          94 :   splay_tree_node node = splay_tree_predecessor (key);
     149                 :          90 :   return node_to_value (node);
     150                 :             : }
     151                 :             : 
     152                 :             : /* Return the immediate successor of KEY, or NULL if there is no
     153                 :             :    successor.  KEY need not be present in the tree.  */
     154                 :             : 
     155                 :             : template <typename KEY_TYPE, typename VALUE_TYPE>
     156                 :             : inline VALUE_TYPE
     157                 :       18778 : typed_splay_tree<KEY_TYPE, VALUE_TYPE>::successor (key_type key)
     158                 :             : {
     159                 :       18778 :   splay_tree_node node = splay_tree_successor (key);
     160                 :       27635 :   return node_to_value (node);
     161                 :             : }
     162                 :             : 
     163                 :             : /* Insert a new node (associating KEY with VALUE).  If a
     164                 :             :    previous node with the indicated KEY exists, its data is replaced
     165                 :             :    with the new value.  */
     166                 :             : 
     167                 :             : template <typename KEY_TYPE, typename VALUE_TYPE>
     168                 :             : inline void
     169                 :       24168 : typed_splay_tree<KEY_TYPE, VALUE_TYPE>::insert (key_type key,
     170                 :             :                                                 value_type value)
     171                 :             : {
     172                 :       24156 :   splay_tree_insert (key, value);
     173                 :             : }
     174                 :             : 
     175                 :             : /* Remove a node (associating KEY with VALUE).  */
     176                 :             : 
     177                 :             : template <typename KEY_TYPE, typename VALUE_TYPE>
     178                 :             : inline void
     179                 :           4 : typed_splay_tree<KEY_TYPE, VALUE_TYPE>::remove (key_type key)
     180                 :             : {
     181                 :           4 :   splay_tree_remove (key);
     182                 :             : }
     183                 :             : 
     184                 :             : /* Get the value with maximal key.  */
     185                 :             : 
     186                 :             : template <typename KEY_TYPE, typename VALUE_TYPE>
     187                 :             : inline VALUE_TYPE
     188                 :           4 : typed_splay_tree<KEY_TYPE, VALUE_TYPE>::max ()
     189                 :             : {
     190                 :           4 :   return node_to_value (splay_tree_max ());
     191                 :             : }
     192                 :             : 
     193                 :             : /* Get the value with minimal key.  */
     194                 :             : 
     195                 :             : template <typename KEY_TYPE, typename VALUE_TYPE>
     196                 :             : inline VALUE_TYPE
     197                 :        9145 : typed_splay_tree<KEY_TYPE, VALUE_TYPE>::min ()
     198                 :             : {
     199                 :        9141 :   return node_to_value (splay_tree_min ());
     200                 :             : }
     201                 :             : 
     202                 :             : /* Call OUTER_CB, passing it the OUTER_USER_DATA, for every node,
     203                 :             :    following an in-order traversal.  If OUTER_CB ever returns a non-zero
     204                 :             :    value, the iteration ceases immediately, and the value is returned.
     205                 :             :    Otherwise, this function returns 0.  */
     206                 :             : 
     207                 :             : template <typename KEY_TYPE, typename VALUE_TYPE>
     208                 :             : inline int
     209                 :        9145 : typed_splay_tree<KEY_TYPE, VALUE_TYPE>::foreach (foreach_fn foreach_fn,
     210                 :             :                                                  void *user_data)
     211                 :             : {
     212                 :        9145 :   return splay_tree_foreach_helper (root, foreach_fn, user_data);
     213                 :             : }
     214                 :             : 
     215                 :             : /* Internal function for converting from splay_tree_node to
     216                 :             :    VALUE_TYPE.  */
     217                 :             : template <typename KEY_TYPE, typename VALUE_TYPE>
     218                 :             : inline VALUE_TYPE
     219                 :      119109 : typed_splay_tree<KEY_TYPE, VALUE_TYPE>::node_to_value (splay_tree_node node)
     220                 :             : {
     221                 :      109960 :   if (node)
     222                 :       61395 :     return node->value;
     223                 :             :   else
     224                 :             :     return 0;
     225                 :             : }
     226                 :             : 
     227                 :             : template <typename KEY_TYPE, typename VALUE_TYPE>
     228                 :             : inline void
     229                 :       24164 : typed_splay_tree<KEY_TYPE, VALUE_TYPE>::KDEL(splay_tree_key x)
     230                 :             : {
     231                 :       24164 :   if (delete_key)
     232                 :           0 :     (*delete_key)(x);
     233                 :             : }
     234                 :             : 
     235                 :             : template <typename KEY_TYPE, typename VALUE_TYPE>
     236                 :             : inline void
     237                 :       24168 : typed_splay_tree<KEY_TYPE, VALUE_TYPE>::VDEL(splay_tree_value x)
     238                 :             : {
     239                 :       24168 :   if (delete_value)
     240                 :       24067 :     (*delete_value)(x);
     241                 :             : }
     242                 :             : 
     243                 :             : /* Deallocate NODE (a member of SP), and all its sub-trees.  */
     244                 :             : 
     245                 :             : template <typename KEY_TYPE, typename VALUE_TYPE>
     246                 :             : void
     247                 :       85612 : typed_splay_tree<KEY_TYPE,
     248                 :             :                  VALUE_TYPE>::splay_tree_delete_helper (splay_tree_node node)
     249                 :             : {
     250                 :       85612 :   splay_tree_node pending = NULL;
     251                 :       85612 :   splay_tree_node active = NULL;
     252                 :             : 
     253                 :       85612 :   if (!node)
     254                 :             :     return;
     255                 :             : 
     256                 :       23755 :   KDEL (node->key);
     257                 :       23755 :   VDEL (node->value);
     258                 :             : 
     259                 :             :   /* We use the "back" field to hold the "next" pointer.  */
     260                 :       23755 :   node->back = pending;
     261                 :       23755 :   pending = node;
     262                 :             : 
     263                 :             :   /* Now, keep processing the pending list until there aren't any
     264                 :             :      more.  This is a little more complicated than just recursing, but
     265                 :             :      it doesn't toast the stack for large trees.  */
     266                 :             : 
     267                 :       47915 :   while (pending)
     268                 :             :     {
     269                 :             :       active = pending;
     270                 :             :       pending = NULL;
     271                 :       48324 :       while (active)
     272                 :             :         {
     273                 :             :           splay_tree_node temp;
     274                 :             : 
     275                 :             :           /* active points to a node which has its key and value
     276                 :             :              deallocated, we just need to process left and right.  */
     277                 :             : 
     278                 :       24164 :           if (active->left)
     279                 :             :             {
     280                 :         385 :               KDEL (active->left->key);
     281                 :         385 :               VDEL (active->left->value);
     282                 :         385 :               active->left->back = pending;
     283                 :         385 :               pending = active->left;
     284                 :             :             }
     285                 :       24164 :           if (active->right)
     286                 :             :             {
     287                 :          24 :               KDEL (active->right->key);
     288                 :          24 :               VDEL (active->right->value);
     289                 :          24 :               active->right->back = pending;
     290                 :             :               pending = active->right;
     291                 :             :             }
     292                 :             : 
     293                 :       24164 :           temp = active;
     294                 :       24164 :           active = temp->back;
     295                 :       24164 :           delete temp;
     296                 :             :         }
     297                 :             :     }
     298                 :             : }
     299                 :             : 
     300                 :             : /* Rotate the edge joining the left child N with its parent P.  PP is the
     301                 :             :    grandparents' pointer to P.  */
     302                 :             : 
     303                 :             : template <typename KEY_TYPE, typename VALUE_TYPE>
     304                 :             : inline void
     305                 :        1876 : typed_splay_tree<KEY_TYPE, VALUE_TYPE>::rotate_left (splay_tree_node *pp,
     306                 :             :                                                      splay_tree_node p,
     307                 :             :                                                      splay_tree_node n)
     308                 :             : {
     309                 :             :   splay_tree_node tmp;
     310                 :        1876 :   tmp = n->right;
     311                 :        1876 :   n->right = p;
     312                 :        1876 :   p->left = tmp;
     313                 :        1876 :   *pp = n;
     314                 :        1251 : }
     315                 :             : 
     316                 :             : /* Rotate the edge joining the right child N with its parent P.  PP is the
     317                 :             :    grandparents' pointer to P.  */
     318                 :             : 
     319                 :             : template <typename KEY_TYPE, typename VALUE_TYPE>
     320                 :             : inline void
     321                 :        1872 : typed_splay_tree<KEY_TYPE, VALUE_TYPE>::rotate_right (splay_tree_node *pp,
     322                 :             :                                                       splay_tree_node p,
     323                 :             :                                                       splay_tree_node n)
     324                 :             : {
     325                 :             :   splay_tree_node tmp;
     326                 :        1872 :   tmp = n->left;
     327                 :        1872 :   n->left = p;
     328                 :        1872 :   p->right = tmp;
     329                 :        1872 :   *pp = n;
     330                 :        1872 : }
     331                 :             : 
     332                 :             : /* Bottom up splay of key.  */
     333                 :             : 
     334                 :             : template <typename KEY_TYPE, typename VALUE_TYPE>
     335                 :             : void
     336                 :      134082 : typed_splay_tree<KEY_TYPE, VALUE_TYPE>::splay_tree_splay (splay_tree_key key)
     337                 :             : {
     338                 :      134082 :   if (root == NULL)
     339                 :             :     return;
     340                 :             : 
     341                 :             :   do {
     342                 :             :     int cmp1, cmp2;
     343                 :             :     splay_tree_node n, c;
     344                 :             : 
     345                 :       87118 :     n = root;
     346                 :       87118 :     cmp1 = (*comp) (key, n->key);
     347                 :             : 
     348                 :             :     /* Found.  */
     349                 :       87118 :     if (cmp1 == 0)
     350                 :             :       return;
     351                 :             : 
     352                 :             :     /* Left or right?  If no child, then we're done.  */
     353                 :       17524 :     if (cmp1 < 0)
     354                 :        3382 :       c = n->left;
     355                 :             :     else
     356                 :       14142 :       c = n->right;
     357                 :       17524 :     if (!c)
     358                 :             :       return;
     359                 :             : 
     360                 :             :     /* Next one left or right?  If found or no child, we're done
     361                 :             :        after one rotation.  */
     362                 :        3123 :     cmp2 = (*comp) (key, c->key);
     363                 :        3123 :     if (cmp2 == 0
     364                 :        2250 :         || (cmp2 < 0 && !c->left)
     365                 :        1637 :         || (cmp2 > 0 && !c->right))
     366                 :             :       {
     367                 :        1853 :         if (cmp1 < 0)
     368                 :         626 :           rotate_left (&root, n, c);
     369                 :             :         else
     370                 :        1227 :           rotate_right (&root, n, c);
     371                 :        1853 :         return;
     372                 :             :       }
     373                 :             : 
     374                 :             :     /* Now we have the four cases of double-rotation.  */
     375                 :        1270 :     if (cmp1 < 0 && cmp2 < 0)
     376                 :             :       {
     377                 :         625 :         rotate_left (&n->left, c, c->left);
     378                 :         625 :         rotate_left (&root, n, n->left);
     379                 :             :       }
     380                 :         645 :     else if (cmp1 > 0 && cmp2 > 0)
     381                 :             :       {
     382                 :          20 :         rotate_right (&n->right, c, c->right);
     383                 :          20 :         rotate_right (&root, n, n->right);
     384                 :             :       }
     385                 :         625 :     else if (cmp1 < 0 && cmp2 > 0)
     386                 :             :       {
     387                 :           0 :         rotate_right (&n->left, c, c->right);
     388                 :           0 :         rotate_left (&root, n, n->left);
     389                 :             :       }
     390                 :         625 :     else if (cmp1 > 0 && cmp2 < 0)
     391                 :             :       {
     392                 :         625 :         rotate_left (&n->right, c, c->left);
     393                 :         625 :         rotate_right (&root, n, n->right);
     394                 :             :       }
     395                 :             :   } while (1);
     396                 :             : }
     397                 :             : 
     398                 :             : /* Call FN, passing it the DATA, for every node below NODE, all of
     399                 :             :    which are from SP, following an in-order traversal.  If FN every
     400                 :             :    returns a non-zero value, the iteration ceases immediately, and the
     401                 :             :    value is returned.  Otherwise, this function returns 0.  */
     402                 :             : 
     403                 :             : template <typename KEY_TYPE, typename VALUE_TYPE>
     404                 :             : int
     405                 :        9145 : typed_splay_tree<KEY_TYPE, VALUE_TYPE>::splay_tree_foreach_helper (
     406                 :             :                                                 splay_tree_node node,
     407                 :             :                                                 foreach_fn fn, void *data)
     408                 :             : {
     409                 :             :   int val;
     410                 :             :   splay_tree_node stack;
     411                 :             : 
     412                 :             :   /* A non-recursive implementation is used to avoid filling the stack
     413                 :             :      for large trees.  Splay trees are worst case O(n) in the depth of
     414                 :             :      the tree.  */
     415                 :             : 
     416                 :        9145 :   stack = NULL;
     417                 :        9145 :   val = 0;
     418                 :             : 
     419                 :        9153 :   for (;;)
     420                 :             :     {
     421                 :       27451 :       while (node != NULL)
     422                 :             :         {
     423                 :        9153 :           node->back = stack;
     424                 :        9153 :           stack = node;
     425                 :        9153 :           node = node->left;
     426                 :             :         }
     427                 :             : 
     428                 :       18298 :       if (stack == NULL)
     429                 :             :         break;
     430                 :             : 
     431                 :        9153 :       node = stack;
     432                 :        9153 :       stack = stack->back;
     433                 :             : 
     434                 :        9153 :       val = (*fn) (node->key, node->value, data);
     435                 :        9153 :       if (val)
     436                 :             :         break;
     437                 :             : 
     438                 :        9153 :       node = node->right;
     439                 :             :     }
     440                 :             : 
     441                 :        9145 :   return val;
     442                 :             : }
     443                 :             : 
     444                 :             : /* Insert a new node (associating KEY with DATA) into SP.  If a
     445                 :             :    previous node with the indicated KEY exists, its data is replaced
     446                 :             :    with the new value.  Returns the new node.  */
     447                 :             : 
     448                 :             : template <typename KEY_TYPE, typename VALUE_TYPE>
     449                 :             : typename typed_splay_tree<KEY_TYPE, VALUE_TYPE>::splay_tree_node
     450                 :       24168 : typed_splay_tree<KEY_TYPE, VALUE_TYPE>::splay_tree_insert (
     451                 :             :                                                 splay_tree_key key,
     452                 :             :                                                 splay_tree_value value)
     453                 :             : {
     454                 :       24168 :   int comparison = 0;
     455                 :             : 
     456                 :       24168 :   splay_tree_splay (key);
     457                 :             : 
     458                 :       24168 :   if (root)
     459                 :         413 :     comparison = (*comp)(root->key, key);
     460                 :             : 
     461                 :       24168 :   if (root && comparison == 0)
     462                 :             :     {
     463                 :             :       /* If the root of the tree already has the indicated KEY, just
     464                 :             :          replace the value with VALUE.  */
     465                 :           0 :       VDEL(root->value);
     466                 :           0 :       root->value = value;
     467                 :             :     }
     468                 :             :   else
     469                 :             :     {
     470                 :             :       /* Create a new node, and insert it at the root.  */
     471                 :             :       splay_tree_node node;
     472                 :             : 
     473                 :       24168 :       node = new splay_tree_node_s;
     474                 :       24168 :       node->key = key;
     475                 :       24168 :       node->value = value;
     476                 :             : 
     477                 :       24168 :       if (!root)
     478                 :       23755 :         node->left = node->right = 0;
     479                 :         413 :       else if (comparison < 0)
     480                 :             :         {
     481                 :         393 :           node->left = root;
     482                 :         393 :           node->right = node->left->right;
     483                 :         393 :           node->left->right = 0;
     484                 :             :         }
     485                 :             :       else
     486                 :             :         {
     487                 :          20 :           node->right = root;
     488                 :          20 :           node->left = node->right->left;
     489                 :          20 :           node->right->left = 0;
     490                 :             :         }
     491                 :             : 
     492                 :       24168 :       root = node;
     493                 :             :     }
     494                 :             : 
     495                 :       24168 :   return root;
     496                 :             : }
     497                 :             : 
     498                 :             : /* Remove KEY from SP.  It is not an error if it did not exist.  */
     499                 :             : 
     500                 :             : template <typename KEY_TYPE, typename VALUE_TYPE>
     501                 :             : void
     502                 :           4 : typed_splay_tree<KEY_TYPE, VALUE_TYPE>::splay_tree_remove (splay_tree_key key)
     503                 :             : {
     504                 :           4 :   splay_tree_splay (key);
     505                 :             : 
     506                 :           4 :   if (root && (*comp) (root->key, key) == 0)
     507                 :             :     {
     508                 :             :       splay_tree_node left, right;
     509                 :             : 
     510                 :           4 :       left = root->left;
     511                 :           4 :       right = root->right;
     512                 :             : 
     513                 :             :       /* Delete the root node itself.  */
     514                 :           4 :       VDEL (root->value);
     515                 :           4 :       delete root;
     516                 :             : 
     517                 :             :       /* One of the children is now the root.  Doesn't matter much
     518                 :             :          which, so long as we preserve the properties of the tree.  */
     519                 :           4 :       if (left)
     520                 :             :         {
     521                 :           4 :           root = left;
     522                 :             : 
     523                 :             :           /* If there was a right child as well, hang it off the
     524                 :             :              right-most leaf of the left child.  */
     525                 :           4 :           if (right)
     526                 :             :             {
     527                 :           0 :               while (left->right)
     528                 :             :                 left = left->right;
     529                 :           0 :               left->right = right;
     530                 :             :             }
     531                 :             :         }
     532                 :             :       else
     533                 :           0 :         root = right;
     534                 :             :     }
     535                 :           4 : }
     536                 :             : 
     537                 :             : /* Lookup KEY in SP, returning VALUE if present, and NULL
     538                 :             :    otherwise.  */
     539                 :             : 
     540                 :             : template <typename KEY_TYPE, typename VALUE_TYPE>
     541                 :             : typename typed_splay_tree<KEY_TYPE, VALUE_TYPE>::splay_tree_node
     542                 :       91088 : typed_splay_tree<KEY_TYPE, VALUE_TYPE>::splay_tree_lookup (splay_tree_key key)
     543                 :             : {
     544                 :       91088 :   splay_tree_splay (key);
     545                 :             : 
     546                 :       91088 :   if (root && (*comp)(root->key, key) == 0)
     547                 :       51771 :     return root;
     548                 :             :   else
     549                 :       39317 :     return 0;
     550                 :             : }
     551                 :             : 
     552                 :             : /* Return the node in SP with the greatest key.  */
     553                 :             : 
     554                 :             : template <typename KEY_TYPE, typename VALUE_TYPE>
     555                 :             : typename typed_splay_tree<KEY_TYPE, VALUE_TYPE>::splay_tree_node
     556                 :           4 : typed_splay_tree<KEY_TYPE, VALUE_TYPE>::splay_tree_max ()
     557                 :             : {
     558                 :           4 :   splay_tree_node n = root;
     559                 :             : 
     560                 :             :   if (!n)
     561                 :             :     return NULL;
     562                 :             : 
     563                 :           8 :   while (n->right)
     564                 :             :     n = n->right;
     565                 :             : 
     566                 :             :   return n;
     567                 :             : }
     568                 :             : 
     569                 :             : /* Return the node in SP with the smallest key.  */
     570                 :             : 
     571                 :             : template <typename KEY_TYPE, typename VALUE_TYPE>
     572                 :             : typename typed_splay_tree<KEY_TYPE, VALUE_TYPE>::splay_tree_node
     573                 :        9145 : typed_splay_tree<KEY_TYPE, VALUE_TYPE>::splay_tree_min ()
     574                 :             : {
     575                 :        9145 :   splay_tree_node n = root;
     576                 :             : 
     577                 :        9145 :   if (!n)
     578                 :             :     return NULL;
     579                 :             : 
     580                 :        9490 :   while (n->left)
     581                 :             :     n = n->left;
     582                 :             : 
     583                 :             :   return n;
     584                 :             : }
     585                 :             : 
     586                 :             : /* Return the immediate predecessor KEY, or NULL if there is no
     587                 :             :    predecessor.  KEY need not be present in the tree.  */
     588                 :             : 
     589                 :             : template <typename KEY_TYPE, typename VALUE_TYPE>
     590                 :             : typename typed_splay_tree<KEY_TYPE, VALUE_TYPE>::splay_tree_node
     591                 :          94 : typed_splay_tree<KEY_TYPE,
     592                 :             :                  VALUE_TYPE>::splay_tree_predecessor (splay_tree_key key)
     593                 :             : {
     594                 :             :   int comparison;
     595                 :             :   splay_tree_node node;
     596                 :             : 
     597                 :             :   /* If the tree is empty, there is certainly no predecessor.  */
     598                 :          94 :   if (!root)
     599                 :             :     return NULL;
     600                 :             : 
     601                 :             :   /* Splay the tree around KEY.  That will leave either the KEY
     602                 :             :      itself, its predecessor, or its successor at the root.  */
     603                 :          69 :   splay_tree_splay (key);
     604                 :          69 :   comparison = (*comp)(root->key, key);
     605                 :             : 
     606                 :             :   /* If the predecessor is at the root, just return it.  */
     607                 :          69 :   if (comparison < 0)
     608                 :          45 :     return root;
     609                 :             : 
     610                 :             :   /* Otherwise, find the rightmost element of the left subtree.  */
     611                 :          24 :   node = root->left;
     612                 :          24 :   if (node)
     613                 :           4 :     while (node->right)
     614                 :             :       node = node->right;
     615                 :             : 
     616                 :             :   return node;
     617                 :             : }
     618                 :             : 
     619                 :             : /* Return the immediate successor KEY, or NULL if there is no
     620                 :             :    successor.  KEY need not be present in the tree.  */
     621                 :             : 
     622                 :             : template <typename KEY_TYPE, typename VALUE_TYPE>
     623                 :             : typename typed_splay_tree<KEY_TYPE, VALUE_TYPE>::splay_tree_node
     624                 :       18778 : typed_splay_tree<KEY_TYPE,
     625                 :             :                  VALUE_TYPE>::splay_tree_successor (splay_tree_key key)
     626                 :             : {
     627                 :             :   int comparison;
     628                 :             :   splay_tree_node node;
     629                 :             : 
     630                 :             :   /* If the tree is empty, there is certainly no successor.  */
     631                 :       18778 :   if (!root)
     632                 :             :     return NULL;
     633                 :             : 
     634                 :             :   /* Splay the tree around KEY.  That will leave either the KEY
     635                 :             :      itself, its predecessor, or its successor at the root.  */
     636                 :       18753 :   splay_tree_splay (key);
     637                 :       18753 :   comparison = (*comp)(root->key, key);
     638                 :             : 
     639                 :             :   /* If the successor is at the root, just return it.  */
     640                 :       18753 :   if (comparison > 0)
     641                 :          20 :     return root;
     642                 :             : 
     643                 :             :   /* Otherwise, find the leftmost element of the right subtree.  */
     644                 :       18733 :   node = root->right;
     645                 :       18733 :   if (node)
     646                 :         576 :     while (node->left)
     647                 :             :       node = node->left;
     648                 :             : 
     649                 :             :   return node;
     650                 :             : }
     651                 :             : 
     652                 :             : #endif  /* GCC_TYPED_SPLAY_TREE_H  */
        

Generated by: LCOV version 2.1-beta

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.