X-Git-Url: http://erislabs.net/gitweb/?a=blobdiff_plain;f=lib%2Fgl_anyavltree_list2.h;h=90a2b0fbd6c52b771c643523b2f321e5b0081495;hb=5191b3546cfb6c163228c23f214e325ddf60d46f;hp=a4c26c58eb796ca1e7a902e9e47f80dbcc981f6a;hpb=0a51cf1590113188ff1dc78dc79d2924c262a865;p=gnulib.git diff --git a/lib/gl_anyavltree_list2.h b/lib/gl_anyavltree_list2.h index a4c26c58e..90a2b0fbd 100644 --- a/lib/gl_anyavltree_list2.h +++ b/lib/gl_anyavltree_list2.h @@ -1,11 +1,11 @@ /* Sequential list data type implemented by a binary tree. - Copyright (C) 2006 Free Software Foundation, Inc. + Copyright (C) 2006-2007, 2009-2013 Free Software Foundation, Inc. Written by Bruno Haible , 2006. - This program is free software; you can redistribute it and/or modify + This program is free software: you can redistribute it and/or modify it under the terms of the GNU General Public License as published by - the Free Software Foundation; either version 2, or (at your option) - any later version. + the Free Software Foundation; either version 3 of the License, or + (at your option) any later version. This program is distributed in the hope that it will be useful, but WITHOUT ANY WARRANTY; without even the implied warranty of @@ -13,15 +13,15 @@ GNU General Public License for more details. You should have received a copy of the GNU General Public License - along with this program; if not, write to the Free Software Foundation, - Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301, USA. */ + along with this program. If not, see . */ /* Common code of gl_avltree_list.c and gl_avltreehash_list.c. */ /* -------------------------- gl_list_t Data Type -------------------------- */ /* Create a subtree for count >= 1 elements. - Its height is h where 2^(h-1) <= count <= 2^h - 1. */ + Its height is h where 2^(h-1) <= count <= 2^h - 1. + Return NULL upon out-of-memory. */ static gl_list_node_t create_subtree_with_contents (size_t count, const void **contents) { @@ -29,11 +29,15 @@ create_subtree_with_contents (size_t count, const void **contents) size_t half2 = count / 2; /* Note: half1 + half2 = count - 1. */ gl_list_node_t node = - (struct gl_list_node_impl *) xmalloc (sizeof (struct gl_list_node_impl)); + (struct gl_list_node_impl *) malloc (sizeof (struct gl_list_node_impl)); + if (node == NULL) + return NULL; if (half1 > 0) { node->left = create_subtree_with_contents (half1, contents); + if (node->left == NULL) + goto fail1; node->left->parent = node; } else @@ -44,6 +48,8 @@ create_subtree_with_contents (size_t count, const void **contents) if (half2 > 0) { node->right = create_subtree_with_contents (half2, contents + half1 + 1); + if (node->right == NULL) + goto fail2; node->right->parent = node; } else @@ -58,21 +64,33 @@ create_subtree_with_contents (size_t count, const void **contents) node->branch_size = count; return node; + + fail2: + if (node->left != NULL) + free_subtree (node->left); + fail1: + free (node); + return NULL; } static gl_list_t -gl_tree_create (gl_list_implementation_t implementation, - gl_listelement_equals_fn equals_fn, - gl_listelement_hashcode_fn hashcode_fn, - bool allow_duplicates, - size_t count, const void **contents) +gl_tree_nx_create (gl_list_implementation_t implementation, + gl_listelement_equals_fn equals_fn, + gl_listelement_hashcode_fn hashcode_fn, + gl_listelement_dispose_fn dispose_fn, + bool allow_duplicates, + size_t count, const void **contents) { struct gl_list_impl *list = - (struct gl_list_impl *) xmalloc (sizeof (struct gl_list_impl)); + (struct gl_list_impl *) malloc (sizeof (struct gl_list_impl)); + + if (list == NULL) + return NULL; list->base.vtable = implementation; list->base.equals_fn = equals_fn; list->base.hashcode_fn = hashcode_fn; + list->base.dispose_fn = dispose_fn; list->base.allow_duplicates = allow_duplicates; #if WITH_HASHTABLE { @@ -80,25 +98,44 @@ gl_tree_create (gl_list_implementation_t implementation, if (estimate < 10) estimate = 10; list->table_size = next_prime (estimate); + if (size_overflow_p (xtimes (list->table_size, sizeof (gl_hash_entry_t)))) + goto fail1; list->table = - (gl_hash_entry_t *) xzalloc (list->table_size * sizeof (gl_hash_entry_t)); + (gl_hash_entry_t *) calloc (list->table_size, sizeof (gl_hash_entry_t)); + if (list->table == NULL) + goto fail1; } #endif if (count > 0) { list->root = create_subtree_with_contents (count, contents); + if (list->root == NULL) + goto fail2; list->root->parent = NULL; #if WITH_HASHTABLE /* Now that the tree is built, node_position() works. Now we can - add the nodes to the hash table. */ - add_nodes_to_buckets (list); + add the nodes to the hash table. */ + if (add_nodes_to_buckets (list) < 0) + goto fail3; #endif } else list->root = NULL; return list; + +#if WITH_HASHTABLE + fail3: + free_subtree (list->root); +#endif + fail2: +#if WITH_HASHTABLE + free (list->table); + fail1: +#endif + free (list); + return NULL; } /* Ensure the tree is balanced, after an insertion or deletion operation. @@ -107,7 +144,7 @@ gl_tree_create (gl_list_implementation_t implementation, Rotation operations are performed starting at PARENT (not NODE itself!). */ static void rebalance (gl_list_t list, - gl_list_node_t node, int height_diff, gl_list_node_t parent) + gl_list_node_t node, int height_diff, gl_list_node_t parent) { for (;;) { @@ -123,259 +160,389 @@ rebalance (gl_list_t list, previous_balance = node->balance; /* The balance of NODE is incremented by BALANCE_DIFF: +1 if the right - branch's height has increased by 1 or the left branch's height has - decreased by 1, -1 if the right branch's height has decreased by 1 or - the left branch's height has increased by 1, 0 if no height change. */ + branch's height has increased by 1 or the left branch's height has + decreased by 1, -1 if the right branch's height has decreased by 1 or + the left branch's height has increased by 1, 0 if no height change. */ if (node->left != NULL || node->right != NULL) - balance_diff = (child == node->right ? height_diff : -height_diff); + balance_diff = (child == node->right ? height_diff : -height_diff); else - /* Special case where above formula doesn't work, because the caller - didn't tell whether node's left or right branch shrunk from height 1 - to NULL. */ - balance_diff = - previous_balance; + /* Special case where above formula doesn't work, because the caller + didn't tell whether node's left or right branch shrunk from height 1 + to NULL. */ + balance_diff = - previous_balance; node->balance += balance_diff; if (balance_diff == previous_balance) - { - /* node->balance is outside the range [-1,1]. Must rotate. */ - gl_list_node_t *nodep; - - if (node->parent == NULL) - /* node == list->root */ - nodep = &list->root; - else if (node->parent->left == node) - nodep = &node->parent->left; - else if (node->parent->right == node) - nodep = &node->parent->right; - else - abort (); - - nodeleft = node->left; - noderight = node->right; - - if (balance_diff < 0) - { - /* node->balance = -2. The subtree is heavier on the left side. - Rotate from left to right: - - * - / \ - h+2 h - */ - gl_list_node_t nodeleftleft = nodeleft->left; - gl_list_node_t nodeleftright = nodeleft->right; - if (nodeleft->balance <= 0) - { - /* - * h+2|h+3 - / \ / \ - h+2 h --> / h+1|h+2 - / \ | / \ - h+1 h|h+1 h+1 h|h+1 h - */ - node->left = nodeleftright; - nodeleft->right = node; - - nodeleft->parent = node->parent; - node->parent = nodeleft; - if (nodeleftright != NULL) - nodeleftright->parent = node; - - nodeleft->balance += 1; - node->balance = - nodeleft->balance; - - node->branch_size = - (nodeleftright != NULL ? nodeleftright->branch_size : 0) - + 1 + (noderight != NULL ? noderight->branch_size : 0); - nodeleft->branch_size = - nodeleftleft->branch_size + 1 + node->branch_size; - - *nodep = nodeleft; - height_diff = (height_diff < 0 - ? /* noderight's height had been decremented from - h+1 to h. The subtree's height changes from - h+3 to h+2|h+3. */ - nodeleft->balance - 1 - : /* nodeleft's height had been incremented from - h+1 to h+2. The subtree's height changes from - h+2 to h+2|h+3. */ - nodeleft->balance); - } - else - { - /* - * h+2 - / \ / \ - h+2 h --> h+1 h+1 - / \ / \ / \ - h h+1 h L R h - / \ - L R - - */ - gl_list_node_t L = nodeleft->right = nodeleftright->left; - gl_list_node_t R = node->left = nodeleftright->right; - nodeleftright->left = nodeleft; - nodeleftright->right = node; - - nodeleftright->parent = node->parent; - if (L != NULL) - L->parent = nodeleft; - if (R != NULL) - R->parent = node; - nodeleft->parent = nodeleftright; - node->parent = nodeleftright; - - nodeleft->balance = (nodeleftright->balance > 0 ? -1 : 0); - node->balance = (nodeleftright->balance < 0 ? 1 : 0); - nodeleftright->balance = 0; - - nodeleft->branch_size = - (nodeleft->left != NULL ? nodeleft->left->branch_size : 0) - + 1 + (nodeleft->right != NULL ? nodeleft->right->branch_size : 0); - node->branch_size = - (node->left != NULL ? node->left->branch_size : 0) - + 1 + (node->right != NULL ? node->right->branch_size : 0); - nodeleftright->branch_size = - nodeleft->branch_size + 1 + node->branch_size; - - *nodep = nodeleftright; - height_diff = (height_diff < 0 - ? /* noderight's height had been decremented from - h+1 to h. The subtree's height changes from - h+3 to h+2. */ - -1 - : /* nodeleft's height had been incremented from - h+1 to h+2. The subtree's height changes from - h+2 to h+2. */ - 0); - } - } - else - { - /* node->balance = 2. The subtree is heavier on the right side. - Rotate from right to left: - - * - / \ - h h+2 - */ - gl_list_node_t noderightleft = noderight->left; - gl_list_node_t noderightright = noderight->right; - if (noderight->balance >= 0) - { - /* - * h+2|h+3 - / \ / \ - h h+2 --> h+1|h+2 \ - / \ / \ | - h|h+1 h+1 h h|h+1 h+1 - */ - node->right = noderightleft; - noderight->left = node; - - noderight->parent = node->parent; - node->parent = noderight; - if (noderightleft != NULL) - noderightleft->parent = node; - - noderight->balance -= 1; - node->balance = - noderight->balance; - - node->branch_size = - (nodeleft != NULL ? nodeleft->branch_size : 0) - + 1 + (noderightleft != NULL ? noderightleft->branch_size : 0); - noderight->branch_size = - node->branch_size + 1 + noderightright->branch_size; - - *nodep = noderight; - height_diff = (height_diff < 0 - ? /* nodeleft's height had been decremented from - h+1 to h. The subtree's height changes from - h+3 to h+2|h+3. */ - - noderight->balance - 1 - : /* noderight's height had been incremented from - h+1 to h+2. The subtree's height changes from - h+2 to h+2|h+3. */ - - noderight->balance); - } - else - { - /* - * h+2 - / \ / \ - h h+2 --> h+1 h+1 - / \ / \ / \ - h+1 h h L R h - / \ - L R - - */ - gl_list_node_t L = node->right = noderightleft->left; - gl_list_node_t R = noderight->left = noderightleft->right; - noderightleft->left = node; - noderightleft->right = noderight; - - noderightleft->parent = node->parent; - if (L != NULL) - L->parent = node; - if (R != NULL) - R->parent = noderight; - node->parent = noderightleft; - noderight->parent = noderightleft; - - node->balance = (noderightleft->balance > 0 ? -1 : 0); - noderight->balance = (noderightleft->balance < 0 ? 1 : 0); - noderightleft->balance = 0; - - node->branch_size = - (node->left != NULL ? node->left->branch_size : 0) - + 1 + (node->right != NULL ? node->right->branch_size : 0); - noderight->branch_size = - (noderight->left != NULL ? noderight->left->branch_size : 0) - + 1 + (noderight->right != NULL ? noderight->right->branch_size : 0); - noderightleft->branch_size = - node->branch_size + 1 + noderight->branch_size; - - *nodep = noderightleft; - height_diff = (height_diff < 0 - ? /* nodeleft's height had been decremented from - h+1 to h. The subtree's height changes from - h+3 to h+2. */ - -1 - : /* noderight's height had been incremented from - h+1 to h+2. The subtree's height changes from - h+2 to h+2. */ - 0); - } - } - node = *nodep; - } + { + /* node->balance is outside the range [-1,1]. Must rotate. */ + gl_list_node_t *nodep; + + if (node->parent == NULL) + /* node == list->root */ + nodep = &list->root; + else if (node->parent->left == node) + nodep = &node->parent->left; + else if (node->parent->right == node) + nodep = &node->parent->right; + else + abort (); + + nodeleft = node->left; + noderight = node->right; + + if (balance_diff < 0) + { + /* node->balance = -2. The subtree is heavier on the left side. + Rotate from left to right: + + * + / \ + h+2 h + */ + gl_list_node_t nodeleftleft = nodeleft->left; + gl_list_node_t nodeleftright = nodeleft->right; + if (nodeleft->balance <= 0) + { + /* + * h+2|h+3 + / \ / \ + h+2 h --> / h+1|h+2 + / \ | / \ + h+1 h|h+1 h+1 h|h+1 h + */ + node->left = nodeleftright; + nodeleft->right = node; + + nodeleft->parent = node->parent; + node->parent = nodeleft; + if (nodeleftright != NULL) + nodeleftright->parent = node; + + nodeleft->balance += 1; + node->balance = - nodeleft->balance; + + node->branch_size = + (nodeleftright != NULL ? nodeleftright->branch_size : 0) + + 1 + (noderight != NULL ? noderight->branch_size : 0); + nodeleft->branch_size = + nodeleftleft->branch_size + 1 + node->branch_size; + + *nodep = nodeleft; + height_diff = (height_diff < 0 + ? /* noderight's height had been decremented from + h+1 to h. The subtree's height changes from + h+3 to h+2|h+3. */ + nodeleft->balance - 1 + : /* nodeleft's height had been incremented from + h+1 to h+2. The subtree's height changes from + h+2 to h+2|h+3. */ + nodeleft->balance); + } + else + { + /* + * h+2 + / \ / \ + h+2 h --> h+1 h+1 + / \ / \ / \ + h h+1 h L R h + / \ + L R + + */ + gl_list_node_t L = nodeleft->right = nodeleftright->left; + gl_list_node_t R = node->left = nodeleftright->right; + nodeleftright->left = nodeleft; + nodeleftright->right = node; + + nodeleftright->parent = node->parent; + if (L != NULL) + L->parent = nodeleft; + if (R != NULL) + R->parent = node; + nodeleft->parent = nodeleftright; + node->parent = nodeleftright; + + nodeleft->balance = (nodeleftright->balance > 0 ? -1 : 0); + node->balance = (nodeleftright->balance < 0 ? 1 : 0); + nodeleftright->balance = 0; + + nodeleft->branch_size = + (nodeleft->left != NULL ? nodeleft->left->branch_size : 0) + + 1 + (nodeleft->right != NULL ? nodeleft->right->branch_size : 0); + node->branch_size = + (node->left != NULL ? node->left->branch_size : 0) + + 1 + (node->right != NULL ? node->right->branch_size : 0); + nodeleftright->branch_size = + nodeleft->branch_size + 1 + node->branch_size; + + *nodep = nodeleftright; + height_diff = (height_diff < 0 + ? /* noderight's height had been decremented from + h+1 to h. The subtree's height changes from + h+3 to h+2. */ + -1 + : /* nodeleft's height had been incremented from + h+1 to h+2. The subtree's height changes from + h+2 to h+2. */ + 0); + } + } + else + { + /* node->balance = 2. The subtree is heavier on the right side. + Rotate from right to left: + + * + / \ + h h+2 + */ + gl_list_node_t noderightleft = noderight->left; + gl_list_node_t noderightright = noderight->right; + if (noderight->balance >= 0) + { + /* + * h+2|h+3 + / \ / \ + h h+2 --> h+1|h+2 \ + / \ / \ | + h|h+1 h+1 h h|h+1 h+1 + */ + node->right = noderightleft; + noderight->left = node; + + noderight->parent = node->parent; + node->parent = noderight; + if (noderightleft != NULL) + noderightleft->parent = node; + + noderight->balance -= 1; + node->balance = - noderight->balance; + + node->branch_size = + (nodeleft != NULL ? nodeleft->branch_size : 0) + + 1 + (noderightleft != NULL ? noderightleft->branch_size : 0); + noderight->branch_size = + node->branch_size + 1 + noderightright->branch_size; + + *nodep = noderight; + height_diff = (height_diff < 0 + ? /* nodeleft's height had been decremented from + h+1 to h. The subtree's height changes from + h+3 to h+2|h+3. */ + - noderight->balance - 1 + : /* noderight's height had been incremented from + h+1 to h+2. The subtree's height changes from + h+2 to h+2|h+3. */ + - noderight->balance); + } + else + { + /* + * h+2 + / \ / \ + h h+2 --> h+1 h+1 + / \ / \ / \ + h+1 h h L R h + / \ + L R + + */ + gl_list_node_t L = node->right = noderightleft->left; + gl_list_node_t R = noderight->left = noderightleft->right; + noderightleft->left = node; + noderightleft->right = noderight; + + noderightleft->parent = node->parent; + if (L != NULL) + L->parent = node; + if (R != NULL) + R->parent = noderight; + node->parent = noderightleft; + noderight->parent = noderightleft; + + node->balance = (noderightleft->balance > 0 ? -1 : 0); + noderight->balance = (noderightleft->balance < 0 ? 1 : 0); + noderightleft->balance = 0; + + node->branch_size = + (node->left != NULL ? node->left->branch_size : 0) + + 1 + (node->right != NULL ? node->right->branch_size : 0); + noderight->branch_size = + (noderight->left != NULL ? noderight->left->branch_size : 0) + + 1 + (noderight->right != NULL ? noderight->right->branch_size : 0); + noderightleft->branch_size = + node->branch_size + 1 + noderight->branch_size; + + *nodep = noderightleft; + height_diff = (height_diff < 0 + ? /* nodeleft's height had been decremented from + h+1 to h. The subtree's height changes from + h+3 to h+2. */ + -1 + : /* noderight's height had been incremented from + h+1 to h+2. The subtree's height changes from + h+2 to h+2. */ + 0); + } + } + node = *nodep; + } else - { - /* No rotation needed. Only propagation of the height change to the - next higher level. */ - if (height_diff < 0) - height_diff = (previous_balance == 0 ? 0 : -1); - else - height_diff = (node->balance == 0 ? 0 : 1); - } + { + /* No rotation needed. Only propagation of the height change to the + next higher level. */ + if (height_diff < 0) + height_diff = (previous_balance == 0 ? 0 : -1); + else + height_diff = (node->balance == 0 ? 0 : 1); + } if (height_diff == 0) - break; + break; parent = node->parent; if (parent == NULL) - break; + break; + } +} + +static void +gl_tree_remove_node_from_tree (gl_list_t list, gl_list_node_t node) +{ + gl_list_node_t parent = node->parent; + + if (node->left == NULL) + { + /* Replace node with node->right. */ + gl_list_node_t child = node->right; + + if (child != NULL) + child->parent = parent; + if (parent == NULL) + list->root = child; + else + { + if (parent->left == node) + parent->left = child; + else /* parent->right == node */ + parent->right = child; + + /* Update branch_size fields of the parent nodes. */ + { + gl_list_node_t p; + + for (p = parent; p != NULL; p = p->parent) + p->branch_size--; + } + + rebalance (list, child, -1, parent); + } + } + else if (node->right == NULL) + { + /* It is not absolutely necessary to treat this case. But the more + general case below is more complicated, hence slower. */ + /* Replace node with node->left. */ + gl_list_node_t child = node->left; + + child->parent = parent; + if (parent == NULL) + list->root = child; + else + { + if (parent->left == node) + parent->left = child; + else /* parent->right == node */ + parent->right = child; + + /* Update branch_size fields of the parent nodes. */ + { + gl_list_node_t p; + + for (p = parent; p != NULL; p = p->parent) + p->branch_size--; + } + + rebalance (list, child, -1, parent); + } + } + else + { + /* Replace node with the rightmost element of the node->left subtree. */ + gl_list_node_t subst; + gl_list_node_t subst_parent; + gl_list_node_t child; + + for (subst = node->left; subst->right != NULL; ) + subst = subst->right; + + subst_parent = subst->parent; + + child = subst->left; + + /* The case subst_parent == node is special: If we do nothing special, + we get confusion about node->left, subst->left and child->parent. + subst_parent == node + <==> The 'for' loop above terminated immediately. + <==> subst == subst_parent->left + [otherwise subst == subst_parent->right] + In this case, we would need to first set + child->parent = node; node->left = child; + and later - when we copy subst into node's position - again + child->parent = subst; subst->left = child; + Altogether a no-op. */ + if (subst_parent != node) + { + if (child != NULL) + child->parent = subst_parent; + subst_parent->right = child; + } + + /* Update branch_size fields of the parent nodes. */ + { + gl_list_node_t p; + + for (p = subst_parent; p != NULL; p = p->parent) + p->branch_size--; + } + + /* Copy subst into node's position. + (This is safer than to copy subst's value into node, keep node in + place, and free subst.) */ + if (subst_parent != node) + { + subst->left = node->left; + subst->left->parent = subst; + } + subst->right = node->right; + subst->right->parent = subst; + subst->balance = node->balance; + subst->branch_size = node->branch_size; + subst->parent = parent; + if (parent == NULL) + list->root = subst; + else if (parent->left == node) + parent->left = subst; + else /* parent->right == node */ + parent->right = subst; + + /* Rebalancing starts at child's parent, that is subst_parent - + except when subst_parent == node. In this case, we need to use + its replacement, subst. */ + rebalance (list, child, -1, subst_parent != node ? subst_parent : subst); } } static gl_list_node_t -gl_tree_add_first (gl_list_t list, const void *elt) +gl_tree_nx_add_first (gl_list_t list, const void *elt) { /* Create new node. */ gl_list_node_t new_node = - (struct gl_list_node_impl *) xmalloc (sizeof (struct gl_list_node_impl)); + (struct gl_list_node_impl *) malloc (sizeof (struct gl_list_node_impl)); + + if (new_node == NULL) + return NULL; new_node->left = NULL; new_node->right = NULL; @@ -400,7 +567,7 @@ gl_tree_add_first (gl_list_t list, const void *elt) gl_list_node_t node; for (node = list->root; node->left != NULL; ) - node = node->left; + node = node->left; node->left = new_node; new_node->parent = node; @@ -408,22 +575,27 @@ gl_tree_add_first (gl_list_t list, const void *elt) /* Update branch_size fields of the parent nodes. */ { - gl_list_node_t p; + gl_list_node_t p; - for (p = node; p != NULL; p = p->parent) - p->branch_size++; + for (p = node; p != NULL; p = p->parent) + p->branch_size++; } /* Rebalance. */ if (node->right == NULL && node->parent != NULL) - rebalance (list, node, 1, node->parent); + rebalance (list, node, 1, node->parent); } #if WITH_HASHTABLE /* Add node to the hash table. Note that this is only possible _after_ the node has been added to the tree structure, because add_to_bucket() uses node_position(). */ - add_to_bucket (list, new_node); + if (add_to_bucket (list, new_node) < 0) + { + gl_tree_remove_node_from_tree (list, new_node); + free (new_node); + return NULL; + } hash_resize_after_add (list); #endif @@ -431,11 +603,14 @@ gl_tree_add_first (gl_list_t list, const void *elt) } static gl_list_node_t -gl_tree_add_last (gl_list_t list, const void *elt) +gl_tree_nx_add_last (gl_list_t list, const void *elt) { /* Create new node. */ gl_list_node_t new_node = - (struct gl_list_node_impl *) xmalloc (sizeof (struct gl_list_node_impl)); + (struct gl_list_node_impl *) malloc (sizeof (struct gl_list_node_impl)); + + if (new_node == NULL) + return NULL; new_node->left = NULL; new_node->right = NULL; @@ -460,7 +635,7 @@ gl_tree_add_last (gl_list_t list, const void *elt) gl_list_node_t node; for (node = list->root; node->right != NULL; ) - node = node->right; + node = node->right; node->right = new_node; new_node->parent = node; @@ -468,22 +643,27 @@ gl_tree_add_last (gl_list_t list, const void *elt) /* Update branch_size fields of the parent nodes. */ { - gl_list_node_t p; + gl_list_node_t p; - for (p = node; p != NULL; p = p->parent) - p->branch_size++; + for (p = node; p != NULL; p = p->parent) + p->branch_size++; } /* Rebalance. */ if (node->left == NULL && node->parent != NULL) - rebalance (list, node, 1, node->parent); + rebalance (list, node, 1, node->parent); } #if WITH_HASHTABLE /* Add node to the hash table. Note that this is only possible _after_ the node has been added to the tree structure, because add_to_bucket() uses node_position(). */ - add_to_bucket (list, new_node); + if (add_to_bucket (list, new_node) < 0) + { + gl_tree_remove_node_from_tree (list, new_node); + free (new_node); + return NULL; + } hash_resize_after_add (list); #endif @@ -491,13 +671,17 @@ gl_tree_add_last (gl_list_t list, const void *elt) } static gl_list_node_t -gl_tree_add_before (gl_list_t list, gl_list_node_t node, const void *elt) +gl_tree_nx_add_before (gl_list_t list, gl_list_node_t node, const void *elt) { /* Create new node. */ - gl_list_node_t new_node = - (struct gl_list_node_impl *) xmalloc (sizeof (struct gl_list_node_impl)); + gl_list_node_t new_node; bool height_inc; + new_node = + (struct gl_list_node_impl *) malloc (sizeof (struct gl_list_node_impl)); + if (new_node == NULL) + return NULL; + new_node->left = NULL; new_node->right = NULL; new_node->balance = 0; @@ -520,7 +704,7 @@ gl_tree_add_before (gl_list_t list, gl_list_node_t node, const void *elt) else { for (node = node->left; node->right != NULL; ) - node = node->right; + node = node->right; node->right = new_node; node->balance++; height_inc = (node->left == NULL); @@ -543,7 +727,12 @@ gl_tree_add_before (gl_list_t list, gl_list_node_t node, const void *elt) /* Add node to the hash table. Note that this is only possible _after_ the node has been added to the tree structure, because add_to_bucket() uses node_position(). */ - add_to_bucket (list, new_node); + if (add_to_bucket (list, new_node) < 0) + { + gl_tree_remove_node_from_tree (list, new_node); + free (new_node); + return NULL; + } hash_resize_after_add (list); #endif @@ -551,13 +740,17 @@ gl_tree_add_before (gl_list_t list, gl_list_node_t node, const void *elt) } static gl_list_node_t -gl_tree_add_after (gl_list_t list, gl_list_node_t node, const void *elt) +gl_tree_nx_add_after (gl_list_t list, gl_list_node_t node, const void *elt) { /* Create new node. */ - gl_list_node_t new_node = - (struct gl_list_node_impl *) xmalloc (sizeof (struct gl_list_node_impl)); + gl_list_node_t new_node; bool height_inc; + new_node = + (struct gl_list_node_impl *) malloc (sizeof (struct gl_list_node_impl)); + if (new_node == NULL) + return NULL; + new_node->left = NULL; new_node->right = NULL; new_node->balance = 0; @@ -580,7 +773,7 @@ gl_tree_add_after (gl_list_t list, gl_list_node_t node, const void *elt) else { for (node = node->right; node->left != NULL; ) - node = node->left; + node = node->left; node->left = new_node; node->balance--; height_inc = (node->right == NULL); @@ -603,148 +796,14 @@ gl_tree_add_after (gl_list_t list, gl_list_node_t node, const void *elt) /* Add node to the hash table. Note that this is only possible _after_ the node has been added to the tree structure, because add_to_bucket() uses node_position(). */ - add_to_bucket (list, new_node); + if (add_to_bucket (list, new_node) < 0) + { + gl_tree_remove_node_from_tree (list, new_node); + free (new_node); + return NULL; + } hash_resize_after_add (list); #endif return new_node; } - -static bool -gl_tree_remove_node (gl_list_t list, gl_list_node_t node) -{ - gl_list_node_t parent; - -#if WITH_HASHTABLE - /* Remove node from the hash table. - Note that this is only possible _before_ the node is removed from the - tree structure, because remove_from_bucket() uses node_position(). */ - remove_from_bucket (list, node); -#endif - - parent = node->parent; - - if (node->left == NULL) - { - /* Replace node with node->right. */ - gl_list_node_t child = node->right; - - if (child != NULL) - child->parent = parent; - if (parent == NULL) - list->root = child; - else - { - if (parent->left == node) - parent->left = child; - else /* parent->right == node */ - parent->right = child; - - /* Update branch_size fields of the parent nodes. */ - { - gl_list_node_t p; - - for (p = parent; p != NULL; p = p->parent) - p->branch_size--; - } - - rebalance (list, child, -1, parent); - } - } - else if (node->right == NULL) - { - /* It is not absolutely necessary to treat this case. But the more - general case below is more complicated, hence slower. */ - /* Replace node with node->left. */ - gl_list_node_t child = node->left; - - child->parent = parent; - if (parent == NULL) - list->root = child; - else - { - if (parent->left == node) - parent->left = child; - else /* parent->right == node */ - parent->right = child; - - /* Update branch_size fields of the parent nodes. */ - { - gl_list_node_t p; - - for (p = parent; p != NULL; p = p->parent) - p->branch_size--; - } - - rebalance (list, child, -1, parent); - } - } - else - { - /* Replace node with the rightmost element of the node->left subtree. */ - gl_list_node_t subst; - gl_list_node_t subst_parent; - gl_list_node_t child; - - for (subst = node->left; subst->right != NULL; ) - subst = subst->right; - - subst_parent = subst->parent; - - child = subst->left; - - /* The case subst_parent == node is special: If we do nothing special, - we get confusion about node->left, subst->left and child->parent. - subst_parent == node - <==> The 'for' loop above terminated immediately. - <==> subst == subst_parent->left - [otherwise subst == subst_parent->right] - In this case, we would need to first set - child->parent = node; node->left = child; - and later - when we copy subst into node's position - again - child->parent = subst; subst->left = child; - Altogether a no-op. */ - if (subst_parent != node) - { - if (child != NULL) - child->parent = subst_parent; - subst_parent->right = child; - } - - /* Update branch_size fields of the parent nodes. */ - { - gl_list_node_t p; - - for (p = subst_parent; p != NULL; p = p->parent) - p->branch_size--; - } - - /* Copy subst into node's position. - (This is safer than to copy subst's value into node, keep node in - place, and free subst.) */ - if (subst_parent != node) - { - subst->left = node->left; - subst->left->parent = subst; - } - subst->right = node->right; - subst->right->parent = subst; - subst->balance = node->balance; - subst->branch_size = node->branch_size; - subst->parent = parent; - if (parent == NULL) - list->root = subst; - else if (parent->left == node) - parent->left = subst; - else /* parent->right == node */ - parent->right = subst; - - /* Rebalancing starts at child's parent, that is subst_parent - - except when subst_parent == node. In this case, we need to use - its replacement, subst. */ - rebalance (list, child, -1, subst_parent != node ? subst_parent : subst); - } - - free (node); - return true; -}