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