/* Sequential list data type implemented by a binary tree. Copyright (C) 2006 Free Software Foundation, Inc. Written by Bruno Haible , 2006. This program is free software; you can redistribute it and/or modify it under the terms of the GNU General Public License as published by the Free Software Foundation; either version 2, or (at your option) any later version. This program is distributed in the hope that it will be useful, but WITHOUT ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License for more details. You should have received a copy of the GNU General Public License along with this program; if not, write to the Free Software Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301, USA. */ /* Common code of gl_rbtree_list.c and gl_rbtreehash_list.c. */ /* A red-black tree is a binary tree where every node is colored black or red such that 1. The root is black. 2. No red node has a red parent. Or equivalently: No red node has a red child. 3. All paths from the root down to any NULL endpoint contain the same number of black nodes. Let's call this the "black-height" bh of the tree. It follows that every such path contains exactly bh black and between 0 and bh red nodes. (The extreme cases are a path containing only black nodes, and a path colored alternatingly black-red-black-red-...-black-red.) The height of the tree therefore is >= bh, <= 2*bh. */ /* -------------------------- gl_list_t Data Type -------------------------- */ /* Color of a node. */ typedef enum color { BLACK, RED } color_t; /* Concrete list node implementation, valid for this file only. */ struct gl_list_node_impl { #if WITH_HASHTABLE struct gl_hash_entry h; /* hash table entry fields; must be first */ #endif struct gl_list_node_impl *left; /* left branch, or NULL */ struct gl_list_node_impl *right; /* right branch, or NULL */ /* Parent pointer, or NULL. The parent pointer is not needed for most operations. It is needed so that a gl_list_node_t can be returned without memory allocation, on which the functions gl_list_remove_node, gl_list_add_before, gl_list_add_after can be implemented. */ struct gl_list_node_impl *parent; color_t color; /* node's color */ size_t branch_size; /* number of nodes in this branch, = branchsize(left)+branchsize(right)+1 */ const void *value; }; /* Concrete gl_list_impl type, valid for this file only. */ struct gl_list_impl { struct gl_list_impl_base base; #if WITH_HASHTABLE /* A hash table: managed as an array of collision lists. */ struct gl_hash_entry **table; size_t table_size; #endif struct gl_list_node_impl *root; /* root node or NULL */ }; /* A red-black tree of height h has a black-height bh >= ceil(h/2) and therefore at least 2^ceil(h/2) - 1 elements. So, h <= 116 (because a tree of height h >= 117 would have at least 2^59 - 1 elements, and because even on 64-bit machines, sizeof (gl_list_node_impl) * (2^59 - 1) > 2^64 this would exceed the address space of the machine. */ #define MAXHEIGHT 116