octave-jordi/gnulib-hg: lib/gl_rbtree

annotate lib/gl_rbtree_oset.c @ 14858:dd10bbc31f53

Copyright: Use LGPL 2.1 instead of LGPL 2.0. * lib/localename.h: Update copyright header. * lib/localename.c: Likewise. * lib/relocatable.h: Likewise. * lib/relocatable.c: Likewise.

author	Bruno Haible <bruno@clisp.org>
date	Fri, 03 Jun 2011 14:21:08 +0200
parents	97fc9a21a8fb
children	8250f2777afc

rev	line source
6982 d88d781b8e7b Ordered set data type implemented by a binary tree. Bruno Haible <bruno@clisp.org> parents: diff changeset	1 /* Ordered set data type implemented by a binary tree.
14079 97fc9a21a8fb maint: update almost all copyright ranges to include 2011 Jim Meyering <meyering@redhat.com> parents: 12559 diff changeset	2 Copyright (C) 2006-2007, 2009-2011 Free Software Foundation, Inc.
6982 d88d781b8e7b Ordered set data type implemented by a binary tree. Bruno Haible <bruno@clisp.org> parents: diff changeset	3 Written by Bruno Haible <bruno@clisp.org>, 2006.
d88d781b8e7b Ordered set data type implemented by a binary tree. Bruno Haible <bruno@clisp.org> parents: diff changeset	4
9309 bbbbbf4cd1c5 Change copyright notice from GPLv2+ to GPLv3+. Bruno Haible <bruno@clisp.org> parents: 8436 diff changeset	5 This program is free software: you can redistribute it and/or modify
6982 d88d781b8e7b Ordered set data type implemented by a binary tree. Bruno Haible <bruno@clisp.org> parents: diff changeset	6 it under the terms of the GNU General Public License as published by
9309 bbbbbf4cd1c5 Change copyright notice from GPLv2+ to GPLv3+. Bruno Haible <bruno@clisp.org> parents: 8436 diff changeset	7 the Free Software Foundation; either version 3 of the License, or
bbbbbf4cd1c5 Change copyright notice from GPLv2+ to GPLv3+. Bruno Haible <bruno@clisp.org> parents: 8436 diff changeset	8 (at your option) any later version.
6982 d88d781b8e7b Ordered set data type implemented by a binary tree. Bruno Haible <bruno@clisp.org> parents: diff changeset	9
d88d781b8e7b Ordered set data type implemented by a binary tree. Bruno Haible <bruno@clisp.org> parents: diff changeset	10 This program is distributed in the hope that it will be useful,
d88d781b8e7b Ordered set data type implemented by a binary tree. Bruno Haible <bruno@clisp.org> parents: diff changeset	11 but WITHOUT ANY WARRANTY; without even the implied warranty of
d88d781b8e7b Ordered set data type implemented by a binary tree. Bruno Haible <bruno@clisp.org> parents: diff changeset	12 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
d88d781b8e7b Ordered set data type implemented by a binary tree. Bruno Haible <bruno@clisp.org> parents: diff changeset	13 GNU General Public License for more details.
d88d781b8e7b Ordered set data type implemented by a binary tree. Bruno Haible <bruno@clisp.org> parents: diff changeset	14
d88d781b8e7b Ordered set data type implemented by a binary tree. Bruno Haible <bruno@clisp.org> parents: diff changeset	15 You should have received a copy of the GNU General Public License
9309 bbbbbf4cd1c5 Change copyright notice from GPLv2+ to GPLv3+. Bruno Haible <bruno@clisp.org> parents: 8436 diff changeset	16 along with this program. If not, see <http://www.gnu.org/licenses/>. */
6982 d88d781b8e7b Ordered set data type implemented by a binary tree. Bruno Haible <bruno@clisp.org> parents: diff changeset	17
7304 1c4ed7637c24 Include <config.h> unconditionally. Bruno Haible <bruno@clisp.org> parents: 6982 diff changeset	18 #include <config.h>
6982 d88d781b8e7b Ordered set data type implemented by a binary tree. Bruno Haible <bruno@clisp.org> parents: diff changeset	19
d88d781b8e7b Ordered set data type implemented by a binary tree. Bruno Haible <bruno@clisp.org> parents: diff changeset	20 /* Specification. */
d88d781b8e7b Ordered set data type implemented by a binary tree. Bruno Haible <bruno@clisp.org> parents: diff changeset	21 #include "gl_rbtree_oset.h"
d88d781b8e7b Ordered set data type implemented by a binary tree. Bruno Haible <bruno@clisp.org> parents: diff changeset	22
d88d781b8e7b Ordered set data type implemented by a binary tree. Bruno Haible <bruno@clisp.org> parents: diff changeset	23 #include <stdlib.h>
d88d781b8e7b Ordered set data type implemented by a binary tree. Bruno Haible <bruno@clisp.org> parents: diff changeset	24
d88d781b8e7b Ordered set data type implemented by a binary tree. Bruno Haible <bruno@clisp.org> parents: diff changeset	25 /* A red-black tree is a binary tree where every node is colored black or
d88d781b8e7b Ordered set data type implemented by a binary tree. Bruno Haible <bruno@clisp.org> parents: diff changeset	26 red such that
d88d781b8e7b Ordered set data type implemented by a binary tree. Bruno Haible <bruno@clisp.org> parents: diff changeset	27 1. The root is black.
d88d781b8e7b Ordered set data type implemented by a binary tree. Bruno Haible <bruno@clisp.org> parents: diff changeset	28 2. No red node has a red parent.
d88d781b8e7b Ordered set data type implemented by a binary tree. Bruno Haible <bruno@clisp.org> parents: diff changeset	29 Or equivalently: No red node has a red child.
d88d781b8e7b Ordered set data type implemented by a binary tree. Bruno Haible <bruno@clisp.org> parents: diff changeset	30 3. All paths from the root down to any NULL endpoint contain the same
d88d781b8e7b Ordered set data type implemented by a binary tree. Bruno Haible <bruno@clisp.org> parents: diff changeset	31 number of black nodes.
d88d781b8e7b Ordered set data type implemented by a binary tree. Bruno Haible <bruno@clisp.org> parents: diff changeset	32 Let's call this the "black-height" bh of the tree. It follows that every
d88d781b8e7b Ordered set data type implemented by a binary tree. Bruno Haible <bruno@clisp.org> parents: diff changeset	33 such path contains exactly bh black and between 0 and bh red nodes. (The
d88d781b8e7b Ordered set data type implemented by a binary tree. Bruno Haible <bruno@clisp.org> parents: diff changeset	34 extreme cases are a path containing only black nodes, and a path colored
d88d781b8e7b Ordered set data type implemented by a binary tree. Bruno Haible <bruno@clisp.org> parents: diff changeset	35 alternatingly black-red-black-red-...-black-red.) The height of the tree
d88d781b8e7b Ordered set data type implemented by a binary tree. Bruno Haible <bruno@clisp.org> parents: diff changeset	36 therefore is >= bh, <= 2*bh.
d88d781b8e7b Ordered set data type implemented by a binary tree. Bruno Haible <bruno@clisp.org> parents: diff changeset	37 */
d88d781b8e7b Ordered set data type implemented by a binary tree. Bruno Haible <bruno@clisp.org> parents: diff changeset	38
d88d781b8e7b Ordered set data type implemented by a binary tree. Bruno Haible <bruno@clisp.org> parents: diff changeset	39 /* -------------------------- gl_oset_t Data Type -------------------------- */
d88d781b8e7b Ordered set data type implemented by a binary tree. Bruno Haible <bruno@clisp.org> parents: diff changeset	40
d88d781b8e7b Ordered set data type implemented by a binary tree. Bruno Haible <bruno@clisp.org> parents: diff changeset	41 /* Color of a node. */
d88d781b8e7b Ordered set data type implemented by a binary tree. Bruno Haible <bruno@clisp.org> parents: diff changeset	42 typedef enum color { BLACK, RED } color_t;
d88d781b8e7b Ordered set data type implemented by a binary tree. Bruno Haible <bruno@clisp.org> parents: diff changeset	43
d88d781b8e7b Ordered set data type implemented by a binary tree. Bruno Haible <bruno@clisp.org> parents: diff changeset	44 /* Tree node implementation, valid for this file only. */
d88d781b8e7b Ordered set data type implemented by a binary tree. Bruno Haible <bruno@clisp.org> parents: diff changeset	45 struct gl_oset_node_impl
d88d781b8e7b Ordered set data type implemented by a binary tree. Bruno Haible <bruno@clisp.org> parents: diff changeset	46 {
d88d781b8e7b Ordered set data type implemented by a binary tree. Bruno Haible <bruno@clisp.org> parents: diff changeset	47 struct gl_oset_node_impl left; / left branch, or NULL */
d88d781b8e7b Ordered set data type implemented by a binary tree. Bruno Haible <bruno@clisp.org> parents: diff changeset	48 struct gl_oset_node_impl right; / right branch, or NULL */
d88d781b8e7b Ordered set data type implemented by a binary tree. Bruno Haible <bruno@clisp.org> parents: diff changeset	49 /* Parent pointer, or NULL. The parent pointer is not needed for most
d88d781b8e7b Ordered set data type implemented by a binary tree. Bruno Haible <bruno@clisp.org> parents: diff changeset	50 operations. It is needed so that a gl_oset_node_t can be returned
d88d781b8e7b Ordered set data type implemented by a binary tree. Bruno Haible <bruno@clisp.org> parents: diff changeset	51 without memory allocation, on which the functions gl_oset_remove_node,
d88d781b8e7b Ordered set data type implemented by a binary tree. Bruno Haible <bruno@clisp.org> parents: diff changeset	52 gl_oset_add_before, gl_oset_add_after can be implemented. */
d88d781b8e7b Ordered set data type implemented by a binary tree. Bruno Haible <bruno@clisp.org> parents: diff changeset	53 struct gl_oset_node_impl *parent;
d88d781b8e7b Ordered set data type implemented by a binary tree. Bruno Haible <bruno@clisp.org> parents: diff changeset	54 color_t color; /* node's color */
d88d781b8e7b Ordered set data type implemented by a binary tree. Bruno Haible <bruno@clisp.org> parents: diff changeset	55 const void *value;
d88d781b8e7b Ordered set data type implemented by a binary tree. Bruno Haible <bruno@clisp.org> parents: diff changeset	56 };
d88d781b8e7b Ordered set data type implemented by a binary tree. Bruno Haible <bruno@clisp.org> parents: diff changeset	57 typedef struct gl_oset_node_impl * gl_oset_node_t;
d88d781b8e7b Ordered set data type implemented by a binary tree. Bruno Haible <bruno@clisp.org> parents: diff changeset	58
d88d781b8e7b Ordered set data type implemented by a binary tree. Bruno Haible <bruno@clisp.org> parents: diff changeset	59 /* Concrete gl_oset_impl type, valid for this file only. */
d88d781b8e7b Ordered set data type implemented by a binary tree. Bruno Haible <bruno@clisp.org> parents: diff changeset	60 struct gl_oset_impl
d88d781b8e7b Ordered set data type implemented by a binary tree. Bruno Haible <bruno@clisp.org> parents: diff changeset	61 {
d88d781b8e7b Ordered set data type implemented by a binary tree. Bruno Haible <bruno@clisp.org> parents: diff changeset	62 struct gl_oset_impl_base base;
d88d781b8e7b Ordered set data type implemented by a binary tree. Bruno Haible <bruno@clisp.org> parents: diff changeset	63 struct gl_oset_node_impl root; / root node or NULL */
d88d781b8e7b Ordered set data type implemented by a binary tree. Bruno Haible <bruno@clisp.org> parents: diff changeset	64 size_t count; /* number of nodes */
d88d781b8e7b Ordered set data type implemented by a binary tree. Bruno Haible <bruno@clisp.org> parents: diff changeset	65 };
d88d781b8e7b Ordered set data type implemented by a binary tree. Bruno Haible <bruno@clisp.org> parents: diff changeset	66
d88d781b8e7b Ordered set data type implemented by a binary tree. Bruno Haible <bruno@clisp.org> parents: diff changeset	67 /* A red-black tree of height h has a black-height bh >= ceil(h/2) and
d88d781b8e7b Ordered set data type implemented by a binary tree. Bruno Haible <bruno@clisp.org> parents: diff changeset	68 therefore at least 2^ceil(h/2) - 1 elements. So, h <= 116 (because a tree
d88d781b8e7b Ordered set data type implemented by a binary tree. Bruno Haible <bruno@clisp.org> parents: diff changeset	69 of height h >= 117 would have at least 2^59 - 1 elements, and because even
d88d781b8e7b Ordered set data type implemented by a binary tree. Bruno Haible <bruno@clisp.org> parents: diff changeset	70 on 64-bit machines,
d88d781b8e7b Ordered set data type implemented by a binary tree. Bruno Haible <bruno@clisp.org> parents: diff changeset	71 sizeof (gl_oset_node_impl) * (2^59 - 1) > 2^64
d88d781b8e7b Ordered set data type implemented by a binary tree. Bruno Haible <bruno@clisp.org> parents: diff changeset	72 this would exceed the address space of the machine. */
d88d781b8e7b Ordered set data type implemented by a binary tree. Bruno Haible <bruno@clisp.org> parents: diff changeset	73 #define MAXHEIGHT 116
d88d781b8e7b Ordered set data type implemented by a binary tree. Bruno Haible <bruno@clisp.org> parents: diff changeset	74
d88d781b8e7b Ordered set data type implemented by a binary tree. Bruno Haible <bruno@clisp.org> parents: diff changeset	75 /* Rotate left a subtree.
d88d781b8e7b Ordered set data type implemented by a binary tree. Bruno Haible <bruno@clisp.org> parents: diff changeset	76
12421 e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9309 diff changeset	77 B D
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9309 diff changeset	78 / \ / \
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9309 diff changeset	79 A D --> B E
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9309 diff changeset	80 / \ / \
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9309 diff changeset	81 C E A C
6982 d88d781b8e7b Ordered set data type implemented by a binary tree. Bruno Haible <bruno@clisp.org> parents: diff changeset	82
d88d781b8e7b Ordered set data type implemented by a binary tree. Bruno Haible <bruno@clisp.org> parents: diff changeset	83 Change the tree structure, update the branch sizes.
d88d781b8e7b Ordered set data type implemented by a binary tree. Bruno Haible <bruno@clisp.org> parents: diff changeset	84 The caller must update the colors and register D as child of its parent. */
d88d781b8e7b Ordered set data type implemented by a binary tree. Bruno Haible <bruno@clisp.org> parents: diff changeset	85 static inline gl_oset_node_t
d88d781b8e7b Ordered set data type implemented by a binary tree. Bruno Haible <bruno@clisp.org> parents: diff changeset	86 rotate_left (gl_oset_node_t b_node, gl_oset_node_t d_node)
d88d781b8e7b Ordered set data type implemented by a binary tree. Bruno Haible <bruno@clisp.org> parents: diff changeset	87 {
d88d781b8e7b Ordered set data type implemented by a binary tree. Bruno Haible <bruno@clisp.org> parents: diff changeset	88 gl_oset_node_t c_node = d_node->left;
d88d781b8e7b Ordered set data type implemented by a binary tree. Bruno Haible <bruno@clisp.org> parents: diff changeset	89
d88d781b8e7b Ordered set data type implemented by a binary tree. Bruno Haible <bruno@clisp.org> parents: diff changeset	90 b_node->right = c_node;
d88d781b8e7b Ordered set data type implemented by a binary tree. Bruno Haible <bruno@clisp.org> parents: diff changeset	91 d_node->left = b_node;
d88d781b8e7b Ordered set data type implemented by a binary tree. Bruno Haible <bruno@clisp.org> parents: diff changeset	92
d88d781b8e7b Ordered set data type implemented by a binary tree. Bruno Haible <bruno@clisp.org> parents: diff changeset	93 d_node->parent = b_node->parent;
d88d781b8e7b Ordered set data type implemented by a binary tree. Bruno Haible <bruno@clisp.org> parents: diff changeset	94 b_node->parent = d_node;
d88d781b8e7b Ordered set data type implemented by a binary tree. Bruno Haible <bruno@clisp.org> parents: diff changeset	95 if (c_node != NULL)
d88d781b8e7b Ordered set data type implemented by a binary tree. Bruno Haible <bruno@clisp.org> parents: diff changeset	96 c_node->parent = b_node;
d88d781b8e7b Ordered set data type implemented by a binary tree. Bruno Haible <bruno@clisp.org> parents: diff changeset	97
d88d781b8e7b Ordered set data type implemented by a binary tree. Bruno Haible <bruno@clisp.org> parents: diff changeset	98 return d_node;
d88d781b8e7b Ordered set data type implemented by a binary tree. Bruno Haible <bruno@clisp.org> parents: diff changeset	99 }
d88d781b8e7b Ordered set data type implemented by a binary tree. Bruno Haible <bruno@clisp.org> parents: diff changeset	100
d88d781b8e7b Ordered set data type implemented by a binary tree. Bruno Haible <bruno@clisp.org> parents: diff changeset	101 /* Rotate right a subtree.
d88d781b8e7b Ordered set data type implemented by a binary tree. Bruno Haible <bruno@clisp.org> parents: diff changeset	102
12421 e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9309 diff changeset	103 D B
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9309 diff changeset	104 / \ / \
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9309 diff changeset	105 B E --> A D
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9309 diff changeset	106 / \ / \
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9309 diff changeset	107 A C C E
6982 d88d781b8e7b Ordered set data type implemented by a binary tree. Bruno Haible <bruno@clisp.org> parents: diff changeset	108
d88d781b8e7b Ordered set data type implemented by a binary tree. Bruno Haible <bruno@clisp.org> parents: diff changeset	109 Change the tree structure, update the branch sizes.
d88d781b8e7b Ordered set data type implemented by a binary tree. Bruno Haible <bruno@clisp.org> parents: diff changeset	110 The caller must update the colors and register B as child of its parent. */
d88d781b8e7b Ordered set data type implemented by a binary tree. Bruno Haible <bruno@clisp.org> parents: diff changeset	111 static inline gl_oset_node_t
d88d781b8e7b Ordered set data type implemented by a binary tree. Bruno Haible <bruno@clisp.org> parents: diff changeset	112 rotate_right (gl_oset_node_t b_node, gl_oset_node_t d_node)
d88d781b8e7b Ordered set data type implemented by a binary tree. Bruno Haible <bruno@clisp.org> parents: diff changeset	113 {
d88d781b8e7b Ordered set data type implemented by a binary tree. Bruno Haible <bruno@clisp.org> parents: diff changeset	114 gl_oset_node_t c_node = b_node->right;
d88d781b8e7b Ordered set data type implemented by a binary tree. Bruno Haible <bruno@clisp.org> parents: diff changeset	115
d88d781b8e7b Ordered set data type implemented by a binary tree. Bruno Haible <bruno@clisp.org> parents: diff changeset	116 d_node->left = c_node;
d88d781b8e7b Ordered set data type implemented by a binary tree. Bruno Haible <bruno@clisp.org> parents: diff changeset	117 b_node->right = d_node;
d88d781b8e7b Ordered set data type implemented by a binary tree. Bruno Haible <bruno@clisp.org> parents: diff changeset	118
d88d781b8e7b Ordered set data type implemented by a binary tree. Bruno Haible <bruno@clisp.org> parents: diff changeset	119 b_node->parent = d_node->parent;
d88d781b8e7b Ordered set data type implemented by a binary tree. Bruno Haible <bruno@clisp.org> parents: diff changeset	120 d_node->parent = b_node;
d88d781b8e7b Ordered set data type implemented by a binary tree. Bruno Haible <bruno@clisp.org> parents: diff changeset	121 if (c_node != NULL)
d88d781b8e7b Ordered set data type implemented by a binary tree. Bruno Haible <bruno@clisp.org> parents: diff changeset	122 c_node->parent = d_node;
d88d781b8e7b Ordered set data type implemented by a binary tree. Bruno Haible <bruno@clisp.org> parents: diff changeset	123
d88d781b8e7b Ordered set data type implemented by a binary tree. Bruno Haible <bruno@clisp.org> parents: diff changeset	124 return b_node;
d88d781b8e7b Ordered set data type implemented by a binary tree. Bruno Haible <bruno@clisp.org> parents: diff changeset	125 }
d88d781b8e7b Ordered set data type implemented by a binary tree. Bruno Haible <bruno@clisp.org> parents: diff changeset	126
d88d781b8e7b Ordered set data type implemented by a binary tree. Bruno Haible <bruno@clisp.org> parents: diff changeset	127 /* Ensure the tree is balanced, after an insertion operation.
d88d781b8e7b Ordered set data type implemented by a binary tree. Bruno Haible <bruno@clisp.org> parents: diff changeset	128 Also assigns node->color.
d88d781b8e7b Ordered set data type implemented by a binary tree. Bruno Haible <bruno@clisp.org> parents: diff changeset	129 parent is the given node's parent, known to be non-NULL. */
d88d781b8e7b Ordered set data type implemented by a binary tree. Bruno Haible <bruno@clisp.org> parents: diff changeset	130 static void
d88d781b8e7b Ordered set data type implemented by a binary tree. Bruno Haible <bruno@clisp.org> parents: diff changeset	131 rebalance_after_add (gl_oset_t set, gl_oset_node_t node, gl_oset_node_t parent)
d88d781b8e7b Ordered set data type implemented by a binary tree. Bruno Haible <bruno@clisp.org> parents: diff changeset	132 {
d88d781b8e7b Ordered set data type implemented by a binary tree. Bruno Haible <bruno@clisp.org> parents: diff changeset	133 for (;;)
d88d781b8e7b Ordered set data type implemented by a binary tree. Bruno Haible <bruno@clisp.org> parents: diff changeset	134 {
d88d781b8e7b Ordered set data type implemented by a binary tree. Bruno Haible <bruno@clisp.org> parents: diff changeset	135 /* At this point, parent = node->parent != NULL.
12421 e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9309 diff changeset	136 Think of node->color being RED (although node->color is not yet
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9309 diff changeset	137 assigned.) */
6982 d88d781b8e7b Ordered set data type implemented by a binary tree. Bruno Haible <bruno@clisp.org> parents: diff changeset	138 gl_oset_node_t grandparent;
d88d781b8e7b Ordered set data type implemented by a binary tree. Bruno Haible <bruno@clisp.org> parents: diff changeset	139 gl_oset_node_t uncle;
d88d781b8e7b Ordered set data type implemented by a binary tree. Bruno Haible <bruno@clisp.org> parents: diff changeset	140
d88d781b8e7b Ordered set data type implemented by a binary tree. Bruno Haible <bruno@clisp.org> parents: diff changeset	141 if (parent->color == BLACK)
12421 e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9309 diff changeset	142 {
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9309 diff changeset	143 /* A RED color for node is acceptable. */
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9309 diff changeset	144 node->color = RED;
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9309 diff changeset	145 return;
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9309 diff changeset	146 }
6982 d88d781b8e7b Ordered set data type implemented by a binary tree. Bruno Haible <bruno@clisp.org> parents: diff changeset	147
d88d781b8e7b Ordered set data type implemented by a binary tree. Bruno Haible <bruno@clisp.org> parents: diff changeset	148 grandparent = parent->parent;
d88d781b8e7b Ordered set data type implemented by a binary tree. Bruno Haible <bruno@clisp.org> parents: diff changeset	149 /* Since parent is RED, we know that
12421 e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9309 diff changeset	150 grandparent is != NULL and colored BLACK. */
6982 d88d781b8e7b Ordered set data type implemented by a binary tree. Bruno Haible <bruno@clisp.org> parents: diff changeset	151
d88d781b8e7b Ordered set data type implemented by a binary tree. Bruno Haible <bruno@clisp.org> parents: diff changeset	152 if (grandparent->left == parent)
12421 e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9309 diff changeset	153 uncle = grandparent->right;
6982 d88d781b8e7b Ordered set data type implemented by a binary tree. Bruno Haible <bruno@clisp.org> parents: diff changeset	154 else if (grandparent->right == parent)
12421 e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9309 diff changeset	155 uncle = grandparent->left;
6982 d88d781b8e7b Ordered set data type implemented by a binary tree. Bruno Haible <bruno@clisp.org> parents: diff changeset	156 else
12421 e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9309 diff changeset	157 abort ();
6982 d88d781b8e7b Ordered set data type implemented by a binary tree. Bruno Haible <bruno@clisp.org> parents: diff changeset	158
d88d781b8e7b Ordered set data type implemented by a binary tree. Bruno Haible <bruno@clisp.org> parents: diff changeset	159 if (uncle != NULL && uncle->color == RED)
12421 e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9309 diff changeset	160 {
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9309 diff changeset	161 /* Change grandparent from BLACK to RED, and
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9309 diff changeset	162 change parent and uncle from RED to BLACK.
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9309 diff changeset	163 This makes it acceptable for node to be RED. */
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9309 diff changeset	164 node->color = RED;
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9309 diff changeset	165 parent->color = uncle->color = BLACK;
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9309 diff changeset	166 node = grandparent;
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9309 diff changeset	167 }
6982 d88d781b8e7b Ordered set data type implemented by a binary tree. Bruno Haible <bruno@clisp.org> parents: diff changeset	168 else
12421 e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9309 diff changeset	169 {
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9309 diff changeset	170 /* grandparent and uncle are BLACK. parent is RED. node wants
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9309 diff changeset	171 to be RED too.
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9309 diff changeset	172 In this case, recoloring is not sufficient. Need to perform
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9309 diff changeset	173 one or two rotations. */
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9309 diff changeset	174 gl_oset_node_t *grandparentp;
6982 d88d781b8e7b Ordered set data type implemented by a binary tree. Bruno Haible <bruno@clisp.org> parents: diff changeset	175
12421 e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9309 diff changeset	176 if (grandparent->parent == NULL)
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9309 diff changeset	177 grandparentp = &set->root;
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9309 diff changeset	178 else if (grandparent->parent->left == grandparent)
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9309 diff changeset	179 grandparentp = &grandparent->parent->left;
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9309 diff changeset	180 else if (grandparent->parent->right == grandparent)
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9309 diff changeset	181 grandparentp = &grandparent->parent->right;
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9309 diff changeset	182 else
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9309 diff changeset	183 abort ();
6982 d88d781b8e7b Ordered set data type implemented by a binary tree. Bruno Haible <bruno@clisp.org> parents: diff changeset	184
12421 e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9309 diff changeset	185 if (grandparent->left == parent)
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9309 diff changeset	186 {
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9309 diff changeset	187 if (parent->right == node)
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9309 diff changeset	188 {
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9309 diff changeset	189 /* Rotation between node and parent. */
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9309 diff changeset	190 grandparent->left = rotate_left (parent, node);
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9309 diff changeset	191 node = parent;
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9309 diff changeset	192 parent = grandparent->left;
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9309 diff changeset	193 }
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9309 diff changeset	194 /* grandparent and uncle are BLACK. parent and node want to be
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9309 diff changeset	195 RED. parent = grandparent->left. node = parent->left.
6982 d88d781b8e7b Ordered set data type implemented by a binary tree. Bruno Haible <bruno@clisp.org> parents: diff changeset	196
12421 e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9309 diff changeset	197 grandparent parent
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9309 diff changeset	198 bh+1 bh+1
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9309 diff changeset	199 / \ / \
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9309 diff changeset	200 parent uncle --> node grandparent
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9309 diff changeset	201 bh bh bh bh
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9309 diff changeset	202 / \ / \
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9309 diff changeset	203 node C C uncle
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9309 diff changeset	204 bh bh bh bh
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9309 diff changeset	205 */
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9309 diff changeset	206 *grandparentp = rotate_right (parent, grandparent);
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9309 diff changeset	207 parent->color = BLACK;
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9309 diff changeset	208 node->color = grandparent->color = RED;
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9309 diff changeset	209 }
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9309 diff changeset	210 else /* grandparent->right == parent */
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9309 diff changeset	211 {
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9309 diff changeset	212 if (parent->left == node)
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9309 diff changeset	213 {
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9309 diff changeset	214 /* Rotation between node and parent. */
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9309 diff changeset	215 grandparent->right = rotate_right (node, parent);
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9309 diff changeset	216 node = parent;
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9309 diff changeset	217 parent = grandparent->right;
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9309 diff changeset	218 }
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9309 diff changeset	219 /* grandparent and uncle are BLACK. parent and node want to be
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9309 diff changeset	220 RED. parent = grandparent->right. node = parent->right.
6982 d88d781b8e7b Ordered set data type implemented by a binary tree. Bruno Haible <bruno@clisp.org> parents: diff changeset	221
12421 e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9309 diff changeset	222 grandparent parent
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9309 diff changeset	223 bh+1 bh+1
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9309 diff changeset	224 / \ / \
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9309 diff changeset	225 uncle parent --> grandparent node
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9309 diff changeset	226 bh bh bh bh
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9309 diff changeset	227 / \ / \
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9309 diff changeset	228 C node uncle C
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9309 diff changeset	229 bh bh bh bh
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9309 diff changeset	230 */
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9309 diff changeset	231 *grandparentp = rotate_left (grandparent, parent);
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9309 diff changeset	232 parent->color = BLACK;
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9309 diff changeset	233 node->color = grandparent->color = RED;
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9309 diff changeset	234 }
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9309 diff changeset	235 return;
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9309 diff changeset	236 }
6982 d88d781b8e7b Ordered set data type implemented by a binary tree. Bruno Haible <bruno@clisp.org> parents: diff changeset	237
d88d781b8e7b Ordered set data type implemented by a binary tree. Bruno Haible <bruno@clisp.org> parents: diff changeset	238 /* Start again with a new (node, parent) pair. */
d88d781b8e7b Ordered set data type implemented by a binary tree. Bruno Haible <bruno@clisp.org> parents: diff changeset	239 parent = node->parent;
d88d781b8e7b Ordered set data type implemented by a binary tree. Bruno Haible <bruno@clisp.org> parents: diff changeset	240
d88d781b8e7b Ordered set data type implemented by a binary tree. Bruno Haible <bruno@clisp.org> parents: diff changeset	241 if (parent == NULL)
12421 e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9309 diff changeset	242 {
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9309 diff changeset	243 /* Change node's color from RED to BLACK. This increases the
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9309 diff changeset	244 tree's black-height. */
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9309 diff changeset	245 node->color = BLACK;
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9309 diff changeset	246 return;
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9309 diff changeset	247 }
6982 d88d781b8e7b Ordered set data type implemented by a binary tree. Bruno Haible <bruno@clisp.org> parents: diff changeset	248 }
d88d781b8e7b Ordered set data type implemented by a binary tree. Bruno Haible <bruno@clisp.org> parents: diff changeset	249 }
d88d781b8e7b Ordered set data type implemented by a binary tree. Bruno Haible <bruno@clisp.org> parents: diff changeset	250
d88d781b8e7b Ordered set data type implemented by a binary tree. Bruno Haible <bruno@clisp.org> parents: diff changeset	251 /* Ensure the tree is balanced, after a deletion operation.
d88d781b8e7b Ordered set data type implemented by a binary tree. Bruno Haible <bruno@clisp.org> parents: diff changeset	252 CHILD was a grandchild of PARENT and is now its child. Between them,
d88d781b8e7b Ordered set data type implemented by a binary tree. Bruno Haible <bruno@clisp.org> parents: diff changeset	253 a black node was removed. CHILD is also black, or NULL.
d88d781b8e7b Ordered set data type implemented by a binary tree. Bruno Haible <bruno@clisp.org> parents: diff changeset	254 (CHILD can also be NULL. But PARENT is non-NULL.) */
d88d781b8e7b Ordered set data type implemented by a binary tree. Bruno Haible <bruno@clisp.org> parents: diff changeset	255 static void
d88d781b8e7b Ordered set data type implemented by a binary tree. Bruno Haible <bruno@clisp.org> parents: diff changeset	256 rebalance_after_remove (gl_oset_t set, gl_oset_node_t child, gl_oset_node_t parent)
d88d781b8e7b Ordered set data type implemented by a binary tree. Bruno Haible <bruno@clisp.org> parents: diff changeset	257 {
d88d781b8e7b Ordered set data type implemented by a binary tree. Bruno Haible <bruno@clisp.org> parents: diff changeset	258 for (;;)
d88d781b8e7b Ordered set data type implemented by a binary tree. Bruno Haible <bruno@clisp.org> parents: diff changeset	259 {
d88d781b8e7b Ordered set data type implemented by a binary tree. Bruno Haible <bruno@clisp.org> parents: diff changeset	260 /* At this point, we reduced the black-height of the CHILD subtree by 1.
12421 e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9309 diff changeset	261 To make up, either look for a possibility to turn a RED to a BLACK
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9309 diff changeset	262 node, or try to reduce the black-height tree of CHILD's sibling
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9309 diff changeset	263 subtree as well. */
6982 d88d781b8e7b Ordered set data type implemented by a binary tree. Bruno Haible <bruno@clisp.org> parents: diff changeset	264 gl_oset_node_t *parentp;
d88d781b8e7b Ordered set data type implemented by a binary tree. Bruno Haible <bruno@clisp.org> parents: diff changeset	265
d88d781b8e7b Ordered set data type implemented by a binary tree. Bruno Haible <bruno@clisp.org> parents: diff changeset	266 if (parent->parent == NULL)
12421 e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9309 diff changeset	267 parentp = &set->root;
6982 d88d781b8e7b Ordered set data type implemented by a binary tree. Bruno Haible <bruno@clisp.org> parents: diff changeset	268 else if (parent->parent->left == parent)
12421 e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9309 diff changeset	269 parentp = &parent->parent->left;
6982 d88d781b8e7b Ordered set data type implemented by a binary tree. Bruno Haible <bruno@clisp.org> parents: diff changeset	270 else if (parent->parent->right == parent)
12421 e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9309 diff changeset	271 parentp = &parent->parent->right;
6982 d88d781b8e7b Ordered set data type implemented by a binary tree. Bruno Haible <bruno@clisp.org> parents: diff changeset	272 else
12421 e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9309 diff changeset	273 abort ();
6982 d88d781b8e7b Ordered set data type implemented by a binary tree. Bruno Haible <bruno@clisp.org> parents: diff changeset	274
d88d781b8e7b Ordered set data type implemented by a binary tree. Bruno Haible <bruno@clisp.org> parents: diff changeset	275 if (parent->left == child)
12421 e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9309 diff changeset	276 {
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9309 diff changeset	277 gl_oset_node_t sibling = parent->right;
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9309 diff changeset	278 /* sibling's black-height is >= 1. In particular,
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9309 diff changeset	279 sibling != NULL.
6982 d88d781b8e7b Ordered set data type implemented by a binary tree. Bruno Haible <bruno@clisp.org> parents: diff changeset	280
12421 e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9309 diff changeset	281 parent
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9309 diff changeset	282 / \
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9309 diff changeset	283 child sibling
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9309 diff changeset	284 bh bh+1
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9309 diff changeset	285 */
6982 d88d781b8e7b Ordered set data type implemented by a binary tree. Bruno Haible <bruno@clisp.org> parents: diff changeset	286
12421 e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9309 diff changeset	287 if (sibling->color == RED)
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9309 diff changeset	288 {
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9309 diff changeset	289 /* sibling is RED, hence parent is BLACK and sibling's children
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9309 diff changeset	290 are non-NULL and BLACK.
6982 d88d781b8e7b Ordered set data type implemented by a binary tree. Bruno Haible <bruno@clisp.org> parents: diff changeset	291
12421 e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9309 diff changeset	292 parent sibling
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9309 diff changeset	293 bh+2 bh+2
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9309 diff changeset	294 / \ / \
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9309 diff changeset	295 child sibling --> parent SR
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9309 diff changeset	296 bh bh+1 bh+1 bh+1
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9309 diff changeset	297 / \ / \
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9309 diff changeset	298 SL SR child SL
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9309 diff changeset	299 bh+1 bh+1 bh bh+1
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9309 diff changeset	300 */
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9309 diff changeset	301 *parentp = rotate_left (parent, sibling);
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9309 diff changeset	302 parent->color = RED;
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9309 diff changeset	303 sibling->color = BLACK;
6982 d88d781b8e7b Ordered set data type implemented by a binary tree. Bruno Haible <bruno@clisp.org> parents: diff changeset	304
12421 e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9309 diff changeset	305 /* Concentrate on the subtree of parent. The new sibling is
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9309 diff changeset	306 one of the old sibling's children, and known to be BLACK. */
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9309 diff changeset	307 parentp = &sibling->left;
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9309 diff changeset	308 sibling = parent->right;
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9309 diff changeset	309 }
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9309 diff changeset	310 /* Now we know that sibling is BLACK.
6982 d88d781b8e7b Ordered set data type implemented by a binary tree. Bruno Haible <bruno@clisp.org> parents: diff changeset	311
12421 e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9309 diff changeset	312 parent
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9309 diff changeset	313 / \
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9309 diff changeset	314 child sibling
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9309 diff changeset	315 bh bh+1
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9309 diff changeset	316 */
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9309 diff changeset	317 if (sibling->right != NULL && sibling->right->color == RED)
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9309 diff changeset	318 {
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9309 diff changeset	319 /*
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9309 diff changeset	320 parent sibling
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9309 diff changeset	321 bh+1\|bh+2 bh+1\|bh+2
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9309 diff changeset	322 / \ / \
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9309 diff changeset	323 child sibling --> parent SR
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9309 diff changeset	324 bh bh+1 bh+1 bh+1
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9309 diff changeset	325 / \ / \
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9309 diff changeset	326 SL SR child SL
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9309 diff changeset	327 bh bh bh bh
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9309 diff changeset	328 */
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9309 diff changeset	329 *parentp = rotate_left (parent, sibling);
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9309 diff changeset	330 sibling->color = parent->color;
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9309 diff changeset	331 parent->color = BLACK;
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9309 diff changeset	332 sibling->right->color = BLACK;
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9309 diff changeset	333 return;
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9309 diff changeset	334 }
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9309 diff changeset	335 else if (sibling->left != NULL && sibling->left->color == RED)
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9309 diff changeset	336 {
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9309 diff changeset	337 /*
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9309 diff changeset	338 parent parent
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9309 diff changeset	339 bh+1\|bh+2 bh+1\|bh+2
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9309 diff changeset	340 / \ / \
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9309 diff changeset	341 child sibling --> child SL
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9309 diff changeset	342 bh bh+1 bh bh+1
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9309 diff changeset	343 / \ / \
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9309 diff changeset	344 SL SR SLL sibling
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9309 diff changeset	345 bh bh bh bh
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9309 diff changeset	346 / \ / \
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9309 diff changeset	347 SLL SLR SLR SR
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9309 diff changeset	348 bh bh bh bh
6982 d88d781b8e7b Ordered set data type implemented by a binary tree. Bruno Haible <bruno@clisp.org> parents: diff changeset	349
12421 e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9309 diff changeset	350 where SLL, SLR, SR are all black.
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9309 diff changeset	351 */
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9309 diff changeset	352 parent->right = rotate_right (sibling->left, sibling);
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9309 diff changeset	353 /* Change sibling from BLACK to RED and SL from RED to BLACK. */
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9309 diff changeset	354 sibling->color = RED;
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9309 diff changeset	355 sibling = parent->right;
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9309 diff changeset	356 sibling->color = BLACK;
6982 d88d781b8e7b Ordered set data type implemented by a binary tree. Bruno Haible <bruno@clisp.org> parents: diff changeset	357
12421 e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9309 diff changeset	358 /* Now do as in the previous case. */
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9309 diff changeset	359 *parentp = rotate_left (parent, sibling);
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9309 diff changeset	360 sibling->color = parent->color;
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9309 diff changeset	361 parent->color = BLACK;
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9309 diff changeset	362 sibling->right->color = BLACK;
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9309 diff changeset	363 return;
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9309 diff changeset	364 }
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9309 diff changeset	365 else
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9309 diff changeset	366 {
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9309 diff changeset	367 if (parent->color == BLACK)
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9309 diff changeset	368 {
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9309 diff changeset	369 /* Change sibling from BLACK to RED. Then the entire
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9309 diff changeset	370 subtree at parent has decreased its black-height.
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9309 diff changeset	371 parent parent
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9309 diff changeset	372 bh+2 bh+1
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9309 diff changeset	373 / \ / \
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9309 diff changeset	374 child sibling --> child sibling
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9309 diff changeset	375 bh bh+1 bh bh
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9309 diff changeset	376 */
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9309 diff changeset	377 sibling->color = RED;
6982 d88d781b8e7b Ordered set data type implemented by a binary tree. Bruno Haible <bruno@clisp.org> parents: diff changeset	378
12421 e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9309 diff changeset	379 child = parent;
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9309 diff changeset	380 }
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9309 diff changeset	381 else
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9309 diff changeset	382 {
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9309 diff changeset	383 /* Change parent from RED to BLACK, but compensate by
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9309 diff changeset	384 changing sibling from BLACK to RED.
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9309 diff changeset	385 parent parent
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9309 diff changeset	386 bh+1 bh+1
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9309 diff changeset	387 / \ / \
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9309 diff changeset	388 child sibling --> child sibling
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9309 diff changeset	389 bh bh+1 bh bh
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9309 diff changeset	390 */
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9309 diff changeset	391 parent->color = BLACK;
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9309 diff changeset	392 sibling->color = RED;
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9309 diff changeset	393 return;
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9309 diff changeset	394 }
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9309 diff changeset	395 }
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9309 diff changeset	396 }
6982 d88d781b8e7b Ordered set data type implemented by a binary tree. Bruno Haible <bruno@clisp.org> parents: diff changeset	397 else if (parent->right == child)
12421 e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9309 diff changeset	398 {
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9309 diff changeset	399 gl_oset_node_t sibling = parent->left;
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9309 diff changeset	400 /* sibling's black-height is >= 1. In particular,
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9309 diff changeset	401 sibling != NULL.
6982 d88d781b8e7b Ordered set data type implemented by a binary tree. Bruno Haible <bruno@clisp.org> parents: diff changeset	402
12421 e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9309 diff changeset	403 parent
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9309 diff changeset	404 / \
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9309 diff changeset	405 sibling child
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9309 diff changeset	406 bh+1 bh
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9309 diff changeset	407 */
6982 d88d781b8e7b Ordered set data type implemented by a binary tree. Bruno Haible <bruno@clisp.org> parents: diff changeset	408
12421 e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9309 diff changeset	409 if (sibling->color == RED)
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9309 diff changeset	410 {
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9309 diff changeset	411 /* sibling is RED, hence parent is BLACK and sibling's children
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9309 diff changeset	412 are non-NULL and BLACK.
6982 d88d781b8e7b Ordered set data type implemented by a binary tree. Bruno Haible <bruno@clisp.org> parents: diff changeset	413
12421 e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9309 diff changeset	414 parent sibling
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9309 diff changeset	415 bh+2 bh+2
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9309 diff changeset	416 / \ / \
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9309 diff changeset	417 sibling child --> SR parent
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9309 diff changeset	418 bh+1 ch bh+1 bh+1
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9309 diff changeset	419 / \ / \
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9309 diff changeset	420 SL SR SL child
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9309 diff changeset	421 bh+1 bh+1 bh+1 bh
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9309 diff changeset	422 */
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9309 diff changeset	423 *parentp = rotate_right (sibling, parent);
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9309 diff changeset	424 parent->color = RED;
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9309 diff changeset	425 sibling->color = BLACK;
6982 d88d781b8e7b Ordered set data type implemented by a binary tree. Bruno Haible <bruno@clisp.org> parents: diff changeset	426
12421 e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9309 diff changeset	427 /* Concentrate on the subtree of parent. The new sibling is
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9309 diff changeset	428 one of the old sibling's children, and known to be BLACK. */
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9309 diff changeset	429 parentp = &sibling->right;
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9309 diff changeset	430 sibling = parent->left;
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9309 diff changeset	431 }
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9309 diff changeset	432 /* Now we know that sibling is BLACK.
6982 d88d781b8e7b Ordered set data type implemented by a binary tree. Bruno Haible <bruno@clisp.org> parents: diff changeset	433
12421 e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9309 diff changeset	434 parent
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9309 diff changeset	435 / \
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9309 diff changeset	436 sibling child
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9309 diff changeset	437 bh+1 bh
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9309 diff changeset	438 */
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9309 diff changeset	439 if (sibling->left != NULL && sibling->left->color == RED)
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9309 diff changeset	440 {
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9309 diff changeset	441 /*
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9309 diff changeset	442 parent sibling
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9309 diff changeset	443 bh+1\|bh+2 bh+1\|bh+2
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9309 diff changeset	444 / \ / \
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9309 diff changeset	445 sibling child --> SL parent
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9309 diff changeset	446 bh+1 bh bh+1 bh+1
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9309 diff changeset	447 / \ / \
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9309 diff changeset	448 SL SR SR child
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9309 diff changeset	449 bh bh bh bh
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9309 diff changeset	450 */
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9309 diff changeset	451 *parentp = rotate_right (sibling, parent);
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9309 diff changeset	452 sibling->color = parent->color;
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9309 diff changeset	453 parent->color = BLACK;
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9309 diff changeset	454 sibling->left->color = BLACK;
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9309 diff changeset	455 return;
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9309 diff changeset	456 }
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9309 diff changeset	457 else if (sibling->right != NULL && sibling->right->color == RED)
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9309 diff changeset	458 {
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9309 diff changeset	459 /*
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9309 diff changeset	460 parent parent
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9309 diff changeset	461 bh+1\|bh+2 bh+1\|bh+2
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9309 diff changeset	462 / \ / \
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9309 diff changeset	463 sibling child --> SR child
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9309 diff changeset	464 bh+1 bh bh+1 bh
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9309 diff changeset	465 / \ / \
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9309 diff changeset	466 SL SR sibling SRR
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9309 diff changeset	467 bh bh bh bh
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9309 diff changeset	468 / \ / \
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9309 diff changeset	469 SRL SRR SL SRL
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9309 diff changeset	470 bh bh bh bh
6982 d88d781b8e7b Ordered set data type implemented by a binary tree. Bruno Haible <bruno@clisp.org> parents: diff changeset	471
12421 e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9309 diff changeset	472 where SL, SRL, SRR are all black.
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9309 diff changeset	473 */
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9309 diff changeset	474 parent->left = rotate_left (sibling, sibling->right);
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9309 diff changeset	475 /* Change sibling from BLACK to RED and SL from RED to BLACK. */
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9309 diff changeset	476 sibling->color = RED;
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9309 diff changeset	477 sibling = parent->left;
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9309 diff changeset	478 sibling->color = BLACK;
6982 d88d781b8e7b Ordered set data type implemented by a binary tree. Bruno Haible <bruno@clisp.org> parents: diff changeset	479
12421 e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9309 diff changeset	480 /* Now do as in the previous case. */
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9309 diff changeset	481 *parentp = rotate_right (sibling, parent);
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9309 diff changeset	482 sibling->color = parent->color;
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9309 diff changeset	483 parent->color = BLACK;
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9309 diff changeset	484 sibling->left->color = BLACK;
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9309 diff changeset	485 return;
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9309 diff changeset	486 }
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9309 diff changeset	487 else
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9309 diff changeset	488 {
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9309 diff changeset	489 if (parent->color == BLACK)
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9309 diff changeset	490 {
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9309 diff changeset	491 /* Change sibling from BLACK to RED. Then the entire
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9309 diff changeset	492 subtree at parent has decreased its black-height.
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9309 diff changeset	493 parent parent
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9309 diff changeset	494 bh+2 bh+1
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9309 diff changeset	495 / \ / \
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9309 diff changeset	496 sibling child --> sibling child
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9309 diff changeset	497 bh+1 bh bh bh
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9309 diff changeset	498 */
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9309 diff changeset	499 sibling->color = RED;
6982 d88d781b8e7b Ordered set data type implemented by a binary tree. Bruno Haible <bruno@clisp.org> parents: diff changeset	500
12421 e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9309 diff changeset	501 child = parent;
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9309 diff changeset	502 }
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9309 diff changeset	503 else
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9309 diff changeset	504 {
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9309 diff changeset	505 /* Change parent from RED to BLACK, but compensate by
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9309 diff changeset	506 changing sibling from BLACK to RED.
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9309 diff changeset	507 parent parent
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9309 diff changeset	508 bh+1 bh+1
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9309 diff changeset	509 / \ / \
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9309 diff changeset	510 sibling child --> sibling child
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9309 diff changeset	511 bh+1 bh bh bh
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9309 diff changeset	512 */
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9309 diff changeset	513 parent->color = BLACK;
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9309 diff changeset	514 sibling->color = RED;
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9309 diff changeset	515 return;
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9309 diff changeset	516 }
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9309 diff changeset	517 }
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9309 diff changeset	518 }
6982 d88d781b8e7b Ordered set data type implemented by a binary tree. Bruno Haible <bruno@clisp.org> parents: diff changeset	519 else
12421 e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9309 diff changeset	520 abort ();
6982 d88d781b8e7b Ordered set data type implemented by a binary tree. Bruno Haible <bruno@clisp.org> parents: diff changeset	521
d88d781b8e7b Ordered set data type implemented by a binary tree. Bruno Haible <bruno@clisp.org> parents: diff changeset	522 /* Start again with a new (child, parent) pair. */
d88d781b8e7b Ordered set data type implemented by a binary tree. Bruno Haible <bruno@clisp.org> parents: diff changeset	523 parent = child->parent;
d88d781b8e7b Ordered set data type implemented by a binary tree. Bruno Haible <bruno@clisp.org> parents: diff changeset	524
d88d781b8e7b Ordered set data type implemented by a binary tree. Bruno Haible <bruno@clisp.org> parents: diff changeset	525 #if 0 /* Already handled. */
d88d781b8e7b Ordered set data type implemented by a binary tree. Bruno Haible <bruno@clisp.org> parents: diff changeset	526 if (child != NULL && child->color == RED)
12421 e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9309 diff changeset	527 {
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9309 diff changeset	528 child->color = BLACK;
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9309 diff changeset	529 return;
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9309 diff changeset	530 }
6982 d88d781b8e7b Ordered set data type implemented by a binary tree. Bruno Haible <bruno@clisp.org> parents: diff changeset	531 #endif
d88d781b8e7b Ordered set data type implemented by a binary tree. Bruno Haible <bruno@clisp.org> parents: diff changeset	532
d88d781b8e7b Ordered set data type implemented by a binary tree. Bruno Haible <bruno@clisp.org> parents: diff changeset	533 if (parent == NULL)
12421 e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9309 diff changeset	534 return;
6982 d88d781b8e7b Ordered set data type implemented by a binary tree. Bruno Haible <bruno@clisp.org> parents: diff changeset	535 }
d88d781b8e7b Ordered set data type implemented by a binary tree. Bruno Haible <bruno@clisp.org> parents: diff changeset	536 }
d88d781b8e7b Ordered set data type implemented by a binary tree. Bruno Haible <bruno@clisp.org> parents: diff changeset	537
d88d781b8e7b Ordered set data type implemented by a binary tree. Bruno Haible <bruno@clisp.org> parents: diff changeset	538 static gl_oset_node_t
12444 29d240cb21b2 Move the malloc checking from module 'oset' to new module 'xoset'. Bruno Haible <bruno@clisp.org> parents: 12421 diff changeset	539 gl_tree_nx_add_first (gl_oset_t set, const void *elt)
6982 d88d781b8e7b Ordered set data type implemented by a binary tree. Bruno Haible <bruno@clisp.org> parents: diff changeset	540 {
d88d781b8e7b Ordered set data type implemented by a binary tree. Bruno Haible <bruno@clisp.org> parents: diff changeset	541 /* Create new node. */
12444 29d240cb21b2 Move the malloc checking from module 'oset' to new module 'xoset'. Bruno Haible <bruno@clisp.org> parents: 12421 diff changeset	542 gl_oset_node_t new_node =
29d240cb21b2 Move the malloc checking from module 'oset' to new module 'xoset'. Bruno Haible <bruno@clisp.org> parents: 12421 diff changeset	543 (struct gl_oset_node_impl *) malloc (sizeof (struct gl_oset_node_impl));
29d240cb21b2 Move the malloc checking from module 'oset' to new module 'xoset'. Bruno Haible <bruno@clisp.org> parents: 12421 diff changeset	544
29d240cb21b2 Move the malloc checking from module 'oset' to new module 'xoset'. Bruno Haible <bruno@clisp.org> parents: 12421 diff changeset	545 if (new_node == NULL)
29d240cb21b2 Move the malloc checking from module 'oset' to new module 'xoset'. Bruno Haible <bruno@clisp.org> parents: 12421 diff changeset	546 return NULL;
6982 d88d781b8e7b Ordered set data type implemented by a binary tree. Bruno Haible <bruno@clisp.org> parents: diff changeset	547
d88d781b8e7b Ordered set data type implemented by a binary tree. Bruno Haible <bruno@clisp.org> parents: diff changeset	548 new_node->left = NULL;
d88d781b8e7b Ordered set data type implemented by a binary tree. Bruno Haible <bruno@clisp.org> parents: diff changeset	549 new_node->right = NULL;
d88d781b8e7b Ordered set data type implemented by a binary tree. Bruno Haible <bruno@clisp.org> parents: diff changeset	550 new_node->value = elt;
d88d781b8e7b Ordered set data type implemented by a binary tree. Bruno Haible <bruno@clisp.org> parents: diff changeset	551
d88d781b8e7b Ordered set data type implemented by a binary tree. Bruno Haible <bruno@clisp.org> parents: diff changeset	552 /* Add it to the tree. */
d88d781b8e7b Ordered set data type implemented by a binary tree. Bruno Haible <bruno@clisp.org> parents: diff changeset	553 if (set->root == NULL)
d88d781b8e7b Ordered set data type implemented by a binary tree. Bruno Haible <bruno@clisp.org> parents: diff changeset	554 {
d88d781b8e7b Ordered set data type implemented by a binary tree. Bruno Haible <bruno@clisp.org> parents: diff changeset	555 new_node->color = BLACK;
d88d781b8e7b Ordered set data type implemented by a binary tree. Bruno Haible <bruno@clisp.org> parents: diff changeset	556 set->root = new_node;
d88d781b8e7b Ordered set data type implemented by a binary tree. Bruno Haible <bruno@clisp.org> parents: diff changeset	557 new_node->parent = NULL;
d88d781b8e7b Ordered set data type implemented by a binary tree. Bruno Haible <bruno@clisp.org> parents: diff changeset	558 }
d88d781b8e7b Ordered set data type implemented by a binary tree. Bruno Haible <bruno@clisp.org> parents: diff changeset	559 else
d88d781b8e7b Ordered set data type implemented by a binary tree. Bruno Haible <bruno@clisp.org> parents: diff changeset	560 {
d88d781b8e7b Ordered set data type implemented by a binary tree. Bruno Haible <bruno@clisp.org> parents: diff changeset	561 gl_oset_node_t node;
d88d781b8e7b Ordered set data type implemented by a binary tree. Bruno Haible <bruno@clisp.org> parents: diff changeset	562
d88d781b8e7b Ordered set data type implemented by a binary tree. Bruno Haible <bruno@clisp.org> parents: diff changeset	563 for (node = set->root; node->left != NULL; )
12421 e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9309 diff changeset	564 node = node->left;
6982 d88d781b8e7b Ordered set data type implemented by a binary tree. Bruno Haible <bruno@clisp.org> parents: diff changeset	565
d88d781b8e7b Ordered set data type implemented by a binary tree. Bruno Haible <bruno@clisp.org> parents: diff changeset	566 node->left = new_node;
d88d781b8e7b Ordered set data type implemented by a binary tree. Bruno Haible <bruno@clisp.org> parents: diff changeset	567 new_node->parent = node;
d88d781b8e7b Ordered set data type implemented by a binary tree. Bruno Haible <bruno@clisp.org> parents: diff changeset	568
d88d781b8e7b Ordered set data type implemented by a binary tree. Bruno Haible <bruno@clisp.org> parents: diff changeset	569 /* Color and rebalance. */
d88d781b8e7b Ordered set data type implemented by a binary tree. Bruno Haible <bruno@clisp.org> parents: diff changeset	570 rebalance_after_add (set, new_node, node);
d88d781b8e7b Ordered set data type implemented by a binary tree. Bruno Haible <bruno@clisp.org> parents: diff changeset	571 }
d88d781b8e7b Ordered set data type implemented by a binary tree. Bruno Haible <bruno@clisp.org> parents: diff changeset	572
d88d781b8e7b Ordered set data type implemented by a binary tree. Bruno Haible <bruno@clisp.org> parents: diff changeset	573 set->count++;
d88d781b8e7b Ordered set data type implemented by a binary tree. Bruno Haible <bruno@clisp.org> parents: diff changeset	574 return new_node;
d88d781b8e7b Ordered set data type implemented by a binary tree. Bruno Haible <bruno@clisp.org> parents: diff changeset	575 }
d88d781b8e7b Ordered set data type implemented by a binary tree. Bruno Haible <bruno@clisp.org> parents: diff changeset	576
d88d781b8e7b Ordered set data type implemented by a binary tree. Bruno Haible <bruno@clisp.org> parents: diff changeset	577 static gl_oset_node_t
12444 29d240cb21b2 Move the malloc checking from module 'oset' to new module 'xoset'. Bruno Haible <bruno@clisp.org> parents: 12421 diff changeset	578 gl_tree_nx_add_before (gl_oset_t set, gl_oset_node_t node, const void *elt)
6982 d88d781b8e7b Ordered set data type implemented by a binary tree. Bruno Haible <bruno@clisp.org> parents: diff changeset	579 {
d88d781b8e7b Ordered set data type implemented by a binary tree. Bruno Haible <bruno@clisp.org> parents: diff changeset	580 /* Create new node. */
12444 29d240cb21b2 Move the malloc checking from module 'oset' to new module 'xoset'. Bruno Haible <bruno@clisp.org> parents: 12421 diff changeset	581 gl_oset_node_t new_node =
29d240cb21b2 Move the malloc checking from module 'oset' to new module 'xoset'. Bruno Haible <bruno@clisp.org> parents: 12421 diff changeset	582 (struct gl_oset_node_impl *) malloc (sizeof (struct gl_oset_node_impl));
29d240cb21b2 Move the malloc checking from module 'oset' to new module 'xoset'. Bruno Haible <bruno@clisp.org> parents: 12421 diff changeset	583
29d240cb21b2 Move the malloc checking from module 'oset' to new module 'xoset'. Bruno Haible <bruno@clisp.org> parents: 12421 diff changeset	584 if (new_node == NULL)
29d240cb21b2 Move the malloc checking from module 'oset' to new module 'xoset'. Bruno Haible <bruno@clisp.org> parents: 12421 diff changeset	585 return NULL;
6982 d88d781b8e7b Ordered set data type implemented by a binary tree. Bruno Haible <bruno@clisp.org> parents: diff changeset	586
d88d781b8e7b Ordered set data type implemented by a binary tree. Bruno Haible <bruno@clisp.org> parents: diff changeset	587 new_node->left = NULL;
d88d781b8e7b Ordered set data type implemented by a binary tree. Bruno Haible <bruno@clisp.org> parents: diff changeset	588 new_node->right = NULL;
d88d781b8e7b Ordered set data type implemented by a binary tree. Bruno Haible <bruno@clisp.org> parents: diff changeset	589 new_node->value = elt;
d88d781b8e7b Ordered set data type implemented by a binary tree. Bruno Haible <bruno@clisp.org> parents: diff changeset	590
d88d781b8e7b Ordered set data type implemented by a binary tree. Bruno Haible <bruno@clisp.org> parents: diff changeset	591 /* Add it to the tree. */
d88d781b8e7b Ordered set data type implemented by a binary tree. Bruno Haible <bruno@clisp.org> parents: diff changeset	592 if (node->left == NULL)
d88d781b8e7b Ordered set data type implemented by a binary tree. Bruno Haible <bruno@clisp.org> parents: diff changeset	593 node->left = new_node;
d88d781b8e7b Ordered set data type implemented by a binary tree. Bruno Haible <bruno@clisp.org> parents: diff changeset	594 else
d88d781b8e7b Ordered set data type implemented by a binary tree. Bruno Haible <bruno@clisp.org> parents: diff changeset	595 {
d88d781b8e7b Ordered set data type implemented by a binary tree. Bruno Haible <bruno@clisp.org> parents: diff changeset	596 for (node = node->left; node->right != NULL; )
12421 e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9309 diff changeset	597 node = node->right;
6982 d88d781b8e7b Ordered set data type implemented by a binary tree. Bruno Haible <bruno@clisp.org> parents: diff changeset	598 node->right = new_node;
d88d781b8e7b Ordered set data type implemented by a binary tree. Bruno Haible <bruno@clisp.org> parents: diff changeset	599 }
d88d781b8e7b Ordered set data type implemented by a binary tree. Bruno Haible <bruno@clisp.org> parents: diff changeset	600 new_node->parent = node;
d88d781b8e7b Ordered set data type implemented by a binary tree. Bruno Haible <bruno@clisp.org> parents: diff changeset	601
d88d781b8e7b Ordered set data type implemented by a binary tree. Bruno Haible <bruno@clisp.org> parents: diff changeset	602 /* Color and rebalance. */
d88d781b8e7b Ordered set data type implemented by a binary tree. Bruno Haible <bruno@clisp.org> parents: diff changeset	603 rebalance_after_add (set, new_node, node);
d88d781b8e7b Ordered set data type implemented by a binary tree. Bruno Haible <bruno@clisp.org> parents: diff changeset	604
d88d781b8e7b Ordered set data type implemented by a binary tree. Bruno Haible <bruno@clisp.org> parents: diff changeset	605 set->count++;
d88d781b8e7b Ordered set data type implemented by a binary tree. Bruno Haible <bruno@clisp.org> parents: diff changeset	606 return new_node;
d88d781b8e7b Ordered set data type implemented by a binary tree. Bruno Haible <bruno@clisp.org> parents: diff changeset	607 }
d88d781b8e7b Ordered set data type implemented by a binary tree. Bruno Haible <bruno@clisp.org> parents: diff changeset	608
d88d781b8e7b Ordered set data type implemented by a binary tree. Bruno Haible <bruno@clisp.org> parents: diff changeset	609 static gl_oset_node_t
12444 29d240cb21b2 Move the malloc checking from module 'oset' to new module 'xoset'. Bruno Haible <bruno@clisp.org> parents: 12421 diff changeset	610 gl_tree_nx_add_after (gl_oset_t set, gl_oset_node_t node, const void *elt)
6982 d88d781b8e7b Ordered set data type implemented by a binary tree. Bruno Haible <bruno@clisp.org> parents: diff changeset	611 {
d88d781b8e7b Ordered set data type implemented by a binary tree. Bruno Haible <bruno@clisp.org> parents: diff changeset	612 /* Create new node. */
12444 29d240cb21b2 Move the malloc checking from module 'oset' to new module 'xoset'. Bruno Haible <bruno@clisp.org> parents: 12421 diff changeset	613 gl_oset_node_t new_node =
29d240cb21b2 Move the malloc checking from module 'oset' to new module 'xoset'. Bruno Haible <bruno@clisp.org> parents: 12421 diff changeset	614 (struct gl_oset_node_impl *) malloc (sizeof (struct gl_oset_node_impl));
29d240cb21b2 Move the malloc checking from module 'oset' to new module 'xoset'. Bruno Haible <bruno@clisp.org> parents: 12421 diff changeset	615
29d240cb21b2 Move the malloc checking from module 'oset' to new module 'xoset'. Bruno Haible <bruno@clisp.org> parents: 12421 diff changeset	616 if (new_node == NULL)
29d240cb21b2 Move the malloc checking from module 'oset' to new module 'xoset'. Bruno Haible <bruno@clisp.org> parents: 12421 diff changeset	617 return NULL;
6982 d88d781b8e7b Ordered set data type implemented by a binary tree. Bruno Haible <bruno@clisp.org> parents: diff changeset	618
d88d781b8e7b Ordered set data type implemented by a binary tree. Bruno Haible <bruno@clisp.org> parents: diff changeset	619 new_node->left = NULL;
d88d781b8e7b Ordered set data type implemented by a binary tree. Bruno Haible <bruno@clisp.org> parents: diff changeset	620 new_node->right = NULL;
d88d781b8e7b Ordered set data type implemented by a binary tree. Bruno Haible <bruno@clisp.org> parents: diff changeset	621 new_node->value = elt;
d88d781b8e7b Ordered set data type implemented by a binary tree. Bruno Haible <bruno@clisp.org> parents: diff changeset	622
d88d781b8e7b Ordered set data type implemented by a binary tree. Bruno Haible <bruno@clisp.org> parents: diff changeset	623 /* Add it to the tree. */
d88d781b8e7b Ordered set data type implemented by a binary tree. Bruno Haible <bruno@clisp.org> parents: diff changeset	624 if (node->right == NULL)
d88d781b8e7b Ordered set data type implemented by a binary tree. Bruno Haible <bruno@clisp.org> parents: diff changeset	625 node->right = new_node;
d88d781b8e7b Ordered set data type implemented by a binary tree. Bruno Haible <bruno@clisp.org> parents: diff changeset	626 else
d88d781b8e7b Ordered set data type implemented by a binary tree. Bruno Haible <bruno@clisp.org> parents: diff changeset	627 {
d88d781b8e7b Ordered set data type implemented by a binary tree. Bruno Haible <bruno@clisp.org> parents: diff changeset	628 for (node = node->right; node->left != NULL; )
12421 e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9309 diff changeset	629 node = node->left;
6982 d88d781b8e7b Ordered set data type implemented by a binary tree. Bruno Haible <bruno@clisp.org> parents: diff changeset	630 node->left = new_node;
d88d781b8e7b Ordered set data type implemented by a binary tree. Bruno Haible <bruno@clisp.org> parents: diff changeset	631 }
d88d781b8e7b Ordered set data type implemented by a binary tree. Bruno Haible <bruno@clisp.org> parents: diff changeset	632 new_node->parent = node;
d88d781b8e7b Ordered set data type implemented by a binary tree. Bruno Haible <bruno@clisp.org> parents: diff changeset	633
d88d781b8e7b Ordered set data type implemented by a binary tree. Bruno Haible <bruno@clisp.org> parents: diff changeset	634 /* Color and rebalance. */
d88d781b8e7b Ordered set data type implemented by a binary tree. Bruno Haible <bruno@clisp.org> parents: diff changeset	635 rebalance_after_add (set, new_node, node);
d88d781b8e7b Ordered set data type implemented by a binary tree. Bruno Haible <bruno@clisp.org> parents: diff changeset	636
d88d781b8e7b Ordered set data type implemented by a binary tree. Bruno Haible <bruno@clisp.org> parents: diff changeset	637 set->count++;
d88d781b8e7b Ordered set data type implemented by a binary tree. Bruno Haible <bruno@clisp.org> parents: diff changeset	638 return new_node;
d88d781b8e7b Ordered set data type implemented by a binary tree. Bruno Haible <bruno@clisp.org> parents: diff changeset	639 }
d88d781b8e7b Ordered set data type implemented by a binary tree. Bruno Haible <bruno@clisp.org> parents: diff changeset	640
d88d781b8e7b Ordered set data type implemented by a binary tree. Bruno Haible <bruno@clisp.org> parents: diff changeset	641 static bool
d88d781b8e7b Ordered set data type implemented by a binary tree. Bruno Haible <bruno@clisp.org> parents: diff changeset	642 gl_tree_remove_node (gl_oset_t set, gl_oset_node_t node)
d88d781b8e7b Ordered set data type implemented by a binary tree. Bruno Haible <bruno@clisp.org> parents: diff changeset	643 {
d88d781b8e7b Ordered set data type implemented by a binary tree. Bruno Haible <bruno@clisp.org> parents: diff changeset	644 gl_oset_node_t parent = node->parent;
d88d781b8e7b Ordered set data type implemented by a binary tree. Bruno Haible <bruno@clisp.org> parents: diff changeset	645
d88d781b8e7b Ordered set data type implemented by a binary tree. Bruno Haible <bruno@clisp.org> parents: diff changeset	646 if (node->left == NULL)
d88d781b8e7b Ordered set data type implemented by a binary tree. Bruno Haible <bruno@clisp.org> parents: diff changeset	647 {
d88d781b8e7b Ordered set data type implemented by a binary tree. Bruno Haible <bruno@clisp.org> parents: diff changeset	648 /* Replace node with node->right. */
d88d781b8e7b Ordered set data type implemented by a binary tree. Bruno Haible <bruno@clisp.org> parents: diff changeset	649 gl_oset_node_t child = node->right;
d88d781b8e7b Ordered set data type implemented by a binary tree. Bruno Haible <bruno@clisp.org> parents: diff changeset	650
d88d781b8e7b Ordered set data type implemented by a binary tree. Bruno Haible <bruno@clisp.org> parents: diff changeset	651 if (child != NULL)
12421 e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9309 diff changeset	652 {
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9309 diff changeset	653 child->parent = parent;
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9309 diff changeset	654 /* Since node->left == NULL, child must be RED and of height 1,
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9309 diff changeset	655 hence node must have been BLACK. Recolor the child. */
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9309 diff changeset	656 child->color = BLACK;
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9309 diff changeset	657 }
6982 d88d781b8e7b Ordered set data type implemented by a binary tree. Bruno Haible <bruno@clisp.org> parents: diff changeset	658 if (parent == NULL)
12421 e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9309 diff changeset	659 set->root = child;
6982 d88d781b8e7b Ordered set data type implemented by a binary tree. Bruno Haible <bruno@clisp.org> parents: diff changeset	660 else
12421 e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9309 diff changeset	661 {
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9309 diff changeset	662 if (parent->left == node)
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9309 diff changeset	663 parent->left = child;
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9309 diff changeset	664 else /* parent->right == node */
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9309 diff changeset	665 parent->right = child;
6982 d88d781b8e7b Ordered set data type implemented by a binary tree. Bruno Haible <bruno@clisp.org> parents: diff changeset	666
12421 e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9309 diff changeset	667 if (child == NULL && node->color == BLACK)
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9309 diff changeset	668 rebalance_after_remove (set, child, parent);
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9309 diff changeset	669 }
6982 d88d781b8e7b Ordered set data type implemented by a binary tree. Bruno Haible <bruno@clisp.org> parents: diff changeset	670 }
d88d781b8e7b Ordered set data type implemented by a binary tree. Bruno Haible <bruno@clisp.org> parents: diff changeset	671 else if (node->right == NULL)
d88d781b8e7b Ordered set data type implemented by a binary tree. Bruno Haible <bruno@clisp.org> parents: diff changeset	672 {
d88d781b8e7b Ordered set data type implemented by a binary tree. Bruno Haible <bruno@clisp.org> parents: diff changeset	673 /* It is not absolutely necessary to treat this case. But the more
12421 e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9309 diff changeset	674 general case below is more complicated, hence slower. */
6982 d88d781b8e7b Ordered set data type implemented by a binary tree. Bruno Haible <bruno@clisp.org> parents: diff changeset	675 /* Replace node with node->left. */
d88d781b8e7b Ordered set data type implemented by a binary tree. Bruno Haible <bruno@clisp.org> parents: diff changeset	676 gl_oset_node_t child = node->left;
d88d781b8e7b Ordered set data type implemented by a binary tree. Bruno Haible <bruno@clisp.org> parents: diff changeset	677
d88d781b8e7b Ordered set data type implemented by a binary tree. Bruno Haible <bruno@clisp.org> parents: diff changeset	678 child->parent = parent;
d88d781b8e7b Ordered set data type implemented by a binary tree. Bruno Haible <bruno@clisp.org> parents: diff changeset	679 /* Since node->right == NULL, child must be RED and of height 1,
12421 e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9309 diff changeset	680 hence node must have been BLACK. Recolor the child. */
6982 d88d781b8e7b Ordered set data type implemented by a binary tree. Bruno Haible <bruno@clisp.org> parents: diff changeset	681 child->color = BLACK;
d88d781b8e7b Ordered set data type implemented by a binary tree. Bruno Haible <bruno@clisp.org> parents: diff changeset	682 if (parent == NULL)
12421 e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9309 diff changeset	683 set->root = child;
6982 d88d781b8e7b Ordered set data type implemented by a binary tree. Bruno Haible <bruno@clisp.org> parents: diff changeset	684 else
12421 e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9309 diff changeset	685 {
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9309 diff changeset	686 if (parent->left == node)
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9309 diff changeset	687 parent->left = child;
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9309 diff changeset	688 else /* parent->right == node */
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9309 diff changeset	689 parent->right = child;
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9309 diff changeset	690 }
6982 d88d781b8e7b Ordered set data type implemented by a binary tree. Bruno Haible <bruno@clisp.org> parents: diff changeset	691 }
d88d781b8e7b Ordered set data type implemented by a binary tree. Bruno Haible <bruno@clisp.org> parents: diff changeset	692 else
d88d781b8e7b Ordered set data type implemented by a binary tree. Bruno Haible <bruno@clisp.org> parents: diff changeset	693 {
d88d781b8e7b Ordered set data type implemented by a binary tree. Bruno Haible <bruno@clisp.org> parents: diff changeset	694 /* Replace node with the rightmost element of the node->left subtree. */
d88d781b8e7b Ordered set data type implemented by a binary tree. Bruno Haible <bruno@clisp.org> parents: diff changeset	695 gl_oset_node_t subst;
d88d781b8e7b Ordered set data type implemented by a binary tree. Bruno Haible <bruno@clisp.org> parents: diff changeset	696 gl_oset_node_t subst_parent;
d88d781b8e7b Ordered set data type implemented by a binary tree. Bruno Haible <bruno@clisp.org> parents: diff changeset	697 gl_oset_node_t child;
d88d781b8e7b Ordered set data type implemented by a binary tree. Bruno Haible <bruno@clisp.org> parents: diff changeset	698 color_t removed_color;
d88d781b8e7b Ordered set data type implemented by a binary tree. Bruno Haible <bruno@clisp.org> parents: diff changeset	699
d88d781b8e7b Ordered set data type implemented by a binary tree. Bruno Haible <bruno@clisp.org> parents: diff changeset	700 for (subst = node->left; subst->right != NULL; )
12421 e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9309 diff changeset	701 subst = subst->right;
6982 d88d781b8e7b Ordered set data type implemented by a binary tree. Bruno Haible <bruno@clisp.org> parents: diff changeset	702
d88d781b8e7b Ordered set data type implemented by a binary tree. Bruno Haible <bruno@clisp.org> parents: diff changeset	703 subst_parent = subst->parent;
d88d781b8e7b Ordered set data type implemented by a binary tree. Bruno Haible <bruno@clisp.org> parents: diff changeset	704
d88d781b8e7b Ordered set data type implemented by a binary tree. Bruno Haible <bruno@clisp.org> parents: diff changeset	705 child = subst->left;
d88d781b8e7b Ordered set data type implemented by a binary tree. Bruno Haible <bruno@clisp.org> parents: diff changeset	706
d88d781b8e7b Ordered set data type implemented by a binary tree. Bruno Haible <bruno@clisp.org> parents: diff changeset	707 removed_color = subst->color;
d88d781b8e7b Ordered set data type implemented by a binary tree. Bruno Haible <bruno@clisp.org> parents: diff changeset	708
d88d781b8e7b Ordered set data type implemented by a binary tree. Bruno Haible <bruno@clisp.org> parents: diff changeset	709 /* The case subst_parent == node is special: If we do nothing special,
12421 e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9309 diff changeset	710 we get confusion about node->left, subst->left and child->parent.
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9309 diff changeset	711 subst_parent == node
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9309 diff changeset	712 <==> The 'for' loop above terminated immediately.
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9309 diff changeset	713 <==> subst == subst_parent->left
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9309 diff changeset	714 [otherwise subst == subst_parent->right]
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9309 diff changeset	715 In this case, we would need to first set
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9309 diff changeset	716 child->parent = node; node->left = child;
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9309 diff changeset	717 and later - when we copy subst into node's position - again
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9309 diff changeset	718 child->parent = subst; subst->left = child;
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9309 diff changeset	719 Altogether a no-op. */
6982 d88d781b8e7b Ordered set data type implemented by a binary tree. Bruno Haible <bruno@clisp.org> parents: diff changeset	720 if (subst_parent != node)
12421 e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9309 diff changeset	721 {
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9309 diff changeset	722 if (child != NULL)
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9309 diff changeset	723 child->parent = subst_parent;
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9309 diff changeset	724 subst_parent->right = child;
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9309 diff changeset	725 }
6982 d88d781b8e7b Ordered set data type implemented by a binary tree. Bruno Haible <bruno@clisp.org> parents: diff changeset	726
d88d781b8e7b Ordered set data type implemented by a binary tree. Bruno Haible <bruno@clisp.org> parents: diff changeset	727 /* Copy subst into node's position.
12421 e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9309 diff changeset	728 (This is safer than to copy subst's value into node, keep node in
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9309 diff changeset	729 place, and free subst.) */
6982 d88d781b8e7b Ordered set data type implemented by a binary tree. Bruno Haible <bruno@clisp.org> parents: diff changeset	730 if (subst_parent != node)
12421 e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9309 diff changeset	731 {
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9309 diff changeset	732 subst->left = node->left;
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9309 diff changeset	733 subst->left->parent = subst;
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9309 diff changeset	734 }
6982 d88d781b8e7b Ordered set data type implemented by a binary tree. Bruno Haible <bruno@clisp.org> parents: diff changeset	735 subst->right = node->right;
d88d781b8e7b Ordered set data type implemented by a binary tree. Bruno Haible <bruno@clisp.org> parents: diff changeset	736 subst->right->parent = subst;
d88d781b8e7b Ordered set data type implemented by a binary tree. Bruno Haible <bruno@clisp.org> parents: diff changeset	737 subst->color = node->color;
d88d781b8e7b Ordered set data type implemented by a binary tree. Bruno Haible <bruno@clisp.org> parents: diff changeset	738 subst->parent = parent;
d88d781b8e7b Ordered set data type implemented by a binary tree. Bruno Haible <bruno@clisp.org> parents: diff changeset	739 if (parent == NULL)
12421 e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9309 diff changeset	740 set->root = subst;
6982 d88d781b8e7b Ordered set data type implemented by a binary tree. Bruno Haible <bruno@clisp.org> parents: diff changeset	741 else if (parent->left == node)
12421 e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9309 diff changeset	742 parent->left = subst;
6982 d88d781b8e7b Ordered set data type implemented by a binary tree. Bruno Haible <bruno@clisp.org> parents: diff changeset	743 else /* parent->right == node */
12421 e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9309 diff changeset	744 parent->right = subst;
6982 d88d781b8e7b Ordered set data type implemented by a binary tree. Bruno Haible <bruno@clisp.org> parents: diff changeset	745
d88d781b8e7b Ordered set data type implemented by a binary tree. Bruno Haible <bruno@clisp.org> parents: diff changeset	746 if (removed_color == BLACK)
12421 e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9309 diff changeset	747 {
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9309 diff changeset	748 if (child != NULL && child->color == RED)
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9309 diff changeset	749 /* Recolor the child. */
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9309 diff changeset	750 child->color = BLACK;
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9309 diff changeset	751 else
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9309 diff changeset	752 /* Rebalancing starts at child's parent, that is subst_parent -
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9309 diff changeset	753 except when subst_parent == node. In this case, we need to use
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9309 diff changeset	754 its replacement, subst. */
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9309 diff changeset	755 rebalance_after_remove (set, child,
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9309 diff changeset	756 subst_parent != node ? subst_parent : subst);
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9309 diff changeset	757 }
6982 d88d781b8e7b Ordered set data type implemented by a binary tree. Bruno Haible <bruno@clisp.org> parents: diff changeset	758 }
d88d781b8e7b Ordered set data type implemented by a binary tree. Bruno Haible <bruno@clisp.org> parents: diff changeset	759
d88d781b8e7b Ordered set data type implemented by a binary tree. Bruno Haible <bruno@clisp.org> parents: diff changeset	760 set->count--;
8436 36bbb949160c Add an element disposal function. Bruno Haible <bruno@clisp.org> parents: 7603 diff changeset	761 if (set->base.dispose_fn != NULL)
36bbb949160c Add an element disposal function. Bruno Haible <bruno@clisp.org> parents: 7603 diff changeset	762 set->base.dispose_fn (node->value);
6982 d88d781b8e7b Ordered set data type implemented by a binary tree. Bruno Haible <bruno@clisp.org> parents: diff changeset	763 free (node);
d88d781b8e7b Ordered set data type implemented by a binary tree. Bruno Haible <bruno@clisp.org> parents: diff changeset	764 return true;
d88d781b8e7b Ordered set data type implemented by a binary tree. Bruno Haible <bruno@clisp.org> parents: diff changeset	765 }
d88d781b8e7b Ordered set data type implemented by a binary tree. Bruno Haible <bruno@clisp.org> parents: diff changeset	766
d88d781b8e7b Ordered set data type implemented by a binary tree. Bruno Haible <bruno@clisp.org> parents: diff changeset	767 /* Generic binary tree code. */
d88d781b8e7b Ordered set data type implemented by a binary tree. Bruno Haible <bruno@clisp.org> parents: diff changeset	768 #include "gl_anytree_oset.h"
d88d781b8e7b Ordered set data type implemented by a binary tree. Bruno Haible <bruno@clisp.org> parents: diff changeset	769
d88d781b8e7b Ordered set data type implemented by a binary tree. Bruno Haible <bruno@clisp.org> parents: diff changeset	770 /* For debugging. */
d88d781b8e7b Ordered set data type implemented by a binary tree. Bruno Haible <bruno@clisp.org> parents: diff changeset	771 static unsigned int
d88d781b8e7b Ordered set data type implemented by a binary tree. Bruno Haible <bruno@clisp.org> parents: diff changeset	772 check_invariants (gl_oset_node_t node, gl_oset_node_t parent, size_t *counterp)
d88d781b8e7b Ordered set data type implemented by a binary tree. Bruno Haible <bruno@clisp.org> parents: diff changeset	773 {
d88d781b8e7b Ordered set data type implemented by a binary tree. Bruno Haible <bruno@clisp.org> parents: diff changeset	774 unsigned int left_blackheight =
d88d781b8e7b Ordered set data type implemented by a binary tree. Bruno Haible <bruno@clisp.org> parents: diff changeset	775 (node->left != NULL ? check_invariants (node->left, node, counterp) : 0);
d88d781b8e7b Ordered set data type implemented by a binary tree. Bruno Haible <bruno@clisp.org> parents: diff changeset	776 unsigned int right_blackheight =
d88d781b8e7b Ordered set data type implemented by a binary tree. Bruno Haible <bruno@clisp.org> parents: diff changeset	777 (node->right != NULL ? check_invariants (node->right, node, counterp) : 0);
d88d781b8e7b Ordered set data type implemented by a binary tree. Bruno Haible <bruno@clisp.org> parents: diff changeset	778
d88d781b8e7b Ordered set data type implemented by a binary tree. Bruno Haible <bruno@clisp.org> parents: diff changeset	779 if (!(node->parent == parent))
d88d781b8e7b Ordered set data type implemented by a binary tree. Bruno Haible <bruno@clisp.org> parents: diff changeset	780 abort ();
d88d781b8e7b Ordered set data type implemented by a binary tree. Bruno Haible <bruno@clisp.org> parents: diff changeset	781 if (!(node->color == BLACK \|\| node->color == RED))
d88d781b8e7b Ordered set data type implemented by a binary tree. Bruno Haible <bruno@clisp.org> parents: diff changeset	782 abort ();
d88d781b8e7b Ordered set data type implemented by a binary tree. Bruno Haible <bruno@clisp.org> parents: diff changeset	783 if (parent == NULL && !(node->color == BLACK))
d88d781b8e7b Ordered set data type implemented by a binary tree. Bruno Haible <bruno@clisp.org> parents: diff changeset	784 abort ();
d88d781b8e7b Ordered set data type implemented by a binary tree. Bruno Haible <bruno@clisp.org> parents: diff changeset	785 if (!(left_blackheight == right_blackheight))
d88d781b8e7b Ordered set data type implemented by a binary tree. Bruno Haible <bruno@clisp.org> parents: diff changeset	786 abort ();
d88d781b8e7b Ordered set data type implemented by a binary tree. Bruno Haible <bruno@clisp.org> parents: diff changeset	787
d88d781b8e7b Ordered set data type implemented by a binary tree. Bruno Haible <bruno@clisp.org> parents: diff changeset	788 (*counterp)++;
d88d781b8e7b Ordered set data type implemented by a binary tree. Bruno Haible <bruno@clisp.org> parents: diff changeset	789
d88d781b8e7b Ordered set data type implemented by a binary tree. Bruno Haible <bruno@clisp.org> parents: diff changeset	790 return left_blackheight + (node->color == BLACK ? 1 : 0);
d88d781b8e7b Ordered set data type implemented by a binary tree. Bruno Haible <bruno@clisp.org> parents: diff changeset	791 }
d88d781b8e7b Ordered set data type implemented by a binary tree. Bruno Haible <bruno@clisp.org> parents: diff changeset	792 void
d88d781b8e7b Ordered set data type implemented by a binary tree. Bruno Haible <bruno@clisp.org> parents: diff changeset	793 gl_rbtree_oset_check_invariants (gl_oset_t set)
d88d781b8e7b Ordered set data type implemented by a binary tree. Bruno Haible <bruno@clisp.org> parents: diff changeset	794 {
d88d781b8e7b Ordered set data type implemented by a binary tree. Bruno Haible <bruno@clisp.org> parents: diff changeset	795 size_t counter = 0;
d88d781b8e7b Ordered set data type implemented by a binary tree. Bruno Haible <bruno@clisp.org> parents: diff changeset	796 if (set->root != NULL)
d88d781b8e7b Ordered set data type implemented by a binary tree. Bruno Haible <bruno@clisp.org> parents: diff changeset	797 check_invariants (set->root, NULL, &counter);
d88d781b8e7b Ordered set data type implemented by a binary tree. Bruno Haible <bruno@clisp.org> parents: diff changeset	798 if (!(set->count == counter))
d88d781b8e7b Ordered set data type implemented by a binary tree. Bruno Haible <bruno@clisp.org> parents: diff changeset	799 abort ();
d88d781b8e7b Ordered set data type implemented by a binary tree. Bruno Haible <bruno@clisp.org> parents: diff changeset	800 }
d88d781b8e7b Ordered set data type implemented by a binary tree. Bruno Haible <bruno@clisp.org> parents: diff changeset	801
d88d781b8e7b Ordered set data type implemented by a binary tree. Bruno Haible <bruno@clisp.org> parents: diff changeset	802 const struct gl_oset_implementation gl_rbtree_oset_implementation =
d88d781b8e7b Ordered set data type implemented by a binary tree. Bruno Haible <bruno@clisp.org> parents: diff changeset	803 {
12444 29d240cb21b2 Move the malloc checking from module 'oset' to new module 'xoset'. Bruno Haible <bruno@clisp.org> parents: 12421 diff changeset	804 gl_tree_nx_create_empty,
6982 d88d781b8e7b Ordered set data type implemented by a binary tree. Bruno Haible <bruno@clisp.org> parents: diff changeset	805 gl_tree_size,
d88d781b8e7b Ordered set data type implemented by a binary tree. Bruno Haible <bruno@clisp.org> parents: diff changeset	806 gl_tree_search,
7403 2fbd1f779c5f Add a search_atleast operation. Bruno Haible <bruno@clisp.org> parents: 7304 diff changeset	807 gl_tree_search_atleast,
12444 29d240cb21b2 Move the malloc checking from module 'oset' to new module 'xoset'. Bruno Haible <bruno@clisp.org> parents: 12421 diff changeset	808 gl_tree_nx_add,
6982 d88d781b8e7b Ordered set data type implemented by a binary tree. Bruno Haible <bruno@clisp.org> parents: diff changeset	809 gl_tree_remove,
d88d781b8e7b Ordered set data type implemented by a binary tree. Bruno Haible <bruno@clisp.org> parents: diff changeset	810 gl_tree_oset_free,
d88d781b8e7b Ordered set data type implemented by a binary tree. Bruno Haible <bruno@clisp.org> parents: diff changeset	811 gl_tree_iterator,
d88d781b8e7b Ordered set data type implemented by a binary tree. Bruno Haible <bruno@clisp.org> parents: diff changeset	812 gl_tree_iterator_next,
d88d781b8e7b Ordered set data type implemented by a binary tree. Bruno Haible <bruno@clisp.org> parents: diff changeset	813 gl_tree_iterator_free
d88d781b8e7b Ordered set data type implemented by a binary tree. Bruno Haible <bruno@clisp.org> parents: diff changeset	814 };

Mercurial > hg > octave-jordi > gnulib-hg

annotate lib/gl_rbtree_oset.c @ 14858:dd10bbc31f53