lib/gl_anytree_list2.h

   1 /* Sequential list data type implemented by a binary tree.
   2    Copyright (C) 2006 Free Software Foundation, Inc.
   3    Written by Bruno Haible <bruno@clisp.org>, 2006.
   4
   5    This program is free software; you can redistribute it and/or modify
   6    it under the terms of the GNU General Public License as published by
   7    the Free Software Foundation; either version 2, or (at your option)
   8    any later version.
   9
  10    This program is distributed in the hope that it will be useful,
  11    but WITHOUT ANY WARRANTY; without even the implied warranty of
  12    MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  13    GNU General Public License for more details.
  14
  15    You should have received a copy of the GNU General Public License
  16    along with this program; if not, write to the Free Software Foundation,
  17    Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301, USA.  */
  18
  19 /* Common code of gl_avltree_list.c, gl_rbtree_list.c,
  20                   gl_avltreehash_list.c, gl_rbtreehash_list.c.  */
  21
  22 static gl_list_t
  23 gl_tree_create_empty (gl_list_implementation_t implementation,
  24                       gl_listelement_equals_fn equals_fn,
  25                       gl_listelement_hashcode_fn hashcode_fn,
  26                       bool allow_duplicates)
  27 {
  28   struct gl_list_impl *list =
  29     (struct gl_list_impl *) xmalloc (sizeof (struct gl_list_impl));
  30
  31   list->base.vtable = implementation;
  32   list->base.equals_fn = equals_fn;
  33   list->base.hashcode_fn = hashcode_fn;
  34   list->base.allow_duplicates = allow_duplicates;
  35 #if WITH_HASHTABLE
  36   list->table_size = 11;
  37   list->table =
  38     (gl_hash_entry_t *) xzalloc (list->table_size * sizeof (gl_hash_entry_t));
  39 #endif
  40   list->root = NULL;
  41
  42   return list;
  43 }
  44
  45 static size_t
  46 gl_tree_size (gl_list_t list)
  47 {
  48   return (list->root != NULL ? list->root->branch_size : 0);
  49 }
  50
  51 static const void *
  52 gl_tree_node_value (gl_list_t list, gl_list_node_t node)
  53 {
  54   return node->value;
  55 }
  56
  57 static gl_list_node_t
  58 gl_tree_next_node (gl_list_t list, gl_list_node_t node)
  59 {
  60   if (node->right != NULL)
  61     {
  62       node = node->right;
  63       while (node->left != NULL)
  64         node = node->left;
  65     }
  66   else
  67     {
  68       while (node->parent != NULL && node->parent->right == node)
  69         node = node->parent;
  70       node = node->parent;
  71     }
  72   return node;
  73 }
  74
  75 static gl_list_node_t
  76 gl_tree_previous_node (gl_list_t list, gl_list_node_t node)
  77 {
  78   if (node->left != NULL)
  79     {
  80       node = node->left;
  81       while (node->right != NULL)
  82         node = node->right;
  83     }
  84   else
  85     {
  86       while (node->parent != NULL && node->parent->left == node)
  87         node = node->parent;
  88       node = node->parent;
  89     }
  90   return node;
  91 }
  92
  93 /* Return the node at the given position < gl_tree_size (list).  */
  94 static inline gl_list_node_t
  95 node_at (gl_list_node_t root, size_t position)
  96 {
  97   /* Here we know that root != NULL.  */
  98   gl_list_node_t node = root;
  99
 100   for (;;)
 101     {
 102       if (node->left != NULL)
 103         {
 104           if (position < node->left->branch_size)
 105             {
 106               node = node->left;
 107               continue;
 108             }
 109           position -= node->left->branch_size;
 110         }
 111       if (position == 0)
 112         break;
 113       position--;
 114       node = node->right;
 115     }
 116   return node;
 117 }
 118
 119 static const void *
 120 gl_tree_get_at (gl_list_t list, size_t position)
 121 {
 122   gl_list_node_t node = list->root;
 123
 124   if (!(node != NULL && position < node->branch_size))
 125     /* Invalid argument.  */
 126     abort ();
 127   node = node_at (node, position);
 128   return node->value;
 129 }
 130
 131 static gl_list_node_t
 132 gl_tree_set_at (gl_list_t list, size_t position, const void *elt)
 133 {
 134   gl_list_node_t node = list->root;
 135
 136   if (!(node != NULL && position < node->branch_size))
 137     /* Invalid argument.  */
 138     abort ();
 139   node = node_at (node, position);
 140 #if WITH_HASHTABLE
 141   if (elt != node->value)
 142     {
 143       size_t new_hashcode =
 144         (list->base.hashcode_fn != NULL
 145          ? list->base.hashcode_fn (elt)
 146          : (size_t)(uintptr_t) elt);
 147
 148       if (new_hashcode != node->h.hashcode)
 149         {
 150           remove_from_bucket (list, node);
 151           node->value = elt;
 152           node->h.hashcode = new_hashcode;
 153           add_to_bucket (list, node);
 154         }
 155       else
 156         node->value = elt;
 157     }
 158 #else
 159   node->value = elt;
 160 #endif
 161   return node;
 162 }
 163
 164 #if !WITH_HASHTABLE
 165
 166 static gl_list_node_t
 167 gl_tree_search_from_to (gl_list_t list, size_t start_index, size_t end_index,
 168                         const void *elt)
 169 {
 170   if (!(start_index <= end_index
 171         && end_index <= (list->root != NULL ? list->root->branch_size : 0)))
 172     /* Invalid arguments.  */
 173     abort ();
 174   {
 175     gl_listelement_equals_fn equals = list->base.equals_fn;
 176     /* Iterate across all elements.  */
 177     gl_list_node_t node = list->root;
 178     iterstack_t stack;
 179     iterstack_item_t *stack_ptr = &stack[0];
 180     size_t index = 0;
 181
 182     if (start_index == 0)
 183       {
 184         /* Consider all elements.  */
 185         for (;;)
 186           {
 187             /* Descend on left branch.  */
 188             for (;;)
 189               {
 190                 if (node == NULL)
 191                   break;
 192                 stack_ptr->node = node;
 193                 stack_ptr->rightp = 0;
 194                 node = node->left;
 195                 stack_ptr++;
 196               }
 197             /* Climb up again.  */
 198             for (;;)
 199               {
 200                 if (stack_ptr == &stack[0])
 201                   return NULL;
 202                 stack_ptr--;
 203                 if (!stack_ptr->rightp)
 204                   break;
 205               }
 206             node = stack_ptr->node;
 207             /* Test against current element.  */
 208             if (equals != NULL ? equals (elt, node->value) : elt == node->value)
 209               return node;
 210             index++;
 211             if (index >= end_index)
 212               return NULL;
 213             /* Descend on right branch.  */
 214             stack_ptr->rightp = 1;
 215             node = node->right;
 216             stack_ptr++;
 217           }
 218       }
 219     else
 220       {
 221         /* Consider only elements at indices >= start_index.
 222            In this case, rightp contains the difference between the start_index
 223            for the parent node and the one for the child node (0 when the child
 224            node is the parent's left child, > 0 when the child is the parent's
 225            right child).  */
 226         for (;;)
 227           {
 228             /* Descend on left branch.  */
 229             for (;;)
 230               {
 231                 if (node == NULL)
 232                   break;
 233                 if (node->branch_size <= start_index)
 234                   break;
 235                 stack_ptr->node = node;
 236                 stack_ptr->rightp = 0;
 237                 node = node->left;
 238                 stack_ptr++;
 239               }
 240             /* Climb up again.  */
 241             for (;;)
 242               {
 243                 if (stack_ptr == &stack[0])
 244                   return NULL;
 245                 stack_ptr--;
 246                 if (!stack_ptr->rightp)
 247                   break;
 248                 start_index += stack_ptr->rightp;
 249               }
 250             node = stack_ptr->node;
 251             {
 252               size_t left_branch_size1 =
 253                 (node->left != NULL ? node->left->branch_size : 0) + 1;
 254               if (start_index < left_branch_size1)
 255                 {
 256                   /* Test against current element.  */
 257                   if (equals != NULL ? equals (elt, node->value) : elt == node->value)
 258                     return node;
 259                   /* Now that we have considered all indices < left_branch_size1,
 260                      we can increment start_index.  */
 261                   start_index = left_branch_size1;
 262                 }
 263               index++;
 264               if (index >= end_index)
 265                 return NULL;
 266               /* Descend on right branch.  */
 267               start_index -= left_branch_size1;
 268               stack_ptr->rightp = left_branch_size1;
 269             }
 270             node = node->right;
 271             stack_ptr++;
 272           }
 273       }
 274   }
 275 }
 276
 277 static size_t
 278 gl_tree_indexof_from_to (gl_list_t list, size_t start_index, size_t end_index,
 279                          const void *elt)
 280 {
 281   if (!(start_index <= end_index
 282         && end_index <= (list->root != NULL ? list->root->branch_size : 0)))
 283     /* Invalid arguments.  */
 284     abort ();
 285   {
 286     gl_listelement_equals_fn equals = list->base.equals_fn;
 287     /* Iterate across all elements.  */
 288     gl_list_node_t node = list->root;
 289     iterstack_t stack;
 290     iterstack_item_t *stack_ptr = &stack[0];
 291     size_t index = 0;
 292
 293     if (start_index == 0)
 294       {
 295         /* Consider all elements.  */
 296         for (;;)
 297           {
 298             /* Descend on left branch.  */
 299             for (;;)
 300               {
 301                 if (node == NULL)
 302                   break;
 303                 stack_ptr->node = node;
 304                 stack_ptr->rightp = 0;
 305                 node = node->left;
 306                 stack_ptr++;
 307               }
 308             /* Climb up again.  */
 309             for (;;)
 310               {
 311                 if (stack_ptr == &stack[0])
 312                   return (size_t)(-1);
 313                 stack_ptr--;
 314                 if (!stack_ptr->rightp)
 315                   break;
 316               }
 317             node = stack_ptr->node;
 318             /* Test against current element.  */
 319             if (equals != NULL ? equals (elt, node->value) : elt == node->value)
 320               return index;
 321             index++;
 322             if (index >= end_index)
 323               return (size_t)(-1);
 324             /* Descend on right branch.  */
 325             stack_ptr->rightp = 1;
 326             node = node->right;
 327             stack_ptr++;
 328           }
 329       }
 330     else
 331       {
 332         /* Consider only elements at indices >= start_index.
 333            In this case, rightp contains the difference between the start_index
 334            for the parent node and the one for the child node (0 when the child
 335            node is the parent's left child, > 0 when the child is the parent's
 336            right child).  */
 337         for (;;)
 338           {
 339             /* Descend on left branch.  */
 340             for (;;)
 341               {
 342                 if (node == NULL)
 343                   break;
 344                 if (node->branch_size <= start_index)
 345                   break;
 346                 stack_ptr->node = node;
 347                 stack_ptr->rightp = 0;
 348                 node = node->left;
 349                 stack_ptr++;
 350               }
 351             /* Climb up again.  */
 352             for (;;)
 353               {
 354                 if (stack_ptr == &stack[0])
 355                   return (size_t)(-1);
 356                 stack_ptr--;
 357                 if (!stack_ptr->rightp)
 358                   break;
 359                 start_index += stack_ptr->rightp;
 360               }
 361             node = stack_ptr->node;
 362             {
 363               size_t left_branch_size1 =
 364                 (node->left != NULL ? node->left->branch_size : 0) + 1;
 365               if (start_index < left_branch_size1)
 366                 {
 367                   /* Test against current element.  */
 368                   if (equals != NULL ? equals (elt, node->value) : elt == node->value)
 369                     return index;
 370                   /* Now that we have considered all indices < left_branch_size1,
 371                      we can increment start_index.  */
 372                   start_index = left_branch_size1;
 373                 }
 374               index++;
 375               if (index >= end_index)
 376                 return (size_t)(-1);
 377               /* Descend on right branch.  */
 378               start_index -= left_branch_size1;
 379               stack_ptr->rightp = left_branch_size1;
 380             }
 381             node = node->right;
 382             stack_ptr++;
 383           }
 384       }
 385   }
 386 }
 387
 388 #endif
 389
 390 static gl_list_node_t
 391 gl_tree_add_at (gl_list_t list, size_t position, const void *elt)
 392 {
 393   size_t count = (list->root != NULL ? list->root->branch_size : 0);
 394
 395   if (!(position <= count))
 396     /* Invalid argument.  */
 397     abort ();
 398   if (position == count)
 399     return gl_tree_add_last (list, elt);
 400   else
 401     return gl_tree_add_before (list, node_at (list->root, position), elt);
 402 }
 403
 404 static bool
 405 gl_tree_remove_at (gl_list_t list, size_t position)
 406 {
 407   gl_list_node_t node = list->root;
 408
 409   if (!(node != NULL && position < node->branch_size))
 410     /* Invalid argument.  */
 411     abort ();
 412   node = node_at (node, position);
 413   return gl_tree_remove_node (list, node);
 414 }
 415
 416 static bool
 417 gl_tree_remove (gl_list_t list, const void *elt)
 418 {
 419   if (list->root != NULL)
 420     {
 421       gl_list_node_t node =
 422         gl_tree_search_from_to (list, 0, list->root->branch_size, elt);
 423
 424       if (node != NULL)
 425         return gl_tree_remove_node (list, node);
 426     }
 427   return false;
 428 }
 429
 430 #if !WITH_HASHTABLE
 431
 432 static void
 433 gl_tree_list_free (gl_list_t list)
 434 {
 435   /* Iterate across all elements in post-order.  */
 436   gl_list_node_t node = list->root;
 437   iterstack_t stack;
 438   iterstack_item_t *stack_ptr = &stack[0];
 439
 440   for (;;)
 441     {
 442       /* Descend on left branch.  */
 443       for (;;)
 444         {
 445           if (node == NULL)
 446             break;
 447           stack_ptr->node = node;
 448           stack_ptr->rightp = false;
 449           node = node->left;
 450           stack_ptr++;
 451         }
 452       /* Climb up again.  */
 453       for (;;)
 454         {
 455           if (stack_ptr == &stack[0])
 456             goto done_iterate;
 457           stack_ptr--;
 458           node = stack_ptr->node;
 459           if (!stack_ptr->rightp)
 460             break;
 461           /* Free the current node.  */
 462           free (node);
 463         }
 464       /* Descend on right branch.  */
 465       stack_ptr->rightp = true;
 466       node = node->right;
 467       stack_ptr++;
 468     }
 469  done_iterate:
 470   free (list);
 471 }
 472
 473 #endif
 474
 475 /* --------------------- gl_list_iterator_t Data Type --------------------- */
 476
 477 static gl_list_iterator_t
 478 gl_tree_iterator (gl_list_t list)
 479 {
 480   gl_list_iterator_t result;
 481   gl_list_node_t node;
 482
 483   result.vtable = list->base.vtable;
 484   result.list = list;
 485   /* Start node is the leftmost node.  */
 486   node = list->root;
 487   if (node != NULL)
 488     while (node->left != NULL)
 489       node = node->left;
 490   result.p = node;
 491   /* End point is past the rightmost node.  */
 492   result.q = NULL;
 493 #ifdef lint
 494   result.i = 0;
 495   result.j = 0;
 496   result.count = 0;
 497 #endif
 498
 499   return result;
 500 }
 501
 502 static gl_list_iterator_t
 503 gl_tree_iterator_from_to (gl_list_t list, size_t start_index, size_t end_index)
 504 {
 505   size_t count = (list->root != NULL ? list->root->branch_size : 0);
 506   gl_list_iterator_t result;
 507
 508   if (!(start_index <= end_index && end_index <= count))
 509     /* Invalid arguments.  */
 510     abort ();
 511   result.vtable = list->base.vtable;
 512   result.list = list;
 513   /* Start node is the node at position start_index.  */
 514   result.p = (start_index < count ? node_at (list->root, start_index) : NULL);
 515   /* End point is the node at position end_index.  */
 516   result.q = (end_index < count ? node_at (list->root, end_index) : NULL);
 517 #ifdef lint
 518   result.i = 0;
 519   result.j = 0;
 520   result.count = 0;
 521 #endif
 522
 523   return result;
 524 }
 525
 526 static bool
 527 gl_tree_iterator_next (gl_list_iterator_t *iterator,
 528                        const void **eltp, gl_list_node_t *nodep)
 529 {
 530   if (iterator->p != iterator->q)
 531     {
 532       gl_list_node_t node = (gl_list_node_t) iterator->p;
 533       *eltp = node->value;
 534       if (nodep != NULL)
 535         *nodep = node;
 536       /* Advance to the next node.  */
 537       if (node->right != NULL)
 538         {
 539           node = node->right;
 540           while (node->left != NULL)
 541             node = node->left;
 542         }
 543       else
 544         {
 545           while (node->parent != NULL && node->parent->right == node)
 546             node = node->parent;
 547           node = node->parent;
 548         }
 549       iterator->p = node;
 550       return true;
 551     }
 552   else
 553     return false;
 554 }
 555
 556 static void
 557 gl_tree_iterator_free (gl_list_iterator_t *iterator)
 558 {
 559 }
 560
 561 /* ---------------------- Sorted gl_list_t Data Type ---------------------- */
 562
 563 static gl_list_node_t
 564 gl_tree_sortedlist_search (gl_list_t list, gl_listelement_compar_fn compar,
 565                            const void *elt)
 566 {
 567   gl_list_node_t node;
 568
 569   for (node = list->root; node != NULL; )
 570     {
 571       int cmp = compar (node->value, elt);
 572
 573       if (cmp < 0)
 574         node = node->right;
 575       else if (cmp > 0)
 576         node = node->left;
 577       else /* cmp == 0 */
 578         {
 579           /* We have an element equal to ELT.  But we need the leftmost such
 580              element.  */
 581           gl_list_node_t found = node;
 582           node = node->left;
 583           for (; node != NULL; )
 584             {
 585               int cmp2 = compar (node->value, elt);
 586
 587               if (cmp2 < 0)
 588                 node = node->right;
 589               else if (cmp2 > 0)
 590                 /* The list was not sorted.  */
 591                 abort ();
 592               else /* cmp2 == 0 */
 593                 {
 594                   found = node;
 595                   node = node->left;
 596                 }
 597             }
 598           return found;
 599         }
 600     }
 601   return NULL;
 602 }
 603
 604 static size_t
 605 gl_tree_sortedlist_indexof (gl_list_t list, gl_listelement_compar_fn compar,
 606                             const void *elt)
 607 {
 608   gl_list_node_t node;
 609   size_t position;
 610
 611   for (node = list->root, position = 0; node != NULL; )
 612     {
 613       int cmp = compar (node->value, elt);
 614
 615       if (cmp < 0)
 616         {
 617           if (node->left != NULL)
 618             position += node->left->branch_size;
 619           position++;
 620           node = node->right;
 621         }
 622       else if (cmp > 0)
 623         node = node->left;
 624       else /* cmp == 0 */
 625         {
 626           /* We have an element equal to ELT.  But we need the leftmost such
 627              element.  */
 628           size_t found_position =
 629             position + (node->left != NULL ? node->left->branch_size : 0);
 630           node = node->left;
 631           for (; node != NULL; )
 632             {
 633               int cmp2 = compar (node->value, elt);
 634
 635               if (cmp2 < 0)
 636                 {
 637                   if (node->left != NULL)
 638                     position += node->left->branch_size;
 639                   position++;
 640                   node = node->right;
 641                 }
 642               else if (cmp2 > 0)
 643                 /* The list was not sorted.  */
 644                 abort ();
 645               else /* cmp2 == 0 */
 646                 {
 647                   found_position =
 648                     position
 649                     + (node->left != NULL ? node->left->branch_size : 0);
 650                   node = node->left;
 651                 }
 652             }
 653           return found_position;
 654         }
 655     }
 656   return (size_t)(-1);
 657 }
 658
 659 static gl_list_node_t
 660 gl_tree_sortedlist_add (gl_list_t list, gl_listelement_compar_fn compar,
 661                         const void *elt)
 662 {
 663   gl_list_node_t node = list->root;
 664
 665   if (node == NULL)
 666     return gl_tree_add_first (list, elt);
 667
 668   for (;;)
 669     {
 670       int cmp = compar (node->value, elt);
 671
 672       if (cmp < 0)
 673         {
 674           if (node->right == NULL)
 675             return gl_tree_add_after (list, node, elt);
 676           node = node->right;
 677         }
 678       else if (cmp > 0)
 679         {
 680           if (node->left == NULL)
 681             return gl_tree_add_before (list, node, elt);
 682           node = node->left;
 683         }
 684       else /* cmp == 0 */
 685         return gl_tree_add_before (list, node, elt);
 686     }
 687 }
 688
 689 static bool
 690 gl_tree_sortedlist_remove (gl_list_t list, gl_listelement_compar_fn compar,
 691                            const void *elt)
 692 {
 693   gl_list_node_t node = gl_tree_sortedlist_search (list, compar, elt);
 694   if (node != NULL)
 695     return gl_tree_remove_node (list, node);
 696   else
 697     return false;
 698 }