LCOV - code coverage report
Current view: top level - gcc - typed-splay-tree.h (source / functions) Hit Total Coverage
Test: gcc.info Lines: 155 164 94.5 %
Date: 2020-03-28 11:57:23 Functions: 22 22 100.0 %
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-2020 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                 :      84466 : 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                 :      84466 :   root = NULL;
     116                 :      84466 :   comp = compare_fn;
     117                 :      84466 :   delete_key = delete_key_fn;
     118                 :      84466 :   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                 :      12466 : inline typed_splay_tree<KEY_TYPE, VALUE_TYPE>::
     125                 :            :   ~typed_splay_tree ()
     126                 :            : {
     127                 :      12466 :   splay_tree_delete_helper (root);
     128                 :            : }
     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                 :      81932 : typed_splay_tree<KEY_TYPE, VALUE_TYPE>::lookup (key_type key)
     136                 :            : {
     137                 :      81932 :   splay_tree_node node = splay_tree_lookup (key);
     138                 :      81926 :   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                 :         92 : typed_splay_tree<KEY_TYPE, VALUE_TYPE>::predecessor (key_type key)
     147                 :            : {
     148                 :         92 :   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                 :      17766 : typed_splay_tree<KEY_TYPE, VALUE_TYPE>::successor (key_type key)
     158                 :            : {
     159                 :      17766 :   splay_tree_node node = splay_tree_successor (key);
     160                 :      26358 :   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                 :      23032 : typed_splay_tree<KEY_TYPE, VALUE_TYPE>::insert (key_type key,
     170                 :            :                                                 value_type value)
     171                 :            : {
     172                 :      23026 :   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                 :          2 : typed_splay_tree<KEY_TYPE, VALUE_TYPE>::remove (key_type key)
     180                 :            : {
     181                 :          2 :   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                 :          2 : typed_splay_tree<KEY_TYPE, VALUE_TYPE>::max ()
     189                 :            : {
     190                 :          0 :   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                 :       8736 : typed_splay_tree<KEY_TYPE, VALUE_TYPE>::min ()
     198                 :            : {
     199                 :       8734 :   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                 :            : typed_splay_tree<KEY_TYPE, VALUE_TYPE>::foreach (foreach_fn foreach_fn,
     210                 :            :                                                  void *user_data)
     211                 :            : {
     212                 :            :   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                 :     108528 : typed_splay_tree<KEY_TYPE, VALUE_TYPE>::node_to_value (splay_tree_node node)
     220                 :            : {
     221                 :      99790 :   if (node)
     222                 :      55737 :     return node->value;
     223                 :            :   else
     224                 :            :     return 0;
     225                 :            : }
     226                 :            : 
     227                 :            : template <typename KEY_TYPE, typename VALUE_TYPE>
     228                 :            : inline void
     229                 :      23030 : typed_splay_tree<KEY_TYPE, VALUE_TYPE>::KDEL(splay_tree_key x)
     230                 :            : {
     231                 :      23030 :   if (delete_key)
     232                 :          0 :     (*delete_key)(x);
     233                 :            : }
     234                 :            : 
     235                 :            : template <typename KEY_TYPE, typename VALUE_TYPE>
     236                 :            : inline void
     237                 :      23032 : typed_splay_tree<KEY_TYPE, VALUE_TYPE>::VDEL(splay_tree_value x)
     238                 :            : {
     239                 :      23032 :   if (delete_value)
     240                 :      22939 :     (*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                 :      84466 : typed_splay_tree<KEY_TYPE,
     248                 :            :                  VALUE_TYPE>::splay_tree_delete_helper (splay_tree_node node)
     249                 :            : {
     250                 :      84466 :   splay_tree_node pending = NULL;
     251                 :      84466 :   splay_tree_node active = NULL;
     252                 :            : 
     253                 :      84466 :   if (!node)
     254                 :            :     return;
     255                 :            : 
     256                 :      22793 :   KDEL (node->key);
     257                 :      22793 :   VDEL (node->value);
     258                 :            : 
     259                 :            :   /* We use the "back" field to hold the "next" pointer.  */
     260                 :      22793 :   node->back = pending;
     261                 :      22793 :   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                 :      45821 :   while (pending)
     268                 :            :     {
     269                 :            :       active = pending;
     270                 :            :       pending = NULL;
     271                 :      46058 :       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                 :      23030 :           if (active->left)
     279                 :            :             {
     280                 :        215 :               KDEL (active->left->key);
     281                 :        215 :               VDEL (active->left->value);
     282                 :        215 :               active->left->back = pending;
     283                 :        215 :               pending = active->left;
     284                 :            :             }
     285                 :      23030 :           if (active->right)
     286                 :            :             {
     287                 :         22 :               KDEL (active->right->key);
     288                 :         22 :               VDEL (active->right->value);
     289                 :         22 :               active->right->back = pending;
     290                 :         22 :               pending = active->right;
     291                 :            :             }
     292                 :            : 
     293                 :      23030 :           temp = active;
     294                 :      23030 :           active = temp->back;
     295                 :      23030 :           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                 :        974 : 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                 :        974 :   tmp = n->right;
     311                 :        974 :   n->right = p;
     312                 :        974 :   p->left = tmp;
     313                 :        974 :   *pp = n;
     314                 :        659 : }
     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                 :        972 : 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                 :        972 :   tmp = n->left;
     327                 :        972 :   n->left = p;
     328                 :        972 :   p->right = tmp;
     329                 :        972 :   *pp = n;
     330                 :        972 : }
     331                 :            : 
     332                 :            : /* Bottom up splay of key.  */
     333                 :            : 
     334                 :            : template <typename KEY_TYPE, typename VALUE_TYPE>
     335                 :            : void
     336                 :     122774 : typed_splay_tree<KEY_TYPE, VALUE_TYPE>::splay_tree_splay (splay_tree_key key)
     337                 :            : {
     338                 :     122774 :   if (root == NULL)
     339                 :            :     return;
     340                 :            : 
     341                 :            :   do {
     342                 :            :     int cmp1, cmp2;
     343                 :            :     splay_tree_node n, c;
     344                 :            : 
     345                 :      77128 :     n = root;
     346                 :     154256 :     cmp1 = (*comp) (key, n->key);
     347                 :            : 
     348                 :            :     /* Found.  */
     349                 :      77128 :     if (cmp1 == 0)
     350                 :            :       return;
     351                 :            : 
     352                 :            :     /* Left or right?  If no child, then we're done.  */
     353                 :      13173 :     if (cmp1 < 0)
     354                 :       1772 :       c = n->left;
     355                 :            :     else
     356                 :      11401 :       c = n->right;
     357                 :      13173 :     if (!c)
     358                 :            :       return;
     359                 :            : 
     360                 :            :     /* Next one left or right?  If found or no child, we're done
     361                 :            :        after one rotation.  */
     362                 :       1631 :     cmp2 = (*comp) (key, c->key);
     363                 :       1631 :     if (cmp2 == 0
     364                 :       1182 :         || (cmp2 < 0 && !c->left)
     365                 :        849 :         || (cmp2 > 0 && !c->right))
     366                 :            :       {
     367                 :        981 :         if (cmp1 < 0)
     368                 :        344 :           rotate_left (&root, n, c);
     369                 :            :         else
     370                 :        637 :           rotate_right (&root, n, c);
     371                 :        981 :         return;
     372                 :            :       }
     373                 :            : 
     374                 :            :     /* Now we have the four cases of double-rotation.  */
     375                 :        650 :     if (cmp1 < 0 && cmp2 < 0)
     376                 :            :       {
     377                 :        315 :         rotate_left (&n->left, c, c->left);
     378                 :        315 :         rotate_left (&root, n, n->left);
     379                 :            :       }
     380                 :        335 :     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                 :        315 :     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                 :        315 :     else if (cmp1 > 0 && cmp2 < 0)
     391                 :            :       {
     392                 :        315 :         rotate_left (&n->right, c, c->left);
     393                 :      77443 :         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                 :            : 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                 :            :   stack = NULL;
     417                 :            :   val = 0;
     418                 :            : 
     419                 :            :   for (;;)
     420                 :            :     {
     421                 :            :       while (node != NULL)
     422                 :            :         {
     423                 :            :           node->back = stack;
     424                 :            :           stack = node;
     425                 :            :           node = node->left;
     426                 :            :         }
     427                 :            : 
     428                 :            :       if (stack == NULL)
     429                 :            :         break;
     430                 :            : 
     431                 :            :       node = stack;
     432                 :            :       stack = stack->back;
     433                 :            : 
     434                 :            :       val = (*fn) (node->key, node->value, data);
     435                 :            :       if (val)
     436                 :            :         break;
     437                 :            : 
     438                 :            :       node = node->right;
     439                 :            :     }
     440                 :            : 
     441                 :            :   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                 :      23032 : typed_splay_tree<KEY_TYPE, VALUE_TYPE>::splay_tree_insert (
     451                 :            :                                                 splay_tree_key key,
     452                 :            :                                                 splay_tree_value value)
     453                 :            : {
     454                 :      23032 :   int comparison = 0;
     455                 :            : 
     456                 :      23032 :   splay_tree_splay (key);
     457                 :            : 
     458                 :      23032 :   if (root)
     459                 :        239 :     comparison = (*comp)(root->key, key);
     460                 :            : 
     461                 :      23032 :   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                 :      23032 :       node = new splay_tree_node_s;
     474                 :      23032 :       node->key = key;
     475                 :      23032 :       node->value = value;
     476                 :            : 
     477                 :      23032 :       if (!root)
     478                 :      22793 :         node->left = node->right = 0;
     479                 :        239 :       else if (comparison < 0)
     480                 :            :         {
     481                 :        219 :           node->left = root;
     482                 :        219 :           node->right = node->left->right;
     483                 :        219 :           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                 :      23032 :       root = node;
     493                 :            :     }
     494                 :            : 
     495                 :      23032 :   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                 :          2 : typed_splay_tree<KEY_TYPE, VALUE_TYPE>::splay_tree_remove (splay_tree_key key)
     503                 :            : {
     504                 :          2 :   splay_tree_splay (key);
     505                 :            : 
     506                 :          2 :   if (root && (*comp) (root->key, key) == 0)
     507                 :            :     {
     508                 :            :       splay_tree_node left, right;
     509                 :            : 
     510                 :          2 :       left = root->left;
     511                 :          2 :       right = root->right;
     512                 :            : 
     513                 :            :       /* Delete the root node itself.  */
     514                 :          2 :       VDEL (root->value);
     515                 :          2 :       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                 :          2 :       if (left)
     520                 :            :         {
     521                 :          2 :           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                 :          2 :           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                 :          2 : }
     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                 :      81932 : typed_splay_tree<KEY_TYPE, VALUE_TYPE>::splay_tree_lookup (splay_tree_key key)
     543                 :            : {
     544                 :      81932 :   splay_tree_splay (key);
     545                 :            : 
     546                 :      81932 :   if (root && (*comp)(root->key, key) == 0)
     547                 :      46724 :     return root;
     548                 :            :   else
     549                 :      35208 :     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                 :          2 : typed_splay_tree<KEY_TYPE, VALUE_TYPE>::splay_tree_max ()
     557                 :            : {
     558                 :          2 :   splay_tree_node n = root;
     559                 :            : 
     560                 :          2 :   if (!n)
     561                 :            :     return NULL;
     562                 :            : 
     563                 :          4 :   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                 :       8736 : typed_splay_tree<KEY_TYPE, VALUE_TYPE>::splay_tree_min ()
     574                 :            : {
     575                 :       8736 :   splay_tree_node n = root;
     576                 :            : 
     577                 :       8736 :   if (!n)
     578                 :            :     return NULL;
     579                 :            : 
     580                 :       8911 :   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                 :         92 : 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                 :         92 :   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                 :         67 :   splay_tree_splay (key);
     604                 :         67 :   comparison = (*comp)(root->key, key);
     605                 :            : 
     606                 :            :   /* If the predecessor is at the root, just return it.  */
     607                 :         67 :   if (comparison < 0)
     608                 :         45 :     return root;
     609                 :            : 
     610                 :            :   /* Otherwise, find the rightmost element of the left subtree.  */
     611                 :         22 :   node = root->left;
     612                 :         22 :   if (node)
     613                 :          2 :     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                 :      17766 : 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                 :      17766 :   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                 :      17741 :   splay_tree_splay (key);
     637                 :      17741 :   comparison = (*comp)(root->key, key);
     638                 :            : 
     639                 :            :   /* If the successor is at the root, just return it.  */
     640                 :      17741 :   if (comparison > 0)
     641                 :         20 :     return root;
     642                 :            : 
     643                 :            :   /* Otherwise, find the leftmost element of the right subtree.  */
     644                 :      17721 :   node = root->right;
     645                 :      17721 :   if (node)
     646                 :        294 :     while (node->left)
     647                 :            :       node = node->left;
     648                 :            : 
     649                 :            :   return node;
     650                 :            : }
     651                 :            : 
     652                 :            : #endif  /* GCC_TYPED_SPLAY_TREE_H  */

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.