pintos-os.org Git - pspp/blob - 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 (gl_list_t list, const void *elt)
 168 {
 169   gl_listelement_equals_fn equals = list->base.equals_fn;
 170   /* Iterate across all elements.  */
 171   gl_list_node_t node = list->root;
 172   iterstack_t stack;
 173   iterstack_item_t *stack_ptr = &stack[0];
 174
 175   for (;;)
 176     {
 177       /* Descend on left branch.  */
 178       for (;;)
 179         {
 180           if (node == NULL)
 181             break;
 182           stack_ptr->node = node;
 183           stack_ptr->rightp = false;
 184           node = node->left;
 185           stack_ptr++;
 186         }
 187       /* Climb up again.  */
 188       for (;;)
 189         {
 190           if (stack_ptr == &stack[0])
 191             return NULL;
 192           stack_ptr--;
 193           if (!stack_ptr->rightp)
 194             break;
 195         }
 196       node = stack_ptr->node;
 197       /* Test against current element.  */
 198       if (equals != NULL ? equals (elt, node->value) : elt == node->value)
 199         return node;
 200       /* Descend on right branch.  */
 201       stack_ptr->rightp = true;
 202       node = node->right;
 203       stack_ptr++;
 204     }
 205 }
 206
 207 static size_t
 208 gl_tree_indexof (gl_list_t list, const void *elt)
 209 {
 210   gl_listelement_equals_fn equals = list->base.equals_fn;
 211   /* Iterate across all elements.  */
 212   gl_list_node_t node = list->root;
 213   iterstack_t stack;
 214   iterstack_item_t *stack_ptr = &stack[0];
 215   size_t index = 0;
 216
 217   for (;;)
 218     {
 219       /* Descend on left branch.  */
 220       for (;;)
 221         {
 222           if (node == NULL)
 223             break;
 224           stack_ptr->node = node;
 225           stack_ptr->rightp = false;
 226           node = node->left;
 227           stack_ptr++;
 228         }
 229       /* Climb up again.  */
 230       for (;;)
 231         {
 232           if (stack_ptr == &stack[0])
 233             return (size_t)(-1);
 234           stack_ptr--;
 235           if (!stack_ptr->rightp)
 236             break;
 237         }
 238       node = stack_ptr->node;
 239       /* Test against current element.  */
 240       if (equals != NULL ? equals (elt, node->value) : elt == node->value)
 241         return index;
 242       index++;
 243       /* Descend on right branch.  */
 244       stack_ptr->rightp = true;
 245       node = node->right;
 246       stack_ptr++;
 247     }
 248 }
 249
 250 #endif
 251
 252 static gl_list_node_t
 253 gl_tree_add_at (gl_list_t list, size_t position, const void *elt)
 254 {
 255   size_t count = (list->root != NULL ? list->root->branch_size : 0);
 256
 257   if (!(position <= count))
 258     /* Invalid argument.  */
 259     abort ();
 260   if (position == count)
 261     return gl_tree_add_last (list, elt);
 262   else
 263     return gl_tree_add_before (list, node_at (list->root, position), elt);
 264 }
 265
 266 static bool
 267 gl_tree_remove_at (gl_list_t list, size_t position)
 268 {
 269   gl_list_node_t node = list->root;
 270
 271   if (!(node != NULL && position < node->branch_size))
 272     /* Invalid argument.  */
 273     abort ();
 274   node = node_at (node, position);
 275   return gl_tree_remove_node (list, node);
 276 }
 277
 278 static bool
 279 gl_tree_remove (gl_list_t list, const void *elt)
 280 {
 281   gl_list_node_t node = gl_tree_search (list, elt);
 282
 283   if (node != NULL)
 284     return gl_tree_remove_node (list, node);
 285   else
 286     return false;
 287 }
 288
 289 #if !WITH_HASHTABLE
 290
 291 static void
 292 gl_tree_list_free (gl_list_t list)
 293 {
 294   /* Iterate across all elements in post-order.  */
 295   gl_list_node_t node = list->root;
 296   iterstack_t stack;
 297   iterstack_item_t *stack_ptr = &stack[0];
 298
 299   for (;;)
 300     {
 301       /* Descend on left branch.  */
 302       for (;;)
 303         {
 304           if (node == NULL)
 305             break;
 306           stack_ptr->node = node;
 307           stack_ptr->rightp = false;
 308           node = node->left;
 309           stack_ptr++;
 310         }
 311       /* Climb up again.  */
 312       for (;;)
 313         {
 314           if (stack_ptr == &stack[0])
 315             goto done_iterate;
 316           stack_ptr--;
 317           node = stack_ptr->node;
 318           if (!stack_ptr->rightp)
 319             break;
 320           /* Free the current node.  */
 321           free (node);
 322         }
 323       /* Descend on right branch.  */
 324       stack_ptr->rightp = true;
 325       node = node->right;
 326       stack_ptr++;
 327     }
 328  done_iterate:
 329   free (list);
 330 }
 331
 332 #endif
 333
 334 /* --------------------- gl_list_iterator_t Data Type --------------------- */
 335
 336 static gl_list_iterator_t
 337 gl_tree_iterator (gl_list_t list)
 338 {
 339   gl_list_iterator_t result;
 340   gl_list_node_t node;
 341
 342   result.vtable = list->base.vtable;
 343   result.list = list;
 344   /* Start node is the leftmost node.  */
 345   node = list->root;
 346   if (node != NULL)
 347     while (node->left != NULL)
 348       node = node->left;
 349   result.p = node;
 350   /* End point is past the rightmost node.  */
 351   result.q = NULL;
 352 #ifdef lint
 353   result.i = 0;
 354   result.j = 0;
 355   result.count = 0;
 356 #endif
 357
 358   return result;
 359 }
 360
 361 static gl_list_iterator_t
 362 gl_tree_iterator_from_to (gl_list_t list, size_t start_index, size_t end_index)
 363 {
 364   size_t count = (list->root != NULL ? list->root->branch_size : 0);
 365   gl_list_iterator_t result;
 366
 367   if (!(start_index <= end_index && end_index <= count))
 368     /* Invalid arguments.  */
 369     abort ();
 370   result.vtable = list->base.vtable;
 371   result.list = list;
 372   /* Start node is the node at position start_index.  */
 373   result.p = (start_index < count ? node_at (list->root, start_index) : NULL);
 374   /* End point is the node at position end_index.  */
 375   result.q = (end_index < count ? node_at (list->root, end_index) : NULL);
 376 #ifdef lint
 377   result.i = 0;
 378   result.j = 0;
 379   result.count = 0;
 380 #endif
 381
 382   return result;
 383 }
 384
 385 static bool
 386 gl_tree_iterator_next (gl_list_iterator_t *iterator,
 387                        const void **eltp, gl_list_node_t *nodep)
 388 {
 389   if (iterator->p != iterator->q)
 390     {
 391       gl_list_node_t node = (gl_list_node_t) iterator->p;
 392       *eltp = node->value;
 393       if (nodep != NULL)
 394         *nodep = node;
 395       /* Advance to the next node.  */
 396       if (node->right != NULL)
 397         {
 398           node = node->right;
 399           while (node->left != NULL)
 400             node = node->left;
 401         }
 402       else
 403         {
 404           while (node->parent != NULL && node->parent->right == node)
 405             node = node->parent;
 406           node = node->parent;
 407         }
 408       iterator->p = node;
 409       return true;
 410     }
 411   else
 412     return false;
 413 }
 414
 415 static void
 416 gl_tree_iterator_free (gl_list_iterator_t *iterator)
 417 {
 418 }
 419
 420 /* ---------------------- Sorted gl_list_t Data Type ---------------------- */
 421
 422 static gl_list_node_t
 423 gl_tree_sortedlist_search (gl_list_t list, gl_listelement_compar_fn compar,
 424                            const void *elt)
 425 {
 426   gl_list_node_t node;
 427
 428   for (node = list->root; node != NULL; )
 429     {
 430       int cmp = compar (node->value, elt);
 431
 432       if (cmp < 0)
 433         node = node->right;
 434       else if (cmp > 0)
 435         node = node->left;
 436       else /* cmp == 0 */
 437         {
 438           /* We have an element equal to ELT.  But we need the leftmost such
 439              element.  */
 440           gl_list_node_t found = node;
 441           node = node->left;
 442           for (; node != NULL; )
 443             {
 444               int cmp2 = compar (node->value, elt);
 445
 446               if (cmp2 < 0)
 447                 node = node->right;
 448               else if (cmp2 > 0)
 449                 /* The list was not sorted.  */
 450                 abort ();
 451               else /* cmp2 == 0 */
 452                 {
 453                   found = node;
 454                   node = node->left;
 455                 }
 456             }
 457           return found;
 458         }
 459     }
 460   return NULL;
 461 }
 462
 463 static size_t
 464 gl_tree_sortedlist_indexof (gl_list_t list, gl_listelement_compar_fn compar,
 465                             const void *elt)
 466 {
 467   gl_list_node_t node;
 468   size_t position;
 469
 470   for (node = list->root, position = 0; node != NULL; )
 471     {
 472       int cmp = compar (node->value, elt);
 473
 474       if (cmp < 0)
 475         {
 476           if (node->left != NULL)
 477             position += node->left->branch_size;
 478           position++;
 479           node = node->right;
 480         }
 481       else if (cmp > 0)
 482         node = node->left;
 483       else /* cmp == 0 */
 484         {
 485           /* We have an element equal to ELT.  But we need the leftmost such
 486              element.  */
 487           size_t found_position =
 488             position + (node->left != NULL ? node->left->branch_size : 0);
 489           node = node->left;
 490           for (; node != NULL; )
 491             {
 492               int cmp2 = compar (node->value, elt);
 493
 494               if (cmp2 < 0)
 495                 {
 496                   if (node->left != NULL)
 497                     position += node->left->branch_size;
 498                   position++;
 499                   node = node->right;
 500                 }
 501               else if (cmp2 > 0)
 502                 /* The list was not sorted.  */
 503                 abort ();
 504               else /* cmp2 == 0 */
 505                 {
 506                   found_position =
 507                     position
 508                     + (node->left != NULL ? node->left->branch_size : 0);
 509                   node = node->left;
 510                 }
 511             }
 512           return found_position;
 513         }
 514     }
 515   return (size_t)(-1);
 516 }
 517
 518 static gl_list_node_t
 519 gl_tree_sortedlist_add (gl_list_t list, gl_listelement_compar_fn compar,
 520                         const void *elt)
 521 {
 522   gl_list_node_t node = list->root;
 523
 524   if (node == NULL)
 525     return gl_tree_add_first (list, elt);
 526
 527   for (;;)
 528     {
 529       int cmp = compar (node->value, elt);
 530
 531       if (cmp < 0)
 532         {
 533           if (node->right == NULL)
 534             return gl_tree_add_after (list, node, elt);
 535           node = node->right;
 536         }
 537       else if (cmp > 0)
 538         {
 539           if (node->left == NULL)
 540             return gl_tree_add_before (list, node, elt);
 541           node = node->left;
 542         }
 543       else /* cmp == 0 */
 544         return gl_tree_add_before (list, node, elt);
 545     }
 546 }
 547
 548 static bool
 549 gl_tree_sortedlist_remove (gl_list_t list, gl_listelement_compar_fn compar,
 550                            const void *elt)
 551 {
 552   gl_list_node_t node = gl_tree_sortedlist_search (list, compar, elt);
 553   if (node != NULL)
 554     return gl_tree_remove_node (list, node);
 555   else
 556     return false;
 557 }