gcc/typed-splay-tree.h

   1 /* A typesafe wrapper around libiberty's splay-tree.h.
   2    Copyright (C) 2015-2018 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 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   root = NULL;
 116   comp = compare_fn;
 117   delete_key = delete_key_fn;
 118   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 inline typed_splay_tree<KEY_TYPE, VALUE_TYPE>::
 125   ~typed_splay_tree ()
 126 {
 127   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 typed_splay_tree<KEY_TYPE, VALUE_TYPE>::lookup (key_type key)
 136 {
 137   splay_tree_node node = splay_tree_lookup (key);
 138   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 typed_splay_tree<KEY_TYPE, VALUE_TYPE>::predecessor (key_type key)
 147 {
 148   splay_tree_node node = splay_tree_predecessor (key);
 149   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 typed_splay_tree<KEY_TYPE, VALUE_TYPE>::successor (key_type key)
 158 {
 159   splay_tree_node node = splay_tree_successor (key);
 160   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 typed_splay_tree<KEY_TYPE, VALUE_TYPE>::insert (key_type key,
 170                                                 value_type value)
 171 {
 172   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 typed_splay_tree<KEY_TYPE, VALUE_TYPE>::remove (key_type key)
 180 {
 181   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 typed_splay_tree<KEY_TYPE, VALUE_TYPE>::max ()
 189 {
 190   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 typed_splay_tree<KEY_TYPE, VALUE_TYPE>::min ()
 198 {
 199   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 typed_splay_tree<KEY_TYPE, VALUE_TYPE>::node_to_value (splay_tree_node node)
 220 {
 221   if (node)
 222     return node->value;
 223   else
 224     return 0;
 225 }
 226
 227 template <typename KEY_TYPE, typename VALUE_TYPE>
 228 inline void
 229 typed_splay_tree<KEY_TYPE, VALUE_TYPE>::KDEL(splay_tree_key x)
 230 {
 231   if (delete_key)
 232     (*delete_key)(x);
 233 }
 234
 235 template <typename KEY_TYPE, typename VALUE_TYPE>
 236 inline void
 237 typed_splay_tree<KEY_TYPE, VALUE_TYPE>::VDEL(splay_tree_value x)
 238 {
 239   if (delete_value)
 240     (*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 typed_splay_tree<KEY_TYPE,
 248                  VALUE_TYPE>::splay_tree_delete_helper (splay_tree_node node)
 249 {
 250   splay_tree_node pending = NULL;
 251   splay_tree_node active = NULL;
 252
 253   if (!node)
 254     return;
 255
 256   KDEL (node->key);
 257   VDEL (node->value);
 258
 259   /* We use the "back" field to hold the "next" pointer.  */
 260   node->back = pending;
 261   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   while (pending)
 268     {
 269       active = pending;
 270       pending = NULL;
 271       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           if (active->left)
 279             {
 280               KDEL (active->left->key);
 281               VDEL (active->left->value);
 282               active->left->back = pending;
 283               pending = active->left;
 284             }
 285           if (active->right)
 286             {
 287               KDEL (active->right->key);
 288               VDEL (active->right->value);
 289               active->right->back = pending;
 290               pending = active->right;
 291             }
 292
 293           temp = active;
 294           active = temp->back;
 295           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 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   tmp = n->right;
 311   n->right = p;
 312   p->left = tmp;
 313   *pp = n;
 314 }
 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 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   tmp = n->left;
 327   n->left = p;
 328   p->right = tmp;
 329   *pp = n;
 330 }
 331
 332 /* Bottom up splay of key.  */
 333
 334 template <typename KEY_TYPE, typename VALUE_TYPE>
 335 void
 336 typed_splay_tree<KEY_TYPE, VALUE_TYPE>::splay_tree_splay (splay_tree_key key)
 337 {
 338   if (root == NULL)
 339     return;
 340
 341   do {
 342     int cmp1, cmp2;
 343     splay_tree_node n, c;
 344
 345     n = root;
 346     cmp1 = (*comp) (key, n->key);
 347
 348     /* Found.  */
 349     if (cmp1 == 0)
 350       return;
 351
 352     /* Left or right?  If no child, then we're done.  */
 353     if (cmp1 < 0)
 354       c = n->left;
 355     else
 356       c = n->right;
 357     if (!c)
 358       return;
 359
 360     /* Next one left or right?  If found or no child, we're done
 361        after one rotation.  */
 362     cmp2 = (*comp) (key, c->key);
 363     if (cmp2 == 0
 364         || (cmp2 < 0 && !c->left)
 365         || (cmp2 > 0 && !c->right))
 366       {
 367         if (cmp1 < 0)
 368           rotate_left (&root, n, c);
 369         else
 370           rotate_right (&root, n, c);
 371         return;
 372       }
 373
 374     /* Now we have the four cases of double-rotation.  */
 375     if (cmp1 < 0 && cmp2 < 0)
 376       {
 377         rotate_left (&n->left, c, c->left);
 378         rotate_left (&root, n, n->left);
 379       }
 380     else if (cmp1 > 0 && cmp2 > 0)
 381       {
 382         rotate_right (&n->right, c, c->right);
 383         rotate_right (&root, n, n->right);
 384       }
 385     else if (cmp1 < 0 && cmp2 > 0)
 386       {
 387         rotate_right (&n->left, c, c->right);
 388         rotate_left (&root, n, n->left);
 389       }
 390     else if (cmp1 > 0 && cmp2 < 0)
 391       {
 392         rotate_left (&n->right, c, c->left);
 393         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 typed_splay_tree<KEY_TYPE, VALUE_TYPE>::splay_tree_insert (
 451                                                 splay_tree_key key,
 452                                                 splay_tree_value value)
 453 {
 454   int comparison = 0;
 455
 456   splay_tree_splay (key);
 457
 458   if (root)
 459     comparison = (*comp)(root->key, key);
 460
 461   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       VDEL(root->value);
 466       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       node = new splay_tree_node_s;
 474       node->key = key;
 475       node->value = value;
 476
 477       if (!root)
 478         node->left = node->right = 0;
 479       else if (comparison < 0)
 480         {
 481           node->left = root;
 482           node->right = node->left->right;
 483           node->left->right = 0;
 484         }
 485       else
 486         {
 487           node->right = root;
 488           node->left = node->right->left;
 489           node->right->left = 0;
 490         }
 491
 492       root = node;
 493     }
 494
 495   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 typed_splay_tree<KEY_TYPE, VALUE_TYPE>::splay_tree_remove (splay_tree_key key)
 503 {
 504   splay_tree_splay (key);
 505
 506   if (root && (*comp) (root->key, key) == 0)
 507     {
 508       splay_tree_node left, right;
 509
 510       left = root->left;
 511       right = root->right;
 512
 513       /* Delete the root node itself.  */
 514       VDEL (root->value);
 515       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       if (left)
 520         {
 521           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           if (right)
 526             {
 527               while (left->right)
 528                 left = left->right;
 529               left->right = right;
 530             }
 531         }
 532       else
 533         root = right;
 534     }
 535 }
 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 typed_splay_tree<KEY_TYPE, VALUE_TYPE>::splay_tree_lookup (splay_tree_key key)
 543 {
 544   splay_tree_splay (key);
 545
 546   if (root && (*comp)(root->key, key) == 0)
 547     return root;
 548   else
 549     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 typed_splay_tree<KEY_TYPE, VALUE_TYPE>::splay_tree_max ()
 557 {
 558   splay_tree_node n = root;
 559
 560   if (!n)
 561     return NULL;
 562
 563   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 typed_splay_tree<KEY_TYPE, VALUE_TYPE>::splay_tree_min ()
 574 {
 575   splay_tree_node n = root;
 576
 577   if (!n)
 578     return NULL;
 579
 580   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 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   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   splay_tree_splay (key);
 604   comparison = (*comp)(root->key, key);
 605
 606   /* If the predecessor is at the root, just return it.  */
 607   if (comparison < 0)
 608     return root;
 609
 610   /* Otherwise, find the rightmost element of the left subtree.  */
 611   node = root->left;
 612   if (node)
 613     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 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   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   splay_tree_splay (key);
 637   comparison = (*comp)(root->key, key);
 638
 639   /* If the successor is at the root, just return it.  */
 640   if (comparison > 0)
 641     return root;
 642
 643   /* Otherwise, find the leftmost element of the right subtree.  */
 644   node = root->right;
 645   if (node)
 646     while (node->left)
 647       node = node->left;
 648
 649   return node;
 650 }
 651
 652 #endif  /* GCC_TYPED_SPLAY_TREE_H  */