lib/gl_anyavltree_list1.h

   1 /* Sequential list data type implemented by a binary tree.
   2    Copyright (C) 2006, 2009-2020 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 /* Common code of gl_avltree_list.c and gl_avltreehash_list.c.  */
  19
  20 /* An AVL tree is a binary tree where
  21    1. The height of each node is calculated as
  22         heightof(node) = 1 + max (heightof(node.left), heightof(node.right)).
  23    2. The heights of the subtrees of each node differ by at most 1:
  24         | heightof(right) - heightof(left) | <= 1.
  25    3. The index of the elements in the node.left subtree are smaller than
  26       the index of node.
  27       The index of the elements in the node.right subtree are larger than
  28       the index of node.
  29  */
  30
  31 /* -------------------------- gl_list_t Data Type -------------------------- */
  32
  33 /* Concrete list node implementation, valid for this file only.  */
  34 struct gl_list_node_impl
  35 {
  36 #if WITH_HASHTABLE
  37   struct gl_hash_entry h;           /* hash table entry fields; must be first */
  38 #endif
  39   struct gl_list_node_impl *left;   /* left branch, or NULL */
  40   struct gl_list_node_impl *right;  /* right branch, or NULL */
  41   /* Parent pointer, or NULL. The parent pointer is not needed for most
  42      operations.  It is needed so that a gl_list_node_t can be returned
  43      without memory allocation, on which the functions gl_list_remove_node,
  44      gl_list_add_before, gl_list_add_after can be implemented.  */
  45   struct gl_list_node_impl *parent;
  46   int balance;                      /* heightof(right) - heightof(left),
  47                                        always = -1 or 0 or 1 */
  48   size_t branch_size;               /* number of nodes in this branch,
  49                                        = branchsize(left)+branchsize(right)+1 */
  50   const void *value;
  51 };
  52
  53 /* Concrete gl_list_impl type, valid for this file only.  */
  54 struct gl_list_impl
  55 {
  56   struct gl_list_impl_base base;
  57 #if WITH_HASHTABLE
  58   /* A hash table: managed as an array of collision lists.  */
  59   struct gl_hash_entry **table;
  60   size_t table_size;
  61 #endif
  62   struct gl_list_node_impl *root;   /* root node or NULL */
  63 };
  64
  65 /* An AVL tree of height h has at least F_(h+2) - 1 [Fibonacci number] and at
  66    most 2^h - 1 elements.  So, h <= 84 (because a tree of height h >= 85 would
  67    have at least F_87 - 1 elements, and because even on 64-bit machines,
  68      sizeof (gl_list_node_impl) * (F_87 - 1) > 2^64
  69    this would exceed the address space of the machine.  */
  70 #define MAXHEIGHT 83