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.
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)
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.
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. */
19 /* Common code of gl_rbtree_list.c and gl_rbtreehash_list.c. */
21 /* A red-black tree is a binary tree where every node is colored black or
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.
35 /* -------------------------- gl_list_t Data Type -------------------------- */
37 /* Color of a node. */
38 typedef enum color { BLACK, RED } color_t;
40 /* Concrete list node implementation, valid for this file only. */
41 struct gl_list_node_impl
44 struct gl_hash_entry h; /* hash table entry fields; must be first */
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 */
59 /* Concrete gl_list_impl type, valid for this file only. */
62 struct gl_list_impl_base base;
64 /* A hash table: managed as an array of collision lists. */
65 struct gl_hash_entry **table;
68 struct gl_list_node_impl *root; /* root node or NULL */
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
75 sizeof (gl_list_node_impl) * (2^59 - 1) > 2^64
76 this would exceed the address space of the machine. */