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
 353   return result;
 354 }
 355
 356 static gl_list_iterator_t
 357 gl_tree_iterator_from_to (gl_list_t list, size_t start_index, size_t end_index)
 358 {
 359   size_t count = (list->root != NULL ? list->root->branch_size : 0);
 360   gl_list_iterator_t result;
 361
 362   if (!(start_index <= end_index && end_index <= count))
 363     /* Invalid arguments.  */
 364     abort ();
 365   result.vtable = list->base.vtable;
 366   result.list = list;
 367   /* Start node is the node at position start_index.  */
 368   result.p = (start_index < count ? node_at (list->root, start_index) : NULL);
 369   /* End point is the node at position end_index.  */
 370   result.q = (end_index < count ? node_at (list->root, end_index) : NULL);
 371
 372   return result;
 373 }
 374
 375 static bool
 376 gl_tree_iterator_next (gl_list_iterator_t *iterator,
 377                        const void **eltp, gl_list_node_t *nodep)
 378 {
 379   if (iterator->p != iterator->q)
 380     {
 381       gl_list_node_t node = (gl_list_node_t) iterator->p;
 382       *eltp = node->value;
 383       if (nodep != NULL)
 384         *nodep = node;
 385       /* Advance to the next node.  */
 386       if (node->right != NULL)
 387         {
 388           node = node->right;
 389           while (node->left != NULL)
 390             node = node->left;
 391         }
 392       else
 393         {
 394           while (node->parent != NULL && node->parent->right == node)
 395             node = node->parent;
 396           node = node->parent;
 397         }
 398       iterator->p = node;
 399       return true;
 400     }
 401   else
 402     return false;
 403 }
 404
 405 static void
 406 gl_tree_iterator_free (gl_list_iterator_t *iterator)
 407 {
 408 }
 409
 410 /* ---------------------- Sorted gl_list_t Data Type ---------------------- */
 411
 412 static gl_list_node_t
 413 gl_tree_sortedlist_search (gl_list_t list, gl_listelement_compar_fn compar,
 414                            const void *elt)
 415 {
 416   gl_list_node_t node;
 417
 418   for (node = list->root; node != NULL; )
 419     {
 420       int cmp = compar (node->value, elt);
 421
 422       if (cmp < 0)
 423         node = node->right;
 424       else if (cmp > 0)
 425         node = node->left;
 426       else /* cmp == 0 */
 427         {
 428           /* We have an element equal to ELT.  But we need the leftmost such
 429              element.  */
 430           gl_list_node_t found = node;
 431           node = node->left;
 432           for (; node != NULL; )
 433             {
 434               int cmp2 = compar (node->value, elt);
 435
 436               if (cmp2 < 0)
 437                 node = node->right;
 438               else if (cmp2 > 0)
 439                 /* The list was not sorted.  */
 440                 abort ();
 441               else /* cmp2 == 0 */
 442                 {
 443                   found = node;
 444                   node = node->left;
 445                 }
 446             }
 447           return found;
 448         }
 449     }
 450   return NULL;
 451 }
 452
 453 static size_t
 454 gl_tree_sortedlist_indexof (gl_list_t list, gl_listelement_compar_fn compar,
 455                             const void *elt)
 456 {
 457   gl_list_node_t node;
 458   size_t position;
 459
 460   for (node = list->root, position = 0; node != NULL; )
 461     {
 462       int cmp = compar (node->value, elt);
 463
 464       if (cmp < 0)
 465         {
 466           if (node->left != NULL)
 467             position += node->left->branch_size;
 468           position++;
 469           node = node->right;
 470         }
 471       else if (cmp > 0)
 472         node = node->left;
 473       else /* cmp == 0 */
 474         {
 475           /* We have an element equal to ELT.  But we need the leftmost such
 476              element.  */
 477           size_t found_position =
 478             position + (node->left != NULL ? node->left->branch_size : 0);
 479           node = node->left;
 480           for (; node != NULL; )
 481             {
 482               int cmp2 = compar (node->value, elt);
 483
 484               if (cmp2 < 0)
 485                 {
 486                   if (node->left != NULL)
 487                     position += node->left->branch_size;
 488                   position++;
 489                   node = node->right;
 490                 }
 491               else if (cmp2 > 0)
 492                 /* The list was not sorted.  */
 493                 abort ();
 494               else /* cmp2 == 0 */
 495                 {
 496                   found_position =
 497                     position
 498                     + (node->left != NULL ? node->left->branch_size : 0);
 499                   node = node->left;
 500                 }
 501             }
 502           return found_position;
 503         }
 504     }
 505   return (size_t)(-1);
 506 }
 507
 508 static gl_list_node_t
 509 gl_tree_sortedlist_add (gl_list_t list, gl_listelement_compar_fn compar,
 510                         const void *elt)
 511 {
 512   gl_list_node_t node = list->root;
 513
 514   if (node == NULL)
 515     return gl_tree_add_first (list, elt);
 516
 517   for (;;)
 518     {
 519       int cmp = compar (node->value, elt);
 520
 521       if (cmp < 0)
 522         {
 523           if (node->right == NULL)
 524             return gl_tree_add_after (list, node, elt);
 525           node = node->right;
 526         }
 527       else if (cmp > 0)
 528         {
 529           if (node->left == NULL)
 530             return gl_tree_add_before (list, node, elt);
 531           node = node->left;
 532         }
 533       else /* cmp == 0 */
 534         return gl_tree_add_before (list, node, elt);
 535     }
 536 }
 537
 538 static bool
 539 gl_tree_sortedlist_remove (gl_list_t list, gl_listelement_compar_fn compar,
 540                            const void *elt)
 541 {
 542   gl_list_node_t node = gl_tree_sortedlist_search (list, compar, elt);
 543   if (node != NULL)
 544     return gl_tree_remove_node (list, node);
 545   else
 546     return false;
 547 }