octave-kai/gnulib-hg: lib/gl_anyavltree

annotate lib/gl_anyavltree_list2.h @ 12421:e8d2c6fc33ad

Use spaces for indentation, not tabs.

author	Bruno Haible <bruno@clisp.org>
date	Thu, 10 Dec 2009 20:28:30 +0100
parents	bbbbbf4cd1c5
children	a8c91b846640

rev	line source
6973 de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	1 /* Sequential list data type implemented by a binary tree.
8438 238942284e2f Allow the use of a destructor for the values stored in the list. Bruno Haible <bruno@clisp.org> parents: 7615 diff changeset	2 Copyright (C) 2006-2007 Free Software Foundation, Inc.
6973 de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	3 Written by Bruno Haible <bruno@clisp.org>, 2006.
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	4
9309 bbbbbf4cd1c5 Change copyright notice from GPLv2+ to GPLv3+. Bruno Haible <bruno@clisp.org> parents: 8438 diff changeset	5 This program is free software: you can redistribute it and/or modify
6973 de9a21fc207a Common code several concrete list implementations. 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: 8438 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: 8438 diff changeset	8 (at your option) any later version.
6973 de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	9
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	10 This program is distributed in the hope that it will be useful,
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	11 but WITHOUT ANY WARRANTY; without even the implied warranty of
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	12 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	13 GNU General Public License for more details.
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	14
de9a21fc207a Common code several concrete list implementations. 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: 8438 diff changeset	16 along with this program. If not, see <http://www.gnu.org/licenses/>. */
6973 de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	17
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	18 /* Common code of gl_avltree_list.c and gl_avltreehash_list.c. */
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	19
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	20 /* -------------------------- gl_list_t Data Type -------------------------- */
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	21
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	22 /* Create a subtree for count >= 1 elements.
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	23 Its height is h where 2^(h-1) <= count <= 2^h - 1. */
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	24 static gl_list_node_t
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	25 create_subtree_with_contents (size_t count, const void **contents)
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	26 {
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	27 size_t half1 = (count - 1) / 2;
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	28 size_t half2 = count / 2;
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	29 /* Note: half1 + half2 = count - 1. */
7615 5657275cb755 More uses of XMALLOC, XNMALLOC and XCALLOC. Bruno Haible <bruno@clisp.org> parents: 6973 diff changeset	30 gl_list_node_t node = XMALLOC (struct gl_list_node_impl);
6973 de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	31
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	32 if (half1 > 0)
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	33 {
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	34 node->left = create_subtree_with_contents (half1, contents);
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	35 node->left->parent = node;
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	36 }
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	37 else
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	38 node->left = NULL;
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	39
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	40 node->value = contents[half1];
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	41
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	42 if (half2 > 0)
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	43 {
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	44 node->right = create_subtree_with_contents (half2, contents + half1 + 1);
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	45 node->right->parent = node;
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	46 }
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	47 else
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	48 node->right = NULL;
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	49
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	50 /* balance is 0, except when count is a power of two and > 1.
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	51 Reason: half1 <= half2 <= half1 + 1, and the two branches can have
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	52 different heights only if half1 = 2^h - 1 and half2 = 2^h; in this
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	53 case, count = half1 + half2 + 1 = 2^(h+1). */
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	54 node->balance = (count > 1 && (count & (count - 1)) == 0 ? 1 : 0);
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	55
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	56 node->branch_size = count;
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	57
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	58 return node;
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	59 }
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	60
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	61 static gl_list_t
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	62 gl_tree_create (gl_list_implementation_t implementation,
12421 e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9309 diff changeset	63 gl_listelement_equals_fn equals_fn,
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9309 diff changeset	64 gl_listelement_hashcode_fn hashcode_fn,
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9309 diff changeset	65 gl_listelement_dispose_fn dispose_fn,
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9309 diff changeset	66 bool allow_duplicates,
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9309 diff changeset	67 size_t count, const void **contents)
6973 de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	68 {
7615 5657275cb755 More uses of XMALLOC, XNMALLOC and XCALLOC. Bruno Haible <bruno@clisp.org> parents: 6973 diff changeset	69 struct gl_list_impl *list = XMALLOC (struct gl_list_impl);
6973 de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	70
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	71 list->base.vtable = implementation;
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	72 list->base.equals_fn = equals_fn;
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	73 list->base.hashcode_fn = hashcode_fn;
8438 238942284e2f Allow the use of a destructor for the values stored in the list. Bruno Haible <bruno@clisp.org> parents: 7615 diff changeset	74 list->base.dispose_fn = dispose_fn;
6973 de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	75 list->base.allow_duplicates = allow_duplicates;
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	76 #if WITH_HASHTABLE
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	77 {
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	78 size_t estimate = xsum (count, count / 2); /* 1.5 * count */
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	79 if (estimate < 10)
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	80 estimate = 10;
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	81 list->table_size = next_prime (estimate);
7615 5657275cb755 More uses of XMALLOC, XNMALLOC and XCALLOC. Bruno Haible <bruno@clisp.org> parents: 6973 diff changeset	82 list->table = XCALLOC (list->table_size, gl_hash_entry_t);
6973 de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	83 }
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	84 #endif
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	85 if (count > 0)
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	86 {
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	87 list->root = create_subtree_with_contents (count, contents);
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	88 list->root->parent = NULL;
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	89
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	90 #if WITH_HASHTABLE
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	91 /* Now that the tree is built, node_position() works. Now we can
12421 e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9309 diff changeset	92 add the nodes to the hash table. */
6973 de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	93 add_nodes_to_buckets (list);
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	94 #endif
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	95 }
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	96 else
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	97 list->root = NULL;
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	98
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	99 return list;
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	100 }
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	101
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	102 /* Ensure the tree is balanced, after an insertion or deletion operation.
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	103 The height of NODE is incremented by HEIGHT_DIFF (1 or -1).
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	104 PARENT = NODE->parent. (NODE can also be NULL. But PARENT is non-NULL.)
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	105 Rotation operations are performed starting at PARENT (not NODE itself!). */
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	106 static void
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	107 rebalance (gl_list_t list,
12421 e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9309 diff changeset	108 gl_list_node_t node, int height_diff, gl_list_node_t parent)
6973 de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	109 {
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	110 for (;;)
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	111 {
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	112 gl_list_node_t child;
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	113 int previous_balance;
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	114 int balance_diff;
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	115 gl_list_node_t nodeleft;
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	116 gl_list_node_t noderight;
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	117
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	118 child = node;
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	119 node = parent;
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	120
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	121 previous_balance = node->balance;
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	122
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	123 /* The balance of NODE is incremented by BALANCE_DIFF: +1 if the right
12421 e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9309 diff changeset	124 branch's height has increased by 1 or the left branch's height has
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9309 diff changeset	125 decreased by 1, -1 if the right branch's height has decreased by 1 or
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9309 diff changeset	126 the left branch's height has increased by 1, 0 if no height change. */
6973 de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	127 if (node->left != NULL \|\| node->right != NULL)
12421 e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9309 diff changeset	128 balance_diff = (child == node->right ? height_diff : -height_diff);
6973 de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	129 else
12421 e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9309 diff changeset	130 /* Special case where above formula doesn't work, because the caller
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9309 diff changeset	131 didn't tell whether node's left or right branch shrunk from height 1
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9309 diff changeset	132 to NULL. */
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9309 diff changeset	133 balance_diff = - previous_balance;
6973 de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	134
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	135 node->balance += balance_diff;
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	136 if (balance_diff == previous_balance)
12421 e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9309 diff changeset	137 {
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9309 diff changeset	138 /* node->balance is outside the range [-1,1]. Must rotate. */
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9309 diff changeset	139 gl_list_node_t *nodep;
6973 de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	140
12421 e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9309 diff changeset	141 if (node->parent == NULL)
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9309 diff changeset	142 /* node == list->root */
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9309 diff changeset	143 nodep = &list->root;
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9309 diff changeset	144 else if (node->parent->left == node)
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9309 diff changeset	145 nodep = &node->parent->left;
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9309 diff changeset	146 else if (node->parent->right == node)
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9309 diff changeset	147 nodep = &node->parent->right;
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9309 diff changeset	148 else
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9309 diff changeset	149 abort ();
6973 de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	150
12421 e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9309 diff changeset	151 nodeleft = node->left;
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9309 diff changeset	152 noderight = node->right;
6973 de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	153
12421 e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9309 diff changeset	154 if (balance_diff < 0)
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9309 diff changeset	155 {
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9309 diff changeset	156 /* node->balance = -2. The subtree is heavier on the left side.
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9309 diff changeset	157 Rotate from left to right:
6973 de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	158
12421 e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9309 diff changeset	159 *
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 h+2 h
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9309 diff changeset	162 */
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9309 diff changeset	163 gl_list_node_t nodeleftleft = nodeleft->left;
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9309 diff changeset	164 gl_list_node_t nodeleftright = nodeleft->right;
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9309 diff changeset	165 if (nodeleft->balance <= 0)
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9309 diff changeset	166 {
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9309 diff changeset	167 /*
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9309 diff changeset	168 * h+2\|h+3
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 h+2 h --> / h+1\|h+2
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9309 diff changeset	171 / \ \| / \
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9309 diff changeset	172 h+1 h\|h+1 h+1 h\|h+1 h
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9309 diff changeset	173 */
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9309 diff changeset	174 node->left = nodeleftright;
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9309 diff changeset	175 nodeleft->right = node;
6973 de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	176
12421 e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9309 diff changeset	177 nodeleft->parent = node->parent;
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9309 diff changeset	178 node->parent = nodeleft;
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9309 diff changeset	179 if (nodeleftright != NULL)
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9309 diff changeset	180 nodeleftright->parent = node;
6973 de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	181
12421 e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9309 diff changeset	182 nodeleft->balance += 1;
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9309 diff changeset	183 node->balance = - nodeleft->balance;
6973 de9a21fc207a Common code several concrete list implementations. 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 node->branch_size =
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9309 diff changeset	186 (nodeleftright != NULL ? nodeleftright->branch_size : 0)
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9309 diff changeset	187 + 1 + (noderight != NULL ? noderight->branch_size : 0);
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9309 diff changeset	188 nodeleft->branch_size =
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9309 diff changeset	189 nodeleftleft->branch_size + 1 + node->branch_size;
6973 de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	190
12421 e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9309 diff changeset	191 *nodep = nodeleft;
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9309 diff changeset	192 height_diff = (height_diff < 0
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9309 diff changeset	193 ? /* noderight's height had been decremented from
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9309 diff changeset	194 h+1 to h. The subtree's height changes from
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9309 diff changeset	195 h+3 to h+2\|h+3. */
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9309 diff changeset	196 nodeleft->balance - 1
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9309 diff changeset	197 : /* nodeleft's height had been incremented from
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9309 diff changeset	198 h+1 to h+2. The subtree's height changes from
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9309 diff changeset	199 h+2 to h+2\|h+3. */
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9309 diff changeset	200 nodeleft->balance);
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9309 diff changeset	201 }
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9309 diff changeset	202 else
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9309 diff changeset	203 {
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9309 diff changeset	204 /*
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9309 diff changeset	205 * h+2
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9309 diff changeset	206 / \ / \
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9309 diff changeset	207 h+2 h --> h+1 h+1
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9309 diff changeset	208 / \ / \ / \
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9309 diff changeset	209 h h+1 h L R h
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9309 diff changeset	210 / \
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9309 diff changeset	211 L R
6973 de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	212
12421 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 gl_list_node_t L = nodeleft->right = nodeleftright->left;
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9309 diff changeset	215 gl_list_node_t R = node->left = nodeleftright->right;
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9309 diff changeset	216 nodeleftright->left = nodeleft;
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9309 diff changeset	217 nodeleftright->right = node;
6973 de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	218
12421 e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9309 diff changeset	219 nodeleftright->parent = node->parent;
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9309 diff changeset	220 if (L != NULL)
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9309 diff changeset	221 L->parent = nodeleft;
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9309 diff changeset	222 if (R != NULL)
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9309 diff changeset	223 R->parent = node;
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9309 diff changeset	224 nodeleft->parent = nodeleftright;
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9309 diff changeset	225 node->parent = nodeleftright;
6973 de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	226
12421 e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9309 diff changeset	227 nodeleft->balance = (nodeleftright->balance > 0 ? -1 : 0);
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9309 diff changeset	228 node->balance = (nodeleftright->balance < 0 ? 1 : 0);
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9309 diff changeset	229 nodeleftright->balance = 0;
6973 de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	230
12421 e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9309 diff changeset	231 nodeleft->branch_size =
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9309 diff changeset	232 (nodeleft->left != NULL ? nodeleft->left->branch_size : 0)
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9309 diff changeset	233 + 1 + (nodeleft->right != NULL ? nodeleft->right->branch_size : 0);
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9309 diff changeset	234 node->branch_size =
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9309 diff changeset	235 (node->left != NULL ? node->left->branch_size : 0)
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9309 diff changeset	236 + 1 + (node->right != NULL ? node->right->branch_size : 0);
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9309 diff changeset	237 nodeleftright->branch_size =
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9309 diff changeset	238 nodeleft->branch_size + 1 + node->branch_size;
6973 de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	239
12421 e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9309 diff changeset	240 *nodep = nodeleftright;
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9309 diff changeset	241 height_diff = (height_diff < 0
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9309 diff changeset	242 ? /* noderight's height had been decremented from
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9309 diff changeset	243 h+1 to h. The subtree's height changes from
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9309 diff changeset	244 h+3 to h+2. */
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9309 diff changeset	245 -1
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9309 diff changeset	246 : /* nodeleft's height had been incremented from
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9309 diff changeset	247 h+1 to h+2. The subtree's height changes from
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9309 diff changeset	248 h+2 to h+2. */
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9309 diff changeset	249 0);
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9309 diff changeset	250 }
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9309 diff changeset	251 }
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9309 diff changeset	252 else
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9309 diff changeset	253 {
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9309 diff changeset	254 /* node->balance = 2. The subtree is heavier on the right side.
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9309 diff changeset	255 Rotate from right to left:
6973 de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	256
12421 e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9309 diff changeset	257 *
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9309 diff changeset	258 / \
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9309 diff changeset	259 h h+2
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9309 diff changeset	260 */
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9309 diff changeset	261 gl_list_node_t noderightleft = noderight->left;
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9309 diff changeset	262 gl_list_node_t noderightright = noderight->right;
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9309 diff changeset	263 if (noderight->balance >= 0)
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9309 diff changeset	264 {
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9309 diff changeset	265 /*
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9309 diff changeset	266 * h+2\|h+3
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9309 diff changeset	267 / \ / \
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9309 diff changeset	268 h h+2 --> h+1\|h+2 \
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9309 diff changeset	269 / \ / \ \|
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9309 diff changeset	270 h\|h+1 h+1 h h\|h+1 h+1
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9309 diff changeset	271 */
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9309 diff changeset	272 node->right = noderightleft;
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9309 diff changeset	273 noderight->left = node;
6973 de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	274
12421 e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9309 diff changeset	275 noderight->parent = node->parent;
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9309 diff changeset	276 node->parent = noderight;
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9309 diff changeset	277 if (noderightleft != NULL)
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9309 diff changeset	278 noderightleft->parent = node;
6973 de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	279
12421 e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9309 diff changeset	280 noderight->balance -= 1;
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9309 diff changeset	281 node->balance = - noderight->balance;
6973 de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	282
12421 e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9309 diff changeset	283 node->branch_size =
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9309 diff changeset	284 (nodeleft != NULL ? nodeleft->branch_size : 0)
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9309 diff changeset	285 + 1 + (noderightleft != NULL ? noderightleft->branch_size : 0);
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9309 diff changeset	286 noderight->branch_size =
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9309 diff changeset	287 node->branch_size + 1 + noderightright->branch_size;
6973 de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	288
12421 e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9309 diff changeset	289 *nodep = noderight;
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9309 diff changeset	290 height_diff = (height_diff < 0
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9309 diff changeset	291 ? /* nodeleft's height had been decremented from
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9309 diff changeset	292 h+1 to h. The subtree's height changes from
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9309 diff changeset	293 h+3 to h+2\|h+3. */
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9309 diff changeset	294 - noderight->balance - 1
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9309 diff changeset	295 : /* noderight's height had been incremented from
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9309 diff changeset	296 h+1 to h+2. The subtree's height changes from
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9309 diff changeset	297 h+2 to h+2\|h+3. */
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9309 diff changeset	298 - noderight->balance);
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9309 diff changeset	299 }
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9309 diff changeset	300 else
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9309 diff changeset	301 {
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9309 diff changeset	302 /*
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9309 diff changeset	303 * h+2
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9309 diff changeset	304 / \ / \
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9309 diff changeset	305 h h+2 --> h+1 h+1
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9309 diff changeset	306 / \ / \ / \
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9309 diff changeset	307 h+1 h h L R h
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9309 diff changeset	308 / \
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9309 diff changeset	309 L R
6973 de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	310
12421 e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9309 diff changeset	311 */
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9309 diff changeset	312 gl_list_node_t L = node->right = noderightleft->left;
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9309 diff changeset	313 gl_list_node_t R = noderight->left = noderightleft->right;
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9309 diff changeset	314 noderightleft->left = node;
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9309 diff changeset	315 noderightleft->right = noderight;
6973 de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	316
12421 e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9309 diff changeset	317 noderightleft->parent = node->parent;
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9309 diff changeset	318 if (L != NULL)
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9309 diff changeset	319 L->parent = node;
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9309 diff changeset	320 if (R != NULL)
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9309 diff changeset	321 R->parent = noderight;
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9309 diff changeset	322 node->parent = noderightleft;
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9309 diff changeset	323 noderight->parent = noderightleft;
6973 de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	324
12421 e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9309 diff changeset	325 node->balance = (noderightleft->balance > 0 ? -1 : 0);
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9309 diff changeset	326 noderight->balance = (noderightleft->balance < 0 ? 1 : 0);
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9309 diff changeset	327 noderightleft->balance = 0;
6973 de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	328
12421 e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9309 diff changeset	329 node->branch_size =
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9309 diff changeset	330 (node->left != NULL ? node->left->branch_size : 0)
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9309 diff changeset	331 + 1 + (node->right != NULL ? node->right->branch_size : 0);
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9309 diff changeset	332 noderight->branch_size =
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9309 diff changeset	333 (noderight->left != NULL ? noderight->left->branch_size : 0)
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9309 diff changeset	334 + 1 + (noderight->right != NULL ? noderight->right->branch_size : 0);
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9309 diff changeset	335 noderightleft->branch_size =
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9309 diff changeset	336 node->branch_size + 1 + noderight->branch_size;
6973 de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	337
12421 e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9309 diff changeset	338 *nodep = noderightleft;
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9309 diff changeset	339 height_diff = (height_diff < 0
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9309 diff changeset	340 ? /* nodeleft's height had been decremented from
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9309 diff changeset	341 h+1 to h. The subtree's height changes from
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9309 diff changeset	342 h+3 to h+2. */
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9309 diff changeset	343 -1
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9309 diff changeset	344 : /* noderight's height had been incremented from
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9309 diff changeset	345 h+1 to h+2. The subtree's height changes from
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9309 diff changeset	346 h+2 to h+2. */
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9309 diff changeset	347 0);
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9309 diff changeset	348 }
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9309 diff changeset	349 }
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9309 diff changeset	350 node = *nodep;
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9309 diff changeset	351 }
6973 de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	352 else
12421 e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9309 diff changeset	353 {
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9309 diff changeset	354 /* No rotation needed. Only propagation of the height change to the
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9309 diff changeset	355 next higher level. */
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9309 diff changeset	356 if (height_diff < 0)
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9309 diff changeset	357 height_diff = (previous_balance == 0 ? 0 : -1);
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9309 diff changeset	358 else
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9309 diff changeset	359 height_diff = (node->balance == 0 ? 0 : 1);
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9309 diff changeset	360 }
6973 de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	361
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	362 if (height_diff == 0)
12421 e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9309 diff changeset	363 break;
6973 de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	364
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	365 parent = node->parent;
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	366 if (parent == NULL)
12421 e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9309 diff changeset	367 break;
6973 de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	368 }
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	369 }
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	370
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	371 static gl_list_node_t
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	372 gl_tree_add_first (gl_list_t list, const void *elt)
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	373 {
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	374 /* Create new node. */
7615 5657275cb755 More uses of XMALLOC, XNMALLOC and XCALLOC. Bruno Haible <bruno@clisp.org> parents: 6973 diff changeset	375 gl_list_node_t new_node = XMALLOC (struct gl_list_node_impl);
6973 de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	376
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	377 new_node->left = NULL;
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	378 new_node->right = NULL;
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	379 new_node->balance = 0;
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	380 new_node->branch_size = 1;
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	381 new_node->value = elt;
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	382 #if WITH_HASHTABLE
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	383 new_node->h.hashcode =
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	384 (list->base.hashcode_fn != NULL
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	385 ? list->base.hashcode_fn (new_node->value)
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	386 : (size_t)(uintptr_t) new_node->value);
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	387 #endif
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	388
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	389 /* Add it to the tree. */
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	390 if (list->root == NULL)
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	391 {
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	392 list->root = new_node;
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	393 new_node->parent = NULL;
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	394 }
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	395 else
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	396 {
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	397 gl_list_node_t node;
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	398
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	399 for (node = list->root; node->left != NULL; )
12421 e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9309 diff changeset	400 node = node->left;
6973 de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	401
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	402 node->left = new_node;
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	403 new_node->parent = node;
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	404 node->balance--;
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	405
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	406 /* Update branch_size fields of the parent nodes. */
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	407 {
12421 e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9309 diff changeset	408 gl_list_node_t p;
6973 de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	409
12421 e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9309 diff changeset	410 for (p = node; p != NULL; p = p->parent)
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9309 diff changeset	411 p->branch_size++;
6973 de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	412 }
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	413
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	414 /* Rebalance. */
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	415 if (node->right == NULL && node->parent != NULL)
12421 e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9309 diff changeset	416 rebalance (list, node, 1, node->parent);
6973 de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	417 }
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	418
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	419 #if WITH_HASHTABLE
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	420 /* Add node to the hash table.
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	421 Note that this is only possible _after_ the node has been added to the
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	422 tree structure, because add_to_bucket() uses node_position(). */
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	423 add_to_bucket (list, new_node);
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	424 hash_resize_after_add (list);
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	425 #endif
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	426
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	427 return new_node;
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	428 }
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	429
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	430 static gl_list_node_t
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	431 gl_tree_add_last (gl_list_t list, const void *elt)
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	432 {
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	433 /* Create new node. */
7615 5657275cb755 More uses of XMALLOC, XNMALLOC and XCALLOC. Bruno Haible <bruno@clisp.org> parents: 6973 diff changeset	434 gl_list_node_t new_node = XMALLOC (struct gl_list_node_impl);
6973 de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	435
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	436 new_node->left = NULL;
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	437 new_node->right = NULL;
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	438 new_node->balance = 0;
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	439 new_node->branch_size = 1;
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	440 new_node->value = elt;
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	441 #if WITH_HASHTABLE
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	442 new_node->h.hashcode =
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	443 (list->base.hashcode_fn != NULL
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	444 ? list->base.hashcode_fn (new_node->value)
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	445 : (size_t)(uintptr_t) new_node->value);
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	446 #endif
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	447
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	448 /* Add it to the tree. */
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	449 if (list->root == NULL)
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	450 {
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	451 list->root = new_node;
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	452 new_node->parent = NULL;
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	453 }
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	454 else
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	455 {
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	456 gl_list_node_t node;
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	457
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	458 for (node = list->root; node->right != NULL; )
12421 e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9309 diff changeset	459 node = node->right;
6973 de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	460
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	461 node->right = new_node;
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	462 new_node->parent = node;
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	463 node->balance++;
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	464
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	465 /* Update branch_size fields of the parent nodes. */
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	466 {
12421 e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9309 diff changeset	467 gl_list_node_t p;
6973 de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	468
12421 e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9309 diff changeset	469 for (p = node; p != NULL; p = p->parent)
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9309 diff changeset	470 p->branch_size++;
6973 de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	471 }
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	472
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	473 /* Rebalance. */
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	474 if (node->left == NULL && node->parent != NULL)
12421 e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9309 diff changeset	475 rebalance (list, node, 1, node->parent);
6973 de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	476 }
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	477
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	478 #if WITH_HASHTABLE
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	479 /* Add node to the hash table.
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	480 Note that this is only possible _after_ the node has been added to the
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	481 tree structure, because add_to_bucket() uses node_position(). */
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	482 add_to_bucket (list, new_node);
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	483 hash_resize_after_add (list);
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	484 #endif
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	485
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	486 return new_node;
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	487 }
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	488
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	489 static gl_list_node_t
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	490 gl_tree_add_before (gl_list_t list, gl_list_node_t node, const void *elt)
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	491 {
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	492 /* Create new node. */
7615 5657275cb755 More uses of XMALLOC, XNMALLOC and XCALLOC. Bruno Haible <bruno@clisp.org> parents: 6973 diff changeset	493 gl_list_node_t new_node = XMALLOC (struct gl_list_node_impl);
6973 de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	494 bool height_inc;
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	495
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	496 new_node->left = NULL;
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	497 new_node->right = NULL;
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	498 new_node->balance = 0;
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	499 new_node->branch_size = 1;
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	500 new_node->value = elt;
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	501 #if WITH_HASHTABLE
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	502 new_node->h.hashcode =
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	503 (list->base.hashcode_fn != NULL
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	504 ? list->base.hashcode_fn (new_node->value)
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	505 : (size_t)(uintptr_t) new_node->value);
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	506 #endif
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	507
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	508 /* Add it to the tree. */
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	509 if (node->left == NULL)
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	510 {
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	511 node->left = new_node;
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	512 node->balance--;
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	513 height_inc = (node->right == NULL);
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	514 }
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	515 else
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	516 {
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	517 for (node = node->left; node->right != NULL; )
12421 e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9309 diff changeset	518 node = node->right;
6973 de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	519 node->right = new_node;
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	520 node->balance++;
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	521 height_inc = (node->left == NULL);
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	522 }
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	523 new_node->parent = node;
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	524
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	525 /* Update branch_size fields of the parent nodes. */
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	526 {
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	527 gl_list_node_t p;
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	528
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	529 for (p = node; p != NULL; p = p->parent)
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	530 p->branch_size++;
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	531 }
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	532
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	533 /* Rebalance. */
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	534 if (height_inc && node->parent != NULL)
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	535 rebalance (list, node, 1, node->parent);
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	536
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	537 #if WITH_HASHTABLE
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	538 /* Add node to the hash table.
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	539 Note that this is only possible _after_ the node has been added to the
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	540 tree structure, because add_to_bucket() uses node_position(). */
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	541 add_to_bucket (list, new_node);
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	542 hash_resize_after_add (list);
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	543 #endif
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	544
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	545 return new_node;
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	546 }
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	547
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	548 static gl_list_node_t
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	549 gl_tree_add_after (gl_list_t list, gl_list_node_t node, const void *elt)
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	550 {
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	551 /* Create new node. */
7615 5657275cb755 More uses of XMALLOC, XNMALLOC and XCALLOC. Bruno Haible <bruno@clisp.org> parents: 6973 diff changeset	552 gl_list_node_t new_node = XMALLOC (struct gl_list_node_impl);
6973 de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	553 bool height_inc;
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	554
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	555 new_node->left = NULL;
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	556 new_node->right = NULL;
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	557 new_node->balance = 0;
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	558 new_node->branch_size = 1;
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	559 new_node->value = elt;
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	560 #if WITH_HASHTABLE
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	561 new_node->h.hashcode =
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	562 (list->base.hashcode_fn != NULL
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	563 ? list->base.hashcode_fn (new_node->value)
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	564 : (size_t)(uintptr_t) new_node->value);
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	565 #endif
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	566
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	567 /* Add it to the tree. */
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	568 if (node->right == NULL)
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	569 {
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	570 node->right = new_node;
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	571 node->balance++;
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	572 height_inc = (node->left == NULL);
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	573 }
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	574 else
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	575 {
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	576 for (node = node->right; node->left != NULL; )
12421 e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9309 diff changeset	577 node = node->left;
6973 de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	578 node->left = new_node;
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	579 node->balance--;
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	580 height_inc = (node->right == NULL);
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	581 }
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	582 new_node->parent = node;
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	583
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	584 /* Update branch_size fields of the parent nodes. */
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	585 {
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	586 gl_list_node_t p;
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	587
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	588 for (p = node; p != NULL; p = p->parent)
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	589 p->branch_size++;
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	590 }
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	591
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	592 /* Rebalance. */
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	593 if (height_inc && node->parent != NULL)
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	594 rebalance (list, node, 1, node->parent);
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	595
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	596 #if WITH_HASHTABLE
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	597 /* Add node to the hash table.
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	598 Note that this is only possible _after_ the node has been added to the
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	599 tree structure, because add_to_bucket() uses node_position(). */
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	600 add_to_bucket (list, new_node);
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	601 hash_resize_after_add (list);
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	602 #endif
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	603
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	604 return new_node;
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	605 }
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	606
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	607 static bool
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	608 gl_tree_remove_node (gl_list_t list, gl_list_node_t node)
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	609 {
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	610 gl_list_node_t parent;
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	611
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	612 #if WITH_HASHTABLE
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	613 /* Remove node from the hash table.
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	614 Note that this is only possible _before_ the node is removed from the
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	615 tree structure, because remove_from_bucket() uses node_position(). */
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	616 remove_from_bucket (list, node);
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	617 #endif
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	618
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	619 parent = node->parent;
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	620
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	621 if (node->left == NULL)
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	622 {
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	623 /* Replace node with node->right. */
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	624 gl_list_node_t child = node->right;
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	625
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	626 if (child != NULL)
12421 e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9309 diff changeset	627 child->parent = parent;
6973 de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	628 if (parent == NULL)
12421 e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9309 diff changeset	629 list->root = child;
6973 de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	630 else
12421 e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9309 diff changeset	631 {
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9309 diff changeset	632 if (parent->left == node)
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9309 diff changeset	633 parent->left = child;
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9309 diff changeset	634 else /* parent->right == node */
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9309 diff changeset	635 parent->right = child;
6973 de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	636
12421 e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9309 diff changeset	637 /* Update branch_size fields of the parent nodes. */
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9309 diff changeset	638 {
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9309 diff changeset	639 gl_list_node_t p;
6973 de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	640
12421 e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9309 diff changeset	641 for (p = parent; p != NULL; p = p->parent)
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9309 diff changeset	642 p->branch_size--;
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9309 diff changeset	643 }
6973 de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	644
12421 e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9309 diff changeset	645 rebalance (list, child, -1, parent);
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9309 diff changeset	646 }
6973 de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	647 }
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	648 else if (node->right == NULL)
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	649 {
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	650 /* 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	651 general case below is more complicated, hence slower. */
6973 de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	652 /* Replace node with node->left. */
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	653 gl_list_node_t child = node->left;
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	654
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	655 child->parent = parent;
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	656 if (parent == NULL)
12421 e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9309 diff changeset	657 list->root = child;
6973 de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	658 else
12421 e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9309 diff changeset	659 {
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9309 diff changeset	660 if (parent->left == node)
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9309 diff changeset	661 parent->left = child;
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9309 diff changeset	662 else /* parent->right == node */
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9309 diff changeset	663 parent->right = child;
6973 de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	664
12421 e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9309 diff changeset	665 /* Update branch_size fields of the parent nodes. */
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9309 diff changeset	666 {
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9309 diff changeset	667 gl_list_node_t p;
6973 de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	668
12421 e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9309 diff changeset	669 for (p = parent; p != NULL; p = p->parent)
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9309 diff changeset	670 p->branch_size--;
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9309 diff changeset	671 }
6973 de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	672
12421 e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9309 diff changeset	673 rebalance (list, child, -1, parent);
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9309 diff changeset	674 }
6973 de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	675 }
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	676 else
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	677 {
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	678 /* Replace node with the rightmost element of the node->left subtree. */
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	679 gl_list_node_t subst;
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	680 gl_list_node_t subst_parent;
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	681 gl_list_node_t child;
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	682
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	683 for (subst = node->left; subst->right != NULL; )
12421 e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9309 diff changeset	684 subst = subst->right;
6973 de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	685
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	686 subst_parent = subst->parent;
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	687
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	688 child = subst->left;
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	689
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	690 /* 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	691 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	692 subst_parent == node
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9309 diff changeset	693 <==> The 'for' loop above terminated immediately.
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9309 diff changeset	694 <==> subst == subst_parent->left
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9309 diff changeset	695 [otherwise subst == subst_parent->right]
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9309 diff changeset	696 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	697 child->parent = node; node->left = child;
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9309 diff changeset	698 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	699 child->parent = subst; subst->left = child;
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9309 diff changeset	700 Altogether a no-op. */
6973 de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	701 if (subst_parent != node)
12421 e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9309 diff changeset	702 {
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9309 diff changeset	703 if (child != NULL)
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9309 diff changeset	704 child->parent = subst_parent;
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9309 diff changeset	705 subst_parent->right = child;
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9309 diff changeset	706 }
6973 de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	707
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	708 /* Update branch_size fields of the parent nodes. */
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	709 {
12421 e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9309 diff changeset	710 gl_list_node_t p;
6973 de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	711
12421 e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9309 diff changeset	712 for (p = subst_parent; p != NULL; p = p->parent)
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9309 diff changeset	713 p->branch_size--;
6973 de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	714 }
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	715
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	716 /* Copy subst into node's position.
12421 e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9309 diff changeset	717 (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	718 place, and free subst.) */
6973 de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	719 if (subst_parent != node)
12421 e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9309 diff changeset	720 {
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9309 diff changeset	721 subst->left = node->left;
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9309 diff changeset	722 subst->left->parent = subst;
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9309 diff changeset	723 }
6973 de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	724 subst->right = node->right;
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	725 subst->right->parent = subst;
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	726 subst->balance = node->balance;
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	727 subst->branch_size = node->branch_size;
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	728 subst->parent = parent;
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	729 if (parent == NULL)
12421 e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9309 diff changeset	730 list->root = subst;
6973 de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	731 else if (parent->left == node)
12421 e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9309 diff changeset	732 parent->left = subst;
6973 de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	733 else /* parent->right == node */
12421 e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9309 diff changeset	734 parent->right = subst;
6973 de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	735
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	736 /* Rebalancing starts at child's parent, that is subst_parent -
12421 e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9309 diff changeset	737 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	738 its replacement, subst. */
6973 de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	739 rebalance (list, child, -1, subst_parent != node ? subst_parent : subst);
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	740 }
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	741
8438 238942284e2f Allow the use of a destructor for the values stored in the list. Bruno Haible <bruno@clisp.org> parents: 7615 diff changeset	742 if (list->base.dispose_fn != NULL)
238942284e2f Allow the use of a destructor for the values stored in the list. Bruno Haible <bruno@clisp.org> parents: 7615 diff changeset	743 list->base.dispose_fn (node->value);
6973 de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	744 free (node);
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	745 return true;
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	746 }

Mercurial > hg > octave-kai > gnulib-hg

annotate lib/gl_anyavltree_list2.h @ 12421:e8d2c6fc33ad