diff options
58 files changed, 2354 insertions, 980 deletions
@@ -1,5 +1,231 @@ 2009-12-13 Bruno Haible <bruno@clisp.org> + Move the malloc checking from module 'list' to new module 'xlist'. + * modules/xlist: New file. + * lib/gl_xlist.h: New file. + * lib/gl_xlist.c: New file. + * lib/gl_list.h (gl_list_create_empty, gl_list_create, + gl_list_node_set_value, gl_list_set_at, gl_list_add_first, + gl_list_add_last, gl_list_add_before, gl_list_add_after, + gl_list_nx_add_at, gl_sortedlist_add): Disable declarations. + (gl_list_nx_create_empty, gl_list_nx_create, gl_list_node_nx_set_value, + gl_list_nx_set_at, gl_list_nx_add_first, gl_list_nx_add_last, + gl_list_nx_add_before, gl_list_nx_add_after, gl_list_nx_add_at, + gl_sortedlist_nx_add): New declarations. + (struct gl_list_implementation): Rename and change methods accordingly. + (gl_list_nx_create_empty): Renamed from gl_list_create_empty. + (gl_list_nx_create): Renamed from gl_list_create. + (gl_list_node_nx_set_value): Renamed from gl_list_node_set_value. + (gl_list_nx_set_at): Renamed from gl_list_set_at. + (gl_list_nx_add_first): Renamed from gl_list_add_first. + (gl_list_nx_add_last): Renamed from gl_list_add_last. + (gl_list_nx_add_before): Renamed from gl_list_add_before. + (gl_list_nx_add_after): Renamed from gl_list_add_after. + (gl_list_nx_add_at): Renamed from gl_list_add_at. + (gl_sortedlist_nx_add): Renamed from gl_sortedlist_add. + * lib/gl_list.c (gl_list_nx_create_empty): Renamed from + gl_list_create_empty. + (gl_list_nx_create): Renamed from gl_list_create. + (gl_list_node_nx_set_value): Renamed from gl_list_node_set_value. + (gl_list_nx_set_at): Renamed from gl_list_set_at. + (gl_list_nx_add_first): Renamed from gl_list_add_first. + (gl_list_nx_add_last): Renamed from gl_list_add_last. + (gl_list_nx_add_before): Renamed from gl_list_add_before. + (gl_list_nx_add_after): Renamed from gl_list_add_after. + (gl_list_nx_add_at): Renamed from gl_list_add_at. + (gl_sortedlist_nx_add): Renamed from gl_sortedlist_add. + * lib/gl_array_list.c: Don't include xalloc.h. + (gl_array_nx_create_empty): Renamed from gl_array_create_empty. Return + NULL upon out-of-memory. + (gl_array_nx_create): Renamed from gl_array_create. Return NULL upon + out-of-memory. + (gl_array_node_nx_set_value): Renamed from gl_array_node_set_value. + Change return type to 'int'. + (gl_array_nx_set_at): Renamed from gl_array_set_at. + (grow): Change return type to 'int'. Return -1 upon out-of-memory. + (gl_array_nx_add_first): Renamed from gl_array_add_first. Return NULL + upon out-of-memory. + (gl_array_nx_add_last): Renamed from gl_array_add_last. Return NULL + upon out-of-memory. + (gl_array_nx_add_before): Renamed from gl_array_add_before. Return NULL + upon out-of-memory. + (gl_array_nx_add_after): Renamed from gl_array_add_after. Return NULL + upon out-of-memory. + (gl_array_nx_add_at): Renamed from gl_array_add_at. Return NULL upon + out-of-memory. + (gl_array_sortedlist_nx_add): Renamed from gl_array_sortedlist_add. + Update. + (gl_array_list_implementation): Update. + * lib/gl_carray_list.c: Don't include xalloc.h. + (gl_carray_nx_create_empty): Renamed from gl_carray_create_empty. + Return NULL upon out-of-memory. + (gl_carray_nx_create): Renamed from gl_carray_create. Return NULL upon + out-of-memory. + (gl_carray_node_nx_set_value): Renamed from gl_carray_node_set_value. + Change return type to 'int'. + (gl_carray_nx_set_at): Renamed from gl_carray_set_at. + (grow): Change return type to 'int'. Return -1 upon out-of-memory. + (gl_carray_nx_add_first): Renamed from gl_carray_add_first. Return NULL + upon out-of-memory. + (gl_carray_nx_add_last): Renamed from gl_carray_add_last. Return NULL + upon out-of-memory. + (gl_carray_nx_add_at): Renamed from gl_carray_add_at. Return NULL upon + out-of-memory. + (gl_carray_nx_add_before): Renamed from gl_carray_add_before. Update. + (gl_carray_nx_add_after): Renamed from gl_carray_add_after. Update. + (gl_carray_sortedlist_nx_add): Renamed from gl_carray_sortedlist_add. + Update. + (gl_carray_list_implementation): Update. + * lib/gl_anyhash_list2.h (hash_resize): Do nothing upon out-of-memory. + * lib/gl_anylinked_list2.h (gl_linked_nx_create_empty): Renamed from + gl_linked_create_empty. Return NULL upon out-of-memory. + (gl_linked_nx_create): Renamed from gl_linked_create. Return NULL upon + out-of-memory. + (gl_linked_node_nx_set_value): Renamed from gl_linked_node_set_value. + Change return type to 'int'. Return -1 upon out-of-memory. + (gl_linked_nx_set_at): Renamed from gl_linked_set_at. Return NULL upon + out-of-memory. + (gl_linked_nx_add_first): Renamed from gl_linked_add_first. Return NULL + upon out-of-memory. + (gl_linked_nx_add_last): Renamed from gl_linked_add_last. Return NULL + upon out-of-memory. + (gl_linked_nx_add_before): Renamed from gl_linked_add_before. Return + NULL upon out-of-memory. + (gl_linked_nx_add_after): Renamed from gl_linked_add_after. Return NULL + upon out-of-memory. + (gl_linked_nx_add_at): Renamed from gl_linked_add_at. Return NULL upon + out-of-memory. + (gl_linked_sortedlist_nx_add): Renamed from gl_linked_sortedlist_add. + Update. + * lib/gl_linked_list.c: Don't include xalloc.h. + (gl_linked_list_implementation): Update. + * lib/gl_linkedhash_list.c: Don't include xalloc.h. + (add_to_bucket): Change return type to 'int'. + (gl_linkedhash_list_implementation): Update. + * lib/gl_anytree_list1.h (free_subtree): New function. + * lib/gl_anytree_list2.h (gl_tree_nx_create_empty): Renamed from + gl_tree_create_empty. Return NULL upon out-of-memory. + (gl_tree_node_nx_set_value): Renamed from gl_tree_node_set_value. + Change return type to 'int'. Return -1 upon out-of-memory. + (gl_tree_nx_set_at): Renamed from gl_tree_set_at. Return NULL upon + out-of-memory. + (gl_tree_nx_add_at): Renamed from gl_tree_add_at. Update. + (gl_tree_remove_node): New function, moved here from + lib/gl_anyavltree_list2.h and lib/gl_anyrbtree_list2.h. + (gl_tree_sortedlist_nx_add): Renamed from gl_tree_sortedlist_add. + Update. + * lib/gl_anyavltree_list2.h (create_subtree_with_contents): Use + malloc, not xmalloc. Return NULL upon out-of-memory. + (gl_tree_nx_create): Renamed from gl_tree_create. Return NULL upon + out-of-memory. + (gl_tree_remove_node_from_tree): New function, extracted from + gl_tree_remove_node. + (gl_tree_nx_add_first): Renamed from gl_tree_add_first. Return NULL + upon out-of-memory. + (gl_tree_nx_add_last): Renamed from gl_tree_add_last. Return NULL upon + out-of-memory. + (gl_tree_nx_add_before): Renamed from gl_tree_add_before. Return NULL + upon out-of-memory. + (gl_tree_nx_add_after): Renamed from gl_tree_add_after. Return NULL + upon out-of-memory. + (gl_tree_remove_node): Remove function. Moved to gl_anytree_list2.h. + * lib/gl_anyrbtree_list2.h (create_subtree_with_contents): Use malloc, + not xmalloc. Return NULL upon out-of-memory. + (gl_tree_nx_create): Renamed from gl_tree_create. Return NULL upon + out-of-memory. + (gl_tree_remove_node_from_tree): New function, extracted from + gl_tree_remove_node. + (gl_tree_nx_add_first): Renamed from gl_tree_add_first. Return NULL + upon out-of-memory. + (gl_tree_nx_add_last): Renamed from gl_tree_add_last. Return NULL upon + out-of-memory. + (gl_tree_nx_add_before): Renamed from gl_tree_add_before. Return NULL + upon out-of-memory. + (gl_tree_nx_add_after): Renamed from gl_tree_add_after. Return NULL + upon out-of-memory. + (gl_tree_remove_node): Remove function. Moved to gl_anytree_list2.h. + * lib/gl_avltree_list.c: Don't include xalloc.h. Include + gl_anytree_list1.h before gl_anyavltree_list2.h. + (gl_avltree_list_implementation): Update. + * lib/gl_rbtree_list.c: Don't include xalloc.h. Include + gl_anytree_list1.h before gl_anyavltree_list2.h. + (gl_rbtree_list_implementation): Update. + * lib/gl_anytreehash_list1.h (add_to_bucket, add_nodes_to_buckets): + Change return type to 'int'. Return -1 upon out-of-memory. Use + __builtin_expect. + * lib/gl_avltreehash_list.c: Don't include xalloc.h. + (gl_avltreehash_list_implementation): Update. + * lib/gl_rbtreehash_list.c: Don't include xalloc.h. + (gl_rbtreehash_list_implementation): Update. + * modules/array-list (Depends-on): Remove xalloc. + * modules/carray-list (Depends-on): Likewise. + * modules/linked-list (Depends-on): Likewise. + * modules/linkedhash-list (Depends-on): Likewise. + * modules/avltree-list (Depends-on): Likewise. + * modules/rbtree-list (Depends-on): Likewise. + * modules/avltreehash-list (Depends-on): Likewise. + * modules/rbtreehash-list (Depends-on): Likewise. + + * modules/xsublist: New file. + * lib/gl_xsublist.h: New file. + * lib/gl_xsublist.c: New file. + * lib/gl_sublist.h (gl_sublist_create): Disable declaration. + (gl_sublist_nx_create): New declaration. + * lib/gl_sublist.c: Don't include xalloc.h. + (gl_sublist_nx_create_empty): Renamed from gl_sublist_create_empty. + (gl_sublist_nx_create_fill): Renamed from gl_sublist_create_fill. + (gl_sublist_node_nx_set_value): Renamed from gl_sublist_node_set_value. + Change return type to 'int'. Return -1 upon out-of-memory. + (gl_sublist_nx_set_at): Renamed from gl_sublist_set_at. Return NULL + upon out-of-memory. + (gl_sublist_nx_add_first): Renamed from gl_sublist_add_first. Return + NULL upon out-of-memory. + (gl_sublist_nx_add_last): Renamed from gl_sublist_add_last. Return NULL + upon out-of-memory. + (gl_sublist_nx_add_before): Renamed from gl_sublist_add_before. Return + NULL upon out-of-memory. + (gl_sublist_nx_add_after): Renamed from gl_sublist_add_after. Return + NULL upon out-of-memory. + (gl_sublist_nx_add_at): Renamed from gl_sublist_add_at. Return NULL + upon out-of-memory. + (gl_sublist_sortedlist_nx_add): Renamed from gl_sublist_sortedlist_add. + (gl_sublist_list_implementation): Update. + (gl_sublist_nx_create): Renamed from gl_sublist_create. Return NULL + upon out-of-memory. + * modules/sublist (Depends-on): Remove xalloc. + + * tests/test-array_list.c: Use gl_list_nx_* functions where possible. + * tests/test-carray_list.c: Likewise. + * tests/test-linked_list.c: Likewise. + * tests/test-linkedhash_list.c: Likewise. + * tests/test-avltree_list.c: Likewise. + * tests/test-rbtree_list.c: Likewise. + * tests/test-avltreehash_list.c: Likewise. + * tests/test-rbtreehash_list.c: Likewise. + * modules/array-list-tests (Makefile.am): Don't link with @LIBINTL@. + * modules/carray-list-tests (Makefile.am): Likewise. + * modules/linked-list-tests (Makefile.am): Likewise. + * modules/linkedhash-list-tests (Makefile.am): Likewise. + * modules/avltree-list-tests (Makefile.am): Likewise. + * modules/rbtree-list-tests (Makefile.am): Likewise. + * modules/avltreehash-list-tests (Makefile.am): Likewise. + * modules/rbtreehash-list-tests (Makefile.am): Likewise. + + * NEWS: Mention the changes. + + * lib/clean-temp.c: Include gl_xlist.h. + * modules/clean-temp (Depends-on): Add xlist. + + * lib/git-merge-changelog.c: Include gl_xlist.h instead of gl_list.h. + * modules/git-merge-changelog (Depends-on): Add xlist. Remove list. + + * tests/test-array_oset.c: Include gl_xlist.h. + * modules/array-oset-tests (Depends-on): Add xlist. + + Reported by José E. Marchesi <jemarch@gnu.org>. + +2009-12-13 Bruno Haible <bruno@clisp.org> + Move the malloc checking from module 'oset' to new module 'xoset'. * modules/xoset: New file. * lib/gl_xoset.h: New file. @@ -6,6 +6,16 @@ User visible incompatible changes Date Modules Changes +2009-12-13 sublist The module does not define functions any more that + call xalloc_die() in out-of-memory situations. Use + module 'xsublist' and include file "gl_xsublist.h" + instead. + +2009-12-13 list The module does not define functions any more that + call xalloc_die() in out-of-memory situations. + Use module 'xlist' and include file "gl_xlist.h" + instead. + 2009-12-13 oset The module does not define functions any more that call xalloc_die() in out-of-memory situations. Use module 'xoset' and include file "gl_xoset.h" diff --git a/lib/clean-temp.c b/lib/clean-temp.c index 99c81d1465..6199128069 100644 --- a/lib/clean-temp.c +++ b/lib/clean-temp.c @@ -1,5 +1,5 @@ /* Temporary directories and temporary files with automatic cleanup. - Copyright (C) 2001, 2003, 2006-2007 Free Software Foundation, Inc. + Copyright (C) 2001, 2003, 2006-2007, 2009 Free Software Foundation, Inc. Written by Bruno Haible <bruno@clisp.org>, 2006. This program is free software: you can redistribute it and/or modify @@ -40,6 +40,7 @@ #include "tmpdir.h" #include "xalloc.h" #include "xmalloca.h" +#include "gl_xlist.h" #include "gl_linkedhash_list.h" #include "gettext.h" #if GNULIB_FWRITEERROR diff --git a/lib/git-merge-changelog.c b/lib/git-merge-changelog.c index 2affd9f1dc..b9ab42947b 100644 --- a/lib/git-merge-changelog.c +++ b/lib/git-merge-changelog.c @@ -130,7 +130,7 @@ #include "progname.h" #include "error.h" #include "read-file.h" -#include "gl_list.h" +#include "gl_xlist.h" #include "gl_array_list.h" #include "gl_linkedhash_list.h" #include "gl_rbtreehash_list.h" diff --git a/lib/gl_anyavltree_list2.h b/lib/gl_anyavltree_list2.h index 1ae6df84b3..38e339281f 100644 --- a/lib/gl_anyavltree_list2.h +++ b/lib/gl_anyavltree_list2.h @@ -1,5 +1,5 @@ /* Sequential list data type implemented by a binary tree. - Copyright (C) 2006-2007 Free Software Foundation, Inc. + Copyright (C) 2006-2007, 2009 Free Software Foundation, Inc. Written by Bruno Haible <bruno@clisp.org>, 2006. This program is free software: you can redistribute it and/or modify @@ -20,18 +20,24 @@ /* -------------------------- 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) { 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) { node->left = create_subtree_with_contents (half1, contents); + if (node->left == NULL) + goto fail1; node->left->parent = node; } else @@ -42,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 @@ -56,17 +64,28 @@ 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, - 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; @@ -79,24 +98,44 @@ gl_tree_create (gl_list_implementation_t implementation, 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 (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; } /* Ensure the tree is balanced, after an insertion or deletion operation. @@ -368,11 +407,142 @@ rebalance (gl_list_t list, } } +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 = 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; @@ -420,7 +590,12 @@ gl_tree_add_first (gl_list_t list, 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 @@ -428,10 +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 = 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; @@ -479,7 +658,12 @@ gl_tree_add_last (gl_list_t list, 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 @@ -487,12 +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 = XMALLOC (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; @@ -538,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 @@ -546,12 +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 = XMALLOC (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; @@ -597,150 +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); - } - - if (list->base.dispose_fn != NULL) - list->base.dispose_fn (node->value); - free (node); - return true; -} diff --git a/lib/gl_anyhash_list2.h b/lib/gl_anyhash_list2.h index 03640f4cbc..db764bc511 100644 --- a/lib/gl_anyhash_list2.h +++ b/lib/gl_anyhash_list2.h @@ -1,5 +1,5 @@ /* Sequential list data type implemented by a hash table with another list. - Copyright (C) 2006 Free Software Foundation, Inc. + Copyright (C) 2006, 2009 Free Software Foundation, Inc. Written by Bruno Haible <bruno@clisp.org>, 2006. This program is free software: you can redistribute it and/or modify @@ -99,9 +99,16 @@ hash_resize (gl_list_t list, size_t estimate) { gl_hash_entry_t *old_table = list->table; /* Allocate the new table. */ - gl_hash_entry_t *new_table = XCALLOC (new_size, gl_hash_entry_t); + gl_hash_entry_t *new_table; size_t i; + if (size_overflow_p (xtimes (new_size, sizeof (gl_hash_entry_t)))) + goto fail; + new_table = + (gl_hash_entry_t *) calloc (new_size, sizeof (gl_hash_entry_t)); + if (new_table == NULL) + goto fail; + /* Iterate through the entries of the old table. */ for (i = list->table_size; i > 0; ) { @@ -123,4 +130,9 @@ hash_resize (gl_list_t list, size_t estimate) list->table_size = new_size; free (old_table); } + return; + + fail: + /* Just continue without resizing the table. */ + return; } diff --git a/lib/gl_anylinked_list2.h b/lib/gl_anylinked_list2.h index 7c7b7e37c4..792abf0001 100644 --- a/lib/gl_anylinked_list2.h +++ b/lib/gl_anylinked_list2.h @@ -1,5 +1,5 @@ /* Sequential list data type implemented by a linked list. - Copyright (C) 2006-2008 Free Software Foundation, Inc. + Copyright (C) 2006-2009 Free Software Foundation, Inc. Written by Bruno Haible <bruno@clisp.org>, 2006. This program is free software: you can redistribute it and/or modify @@ -37,13 +37,17 @@ /* -------------------------- gl_list_t Data Type -------------------------- */ static gl_list_t -gl_linked_create_empty (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) +gl_linked_nx_create_empty (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) { - 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; @@ -52,26 +56,39 @@ gl_linked_create_empty (gl_list_implementation_t implementation, list->base.allow_duplicates = allow_duplicates; #if WITH_HASHTABLE list->table_size = 11; - list->table = XCALLOC (list->table_size, gl_hash_entry_t); + list->table = + (gl_hash_entry_t *) calloc (list->table_size, sizeof (gl_hash_entry_t)); + if (list->table == NULL) + goto fail; #endif list->root.next = &list->root; list->root.prev = &list->root; list->count = 0; return list; + +#if WITH_HASHTABLE + fail: + free (list); + return NULL; +#endif } static gl_list_t -gl_linked_create (gl_list_implementation_t implementation, +gl_linked_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)); gl_list_node_t tail; + if (list == NULL) + return NULL; + list->base.vtable = implementation; list->base.equals_fn = equals_fn; list->base.hashcode_fn = hashcode_fn; @@ -83,14 +100,23 @@ gl_linked_create (gl_list_implementation_t implementation, 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 list->count = count; tail = &list->root; for (; count > 0; contents++, count--) { - 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) + goto fail2; node->value = *contents; #if WITH_HASHTABLE @@ -100,7 +126,11 @@ gl_linked_create (gl_list_implementation_t implementation, : (size_t)(uintptr_t) node->value); /* Add node to the hash table. */ - add_to_bucket (list, node); + if (add_to_bucket (list, node) < 0) + { + free (node); + goto fail2; + } #endif /* Add node to the list. */ @@ -112,6 +142,25 @@ gl_linked_create (gl_list_implementation_t implementation, list->root.prev = tail; return list; + + fail2: + { + gl_list_node_t node; + + for (node = tail; node != &list->root; ) + { + gl_list_node_t prev = node->prev; + + free (node); + node = prev; + } + } +#if WITH_HASHTABLE + free (list->table); + fail1: +#endif + free (list); + return NULL; } static size_t @@ -126,8 +175,9 @@ gl_linked_node_value (gl_list_t list, gl_list_node_t node) return node->value; } -static void -gl_linked_node_set_value (gl_list_t list, gl_list_node_t node, const void *elt) +static int +gl_linked_node_nx_set_value (gl_list_t list, gl_list_node_t node, + const void *elt) { #if WITH_HASHTABLE if (elt != node->value) @@ -142,7 +192,19 @@ gl_linked_node_set_value (gl_list_t list, gl_list_node_t node, const void *elt) remove_from_bucket (list, node); node->value = elt; node->h.hashcode = new_hashcode; - add_to_bucket (list, node); + if (add_to_bucket (list, node) < 0) + { + /* Out of memory. We removed node from a bucket but cannot add + it to another bucket. In order to avoid inconsistencies, we + must remove node entirely from the list. */ + gl_list_node_t before_removed = node->prev; + gl_list_node_t after_removed = node->next; + ASYNCSAFE(gl_list_node_t) before_removed->next = after_removed; + after_removed->prev = before_removed; + list->count--; + free (node); + return -1; + } } else node->value = elt; @@ -150,6 +212,7 @@ gl_linked_node_set_value (gl_list_t list, gl_list_node_t node, const void *elt) #else node->value = elt; #endif + return 0; } static gl_list_node_t @@ -191,7 +254,7 @@ gl_linked_get_at (gl_list_t list, size_t position) } static gl_list_node_t -gl_linked_set_at (gl_list_t list, size_t position, const void *elt) +gl_linked_nx_set_at (gl_list_t list, size_t position, const void *elt) { size_t count = list->count; gl_list_node_t node; @@ -226,7 +289,19 @@ gl_linked_set_at (gl_list_t list, size_t position, const void *elt) remove_from_bucket (list, node); node->value = elt; node->h.hashcode = new_hashcode; - add_to_bucket (list, node); + if (add_to_bucket (list, node) < 0) + { + /* Out of memory. We removed node from a bucket but cannot add + it to another bucket. In order to avoid inconsistencies, we + must remove node entirely from the list. */ + gl_list_node_t before_removed = node->prev; + gl_list_node_t after_removed = node->next; + ASYNCSAFE(gl_list_node_t) before_removed->next = after_removed; + after_removed->prev = before_removed; + list->count--; + free (node); + return NULL; + } } else node->value = elt; @@ -518,9 +593,13 @@ gl_linked_indexof_from_to (gl_list_t list, size_t start_index, size_t end_index, } static gl_list_node_t -gl_linked_add_first (gl_list_t list, const void *elt) +gl_linked_nx_add_first (gl_list_t list, const void *elt) { - 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; ASYNCSAFE(const void *) node->value = elt; #if WITH_HASHTABLE @@ -530,7 +609,11 @@ gl_linked_add_first (gl_list_t list, const void *elt) : (size_t)(uintptr_t) node->value); /* Add node to the hash table. */ - add_to_bucket (list, node); + if (add_to_bucket (list, node) < 0) + { + free (node); + return NULL; + } #endif /* Add node to the list. */ @@ -548,9 +631,13 @@ gl_linked_add_first (gl_list_t list, const void *elt) } static gl_list_node_t -gl_linked_add_last (gl_list_t list, const void *elt) +gl_linked_nx_add_last (gl_list_t list, const void *elt) { - 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; ASYNCSAFE(const void *) node->value = elt; #if WITH_HASHTABLE @@ -560,7 +647,11 @@ gl_linked_add_last (gl_list_t list, const void *elt) : (size_t)(uintptr_t) node->value); /* Add node to the hash table. */ - add_to_bucket (list, node); + if (add_to_bucket (list, node) < 0) + { + free (node); + return NULL; + } #endif /* Add node to the list. */ @@ -578,9 +669,13 @@ gl_linked_add_last (gl_list_t list, const void *elt) } static gl_list_node_t -gl_linked_add_before (gl_list_t list, gl_list_node_t node, const void *elt) +gl_linked_nx_add_before (gl_list_t list, gl_list_node_t node, const void *elt) { - 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; ASYNCSAFE(const void *) new_node->value = elt; #if WITH_HASHTABLE @@ -590,7 +685,11 @@ gl_linked_add_before (gl_list_t list, gl_list_node_t node, const void *elt) : (size_t)(uintptr_t) new_node->value); /* Add new_node to the hash table. */ - add_to_bucket (list, new_node); + if (add_to_bucket (list, new_node) < 0) + { + free (new_node); + return NULL; + } #endif /* Add new_node to the list. */ @@ -608,9 +707,13 @@ gl_linked_add_before (gl_list_t list, gl_list_node_t node, const void *elt) } static gl_list_node_t -gl_linked_add_after (gl_list_t list, gl_list_node_t node, const void *elt) +gl_linked_nx_add_after (gl_list_t list, gl_list_node_t node, const void *elt) { - 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; ASYNCSAFE(const void *) new_node->value = elt; #if WITH_HASHTABLE @@ -620,7 +723,11 @@ gl_linked_add_after (gl_list_t list, gl_list_node_t node, const void *elt) : (size_t)(uintptr_t) new_node->value); /* Add new_node to the hash table. */ - add_to_bucket (list, new_node); + if (add_to_bucket (list, new_node) < 0) + { + free (new_node); + return NULL; + } #endif /* Add new_node to the list. */ @@ -638,7 +745,7 @@ gl_linked_add_after (gl_list_t list, gl_list_node_t node, const void *elt) } static gl_list_node_t -gl_linked_add_at (gl_list_t list, size_t position, const void *elt) +gl_linked_nx_add_at (gl_list_t list, size_t position, const void *elt) { size_t count = list->count; gl_list_node_t new_node; @@ -647,7 +754,10 @@ gl_linked_add_at (gl_list_t list, size_t position, const void *elt) /* Invalid argument. */ abort (); - new_node = XMALLOC (struct gl_list_node_impl); + new_node = (struct gl_list_node_impl *) malloc (sizeof (struct gl_list_node_impl)); + if (new_node == NULL) + return NULL; + ASYNCSAFE(const void *) new_node->value = elt; #if WITH_HASHTABLE new_node->h.hashcode = @@ -656,7 +766,11 @@ gl_linked_add_at (gl_list_t list, size_t position, const void *elt) : (size_t)(uintptr_t) new_node->value); /* Add new_node to the hash table. */ - add_to_bucket (list, new_node); + if (add_to_bucket (list, new_node) < 0) + { + free (new_node); + return NULL; + } #endif /* Add new_node to the list. */ @@ -1051,15 +1165,15 @@ gl_linked_sortedlist_indexof_from_to (gl_list_t list, } static gl_list_node_t -gl_linked_sortedlist_add (gl_list_t list, gl_listelement_compar_fn compar, - const void *elt) +gl_linked_sortedlist_nx_add (gl_list_t list, gl_listelement_compar_fn compar, + const void *elt) { gl_list_node_t node; for (node = list->root.next; node != &list->root; node = node->next) if (compar (node->value, elt) >= 0) - return gl_linked_add_before (list, node, elt); - return gl_linked_add_last (list, elt); + return gl_linked_nx_add_before (list, node, elt); + return gl_linked_nx_add_last (list, elt); } static bool diff --git a/lib/gl_anyrbtree_list2.h b/lib/gl_anyrbtree_list2.h index 4f6a91219d..487a27e49d 100644 --- a/lib/gl_anyrbtree_list2.h +++ b/lib/gl_anyrbtree_list2.h @@ -1,5 +1,5 @@ /* Sequential list data type implemented by a binary tree. - Copyright (C) 2006-2007 Free Software Foundation, Inc. + Copyright (C) 2006-2007, 2009 Free Software Foundation, Inc. Written by Bruno Haible <bruno@clisp.org>, 2006. This program is free software: you can redistribute it and/or modify @@ -22,7 +22,8 @@ /* 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) @@ -30,7 +31,10 @@ create_subtree_with_contents (unsigned int bh, 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) { @@ -38,6 +42,8 @@ create_subtree_with_contents (unsigned int bh, 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 @@ -51,6 +57,8 @@ create_subtree_with_contents (unsigned int bh, 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 @@ -61,17 +69,28 @@ create_subtree_with_contents (unsigned int bh, 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; @@ -84,7 +103,12 @@ gl_tree_create (gl_list_implementation_t implementation, 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) @@ -100,18 +124,33 @@ gl_tree_create (gl_list_implementation_t implementation, } 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. @@ -593,11 +632,160 @@ rebalance_after_remove (gl_list_t list, gl_list_node_t child, gl_list_node_t par } } +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; @@ -643,7 +831,12 @@ gl_tree_add_first (gl_list_t list, 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 @@ -651,10 +844,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 = 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; @@ -700,7 +897,12 @@ gl_tree_add_last (gl_list_t list, 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 @@ -708,10 +910,14 @@ 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 = 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; @@ -750,7 +956,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 @@ -758,10 +969,14 @@ 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 = 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; @@ -800,168 +1015,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; - /* 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; -} diff --git a/lib/gl_anytree_list1.h b/lib/gl_anytree_list1.h index c73a4f139d..bebfd93400 100644 --- a/lib/gl_anytree_list1.h +++ b/lib/gl_anytree_list1.h @@ -1,5 +1,5 @@ /* Sequential list data type implemented by a binary tree. - Copyright (C) 2006 Free Software Foundation, Inc. + Copyright (C) 2006, 2009 Free Software Foundation, Inc. Written by Bruno Haible <bruno@clisp.org>, 2006. This program is free software: you can redistribute it and/or modify @@ -27,3 +27,15 @@ typedef struct /* A stack used for iterating across the elements. */ typedef iterstack_item_t iterstack_t[MAXHEIGHT]; + +/* Free a non-empty subtree recursively. + This function is recursive and therefore not very fast. */ +static void +free_subtree (gl_list_node_t node) +{ + if (node->left != NULL) + free_subtree (node->left); + if (node->right != NULL) + free_subtree (node->right); + free (node); +} diff --git a/lib/gl_anytree_list2.h b/lib/gl_anytree_list2.h index c2cc82084e..0b2889991e 100644 --- a/lib/gl_anytree_list2.h +++ b/lib/gl_anytree_list2.h @@ -1,5 +1,5 @@ /* Sequential list data type implemented by a binary tree. - Copyright (C) 2006-2008 Free Software Foundation, Inc. + Copyright (C) 2006-2009 Free Software Foundation, Inc. Written by Bruno Haible <bruno@clisp.org>, 2006. This program is free software: you can redistribute it and/or modify @@ -19,13 +19,16 @@ gl_avltreehash_list.c, gl_rbtreehash_list.c. */ static gl_list_t -gl_tree_create_empty (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) +gl_tree_nx_create_empty (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) { - 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; @@ -34,11 +37,20 @@ gl_tree_create_empty (gl_list_implementation_t implementation, list->base.allow_duplicates = allow_duplicates; #if WITH_HASHTABLE list->table_size = 11; - list->table = XCALLOC (list->table_size, gl_hash_entry_t); + list->table = + (gl_hash_entry_t *) calloc (list->table_size, sizeof (gl_hash_entry_t)); + if (list->table == NULL) + goto fail; #endif list->root = NULL; return list; + +#if WITH_HASHTABLE + fail: + free (list); + return NULL; +#endif } static size_t @@ -53,8 +65,8 @@ gl_tree_node_value (gl_list_t list, gl_list_node_t node) return node->value; } -static void -gl_tree_node_set_value (gl_list_t list, gl_list_node_t node, const void *elt) +static int +gl_tree_node_nx_set_value (gl_list_t list, gl_list_node_t node, const void *elt) { #if WITH_HASHTABLE if (elt != node->value) @@ -69,7 +81,15 @@ gl_tree_node_set_value (gl_list_t list, gl_list_node_t node, const void *elt) remove_from_bucket (list, node); node->value = elt; node->h.hashcode = new_hashcode; - add_to_bucket (list, node); + if (add_to_bucket (list, node) < 0) + { + /* Out of memory. We removed node from a bucket but cannot add + it to another bucket. In order to avoid inconsistencies, we + must remove node entirely from the list. */ + gl_tree_remove_node_from_tree (list, node); + free (node); + return -1; + } } else node->value = elt; @@ -77,6 +97,7 @@ gl_tree_node_set_value (gl_list_t list, gl_list_node_t node, const void *elt) #else node->value = elt; #endif + return 0; } static gl_list_node_t @@ -154,7 +175,7 @@ gl_tree_get_at (gl_list_t list, size_t position) } static gl_list_node_t -gl_tree_set_at (gl_list_t list, size_t position, const void *elt) +gl_tree_nx_set_at (gl_list_t list, size_t position, const void *elt) { gl_list_node_t node = list->root; @@ -175,7 +196,15 @@ gl_tree_set_at (gl_list_t list, size_t position, const void *elt) remove_from_bucket (list, node); node->value = elt; node->h.hashcode = new_hashcode; - add_to_bucket (list, node); + if (add_to_bucket (list, node) < 0) + { + /* Out of memory. We removed node from a bucket but cannot add + it to another bucket. In order to avoid inconsistencies, we + must remove node entirely from the list. */ + gl_tree_remove_node_from_tree (list, node); + free (node); + return NULL; + } } else node->value = elt; @@ -413,7 +442,7 @@ gl_tree_indexof_from_to (gl_list_t list, size_t start_index, size_t end_index, #endif static gl_list_node_t -gl_tree_add_at (gl_list_t list, size_t position, const void *elt) +gl_tree_nx_add_at (gl_list_t list, size_t position, const void *elt) { size_t count = (list->root != NULL ? list->root->branch_size : 0); @@ -421,9 +450,27 @@ gl_tree_add_at (gl_list_t list, size_t position, const void *elt) /* Invalid argument. */ abort (); if (position == count) - return gl_tree_add_last (list, elt); + return gl_tree_nx_add_last (list, elt); else - return gl_tree_add_before (list, node_at (list->root, position), elt); + return gl_tree_nx_add_before (list, node_at (list->root, position), elt); +} + +static bool +gl_tree_remove_node (gl_list_t list, gl_list_node_t node) +{ +#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 + + gl_tree_remove_node_from_tree (list, node); + + if (list->base.dispose_fn != NULL) + list->base.dispose_fn (node->value); + free (node); + return true; } static bool @@ -852,13 +899,13 @@ gl_tree_sortedlist_indexof_from_to (gl_list_t list, } static gl_list_node_t -gl_tree_sortedlist_add (gl_list_t list, gl_listelement_compar_fn compar, - const void *elt) +gl_tree_sortedlist_nx_add (gl_list_t list, gl_listelement_compar_fn compar, + const void *elt) { gl_list_node_t node = list->root; if (node == NULL) - return gl_tree_add_first (list, elt); + return gl_tree_nx_add_first (list, elt); for (;;) { @@ -867,17 +914,17 @@ gl_tree_sortedlist_add (gl_list_t list, gl_listelement_compar_fn compar, if (cmp < 0) { if (node->right == NULL) - return gl_tree_add_after (list, node, elt); + return gl_tree_nx_add_after (list, node, elt); node = node->right; } else if (cmp > 0) { if (node->left == NULL) - return gl_tree_add_before (list, node, elt); + return gl_tree_nx_add_before (list, node, elt); node = node->left; } else /* cmp == 0 */ - return gl_tree_add_before (list, node, elt); + return gl_tree_nx_add_before (list, node, elt); } } diff --git a/lib/gl_anytreehash_list1.h b/lib/gl_anytreehash_list1.h index ab2f1a675c..97a97206b8 100644 --- a/lib/gl_anytreehash_list1.h +++ b/lib/gl_anytreehash_list1.h @@ -104,8 +104,9 @@ gl_oset_first (gl_oset_t set) O((log n)^2): gl_oset_nx_add may need to add an element to an ordered set of size O(n), needing O(log n) comparison function calls. The comparison function is compare_by_position, which is O(log n) worst-case. - If duplicates are forbidden, this function is O(1). */ -static void + If duplicates are forbidden, this function is O(1). + Return 0 upon success, -1 upon out-of-memory. */ +static int add_to_bucket (gl_list_t list, gl_list_node_t new_node) { size_t bucket = new_node->h.hashcode % list->table_size; @@ -134,9 +135,7 @@ add_to_bucket (gl_list_t list, gl_list_node_t new_node) { /* Found already multiple nodes with the same value. Add the new_node to it. */ - if (gl_oset_nx_add (nodes, new_node) < 0) - xalloc_die (); - return; + return gl_oset_nx_add (nodes, new_node); } } else @@ -154,20 +153,27 @@ add_to_bucket (gl_list_t list, gl_list_node_t new_node) gl_oset_nx_create_empty (OSET_TREE_FLAVOR, compare_by_position, NULL); if (nodes == NULL) - xalloc_die (); + return -1; if (gl_oset_nx_add (nodes, node) < 0) - xalloc_die (); + goto fail; if (gl_oset_nx_add (nodes, new_node) < 0) - xalloc_die (); + goto fail; - multi_entry = XMALLOC (struct gl_multiple_nodes); + multi_entry = + (struct gl_multiple_nodes *) malloc (sizeof (struct gl_multiple_nodes)); + if (multi_entry == NULL) + goto fail; multi_entry->h.hash_next = entry->hash_next; multi_entry->h.hashcode = entry->hashcode; multi_entry->magic = MULTIPLE_NODES_MAGIC; multi_entry->nodes = nodes; *entryp = &multi_entry->h; - return; + return 0; + + fail: + gl_oset_free (nodes); + return -1; } } } @@ -176,7 +182,13 @@ add_to_bucket (gl_list_t list, gl_list_node_t new_node) /* If no duplicates are allowed, multiple nodes are not needed. */ new_node->h.hash_next = list->table[bucket]; list->table[bucket] = &new_node->h; + return 0; } +/* Tell GCC that the likely return value is 0. */ +#if __GNUC__ >= 3 +# define add_to_bucket(list,node) \ + __builtin_expect ((add_to_bucket) (list, node), 0) +#endif /* Remove a node from the hash table structure. If duplicates are allowed, this function performs in average time @@ -258,8 +270,9 @@ remove_from_bucket (gl_list_t list, gl_list_node_t old_node) } /* Build up the hash table during initialization: Store all the nodes of - list->root in the hash table. */ -static inline void + list->root in the hash table. + Return 0 upon success, -1 upon out-of-memory. */ +static inline int add_nodes_to_buckets (gl_list_t list) { /* Iterate across all nodes. */ @@ -283,7 +296,7 @@ add_nodes_to_buckets (gl_list_t list) for (;;) { if (stack_ptr == &stack[0]) - return; + goto done; stack_ptr--; if (!stack_ptr->rightp) break; @@ -294,10 +307,52 @@ add_nodes_to_buckets (gl_list_t list) (list->base.hashcode_fn != NULL ? list->base.hashcode_fn (node->value) : (size_t)(uintptr_t) node->value); - add_to_bucket (list, node); + if (add_to_bucket (list, node) < 0) + goto fail; /* Descend on right branch. */ stack_ptr->rightp = true; node = node->right; stack_ptr++; } + done: + return 0; + + fail: + /* Undo everything. */ + for (;;) + { + /* Descend on left branch. */ + stack_ptr->rightp = false; + node = node->left; + stack_ptr++; + /* Descend on right branch. */ + for (;;) + { + if (node == NULL) + break; + stack_ptr->node = node; + stack_ptr->rightp = true; + node = node->right; + stack_ptr++; + } + /* Climb up again. */ + for (;;) + { + if (stack_ptr == &stack[0]) + goto fail_done; + stack_ptr--; + if (stack_ptr->rightp) + break; + } + node = stack_ptr->node; + /* Remove the current node from the hash table. */ + remove_from_bucket (list, node); + } + fail_done: + return -1; } +/* Tell GCC that the likely return value is 0. */ +#if __GNUC__ >= 3 +# define add_nodes_to_buckets(list) \ + __builtin_expect ((add_nodes_to_buckets) (list), 0) +#endif diff --git a/lib/gl_array_list.c b/lib/gl_array_list.c index d75bf0a740..6d5b124419 100644 --- a/lib/gl_array_list.c +++ b/lib/gl_array_list.c @@ -1,5 +1,5 @@ /* Sequential list data type implemented by an array. - Copyright (C) 2006-2008 Free Software Foundation, Inc. + Copyright (C) 2006-2009 Free Software Foundation, Inc. Written by Bruno Haible <bruno@clisp.org>, 2006. This program is free software: you can redistribute it and/or modify @@ -24,8 +24,6 @@ /* Get memcpy. */ #include <string.h> -#include "xalloc.h" - /* Checked size_t computations. */ #include "xsize.h" @@ -52,13 +50,17 @@ struct gl_list_impl #define NODE_TO_INDEX(node) ((uintptr_t)(node) - 1) static gl_list_t -gl_array_create_empty (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) +gl_array_nx_create_empty (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) { - 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; @@ -73,14 +75,18 @@ gl_array_create_empty (gl_list_implementation_t implementation, } static gl_list_t -gl_array_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_array_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; @@ -89,7 +95,11 @@ gl_array_create (gl_list_implementation_t implementation, list->base.allow_duplicates = allow_duplicates; if (count > 0) { - list->elements = XNMALLOC (count, const void *); + if (size_overflow_p (xtimes (count, sizeof (const void *)))) + goto fail; + list->elements = (const void **) malloc (count * sizeof (const void *)); + if (list->elements == NULL) + goto fail; memcpy (list->elements, contents, count * sizeof (const void *)); } else @@ -98,6 +108,10 @@ gl_array_create (gl_list_implementation_t implementation, list->allocated = count; return list; + + fail: + free (list); + return NULL; } static size_t @@ -116,14 +130,16 @@ gl_array_node_value (gl_list_t list, gl_list_node_t node) return list->elements[index]; } -static void -gl_array_node_set_value (gl_list_t list, gl_list_node_t node, const void *elt) +static int +gl_array_node_nx_set_value (gl_list_t list, gl_list_node_t node, + const void *elt) { uintptr_t index = NODE_TO_INDEX (node); if (!(index < list->count)) /* Invalid argument. */ abort (); list->elements[index] = elt; + return 0; } static gl_list_node_t @@ -165,7 +181,7 @@ gl_array_get_at (gl_list_t list, size_t position) } static gl_list_node_t -gl_array_set_at (gl_list_t list, size_t position, const void *elt) +gl_array_nx_set_at (gl_list_t list, size_t position, const void *elt) { size_t count = list->count; @@ -227,8 +243,9 @@ gl_array_search_from_to (gl_list_t list, size_t start_index, size_t end_index, return INDEX_TO_NODE (index); } -/* Ensure that list->allocated > list->count. */ -static void +/* Ensure that list->allocated > list->count. + Return 0 upon success, -1 upon out-of-memory. */ +static int grow (gl_list_t list) { size_t new_allocated; @@ -240,24 +257,26 @@ grow (gl_list_t list) memory_size = xtimes (new_allocated, sizeof (const void *)); if (size_overflow_p (memory_size)) /* Overflow, would lead to out of memory. */ - xalloc_die (); - memory = (const void **) xrealloc (list->elements, memory_size); + return -1; + memory = (const void **) realloc (list->elements, memory_size); if (memory == NULL) /* Out of memory. */ - xalloc_die (); + return -1; list->elements = memory; list->allocated = new_allocated; + return 0; } static gl_list_node_t -gl_array_add_first (gl_list_t list, const void *elt) +gl_array_nx_add_first (gl_list_t list, const void *elt) { size_t count = list->count; const void **elements; size_t i; if (count == list->allocated) - grow (list); + if (grow (list) < 0) + return NULL; elements = list->elements; for (i = count; i > 0; i--) elements[i] = elements[i - 1]; @@ -267,19 +286,20 @@ gl_array_add_first (gl_list_t list, const void *elt) } static gl_list_node_t -gl_array_add_last (gl_list_t list, const void *elt) +gl_array_nx_add_last (gl_list_t list, const void *elt) { size_t count = list->count; if (count == list->allocated) - grow (list); + if (grow (list) < 0) + return NULL; list->elements[count] = elt; list->count = count + 1; return INDEX_TO_NODE (count); } static gl_list_node_t -gl_array_add_before (gl_list_t list, gl_list_node_t node, const void *elt) +gl_array_nx_add_before (gl_list_t list, gl_list_node_t node, const void *elt) { size_t count = list->count; uintptr_t index = NODE_TO_INDEX (node); @@ -292,7 +312,8 @@ gl_array_add_before (gl_list_t list, gl_list_node_t node, const void *elt) abort (); position = index; if (count == list->allocated) - grow (list); + if (grow (list) < 0) + return NULL; elements = list->elements; for (i = count; i > position; i--) elements[i] = elements[i - 1]; @@ -302,7 +323,7 @@ gl_array_add_before (gl_list_t list, gl_list_node_t node, const void *elt) } static gl_list_node_t -gl_array_add_after (gl_list_t list, gl_list_node_t node, const void *elt) +gl_array_nx_add_after (gl_list_t list, gl_list_node_t node, const void *elt) { size_t count = list->count; uintptr_t index = NODE_TO_INDEX (node); @@ -315,7 +336,8 @@ gl_array_add_after (gl_list_t list, gl_list_node_t node, const void *elt) abort (); position = index + 1; if (count == list->allocated) - grow (list); + if (grow (list) < 0) + return NULL; elements = list->elements; for (i = count; i > position; i--) elements[i] = elements[i - 1]; @@ -325,7 +347,7 @@ gl_array_add_after (gl_list_t list, gl_list_node_t node, const void *elt) } static gl_list_node_t -gl_array_add_at (gl_list_t list, size_t position, const void *elt) +gl_array_nx_add_at (gl_list_t list, size_t position, const void *elt) { size_t count = list->count; const void **elements; @@ -335,7 +357,8 @@ gl_array_add_at (gl_list_t list, size_t position, const void *elt) /* Invalid argument. */ abort (); if (count == list->allocated) - grow (list); + if (grow (list) < 0) + return NULL; elements = list->elements; for (i = count; i > position; i--) elements[i] = elements[i - 1]; @@ -583,8 +606,8 @@ gl_array_sortedlist_search (gl_list_t list, gl_listelement_compar_fn compar, } static gl_list_node_t -gl_array_sortedlist_add (gl_list_t list, gl_listelement_compar_fn compar, - const void *elt) +gl_array_sortedlist_nx_add (gl_list_t list, gl_listelement_compar_fn compar, + const void *elt) { size_t count = list->count; size_t low = 0; @@ -607,7 +630,7 @@ gl_array_sortedlist_add (gl_list_t list, gl_listelement_compar_fn compar, break; } } - return gl_array_add_at (list, low, elt); + return gl_array_nx_add_at (list, low, elt); } static bool @@ -624,22 +647,22 @@ gl_array_sortedlist_remove (gl_list_t list, gl_listelement_compar_fn compar, const struct gl_list_implementation gl_array_list_implementation = { - gl_array_create_empty, - gl_array_create, + gl_array_nx_create_empty, + gl_array_nx_create, gl_array_size, gl_array_node_value, - gl_array_node_set_value, + gl_array_node_nx_set_value, gl_array_next_node, gl_array_previous_node, gl_array_get_at, - gl_array_set_at, + gl_array_nx_set_at, gl_array_search_from_to, gl_array_indexof_from_to, - gl_array_add_first, - gl_array_add_last, - gl_array_add_before, - gl_array_add_after, - gl_array_add_at, + gl_array_nx_add_first, + gl_array_nx_add_last, + gl_array_nx_add_before, + gl_array_nx_add_after, + gl_array_nx_add_at, gl_array_remove_node, gl_array_remove_at, gl_array_remove, @@ -652,6 +675,6 @@ const struct gl_list_implementation gl_array_list_implementation = gl_array_sortedlist_search_from_to, gl_array_sortedlist_indexof, gl_array_sortedlist_indexof_from_to, - gl_array_sortedlist_add, + gl_array_sortedlist_nx_add, gl_array_sortedlist_remove }; diff --git a/lib/gl_avltree_list.c b/lib/gl_avltree_list.c index 1f6c470ff5..c11a56882f 100644 --- a/lib/gl_avltree_list.c +++ b/lib/gl_avltree_list.c @@ -1,5 +1,5 @@ /* Sequential list data type implemented by a binary tree. - Copyright (C) 2006, 2008 Free Software Foundation, Inc. + Copyright (C) 2006, 2008-2009 Free Software Foundation, Inc. Written by Bruno Haible <bruno@clisp.org>, 2006. This program is free software: you can redistribute it and/or modify @@ -22,16 +22,18 @@ #include <stdlib.h> -#include "xalloc.h" - /* -------------------------- gl_list_t Data Type -------------------------- */ /* Generic AVL tree code. */ #include "gl_anyavltree_list1.h" -#include "gl_anyavltree_list2.h" /* Generic binary tree code. */ #include "gl_anytree_list1.h" + +/* Generic AVL tree code. */ +#include "gl_anyavltree_list2.h" + +/* Generic binary tree code. */ #include "gl_anytree_list2.h" /* For debugging. */ @@ -66,22 +68,22 @@ gl_avltree_list_check_invariants (gl_list_t list) const struct gl_list_implementation gl_avltree_list_implementation = { - gl_tree_create_empty, - gl_tree_create, + gl_tree_nx_create_empty, + gl_tree_nx_create, gl_tree_size, gl_tree_node_value, - gl_tree_node_set_value, + gl_tree_node_nx_set_value, gl_tree_next_node, gl_tree_previous_node, gl_tree_get_at, - gl_tree_set_at, + gl_tree_nx_set_at, gl_tree_search_from_to, gl_tree_indexof_from_to, - gl_tree_add_first, - gl_tree_add_last, - gl_tree_add_before, - gl_tree_add_after, - gl_tree_add_at, + gl_tree_nx_add_first, + gl_tree_nx_add_last, + gl_tree_nx_add_before, + gl_tree_nx_add_after, + gl_tree_nx_add_at, gl_tree_remove_node, gl_tree_remove_at, gl_tree_remove, @@ -94,6 +96,6 @@ const struct gl_list_implementation gl_avltree_list_implementation = gl_tree_sortedlist_search_from_to, gl_tree_sortedlist_indexof, gl_tree_sortedlist_indexof_from_to, - gl_tree_sortedlist_add, + gl_tree_sortedlist_nx_add, gl_tree_sortedlist_remove }; diff --git a/lib/gl_avltreehash_list.c b/lib/gl_avltreehash_list.c index 33f56fe741..ef968ef060 100644 --- a/lib/gl_avltreehash_list.c +++ b/lib/gl_avltreehash_list.c @@ -1,5 +1,5 @@ /* Sequential list data type implemented by a hash table with a binary tree. - Copyright (C) 2006, 2008 Free Software Foundation, Inc. + Copyright (C) 2006, 2008-2009 Free Software Foundation, Inc. Written by Bruno Haible <bruno@clisp.org>, 2006. This program is free software: you can redistribute it and/or modify @@ -24,7 +24,6 @@ #include <stdlib.h> #include "gl_avltree_oset.h" -#include "xalloc.h" #include "xsize.h" #ifndef uintptr_t @@ -95,22 +94,22 @@ gl_avltreehash_list_check_invariants (gl_list_t list) const struct gl_list_implementation gl_avltreehash_list_implementation = { - gl_tree_create_empty, - gl_tree_create, + gl_tree_nx_create_empty, + gl_tree_nx_create, gl_tree_size, gl_tree_node_value, - gl_tree_node_set_value, + gl_tree_node_nx_set_value, gl_tree_next_node, gl_tree_previous_node, gl_tree_get_at, - gl_tree_set_at, + gl_tree_nx_set_at, gl_tree_search_from_to, gl_tree_indexof_from_to, - gl_tree_add_first, - gl_tree_add_last, - gl_tree_add_before, - gl_tree_add_after, - gl_tree_add_at, + gl_tree_nx_add_first, + gl_tree_nx_add_last, + gl_tree_nx_add_before, + gl_tree_nx_add_after, + gl_tree_nx_add_at, gl_tree_remove_node, gl_tree_remove_at, gl_tree_remove, @@ -123,6 +122,6 @@ const struct gl_list_implementation gl_avltreehash_list_implementation = gl_tree_sortedlist_search_from_to, gl_tree_sortedlist_indexof, gl_tree_sortedlist_indexof_from_to, - gl_tree_sortedlist_add, + gl_tree_sortedlist_nx_add, gl_tree_sortedlist_remove }; diff --git a/lib/gl_carray_list.c b/lib/gl_carray_list.c index 719b914d01..517afdaaf9 100644 --- a/lib/gl_carray_list.c +++ b/lib/gl_carray_list.c @@ -1,5 +1,5 @@ /* Sequential list data type implemented by a circular array. - Copyright (C) 2006-2008 Free Software Foundation, Inc. + Copyright (C) 2006-2009 Free Software Foundation, Inc. Written by Bruno Haible <bruno@clisp.org>, 2006. This program is free software: you can redistribute it and/or modify @@ -24,8 +24,6 @@ /* Get memcpy. */ #include <string.h> -#include "xalloc.h" - /* Checked size_t computations. */ #include "xsize.h" @@ -55,13 +53,17 @@ struct gl_list_impl #define NODE_TO_INDEX(node) ((uintptr_t)(node) - 1) static gl_list_t -gl_carray_create_empty (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) +gl_carray_nx_create_empty (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) { - 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; @@ -77,14 +79,18 @@ gl_carray_create_empty (gl_list_implementation_t implementation, } static gl_list_t -gl_carray_create (gl_list_implementation_t implementation, +gl_carray_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; @@ -93,7 +99,11 @@ gl_carray_create (gl_list_implementation_t implementation, list->base.allow_duplicates = allow_duplicates; if (count > 0) { - list->elements = XNMALLOC (count, const void *); + if (size_overflow_p (xtimes (count, sizeof (const void *)))) + goto fail; + list->elements = (const void **) malloc (count * sizeof (const void *)); + if (list->elements == NULL) + goto fail; memcpy (list->elements, contents, count * sizeof (const void *)); } else @@ -103,6 +113,10 @@ gl_carray_create (gl_list_implementation_t implementation, list->allocated = count; return list; + + fail: + free (list); + return NULL; } static size_t @@ -126,8 +140,9 @@ gl_carray_node_value (gl_list_t list, gl_list_node_t node) return list->elements[i]; } -static void -gl_carray_node_set_value (gl_list_t list, gl_list_node_t node, const void *elt) +static int +gl_carray_node_nx_set_value (gl_list_t list, gl_list_node_t node, + const void *elt) { uintptr_t index = NODE_TO_INDEX (node); size_t i; @@ -139,6 +154,7 @@ gl_carray_node_set_value (gl_list_t list, gl_list_node_t node, const void *elt) if (i >= list->allocated) i -= list->allocated; list->elements[i] = elt; + return 0; } static gl_list_node_t @@ -184,7 +200,7 @@ gl_carray_get_at (gl_list_t list, size_t position) } static gl_list_node_t -gl_carray_set_at (gl_list_t list, size_t position, const void *elt) +gl_carray_nx_set_at (gl_list_t list, size_t position, const void *elt) { size_t count = list->count; size_t i; @@ -269,8 +285,9 @@ gl_carray_search_from_to (gl_list_t list, size_t start_index, size_t end_index, return INDEX_TO_NODE (index); } -/* Ensure that list->allocated > list->count. */ -static void +/* Ensure that list->allocated > list->count. + Return 0 upon success, -1 upon out-of-memory. */ +static int grow (gl_list_t list) { size_t new_allocated; @@ -282,13 +299,13 @@ grow (gl_list_t list) memory_size = xtimes (new_allocated, sizeof (const void *)); if (size_overflow_p (memory_size)) /* Overflow, would lead to out of memory. */ - xalloc_die (); + return -1; if (list->offset > 0 && list->count > 0) { - memory = (const void **) xmalloc (memory_size); + memory = (const void **) malloc (memory_size); if (memory == NULL) /* Out of memory. */ - xalloc_die (); + return -1; if (list->offset + list->count > list->allocated) { memcpy (memory, &list->elements[list->offset], @@ -306,23 +323,25 @@ grow (gl_list_t list) } else { - memory = (const void **) xrealloc (list->elements, memory_size); + memory = (const void **) realloc (list->elements, memory_size); if (memory == NULL) /* Out of memory. */ - xalloc_die (); + return -1; } list->elements = memory; list->offset = 0; list->allocated = new_allocated; + return 0; } static gl_list_node_t -gl_carray_add_first (gl_list_t list, const void *elt) +gl_carray_nx_add_first (gl_list_t list, const void *elt) { size_t count = list->count; if (count == list->allocated) - grow (list); + if (grow (list) < 0) + return NULL; list->offset = (list->offset == 0 ? list->allocated : list->offset) - 1; list->elements[list->offset] = elt; list->count = count + 1; @@ -330,13 +349,14 @@ gl_carray_add_first (gl_list_t list, const void *elt) } static gl_list_node_t -gl_carray_add_last (gl_list_t list, const void *elt) +gl_carray_nx_add_last (gl_list_t list, const void *elt) { size_t count = list->count; size_t i; if (count == list->allocated) - grow (list); + if (grow (list) < 0) + return NULL; i = list->offset + count; if (i >= list->allocated) i -= list->allocated; @@ -346,7 +366,7 @@ gl_carray_add_last (gl_list_t list, const void *elt) } static gl_list_node_t -gl_carray_add_at (gl_list_t list, size_t position, const void *elt) +gl_carray_nx_add_at (gl_list_t list, size_t position, const void *elt) { size_t count = list->count; const void **elements; @@ -355,7 +375,8 @@ gl_carray_add_at (gl_list_t list, size_t position, const void *elt) /* Invalid argument. */ abort (); if (count == list->allocated) - grow (list); + if (grow (list) < 0) + return NULL; elements = list->elements; if (position <= (count / 2)) { @@ -420,7 +441,7 @@ gl_carray_add_at (gl_list_t list, size_t position, const void *elt) } static gl_list_node_t -gl_carray_add_before (gl_list_t list, gl_list_node_t node, const void *elt) +gl_carray_nx_add_before (gl_list_t list, gl_list_node_t node, const void *elt) { size_t count = list->count; uintptr_t index = NODE_TO_INDEX (node); @@ -428,11 +449,11 @@ gl_carray_add_before (gl_list_t list, gl_list_node_t node, const void *elt) if (!(index < count)) /* Invalid argument. */ abort (); - return gl_carray_add_at (list, index, elt); + return gl_carray_nx_add_at (list, index, elt); } static gl_list_node_t -gl_carray_add_after (gl_list_t list, gl_list_node_t node, const void *elt) +gl_carray_nx_add_after (gl_list_t list, gl_list_node_t node, const void *elt) { size_t count = list->count; uintptr_t index = NODE_TO_INDEX (node); @@ -440,7 +461,7 @@ gl_carray_add_after (gl_list_t list, gl_list_node_t node, const void *elt) if (!(index < count)) /* Invalid argument. */ abort (); - return gl_carray_add_at (list, index + 1, elt); + return gl_carray_nx_add_at (list, index + 1, elt); } static bool @@ -771,8 +792,8 @@ gl_carray_sortedlist_search (gl_list_t list, gl_listelement_compar_fn compar, } static gl_list_node_t -gl_carray_sortedlist_add (gl_list_t list, gl_listelement_compar_fn compar, - const void *elt) +gl_carray_sortedlist_nx_add (gl_list_t list, gl_listelement_compar_fn compar, + const void *elt) { size_t count = list->count; size_t low = 0; @@ -802,7 +823,7 @@ gl_carray_sortedlist_add (gl_list_t list, gl_listelement_compar_fn compar, break; } } - return gl_carray_add_at (list, low, elt); + return gl_carray_nx_add_at (list, low, elt); } static bool @@ -819,22 +840,22 @@ gl_carray_sortedlist_remove (gl_list_t list, gl_listelement_compar_fn compar, const struct gl_list_implementation gl_carray_list_implementation = { - gl_carray_create_empty, - gl_carray_create, + gl_carray_nx_create_empty, + gl_carray_nx_create, gl_carray_size, gl_carray_node_value, - gl_carray_node_set_value, + gl_carray_node_nx_set_value, gl_carray_next_node, gl_carray_previous_node, gl_carray_get_at, - gl_carray_set_at, + gl_carray_nx_set_at, gl_carray_search_from_to, gl_carray_indexof_from_to, - gl_carray_add_first, - gl_carray_add_last, - gl_carray_add_before, - gl_carray_add_after, - gl_carray_add_at, + gl_carray_nx_add_first, + gl_carray_nx_add_last, + gl_carray_nx_add_before, + gl_carray_nx_add_after, + gl_carray_nx_add_at, gl_carray_remove_node, gl_carray_remove_at, gl_carray_remove, @@ -847,6 +868,6 @@ const struct gl_list_implementation gl_carray_list_implementation = gl_carray_sortedlist_search_from_to, gl_carray_sortedlist_indexof, gl_carray_sortedlist_indexof_from_to, - gl_carray_sortedlist_add, + gl_carray_sortedlist_nx_add, gl_carray_sortedlist_remove }; diff --git a/lib/gl_linked_list.c b/lib/gl_linked_list.c index a1bd5eee4a..7211978de3 100644 --- a/lib/gl_linked_list.c +++ b/lib/gl_linked_list.c @@ -1,5 +1,5 @@ /* Sequential list data type implemented by a linked list. - Copyright (C) 2006, 2008 Free Software Foundation, Inc. + Copyright (C) 2006, 2008-2009 Free Software Foundation, Inc. Written by Bruno Haible <bruno@clisp.org>, 2006. This program is free software: you can redistribute it and/or modify @@ -22,8 +22,6 @@ #include <stdlib.h> -#include "xalloc.h" - /* -------------------------- gl_list_t Data Type -------------------------- */ /* Generic linked list code. */ @@ -33,22 +31,22 @@ const struct gl_list_implementation gl_linked_list_implementation = { - gl_linked_create_empty, - gl_linked_create, + gl_linked_nx_create_empty, + gl_linked_nx_create, gl_linked_size, gl_linked_node_value, - gl_linked_node_set_value, + gl_linked_node_nx_set_value, gl_linked_next_node, gl_linked_previous_node, gl_linked_get_at, - gl_linked_set_at, + gl_linked_nx_set_at, gl_linked_search_from_to, gl_linked_indexof_from_to, - gl_linked_add_first, - gl_linked_add_last, - gl_linked_add_before, - gl_linked_add_after, - gl_linked_add_at, + gl_linked_nx_add_first, + gl_linked_nx_add_last, + gl_linked_nx_add_before, + gl_linked_nx_add_after, + gl_linked_nx_add_at, gl_linked_remove_node, gl_linked_remove_at, gl_linked_remove, @@ -61,6 +59,6 @@ const struct gl_list_implementation gl_linked_list_implementation = gl_linked_sortedlist_search_from_to, gl_linked_sortedlist_indexof, gl_linked_sortedlist_indexof_from_to, - gl_linked_sortedlist_add, + gl_linked_sortedlist_nx_add, gl_linked_sortedlist_remove }; diff --git a/lib/gl_linkedhash_list.c b/lib/gl_linkedhash_list.c index c83c056cf2..30d71b8ab0 100644 --- a/lib/gl_linkedhash_list.c +++ b/lib/gl_linkedhash_list.c @@ -1,5 +1,5 @@ /* Sequential list data type implemented by a hash table with a linked list. - Copyright (C) 2006, 2008 Free Software Foundation, Inc. + Copyright (C) 2006, 2008-2009 Free Software Foundation, Inc. Written by Bruno Haible <bruno@clisp.org>, 2006. This program is free software: you can redistribute it and/or modify @@ -23,7 +23,6 @@ #include <stdint.h> /* for SIZE_MAX */ #include <stdlib.h> -#include "xalloc.h" #include "xsize.h" #ifndef uintptr_t @@ -62,6 +61,8 @@ add_to_bucket (gl_list_t list, gl_list_node_t node) node->h.hash_next = list->table[bucket]; list->table[bucket] = &node->h; } +/* Tell all compilers that the return value is 0. */ +#define add_to_bucket(list,node) ((add_to_bucket) (list, node), 0) /* Remove a node from the hash table structure. */ static inline void @@ -90,22 +91,22 @@ remove_from_bucket (gl_list_t list, gl_list_node_t node) const struct gl_list_implementation gl_linkedhash_list_implementation = { - gl_linked_create_empty, - gl_linked_create, + gl_linked_nx_create_empty, + gl_linked_nx_create, gl_linked_size, gl_linked_node_value, - gl_linked_node_set_value, + gl_linked_node_nx_set_value, gl_linked_next_node, gl_linked_previous_node, gl_linked_get_at, - gl_linked_set_at, + gl_linked_nx_set_at, gl_linked_search_from_to, gl_linked_indexof_from_to, - gl_linked_add_first, - gl_linked_add_last, - gl_linked_add_before, - gl_linked_add_after, - gl_linked_add_at, + gl_linked_nx_add_first, + gl_linked_nx_add_last, + gl_linked_nx_add_before, + gl_linked_nx_add_after, + gl_linked_nx_add_at, gl_linked_remove_node, gl_linked_remove_at, gl_linked_remove, @@ -118,6 +119,6 @@ const struct gl_list_implementation gl_linkedhash_list_implementation = gl_linked_sortedlist_search_from_to, gl_linked_sortedlist_indexof, gl_linked_sortedlist_indexof_from_to, - gl_linked_sortedlist_add, + gl_linked_sortedlist_nx_add, gl_linked_sortedlist_remove }; diff --git a/lib/gl_list.c b/lib/gl_list.c index 369615e0b4..72bb22ea27 100644 --- a/lib/gl_list.c +++ b/lib/gl_list.c @@ -27,26 +27,28 @@ Use #define to avoid a warning because of extern vs. static. */ gl_list_t -gl_list_create_empty (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) +gl_list_nx_create_empty (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) { - return implementation->create_empty (implementation, equals_fn, hashcode_fn, - dispose_fn, allow_duplicates); + return implementation->nx_create_empty (implementation, equals_fn, + hashcode_fn, dispose_fn, + allow_duplicates); } gl_list_t -gl_list_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_list_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) { - return implementation->create (implementation, equals_fn, hashcode_fn, - dispose_fn, allow_duplicates, count, contents); + return implementation->nx_create (implementation, equals_fn, hashcode_fn, + dispose_fn, allow_duplicates, count, + contents); } size_t @@ -63,11 +65,12 @@ gl_list_node_value (gl_list_t list, gl_list_node_t node) ->node_value (list, node); } -void -gl_list_node_set_value (gl_list_t list, gl_list_node_t node, const void *elt) +int +gl_list_node_nx_set_value (gl_list_t list, gl_list_node_t node, + const void *elt) { - ((const struct gl_list_impl_base *) list)->vtable - ->node_set_value (list, node, elt); + return ((const struct gl_list_impl_base *) list)->vtable + ->node_nx_set_value (list, node, elt); } gl_list_node_t @@ -92,10 +95,10 @@ gl_list_get_at (gl_list_t list, size_t position) } gl_list_node_t -gl_list_set_at (gl_list_t list, size_t position, const void *elt) +gl_list_nx_set_at (gl_list_t list, size_t position, const void *elt) { return ((const struct gl_list_impl_base *) list)->vtable - ->set_at (list, position, elt); + ->nx_set_at (list, position, elt); } gl_list_node_t @@ -145,38 +148,38 @@ gl_list_indexof_from_to (gl_list_t list, size_t start_index, size_t end_index, c } gl_list_node_t -gl_list_add_first (gl_list_t list, const void *elt) +gl_list_nx_add_first (gl_list_t list, const void *elt) { return ((const struct gl_list_impl_base *) list)->vtable - ->add_first (list, elt); + ->nx_add_first (list, elt); } gl_list_node_t -gl_list_add_last (gl_list_t list, const void *elt) +gl_list_nx_add_last (gl_list_t list, const void *elt) { return ((const struct gl_list_impl_base *) list)->vtable - ->add_last (list, elt); + ->nx_add_last (list, elt); } gl_list_node_t -gl_list_add_before (gl_list_t list, gl_list_node_t node, const void *elt) +gl_list_nx_add_before (gl_list_t list, gl_list_node_t node, const void *elt) { return ((const struct gl_list_impl_base *) list)->vtable - ->add_before (list, node, elt); + ->nx_add_before (list, node, elt); } gl_list_node_t -gl_list_add_after (gl_list_t list, gl_list_node_t node, const void *elt) +gl_list_nx_add_after (gl_list_t list, gl_list_node_t node, const void *elt) { return ((const struct gl_list_impl_base *) list)->vtable - ->add_after (list, node, elt); + ->nx_add_after (list, node, elt); } gl_list_node_t -gl_list_add_at (gl_list_t list, size_t position, const void *elt) +gl_list_nx_add_at (gl_list_t list, size_t position, const void *elt) { return ((const struct gl_list_impl_base *) list)->vtable - ->add_at (list, position, elt); + ->nx_add_at (list, position, elt); } bool @@ -264,10 +267,10 @@ gl_sortedlist_indexof_from_to (gl_list_t list, gl_listelement_compar_fn compar, } gl_list_node_t -gl_sortedlist_add (gl_list_t list, gl_listelement_compar_fn compar, const void *elt) +gl_sortedlist_nx_add (gl_list_t list, gl_listelement_compar_fn compar, const void *elt) { return ((const struct gl_list_impl_base *) list)->vtable - ->sortedlist_add (list, compar, elt); + ->sortedlist_nx_add (list, compar, elt); } bool diff --git a/lib/gl_list.h b/lib/gl_list.h index 53cfc53984..ccbf8a359b 100644 --- a/lib/gl_list.h +++ b/lib/gl_list.h @@ -129,11 +129,19 @@ typedef const struct gl_list_implementation * gl_list_implementation_t; DISPOSE_FN is an element disposal function or NULL. ALLOW_DUPLICATES is false if duplicate elements shall not be allowed in the list. The implementation may verify this at runtime. */ +#if 0 /* declared in gl_xlist.h */ extern gl_list_t gl_list_create_empty (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); +#endif +/* Likewise. Return NULL upon out-of-memory. */ +extern gl_list_t gl_list_nx_create_empty (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); /* Create a list with given contents. IMPLEMENTATION is one of GL_ARRAY_LIST, GL_CARRAY_LIST, GL_LINKED_LIST, @@ -146,12 +154,21 @@ extern gl_list_t gl_list_create_empty (gl_list_implementation_t implementation, the list. The implementation may verify this at runtime. COUNT is the number of initial elements. CONTENTS[0..COUNT-1] is the initial contents. */ +#if 0 /* declared in gl_xlist.h */ extern gl_list_t gl_list_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); +#endif +/* Likewise. Return NULL upon out-of-memory. */ +extern gl_list_t gl_list_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); /* Return the current number of elements in a list. */ extern size_t gl_list_size (gl_list_t list); @@ -160,8 +177,17 @@ extern size_t gl_list_size (gl_list_t list); extern const void * gl_list_node_value (gl_list_t list, gl_list_node_t node); /* Replace the element value represented by a list node. */ +#if 0 /* declared in gl_xlist.h */ extern void gl_list_node_set_value (gl_list_t list, gl_list_node_t node, const void *elt); +#endif +/* Likewise. Return 0 upon success, -1 upon out-of-memory. */ +extern int gl_list_node_nx_set_value (gl_list_t list, gl_list_node_t node, + const void *elt) +#if __GNUC__ > 3 || (__GNUC__ == 3 && __GNUC_MINOR__ >= 4) + __attribute__ ((__warn_unused_result__)) +#endif + ; /* Return the node immediately after the given node in the list, or NULL if the given node is the last (rightmost) one in the list. */ @@ -178,8 +204,17 @@ extern const void * gl_list_get_at (gl_list_t list, size_t position); /* Replace the element at a given position in the list. POSITION must be >= 0 and < gl_list_size (list). Return its node. */ +#if 0 /* declared in gl_xlist.h */ extern gl_list_node_t gl_list_set_at (gl_list_t list, size_t position, const void *elt); +#endif +/* Likewise. Return NULL upon out-of-memory. */ +extern gl_list_node_t gl_list_nx_set_at (gl_list_t list, size_t position, + const void *elt) +#if __GNUC__ > 3 || (__GNUC__ == 3 && __GNUC_MINOR__ >= 4) + __attribute__ ((__warn_unused_result__)) +#endif + ; /* Search whether an element is already in the list. Return its node if found, or NULL if not present in the list. */ @@ -218,26 +253,70 @@ extern size_t gl_list_indexof_from_to (gl_list_t list, /* Add an element as the first element of the list. Return its node. */ +#if 0 /* declared in gl_xlist.h */ extern gl_list_node_t gl_list_add_first (gl_list_t list, const void *elt); +#endif +/* Likewise. Return NULL upon out-of-memory. */ +extern gl_list_node_t gl_list_nx_add_first (gl_list_t list, const void *elt) +#if __GNUC__ > 3 || (__GNUC__ == 3 && __GNUC_MINOR__ >= 4) + __attribute__ ((__warn_unused_result__)) +#endif + ; /* Add an element as the last element of the list. Return its node. */ +#if 0 /* declared in gl_xlist.h */ extern gl_list_node_t gl_list_add_last (gl_list_t list, const void *elt); +#endif +/* Likewise. Return NULL upon out-of-memory. */ +extern gl_list_node_t gl_list_nx_add_last (gl_list_t list, const void *elt) +#if __GNUC__ > 3 || (__GNUC__ == 3 && __GNUC_MINOR__ >= 4) + __attribute__ ((__warn_unused_result__)) +#endif + ; /* Add an element before a given element node of the list. Return its node. */ +#if 0 /* declared in gl_xlist.h */ extern gl_list_node_t gl_list_add_before (gl_list_t list, gl_list_node_t node, const void *elt); +#endif +/* Likewise. Return NULL upon out-of-memory. */ +extern gl_list_node_t gl_list_nx_add_before (gl_list_t list, + gl_list_node_t node, + const void *elt) +#if __GNUC__ > 3 || (__GNUC__ == 3 && __GNUC_MINOR__ >= 4) + __attribute__ ((__warn_unused_result__)) +#endif + ; /* Add an element after a given element node of the list. Return its node. */ +#if 0 /* declared in gl_xlist.h */ extern gl_list_node_t gl_list_add_after (gl_list_t list, gl_list_node_t node, const void *elt); +#endif +/* Likewise. Return NULL upon out-of-memory. */ +extern gl_list_node_t gl_list_nx_add_after (gl_list_t list, gl_list_node_t node, + const void *elt) +#if __GNUC__ > 3 || (__GNUC__ == 3 && __GNUC_MINOR__ >= 4) + __attribute__ ((__warn_unused_result__)) +#endif + ; /* Add an element add a given position in the list. POSITION must be >= 0 and <= gl_list_size (list). */ +#if 0 /* declared in gl_xlist.h */ extern gl_list_node_t gl_list_add_at (gl_list_t list, size_t position, const void *elt); +#endif +/* Likewise. Return NULL upon out-of-memory. */ +extern gl_list_node_t gl_list_nx_add_at (gl_list_t list, size_t position, + const void *elt) +#if __GNUC__ > 3 || (__GNUC__ == 3 && __GNUC_MINOR__ >= 4) + __attribute__ ((__warn_unused_result__)) +#endif + ; /* Remove an element from the list. Return true. */ @@ -355,9 +434,19 @@ extern size_t gl_sortedlist_indexof_from_to (gl_list_t list, /* Add an element at the appropriate position in the list. The list is assumed to be sorted with COMPAR. Return its node. */ +#if 0 /* declared in gl_xlist.h */ extern gl_list_node_t gl_sortedlist_add (gl_list_t list, gl_listelement_compar_fn compar, const void *elt); +#endif +/* Likewise. Return NULL upon out-of-memory. */ +extern gl_list_node_t gl_sortedlist_nx_add (gl_list_t list, + gl_listelement_compar_fn compar, + const void *elt) +#if __GNUC__ > 3 || (__GNUC__ == 3 && __GNUC_MINOR__ >= 4) + __attribute__ ((__warn_unused_result__)) +#endif + ; /* Search and remove an element from the list. The list is assumed to be sorted with COMPAR. @@ -373,36 +462,38 @@ extern bool gl_sortedlist_remove (gl_list_t list, struct gl_list_implementation { /* gl_list_t functions. */ - gl_list_t (*create_empty) (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); - gl_list_t (*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_list_t (*nx_create_empty) (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); + gl_list_t (*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); size_t (*size) (gl_list_t list); const void * (*node_value) (gl_list_t list, gl_list_node_t node); - void (*node_set_value) (gl_list_t list, gl_list_node_t node, const void *elt); + int (*node_nx_set_value) (gl_list_t list, gl_list_node_t node, + const void *elt); gl_list_node_t (*next_node) (gl_list_t list, gl_list_node_t node); gl_list_node_t (*previous_node) (gl_list_t list, gl_list_node_t node); const void * (*get_at) (gl_list_t list, size_t position); - gl_list_node_t (*set_at) (gl_list_t list, size_t position, const void *elt); + gl_list_node_t (*nx_set_at) (gl_list_t list, size_t position, + const void *elt); gl_list_node_t (*search_from_to) (gl_list_t list, size_t start_index, size_t end_index, const void *elt); size_t (*indexof_from_to) (gl_list_t list, size_t start_index, size_t end_index, const void *elt); - gl_list_node_t (*add_first) (gl_list_t list, const void *elt); - gl_list_node_t (*add_last) (gl_list_t list, const void *elt); - gl_list_node_t (*add_before) (gl_list_t list, gl_list_node_t node, - const void *elt); - gl_list_node_t (*add_after) (gl_list_t list, gl_list_node_t node, + gl_list_node_t (*nx_add_first) (gl_list_t list, const void *elt); + gl_list_node_t (*nx_add_last) (gl_list_t list, const void *elt); + gl_list_node_t (*nx_add_before) (gl_list_t list, gl_list_node_t node, + const void *elt); + gl_list_node_t (*nx_add_after) (gl_list_t list, gl_list_node_t node, + const void *elt); + gl_list_node_t (*nx_add_at) (gl_list_t list, size_t position, const void *elt); - gl_list_node_t (*add_at) (gl_list_t list, size_t position, - const void *elt); bool (*remove_node) (gl_list_t list, gl_list_node_t node); bool (*remove_at) (gl_list_t list, size_t position); bool (*remove_elt) (gl_list_t list, const void *elt); @@ -431,8 +522,8 @@ struct gl_list_implementation gl_listelement_compar_fn compar, size_t start_index, size_t end_index, const void *elt); - gl_list_node_t (*sortedlist_add) (gl_list_t list, - gl_listelement_compar_fn compar, + gl_list_node_t (*sortedlist_nx_add) (gl_list_t list, + gl_listelement_compar_fn compar, const void *elt); bool (*sortedlist_remove) (gl_list_t list, gl_listelement_compar_fn compar, @@ -454,29 +545,31 @@ struct gl_list_impl_base struct gl_list_implementation. Use #define to avoid a warning because of extern vs. static. */ -# define gl_list_create_empty gl_list_create_empty_inline +# define gl_list_nx_create_empty gl_list_nx_create_empty_inline static inline gl_list_t -gl_list_create_empty (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) +gl_list_nx_create_empty (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) { - return implementation->create_empty (implementation, equals_fn, hashcode_fn, - dispose_fn, allow_duplicates); + return implementation->nx_create_empty (implementation, equals_fn, + hashcode_fn, dispose_fn, + allow_duplicates); } -# define gl_list_create gl_list_create_inline +# define gl_list_nx_create gl_list_nx_create_inline static inline gl_list_t -gl_list_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_list_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) { - return implementation->create (implementation, equals_fn, hashcode_fn, - dispose_fn, allow_duplicates, count, contents); + return implementation->nx_create (implementation, equals_fn, hashcode_fn, + dispose_fn, allow_duplicates, count, + contents); } # define gl_list_size gl_list_size_inline @@ -495,12 +588,13 @@ gl_list_node_value (gl_list_t list, gl_list_node_t node) ->node_value (list, node); } -# define gl_list_node_set_value gl_list_node_set_value_inline -static inline void -gl_list_node_set_value (gl_list_t list, gl_list_node_t node, const void *elt) +# define gl_list_node_nx_set_value gl_list_node_nx_set_value_inline +static inline int +gl_list_node_nx_set_value (gl_list_t list, gl_list_node_t node, + const void *elt) { - ((const struct gl_list_impl_base *) list)->vtable - ->node_set_value (list, node, elt); + return ((const struct gl_list_impl_base *) list)->vtable + ->node_nx_set_value (list, node, elt); } # define gl_list_next_node gl_list_next_node_inline @@ -527,12 +621,12 @@ gl_list_get_at (gl_list_t list, size_t position) ->get_at (list, position); } -# define gl_list_set_at gl_list_set_at_inline +# define gl_list_nx_set_at gl_list_nx_set_at_inline static inline gl_list_node_t -gl_list_set_at (gl_list_t list, size_t position, const void *elt) +gl_list_nx_set_at (gl_list_t list, size_t position, const void *elt) { return ((const struct gl_list_impl_base *) list)->vtable - ->set_at (list, position, elt); + ->nx_set_at (list, position, elt); } # define gl_list_search gl_list_search_inline @@ -589,44 +683,44 @@ gl_list_indexof_from_to (gl_list_t list, size_t start_index, size_t end_index, ->indexof_from_to (list, start_index, end_index, elt); } -# define gl_list_add_first gl_list_add_first_inline +# define gl_list_nx_add_first gl_list_nx_add_first_inline static inline gl_list_node_t -gl_list_add_first (gl_list_t list, const void *elt) +gl_list_nx_add_first (gl_list_t list, const void *elt) { return ((const struct gl_list_impl_base *) list)->vtable - ->add_first (list, elt); + ->nx_add_first (list, elt); } -# define gl_list_add_last gl_list_add_last_inline +# define gl_list_nx_add_last gl_list_nx_add_last_inline static inline gl_list_node_t -gl_list_add_last (gl_list_t list, const void *elt) +gl_list_nx_add_last (gl_list_t list, const void *elt) { return ((const struct gl_list_impl_base *) list)->vtable - ->add_last (list, elt); + ->nx_add_last (list, elt); } -# define gl_list_add_before gl_list_add_before_inline +# define gl_list_nx_add_before gl_list_nx_add_before_inline static inline gl_list_node_t -gl_list_add_before (gl_list_t list, gl_list_node_t node, const void *elt) +gl_list_nx_add_before (gl_list_t list, gl_list_node_t node, const void *elt) { return ((const struct gl_list_impl_base *) list)->vtable - ->add_before (list, node, elt); + ->nx_add_before (list, node, elt); } -# define gl_list_add_after gl_list_add_after_inline +# define gl_list_nx_add_after gl_list_nx_add_after_inline static inline gl_list_node_t -gl_list_add_after (gl_list_t list, gl_list_node_t node, const void *elt) +gl_list_nx_add_after (gl_list_t list, gl_list_node_t node, const void *elt) { return ((const struct gl_list_impl_base *) list)->vtable - ->add_after (list, node, elt); + ->nx_add_after (list, node, elt); } -# define gl_list_add_at gl_list_add_at_inline +# define gl_list_nx_add_at gl_list_nx_add_at_inline static inline gl_list_node_t -gl_list_add_at (gl_list_t list, size_t position, const void *elt) +gl_list_nx_add_at (gl_list_t list, size_t position, const void *elt) { return ((const struct gl_list_impl_base *) list)->vtable - ->add_at (list, position, elt); + ->nx_add_at (list, position, elt); } # define gl_list_remove_node gl_list_remove_node_inline @@ -725,12 +819,12 @@ gl_sortedlist_indexof_from_to (gl_list_t list, gl_listelement_compar_fn compar, elt); } -# define gl_sortedlist_add gl_sortedlist_add_inline +# define gl_sortedlist_nx_add gl_sortedlist_nx_add_inline static inline gl_list_node_t -gl_sortedlist_add (gl_list_t list, gl_listelement_compar_fn compar, const void *elt) +gl_sortedlist_nx_add (gl_list_t list, gl_listelement_compar_fn compar, const void *elt) { return ((const struct gl_list_impl_base *) list)->vtable - ->sortedlist_add (list, compar, elt); + ->sortedlist_nx_add (list, compar, elt); } # define gl_sortedlist_remove gl_sortedlist_remove_inline diff --git a/lib/gl_rbtree_list.c b/lib/gl_rbtree_list.c index e584702c5b..79aaaf7d30 100644 --- a/lib/gl_rbtree_list.c +++ b/lib/gl_rbtree_list.c @@ -1,5 +1,5 @@ /* Sequential list data type implemented by a binary tree. - Copyright (C) 2006, 2008 Free Software Foundation, Inc. + Copyright (C) 2006, 2008-2009 Free Software Foundation, Inc. Written by Bruno Haible <bruno@clisp.org>, 2006. This program is free software: you can redistribute it and/or modify @@ -22,16 +22,18 @@ #include <stdlib.h> -#include "xalloc.h" - /* -------------------------- gl_list_t Data Type -------------------------- */ /* Generic red-black tree code. */ #include "gl_anyrbtree_list1.h" -#include "gl_anyrbtree_list2.h" /* Generic binary tree code. */ #include "gl_anytree_list1.h" + +/* Generic red-black tree code. */ +#include "gl_anyrbtree_list2.h" + +/* Generic binary tree code. */ #include "gl_anytree_list2.h" /* For debugging. */ @@ -67,22 +69,22 @@ gl_rbtree_list_check_invariants (gl_list_t list) const struct gl_list_implementation gl_rbtree_list_implementation = { - gl_tree_create_empty, - gl_tree_create, + gl_tree_nx_create_empty, + gl_tree_nx_create, gl_tree_size, gl_tree_node_value, - gl_tree_node_set_value, + gl_tree_node_nx_set_value, gl_tree_next_node, gl_tree_previous_node, gl_tree_get_at, - gl_tree_set_at, + gl_tree_nx_set_at, gl_tree_search_from_to, gl_tree_indexof_from_to, - gl_tree_add_first, - gl_tree_add_last, - gl_tree_add_before, - gl_tree_add_after, - gl_tree_add_at, + gl_tree_nx_add_first, + gl_tree_nx_add_last, + gl_tree_nx_add_before, + gl_tree_nx_add_after, + gl_tree_nx_add_at, gl_tree_remove_node, gl_tree_remove_at, gl_tree_remove, @@ -95,6 +97,6 @@ const struct gl_list_implementation gl_rbtree_list_implementation = gl_tree_sortedlist_search_from_to, gl_tree_sortedlist_indexof, gl_tree_sortedlist_indexof_from_to, - gl_tree_sortedlist_add, + gl_tree_sortedlist_nx_add, gl_tree_sortedlist_remove }; diff --git a/lib/gl_rbtreehash_list.c b/lib/gl_rbtreehash_list.c index 2b21dfa759..38af650858 100644 --- a/lib/gl_rbtreehash_list.c +++ b/lib/gl_rbtreehash_list.c @@ -1,5 +1,5 @@ /* Sequential list data type implemented by a hash table with a binary tree. - Copyright (C) 2006, 2008 Free Software Foundation, Inc. + Copyright (C) 2006, 2008-2009 Free Software Foundation, Inc. Written by Bruno Haible <bruno@clisp.org>, 2006. This program is free software: you can redistribute it and/or modify @@ -24,7 +24,6 @@ #include <stdlib.h> #include "gl_rbtree_oset.h" -#include "xalloc.h" #include "xsize.h" #ifndef uintptr_t @@ -96,22 +95,22 @@ gl_rbtreehash_list_check_invariants (gl_list_t list) const struct gl_list_implementation gl_rbtreehash_list_implementation = { - gl_tree_create_empty, - gl_tree_create, + gl_tree_nx_create_empty, + gl_tree_nx_create, gl_tree_size, gl_tree_node_value, - gl_tree_node_set_value, + gl_tree_node_nx_set_value, gl_tree_next_node, gl_tree_previous_node, gl_tree_get_at, - gl_tree_set_at, + gl_tree_nx_set_at, gl_tree_search_from_to, gl_tree_indexof_from_to, - gl_tree_add_first, - gl_tree_add_last, - gl_tree_add_before, - gl_tree_add_after, - gl_tree_add_at, + gl_tree_nx_add_first, + gl_tree_nx_add_last, + gl_tree_nx_add_before, + gl_tree_nx_add_after, + gl_tree_nx_add_at, gl_tree_remove_node, gl_tree_remove_at, gl_tree_remove, @@ -124,6 +123,6 @@ const struct gl_list_implementation gl_rbtreehash_list_implementation = gl_tree_sortedlist_search_from_to, gl_tree_sortedlist_indexof, gl_tree_sortedlist_indexof_from_to, - gl_tree_sortedlist_add, + gl_tree_sortedlist_nx_add, gl_tree_sortedlist_remove }; diff --git a/lib/gl_sublist.c b/lib/gl_sublist.c index 7970ee772a..09299d56fe 100644 --- a/lib/gl_sublist.c +++ b/lib/gl_sublist.c @@ -1,5 +1,5 @@ /* Sequential list data type backed by another list. - Copyright (C) 2006-2008 Free Software Foundation, Inc. + Copyright (C) 2006-2009 Free Software Foundation, Inc. Written by Bruno Haible <bruno@clisp.org>, 2006. This program is free software: you can redistribute it and/or modify @@ -22,8 +22,6 @@ #include <stdlib.h> -#include "xalloc.h" - #ifndef uintptr_t # define uintptr_t unsigned long #endif @@ -49,23 +47,23 @@ struct gl_list_impl #define NODE_TO_INDEX(node) ((uintptr_t)(node) - 1) static gl_list_t -gl_sublist_create_empty (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) +gl_sublist_nx_create_empty (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) { /* Shouldn't be called. */ abort (); } static gl_list_t -gl_sublist_create_fill (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_sublist_nx_create_fill (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) { /* Shouldn't be called. */ abort (); @@ -87,14 +85,16 @@ gl_sublist_node_value (gl_list_t list, gl_list_node_t node) return gl_list_get_at (list->whole, list->start + index); } -static void -gl_sublist_node_set_value (gl_list_t list, gl_list_node_t node, const void *elt) +static int +gl_sublist_node_nx_set_value (gl_list_t list, gl_list_node_t node, const void *elt) { uintptr_t index = NODE_TO_INDEX (node); if (!(index < list->end - list->start)) /* Invalid argument. */ abort (); - gl_list_set_at (list->whole, list->start + index, elt); + if (gl_list_nx_set_at (list->whole, list->start + index, elt) == NULL) + return -1; + return 0; } static gl_list_node_t @@ -135,12 +135,13 @@ gl_sublist_get_at (gl_list_t list, size_t position) } static gl_list_node_t -gl_sublist_set_at (gl_list_t list, size_t position, const void *elt) +gl_sublist_nx_set_at (gl_list_t list, size_t position, const void *elt) { if (!(position < list->end - list->start)) /* Invalid argument. */ abort (); - gl_list_set_at (list->whole, list->start + position, elt); + if (gl_list_nx_set_at (list->whole, list->start + position, elt) == NULL) + return NULL; return INDEX_TO_NODE (position); } @@ -185,53 +186,58 @@ gl_sublist_indexof_from_to (gl_list_t list, } static gl_list_node_t -gl_sublist_add_first (gl_list_t list, const void *elt) +gl_sublist_nx_add_first (gl_list_t list, const void *elt) { - gl_list_add_at (list->whole, list->start, elt); + if (gl_list_nx_add_at (list->whole, list->start, elt) == NULL) + return NULL; list->end++; return INDEX_TO_NODE (0); } static gl_list_node_t -gl_sublist_add_last (gl_list_t list, const void *elt) +gl_sublist_nx_add_last (gl_list_t list, const void *elt) { - gl_list_add_at (list->whole, list->end, elt); + if (gl_list_nx_add_at (list->whole, list->end, elt) == NULL) + return NULL; list->end++; return INDEX_TO_NODE (list->end - list->start - 1); } static gl_list_node_t -gl_sublist_add_before (gl_list_t list, gl_list_node_t node, const void *elt) +gl_sublist_nx_add_before (gl_list_t list, gl_list_node_t node, const void *elt) { size_t position = NODE_TO_INDEX (node); if (!(position < list->end - list->start)) /* Invalid argument. */ abort (); - gl_list_add_at (list->whole, list->start + position, elt); + if (gl_list_nx_add_at (list->whole, list->start + position, elt) == NULL) + return NULL; list->end++; return INDEX_TO_NODE (position); } static gl_list_node_t -gl_sublist_add_after (gl_list_t list, gl_list_node_t node, const void *elt) +gl_sublist_nx_add_after (gl_list_t list, gl_list_node_t node, const void *elt) { size_t position = NODE_TO_INDEX (node); if (!(position < list->end - list->start)) /* Invalid argument. */ abort (); position++; - gl_list_add_at (list->whole, list->start + position, elt); + if (gl_list_nx_add_at (list->whole, list->start + position, elt) == NULL) + return NULL; list->end++; return INDEX_TO_NODE (position); } static gl_list_node_t -gl_sublist_add_at (gl_list_t list, size_t position, const void *elt) +gl_sublist_nx_add_at (gl_list_t list, size_t position, const void *elt) { if (!(position <= list->end - list->start)) /* Invalid argument. */ abort (); - gl_list_add_at (list->whole, list->start + position, elt); + if (gl_list_nx_add_at (list->whole, list->start + position, elt) == NULL) + return NULL; list->end++; return INDEX_TO_NODE (position); } @@ -378,9 +384,9 @@ gl_sublist_sortedlist_indexof_from_to (gl_list_t list, } static gl_list_node_t -gl_sublist_sortedlist_add (gl_list_t list, - gl_listelement_compar_fn compar, - const void *elt) +gl_sublist_sortedlist_nx_add (gl_list_t list, + gl_listelement_compar_fn compar, + const void *elt) { /* It's impossible to implement this method without risking to put the whole list into unsorted order (namely, when the given ELT is smaller @@ -403,22 +409,22 @@ gl_sublist_sortedlist_remove (gl_list_t list, static const struct gl_list_implementation gl_sublist_list_implementation = { - gl_sublist_create_empty, - gl_sublist_create_fill, + gl_sublist_nx_create_empty, + gl_sublist_nx_create_fill, gl_sublist_size, gl_sublist_node_value, - gl_sublist_node_set_value, + gl_sublist_node_nx_set_value, gl_sublist_next_node, gl_sublist_previous_node, gl_sublist_get_at, - gl_sublist_set_at, + gl_sublist_nx_set_at, gl_sublist_search_from_to, gl_sublist_indexof_from_to, - gl_sublist_add_first, - gl_sublist_add_last, - gl_sublist_add_before, - gl_sublist_add_after, - gl_sublist_add_at, + gl_sublist_nx_add_first, + gl_sublist_nx_add_last, + gl_sublist_nx_add_before, + gl_sublist_nx_add_after, + gl_sublist_nx_add_at, gl_sublist_remove_node, gl_sublist_remove_at, gl_sublist_remove, @@ -431,18 +437,22 @@ static const struct gl_list_implementation gl_sublist_list_implementation = gl_sublist_sortedlist_search_from_to, gl_sublist_sortedlist_indexof, gl_sublist_sortedlist_indexof_from_to, - gl_sublist_sortedlist_add, + gl_sublist_sortedlist_nx_add, gl_sublist_sortedlist_remove }; gl_list_t -gl_sublist_create (gl_list_t whole_list, size_t start_index, size_t end_index) +gl_sublist_nx_create (gl_list_t whole_list, size_t start_index, size_t end_index) { if (!(start_index <= end_index && end_index <= gl_list_size (whole_list))) /* Invalid arguments. */ abort (); { - 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 = &gl_sublist_list_implementation; list->base.equals_fn = whole_list->base.equals_fn; /* actually unused */ diff --git a/lib/gl_sublist.h b/lib/gl_sublist.h index bd3539ecd1..0daa027d40 100644 --- a/lib/gl_sublist.h +++ b/lib/gl_sublist.h @@ -1,5 +1,5 @@ /* Sequential list data type backed by another list. - Copyright (C) 2006 Free Software Foundation, Inc. + Copyright (C) 2006, 2009 Free Software Foundation, Inc. Written by Bruno Haible <bruno@clisp.org>, 2006. This program is free software: you can redistribute it and/or modify @@ -33,8 +33,13 @@ extern "C" { - The sublist is only valid as long as the whole list is valid. - The sublist must not be passed to the gl_list_sortedlist_add() function. */ +#if 0 /* declared in gl_xsublist.h */ extern gl_list_t gl_sublist_create (gl_list_t whole_list, size_t start_index, size_t end_index); +#endif +/* Likewise. Return NULL upon out-of-memory. */ +extern gl_list_t gl_sublist_nx_create (gl_list_t whole_list, + size_t start_index, size_t end_index); #ifdef __cplusplus diff --git a/lib/gl_xlist.c b/lib/gl_xlist.c new file mode 100644 index 0000000000..61018b700e --- /dev/null +++ b/lib/gl_xlist.c @@ -0,0 +1,128 @@ +/* Abstract sequential list data type, with out-of-memory checking. + Copyright (C) 2009 Free Software Foundation, Inc. + Written by Bruno Haible <bruno@clisp.org>, 2009. + + 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 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 + MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the + 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, see <http://www.gnu.org/licenses/>. */ + +#include <config.h> + +/* Specification. */ +#include "gl_xlist.h" + +#if !HAVE_INLINE + +gl_list_t +gl_list_create_empty (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) +{ + gl_list_t result = + gl_list_nx_create_empty (implementation, equals_fn, hashcode_fn, dispose_fn, + allow_duplicates); + if (result == NULL) + xalloc_die (); + return result; +} + +gl_list_t +gl_list_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_list_t result = + gl_list_nx_create (implementation, equals_fn, hashcode_fn, dispose_fn, + allow_duplicates, count, contents); + if (result == NULL) + xalloc_die (); + return result; +} + +void +gl_list_node_set_value (gl_list_t list, gl_list_node_t node, const void *elt) +{ + int result = gl_list_node_nx_set_value (list, node, elt); + if (result < 0) + xalloc_die (); +} + +gl_list_node_t +gl_list_set_at (gl_list_t list, size_t position, const void *elt) +{ + gl_list_node_t result = gl_list_nx_set_at (list, position, elt); + if (result == NULL) + xalloc_die (); + return result; +} + +gl_list_node_t +gl_list_add_first (gl_list_t list, const void *elt) +{ + gl_list_node_t result = gl_list_nx_add_first (list, elt); + if (result == NULL) + xalloc_die (); + return result; +} + +gl_list_node_t +gl_list_add_last (gl_list_t list, const void *elt) +{ + gl_list_node_t result = gl_list_nx_add_last (list, elt); + if (result == NULL) + xalloc_die (); + return result; +} + +gl_list_node_t +gl_list_add_before (gl_list_t list, gl_list_node_t node, const void *elt) +{ + gl_list_node_t result = gl_list_nx_add_before (list, node, elt); + if (result == NULL) + xalloc_die (); + return result; +} + +gl_list_node_t +gl_list_add_after (gl_list_t list, gl_list_node_t node, const void *elt) +{ + gl_list_node_t result = gl_list_nx_add_after (list, node, elt); + if (result == NULL) + xalloc_die (); + return result; +} + +gl_list_node_t +gl_list_add_at (gl_list_t list, size_t position, const void *elt) +{ + gl_list_node_t result = gl_list_nx_add_at (list, position, elt); + if (result == NULL) + xalloc_die (); + return result; +} + +gl_list_node_t +gl_sortedlist_add (gl_list_t list, gl_listelement_compar_fn compar, + const void *elt) +{ + gl_list_node_t result = gl_sortedlist_nx_add (list, compar, elt); + if (result == NULL) + xalloc_die (); + return result; +} + +#endif diff --git a/lib/gl_xlist.h b/lib/gl_xlist.h new file mode 100644 index 0000000000..4c901be4b7 --- /dev/null +++ b/lib/gl_xlist.h @@ -0,0 +1,179 @@ +/* Abstract sequential list data type, with out-of-memory checking. + Copyright (C) 2009 Free Software Foundation, Inc. + Written by Bruno Haible <bruno@clisp.org>, 2009. + + 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 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 + MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the + 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, see <http://www.gnu.org/licenses/>. */ + +#ifndef _GL_XLIST_H +#define _GL_XLIST_H + +#include "gl_list.h" +#include "xalloc.h" + +#ifdef __cplusplus +extern "C" { +#endif + +/* These functions are thin wrappers around the corresponding functions with + _nx_ infix from gl_list.h. Upon out-of-memory, they invoke xalloc_die (), + instead of returning an error indicator. */ +extern gl_list_t gl_list_create_empty (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); +extern gl_list_t gl_list_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); +extern void gl_list_node_set_value (gl_list_t list, gl_list_node_t node, + const void *elt); +extern gl_list_node_t gl_list_set_at (gl_list_t list, size_t position, + const void *elt); +extern gl_list_node_t gl_list_add_first (gl_list_t list, const void *elt); +extern gl_list_node_t gl_list_add_last (gl_list_t list, const void *elt); +extern gl_list_node_t gl_list_add_before (gl_list_t list, gl_list_node_t node, + const void *elt); +extern gl_list_node_t gl_list_add_after (gl_list_t list, gl_list_node_t node, + const void *elt); +extern gl_list_node_t gl_list_add_at (gl_list_t list, size_t position, + const void *elt); +extern gl_list_node_t gl_sortedlist_add (gl_list_t list, + gl_listelement_compar_fn compar, + const void *elt); + +#if HAVE_INLINE + +# define gl_list_create_empty gl_list_create_empty_inline +static inline gl_list_t +gl_list_create_empty (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) +{ + gl_list_t result = + gl_list_nx_create_empty (implementation, equals_fn, hashcode_fn, dispose_fn, + allow_duplicates); + if (result == NULL) + xalloc_die (); + return result; +} + +# define gl_list_create gl_list_create_inline +static inline gl_list_t +gl_list_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_list_t result = + gl_list_nx_create (implementation, equals_fn, hashcode_fn, dispose_fn, + allow_duplicates, count, contents); + if (result == NULL) + xalloc_die (); + return result; +} + +# define gl_list_node_set_value gl_list_node_set_value_inline +static inline void +gl_list_node_set_value (gl_list_t list, gl_list_node_t node, const void *elt) +{ + int result = gl_list_node_nx_set_value (list, node, elt); + if (result < 0) + xalloc_die (); +} + +# define gl_list_set_at gl_list_set_at_inline +static inline gl_list_node_t +gl_list_set_at (gl_list_t list, size_t position, const void *elt) +{ + gl_list_node_t result = gl_list_nx_set_at (list, position, elt); + if (result == NULL) + xalloc_die (); + return result; +} + +# define gl_list_add_first gl_list_add_first_inline +static inline gl_list_node_t +gl_list_add_first (gl_list_t list, const void *elt) +{ + gl_list_node_t result = gl_list_nx_add_first (list, elt); + if (result == NULL) + xalloc_die (); + return result; +} + +# define gl_list_add_last gl_list_add_last_inline +static inline gl_list_node_t +gl_list_add_last (gl_list_t list, const void *elt) +{ + gl_list_node_t result = gl_list_nx_add_last (list, elt); + if (result == NULL) + xalloc_die (); + return result; +} + +# define gl_list_add_before gl_list_add_before_inline +static inline gl_list_node_t +gl_list_add_before (gl_list_t list, gl_list_node_t node, const void *elt) +{ + gl_list_node_t result = gl_list_nx_add_before (list, node, elt); + if (result == NULL) + xalloc_die (); + return result; +} + +# define gl_list_add_after gl_list_add_after_inline +static inline gl_list_node_t +gl_list_add_after (gl_list_t list, gl_list_node_t node, const void *elt) +{ + gl_list_node_t result = gl_list_nx_add_after (list, node, elt); + if (result == NULL) + xalloc_die (); + return result; +} + +# define gl_list_add_at gl_list_add_at_inline +static inline gl_list_node_t +gl_list_add_at (gl_list_t list, size_t position, const void *elt) +{ + gl_list_node_t result = gl_list_nx_add_at (list, position, elt); + if (result == NULL) + xalloc_die (); + return result; +} + +# define gl_sortedlist_add gl_sortedlist_add_inline +static inline gl_list_node_t +gl_sortedlist_add (gl_list_t list, gl_listelement_compar_fn compar, + const void *elt) +{ + gl_list_node_t result = gl_sortedlist_nx_add (list, compar, elt); + if (result == NULL) + xalloc_die (); + return result; +} + +#endif + +#ifdef __cplusplus +} +#endif + +#endif /* _GL_XLIST_H */ diff --git a/lib/gl_xsublist.c b/lib/gl_xsublist.c new file mode 100644 index 0000000000..1a11f362fb --- /dev/null +++ b/lib/gl_xsublist.c @@ -0,0 +1,35 @@ +/* Sequential list data type backed by another list, with out-of-memory + checking. + Copyright (C) 2009 Free Software Foundation, Inc. + Written by Bruno Haible <bruno@clisp.org>, 2009. + + 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 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 + MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the + 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, see <http://www.gnu.org/licenses/>. */ + +#include <config.h> + +/* Specification. */ +#include "gl_xsublist.h" + +#if !HAVE_INLINE + +gl_list_t +gl_sublist_create (gl_list_t whole_list, size_t start_index, size_t end_index) +{ + gl_list_t result = gl_sublist_nx_create (whole_list, start_index, end_index); + if (result == NULL) + xalloc_die (); + return result; +} + +#endif diff --git a/lib/gl_xsublist.h b/lib/gl_xsublist.h new file mode 100644 index 0000000000..42b5d8e2d0 --- /dev/null +++ b/lib/gl_xsublist.h @@ -0,0 +1,53 @@ +/* Sequential list data type backed by another list, with out-of-memory + checking. + Copyright (C) 2009 Free Software Foundation, Inc. + Written by Bruno Haible <bruno@clisp.org>, 2009. + + 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 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 + MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the + 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, see <http://www.gnu.org/licenses/>. */ + +#ifndef _GL_XSUBLIST_H +#define _GL_XSUBLIST_H + +#include "gl_sublist.h" +#include "xalloc.h" + +#ifdef __cplusplus +extern "C" { +#endif + +/* These functions are thin wrappers around the corresponding functions with + _nx_ infix from gl_sublist.h. Upon out-of-memory, they invoke + xalloc_die (), instead of returning an error indicator. */ +extern gl_list_t gl_sublist_create (gl_list_t whole_list, + size_t start_index, size_t end_index); + +#if HAVE_INLINE + +# define gl_sublist_create gl_sublist_create_inline +static inline gl_list_t +gl_sublist_create (gl_list_t whole_list, size_t start_index, size_t end_index) +{ + gl_list_t result = gl_sublist_nx_create (whole_list, start_index, end_index); + if (result == NULL) + xalloc_die (); + return result; +} + +#endif + +#ifdef __cplusplus +} +#endif + +#endif /* _GL_XSUBLIST_H */ diff --git a/modules/array-list b/modules/array-list index 946789ca70..9d6e2b9fc8 100644 --- a/modules/array-list +++ b/modules/array-list @@ -7,7 +7,6 @@ lib/gl_array_list.c Depends-on: list -xalloc xsize configure.ac: diff --git a/modules/array-list-tests b/modules/array-list-tests index 6109216499..83dc54c43b 100644 --- a/modules/array-list-tests +++ b/modules/array-list-tests @@ -9,5 +9,4 @@ configure.ac: Makefile.am: TESTS += test-array_list check_PROGRAMS += test-array_list -test_array_list_LDADD = $(LDADD) @LIBINTL@ diff --git a/modules/array-oset-tests b/modules/array-oset-tests index 3fd51ccd85..89f071d4b7 100644 --- a/modules/array-oset-tests +++ b/modules/array-oset-tests @@ -2,6 +2,7 @@ Files: tests/test-array_oset.c Depends-on: +xlist array-list progname diff --git a/modules/avltree-list b/modules/avltree-list index 7ef1413b9a..90a42fda6b 100644 --- a/modules/avltree-list +++ b/modules/avltree-list @@ -11,7 +11,6 @@ lib/gl_anytree_list2.h Depends-on: list -xalloc configure.ac: diff --git a/modules/avltree-list-tests b/modules/avltree-list-tests index c8c60f4f5a..c87eda30b6 100644 --- a/modules/avltree-list-tests +++ b/modules/avltree-list-tests @@ -10,4 +10,3 @@ configure.ac: Makefile.am: TESTS += test-avltree_list check_PROGRAMS += test-avltree_list -test_avltree_list_LDADD = $(LDADD) @LIBINTL@ diff --git a/modules/avltreehash-list b/modules/avltreehash-list index 004267298a..4c5622cc95 100644 --- a/modules/avltreehash-list +++ b/modules/avltreehash-list @@ -17,7 +17,6 @@ Depends-on: list avltree-oset stdint -xalloc xsize configure.ac: diff --git a/modules/avltreehash-list-tests b/modules/avltreehash-list-tests index 54245a8138..dd013d2121 100644 --- a/modules/avltreehash-list-tests +++ b/modules/avltreehash-list-tests @@ -10,5 +10,4 @@ configure.ac: Makefile.am: TESTS += test-avltreehash_list check_PROGRAMS += test-avltreehash_list -test_avltreehash_list_LDADD = $(LDADD) @LIBINTL@ diff --git a/modules/carray-list b/modules/carray-list index 70581fcbec..3b88d83d7c 100644 --- a/modules/carray-list +++ b/modules/carray-list @@ -7,7 +7,6 @@ lib/gl_carray_list.c Depends-on: list -xalloc xsize configure.ac: diff --git a/modules/carray-list-tests b/modules/carray-list-tests index 082862cb5e..82e7b7894b 100644 --- a/modules/carray-list-tests +++ b/modules/carray-list-tests @@ -10,5 +10,4 @@ configure.ac: Makefile.am: TESTS += test-carray_list check_PROGRAMS += test-carray_list -test_carray_list_LDADD = $(LDADD) @LIBINTL@ diff --git a/modules/clean-temp b/modules/clean-temp index b16a33e5d3..d4afa34612 100644 --- a/modules/clean-temp +++ b/modules/clean-temp @@ -18,6 +18,7 @@ rmdir xalloc xmalloca linkedhash-list +xlist gettext-h configure.ac: diff --git a/modules/git-merge-changelog b/modules/git-merge-changelog index 732324e2ab..94d584e2eb 100644 --- a/modules/git-merge-changelog +++ b/modules/git-merge-changelog @@ -10,7 +10,7 @@ stdbool progname error read-file -list +xlist array-list linkedhash-list linked-list diff --git a/modules/linked-list b/modules/linked-list index 02dd55a3a8..1c66585e80 100644 --- a/modules/linked-list +++ b/modules/linked-list @@ -9,7 +9,6 @@ lib/gl_anylinked_list2.h Depends-on: list -xalloc configure.ac: diff --git a/modules/linked-list-tests b/modules/linked-list-tests index 3b37c2b06b..fca22a6a1b 100644 --- a/modules/linked-list-tests +++ b/modules/linked-list-tests @@ -10,4 +10,3 @@ configure.ac: Makefile.am: TESTS += test-linked_list check_PROGRAMS += test-linked_list -test_linked_list_LDADD = $(LDADD) @LIBINTL@ diff --git a/modules/linkedhash-list b/modules/linkedhash-list index 5449ac59ac..16bc79f1d4 100644 --- a/modules/linkedhash-list +++ b/modules/linkedhash-list @@ -12,7 +12,6 @@ lib/gl_anylinked_list2.h Depends-on: list stdint -xalloc xsize configure.ac: diff --git a/modules/linkedhash-list-tests b/modules/linkedhash-list-tests index baf80e5630..4f13d9aa7a 100644 --- a/modules/linkedhash-list-tests +++ b/modules/linkedhash-list-tests @@ -10,4 +10,3 @@ configure.ac: Makefile.am: TESTS += test-linkedhash_list check_PROGRAMS += test-linkedhash_list -test_linkedhash_list_LDADD = $(LDADD) @LIBINTL@ diff --git a/modules/rbtree-list b/modules/rbtree-list index ea75a6a24e..4ea7796f3a 100644 --- a/modules/rbtree-list +++ b/modules/rbtree-list @@ -11,7 +11,6 @@ lib/gl_anytree_list2.h Depends-on: list -xalloc configure.ac: diff --git a/modules/rbtree-list-tests b/modules/rbtree-list-tests index 3d909e274e..2cd042e102 100644 --- a/modules/rbtree-list-tests +++ b/modules/rbtree-list-tests @@ -10,4 +10,3 @@ configure.ac: Makefile.am: TESTS += test-rbtree_list check_PROGRAMS += test-rbtree_list -test_rbtree_list_LDADD = $(LDADD) @LIBINTL@ diff --git a/modules/rbtreehash-list b/modules/rbtreehash-list index 79049099f0..7355e8bc73 100644 --- a/modules/rbtreehash-list +++ b/modules/rbtreehash-list @@ -17,7 +17,6 @@ Depends-on: list rbtree-oset stdint -xalloc xsize configure.ac: diff --git a/modules/rbtreehash-list-tests b/modules/rbtreehash-list-tests index c7b8704301..2d17f01f09 100644 --- a/modules/rbtreehash-list-tests +++ b/modules/rbtreehash-list-tests @@ -10,4 +10,3 @@ configure.ac: Makefile.am: TESTS += test-rbtreehash_list check_PROGRAMS += test-rbtreehash_list -test_rbtreehash_list_LDADD = $(LDADD) @LIBINTL@ diff --git a/modules/sublist b/modules/sublist index e8e3d9873a..7b0ddcb04d 100644 --- a/modules/sublist +++ b/modules/sublist @@ -7,7 +7,6 @@ lib/gl_sublist.c Depends-on: list -xalloc configure.ac: diff --git a/modules/xlist b/modules/xlist new file mode 100644 index 0000000000..4bac28fef6 --- /dev/null +++ b/modules/xlist @@ -0,0 +1,27 @@ +Description: +Abstract sequential list data type, with out-of-memory checking. + +Files: +lib/gl_xlist.h +lib/gl_xlist.c +m4/gl_list.m4 + +Depends-on: +inline +stdbool +xalloc-die + +configure.ac: +gl_LIST + +Makefile.am: +lib_SOURCES += gl_xlist.h gl_xlist.c + +Include: +"gl_xlist.h" + +License: +GPL + +Maintainer: +Bruno Haible diff --git a/modules/xsublist b/modules/xsublist new file mode 100644 index 0000000000..e3b7cf85b5 --- /dev/null +++ b/modules/xsublist @@ -0,0 +1,24 @@ +Description: +Sequential list data type backed by another list, with out-of-memory checking. + +Files: +lib/gl_xsublist.h +lib/gl_xsublist.c + +Depends-on: +sublist +xalloc-die + +configure.ac: + +Makefile.am: +lib_SOURCES += gl_xsublist.h gl_xsublist.c + +Include: +"gl_xsublist.h" + +License: +GPL + +Maintainer: +Bruno Haible diff --git a/tests/test-array_list.c b/tests/test-array_list.c index 48619e4fe4..2f33d4c573 100644 --- a/tests/test-array_list.c +++ b/tests/test-array_list.c @@ -1,5 +1,5 @@ /* Test of sequential list data type implementation. - Copyright (C) 2006-2008 Free Software Foundation, Inc. + Copyright (C) 2006-2009 Free Software Foundation, Inc. Written by Bruno Haible <bruno@clisp.org>, 2007. This program is free software: you can redistribute it and/or modify @@ -79,12 +79,14 @@ main (int argc, char *argv[]) contents[i] = RANDOM_OBJECT (); /* Create list1. */ - list1 = gl_list_create (GL_ARRAY_LIST, NULL, NULL, NULL, true, - initial_size, contents); + list1 = gl_list_nx_create (GL_ARRAY_LIST, NULL, NULL, NULL, true, + initial_size, contents); + ASSERT (list1 != NULL); /* Create list2. */ - list2 = gl_list_create_empty (GL_ARRAY_LIST, NULL, NULL, NULL, true); + list2 = gl_list_nx_create_empty (GL_ARRAY_LIST, NULL, NULL, NULL, true); + ASSERT (list2 != NULL); for (i = 0; i < initial_size; i++) - gl_list_add_last (list2, contents[i]); + ASSERT (gl_list_nx_add_last (list2, contents[i]) != NULL); check_equals (list1, list2); @@ -100,11 +102,13 @@ main (int argc, char *argv[]) const char *obj = RANDOM_OBJECT (); gl_list_node_t node1, node2; - node1 = gl_list_set_at (list1, index, obj); + node1 = gl_list_nx_set_at (list1, index, obj); + ASSERT (node1 != NULL); ASSERT (gl_list_get_at (list1, index) == obj); ASSERT (gl_list_node_value (list1, node1) == obj); - node2 = gl_list_set_at (list2, index, obj); + node2 = gl_list_nx_set_at (list2, index, obj); + ASSERT (node2 != NULL); ASSERT (gl_list_get_at (list2, index) == obj); ASSERT (gl_list_node_value (list2, node2) == obj); @@ -161,8 +165,10 @@ main (int argc, char *argv[]) { const char *obj = RANDOM_OBJECT (); gl_list_node_t node1, node2; - node1 = gl_list_add_first (list1, obj); - node2 = gl_list_add_first (list2, obj); + node1 = gl_list_nx_add_first (list1, obj); + ASSERT (node1 != NULL); + node2 = gl_list_nx_add_first (list2, obj); + ASSERT (node2 != NULL); ASSERT (gl_list_node_value (list1, node1) == obj); ASSERT (gl_list_node_value (list2, node2) == obj); ASSERT (gl_list_get_at (list1, 0) == obj); @@ -173,8 +179,10 @@ main (int argc, char *argv[]) { const char *obj = RANDOM_OBJECT (); gl_list_node_t node1, node2; - node1 = gl_list_add_last (list1, obj); - node2 = gl_list_add_last (list2, obj); + node1 = gl_list_nx_add_last (list1, obj); + ASSERT (node1 != NULL); + node2 = gl_list_nx_add_last (list2, obj); + ASSERT (node2 != NULL); ASSERT (gl_list_node_value (list1, node1) == obj); ASSERT (gl_list_node_value (list2, node2) == obj); ASSERT (gl_list_get_at (list1, gl_list_size (list1) - 1) == obj); @@ -187,12 +195,18 @@ main (int argc, char *argv[]) const char *obj1 = RANDOM_OBJECT (); const char *obj2 = RANDOM_OBJECT (); gl_list_node_t node1, node2; - node1 = gl_list_add_first (list1, obj2); - node1 = gl_list_add_before (list1, node1, obj0); - node1 = gl_list_add_after (list1, node1, obj1); - node2 = gl_list_add_first (list2, obj2); - node2 = gl_list_add_before (list2, node2, obj0); - node2 = gl_list_add_after (list2, node2, obj1); + node1 = gl_list_nx_add_first (list1, obj2); + ASSERT (node1 != NULL); + node1 = gl_list_nx_add_before (list1, node1, obj0); + ASSERT (node1 != NULL); + node1 = gl_list_nx_add_after (list1, node1, obj1); + ASSERT (node1 != NULL); + node2 = gl_list_nx_add_first (list2, obj2); + ASSERT (node2 != NULL); + node2 = gl_list_nx_add_before (list2, node2, obj0); + ASSERT (node2 != NULL); + node2 = gl_list_nx_add_after (list2, node2, obj1); + ASSERT (node2 != NULL); ASSERT (gl_list_node_value (list1, node1) == obj1); ASSERT (gl_list_node_value (list2, node2) == obj1); ASSERT (gl_list_get_at (list1, 0) == obj0); @@ -208,8 +222,10 @@ main (int argc, char *argv[]) size_t index = RANDOM (gl_list_size (list1) + 1); const char *obj = RANDOM_OBJECT (); gl_list_node_t node1, node2; - node1 = gl_list_add_at (list1, index, obj); - node2 = gl_list_add_at (list2, index, obj); + node1 = gl_list_nx_add_at (list1, index, obj); + ASSERT (node1 != NULL); + node2 = gl_list_nx_add_at (list2, index, obj); + ASSERT (node2 != NULL); ASSERT (gl_list_get_at (list1, index) == obj); ASSERT (gl_list_node_value (list1, node1) == obj); ASSERT (gl_list_get_at (list2, index) == obj); diff --git a/tests/test-array_oset.c b/tests/test-array_oset.c index 20025305c6..f79d1620bb 100644 --- a/tests/test-array_oset.c +++ b/tests/test-array_oset.c @@ -23,6 +23,7 @@ #include <stdlib.h> #include <string.h> +#include "gl_xlist.h" #include "gl_array_list.h" #include "progname.h" diff --git a/tests/test-avltree_list.c b/tests/test-avltree_list.c index af18059c70..4047ff64ac 100644 --- a/tests/test-avltree_list.c +++ b/tests/test-avltree_list.c @@ -91,16 +91,19 @@ main (int argc, char *argv[]) contents[i] = RANDOM_OBJECT (); /* Create list1. */ - list1 = gl_list_create (GL_ARRAY_LIST, NULL, NULL, NULL, true, - initial_size, contents); + list1 = gl_list_nx_create (GL_ARRAY_LIST, NULL, NULL, NULL, true, + initial_size, contents); + ASSERT (list1 != NULL); /* Create list2. */ - list2 = gl_list_create_empty (GL_AVLTREE_LIST, NULL, NULL, NULL, true); + list2 = gl_list_nx_create_empty (GL_AVLTREE_LIST, NULL, NULL, NULL, true); + ASSERT (list2 != NULL); for (i = 0; i < initial_size; i++) - gl_list_add_last (list2, contents[i]); + ASSERT (gl_list_nx_add_last (list2, contents[i]) != NULL); /* Create list3. */ - list3 = gl_list_create (GL_AVLTREE_LIST, NULL, NULL, NULL, true, - initial_size, contents); + list3 = gl_list_nx_create (GL_AVLTREE_LIST, NULL, NULL, NULL, true, + initial_size, contents); + ASSERT (list3 != NULL); check_all (list1, list2, list3); @@ -116,15 +119,18 @@ main (int argc, char *argv[]) const char *obj = RANDOM_OBJECT (); gl_list_node_t node1, node2, node3; - node1 = gl_list_set_at (list1, index, obj); + node1 = gl_list_nx_set_at (list1, index, obj); + ASSERT (node1 != NULL); ASSERT (gl_list_get_at (list1, index) == obj); ASSERT (gl_list_node_value (list1, node1) == obj); - node2 = gl_list_set_at (list2, index, obj); + node2 = gl_list_nx_set_at (list2, index, obj); + ASSERT (node2 != NULL); ASSERT (gl_list_get_at (list2, index) == obj); ASSERT (gl_list_node_value (list2, node2) == obj); - node3 = gl_list_set_at (list3, index, obj); + node3 = gl_list_nx_set_at (list3, index, obj); + ASSERT (node3 != NULL); ASSERT (gl_list_get_at (list3, index) == obj); ASSERT (gl_list_node_value (list3, node3) == obj); @@ -198,9 +204,12 @@ main (int argc, char *argv[]) { const char *obj = RANDOM_OBJECT (); gl_list_node_t node1, node2, node3; - node1 = gl_list_add_first (list1, obj); - node2 = gl_list_add_first (list2, obj); - node3 = gl_list_add_first (list3, obj); + node1 = gl_list_nx_add_first (list1, obj); + ASSERT (node1 != NULL); + node2 = gl_list_nx_add_first (list2, obj); + ASSERT (node2 != NULL); + node3 = gl_list_nx_add_first (list3, obj); + ASSERT (node3 != NULL); ASSERT (gl_list_node_value (list1, node1) == obj); ASSERT (gl_list_node_value (list2, node2) == obj); ASSERT (gl_list_node_value (list3, node3) == obj); @@ -213,9 +222,12 @@ main (int argc, char *argv[]) { const char *obj = RANDOM_OBJECT (); gl_list_node_t node1, node2, node3; - node1 = gl_list_add_last (list1, obj); - node2 = gl_list_add_last (list2, obj); - node3 = gl_list_add_last (list3, obj); + node1 = gl_list_nx_add_last (list1, obj); + ASSERT (node1 != NULL); + node2 = gl_list_nx_add_last (list2, obj); + ASSERT (node2 != NULL); + node3 = gl_list_nx_add_last (list3, obj); + ASSERT (node3 != NULL); ASSERT (gl_list_node_value (list1, node1) == obj); ASSERT (gl_list_node_value (list2, node2) == obj); ASSERT (gl_list_node_value (list3, node3) == obj); @@ -230,15 +242,24 @@ main (int argc, char *argv[]) const char *obj1 = RANDOM_OBJECT (); const char *obj2 = RANDOM_OBJECT (); gl_list_node_t node1, node2, node3; - node1 = gl_list_add_first (list1, obj2); - node1 = gl_list_add_before (list1, node1, obj0); - node1 = gl_list_add_after (list1, node1, obj1); - node2 = gl_list_add_first (list2, obj2); - node2 = gl_list_add_before (list2, node2, obj0); - node2 = gl_list_add_after (list2, node2, obj1); - node3 = gl_list_add_first (list3, obj2); - node3 = gl_list_add_before (list3, node3, obj0); - node3 = gl_list_add_after (list3, node3, obj1); + node1 = gl_list_nx_add_first (list1, obj2); + ASSERT (node1 != NULL); + node1 = gl_list_nx_add_before (list1, node1, obj0); + ASSERT (node1 != NULL); + node1 = gl_list_nx_add_after (list1, node1, obj1); + ASSERT (node1 != NULL); + node2 = gl_list_nx_add_first (list2, obj2); + ASSERT (node2 != NULL); + node2 = gl_list_nx_add_before (list2, node2, obj0); + ASSERT (node2 != NULL); + node2 = gl_list_nx_add_after (list2, node2, obj1); + ASSERT (node2 != NULL); + node3 = gl_list_nx_add_first (list3, obj2); + ASSERT (node3 != NULL); + node3 = gl_list_nx_add_before (list3, node3, obj0); + ASSERT (node3 != NULL); + node3 = gl_list_nx_add_after (list3, node3, obj1); + ASSERT (node3 != NULL); ASSERT (gl_list_node_value (list1, node1) == obj1); ASSERT (gl_list_node_value (list2, node2) == obj1); ASSERT (gl_list_node_value (list3, node3) == obj1); @@ -258,9 +279,12 @@ main (int argc, char *argv[]) size_t index = RANDOM (gl_list_size (list1) + 1); const char *obj = RANDOM_OBJECT (); gl_list_node_t node1, node2, node3; - node1 = gl_list_add_at (list1, index, obj); - node2 = gl_list_add_at (list2, index, obj); - node3 = gl_list_add_at (list3, index, obj); + node1 = gl_list_nx_add_at (list1, index, obj); + ASSERT (node1 != NULL); + node2 = gl_list_nx_add_at (list2, index, obj); + ASSERT (node2 != NULL); + node3 = gl_list_nx_add_at (list3, index, obj); + ASSERT (node3 != NULL); ASSERT (gl_list_get_at (list1, index) == obj); ASSERT (gl_list_node_value (list1, node1) == obj); ASSERT (gl_list_get_at (list2, index) == obj); diff --git a/tests/test-avltreehash_list.c b/tests/test-avltreehash_list.c index cea8519b6a..12a716ade6 100644 --- a/tests/test-avltreehash_list.c +++ b/tests/test-avltreehash_list.c @@ -1,5 +1,5 @@ /* Test of sequential list data type implementation. - Copyright (C) 2006-2008 Free Software Foundation, Inc. + Copyright (C) 2006-2009 Free Software Foundation, Inc. Written by Bruno Haible <bruno@clisp.org>, 2006. This program is free software: you can redistribute it and/or modify @@ -118,19 +118,22 @@ main (int argc, char *argv[]) contents[i] = RANDOM_OBJECT (); /* Create list1. */ - list1 = gl_list_create (GL_ARRAY_LIST, - string_equals, string_hash, NULL, true, - initial_size, contents); + list1 = gl_list_nx_create (GL_ARRAY_LIST, + string_equals, string_hash, NULL, true, + initial_size, contents); + ASSERT (list1 != NULL); /* Create list2. */ - list2 = gl_list_create_empty (GL_AVLTREEHASH_LIST, - string_equals, string_hash, NULL, true); + list2 = gl_list_nx_create_empty (GL_AVLTREEHASH_LIST, + string_equals, string_hash, NULL, true); + ASSERT (list2 != NULL); for (i = 0; i < initial_size; i++) - gl_list_add_last (list2, contents[i]); + ASSERT (gl_list_nx_add_last (list2, contents[i]) != NULL); /* Create list3. */ - list3 = gl_list_create (GL_AVLTREEHASH_LIST, - string_equals, string_hash, NULL, true, - initial_size, contents); + list3 = gl_list_nx_create (GL_AVLTREEHASH_LIST, + string_equals, string_hash, NULL, true, + initial_size, contents); + ASSERT (list3 != NULL); check_all (list1, list2, list3); @@ -146,15 +149,18 @@ main (int argc, char *argv[]) const char *obj = RANDOM_OBJECT (); gl_list_node_t node1, node2, node3; - node1 = gl_list_set_at (list1, index, obj); + node1 = gl_list_nx_set_at (list1, index, obj); + ASSERT (node1 != NULL); ASSERT (gl_list_get_at (list1, index) == obj); ASSERT (gl_list_node_value (list1, node1) == obj); - node2 = gl_list_set_at (list2, index, obj); + node2 = gl_list_nx_set_at (list2, index, obj); + ASSERT (node2 != NULL); ASSERT (gl_list_get_at (list2, index) == obj); ASSERT (gl_list_node_value (list2, node2) == obj); - node3 = gl_list_set_at (list3, index, obj); + node3 = gl_list_nx_set_at (list3, index, obj); + ASSERT (node3 != NULL); ASSERT (gl_list_get_at (list3, index) == obj); ASSERT (gl_list_node_value (list3, node3) == obj); @@ -228,9 +234,12 @@ main (int argc, char *argv[]) { const char *obj = RANDOM_OBJECT (); gl_list_node_t node1, node2, node3; - node1 = gl_list_add_first (list1, obj); - node2 = gl_list_add_first (list2, obj); - node3 = gl_list_add_first (list3, obj); + node1 = gl_list_nx_add_first (list1, obj); + ASSERT (node1 != NULL); + node2 = gl_list_nx_add_first (list2, obj); + ASSERT (node2 != NULL); + node3 = gl_list_nx_add_first (list3, obj); + ASSERT (node3 != NULL); ASSERT (gl_list_node_value (list1, node1) == obj); ASSERT (gl_list_node_value (list2, node2) == obj); ASSERT (gl_list_node_value (list3, node3) == obj); @@ -243,9 +252,12 @@ main (int argc, char *argv[]) { const char *obj = RANDOM_OBJECT (); gl_list_node_t node1, node2, node3; - node1 = gl_list_add_last (list1, obj); - node2 = gl_list_add_last (list2, obj); - node3 = gl_list_add_last (list3, obj); + node1 = gl_list_nx_add_last (list1, obj); + ASSERT (node1 != NULL); + node2 = gl_list_nx_add_last (list2, obj); + ASSERT (node2 != NULL); + node3 = gl_list_nx_add_last (list3, obj); + ASSERT (node3 != NULL); ASSERT (gl_list_node_value (list1, node1) == obj); ASSERT (gl_list_node_value (list2, node2) == obj); ASSERT (gl_list_node_value (list3, node3) == obj); @@ -260,15 +272,24 @@ main (int argc, char *argv[]) const char *obj1 = RANDOM_OBJECT (); const char *obj2 = RANDOM_OBJECT (); gl_list_node_t node1, node2, node3; - node1 = gl_list_add_first (list1, obj2); - node1 = gl_list_add_before (list1, node1, obj0); - node1 = gl_list_add_after (list1, node1, obj1); - node2 = gl_list_add_first (list2, obj2); - node2 = gl_list_add_before (list2, node2, obj0); - node2 = gl_list_add_after (list2, node2, obj1); - node3 = gl_list_add_first (list3, obj2); - node3 = gl_list_add_before (list3, node3, obj0); - node3 = gl_list_add_after (list3, node3, obj1); + node1 = gl_list_nx_add_first (list1, obj2); + ASSERT (node1 != NULL); + node1 = gl_list_nx_add_before (list1, node1, obj0); + ASSERT (node1 != NULL); + node1 = gl_list_nx_add_after (list1, node1, obj1); + ASSERT (node1 != NULL); + node2 = gl_list_nx_add_first (list2, obj2); + ASSERT (node2 != NULL); + node2 = gl_list_nx_add_before (list2, node2, obj0); + ASSERT (node2 != NULL); + node2 = gl_list_nx_add_after (list2, node2, obj1); + ASSERT (node2 != NULL); + node3 = gl_list_nx_add_first (list3, obj2); + ASSERT (node3 != NULL); + node3 = gl_list_nx_add_before (list3, node3, obj0); + ASSERT (node3 != NULL); + node3 = gl_list_nx_add_after (list3, node3, obj1); + ASSERT (node3 != NULL); ASSERT (gl_list_node_value (list1, node1) == obj1); ASSERT (gl_list_node_value (list2, node2) == obj1); ASSERT (gl_list_node_value (list3, node3) == obj1); @@ -288,9 +309,12 @@ main (int argc, char *argv[]) size_t index = RANDOM (gl_list_size (list1) + 1); const char *obj = RANDOM_OBJECT (); gl_list_node_t node1, node2, node3; - node1 = gl_list_add_at (list1, index, obj); - node2 = gl_list_add_at (list2, index, obj); - node3 = gl_list_add_at (list3, index, obj); + node1 = gl_list_nx_add_at (list1, index, obj); + ASSERT (node1 != NULL); + node2 = gl_list_nx_add_at (list2, index, obj); + ASSERT (node2 != NULL); + node3 = gl_list_nx_add_at (list3, index, obj); + ASSERT (node3 != NULL); ASSERT (gl_list_get_at (list1, index) == obj); ASSERT (gl_list_node_value (list1, node1) == obj); ASSERT (gl_list_get_at (list2, index) == obj); diff --git a/tests/test-carray_list.c b/tests/test-carray_list.c index 04c39557f8..def7c5539d 100644 --- a/tests/test-carray_list.c +++ b/tests/test-carray_list.c @@ -1,5 +1,5 @@ /* Test of sequential list data type implementation. - Copyright (C) 2006-2008 Free Software Foundation, Inc. + Copyright (C) 2006-2009 Free Software Foundation, Inc. Written by Bruno Haible <bruno@clisp.org>, 2006. This program is free software: you can redistribute it and/or modify @@ -87,16 +87,19 @@ main (int argc, char *argv[]) contents[i] = RANDOM_OBJECT (); /* Create list1. */ - list1 = gl_list_create (GL_ARRAY_LIST, NULL, NULL, NULL, true, - initial_size, contents); + list1 = gl_list_nx_create (GL_ARRAY_LIST, NULL, NULL, NULL, true, + initial_size, contents); + ASSERT (list1 != NULL); /* Create list2. */ - list2 = gl_list_create_empty (GL_CARRAY_LIST, NULL, NULL, NULL, true); + list2 = gl_list_nx_create_empty (GL_CARRAY_LIST, NULL, NULL, NULL, true); + ASSERT (list2 != NULL); for (i = 0; i < initial_size; i++) - gl_list_add_last (list2, contents[i]); + ASSERT (gl_list_nx_add_last (list2, contents[i]) != NULL); /* Create list3. */ - list3 = gl_list_create (GL_CARRAY_LIST, NULL, NULL, NULL, true, - initial_size, contents); + list3 = gl_list_nx_create (GL_CARRAY_LIST, NULL, NULL, NULL, true, + initial_size, contents); + ASSERT (list3 != NULL); check_all (list1, list2, list3); @@ -112,15 +115,18 @@ main (int argc, char *argv[]) const char *obj = RANDOM_OBJECT (); gl_list_node_t node1, node2, node3; - node1 = gl_list_set_at (list1, index, obj); + node1 = gl_list_nx_set_at (list1, index, obj); + ASSERT (node1 != NULL); ASSERT (gl_list_get_at (list1, index) == obj); ASSERT (gl_list_node_value (list1, node1) == obj); - node2 = gl_list_set_at (list2, index, obj); + node2 = gl_list_nx_set_at (list2, index, obj); + ASSERT (node2 != NULL); ASSERT (gl_list_get_at (list2, index) == obj); ASSERT (gl_list_node_value (list2, node2) == obj); - node3 = gl_list_set_at (list3, index, obj); + node3 = gl_list_nx_set_at (list3, index, obj); + ASSERT (node3 != NULL); ASSERT (gl_list_get_at (list3, index) == obj); ASSERT (gl_list_node_value (list3, node3) == obj); @@ -194,9 +200,12 @@ main (int argc, char *argv[]) { const char *obj = RANDOM_OBJECT (); gl_list_node_t node1, node2, node3; - node1 = gl_list_add_first (list1, obj); - node2 = gl_list_add_first (list2, obj); - node3 = gl_list_add_first (list3, obj); + node1 = gl_list_nx_add_first (list1, obj); + ASSERT (node1 != NULL); + node2 = gl_list_nx_add_first (list2, obj); + ASSERT (node2 != NULL); + node3 = gl_list_nx_add_first (list3, obj); + ASSERT (node3 != NULL); ASSERT (gl_list_node_value (list1, node1) == obj); ASSERT (gl_list_node_value (list2, node2) == obj); ASSERT (gl_list_node_value (list3, node3) == obj); @@ -209,9 +218,12 @@ main (int argc, char *argv[]) { const char *obj = RANDOM_OBJECT (); gl_list_node_t node1, node2, node3; - node1 = gl_list_add_last (list1, obj); - node2 = gl_list_add_last (list2, obj); - node3 = gl_list_add_last (list3, obj); + node1 = gl_list_nx_add_last (list1, obj); + ASSERT (node1 != NULL); + node2 = gl_list_nx_add_last (list2, obj); + ASSERT (node2 != NULL); + node3 = gl_list_nx_add_last (list3, obj); + ASSERT (node3 != NULL); ASSERT (gl_list_node_value (list1, node1) == obj); ASSERT (gl_list_node_value (list2, node2) == obj); ASSERT (gl_list_node_value (list3, node3) == obj); @@ -226,15 +238,24 @@ main (int argc, char *argv[]) const char *obj1 = RANDOM_OBJECT (); const char *obj2 = RANDOM_OBJECT (); gl_list_node_t node1, node2, node3; - node1 = gl_list_add_first (list1, obj2); - node1 = gl_list_add_before (list1, node1, obj0); - node1 = gl_list_add_after (list1, node1, obj1); - node2 = gl_list_add_first (list2, obj2); - node2 = gl_list_add_before (list2, node2, obj0); - node2 = gl_list_add_after (list2, node2, obj1); - node3 = gl_list_add_first (list3, obj2); - node3 = gl_list_add_before (list3, node3, obj0); - node3 = gl_list_add_after (list3, node3, obj1); + node1 = gl_list_nx_add_first (list1, obj2); + ASSERT (node1 != NULL); + node1 = gl_list_nx_add_before (list1, node1, obj0); + ASSERT (node1 != NULL); + node1 = gl_list_nx_add_after (list1, node1, obj1); + ASSERT (node1 != NULL); + node2 = gl_list_nx_add_first (list2, obj2); + ASSERT (node2 != NULL); + node2 = gl_list_nx_add_before (list2, node2, obj0); + ASSERT (node2 != NULL); + node2 = gl_list_nx_add_after (list2, node2, obj1); + ASSERT (node2 != NULL); + node3 = gl_list_nx_add_first (list3, obj2); + ASSERT (node3 != NULL); + node3 = gl_list_nx_add_before (list3, node3, obj0); + ASSERT (node3 != NULL); + node3 = gl_list_nx_add_after (list3, node3, obj1); + ASSERT (node3 != NULL); ASSERT (gl_list_node_value (list1, node1) == obj1); ASSERT (gl_list_node_value (list2, node2) == obj1); ASSERT (gl_list_node_value (list3, node3) == obj1); @@ -254,9 +275,12 @@ main (int argc, char *argv[]) size_t index = RANDOM (gl_list_size (list1) + 1); const char *obj = RANDOM_OBJECT (); gl_list_node_t node1, node2, node3; - node1 = gl_list_add_at (list1, index, obj); - node2 = gl_list_add_at (list2, index, obj); - node3 = gl_list_add_at (list3, index, obj); + node1 = gl_list_nx_add_at (list1, index, obj); + ASSERT (node1 != NULL); + node2 = gl_list_nx_add_at (list2, index, obj); + ASSERT (node2 != NULL); + node3 = gl_list_nx_add_at (list3, index, obj); + ASSERT (node3 != NULL); ASSERT (gl_list_get_at (list1, index) == obj); ASSERT (gl_list_node_value (list1, node1) == obj); ASSERT (gl_list_get_at (list2, index) == obj); diff --git a/tests/test-linked_list.c b/tests/test-linked_list.c index 3051a7e6ed..5511c89cbb 100644 --- a/tests/test-linked_list.c +++ b/tests/test-linked_list.c @@ -1,5 +1,5 @@ /* Test of sequential list data type implementation. - Copyright (C) 2006-2008 Free Software Foundation, Inc. + Copyright (C) 2006-2009 Free Software Foundation, Inc. Written by Bruno Haible <bruno@clisp.org>, 2006. This program is free software: you can redistribute it and/or modify @@ -87,16 +87,19 @@ main (int argc, char *argv[]) contents[i] = RANDOM_OBJECT (); /* Create list1. */ - list1 = gl_list_create (GL_ARRAY_LIST, NULL, NULL, NULL, true, - initial_size, contents); + list1 = gl_list_nx_create (GL_ARRAY_LIST, NULL, NULL, NULL, true, + initial_size, contents); + ASSERT (list1 != NULL); /* Create list2. */ - list2 = gl_list_create_empty (GL_LINKED_LIST, NULL, NULL, NULL, true); + list2 = gl_list_nx_create_empty (GL_LINKED_LIST, NULL, NULL, NULL, true); + ASSERT (list2 != NULL); for (i = 0; i < initial_size; i++) - gl_list_add_last (list2, contents[i]); + ASSERT (gl_list_nx_add_last (list2, contents[i]) != NULL); /* Create list3. */ - list3 = gl_list_create (GL_LINKED_LIST, NULL, NULL, NULL, true, - initial_size, contents); + list3 = gl_list_nx_create (GL_LINKED_LIST, NULL, NULL, NULL, true, + initial_size, contents); + ASSERT (list3 != NULL); check_all (list1, list2, list3); @@ -112,15 +115,18 @@ main (int argc, char *argv[]) const char *obj = RANDOM_OBJECT (); gl_list_node_t node1, node2, node3; - node1 = gl_list_set_at (list1, index, obj); + node1 = gl_list_nx_set_at (list1, index, obj); + ASSERT (node1 != NULL); ASSERT (gl_list_get_at (list1, index) == obj); ASSERT (gl_list_node_value (list1, node1) == obj); - node2 = gl_list_set_at (list2, index, obj); + node2 = gl_list_nx_set_at (list2, index, obj); + ASSERT (node2 != NULL); ASSERT (gl_list_get_at (list2, index) == obj); ASSERT (gl_list_node_value (list2, node2) == obj); - node3 = gl_list_set_at (list3, index, obj); + node3 = gl_list_nx_set_at (list3, index, obj); + ASSERT (node3 != NULL); ASSERT (gl_list_get_at (list3, index) == obj); ASSERT (gl_list_node_value (list3, node3) == obj); @@ -194,9 +200,12 @@ main (int argc, char *argv[]) { const char *obj = RANDOM_OBJECT (); gl_list_node_t node1, node2, node3; - node1 = gl_list_add_first (list1, obj); - node2 = gl_list_add_first (list2, obj); - node3 = gl_list_add_first (list3, obj); + node1 = gl_list_nx_add_first (list1, obj); + ASSERT (node1 != NULL); + node2 = gl_list_nx_add_first (list2, obj); + ASSERT (node2 != NULL); + node3 = gl_list_nx_add_first (list3, obj); + ASSERT (node3 != NULL); ASSERT (gl_list_node_value (list1, node1) == obj); ASSERT (gl_list_node_value (list2, node2) == obj); ASSERT (gl_list_node_value (list3, node3) == obj); @@ -209,9 +218,12 @@ main (int argc, char *argv[]) { const char *obj = RANDOM_OBJECT (); gl_list_node_t node1, node2, node3; - node1 = gl_list_add_last (list1, obj); - node2 = gl_list_add_last (list2, obj); - node3 = gl_list_add_last (list3, obj); + node1 = gl_list_nx_add_last (list1, obj); + ASSERT (node1 != NULL); + node2 = gl_list_nx_add_last (list2, obj); + ASSERT (node2 != NULL); + node3 = gl_list_nx_add_last (list3, obj); + ASSERT (node3 != NULL); ASSERT (gl_list_node_value (list1, node1) == obj); ASSERT (gl_list_node_value (list2, node2) == obj); ASSERT (gl_list_node_value (list3, node3) == obj); @@ -226,15 +238,24 @@ main (int argc, char *argv[]) const char *obj1 = RANDOM_OBJECT (); const char *obj2 = RANDOM_OBJECT (); gl_list_node_t node1, node2, node3; - node1 = gl_list_add_first (list1, obj2); - node1 = gl_list_add_before (list1, node1, obj0); - node1 = gl_list_add_after (list1, node1, obj1); - node2 = gl_list_add_first (list2, obj2); - node2 = gl_list_add_before (list2, node2, obj0); - node2 = gl_list_add_after (list2, node2, obj1); - node3 = gl_list_add_first (list3, obj2); - node3 = gl_list_add_before (list3, node3, obj0); - node3 = gl_list_add_after (list3, node3, obj1); + node1 = gl_list_nx_add_first (list1, obj2); + ASSERT (node1 != NULL); + node1 = gl_list_nx_add_before (list1, node1, obj0); + ASSERT (node1 != NULL); + node1 = gl_list_nx_add_after (list1, node1, obj1); + ASSERT (node1 != NULL); + node2 = gl_list_nx_add_first (list2, obj2); + ASSERT (node2 != NULL); + node2 = gl_list_nx_add_before (list2, node2, obj0); + ASSERT (node2 != NULL); + node2 = gl_list_nx_add_after (list2, node2, obj1); + ASSERT (node2 != NULL); + node3 = gl_list_nx_add_first (list3, obj2); + ASSERT (node3 != NULL); + node3 = gl_list_nx_add_before (list3, node3, obj0); + ASSERT (node3 != NULL); + node3 = gl_list_nx_add_after (list3, node3, obj1); + ASSERT (node3 != NULL); ASSERT (gl_list_node_value (list1, node1) == obj1); ASSERT (gl_list_node_value (list2, node2) == obj1); ASSERT (gl_list_node_value (list3, node3) == obj1); @@ -254,9 +275,12 @@ main (int argc, char *argv[]) size_t index = RANDOM (gl_list_size (list1) + 1); const char *obj = RANDOM_OBJECT (); gl_list_node_t node1, node2, node3; - node1 = gl_list_add_at (list1, index, obj); - node2 = gl_list_add_at (list2, index, obj); - node3 = gl_list_add_at (list3, index, obj); + node1 = gl_list_nx_add_at (list1, index, obj); + ASSERT (node1 != NULL); + node2 = gl_list_nx_add_at (list2, index, obj); + ASSERT (node2 != NULL); + node3 = gl_list_nx_add_at (list3, index, obj); + ASSERT (node3 != NULL); ASSERT (gl_list_get_at (list1, index) == obj); ASSERT (gl_list_node_value (list1, node1) == obj); ASSERT (gl_list_get_at (list2, index) == obj); diff --git a/tests/test-linkedhash_list.c b/tests/test-linkedhash_list.c index 58edac8e70..98913c5742 100644 --- a/tests/test-linkedhash_list.c +++ b/tests/test-linkedhash_list.c @@ -1,5 +1,5 @@ /* Test of sequential list data type implementation. - Copyright (C) 2006-2008 Free Software Foundation, Inc. + Copyright (C) 2006-2009 Free Software Foundation, Inc. Written by Bruno Haible <bruno@clisp.org>, 2006. This program is free software: you can redistribute it and/or modify @@ -114,19 +114,22 @@ main (int argc, char *argv[]) contents[i] = RANDOM_OBJECT (); /* Create list1. */ - list1 = gl_list_create (GL_ARRAY_LIST, - string_equals, string_hash, NULL, true, - initial_size, contents); + list1 = gl_list_nx_create (GL_ARRAY_LIST, + string_equals, string_hash, NULL, true, + initial_size, contents); + ASSERT (list1 != NULL); /* Create list2. */ - list2 = gl_list_create_empty (GL_LINKEDHASH_LIST, - string_equals, string_hash, NULL, true); + list2 = gl_list_nx_create_empty (GL_LINKEDHASH_LIST, + string_equals, string_hash, NULL, true); + ASSERT (list2 != NULL); for (i = 0; i < initial_size; i++) - gl_list_add_last (list2, contents[i]); + ASSERT (gl_list_nx_add_last (list2, contents[i]) != NULL); /* Create list3. */ - list3 = gl_list_create (GL_LINKEDHASH_LIST, - string_equals, string_hash, NULL, true, - initial_size, contents); + list3 = gl_list_nx_create (GL_LINKEDHASH_LIST, + string_equals, string_hash, NULL, true, + initial_size, contents); + ASSERT (list3 != NULL); check_all (list1, list2, list3); @@ -142,15 +145,18 @@ main (int argc, char *argv[]) const char *obj = RANDOM_OBJECT (); gl_list_node_t node1, node2, node3; - node1 = gl_list_set_at (list1, index, obj); + node1 = gl_list_nx_set_at (list1, index, obj); + ASSERT (node1 != NULL); ASSERT (gl_list_get_at (list1, index) == obj); ASSERT (gl_list_node_value (list1, node1) == obj); - node2 = gl_list_set_at (list2, index, obj); + node2 = gl_list_nx_set_at (list2, index, obj); + ASSERT (node2 != NULL); ASSERT (gl_list_get_at (list2, index) == obj); ASSERT (gl_list_node_value (list2, node2) == obj); - node3 = gl_list_set_at (list3, index, obj); + node3 = gl_list_nx_set_at (list3, index, obj); + ASSERT (node3 != NULL); ASSERT (gl_list_get_at (list3, index) == obj); ASSERT (gl_list_node_value (list3, node3) == obj); @@ -224,9 +230,12 @@ main (int argc, char *argv[]) { const char *obj = RANDOM_OBJECT (); gl_list_node_t node1, node2, node3; - node1 = gl_list_add_first (list1, obj); - node2 = gl_list_add_first (list2, obj); - node3 = gl_list_add_first (list3, obj); + node1 = gl_list_nx_add_first (list1, obj); + ASSERT (node1 != NULL); + node2 = gl_list_nx_add_first (list2, obj); + ASSERT (node2 != NULL); + node3 = gl_list_nx_add_first (list3, obj); + ASSERT (node3 != NULL); ASSERT (gl_list_node_value (list1, node1) == obj); ASSERT (gl_list_node_value (list2, node2) == obj); ASSERT (gl_list_node_value (list3, node3) == obj); @@ -239,9 +248,12 @@ main (int argc, char *argv[]) { const char *obj = RANDOM_OBJECT (); gl_list_node_t node1, node2, node3; - node1 = gl_list_add_last (list1, obj); - node2 = gl_list_add_last (list2, obj); - node3 = gl_list_add_last (list3, obj); + node1 = gl_list_nx_add_last (list1, obj); + ASSERT (node1 != NULL); + node2 = gl_list_nx_add_last (list2, obj); + ASSERT (node2 != NULL); + node3 = gl_list_nx_add_last (list3, obj); + ASSERT (node3 != NULL); ASSERT (gl_list_node_value (list1, node1) == obj); ASSERT (gl_list_node_value (list2, node2) == obj); ASSERT (gl_list_node_value (list3, node3) == obj); @@ -256,15 +268,24 @@ main (int argc, char *argv[]) const char *obj1 = RANDOM_OBJECT (); const char *obj2 = RANDOM_OBJECT (); gl_list_node_t node1, node2, node3; - node1 = gl_list_add_first (list1, obj2); - node1 = gl_list_add_before (list1, node1, obj0); - node1 = gl_list_add_after (list1, node1, obj1); - node2 = gl_list_add_first (list2, obj2); - node2 = gl_list_add_before (list2, node2, obj0); - node2 = gl_list_add_after (list2, node2, obj1); - node3 = gl_list_add_first (list3, obj2); - node3 = gl_list_add_before (list3, node3, obj0); - node3 = gl_list_add_after (list3, node3, obj1); + node1 = gl_list_nx_add_first (list1, obj2); + ASSERT (node1 != NULL); + node1 = gl_list_nx_add_before (list1, node1, obj0); + ASSERT (node1 != NULL); + node1 = gl_list_nx_add_after (list1, node1, obj1); + ASSERT (node1 != NULL); + node2 = gl_list_nx_add_first (list2, obj2); + ASSERT (node2 != NULL); + node2 = gl_list_nx_add_before (list2, node2, obj0); + ASSERT (node2 != NULL); + node2 = gl_list_nx_add_after (list2, node2, obj1); + ASSERT (node2 != NULL); + node3 = gl_list_nx_add_first (list3, obj2); + ASSERT (node3 != NULL); + node3 = gl_list_nx_add_before (list3, node3, obj0); + ASSERT (node3 != NULL); + node3 = gl_list_nx_add_after (list3, node3, obj1); + ASSERT (node3 != NULL); ASSERT (gl_list_node_value (list1, node1) == obj1); ASSERT (gl_list_node_value (list2, node2) == obj1); ASSERT (gl_list_node_value (list3, node3) == obj1); @@ -284,9 +305,12 @@ main (int argc, char *argv[]) size_t index = RANDOM (gl_list_size (list1) + 1); const char *obj = RANDOM_OBJECT (); gl_list_node_t node1, node2, node3; - node1 = gl_list_add_at (list1, index, obj); - node2 = gl_list_add_at (list2, index, obj); - node3 = gl_list_add_at (list3, index, obj); + node1 = gl_list_nx_add_at (list1, index, obj); + ASSERT (node1 != NULL); + node2 = gl_list_nx_add_at (list2, index, obj); + ASSERT (node2 != NULL); + node3 = gl_list_nx_add_at (list3, index, obj); + ASSERT (node3 != NULL); ASSERT (gl_list_get_at (list1, index) == obj); ASSERT (gl_list_node_value (list1, node1) == obj); ASSERT (gl_list_get_at (list2, index) == obj); diff --git a/tests/test-rbtree_list.c b/tests/test-rbtree_list.c index 8351dd3b47..1f91492eb5 100644 --- a/tests/test-rbtree_list.c +++ b/tests/test-rbtree_list.c @@ -1,5 +1,5 @@ /* Test of sequential list data type implementation. - Copyright (C) 2006-2008 Free Software Foundation, Inc. + Copyright (C) 2006-2009 Free Software Foundation, Inc. Written by Bruno Haible <bruno@clisp.org>, 2006. This program is free software: you can redistribute it and/or modify @@ -91,16 +91,19 @@ main (int argc, char *argv[]) contents[i] = RANDOM_OBJECT (); /* Create list1. */ - list1 = gl_list_create (GL_ARRAY_LIST, NULL, NULL, NULL, true, - initial_size, contents); + list1 = gl_list_nx_create (GL_ARRAY_LIST, NULL, NULL, NULL, true, + initial_size, contents); + ASSERT (list1 != NULL); /* Create list2. */ - list2 = gl_list_create_empty (GL_RBTREE_LIST, NULL, NULL, NULL, true); + list2 = gl_list_nx_create_empty (GL_RBTREE_LIST, NULL, NULL, NULL, true); + ASSERT (list2 != NULL); for (i = 0; i < initial_size; i++) - gl_list_add_last (list2, contents[i]); + ASSERT (gl_list_nx_add_last (list2, contents[i]) != NULL); /* Create list3. */ - list3 = gl_list_create (GL_RBTREE_LIST, NULL, NULL, NULL, true, - initial_size, contents); + list3 = gl_list_nx_create (GL_RBTREE_LIST, NULL, NULL, NULL, true, + initial_size, contents); + ASSERT (list3 != NULL); check_all (list1, list2, list3); @@ -116,15 +119,18 @@ main (int argc, char *argv[]) const char *obj = RANDOM_OBJECT (); gl_list_node_t node1, node2, node3; - node1 = gl_list_set_at (list1, index, obj); + node1 = gl_list_nx_set_at (list1, index, obj); + ASSERT (node1 != NULL); ASSERT (gl_list_get_at (list1, index) == obj); ASSERT (gl_list_node_value (list1, node1) == obj); - node2 = gl_list_set_at (list2, index, obj); + node2 = gl_list_nx_set_at (list2, index, obj); + ASSERT (node2 != NULL); ASSERT (gl_list_get_at (list2, index) == obj); ASSERT (gl_list_node_value (list2, node2) == obj); - node3 = gl_list_set_at (list3, index, obj); + node3 = gl_list_nx_set_at (list3, index, obj); + ASSERT (node3 != NULL); ASSERT (gl_list_get_at (list3, index) == obj); ASSERT (gl_list_node_value (list3, node3) == obj); @@ -198,9 +204,12 @@ main (int argc, char *argv[]) { const char *obj = RANDOM_OBJECT (); gl_list_node_t node1, node2, node3; - node1 = gl_list_add_first (list1, obj); - node2 = gl_list_add_first (list2, obj); - node3 = gl_list_add_first (list3, obj); + node1 = gl_list_nx_add_first (list1, obj); + ASSERT (node1 != NULL); + node2 = gl_list_nx_add_first (list2, obj); + ASSERT (node2 != NULL); + node3 = gl_list_nx_add_first (list3, obj); + ASSERT (node3 != NULL); ASSERT (gl_list_node_value (list1, node1) == obj); ASSERT (gl_list_node_value (list2, node2) == obj); ASSERT (gl_list_node_value (list3, node3) == obj); @@ -213,9 +222,12 @@ main (int argc, char *argv[]) { const char *obj = RANDOM_OBJECT (); gl_list_node_t node1, node2, node3; - node1 = gl_list_add_last (list1, obj); - node2 = gl_list_add_last (list2, obj); - node3 = gl_list_add_last (list3, obj); + node1 = gl_list_nx_add_last (list1, obj); + ASSERT (node1 != NULL); + node2 = gl_list_nx_add_last (list2, obj); + ASSERT (node2 != NULL); + node3 = gl_list_nx_add_last (list3, obj); + ASSERT (node3 != NULL); ASSERT (gl_list_node_value (list1, node1) == obj); ASSERT (gl_list_node_value (list2, node2) == obj); ASSERT (gl_list_node_value (list3, node3) == obj); @@ -230,15 +242,24 @@ main (int argc, char *argv[]) const char *obj1 = RANDOM_OBJECT (); const char *obj2 = RANDOM_OBJECT (); gl_list_node_t node1, node2, node3; - node1 = gl_list_add_first (list1, obj2); - node1 = gl_list_add_before (list1, node1, obj0); - node1 = gl_list_add_after (list1, node1, obj1); - node2 = gl_list_add_first (list2, obj2); - node2 = gl_list_add_before (list2, node2, obj0); - node2 = gl_list_add_after (list2, node2, obj1); - node3 = gl_list_add_first (list3, obj2); - node3 = gl_list_add_before (list3, node3, obj0); - node3 = gl_list_add_after (list3, node3, obj1); + node1 = gl_list_nx_add_first (list1, obj2); + ASSERT (node1 != NULL); + node1 = gl_list_nx_add_before (list1, node1, obj0); + ASSERT (node1 != NULL); + node1 = gl_list_nx_add_after (list1, node1, obj1); + ASSERT (node1 != NULL); + node2 = gl_list_nx_add_first (list2, obj2); + ASSERT (node2 != NULL); + node2 = gl_list_nx_add_before (list2, node2, obj0); + ASSERT (node2 != NULL); + node2 = gl_list_nx_add_after (list2, node2, obj1); + ASSERT (node2 != NULL); + node3 = gl_list_nx_add_first (list3, obj2); + ASSERT (node3 != NULL); + node3 = gl_list_nx_add_before (list3, node3, obj0); + ASSERT (node3 != NULL); + node3 = gl_list_nx_add_after (list3, node3, obj1); + ASSERT (node3 != NULL); ASSERT (gl_list_node_value (list1, node1) == obj1); ASSERT (gl_list_node_value (list2, node2) == obj1); ASSERT (gl_list_node_value (list3, node3) == obj1); @@ -258,9 +279,12 @@ main (int argc, char *argv[]) size_t index = RANDOM (gl_list_size (list1) + 1); const char *obj = RANDOM_OBJECT (); gl_list_node_t node1, node2, node3; - node1 = gl_list_add_at (list1, index, obj); - node2 = gl_list_add_at (list2, index, obj); - node3 = gl_list_add_at (list3, index, obj); + node1 = gl_list_nx_add_at (list1, index, obj); + ASSERT (node1 != NULL); + node2 = gl_list_nx_add_at (list2, index, obj); + ASSERT (node2 != NULL); + node3 = gl_list_nx_add_at (list3, index, obj); + ASSERT (node3 != NULL); ASSERT (gl_list_get_at (list1, index) == obj); ASSERT (gl_list_node_value (list1, node1) == obj); ASSERT (gl_list_get_at (list2, index) == obj); diff --git a/tests/test-rbtreehash_list.c b/tests/test-rbtreehash_list.c index 0031f26ae6..7ec8f1ef1a 100644 --- a/tests/test-rbtreehash_list.c +++ b/tests/test-rbtreehash_list.c @@ -1,5 +1,5 @@ /* Test of sequential list data type implementation. - Copyright (C) 2006-2008 Free Software Foundation, Inc. + Copyright (C) 2006-2009 Free Software Foundation, Inc. Written by Bruno Haible <bruno@clisp.org>, 2006. This program is free software: you can redistribute it and/or modify @@ -118,19 +118,22 @@ main (int argc, char *argv[]) contents[i] = RANDOM_OBJECT (); /* Create list1. */ - list1 = gl_list_create (GL_ARRAY_LIST, - string_equals, string_hash, NULL, true, - initial_size, contents); + list1 = gl_list_nx_create (GL_ARRAY_LIST, + string_equals, string_hash, NULL, true, + initial_size, contents); + ASSERT (list1 != NULL); /* Create list2. */ - list2 = gl_list_create_empty (GL_RBTREEHASH_LIST, - string_equals, string_hash, NULL, true); + list2 = gl_list_nx_create_empty (GL_RBTREEHASH_LIST, + string_equals, string_hash, NULL, true); + ASSERT (list2 != NULL); for (i = 0; i < initial_size; i++) - gl_list_add_last (list2, contents[i]); + ASSERT (gl_list_nx_add_last (list2, contents[i]) != NULL); /* Create list3. */ - list3 = gl_list_create (GL_RBTREEHASH_LIST, - string_equals, string_hash, NULL, true, - initial_size, contents); + list3 = gl_list_nx_create (GL_RBTREEHASH_LIST, + string_equals, string_hash, NULL, true, + initial_size, contents); + ASSERT (list3 != NULL); check_all (list1, list2, list3); @@ -146,15 +149,18 @@ main (int argc, char *argv[]) const char *obj = RANDOM_OBJECT (); gl_list_node_t node1, node2, node3; - node1 = gl_list_set_at (list1, index, obj); + node1 = gl_list_nx_set_at (list1, index, obj); + ASSERT (node1 != NULL); ASSERT (gl_list_get_at (list1, index) == obj); ASSERT (gl_list_node_value (list1, node1) == obj); - node2 = gl_list_set_at (list2, index, obj); + node2 = gl_list_nx_set_at (list2, index, obj); + ASSERT (node2 != NULL); ASSERT (gl_list_get_at (list2, index) == obj); ASSERT (gl_list_node_value (list2, node2) == obj); - node3 = gl_list_set_at (list3, index, obj); + node3 = gl_list_nx_set_at (list3, index, obj); + ASSERT (node3 != NULL); ASSERT (gl_list_get_at (list3, index) == obj); ASSERT (gl_list_node_value (list3, node3) == obj); @@ -228,9 +234,12 @@ main (int argc, char *argv[]) { const char *obj = RANDOM_OBJECT (); gl_list_node_t node1, node2, node3; - node1 = gl_list_add_first (list1, obj); - node2 = gl_list_add_first (list2, obj); - node3 = gl_list_add_first (list3, obj); + node1 = gl_list_nx_add_first (list1, obj); + ASSERT (node1 != NULL); + node2 = gl_list_nx_add_first (list2, obj); + ASSERT (node2 != NULL); + node3 = gl_list_nx_add_first (list3, obj); + ASSERT (node3 != NULL); ASSERT (gl_list_node_value (list1, node1) == obj); ASSERT (gl_list_node_value (list2, node2) == obj); ASSERT (gl_list_node_value (list3, node3) == obj); @@ -243,9 +252,12 @@ main (int argc, char *argv[]) { const char *obj = RANDOM_OBJECT (); gl_list_node_t node1, node2, node3; - node1 = gl_list_add_last (list1, obj); - node2 = gl_list_add_last (list2, obj); - node3 = gl_list_add_last (list3, obj); + node1 = gl_list_nx_add_last (list1, obj); + ASSERT (node1 != NULL); + node2 = gl_list_nx_add_last (list2, obj); + ASSERT (node2 != NULL); + node3 = gl_list_nx_add_last (list3, obj); + ASSERT (node3 != NULL); ASSERT (gl_list_node_value (list1, node1) == obj); ASSERT (gl_list_node_value (list2, node2) == obj); ASSERT (gl_list_node_value (list3, node3) == obj); @@ -260,15 +272,24 @@ main (int argc, char *argv[]) const char *obj1 = RANDOM_OBJECT (); const char *obj2 = RANDOM_OBJECT (); gl_list_node_t node1, node2, node3; - node1 = gl_list_add_first (list1, obj2); - node1 = gl_list_add_before (list1, node1, obj0); - node1 = gl_list_add_after (list1, node1, obj1); - node2 = gl_list_add_first (list2, obj2); - node2 = gl_list_add_before (list2, node2, obj0); - node2 = gl_list_add_after (list2, node2, obj1); - node3 = gl_list_add_first (list3, obj2); - node3 = gl_list_add_before (list3, node3, obj0); - node3 = gl_list_add_after (list3, node3, obj1); + node1 = gl_list_nx_add_first (list1, obj2); + ASSERT (node1 != NULL); + node1 = gl_list_nx_add_before (list1, node1, obj0); + ASSERT (node1 != NULL); + node1 = gl_list_nx_add_after (list1, node1, obj1); + ASSERT (node1 != NULL); + node2 = gl_list_nx_add_first (list2, obj2); + ASSERT (node2 != NULL); + node2 = gl_list_nx_add_before (list2, node2, obj0); + ASSERT (node2 != NULL); + node2 = gl_list_nx_add_after (list2, node2, obj1); + ASSERT (node2 != NULL); + node3 = gl_list_nx_add_first (list3, obj2); + ASSERT (node3 != NULL); + node3 = gl_list_nx_add_before (list3, node3, obj0); + ASSERT (node3 != NULL); + node3 = gl_list_nx_add_after (list3, node3, obj1); + ASSERT (node3 != NULL); ASSERT (gl_list_node_value (list1, node1) == obj1); ASSERT (gl_list_node_value (list2, node2) == obj1); ASSERT (gl_list_node_value (list3, node3) == obj1); @@ -288,9 +309,12 @@ main (int argc, char *argv[]) size_t index = RANDOM (gl_list_size (list1) + 1); const char *obj = RANDOM_OBJECT (); gl_list_node_t node1, node2, node3; - node1 = gl_list_add_at (list1, index, obj); - node2 = gl_list_add_at (list2, index, obj); - node3 = gl_list_add_at (list3, index, obj); + node1 = gl_list_nx_add_at (list1, index, obj); + ASSERT (node1 != NULL); + node2 = gl_list_nx_add_at (list2, index, obj); + ASSERT (node2 != NULL); + node3 = gl_list_nx_add_at (list3, index, obj); + ASSERT (node3 != NULL); ASSERT (gl_list_get_at (list1, index) == obj); ASSERT (gl_list_node_value (list1, node1) == obj); ASSERT (gl_list_get_at (list2, index) == obj); |