/* Sequential list data type implemented by a binary tree.
- Copyright (C) 2006-2007 Free Software Foundation, Inc.
+ Copyright (C) 2006-2007, 2009-2014 Free Software Foundation, Inc.
Written by Bruno Haible <bruno@clisp.org>, 2006.
This program is free software: you can redistribute it and/or modify
/* Create a subtree for count >= 1 elements.
Its black-height bh is passed as argument, with
2^bh - 1 <= count <= 2^(bh+1) - 1. bh == 0 implies count == 1.
- 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 (unsigned int bh,
size_t count, const void **contents)
size_t half1 = (count - 1) / 2;
size_t half2 = count / 2;
/* Note: half1 + half2 = count - 1. */
- gl_list_node_t node = XMALLOC (struct gl_list_node_impl);
+ gl_list_node_t node =
+ (struct gl_list_node_impl *) malloc (sizeof (struct gl_list_node_impl));
+ if (node == NULL)
+ return NULL;
if (half1 > 0)
{
2^(bh-1) - 1 <= half1 <= 2^bh - 1. */
node->left =
create_subtree_with_contents (bh - 1, half1, contents);
+ if (node->left == NULL)
+ goto fail1;
node->left->parent = node;
}
else
2^(bh-1) - 1 <= half2 <= 2^bh - 1. */
node->right =
create_subtree_with_contents (bh - 1, half2, contents + half1 + 1);
+ if (node->right == NULL)
+ goto fail2;
node->right->parent = node;
}
else
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,
- gl_listelement_dispose_fn dispose_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 = XMALLOC (struct gl_list_impl);
+ struct gl_list_impl *list =
+ (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;
if (estimate < 10)
estimate = 10;
list->table_size = next_prime (estimate);
- list->table = XCALLOC (list->table_size, gl_hash_entry_t);
+ if (size_overflow_p (xtimes (list->table_size, sizeof (gl_hash_entry_t))))
+ goto fail1;
+ list->table =
+ (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 (bh, 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);
+ 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;
}
/* Rotate left a subtree.
Change the tree structure, update the branch sizes.
The caller must update the colors and register D as child of its parent. */
-static inline gl_list_node_t
+static gl_list_node_t
rotate_left (gl_list_node_t b_node, gl_list_node_t d_node)
{
gl_list_node_t a_node = b_node->left;
Change the tree structure, update the branch sizes.
The caller must update the colors and register B as child of its parent. */
-static inline gl_list_node_t
+static gl_list_node_t
rotate_right (gl_list_node_t b_node, gl_list_node_t d_node)
{
gl_list_node_t a_node = b_node->left;
}
}
+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;
+ /* Since node->left == NULL, child must be RED and of height 1,
+ hence node must have been BLACK. Recolor the child. */
+ child->color = BLACK;
+ }
+ 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--;
+ }
+
+ if (child == NULL && node->color == BLACK)
+ rebalance_after_remove (list, child, 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;
+ /* Since node->right == NULL, child must be RED and of height 1,
+ hence node must have been BLACK. Recolor the child. */
+ child->color = BLACK;
+ 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--;
+ }
+ }
+ }
+ 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;
+ color_t removed_color;
+
+ for (subst = node->left; subst->right != NULL; )
+ subst = subst->right;
+
+ subst_parent = subst->parent;
+
+ child = subst->left;
+
+ removed_color = subst->color;
+
+ /* 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->color = node->color;
+ 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;
+
+ if (removed_color == BLACK)
+ {
+ if (child != NULL && child->color == RED)
+ /* Recolor the child. */
+ child->color = BLACK;
+ else
+ /* 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_after_remove (list, child,
+ 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 = XMALLOC (struct gl_list_node_impl);
+ gl_list_node_t 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;
/* 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
}
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 = XMALLOC (struct gl_list_node_impl);
+ gl_list_node_t 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;
/* 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
}
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 = XMALLOC (struct gl_list_node_impl);
+ gl_list_node_t 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;
/* 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
}
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 = XMALLOC (struct gl_list_node_impl);
+ gl_list_node_t 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;
/* 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;
- /* Since node->left == NULL, child must be RED and of height 1,
- hence node must have been BLACK. Recolor the child. */
- child->color = BLACK;
- }
- 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--;
- }
-
- if (child == NULL && node->color == BLACK)
- rebalance_after_remove (list, child, 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;
- /* Since node->right == NULL, child must be RED and of height 1,
- hence node must have been BLACK. Recolor the child. */
- child->color = BLACK;
- 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--;
- }
- }
- }
- 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;
- color_t removed_color;
-
- for (subst = node->left; subst->right != NULL; )
- subst = subst->right;
-
- subst_parent = subst->parent;
-
- child = subst->left;
-
- removed_color = subst->color;
-
- /* 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->color = node->color;
- 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;
-
- if (removed_color == BLACK)
- {
- if (child != NULL && child->color == RED)
- /* Recolor the child. */
- child->color = BLACK;
- else
- /* 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_after_remove (list, child,
- subst_parent != node ? subst_parent : subst);
- }
- }
-
- if (list->base.dispose_fn != NULL)
- list->base.dispose_fn (node->value);
- free (node);
- return true;
-}
projects / gnulib.git / blobdiff