1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
|
/* Sequential list data type implemented by a binary tree.
Copyright (C) 2006 Free Software Foundation, Inc.
Written by Bruno Haible <bruno@clisp.org>, 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 3 of the License, 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, see <http://www.gnu.org/licenses/>. */
/* 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
|
