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_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