gnulib: lib/gl_anyavltree_list2.h annotate

annotate lib/gl_anyavltree_list2.h @ 40196:e63f5d3edab5

relocatable-prog: Update documentation. * doc/relocatable-maint.texi (Supporting Relocation): Update to match the recent changes.

author	Bruno Haible <bruno@clisp.org>
date	Sun, 24 Feb 2019 01:49:15 +0100
parents	b06060465f09
children

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.
40057 b06060465f09 maint: Run 'make update-copyright' Paul Eggert <eggert@cs.ucla.edu> parents: 19484 diff changeset	2 Copyright (C) 2006-2007, 2009-2019 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
19190 9759915b2aca all: prefer https: URLs Paul Eggert <eggert@cs.ucla.edu> parents: 18626 diff changeset	16 along with this program. If not, see <https://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.
12445 a8c91b846640 Move the malloc checking from module 'list' to new module 'xlist'. Bruno Haible <bruno@clisp.org> parents: 12421 diff changeset	23 Its height is h where 2^(h-1) <= count <= 2^h - 1.
a8c91b846640 Move the malloc checking from module 'list' to new module 'xlist'. Bruno Haible <bruno@clisp.org> parents: 12421 diff changeset	24 Return NULL upon out-of-memory. */
6973 de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	25 static gl_list_node_t
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	26 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	27 {
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	28 size_t half1 = (count - 1) / 2;
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	29 size_t half2 = count / 2;
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	30 /* Note: half1 + half2 = count - 1. */
12445 a8c91b846640 Move the malloc checking from module 'list' to new module 'xlist'. Bruno Haible <bruno@clisp.org> parents: 12421 diff changeset	31 gl_list_node_t node =
a8c91b846640 Move the malloc checking from module 'list' to new module 'xlist'. Bruno Haible <bruno@clisp.org> parents: 12421 diff changeset	32 (struct gl_list_node_impl *) malloc (sizeof (struct gl_list_node_impl));
a8c91b846640 Move the malloc checking from module 'list' to new module 'xlist'. Bruno Haible <bruno@clisp.org> parents: 12421 diff changeset	33 if (node == NULL)
a8c91b846640 Move the malloc checking from module 'list' to new module 'xlist'. Bruno Haible <bruno@clisp.org> parents: 12421 diff changeset	34 return NULL;
6973 de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	35
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	36 if (half1 > 0)
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	37 {
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	38 node->left = create_subtree_with_contents (half1, contents);
12445 a8c91b846640 Move the malloc checking from module 'list' to new module 'xlist'. Bruno Haible <bruno@clisp.org> parents: 12421 diff changeset	39 if (node->left == NULL)
a8c91b846640 Move the malloc checking from module 'list' to new module 'xlist'. Bruno Haible <bruno@clisp.org> parents: 12421 diff changeset	40 goto fail1;
6973 de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	41 node->left->parent = node;
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	42 }
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	43 else
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	44 node->left = NULL;
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	45
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	46 node->value = contents[half1];
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	47
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	48 if (half2 > 0)
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 node->right = create_subtree_with_contents (half2, contents + half1 + 1);
12445 a8c91b846640 Move the malloc checking from module 'list' to new module 'xlist'. Bruno Haible <bruno@clisp.org> parents: 12421 diff changeset	51 if (node->right == NULL)
a8c91b846640 Move the malloc checking from module 'list' to new module 'xlist'. Bruno Haible <bruno@clisp.org> parents: 12421 diff changeset	52 goto fail2;
6973 de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	53 node->right->parent = node;
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	54 }
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	55 else
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	56 node->right = NULL;
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 /* 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	59 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	60 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	61 case, count = half1 + half2 + 1 = 2^(h+1). */
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	62 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	63
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	64 node->branch_size = count;
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	65
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	66 return node;
12445 a8c91b846640 Move the malloc checking from module 'list' to new module 'xlist'. Bruno Haible <bruno@clisp.org> parents: 12421 diff changeset	67
a8c91b846640 Move the malloc checking from module 'list' to new module 'xlist'. Bruno Haible <bruno@clisp.org> parents: 12421 diff changeset	68 fail2:
a8c91b846640 Move the malloc checking from module 'list' to new module 'xlist'. Bruno Haible <bruno@clisp.org> parents: 12421 diff changeset	69 if (node->left != NULL)
a8c91b846640 Move the malloc checking from module 'list' to new module 'xlist'. Bruno Haible <bruno@clisp.org> parents: 12421 diff changeset	70 free_subtree (node->left);
a8c91b846640 Move the malloc checking from module 'list' to new module 'xlist'. Bruno Haible <bruno@clisp.org> parents: 12421 diff changeset	71 fail1:
a8c91b846640 Move the malloc checking from module 'list' to new module 'xlist'. Bruno Haible <bruno@clisp.org> parents: 12421 diff changeset	72 free (node);
a8c91b846640 Move the malloc checking from module 'list' to new module 'xlist'. Bruno Haible <bruno@clisp.org> parents: 12421 diff changeset	73 return NULL;
6973 de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	74 }
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	75
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	76 static gl_list_t
12445 a8c91b846640 Move the malloc checking from module 'list' to new module 'xlist'. Bruno Haible <bruno@clisp.org> parents: 12421 diff changeset	77 gl_tree_nx_create (gl_list_implementation_t implementation,
a8c91b846640 Move the malloc checking from module 'list' to new module 'xlist'. Bruno Haible <bruno@clisp.org> parents: 12421 diff changeset	78 gl_listelement_equals_fn equals_fn,
a8c91b846640 Move the malloc checking from module 'list' to new module 'xlist'. Bruno Haible <bruno@clisp.org> parents: 12421 diff changeset	79 gl_listelement_hashcode_fn hashcode_fn,
a8c91b846640 Move the malloc checking from module 'list' to new module 'xlist'. Bruno Haible <bruno@clisp.org> parents: 12421 diff changeset	80 gl_listelement_dispose_fn dispose_fn,
a8c91b846640 Move the malloc checking from module 'list' to new module 'xlist'. Bruno Haible <bruno@clisp.org> parents: 12421 diff changeset	81 bool allow_duplicates,
a8c91b846640 Move the malloc checking from module 'list' to new module 'xlist'. Bruno Haible <bruno@clisp.org> parents: 12421 diff changeset	82 size_t count, const void **contents)
6973 de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	83 {
12445 a8c91b846640 Move the malloc checking from module 'list' to new module 'xlist'. Bruno Haible <bruno@clisp.org> parents: 12421 diff changeset	84 struct gl_list_impl *list =
a8c91b846640 Move the malloc checking from module 'list' to new module 'xlist'. Bruno Haible <bruno@clisp.org> parents: 12421 diff changeset	85 (struct gl_list_impl *) malloc (sizeof (struct gl_list_impl));
a8c91b846640 Move the malloc checking from module 'list' to new module 'xlist'. Bruno Haible <bruno@clisp.org> parents: 12421 diff changeset	86
a8c91b846640 Move the malloc checking from module 'list' to new module 'xlist'. Bruno Haible <bruno@clisp.org> parents: 12421 diff changeset	87 if (list == NULL)
a8c91b846640 Move the malloc checking from module 'list' to new module 'xlist'. Bruno Haible <bruno@clisp.org> parents: 12421 diff changeset	88 return NULL;
6973 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 list->base.vtable = implementation;
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	91 list->base.equals_fn = equals_fn;
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	92 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	93 list->base.dispose_fn = dispose_fn;
6973 de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	94 list->base.allow_duplicates = allow_duplicates;
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	95 #if WITH_HASHTABLE
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	96 {
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	97 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	98 if (estimate < 10)
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	99 estimate = 10;
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	100 list->table_size = next_prime (estimate);
12445 a8c91b846640 Move the malloc checking from module 'list' to new module 'xlist'. Bruno Haible <bruno@clisp.org> parents: 12421 diff changeset	101 if (size_overflow_p (xtimes (list->table_size, sizeof (gl_hash_entry_t))))
a8c91b846640 Move the malloc checking from module 'list' to new module 'xlist'. Bruno Haible <bruno@clisp.org> parents: 12421 diff changeset	102 goto fail1;
a8c91b846640 Move the malloc checking from module 'list' to new module 'xlist'. Bruno Haible <bruno@clisp.org> parents: 12421 diff changeset	103 list->table =
a8c91b846640 Move the malloc checking from module 'list' to new module 'xlist'. Bruno Haible <bruno@clisp.org> parents: 12421 diff changeset	104 (gl_hash_entry_t *) calloc (list->table_size, sizeof (gl_hash_entry_t));
a8c91b846640 Move the malloc checking from module 'list' to new module 'xlist'. Bruno Haible <bruno@clisp.org> parents: 12421 diff changeset	105 if (list->table == NULL)
a8c91b846640 Move the malloc checking from module 'list' to new module 'xlist'. Bruno Haible <bruno@clisp.org> parents: 12421 diff changeset	106 goto fail1;
6973 de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	107 }
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	108 #endif
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	109 if (count > 0)
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	110 {
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	111 list->root = create_subtree_with_contents (count, contents);
12445 a8c91b846640 Move the malloc checking from module 'list' to new module 'xlist'. Bruno Haible <bruno@clisp.org> parents: 12421 diff changeset	112 if (list->root == NULL)
a8c91b846640 Move the malloc checking from module 'list' to new module 'xlist'. Bruno Haible <bruno@clisp.org> parents: 12421 diff changeset	113 goto fail2;
6973 de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	114 list->root->parent = NULL;
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	115
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	116 #if WITH_HASHTABLE
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	117 /* 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	118 add the nodes to the hash table. */
12445 a8c91b846640 Move the malloc checking from module 'list' to new module 'xlist'. Bruno Haible <bruno@clisp.org> parents: 12421 diff changeset	119 if (add_nodes_to_buckets (list) < 0)
a8c91b846640 Move the malloc checking from module 'list' to new module 'xlist'. Bruno Haible <bruno@clisp.org> parents: 12421 diff changeset	120 goto fail3;
6973 de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	121 #endif
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 else
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	124 list->root = NULL;
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	125
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	126 return list;
12445 a8c91b846640 Move the malloc checking from module 'list' to new module 'xlist'. Bruno Haible <bruno@clisp.org> parents: 12421 diff changeset	127
a8c91b846640 Move the malloc checking from module 'list' to new module 'xlist'. Bruno Haible <bruno@clisp.org> parents: 12421 diff changeset	128 #if WITH_HASHTABLE
a8c91b846640 Move the malloc checking from module 'list' to new module 'xlist'. Bruno Haible <bruno@clisp.org> parents: 12421 diff changeset	129 fail3:
a8c91b846640 Move the malloc checking from module 'list' to new module 'xlist'. Bruno Haible <bruno@clisp.org> parents: 12421 diff changeset	130 free_subtree (list->root);
a8c91b846640 Move the malloc checking from module 'list' to new module 'xlist'. Bruno Haible <bruno@clisp.org> parents: 12421 diff changeset	131 #endif
a8c91b846640 Move the malloc checking from module 'list' to new module 'xlist'. Bruno Haible <bruno@clisp.org> parents: 12421 diff changeset	132 fail2:
a8c91b846640 Move the malloc checking from module 'list' to new module 'xlist'. Bruno Haible <bruno@clisp.org> parents: 12421 diff changeset	133 #if WITH_HASHTABLE
a8c91b846640 Move the malloc checking from module 'list' to new module 'xlist'. Bruno Haible <bruno@clisp.org> parents: 12421 diff changeset	134 free (list->table);
a8c91b846640 Move the malloc checking from module 'list' to new module 'xlist'. Bruno Haible <bruno@clisp.org> parents: 12421 diff changeset	135 fail1:
a8c91b846640 Move the malloc checking from module 'list' to new module 'xlist'. Bruno Haible <bruno@clisp.org> parents: 12421 diff changeset	136 #endif
a8c91b846640 Move the malloc checking from module 'list' to new module 'xlist'. Bruno Haible <bruno@clisp.org> parents: 12421 diff changeset	137 free (list);
a8c91b846640 Move the malloc checking from module 'list' to new module 'xlist'. Bruno Haible <bruno@clisp.org> parents: 12421 diff changeset	138 return NULL;
6973 de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	139 }
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	140
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	141 /* 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	142 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	143 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	144 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	145 static void
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	146 rebalance (gl_list_t list,
12421 e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9309 diff changeset	147 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	148 {
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	149 for (;;)
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	150 {
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	151 gl_list_node_t child;
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	152 int previous_balance;
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	153 int balance_diff;
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	154 gl_list_node_t nodeleft;
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	155 gl_list_node_t noderight;
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	156
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	157 child = node;
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	158 node = parent;
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	159
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	160 previous_balance = node->balance;
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	161
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	162 /* 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	163 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	164 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	165 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	166 if (node->left != NULL \|\| node->right != NULL)
12421 e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9309 diff changeset	167 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	168 else
12421 e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9309 diff changeset	169 /* 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	170 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	171 to NULL. */
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9309 diff changeset	172 balance_diff = - previous_balance;
6973 de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	173
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	174 node->balance += balance_diff;
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	175 if (balance_diff == previous_balance)
12421 e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9309 diff changeset	176 {
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9309 diff changeset	177 /* 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	178 gl_list_node_t *nodep;
6973 de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	179
12421 e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9309 diff changeset	180 if (node->parent == NULL)
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9309 diff changeset	181 /* node == list->root */
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9309 diff changeset	182 nodep = &list->root;
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9309 diff changeset	183 else if (node->parent->left == node)
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9309 diff changeset	184 nodep = &node->parent->left;
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9309 diff changeset	185 else if (node->parent->right == node)
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9309 diff changeset	186 nodep = &node->parent->right;
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9309 diff changeset	187 else
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9309 diff changeset	188 abort ();
6973 de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	189
12421 e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9309 diff changeset	190 nodeleft = node->left;
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9309 diff changeset	191 noderight = node->right;
6973 de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	192
12421 e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9309 diff changeset	193 if (balance_diff < 0)
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9309 diff changeset	194 {
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9309 diff changeset	195 /* 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	196 Rotate from left to right:
6973 de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	197
12421 e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9309 diff changeset	198 *
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9309 diff changeset	199 / \
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9309 diff changeset	200 h+2 h
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 gl_list_node_t nodeleftleft = nodeleft->left;
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9309 diff changeset	203 gl_list_node_t nodeleftright = nodeleft->right;
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9309 diff changeset	204 if (nodeleft->balance <= 0)
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9309 diff changeset	205 {
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9309 diff changeset	206 /*
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9309 diff changeset	207 * h+2\|h+3
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+2 h --> / h+1\|h+2
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 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	212 */
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9309 diff changeset	213 node->left = nodeleftright;
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9309 diff changeset	214 nodeleft->right = node;
6973 de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	215
12421 e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9309 diff changeset	216 nodeleft->parent = node->parent;
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9309 diff changeset	217 node->parent = nodeleft;
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9309 diff changeset	218 if (nodeleftright != NULL)
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9309 diff changeset	219 nodeleftright->parent = node;
6973 de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	220
12421 e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9309 diff changeset	221 nodeleft->balance += 1;
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9309 diff changeset	222 node->balance = - nodeleft->balance;
6973 de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	223
12421 e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9309 diff changeset	224 node->branch_size =
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9309 diff changeset	225 (nodeleftright != NULL ? nodeleftright->branch_size : 0)
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9309 diff changeset	226 + 1 + (noderight != NULL ? noderight->branch_size : 0);
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9309 diff changeset	227 nodeleft->branch_size =
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9309 diff changeset	228 nodeleftleft->branch_size + 1 + node->branch_size;
6973 de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	229
12421 e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9309 diff changeset	230 *nodep = nodeleft;
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9309 diff changeset	231 height_diff = (height_diff < 0
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9309 diff changeset	232 ? /* noderight's height had been decremented from
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9309 diff changeset	233 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	234 h+3 to h+2\|h+3. */
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9309 diff changeset	235 nodeleft->balance - 1
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9309 diff changeset	236 : /* nodeleft's height had been incremented from
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9309 diff changeset	237 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	238 h+2 to h+2\|h+3. */
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9309 diff changeset	239 nodeleft->balance);
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9309 diff changeset	240 }
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9309 diff changeset	241 else
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9309 diff changeset	242 {
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9309 diff changeset	243 /*
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9309 diff changeset	244 * h+2
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9309 diff changeset	245 / \ / \
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9309 diff changeset	246 h+2 h --> h+1 h+1
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9309 diff changeset	247 / \ / \ / \
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9309 diff changeset	248 h h+1 h L R h
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9309 diff changeset	249 / \
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9309 diff changeset	250 L R
6973 de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	251
12421 e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9309 diff changeset	252 */
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9309 diff changeset	253 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	254 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	255 nodeleftright->left = nodeleft;
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9309 diff changeset	256 nodeleftright->right = node;
6973 de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	257
12421 e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9309 diff changeset	258 nodeleftright->parent = node->parent;
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9309 diff changeset	259 if (L != NULL)
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9309 diff changeset	260 L->parent = nodeleft;
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9309 diff changeset	261 if (R != NULL)
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9309 diff changeset	262 R->parent = node;
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9309 diff changeset	263 nodeleft->parent = nodeleftright;
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9309 diff changeset	264 node->parent = nodeleftright;
6973 de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	265
12421 e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9309 diff changeset	266 nodeleft->balance = (nodeleftright->balance > 0 ? -1 : 0);
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9309 diff changeset	267 node->balance = (nodeleftright->balance < 0 ? 1 : 0);
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9309 diff changeset	268 nodeleftright->balance = 0;
6973 de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	269
12421 e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9309 diff changeset	270 nodeleft->branch_size =
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9309 diff changeset	271 (nodeleft->left != NULL ? nodeleft->left->branch_size : 0)
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9309 diff changeset	272 + 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	273 node->branch_size =
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9309 diff changeset	274 (node->left != NULL ? node->left->branch_size : 0)
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9309 diff changeset	275 + 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	276 nodeleftright->branch_size =
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9309 diff changeset	277 nodeleft->branch_size + 1 + node->branch_size;
6973 de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	278
12421 e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9309 diff changeset	279 *nodep = nodeleftright;
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9309 diff changeset	280 height_diff = (height_diff < 0
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9309 diff changeset	281 ? /* noderight's height had been decremented from
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9309 diff changeset	282 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	283 h+3 to h+2. */
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9309 diff changeset	284 -1
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9309 diff changeset	285 : /* nodeleft's height had been incremented from
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9309 diff changeset	286 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	287 h+2 to h+2. */
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9309 diff changeset	288 0);
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9309 diff changeset	289 }
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9309 diff changeset	290 }
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9309 diff changeset	291 else
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9309 diff changeset	292 {
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9309 diff changeset	293 /* 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	294 Rotate from right to left:
6973 de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	295
12421 e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9309 diff changeset	296 *
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9309 diff changeset	297 / \
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9309 diff changeset	298 h h+2
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 gl_list_node_t noderightleft = noderight->left;
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9309 diff changeset	301 gl_list_node_t noderightright = noderight->right;
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9309 diff changeset	302 if (noderight->balance >= 0)
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9309 diff changeset	303 {
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+2\|h+3
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 h+2 --> h+1\|h+2 \
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 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	310 */
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9309 diff changeset	311 node->right = noderightleft;
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9309 diff changeset	312 noderight->left = node;
6973 de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	313
12421 e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9309 diff changeset	314 noderight->parent = node->parent;
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9309 diff changeset	315 node->parent = noderight;
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9309 diff changeset	316 if (noderightleft != NULL)
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9309 diff changeset	317 noderightleft->parent = node;
6973 de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	318
12421 e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9309 diff changeset	319 noderight->balance -= 1;
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9309 diff changeset	320 node->balance = - noderight->balance;
6973 de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	321
12421 e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9309 diff changeset	322 node->branch_size =
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9309 diff changeset	323 (nodeleft != NULL ? nodeleft->branch_size : 0)
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9309 diff changeset	324 + 1 + (noderightleft != NULL ? noderightleft->branch_size : 0);
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9309 diff changeset	325 noderight->branch_size =
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9309 diff changeset	326 node->branch_size + 1 + noderightright->branch_size;
6973 de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	327
12421 e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9309 diff changeset	328 *nodep = noderight;
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9309 diff changeset	329 height_diff = (height_diff < 0
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9309 diff changeset	330 ? /* nodeleft's height had been decremented from
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9309 diff changeset	331 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	332 h+3 to h+2\|h+3. */
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9309 diff changeset	333 - noderight->balance - 1
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9309 diff changeset	334 : /* noderight's height had been incremented from
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9309 diff changeset	335 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	336 h+2 to h+2\|h+3. */
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9309 diff changeset	337 - noderight->balance);
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9309 diff changeset	338 }
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9309 diff changeset	339 else
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9309 diff changeset	340 {
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9309 diff changeset	341 /*
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9309 diff changeset	342 * h+2
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9309 diff changeset	343 / \ / \
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9309 diff changeset	344 h h+2 --> h+1 h+1
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9309 diff changeset	345 / \ / \ / \
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9309 diff changeset	346 h+1 h h L R h
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9309 diff changeset	347 / \
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9309 diff changeset	348 L R
6973 de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	349
12421 e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9309 diff changeset	350 */
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9309 diff changeset	351 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	352 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	353 noderightleft->left = node;
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9309 diff changeset	354 noderightleft->right = noderight;
6973 de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	355
12421 e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9309 diff changeset	356 noderightleft->parent = node->parent;
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9309 diff changeset	357 if (L != NULL)
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9309 diff changeset	358 L->parent = node;
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9309 diff changeset	359 if (R != NULL)
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9309 diff changeset	360 R->parent = noderight;
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9309 diff changeset	361 node->parent = noderightleft;
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9309 diff changeset	362 noderight->parent = noderightleft;
6973 de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	363
12421 e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9309 diff changeset	364 node->balance = (noderightleft->balance > 0 ? -1 : 0);
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9309 diff changeset	365 noderight->balance = (noderightleft->balance < 0 ? 1 : 0);
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9309 diff changeset	366 noderightleft->balance = 0;
6973 de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	367
12421 e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9309 diff changeset	368 node->branch_size =
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9309 diff changeset	369 (node->left != NULL ? node->left->branch_size : 0)
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9309 diff changeset	370 + 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	371 noderight->branch_size =
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9309 diff changeset	372 (noderight->left != NULL ? noderight->left->branch_size : 0)
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9309 diff changeset	373 + 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	374 noderightleft->branch_size =
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9309 diff changeset	375 node->branch_size + 1 + noderight->branch_size;
6973 de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	376
12421 e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9309 diff changeset	377 *nodep = noderightleft;
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9309 diff changeset	378 height_diff = (height_diff < 0
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9309 diff changeset	379 ? /* nodeleft's height had been decremented from
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9309 diff changeset	380 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	381 h+3 to h+2. */
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9309 diff changeset	382 -1
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9309 diff changeset	383 : /* noderight's height had been incremented from
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9309 diff changeset	384 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	385 h+2 to h+2. */
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9309 diff changeset	386 0);
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9309 diff changeset	387 }
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9309 diff changeset	388 }
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9309 diff changeset	389 node = *nodep;
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9309 diff changeset	390 }
6973 de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	391 else
12421 e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9309 diff changeset	392 {
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9309 diff changeset	393 /* 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	394 next higher level. */
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9309 diff changeset	395 if (height_diff < 0)
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9309 diff changeset	396 height_diff = (previous_balance == 0 ? 0 : -1);
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9309 diff changeset	397 else
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9309 diff changeset	398 height_diff = (node->balance == 0 ? 0 : 1);
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9309 diff changeset	399 }
6973 de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	400
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	401 if (height_diff == 0)
12421 e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9309 diff changeset	402 break;
6973 de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	403
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	404 parent = node->parent;
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	405 if (parent == NULL)
12421 e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9309 diff changeset	406 break;
6973 de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	407 }
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	408 }
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	409
12445 a8c91b846640 Move the malloc checking from module 'list' to new module 'xlist'. Bruno Haible <bruno@clisp.org> parents: 12421 diff changeset	410 static void
a8c91b846640 Move the malloc checking from module 'list' to new module 'xlist'. Bruno Haible <bruno@clisp.org> parents: 12421 diff changeset	411 gl_tree_remove_node_from_tree (gl_list_t list, gl_list_node_t node)
6973 de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	412 {
12445 a8c91b846640 Move the malloc checking from module 'list' to new module 'xlist'. Bruno Haible <bruno@clisp.org> parents: 12421 diff changeset	413 gl_list_node_t parent = node->parent;
6973 de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	414
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	415 if (node->left == NULL)
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	416 {
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	417 /* Replace node with node->right. */
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	418 gl_list_node_t child = node->right;
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	419
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	420 if (child != NULL)
12421 e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9309 diff changeset	421 child->parent = parent;
6973 de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	422 if (parent == NULL)
12421 e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9309 diff changeset	423 list->root = child;
6973 de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	424 else
12421 e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9309 diff changeset	425 {
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9309 diff changeset	426 if (parent->left == node)
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9309 diff changeset	427 parent->left = child;
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9309 diff changeset	428 else /* parent->right == node */
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9309 diff changeset	429 parent->right = child;
6973 de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	430
12421 e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9309 diff changeset	431 /* Update branch_size fields of the parent nodes. */
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9309 diff changeset	432 {
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9309 diff changeset	433 gl_list_node_t p;
6973 de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	434
12421 e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9309 diff changeset	435 for (p = parent; p != NULL; p = p->parent)
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9309 diff changeset	436 p->branch_size--;
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9309 diff changeset	437 }
6973 de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	438
12421 e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9309 diff changeset	439 rebalance (list, child, -1, parent);
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9309 diff changeset	440 }
6973 de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	441 }
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	442 else if (node->right == NULL)
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	443 {
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	444 /* 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	445 general case below is more complicated, hence slower. */
6973 de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	446 /* Replace node with node->left. */
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	447 gl_list_node_t child = node->left;
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	448
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	449 child->parent = parent;
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	450 if (parent == NULL)
12421 e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9309 diff changeset	451 list->root = child;
6973 de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	452 else
12421 e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9309 diff changeset	453 {
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9309 diff changeset	454 if (parent->left == node)
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9309 diff changeset	455 parent->left = child;
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9309 diff changeset	456 else /* parent->right == node */
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9309 diff changeset	457 parent->right = child;
6973 de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	458
12421 e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9309 diff changeset	459 /* Update branch_size fields of the parent nodes. */
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9309 diff changeset	460 {
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9309 diff changeset	461 gl_list_node_t p;
6973 de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	462
12421 e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9309 diff changeset	463 for (p = parent; p != NULL; p = p->parent)
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9309 diff changeset	464 p->branch_size--;
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9309 diff changeset	465 }
6973 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 rebalance (list, child, -1, parent);
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9309 diff changeset	468 }
6973 de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	469 }
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	470 else
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 /* 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	473 gl_list_node_t subst;
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	474 gl_list_node_t subst_parent;
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	475 gl_list_node_t child;
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 for (subst = node->left; subst->right != NULL; )
12421 e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9309 diff changeset	478 subst = subst->right;
6973 de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	479
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	480 subst_parent = subst->parent;
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	481
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	482 child = subst->left;
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	483
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	484 /* 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	485 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	486 subst_parent == node
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9309 diff changeset	487 <==> The 'for' loop above terminated immediately.
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9309 diff changeset	488 <==> subst == subst_parent->left
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9309 diff changeset	489 [otherwise subst == subst_parent->right]
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9309 diff changeset	490 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	491 child->parent = node; node->left = child;
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9309 diff changeset	492 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	493 child->parent = subst; subst->left = child;
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9309 diff changeset	494 Altogether a no-op. */
6973 de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	495 if (subst_parent != node)
12421 e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9309 diff changeset	496 {
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9309 diff changeset	497 if (child != NULL)
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9309 diff changeset	498 child->parent = subst_parent;
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9309 diff changeset	499 subst_parent->right = child;
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9309 diff changeset	500 }
6973 de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	501
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	502 /* Update branch_size fields of the parent nodes. */
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	503 {
12421 e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9309 diff changeset	504 gl_list_node_t p;
6973 de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	505
12421 e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9309 diff changeset	506 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	507 p->branch_size--;
6973 de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	508 }
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	509
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	510 /* Copy subst into node's position.
12421 e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9309 diff changeset	511 (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	512 place, and free subst.) */
6973 de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	513 if (subst_parent != node)
12421 e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9309 diff changeset	514 {
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9309 diff changeset	515 subst->left = node->left;
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9309 diff changeset	516 subst->left->parent = subst;
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9309 diff changeset	517 }
6973 de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	518 subst->right = node->right;
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	519 subst->right->parent = subst;
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	520 subst->balance = node->balance;
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	521 subst->branch_size = node->branch_size;
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	522 subst->parent = parent;
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	523 if (parent == NULL)
12421 e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9309 diff changeset	524 list->root = subst;
6973 de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	525 else if (parent->left == node)
12421 e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9309 diff changeset	526 parent->left = subst;
6973 de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	527 else /* parent->right == node */
12421 e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9309 diff changeset	528 parent->right = subst;
6973 de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	529
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	530 /* 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	531 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	532 its replacement, subst. */
6973 de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	533 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	534 }
12445 a8c91b846640 Move the malloc checking from module 'list' to new module 'xlist'. Bruno Haible <bruno@clisp.org> parents: 12421 diff changeset	535 }
6973 de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	536
12445 a8c91b846640 Move the malloc checking from module 'list' to new module 'xlist'. Bruno Haible <bruno@clisp.org> parents: 12421 diff changeset	537 static gl_list_node_t
a8c91b846640 Move the malloc checking from module 'list' to new module 'xlist'. Bruno Haible <bruno@clisp.org> parents: 12421 diff changeset	538 gl_tree_nx_add_first (gl_list_t list, const void *elt)
a8c91b846640 Move the malloc checking from module 'list' to new module 'xlist'. Bruno Haible <bruno@clisp.org> parents: 12421 diff changeset	539 {
a8c91b846640 Move the malloc checking from module 'list' to new module 'xlist'. Bruno Haible <bruno@clisp.org> parents: 12421 diff changeset	540 /* Create new node. */
a8c91b846640 Move the malloc checking from module 'list' to new module 'xlist'. Bruno Haible <bruno@clisp.org> parents: 12421 diff changeset	541 gl_list_node_t new_node =
a8c91b846640 Move the malloc checking from module 'list' to new module 'xlist'. Bruno Haible <bruno@clisp.org> parents: 12421 diff changeset	542 (struct gl_list_node_impl *) malloc (sizeof (struct gl_list_node_impl));
a8c91b846640 Move the malloc checking from module 'list' to new module 'xlist'. Bruno Haible <bruno@clisp.org> parents: 12421 diff changeset	543
a8c91b846640 Move the malloc checking from module 'list' to new module 'xlist'. Bruno Haible <bruno@clisp.org> parents: 12421 diff changeset	544 if (new_node == NULL)
a8c91b846640 Move the malloc checking from module 'list' to new module 'xlist'. Bruno Haible <bruno@clisp.org> parents: 12421 diff changeset	545 return NULL;
a8c91b846640 Move the malloc checking from module 'list' to new module 'xlist'. Bruno Haible <bruno@clisp.org> parents: 12421 diff changeset	546
a8c91b846640 Move the malloc checking from module 'list' to new module 'xlist'. Bruno Haible <bruno@clisp.org> parents: 12421 diff changeset	547 new_node->left = NULL;
a8c91b846640 Move the malloc checking from module 'list' to new module 'xlist'. Bruno Haible <bruno@clisp.org> parents: 12421 diff changeset	548 new_node->right = NULL;
a8c91b846640 Move the malloc checking from module 'list' to new module 'xlist'. Bruno Haible <bruno@clisp.org> parents: 12421 diff changeset	549 new_node->balance = 0;
a8c91b846640 Move the malloc checking from module 'list' to new module 'xlist'. Bruno Haible <bruno@clisp.org> parents: 12421 diff changeset	550 new_node->branch_size = 1;
a8c91b846640 Move the malloc checking from module 'list' to new module 'xlist'. Bruno Haible <bruno@clisp.org> parents: 12421 diff changeset	551 new_node->value = elt;
a8c91b846640 Move the malloc checking from module 'list' to new module 'xlist'. Bruno Haible <bruno@clisp.org> parents: 12421 diff changeset	552 #if WITH_HASHTABLE
a8c91b846640 Move the malloc checking from module 'list' to new module 'xlist'. Bruno Haible <bruno@clisp.org> parents: 12421 diff changeset	553 new_node->h.hashcode =
a8c91b846640 Move the malloc checking from module 'list' to new module 'xlist'. Bruno Haible <bruno@clisp.org> parents: 12421 diff changeset	554 (list->base.hashcode_fn != NULL
a8c91b846640 Move the malloc checking from module 'list' to new module 'xlist'. Bruno Haible <bruno@clisp.org> parents: 12421 diff changeset	555 ? list->base.hashcode_fn (new_node->value)
a8c91b846640 Move the malloc checking from module 'list' to new module 'xlist'. Bruno Haible <bruno@clisp.org> parents: 12421 diff changeset	556 : (size_t)(uintptr_t) new_node->value);
a8c91b846640 Move the malloc checking from module 'list' to new module 'xlist'. Bruno Haible <bruno@clisp.org> parents: 12421 diff changeset	557 #endif
a8c91b846640 Move the malloc checking from module 'list' to new module 'xlist'. Bruno Haible <bruno@clisp.org> parents: 12421 diff changeset	558
a8c91b846640 Move the malloc checking from module 'list' to new module 'xlist'. Bruno Haible <bruno@clisp.org> parents: 12421 diff changeset	559 /* Add it to the tree. */
a8c91b846640 Move the malloc checking from module 'list' to new module 'xlist'. Bruno Haible <bruno@clisp.org> parents: 12421 diff changeset	560 if (list->root == NULL)
a8c91b846640 Move the malloc checking from module 'list' to new module 'xlist'. Bruno Haible <bruno@clisp.org> parents: 12421 diff changeset	561 {
a8c91b846640 Move the malloc checking from module 'list' to new module 'xlist'. Bruno Haible <bruno@clisp.org> parents: 12421 diff changeset	562 list->root = new_node;
a8c91b846640 Move the malloc checking from module 'list' to new module 'xlist'. Bruno Haible <bruno@clisp.org> parents: 12421 diff changeset	563 new_node->parent = NULL;
a8c91b846640 Move the malloc checking from module 'list' to new module 'xlist'. Bruno Haible <bruno@clisp.org> parents: 12421 diff changeset	564 }
a8c91b846640 Move the malloc checking from module 'list' to new module 'xlist'. Bruno Haible <bruno@clisp.org> parents: 12421 diff changeset	565 else
a8c91b846640 Move the malloc checking from module 'list' to new module 'xlist'. Bruno Haible <bruno@clisp.org> parents: 12421 diff changeset	566 {
a8c91b846640 Move the malloc checking from module 'list' to new module 'xlist'. Bruno Haible <bruno@clisp.org> parents: 12421 diff changeset	567 gl_list_node_t node;
a8c91b846640 Move the malloc checking from module 'list' to new module 'xlist'. Bruno Haible <bruno@clisp.org> parents: 12421 diff changeset	568
a8c91b846640 Move the malloc checking from module 'list' to new module 'xlist'. Bruno Haible <bruno@clisp.org> parents: 12421 diff changeset	569 for (node = list->root; node->left != NULL; )
a8c91b846640 Move the malloc checking from module 'list' to new module 'xlist'. Bruno Haible <bruno@clisp.org> parents: 12421 diff changeset	570 node = node->left;
a8c91b846640 Move the malloc checking from module 'list' to new module 'xlist'. Bruno Haible <bruno@clisp.org> parents: 12421 diff changeset	571
a8c91b846640 Move the malloc checking from module 'list' to new module 'xlist'. Bruno Haible <bruno@clisp.org> parents: 12421 diff changeset	572 node->left = new_node;
a8c91b846640 Move the malloc checking from module 'list' to new module 'xlist'. Bruno Haible <bruno@clisp.org> parents: 12421 diff changeset	573 new_node->parent = node;
a8c91b846640 Move the malloc checking from module 'list' to new module 'xlist'. Bruno Haible <bruno@clisp.org> parents: 12421 diff changeset	574 node->balance--;
a8c91b846640 Move the malloc checking from module 'list' to new module 'xlist'. Bruno Haible <bruno@clisp.org> parents: 12421 diff changeset	575
a8c91b846640 Move the malloc checking from module 'list' to new module 'xlist'. Bruno Haible <bruno@clisp.org> parents: 12421 diff changeset	576 /* Update branch_size fields of the parent nodes. */
a8c91b846640 Move the malloc checking from module 'list' to new module 'xlist'. Bruno Haible <bruno@clisp.org> parents: 12421 diff changeset	577 {
a8c91b846640 Move the malloc checking from module 'list' to new module 'xlist'. Bruno Haible <bruno@clisp.org> parents: 12421 diff changeset	578 gl_list_node_t p;
a8c91b846640 Move the malloc checking from module 'list' to new module 'xlist'. Bruno Haible <bruno@clisp.org> parents: 12421 diff changeset	579
a8c91b846640 Move the malloc checking from module 'list' to new module 'xlist'. Bruno Haible <bruno@clisp.org> parents: 12421 diff changeset	580 for (p = node; p != NULL; p = p->parent)
a8c91b846640 Move the malloc checking from module 'list' to new module 'xlist'. Bruno Haible <bruno@clisp.org> parents: 12421 diff changeset	581 p->branch_size++;
a8c91b846640 Move the malloc checking from module 'list' to new module 'xlist'. Bruno Haible <bruno@clisp.org> parents: 12421 diff changeset	582 }
a8c91b846640 Move the malloc checking from module 'list' to new module 'xlist'. Bruno Haible <bruno@clisp.org> parents: 12421 diff changeset	583
a8c91b846640 Move the malloc checking from module 'list' to new module 'xlist'. Bruno Haible <bruno@clisp.org> parents: 12421 diff changeset	584 /* Rebalance. */
a8c91b846640 Move the malloc checking from module 'list' to new module 'xlist'. Bruno Haible <bruno@clisp.org> parents: 12421 diff changeset	585 if (node->right == NULL && node->parent != NULL)
a8c91b846640 Move the malloc checking from module 'list' to new module 'xlist'. Bruno Haible <bruno@clisp.org> parents: 12421 diff changeset	586 rebalance (list, node, 1, node->parent);
a8c91b846640 Move the malloc checking from module 'list' to new module 'xlist'. Bruno Haible <bruno@clisp.org> parents: 12421 diff changeset	587 }
a8c91b846640 Move the malloc checking from module 'list' to new module 'xlist'. Bruno Haible <bruno@clisp.org> parents: 12421 diff changeset	588
a8c91b846640 Move the malloc checking from module 'list' to new module 'xlist'. Bruno Haible <bruno@clisp.org> parents: 12421 diff changeset	589 #if WITH_HASHTABLE
a8c91b846640 Move the malloc checking from module 'list' to new module 'xlist'. Bruno Haible <bruno@clisp.org> parents: 12421 diff changeset	590 /* Add node to the hash table.
a8c91b846640 Move the malloc checking from module 'list' to new module 'xlist'. Bruno Haible <bruno@clisp.org> parents: 12421 diff changeset	591 Note that this is only possible _after_ the node has been added to the
a8c91b846640 Move the malloc checking from module 'list' to new module 'xlist'. Bruno Haible <bruno@clisp.org> parents: 12421 diff changeset	592 tree structure, because add_to_bucket() uses node_position(). */
a8c91b846640 Move the malloc checking from module 'list' to new module 'xlist'. Bruno Haible <bruno@clisp.org> parents: 12421 diff changeset	593 if (add_to_bucket (list, new_node) < 0)
a8c91b846640 Move the malloc checking from module 'list' to new module 'xlist'. Bruno Haible <bruno@clisp.org> parents: 12421 diff changeset	594 {
a8c91b846640 Move the malloc checking from module 'list' to new module 'xlist'. Bruno Haible <bruno@clisp.org> parents: 12421 diff changeset	595 gl_tree_remove_node_from_tree (list, new_node);
a8c91b846640 Move the malloc checking from module 'list' to new module 'xlist'. Bruno Haible <bruno@clisp.org> parents: 12421 diff changeset	596 free (new_node);
a8c91b846640 Move the malloc checking from module 'list' to new module 'xlist'. Bruno Haible <bruno@clisp.org> parents: 12421 diff changeset	597 return NULL;
a8c91b846640 Move the malloc checking from module 'list' to new module 'xlist'. Bruno Haible <bruno@clisp.org> parents: 12421 diff changeset	598 }
a8c91b846640 Move the malloc checking from module 'list' to new module 'xlist'. Bruno Haible <bruno@clisp.org> parents: 12421 diff changeset	599 hash_resize_after_add (list);
a8c91b846640 Move the malloc checking from module 'list' to new module 'xlist'. Bruno Haible <bruno@clisp.org> parents: 12421 diff changeset	600 #endif
a8c91b846640 Move the malloc checking from module 'list' to new module 'xlist'. Bruno Haible <bruno@clisp.org> parents: 12421 diff changeset	601
a8c91b846640 Move the malloc checking from module 'list' to new module 'xlist'. Bruno Haible <bruno@clisp.org> parents: 12421 diff changeset	602 return new_node;
a8c91b846640 Move the malloc checking from module 'list' to new module 'xlist'. Bruno Haible <bruno@clisp.org> parents: 12421 diff changeset	603 }
a8c91b846640 Move the malloc checking from module 'list' to new module 'xlist'. Bruno Haible <bruno@clisp.org> parents: 12421 diff changeset	604
a8c91b846640 Move the malloc checking from module 'list' to new module 'xlist'. Bruno Haible <bruno@clisp.org> parents: 12421 diff changeset	605 static gl_list_node_t
a8c91b846640 Move the malloc checking from module 'list' to new module 'xlist'. Bruno Haible <bruno@clisp.org> parents: 12421 diff changeset	606 gl_tree_nx_add_last (gl_list_t list, const void *elt)
a8c91b846640 Move the malloc checking from module 'list' to new module 'xlist'. Bruno Haible <bruno@clisp.org> parents: 12421 diff changeset	607 {
a8c91b846640 Move the malloc checking from module 'list' to new module 'xlist'. Bruno Haible <bruno@clisp.org> parents: 12421 diff changeset	608 /* Create new node. */
a8c91b846640 Move the malloc checking from module 'list' to new module 'xlist'. Bruno Haible <bruno@clisp.org> parents: 12421 diff changeset	609 gl_list_node_t new_node =
a8c91b846640 Move the malloc checking from module 'list' to new module 'xlist'. Bruno Haible <bruno@clisp.org> parents: 12421 diff changeset	610 (struct gl_list_node_impl *) malloc (sizeof (struct gl_list_node_impl));
a8c91b846640 Move the malloc checking from module 'list' to new module 'xlist'. Bruno Haible <bruno@clisp.org> parents: 12421 diff changeset	611
a8c91b846640 Move the malloc checking from module 'list' to new module 'xlist'. Bruno Haible <bruno@clisp.org> parents: 12421 diff changeset	612 if (new_node == NULL)
a8c91b846640 Move the malloc checking from module 'list' to new module 'xlist'. Bruno Haible <bruno@clisp.org> parents: 12421 diff changeset	613 return NULL;
a8c91b846640 Move the malloc checking from module 'list' to new module 'xlist'. Bruno Haible <bruno@clisp.org> parents: 12421 diff changeset	614
a8c91b846640 Move the malloc checking from module 'list' to new module 'xlist'. Bruno Haible <bruno@clisp.org> parents: 12421 diff changeset	615 new_node->left = NULL;
a8c91b846640 Move the malloc checking from module 'list' to new module 'xlist'. Bruno Haible <bruno@clisp.org> parents: 12421 diff changeset	616 new_node->right = NULL;
a8c91b846640 Move the malloc checking from module 'list' to new module 'xlist'. Bruno Haible <bruno@clisp.org> parents: 12421 diff changeset	617 new_node->balance = 0;
a8c91b846640 Move the malloc checking from module 'list' to new module 'xlist'. Bruno Haible <bruno@clisp.org> parents: 12421 diff changeset	618 new_node->branch_size = 1;
a8c91b846640 Move the malloc checking from module 'list' to new module 'xlist'. Bruno Haible <bruno@clisp.org> parents: 12421 diff changeset	619 new_node->value = elt;
a8c91b846640 Move the malloc checking from module 'list' to new module 'xlist'. Bruno Haible <bruno@clisp.org> parents: 12421 diff changeset	620 #if WITH_HASHTABLE
a8c91b846640 Move the malloc checking from module 'list' to new module 'xlist'. Bruno Haible <bruno@clisp.org> parents: 12421 diff changeset	621 new_node->h.hashcode =
a8c91b846640 Move the malloc checking from module 'list' to new module 'xlist'. Bruno Haible <bruno@clisp.org> parents: 12421 diff changeset	622 (list->base.hashcode_fn != NULL
a8c91b846640 Move the malloc checking from module 'list' to new module 'xlist'. Bruno Haible <bruno@clisp.org> parents: 12421 diff changeset	623 ? list->base.hashcode_fn (new_node->value)
a8c91b846640 Move the malloc checking from module 'list' to new module 'xlist'. Bruno Haible <bruno@clisp.org> parents: 12421 diff changeset	624 : (size_t)(uintptr_t) new_node->value);
a8c91b846640 Move the malloc checking from module 'list' to new module 'xlist'. Bruno Haible <bruno@clisp.org> parents: 12421 diff changeset	625 #endif
a8c91b846640 Move the malloc checking from module 'list' to new module 'xlist'. Bruno Haible <bruno@clisp.org> parents: 12421 diff changeset	626
a8c91b846640 Move the malloc checking from module 'list' to new module 'xlist'. Bruno Haible <bruno@clisp.org> parents: 12421 diff changeset	627 /* Add it to the tree. */
a8c91b846640 Move the malloc checking from module 'list' to new module 'xlist'. Bruno Haible <bruno@clisp.org> parents: 12421 diff changeset	628 if (list->root == NULL)
a8c91b846640 Move the malloc checking from module 'list' to new module 'xlist'. Bruno Haible <bruno@clisp.org> parents: 12421 diff changeset	629 {
a8c91b846640 Move the malloc checking from module 'list' to new module 'xlist'. Bruno Haible <bruno@clisp.org> parents: 12421 diff changeset	630 list->root = new_node;
a8c91b846640 Move the malloc checking from module 'list' to new module 'xlist'. Bruno Haible <bruno@clisp.org> parents: 12421 diff changeset	631 new_node->parent = NULL;
a8c91b846640 Move the malloc checking from module 'list' to new module 'xlist'. Bruno Haible <bruno@clisp.org> parents: 12421 diff changeset	632 }
a8c91b846640 Move the malloc checking from module 'list' to new module 'xlist'. Bruno Haible <bruno@clisp.org> parents: 12421 diff changeset	633 else
a8c91b846640 Move the malloc checking from module 'list' to new module 'xlist'. Bruno Haible <bruno@clisp.org> parents: 12421 diff changeset	634 {
a8c91b846640 Move the malloc checking from module 'list' to new module 'xlist'. Bruno Haible <bruno@clisp.org> parents: 12421 diff changeset	635 gl_list_node_t node;
a8c91b846640 Move the malloc checking from module 'list' to new module 'xlist'. Bruno Haible <bruno@clisp.org> parents: 12421 diff changeset	636
a8c91b846640 Move the malloc checking from module 'list' to new module 'xlist'. Bruno Haible <bruno@clisp.org> parents: 12421 diff changeset	637 for (node = list->root; node->right != NULL; )
a8c91b846640 Move the malloc checking from module 'list' to new module 'xlist'. Bruno Haible <bruno@clisp.org> parents: 12421 diff changeset	638 node = node->right;
a8c91b846640 Move the malloc checking from module 'list' to new module 'xlist'. Bruno Haible <bruno@clisp.org> parents: 12421 diff changeset	639
a8c91b846640 Move the malloc checking from module 'list' to new module 'xlist'. Bruno Haible <bruno@clisp.org> parents: 12421 diff changeset	640 node->right = new_node;
a8c91b846640 Move the malloc checking from module 'list' to new module 'xlist'. Bruno Haible <bruno@clisp.org> parents: 12421 diff changeset	641 new_node->parent = node;
a8c91b846640 Move the malloc checking from module 'list' to new module 'xlist'. Bruno Haible <bruno@clisp.org> parents: 12421 diff changeset	642 node->balance++;
a8c91b846640 Move the malloc checking from module 'list' to new module 'xlist'. Bruno Haible <bruno@clisp.org> parents: 12421 diff changeset	643
a8c91b846640 Move the malloc checking from module 'list' to new module 'xlist'. Bruno Haible <bruno@clisp.org> parents: 12421 diff changeset	644 /* Update branch_size fields of the parent nodes. */
a8c91b846640 Move the malloc checking from module 'list' to new module 'xlist'. Bruno Haible <bruno@clisp.org> parents: 12421 diff changeset	645 {
a8c91b846640 Move the malloc checking from module 'list' to new module 'xlist'. Bruno Haible <bruno@clisp.org> parents: 12421 diff changeset	646 gl_list_node_t p;
a8c91b846640 Move the malloc checking from module 'list' to new module 'xlist'. Bruno Haible <bruno@clisp.org> parents: 12421 diff changeset	647
a8c91b846640 Move the malloc checking from module 'list' to new module 'xlist'. Bruno Haible <bruno@clisp.org> parents: 12421 diff changeset	648 for (p = node; p != NULL; p = p->parent)
a8c91b846640 Move the malloc checking from module 'list' to new module 'xlist'. Bruno Haible <bruno@clisp.org> parents: 12421 diff changeset	649 p->branch_size++;
a8c91b846640 Move the malloc checking from module 'list' to new module 'xlist'. Bruno Haible <bruno@clisp.org> parents: 12421 diff changeset	650 }
a8c91b846640 Move the malloc checking from module 'list' to new module 'xlist'. Bruno Haible <bruno@clisp.org> parents: 12421 diff changeset	651
a8c91b846640 Move the malloc checking from module 'list' to new module 'xlist'. Bruno Haible <bruno@clisp.org> parents: 12421 diff changeset	652 /* Rebalance. */
a8c91b846640 Move the malloc checking from module 'list' to new module 'xlist'. Bruno Haible <bruno@clisp.org> parents: 12421 diff changeset	653 if (node->left == NULL && node->parent != NULL)
a8c91b846640 Move the malloc checking from module 'list' to new module 'xlist'. Bruno Haible <bruno@clisp.org> parents: 12421 diff changeset	654 rebalance (list, node, 1, node->parent);
a8c91b846640 Move the malloc checking from module 'list' to new module 'xlist'. Bruno Haible <bruno@clisp.org> parents: 12421 diff changeset	655 }
a8c91b846640 Move the malloc checking from module 'list' to new module 'xlist'. Bruno Haible <bruno@clisp.org> parents: 12421 diff changeset	656
a8c91b846640 Move the malloc checking from module 'list' to new module 'xlist'. Bruno Haible <bruno@clisp.org> parents: 12421 diff changeset	657 #if WITH_HASHTABLE
a8c91b846640 Move the malloc checking from module 'list' to new module 'xlist'. Bruno Haible <bruno@clisp.org> parents: 12421 diff changeset	658 /* Add node to the hash table.
a8c91b846640 Move the malloc checking from module 'list' to new module 'xlist'. Bruno Haible <bruno@clisp.org> parents: 12421 diff changeset	659 Note that this is only possible _after_ the node has been added to the
a8c91b846640 Move the malloc checking from module 'list' to new module 'xlist'. Bruno Haible <bruno@clisp.org> parents: 12421 diff changeset	660 tree structure, because add_to_bucket() uses node_position(). */
a8c91b846640 Move the malloc checking from module 'list' to new module 'xlist'. Bruno Haible <bruno@clisp.org> parents: 12421 diff changeset	661 if (add_to_bucket (list, new_node) < 0)
a8c91b846640 Move the malloc checking from module 'list' to new module 'xlist'. Bruno Haible <bruno@clisp.org> parents: 12421 diff changeset	662 {
a8c91b846640 Move the malloc checking from module 'list' to new module 'xlist'. Bruno Haible <bruno@clisp.org> parents: 12421 diff changeset	663 gl_tree_remove_node_from_tree (list, new_node);
a8c91b846640 Move the malloc checking from module 'list' to new module 'xlist'. Bruno Haible <bruno@clisp.org> parents: 12421 diff changeset	664 free (new_node);
a8c91b846640 Move the malloc checking from module 'list' to new module 'xlist'. Bruno Haible <bruno@clisp.org> parents: 12421 diff changeset	665 return NULL;
a8c91b846640 Move the malloc checking from module 'list' to new module 'xlist'. Bruno Haible <bruno@clisp.org> parents: 12421 diff changeset	666 }
a8c91b846640 Move the malloc checking from module 'list' to new module 'xlist'. Bruno Haible <bruno@clisp.org> parents: 12421 diff changeset	667 hash_resize_after_add (list);
a8c91b846640 Move the malloc checking from module 'list' to new module 'xlist'. Bruno Haible <bruno@clisp.org> parents: 12421 diff changeset	668 #endif
a8c91b846640 Move the malloc checking from module 'list' to new module 'xlist'. Bruno Haible <bruno@clisp.org> parents: 12421 diff changeset	669
a8c91b846640 Move the malloc checking from module 'list' to new module 'xlist'. Bruno Haible <bruno@clisp.org> parents: 12421 diff changeset	670 return new_node;
6973 de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	671 }
12445 a8c91b846640 Move the malloc checking from module 'list' to new module 'xlist'. Bruno Haible <bruno@clisp.org> parents: 12421 diff changeset	672
a8c91b846640 Move the malloc checking from module 'list' to new module 'xlist'. Bruno Haible <bruno@clisp.org> parents: 12421 diff changeset	673 static gl_list_node_t
a8c91b846640 Move the malloc checking from module 'list' to new module 'xlist'. Bruno Haible <bruno@clisp.org> parents: 12421 diff changeset	674 gl_tree_nx_add_before (gl_list_t list, gl_list_node_t node, const void *elt)
a8c91b846640 Move the malloc checking from module 'list' to new module 'xlist'. Bruno Haible <bruno@clisp.org> parents: 12421 diff changeset	675 {
a8c91b846640 Move the malloc checking from module 'list' to new module 'xlist'. Bruno Haible <bruno@clisp.org> parents: 12421 diff changeset	676 /* Create new node. */
a8c91b846640 Move the malloc checking from module 'list' to new module 'xlist'. Bruno Haible <bruno@clisp.org> parents: 12421 diff changeset	677 gl_list_node_t new_node;
a8c91b846640 Move the malloc checking from module 'list' to new module 'xlist'. Bruno Haible <bruno@clisp.org> parents: 12421 diff changeset	678 bool height_inc;
a8c91b846640 Move the malloc checking from module 'list' to new module 'xlist'. Bruno Haible <bruno@clisp.org> parents: 12421 diff changeset	679
a8c91b846640 Move the malloc checking from module 'list' to new module 'xlist'. Bruno Haible <bruno@clisp.org> parents: 12421 diff changeset	680 new_node =
a8c91b846640 Move the malloc checking from module 'list' to new module 'xlist'. Bruno Haible <bruno@clisp.org> parents: 12421 diff changeset	681 (struct gl_list_node_impl *) malloc (sizeof (struct gl_list_node_impl));
a8c91b846640 Move the malloc checking from module 'list' to new module 'xlist'. Bruno Haible <bruno@clisp.org> parents: 12421 diff changeset	682 if (new_node == NULL)
a8c91b846640 Move the malloc checking from module 'list' to new module 'xlist'. Bruno Haible <bruno@clisp.org> parents: 12421 diff changeset	683 return NULL;
a8c91b846640 Move the malloc checking from module 'list' to new module 'xlist'. Bruno Haible <bruno@clisp.org> parents: 12421 diff changeset	684
a8c91b846640 Move the malloc checking from module 'list' to new module 'xlist'. Bruno Haible <bruno@clisp.org> parents: 12421 diff changeset	685 new_node->left = NULL;
a8c91b846640 Move the malloc checking from module 'list' to new module 'xlist'. Bruno Haible <bruno@clisp.org> parents: 12421 diff changeset	686 new_node->right = NULL;
a8c91b846640 Move the malloc checking from module 'list' to new module 'xlist'. Bruno Haible <bruno@clisp.org> parents: 12421 diff changeset	687 new_node->balance = 0;
a8c91b846640 Move the malloc checking from module 'list' to new module 'xlist'. Bruno Haible <bruno@clisp.org> parents: 12421 diff changeset	688 new_node->branch_size = 1;
a8c91b846640 Move the malloc checking from module 'list' to new module 'xlist'. Bruno Haible <bruno@clisp.org> parents: 12421 diff changeset	689 new_node->value = elt;
a8c91b846640 Move the malloc checking from module 'list' to new module 'xlist'. Bruno Haible <bruno@clisp.org> parents: 12421 diff changeset	690 #if WITH_HASHTABLE
a8c91b846640 Move the malloc checking from module 'list' to new module 'xlist'. Bruno Haible <bruno@clisp.org> parents: 12421 diff changeset	691 new_node->h.hashcode =
a8c91b846640 Move the malloc checking from module 'list' to new module 'xlist'. Bruno Haible <bruno@clisp.org> parents: 12421 diff changeset	692 (list->base.hashcode_fn != NULL
a8c91b846640 Move the malloc checking from module 'list' to new module 'xlist'. Bruno Haible <bruno@clisp.org> parents: 12421 diff changeset	693 ? list->base.hashcode_fn (new_node->value)
a8c91b846640 Move the malloc checking from module 'list' to new module 'xlist'. Bruno Haible <bruno@clisp.org> parents: 12421 diff changeset	694 : (size_t)(uintptr_t) new_node->value);
a8c91b846640 Move the malloc checking from module 'list' to new module 'xlist'. Bruno Haible <bruno@clisp.org> parents: 12421 diff changeset	695 #endif
a8c91b846640 Move the malloc checking from module 'list' to new module 'xlist'. Bruno Haible <bruno@clisp.org> parents: 12421 diff changeset	696
a8c91b846640 Move the malloc checking from module 'list' to new module 'xlist'. Bruno Haible <bruno@clisp.org> parents: 12421 diff changeset	697 /* Add it to the tree. */
a8c91b846640 Move the malloc checking from module 'list' to new module 'xlist'. Bruno Haible <bruno@clisp.org> parents: 12421 diff changeset	698 if (node->left == NULL)
a8c91b846640 Move the malloc checking from module 'list' to new module 'xlist'. Bruno Haible <bruno@clisp.org> parents: 12421 diff changeset	699 {
a8c91b846640 Move the malloc checking from module 'list' to new module 'xlist'. Bruno Haible <bruno@clisp.org> parents: 12421 diff changeset	700 node->left = new_node;
a8c91b846640 Move the malloc checking from module 'list' to new module 'xlist'. Bruno Haible <bruno@clisp.org> parents: 12421 diff changeset	701 node->balance--;
a8c91b846640 Move the malloc checking from module 'list' to new module 'xlist'. Bruno Haible <bruno@clisp.org> parents: 12421 diff changeset	702 height_inc = (node->right == NULL);
a8c91b846640 Move the malloc checking from module 'list' to new module 'xlist'. Bruno Haible <bruno@clisp.org> parents: 12421 diff changeset	703 }
a8c91b846640 Move the malloc checking from module 'list' to new module 'xlist'. Bruno Haible <bruno@clisp.org> parents: 12421 diff changeset	704 else
a8c91b846640 Move the malloc checking from module 'list' to new module 'xlist'. Bruno Haible <bruno@clisp.org> parents: 12421 diff changeset	705 {
a8c91b846640 Move the malloc checking from module 'list' to new module 'xlist'. Bruno Haible <bruno@clisp.org> parents: 12421 diff changeset	706 for (node = node->left; node->right != NULL; )
a8c91b846640 Move the malloc checking from module 'list' to new module 'xlist'. Bruno Haible <bruno@clisp.org> parents: 12421 diff changeset	707 node = node->right;
a8c91b846640 Move the malloc checking from module 'list' to new module 'xlist'. Bruno Haible <bruno@clisp.org> parents: 12421 diff changeset	708 node->right = new_node;
a8c91b846640 Move the malloc checking from module 'list' to new module 'xlist'. Bruno Haible <bruno@clisp.org> parents: 12421 diff changeset	709 node->balance++;
a8c91b846640 Move the malloc checking from module 'list' to new module 'xlist'. Bruno Haible <bruno@clisp.org> parents: 12421 diff changeset	710 height_inc = (node->left == NULL);
a8c91b846640 Move the malloc checking from module 'list' to new module 'xlist'. Bruno Haible <bruno@clisp.org> parents: 12421 diff changeset	711 }
a8c91b846640 Move the malloc checking from module 'list' to new module 'xlist'. Bruno Haible <bruno@clisp.org> parents: 12421 diff changeset	712 new_node->parent = node;
a8c91b846640 Move the malloc checking from module 'list' to new module 'xlist'. Bruno Haible <bruno@clisp.org> parents: 12421 diff changeset	713
a8c91b846640 Move the malloc checking from module 'list' to new module 'xlist'. Bruno Haible <bruno@clisp.org> parents: 12421 diff changeset	714 /* Update branch_size fields of the parent nodes. */
a8c91b846640 Move the malloc checking from module 'list' to new module 'xlist'. Bruno Haible <bruno@clisp.org> parents: 12421 diff changeset	715 {
a8c91b846640 Move the malloc checking from module 'list' to new module 'xlist'. Bruno Haible <bruno@clisp.org> parents: 12421 diff changeset	716 gl_list_node_t p;
a8c91b846640 Move the malloc checking from module 'list' to new module 'xlist'. Bruno Haible <bruno@clisp.org> parents: 12421 diff changeset	717
a8c91b846640 Move the malloc checking from module 'list' to new module 'xlist'. Bruno Haible <bruno@clisp.org> parents: 12421 diff changeset	718 for (p = node; p != NULL; p = p->parent)
a8c91b846640 Move the malloc checking from module 'list' to new module 'xlist'. Bruno Haible <bruno@clisp.org> parents: 12421 diff changeset	719 p->branch_size++;
a8c91b846640 Move the malloc checking from module 'list' to new module 'xlist'. Bruno Haible <bruno@clisp.org> parents: 12421 diff changeset	720 }
a8c91b846640 Move the malloc checking from module 'list' to new module 'xlist'. Bruno Haible <bruno@clisp.org> parents: 12421 diff changeset	721
a8c91b846640 Move the malloc checking from module 'list' to new module 'xlist'. Bruno Haible <bruno@clisp.org> parents: 12421 diff changeset	722 /* Rebalance. */
a8c91b846640 Move the malloc checking from module 'list' to new module 'xlist'. Bruno Haible <bruno@clisp.org> parents: 12421 diff changeset	723 if (height_inc && node->parent != NULL)
a8c91b846640 Move the malloc checking from module 'list' to new module 'xlist'. Bruno Haible <bruno@clisp.org> parents: 12421 diff changeset	724 rebalance (list, node, 1, node->parent);
a8c91b846640 Move the malloc checking from module 'list' to new module 'xlist'. Bruno Haible <bruno@clisp.org> parents: 12421 diff changeset	725
a8c91b846640 Move the malloc checking from module 'list' to new module 'xlist'. Bruno Haible <bruno@clisp.org> parents: 12421 diff changeset	726 #if WITH_HASHTABLE
a8c91b846640 Move the malloc checking from module 'list' to new module 'xlist'. Bruno Haible <bruno@clisp.org> parents: 12421 diff changeset	727 /* Add node to the hash table.
a8c91b846640 Move the malloc checking from module 'list' to new module 'xlist'. Bruno Haible <bruno@clisp.org> parents: 12421 diff changeset	728 Note that this is only possible _after_ the node has been added to the
a8c91b846640 Move the malloc checking from module 'list' to new module 'xlist'. Bruno Haible <bruno@clisp.org> parents: 12421 diff changeset	729 tree structure, because add_to_bucket() uses node_position(). */
a8c91b846640 Move the malloc checking from module 'list' to new module 'xlist'. Bruno Haible <bruno@clisp.org> parents: 12421 diff changeset	730 if (add_to_bucket (list, new_node) < 0)
a8c91b846640 Move the malloc checking from module 'list' to new module 'xlist'. Bruno Haible <bruno@clisp.org> parents: 12421 diff changeset	731 {
a8c91b846640 Move the malloc checking from module 'list' to new module 'xlist'. Bruno Haible <bruno@clisp.org> parents: 12421 diff changeset	732 gl_tree_remove_node_from_tree (list, new_node);
a8c91b846640 Move the malloc checking from module 'list' to new module 'xlist'. Bruno Haible <bruno@clisp.org> parents: 12421 diff changeset	733 free (new_node);
a8c91b846640 Move the malloc checking from module 'list' to new module 'xlist'. Bruno Haible <bruno@clisp.org> parents: 12421 diff changeset	734 return NULL;
a8c91b846640 Move the malloc checking from module 'list' to new module 'xlist'. Bruno Haible <bruno@clisp.org> parents: 12421 diff changeset	735 }
a8c91b846640 Move the malloc checking from module 'list' to new module 'xlist'. Bruno Haible <bruno@clisp.org> parents: 12421 diff changeset	736 hash_resize_after_add (list);
a8c91b846640 Move the malloc checking from module 'list' to new module 'xlist'. Bruno Haible <bruno@clisp.org> parents: 12421 diff changeset	737 #endif
a8c91b846640 Move the malloc checking from module 'list' to new module 'xlist'. Bruno Haible <bruno@clisp.org> parents: 12421 diff changeset	738
a8c91b846640 Move the malloc checking from module 'list' to new module 'xlist'. Bruno Haible <bruno@clisp.org> parents: 12421 diff changeset	739 return new_node;
a8c91b846640 Move the malloc checking from module 'list' to new module 'xlist'. Bruno Haible <bruno@clisp.org> parents: 12421 diff changeset	740 }
a8c91b846640 Move the malloc checking from module 'list' to new module 'xlist'. Bruno Haible <bruno@clisp.org> parents: 12421 diff changeset	741
a8c91b846640 Move the malloc checking from module 'list' to new module 'xlist'. Bruno Haible <bruno@clisp.org> parents: 12421 diff changeset	742 static gl_list_node_t
a8c91b846640 Move the malloc checking from module 'list' to new module 'xlist'. Bruno Haible <bruno@clisp.org> parents: 12421 diff changeset	743 gl_tree_nx_add_after (gl_list_t list, gl_list_node_t node, const void *elt)
a8c91b846640 Move the malloc checking from module 'list' to new module 'xlist'. Bruno Haible <bruno@clisp.org> parents: 12421 diff changeset	744 {
a8c91b846640 Move the malloc checking from module 'list' to new module 'xlist'. Bruno Haible <bruno@clisp.org> parents: 12421 diff changeset	745 /* Create new node. */
a8c91b846640 Move the malloc checking from module 'list' to new module 'xlist'. Bruno Haible <bruno@clisp.org> parents: 12421 diff changeset	746 gl_list_node_t new_node;
a8c91b846640 Move the malloc checking from module 'list' to new module 'xlist'. Bruno Haible <bruno@clisp.org> parents: 12421 diff changeset	747 bool height_inc;
a8c91b846640 Move the malloc checking from module 'list' to new module 'xlist'. Bruno Haible <bruno@clisp.org> parents: 12421 diff changeset	748
a8c91b846640 Move the malloc checking from module 'list' to new module 'xlist'. Bruno Haible <bruno@clisp.org> parents: 12421 diff changeset	749 new_node =
a8c91b846640 Move the malloc checking from module 'list' to new module 'xlist'. Bruno Haible <bruno@clisp.org> parents: 12421 diff changeset	750 (struct gl_list_node_impl *) malloc (sizeof (struct gl_list_node_impl));
a8c91b846640 Move the malloc checking from module 'list' to new module 'xlist'. Bruno Haible <bruno@clisp.org> parents: 12421 diff changeset	751 if (new_node == NULL)
a8c91b846640 Move the malloc checking from module 'list' to new module 'xlist'. Bruno Haible <bruno@clisp.org> parents: 12421 diff changeset	752 return NULL;
a8c91b846640 Move the malloc checking from module 'list' to new module 'xlist'. Bruno Haible <bruno@clisp.org> parents: 12421 diff changeset	753
a8c91b846640 Move the malloc checking from module 'list' to new module 'xlist'. Bruno Haible <bruno@clisp.org> parents: 12421 diff changeset	754 new_node->left = NULL;
a8c91b846640 Move the malloc checking from module 'list' to new module 'xlist'. Bruno Haible <bruno@clisp.org> parents: 12421 diff changeset	755 new_node->right = NULL;
a8c91b846640 Move the malloc checking from module 'list' to new module 'xlist'. Bruno Haible <bruno@clisp.org> parents: 12421 diff changeset	756 new_node->balance = 0;
a8c91b846640 Move the malloc checking from module 'list' to new module 'xlist'. Bruno Haible <bruno@clisp.org> parents: 12421 diff changeset	757 new_node->branch_size = 1;
a8c91b846640 Move the malloc checking from module 'list' to new module 'xlist'. Bruno Haible <bruno@clisp.org> parents: 12421 diff changeset	758 new_node->value = elt;
a8c91b846640 Move the malloc checking from module 'list' to new module 'xlist'. Bruno Haible <bruno@clisp.org> parents: 12421 diff changeset	759 #if WITH_HASHTABLE
a8c91b846640 Move the malloc checking from module 'list' to new module 'xlist'. Bruno Haible <bruno@clisp.org> parents: 12421 diff changeset	760 new_node->h.hashcode =
a8c91b846640 Move the malloc checking from module 'list' to new module 'xlist'. Bruno Haible <bruno@clisp.org> parents: 12421 diff changeset	761 (list->base.hashcode_fn != NULL
a8c91b846640 Move the malloc checking from module 'list' to new module 'xlist'. Bruno Haible <bruno@clisp.org> parents: 12421 diff changeset	762 ? list->base.hashcode_fn (new_node->value)
a8c91b846640 Move the malloc checking from module 'list' to new module 'xlist'. Bruno Haible <bruno@clisp.org> parents: 12421 diff changeset	763 : (size_t)(uintptr_t) new_node->value);
a8c91b846640 Move the malloc checking from module 'list' to new module 'xlist'. Bruno Haible <bruno@clisp.org> parents: 12421 diff changeset	764 #endif
a8c91b846640 Move the malloc checking from module 'list' to new module 'xlist'. Bruno Haible <bruno@clisp.org> parents: 12421 diff changeset	765
a8c91b846640 Move the malloc checking from module 'list' to new module 'xlist'. Bruno Haible <bruno@clisp.org> parents: 12421 diff changeset	766 /* Add it to the tree. */
a8c91b846640 Move the malloc checking from module 'list' to new module 'xlist'. Bruno Haible <bruno@clisp.org> parents: 12421 diff changeset	767 if (node->right == NULL)
a8c91b846640 Move the malloc checking from module 'list' to new module 'xlist'. Bruno Haible <bruno@clisp.org> parents: 12421 diff changeset	768 {
a8c91b846640 Move the malloc checking from module 'list' to new module 'xlist'. Bruno Haible <bruno@clisp.org> parents: 12421 diff changeset	769 node->right = new_node;
a8c91b846640 Move the malloc checking from module 'list' to new module 'xlist'. Bruno Haible <bruno@clisp.org> parents: 12421 diff changeset	770 node->balance++;
a8c91b846640 Move the malloc checking from module 'list' to new module 'xlist'. Bruno Haible <bruno@clisp.org> parents: 12421 diff changeset	771 height_inc = (node->left == NULL);
a8c91b846640 Move the malloc checking from module 'list' to new module 'xlist'. Bruno Haible <bruno@clisp.org> parents: 12421 diff changeset	772 }
a8c91b846640 Move the malloc checking from module 'list' to new module 'xlist'. Bruno Haible <bruno@clisp.org> parents: 12421 diff changeset	773 else
a8c91b846640 Move the malloc checking from module 'list' to new module 'xlist'. Bruno Haible <bruno@clisp.org> parents: 12421 diff changeset	774 {
a8c91b846640 Move the malloc checking from module 'list' to new module 'xlist'. Bruno Haible <bruno@clisp.org> parents: 12421 diff changeset	775 for (node = node->right; node->left != NULL; )
a8c91b846640 Move the malloc checking from module 'list' to new module 'xlist'. Bruno Haible <bruno@clisp.org> parents: 12421 diff changeset	776 node = node->left;
a8c91b846640 Move the malloc checking from module 'list' to new module 'xlist'. Bruno Haible <bruno@clisp.org> parents: 12421 diff changeset	777 node->left = new_node;
a8c91b846640 Move the malloc checking from module 'list' to new module 'xlist'. Bruno Haible <bruno@clisp.org> parents: 12421 diff changeset	778 node->balance--;
a8c91b846640 Move the malloc checking from module 'list' to new module 'xlist'. Bruno Haible <bruno@clisp.org> parents: 12421 diff changeset	779 height_inc = (node->right == NULL);
a8c91b846640 Move the malloc checking from module 'list' to new module 'xlist'. Bruno Haible <bruno@clisp.org> parents: 12421 diff changeset	780 }
a8c91b846640 Move the malloc checking from module 'list' to new module 'xlist'. Bruno Haible <bruno@clisp.org> parents: 12421 diff changeset	781 new_node->parent = node;
a8c91b846640 Move the malloc checking from module 'list' to new module 'xlist'. Bruno Haible <bruno@clisp.org> parents: 12421 diff changeset	782
a8c91b846640 Move the malloc checking from module 'list' to new module 'xlist'. Bruno Haible <bruno@clisp.org> parents: 12421 diff changeset	783 /* Update branch_size fields of the parent nodes. */
a8c91b846640 Move the malloc checking from module 'list' to new module 'xlist'. Bruno Haible <bruno@clisp.org> parents: 12421 diff changeset	784 {
a8c91b846640 Move the malloc checking from module 'list' to new module 'xlist'. Bruno Haible <bruno@clisp.org> parents: 12421 diff changeset	785 gl_list_node_t p;
a8c91b846640 Move the malloc checking from module 'list' to new module 'xlist'. Bruno Haible <bruno@clisp.org> parents: 12421 diff changeset	786
a8c91b846640 Move the malloc checking from module 'list' to new module 'xlist'. Bruno Haible <bruno@clisp.org> parents: 12421 diff changeset	787 for (p = node; p != NULL; p = p->parent)
a8c91b846640 Move the malloc checking from module 'list' to new module 'xlist'. Bruno Haible <bruno@clisp.org> parents: 12421 diff changeset	788 p->branch_size++;
a8c91b846640 Move the malloc checking from module 'list' to new module 'xlist'. Bruno Haible <bruno@clisp.org> parents: 12421 diff changeset	789 }
a8c91b846640 Move the malloc checking from module 'list' to new module 'xlist'. Bruno Haible <bruno@clisp.org> parents: 12421 diff changeset	790
a8c91b846640 Move the malloc checking from module 'list' to new module 'xlist'. Bruno Haible <bruno@clisp.org> parents: 12421 diff changeset	791 /* Rebalance. */
a8c91b846640 Move the malloc checking from module 'list' to new module 'xlist'. Bruno Haible <bruno@clisp.org> parents: 12421 diff changeset	792 if (height_inc && node->parent != NULL)
a8c91b846640 Move the malloc checking from module 'list' to new module 'xlist'. Bruno Haible <bruno@clisp.org> parents: 12421 diff changeset	793 rebalance (list, node, 1, node->parent);
a8c91b846640 Move the malloc checking from module 'list' to new module 'xlist'. Bruno Haible <bruno@clisp.org> parents: 12421 diff changeset	794
a8c91b846640 Move the malloc checking from module 'list' to new module 'xlist'. Bruno Haible <bruno@clisp.org> parents: 12421 diff changeset	795 #if WITH_HASHTABLE
a8c91b846640 Move the malloc checking from module 'list' to new module 'xlist'. Bruno Haible <bruno@clisp.org> parents: 12421 diff changeset	796 /* Add node to the hash table.
a8c91b846640 Move the malloc checking from module 'list' to new module 'xlist'. Bruno Haible <bruno@clisp.org> parents: 12421 diff changeset	797 Note that this is only possible _after_ the node has been added to the
a8c91b846640 Move the malloc checking from module 'list' to new module 'xlist'. Bruno Haible <bruno@clisp.org> parents: 12421 diff changeset	798 tree structure, because add_to_bucket() uses node_position(). */
a8c91b846640 Move the malloc checking from module 'list' to new module 'xlist'. Bruno Haible <bruno@clisp.org> parents: 12421 diff changeset	799 if (add_to_bucket (list, new_node) < 0)
a8c91b846640 Move the malloc checking from module 'list' to new module 'xlist'. Bruno Haible <bruno@clisp.org> parents: 12421 diff changeset	800 {
a8c91b846640 Move the malloc checking from module 'list' to new module 'xlist'. Bruno Haible <bruno@clisp.org> parents: 12421 diff changeset	801 gl_tree_remove_node_from_tree (list, new_node);
a8c91b846640 Move the malloc checking from module 'list' to new module 'xlist'. Bruno Haible <bruno@clisp.org> parents: 12421 diff changeset	802 free (new_node);
a8c91b846640 Move the malloc checking from module 'list' to new module 'xlist'. Bruno Haible <bruno@clisp.org> parents: 12421 diff changeset	803 return NULL;
a8c91b846640 Move the malloc checking from module 'list' to new module 'xlist'. Bruno Haible <bruno@clisp.org> parents: 12421 diff changeset	804 }
a8c91b846640 Move the malloc checking from module 'list' to new module 'xlist'. Bruno Haible <bruno@clisp.org> parents: 12421 diff changeset	805 hash_resize_after_add (list);
a8c91b846640 Move the malloc checking from module 'list' to new module 'xlist'. Bruno Haible <bruno@clisp.org> parents: 12421 diff changeset	806 #endif
a8c91b846640 Move the malloc checking from module 'list' to new module 'xlist'. Bruno Haible <bruno@clisp.org> parents: 12421 diff changeset	807
a8c91b846640 Move the malloc checking from module 'list' to new module 'xlist'. Bruno Haible <bruno@clisp.org> parents: 12421 diff changeset	808 return new_node;
a8c91b846640 Move the malloc checking from module 'list' to new module 'xlist'. Bruno Haible <bruno@clisp.org> parents: 12421 diff changeset	809 }

Mercurial > gnulib

annotate lib/gl_anyavltree_list2.h @ 40196:e63f5d3edab5