1  /* Sequential list data type implemented by a hash table with a binary tree.
       2     Copyright (C) 2006, 2008-2021 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 3 of the License, or
       8     (at your option) 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, see <https://www.gnu.org/licenses/>.  */
      17  
      18  #include <config.h>
      19  
      20  /* Specification.  */
      21  #include "gl_rbtreehash_list.h"
      22  
      23  #include <stdint.h> /* for uintptr_t, SIZE_MAX */
      24  #include <stdlib.h>
      25  
      26  #include "gl_rbtree_oset.h"
      27  #include "xsize.h"
      28  
      29  #define WITH_HASHTABLE 1
      30  
      31  /* Which kind of binary trees to use for ordered sets.  Quite arbitrary.  */
      32  #define OSET_TREE_FLAVOR GL_RBTREE_OSET
      33  
      34  /* -------------------------- gl_list_t Data Type -------------------------- */
      35  
      36  /* Generic hash-table code: Type definitions.  */
      37  #include "gl_anyhash1.h"
      38  
      39  /* Generic red-black tree code: Type definitions.  */
      40  #include "gl_anyrbtree_list1.h"
      41  
      42  /* Generic hash-table code: Low-level code.  */
      43  #define CONTAINER_T gl_list_t
      44  #define CONTAINER_COUNT(list) \
      45    ((list)->root != NULL ? (list)->root->branch_size : 0)
      46  #include "gl_anyhash2.h"
      47  
      48  /* Generic binary tree code: Type definitions.  */
      49  #include "gl_anytree_list1.h"
      50  
      51  /* Hash-table with binary tree code: Handling of hash buckets.  */
      52  #include "gl_anytreehash_list1.h"
      53  
      54  /* Generic red-black tree code: Insertion/deletion algorithms.  */
      55  #include "gl_anyrbtree_list2.h"
      56  
      57  /* Generic binary tree code: Functions taking advantage of the hash table.  */
      58  #include "gl_anytreehash_list2.h"
      59  
      60  /* Generic binary tree code: All other functions.  */
      61  #include "gl_anytree_list2.h"
      62  
      63  /* For debugging.  */
      64  static unsigned int
      65  check_invariants (gl_list_node_t node, gl_list_node_t parent)
      66  {
      67    unsigned int left_blackheight =
      68      (node->left != NULL ? check_invariants (node->left, node) : 0);
      69    unsigned int right_blackheight =
      70      (node->right != NULL ? check_invariants (node->right, node) : 0);
      71  
      72    if (!(node->parent == parent))
      73      abort ();
      74    if (!(node->branch_size
      75          == (node->left != NULL ? node->left->branch_size : 0)
      76             + 1 + (node->right != NULL ? node->right->branch_size : 0)))
      77      abort ();
      78    if (!(node->color == BLACK || node->color == RED))
      79      abort ();
      80    if (parent == NULL && !(node->color == BLACK))
      81      abort ();
      82    if (!(left_blackheight == right_blackheight))
      83      abort ();
      84  
      85    return left_blackheight + (node->color == BLACK ? 1 : 0);
      86  }
      87  void
      88  gl_rbtreehash_list_check_invariants (gl_list_t list)
      89  {
      90    if (list->root != NULL)
      91      check_invariants (list->root, NULL);
      92  }
      93  
      94  
      95  const struct gl_list_implementation gl_rbtreehash_list_implementation =
      96    {
      97      gl_tree_nx_create_empty,
      98      gl_tree_nx_create,
      99      gl_tree_size,
     100      gl_tree_node_value,
     101      gl_tree_node_nx_set_value,
     102      gl_tree_next_node,
     103      gl_tree_previous_node,
     104      gl_tree_first_node,
     105      gl_tree_last_node,
     106      gl_tree_get_at,
     107      gl_tree_nx_set_at,
     108      gl_tree_search_from_to,
     109      gl_tree_indexof_from_to,
     110      gl_tree_nx_add_first,
     111      gl_tree_nx_add_last,
     112      gl_tree_nx_add_before,
     113      gl_tree_nx_add_after,
     114      gl_tree_nx_add_at,
     115      gl_tree_remove_node,
     116      gl_tree_remove_at,
     117      gl_tree_remove,
     118      gl_tree_list_free,
     119      gl_tree_iterator,
     120      gl_tree_iterator_from_to,
     121      gl_tree_iterator_next,
     122      gl_tree_iterator_free,
     123      gl_tree_sortedlist_search,
     124      gl_tree_sortedlist_search_from_to,
     125      gl_tree_sortedlist_indexof,
     126      gl_tree_sortedlist_indexof_from_to,
     127      gl_tree_sortedlist_nx_add,
     128      gl_tree_sortedlist_remove
     129    };