1  /* Sequential list data type implemented by a binary tree.
       2     Copyright (C) 2006, 2008-2023 Free Software Foundation, Inc.
       3     Written by Bruno Haible <bruno@clisp.org>, 2006.
       4  
       5     This file is free software: you can redistribute it and/or modify
       6     it under the terms of the GNU Lesser General Public License as
       7     published by the Free Software Foundation; either version 2.1 of the
       8     License, or (at your option) any later version.
       9  
      10     This file 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 Lesser General Public License for more details.
      14  
      15     You should have received a copy of the GNU Lesser General Public License
      16     along with this program.  If not, see <https://www.gnu.org/licenses/>.  */
      17  
      18  #include <config.h>
      19  
      20  /* Specification.  */
      21  #include "gl_rbtree_list.h"
      22  
      23  #include <stdlib.h>
      24  
      25  /* -------------------------- gl_list_t Data Type -------------------------- */
      26  
      27  /* Generic red-black tree code.  */
      28  #include "gl_anyrbtree_list1.h"
      29  
      30  /* Generic binary tree code.  */
      31  #include "gl_anytree_list1.h"
      32  
      33  /* Generic red-black tree code.  */
      34  #include "gl_anyrbtree_list2.h"
      35  
      36  /* Generic binary tree code.  */
      37  #include "gl_anytree_list2.h"
      38  
      39  /* For debugging.  */
      40  static unsigned int
      41  check_invariants (gl_list_node_t node, gl_list_node_t parent)
      42  {
      43    unsigned int left_blackheight =
      44      (node->left != NULL ? check_invariants (node->left, node) : 0);
      45    unsigned int right_blackheight =
      46      (node->right != NULL ? check_invariants (node->right, node) : 0);
      47  
      48    if (!(node->parent == parent))
      49      abort ();
      50    if (!(node->branch_size
      51          == (node->left != NULL ? node->left->branch_size : 0)
      52             + 1 + (node->right != NULL ? node->right->branch_size : 0)))
      53      abort ();
      54    if (!(node->color == BLACK || node->color == RED))
      55      abort ();
      56    if (parent == NULL && !(node->color == BLACK))
      57      abort ();
      58    if (!(left_blackheight == right_blackheight))
      59      abort ();
      60  
      61    return left_blackheight + (node->color == BLACK ? 1 : 0);
      62  }
      63  extern void gl_rbtree_list_check_invariants (gl_list_t list);
      64  void
      65  gl_rbtree_list_check_invariants (gl_list_t list)
      66  {
      67    if (list->root != NULL)
      68      (void) check_invariants (list->root, NULL);
      69  }
      70  
      71  const struct gl_list_implementation gl_rbtree_list_implementation =
      72    {
      73      gl_tree_nx_create_empty,
      74      gl_tree_nx_create,
      75      gl_tree_size,
      76      gl_tree_node_value,
      77      gl_tree_node_nx_set_value,
      78      gl_tree_next_node,
      79      gl_tree_previous_node,
      80      gl_tree_first_node,
      81      gl_tree_last_node,
      82      gl_tree_get_at,
      83      gl_tree_nx_set_at,
      84      gl_tree_search_from_to,
      85      gl_tree_indexof_from_to,
      86      gl_tree_nx_add_first,
      87      gl_tree_nx_add_last,
      88      gl_tree_nx_add_before,
      89      gl_tree_nx_add_after,
      90      gl_tree_nx_add_at,
      91      gl_tree_remove_node,
      92      gl_tree_remove_at,
      93      gl_tree_remove,
      94      gl_tree_list_free,
      95      gl_tree_iterator,
      96      gl_tree_iterator_from_to,
      97      gl_tree_iterator_next,
      98      gl_tree_iterator_free,
      99      gl_tree_sortedlist_search,
     100      gl_tree_sortedlist_search_from_to,
     101      gl_tree_sortedlist_indexof,
     102      gl_tree_sortedlist_indexof_from_to,
     103      gl_tree_sortedlist_nx_add,
     104      gl_tree_sortedlist_remove
     105    };