1  /* Sequential list data type implemented by a binary tree.
       2     Copyright (C) 2006, 2009-2021 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  /* Common code of gl_rbtree_list.c and gl_rbtreehash_list.c.  */
      19  
      20  /* A red-black tree is a binary tree where every node is colored black or
      21     red such that
      22     1. The root is black.
      23     2. No red node has a red parent.
      24        Or equivalently: No red node has a red child.
      25     3. All paths from the root down to any NULL endpoint contain the same
      26        number of black nodes.
      27     Let's call this the "black-height" bh of the tree.  It follows that every
      28     such path contains exactly bh black and between 0 and bh red nodes.  (The
      29     extreme cases are a path containing only black nodes, and a path colored
      30     alternately black-red-black-red-...-black-red.)  The height of the tree
      31     therefore is >= bh, <= 2*bh.
      32   */
      33  
      34  /* -------------------------- gl_list_t Data Type -------------------------- */
      35  
      36  /* Color of a node.  */
      37  typedef enum color { BLACK, RED } color_t;
      38  
      39  /* Concrete list node implementation, valid for this file only.  */
      40  struct gl_list_node_impl
      41  {
      42  #if WITH_HASHTABLE
      43    struct gl_hash_entry h;           /* hash table entry fields; must be first */
      44  #endif
      45    struct gl_list_node_impl *left;   /* left branch, or NULL */
      46    struct gl_list_node_impl *right;  /* right branch, or NULL */
      47    /* Parent pointer, or NULL. The parent pointer is not needed for most
      48       operations.  It is needed so that a gl_list_node_t can be returned
      49       without memory allocation, on which the functions gl_list_remove_node,
      50       gl_list_add_before, gl_list_add_after can be implemented.  */
      51    struct gl_list_node_impl *parent;
      52    color_t color;                    /* node's color */
      53    size_t branch_size;               /* number of nodes in this branch,
      54                                         = branchsize(left)+branchsize(right)+1 */
      55    const void *value;
      56  };
      57  
      58  /* Concrete gl_list_impl type, valid for this file only.  */
      59  struct gl_list_impl
      60  {
      61    struct gl_list_impl_base base;
      62  #if WITH_HASHTABLE
      63    /* A hash table: managed as an array of collision lists.  */
      64    struct gl_hash_entry **table;
      65    size_t table_size;
      66  #endif
      67    struct gl_list_node_impl *root;   /* root node or NULL */
      68  };
      69  
      70  /* A red-black tree of height h has a black-height bh >= ceil(h/2) and
      71     therefore at least 2^ceil(h/2) - 1 elements.  So, h <= 116 (because a tree
      72     of height h >= 117 would have at least 2^59 - 1 elements, and because even
      73     on 64-bit machines,
      74       sizeof (gl_list_node_impl) * (2^59 - 1) > 2^64
      75     this would exceed the address space of the machine.  */
      76  #define MAXHEIGHT 116