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