changeset 12445:a8c91b846640

Move the malloc checking from module 'list' to new module 'xlist'.
author Bruno Haible <bruno@clisp.org>
date Mon, 14 Dec 2009 00:24:41 +0100
parents 29d240cb21b2
children 7e43ee94abd0
files ChangeLog NEWS lib/clean-temp.c lib/git-merge-changelog.c lib/gl_anyavltree_list2.h lib/gl_anyhash_list2.h lib/gl_anylinked_list2.h lib/gl_anyrbtree_list2.h lib/gl_anytree_list1.h lib/gl_anytree_list2.h lib/gl_anytreehash_list1.h lib/gl_array_list.c lib/gl_avltree_list.c lib/gl_avltreehash_list.c lib/gl_carray_list.c lib/gl_linked_list.c lib/gl_linkedhash_list.c lib/gl_list.c lib/gl_list.h lib/gl_rbtree_list.c lib/gl_rbtreehash_list.c lib/gl_sublist.c lib/gl_sublist.h lib/gl_xlist.c lib/gl_xlist.h lib/gl_xsublist.c lib/gl_xsublist.h modules/array-list modules/array-list-tests modules/array-oset-tests modules/avltree-list modules/avltree-list-tests modules/avltreehash-list modules/avltreehash-list-tests modules/carray-list modules/carray-list-tests modules/clean-temp modules/git-merge-changelog modules/linked-list modules/linked-list-tests modules/linkedhash-list modules/linkedhash-list-tests modules/rbtree-list modules/rbtree-list-tests modules/rbtreehash-list modules/rbtreehash-list-tests modules/sublist modules/xlist modules/xsublist tests/test-array_list.c tests/test-array_oset.c tests/test-avltree_list.c tests/test-avltreehash_list.c tests/test-carray_list.c tests/test-linked_list.c tests/test-linkedhash_list.c tests/test-rbtree_list.c tests/test-rbtreehash_list.c
diffstat 58 files changed, 2512 insertions(+), 1138 deletions(-) [+]
line wrap: on
line diff
--- a/ChangeLog
+++ b/ChangeLog
@@ -1,3 +1,229 @@
+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'.
--- a/NEWS
+++ b/NEWS
@@ -6,6 +6,16 @@
 
 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"
--- 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
--- 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"
--- 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 @@
   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 @@
   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 @@
     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,255 +407,10 @@
     }
 }
 
-static gl_list_node_t
-gl_tree_add_first (gl_list_t list, const void *elt)
-{
-  /* Create new node.  */
-  gl_list_node_t new_node = XMALLOC (struct gl_list_node_impl);
-
-  new_node->left = NULL;
-  new_node->right = NULL;
-  new_node->balance = 0;
-  new_node->branch_size = 1;
-  new_node->value = elt;
-#if WITH_HASHTABLE
-  new_node->h.hashcode =
-    (list->base.hashcode_fn != NULL
-     ? list->base.hashcode_fn (new_node->value)
-     : (size_t)(uintptr_t) new_node->value);
-#endif
-
-  /* Add it to the tree.  */
-  if (list->root == NULL)
-    {
-      list->root = new_node;
-      new_node->parent = NULL;
-    }
-  else
-    {
-      gl_list_node_t node;
-
-      for (node = list->root; node->left != NULL; )
-        node = node->left;
-
-      node->left = new_node;
-      new_node->parent = node;
-      node->balance--;
-
-      /* Update branch_size fields of the parent nodes.  */
-      {
-        gl_list_node_t p;
-
-        for (p = node; p != NULL; p = p->parent)
-          p->branch_size++;
-      }
-
-      /* Rebalance.  */
-      if (node->right == NULL && node->parent != NULL)
-        rebalance (list, node, 1, node->parent);
-    }
-
-#if WITH_HASHTABLE
-  /* Add node to the hash table.
-     Note that this is only possible _after_ the node has been added to the
-     tree structure, because add_to_bucket() uses node_position().  */
-  add_to_bucket (list, new_node);
-  hash_resize_after_add (list);
-#endif
-
-  return new_node;
-}
-
-static gl_list_node_t
-gl_tree_add_last (gl_list_t list, const void *elt)
-{
-  /* Create new node.  */
-  gl_list_node_t new_node = XMALLOC (struct gl_list_node_impl);
-
-  new_node->left = NULL;
-  new_node->right = NULL;
-  new_node->balance = 0;
-  new_node->branch_size = 1;
-  new_node->value = elt;
-#if WITH_HASHTABLE
-  new_node->h.hashcode =
-    (list->base.hashcode_fn != NULL
-     ? list->base.hashcode_fn (new_node->value)
-     : (size_t)(uintptr_t) new_node->value);
-#endif
-
-  /* Add it to the tree.  */
-  if (list->root == NULL)
-    {
-      list->root = new_node;
-      new_node->parent = NULL;
-    }
-  else
-    {
-      gl_list_node_t node;
-
-      for (node = list->root; node->right != NULL; )
-        node = node->right;
-
-      node->right = new_node;
-      new_node->parent = node;
-      node->balance++;
-
-      /* Update branch_size fields of the parent nodes.  */
-      {
-        gl_list_node_t p;
-
-        for (p = node; p != NULL; p = p->parent)
-          p->branch_size++;
-      }
-
-      /* Rebalance.  */
-      if (node->left == NULL && node->parent != NULL)
-        rebalance (list, node, 1, node->parent);
-    }
-
-#if WITH_HASHTABLE
-  /* Add node to the hash table.
-     Note that this is only possible _after_ the node has been added to the
-     tree structure, because add_to_bucket() uses node_position().  */
-  add_to_bucket (list, new_node);
-  hash_resize_after_add (list);
-#endif
-
-  return new_node;
-}
-
-static gl_list_node_t
-gl_tree_add_before (gl_list_t list, gl_list_node_t node, const void *elt)
+static void
+gl_tree_remove_node_from_tree (gl_list_t list, gl_list_node_t node)
 {
-  /* Create new node.  */
-  gl_list_node_t new_node = XMALLOC (struct gl_list_node_impl);
-  bool height_inc;
-
-  new_node->left = NULL;
-  new_node->right = NULL;
-  new_node->balance = 0;
-  new_node->branch_size = 1;
-  new_node->value = elt;
-#if WITH_HASHTABLE
-  new_node->h.hashcode =
-    (list->base.hashcode_fn != NULL
-     ? list->base.hashcode_fn (new_node->value)
-     : (size_t)(uintptr_t) new_node->value);
-#endif
-
-  /* Add it to the tree.  */
-  if (node->left == NULL)
-    {
-      node->left = new_node;
-      node->balance--;
-      height_inc = (node->right == NULL);
-    }
-  else
-    {
-      for (node = node->left; node->right != NULL; )
-        node = node->right;
-      node->right = new_node;
-      node->balance++;
-      height_inc = (node->left == NULL);
-    }
-  new_node->parent = node;
-
-  /* Update branch_size fields of the parent nodes.  */
-  {
-    gl_list_node_t p;
-
-    for (p = node; p != NULL; p = p->parent)
-      p->branch_size++;
-  }
-
-  /* Rebalance.  */
-  if (height_inc && node->parent != NULL)
-    rebalance (list, node, 1, node->parent);
-
-#if WITH_HASHTABLE
-  /* Add node to the hash table.
-     Note that this is only possible _after_ the node has been added to the
-     tree structure, because add_to_bucket() uses node_position().  */
-  add_to_bucket (list, new_node);
-  hash_resize_after_add (list);
-#endif
-
-  return new_node;
-}
-
-static gl_list_node_t
-gl_tree_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);
-  bool height_inc;
-
-  new_node->left = NULL;
-  new_node->right = NULL;
-  new_node->balance = 0;
-  new_node->branch_size = 1;
-  new_node->value = elt;
-#if WITH_HASHTABLE
-  new_node->h.hashcode =
-    (list->base.hashcode_fn != NULL
-     ? list->base.hashcode_fn (new_node->value)
-     : (size_t)(uintptr_t) new_node->value);
-#endif
-
-  /* Add it to the tree.  */
-  if (node->right == NULL)
-    {
-      node->right = new_node;
-      node->balance++;
-      height_inc = (node->left == NULL);
-    }
-  else
-    {
-      for (node = node->right; node->left != NULL; )
-        node = node->left;
-      node->left = new_node;
-      node->balance--;
-      height_inc = (node->right == NULL);
-    }
-  new_node->parent = node;
-
-  /* Update branch_size fields of the parent nodes.  */
-  {
-    gl_list_node_t p;
-
-    for (p = node; p != NULL; p = p->parent)
-      p->branch_size++;
-  }
-
-  /* Rebalance.  */
-  if (height_inc && node->parent != NULL)
-    rebalance (list, node, 1, node->parent);
-
-#if WITH_HASHTABLE
-  /* Add node to the hash table.
-     Note that this is only possible _after_ the node has been added to the
-     tree structure, because add_to_bucket() uses node_position().  */
-  add_to_bucket (list, new_node);
-  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;
+  gl_list_node_t parent = node->parent;
 
   if (node->left == NULL)
     {
@@ -738,9 +532,278 @@
          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;
+static gl_list_node_t
+gl_tree_nx_add_first (gl_list_t list, const void *elt)
+{
+  /* Create new node.  */
+  gl_list_node_t new_node =
+    (struct gl_list_node_impl *) 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;
+  new_node->branch_size = 1;
+  new_node->value = elt;
+#if WITH_HASHTABLE
+  new_node->h.hashcode =
+    (list->base.hashcode_fn != NULL
+     ? list->base.hashcode_fn (new_node->value)
+     : (size_t)(uintptr_t) new_node->value);
+#endif
+
+  /* Add it to the tree.  */
+  if (list->root == NULL)
+    {
+      list->root = new_node;
+      new_node->parent = NULL;
+    }
+  else
+    {
+      gl_list_node_t node;
+
+      for (node = list->root; node->left != NULL; )
+        node = node->left;
+
+      node->left = new_node;
+      new_node->parent = node;
+      node->balance--;
+
+      /* Update branch_size fields of the parent nodes.  */
+      {
+        gl_list_node_t p;
+
+        for (p = node; p != NULL; p = p->parent)
+          p->branch_size++;
+      }
+
+      /* Rebalance.  */
+      if (node->right == NULL && node->parent != NULL)
+        rebalance (list, node, 1, node->parent);
+    }
+
+#if WITH_HASHTABLE
+  /* Add node to the hash table.
+     Note that this is only possible _after_ the node has been added to the
+     tree structure, because add_to_bucket() uses node_position().  */
+  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 gl_list_node_t
+gl_tree_nx_add_last (gl_list_t list, const void *elt)
+{
+  /* Create new node.  */
+  gl_list_node_t new_node =
+    (struct gl_list_node_impl *) 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;
+  new_node->branch_size = 1;
+  new_node->value = elt;
+#if WITH_HASHTABLE
+  new_node->h.hashcode =
+    (list->base.hashcode_fn != NULL
+     ? list->base.hashcode_fn (new_node->value)
+     : (size_t)(uintptr_t) new_node->value);
+#endif
+
+  /* Add it to the tree.  */
+  if (list->root == NULL)
+    {
+      list->root = new_node;
+      new_node->parent = NULL;
+    }
+  else
+    {
+      gl_list_node_t node;
+
+      for (node = list->root; node->right != NULL; )
+        node = node->right;
+
+      node->right = new_node;
+      new_node->parent = node;
+      node->balance++;
+
+      /* Update branch_size fields of the parent nodes.  */
+      {
+        gl_list_node_t p;
+
+        for (p = node; p != NULL; p = p->parent)
+          p->branch_size++;
+      }
+
+      /* Rebalance.  */
+      if (node->left == NULL && node->parent != NULL)
+        rebalance (list, node, 1, node->parent);
+    }
+
+#if WITH_HASHTABLE
+  /* Add node to the hash table.
+     Note that this is only possible _after_ the node has been added to the
+     tree structure, because add_to_bucket() uses node_position().  */
+  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 gl_list_node_t
+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;
+  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;
+  new_node->branch_size = 1;
+  new_node->value = elt;
+#if WITH_HASHTABLE
+  new_node->h.hashcode =
+    (list->base.hashcode_fn != NULL
+     ? list->base.hashcode_fn (new_node->value)
+     : (size_t)(uintptr_t) new_node->value);
+#endif
+
+  /* Add it to the tree.  */
+  if (node->left == NULL)
+    {
+      node->left = new_node;
+      node->balance--;
+      height_inc = (node->right == NULL);
+    }
+  else
+    {
+      for (node = node->left; node->right != NULL; )
+        node = node->right;
+      node->right = new_node;
+      node->balance++;
+      height_inc = (node->left == NULL);
+    }
+  new_node->parent = node;
+
+  /* Update branch_size fields of the parent nodes.  */
+  {
+    gl_list_node_t p;
+
+    for (p = node; p != NULL; p = p->parent)
+      p->branch_size++;
+  }
+
+  /* Rebalance.  */
+  if (height_inc && node->parent != NULL)
+    rebalance (list, node, 1, node->parent);
+
+#if WITH_HASHTABLE
+  /* Add node to the hash table.
+     Note that this is only possible _after_ the node has been added to the
+     tree structure, because add_to_bucket() uses node_position().  */
+  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 gl_list_node_t
+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;
+  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;
+  new_node->branch_size = 1;
+  new_node->value = elt;
+#if WITH_HASHTABLE
+  new_node->h.hashcode =
+    (list->base.hashcode_fn != NULL
+     ? list->base.hashcode_fn (new_node->value)
+     : (size_t)(uintptr_t) new_node->value);
+#endif
+
+  /* Add it to the tree.  */
+  if (node->right == NULL)
+    {
+      node->right = new_node;
+      node->balance++;
+      height_inc = (node->left == NULL);
+    }
+  else
+    {
+      for (node = node->right; node->left != NULL; )
+        node = node->left;
+      node->left = new_node;
+      node->balance--;
+      height_inc = (node->right == NULL);
+    }
+  new_node->parent = node;
+
+  /* Update branch_size fields of the parent nodes.  */
+  {
+    gl_list_node_t p;
+
+    for (p = node; p != NULL; p = p->parent)
+      p->branch_size++;
+  }
+
+  /* Rebalance.  */
+  if (height_inc && node->parent != NULL)
+    rebalance (list, node, 1, node->parent);
+
+#if WITH_HASHTABLE
+  /* Add node to the hash table.
+     Note that this is only possible _after_ the node has been added to the
+     tree structure, because add_to_bucket() uses node_position().  */
+  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;
+}
--- 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 @@
     {
       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 @@
       list->table_size = new_size;
       free (old_table);
     }
+  return;
+
+ fail:
+  /* Just continue without resizing the table.  */
+  return;
 }
--- 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 @@
   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 @@
     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 @@
          : (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 @@
   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 @@
   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 @@
           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 @@
 #else
   node->value = elt;
 #endif
+  return 0;
 }
 
 static gl_list_node_t
@@ -191,7 +254,7 @@
 }
 
 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 @@
           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 @@
 }
 
 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 @@
      : (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 @@
 }
 
 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 @@
      : (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 @@
 }
 
 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 @@
      : (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 @@
 }
 
 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 @@
      : (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 @@
 }
 
 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 @@
     /* 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 @@
      : (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 @@
 }
 
 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
--- 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 @@
   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 @@
            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 @@
            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 @@
   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 @@
     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 @@
       }
 
       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,233 +632,10 @@
     }
 }
 
-static gl_list_node_t
-gl_tree_add_first (gl_list_t list, const void *elt)
-{
-  /* Create new node.  */
-  gl_list_node_t new_node = XMALLOC (struct gl_list_node_impl);
-
-  new_node->left = NULL;
-  new_node->right = NULL;
-  new_node->branch_size = 1;
-  new_node->value = elt;
-#if WITH_HASHTABLE
-  new_node->h.hashcode =
-    (list->base.hashcode_fn != NULL
-     ? list->base.hashcode_fn (new_node->value)
-     : (size_t)(uintptr_t) new_node->value);
-#endif
-
-  /* Add it to the tree.  */
-  if (list->root == NULL)
-    {
-      new_node->color = BLACK;
-      list->root = new_node;
-      new_node->parent = NULL;
-    }
-  else
-    {
-      gl_list_node_t node;
-
-      for (node = list->root; node->left != NULL; )
-        node = node->left;
-
-      node->left = new_node;
-      new_node->parent = node;
-
-      /* Update branch_size fields of the parent nodes.  */
-      {
-        gl_list_node_t p;
-
-        for (p = node; p != NULL; p = p->parent)
-          p->branch_size++;
-      }
-
-      /* Color and rebalance.  */
-      rebalance_after_add (list, new_node, node);
-    }
-
-#if WITH_HASHTABLE
-  /* Add node to the hash table.
-     Note that this is only possible _after_ the node has been added to the
-     tree structure, because add_to_bucket() uses node_position().  */
-  add_to_bucket (list, new_node);
-  hash_resize_after_add (list);
-#endif
-
-  return new_node;
-}
-
-static gl_list_node_t
-gl_tree_add_last (gl_list_t list, const void *elt)
+static void
+gl_tree_remove_node_from_tree (gl_list_t list, gl_list_node_t node)
 {
-  /* Create new node.  */
-  gl_list_node_t new_node = XMALLOC (struct gl_list_node_impl);
-
-  new_node->left = NULL;
-  new_node->right = NULL;
-  new_node->branch_size = 1;
-  new_node->value = elt;
-#if WITH_HASHTABLE
-  new_node->h.hashcode =
-    (list->base.hashcode_fn != NULL
-     ? list->base.hashcode_fn (new_node->value)
-     : (size_t)(uintptr_t) new_node->value);
-#endif
-
-  /* Add it to the tree.  */
-  if (list->root == NULL)
-    {
-      new_node->color = BLACK;
-      list->root = new_node;
-      new_node->parent = NULL;
-    }
-  else
-    {
-      gl_list_node_t node;
-
-      for (node = list->root; node->right != NULL; )
-        node = node->right;
-
-      node->right = new_node;
-      new_node->parent = node;
-
-      /* Update branch_size fields of the parent nodes.  */
-      {
-        gl_list_node_t p;
-
-        for (p = node; p != NULL; p = p->parent)
-          p->branch_size++;
-      }
-
-      /* Color and rebalance.  */
-      rebalance_after_add (list, new_node, node);
-    }
-
-#if WITH_HASHTABLE
-  /* Add node to the hash table.
-     Note that this is only possible _after_ the node has been added to the
-     tree structure, because add_to_bucket() uses node_position().  */
-  add_to_bucket (list, new_node);
-  hash_resize_after_add (list);
-#endif
-
-  return new_node;
-}
-
-static gl_list_node_t
-gl_tree_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);
-
-  new_node->left = NULL;
-  new_node->right = NULL;
-  new_node->branch_size = 1;
-  new_node->value = elt;
-#if WITH_HASHTABLE
-  new_node->h.hashcode =
-    (list->base.hashcode_fn != NULL
-     ? list->base.hashcode_fn (new_node->value)
-     : (size_t)(uintptr_t) new_node->value);
-#endif
-
-  /* Add it to the tree.  */
-  if (node->left == NULL)
-    node->left = new_node;
-  else
-    {
-      for (node = node->left; node->right != NULL; )
-        node = node->right;
-      node->right = new_node;
-    }
-  new_node->parent = node;
-
-  /* Update branch_size fields of the parent nodes.  */
-  {
-    gl_list_node_t p;
-
-    for (p = node; p != NULL; p = p->parent)
-      p->branch_size++;
-  }
-
-  /* Color and rebalance.  */
-  rebalance_after_add (list, new_node, node);
-
-#if WITH_HASHTABLE
-  /* Add node to the hash table.
-     Note that this is only possible _after_ the node has been added to the
-     tree structure, because add_to_bucket() uses node_position().  */
-  add_to_bucket (list, new_node);
-  hash_resize_after_add (list);
-#endif
-
-  return new_node;
-}
-
-static gl_list_node_t
-gl_tree_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);
-
-  new_node->left = NULL;
-  new_node->right = NULL;
-  new_node->branch_size = 1;
-  new_node->value = elt;
-#if WITH_HASHTABLE
-  new_node->h.hashcode =
-    (list->base.hashcode_fn != NULL
-     ? list->base.hashcode_fn (new_node->value)
-     : (size_t)(uintptr_t) new_node->value);
-#endif
-
-  /* Add it to the tree.  */
-  if (node->right == NULL)
-    node->right = new_node;
-  else
-    {
-      for (node = node->right; node->left != NULL; )
-        node = node->left;
-      node->left = new_node;
-    }
-  new_node->parent = node;
-
-  /* Update branch_size fields of the parent nodes.  */
-  {
-    gl_list_node_t p;
-
-    for (p = node; p != NULL; p = p->parent)
-      p->branch_size++;
-  }
-
-  /* Color and rebalance.  */
-  rebalance_after_add (list, new_node, node);
-
-#if WITH_HASHTABLE
-  /* Add node to the hash table.
-     Note that this is only possible _after_ the node has been added to the
-     tree structure, because add_to_bucket() uses node_position().  */
-  add_to_bucket (list, new_node);
-  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;
+  gl_list_node_t parent = node->parent;
 
   if (node->left == NULL)
     {
@@ -959,9 +775,254 @@
                                     subst_parent != node ? subst_parent : subst);
         }
     }
+}
 
-  if (list->base.dispose_fn != NULL)
-    list->base.dispose_fn (node->value);
-  free (node);
-  return true;
+static gl_list_node_t
+gl_tree_nx_add_first (gl_list_t list, const void *elt)
+{
+  /* Create new node.  */
+  gl_list_node_t new_node =
+    (struct gl_list_node_impl *) malloc (sizeof (struct gl_list_node_impl));
+
+  if (new_node == NULL)
+    return NULL;
+
+  new_node->left = NULL;
+  new_node->right = NULL;
+  new_node->branch_size = 1;
+  new_node->value = elt;
+#if WITH_HASHTABLE
+  new_node->h.hashcode =
+    (list->base.hashcode_fn != NULL
+     ? list->base.hashcode_fn (new_node->value)
+     : (size_t)(uintptr_t) new_node->value);
+#endif
+
+  /* Add it to the tree.  */
+  if (list->root == NULL)
+    {
+      new_node->color = BLACK;
+      list->root = new_node;
+      new_node->parent = NULL;
+    }
+  else
+    {
+      gl_list_node_t node;
+
+      for (node = list->root; node->left != NULL; )
+        node = node->left;
+
+      node->left = new_node;
+      new_node->parent = node;
+
+      /* Update branch_size fields of the parent nodes.  */
+      {
+        gl_list_node_t p;
+
+        for (p = node; p != NULL; p = p->parent)
+          p->branch_size++;
+      }
+
+      /* Color and rebalance.  */
+      rebalance_after_add (list, new_node, node);
+    }
+
+#if WITH_HASHTABLE
+  /* Add node to the hash table.
+     Note that this is only possible _after_ the node has been added to the
+     tree structure, because add_to_bucket() uses node_position().  */
+  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 gl_list_node_t
+gl_tree_nx_add_last (gl_list_t list, const void *elt)
+{
+  /* Create new node.  */
+  gl_list_node_t new_node =
+    (struct gl_list_node_impl *) malloc (sizeof (struct gl_list_node_impl));
+
+  if (new_node == NULL)
+    return NULL;
+
+  new_node->left = NULL;
+  new_node->right = NULL;
+  new_node->branch_size = 1;
+  new_node->value = elt;
+#if WITH_HASHTABLE
+  new_node->h.hashcode =
+    (list->base.hashcode_fn != NULL
+     ? list->base.hashcode_fn (new_node->value)
+     : (size_t)(uintptr_t) new_node->value);
+#endif
+
+  /* Add it to the tree.  */
+  if (list->root == NULL)
+    {
+      new_node->color = BLACK;
+      list->root = new_node;
+      new_node->parent = NULL;
+    }
+  else
+    {
+      gl_list_node_t node;
+
+      for (node = list->root; node->right != NULL; )
+        node = node->right;
+
+      node->right = new_node;
+      new_node->parent = node;
+
+      /* Update branch_size fields of the parent nodes.  */
+      {
+        gl_list_node_t p;
+
+        for (p = node; p != NULL; p = p->parent)
+          p->branch_size++;
+      }
+
+      /* Color and rebalance.  */
+      rebalance_after_add (list, new_node, node);
+    }
+
+#if WITH_HASHTABLE
+  /* Add node to the hash table.
+     Note that this is only possible _after_ the node has been added to the
+     tree structure, because add_to_bucket() uses node_position().  */
+  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 gl_list_node_t
+gl_tree_nx_add_before (gl_list_t list, gl_list_node_t node, const void *elt)
+{
+  /* Create new node.  */
+  gl_list_node_t new_node =
+    (struct gl_list_node_impl *) malloc (sizeof (struct gl_list_node_impl));
+
+  if (new_node == NULL)
+    return NULL;
+
+  new_node->left = NULL;
+  new_node->right = NULL;
+  new_node->branch_size = 1;
+  new_node->value = elt;
+#if WITH_HASHTABLE
+  new_node->h.hashcode =
+    (list->base.hashcode_fn != NULL
+     ? list->base.hashcode_fn (new_node->value)
+     : (size_t)(uintptr_t) new_node->value);
+#endif
+
+  /* Add it to the tree.  */
+  if (node->left == NULL)
+    node->left = new_node;
+  else
+    {
+      for (node = node->left; node->right != NULL; )
+        node = node->right;
+      node->right = new_node;
+    }
+  new_node->parent = node;
+
+  /* Update branch_size fields of the parent nodes.  */
+  {
+    gl_list_node_t p;
+
+    for (p = node; p != NULL; p = p->parent)
+      p->branch_size++;
+  }
+
+  /* Color and rebalance.  */
+  rebalance_after_add (list, new_node, node);
+
+#if WITH_HASHTABLE
+  /* Add node to the hash table.
+     Note that this is only possible _after_ the node has been added to the
+     tree structure, because add_to_bucket() uses node_position().  */
+  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 gl_list_node_t
+gl_tree_nx_add_after (gl_list_t list, gl_list_node_t node, const void *elt)
+{
+  /* Create new node.  */
+  gl_list_node_t new_node =
+    (struct gl_list_node_impl *) malloc (sizeof (struct gl_list_node_impl));
+
+  if (new_node == NULL)
+    return NULL;
+
+  new_node->left = NULL;
+  new_node->right = NULL;
+  new_node->branch_size = 1;
+  new_node->value = elt;
+#if WITH_HASHTABLE
+  new_node->h.hashcode =
+    (list->base.hashcode_fn != NULL
+     ? list->base.hashcode_fn (new_node->value)
+     : (size_t)(uintptr_t) new_node->value);
+#endif
+
+  /* Add it to the tree.  */
+  if (node->right == NULL)
+    node->right = new_node;
+  else
+    {
+      for (node = node->right; node->left != NULL; )
+        node = node->left;
+      node->left = new_node;
+    }
+  new_node->parent = node;
+
+  /* Update branch_size fields of the parent nodes.  */
+  {
+    gl_list_node_t p;
+
+    for (p = node; p != NULL; p = p->parent)
+      p->branch_size++;
+  }
+
+  /* Color and rebalance.  */
+  rebalance_after_add (list, new_node, node);
+
+#if WITH_HASHTABLE
+  /* Add node to the hash table.
+     Note that this is only possible _after_ the node has been added to the
+     tree structure, because add_to_bucket() uses node_position().  */
+  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;
+}
--- 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 @@
 
 /* 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);
+}
--- 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 @@
   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 @@
   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 @@
           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 @@
 #else
   node->value = elt;
 #endif
+  return 0;
 }
 
 static gl_list_node_t
@@ -154,7 +175,7 @@
 }
 
 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 @@
           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 @@
 #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 @@
     /* 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 @@
 }
 
 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 @@
       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);
     }
 }
 
--- a/lib/gl_anytreehash_list1.h
+++ b/lib/gl_anytreehash_list1.h
@@ -104,8 +104,9 @@
    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 @@
                     {
                       /* 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 @@
                         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 @@
   /* 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 @@
 }
 
 /* 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 @@
       for (;;)
         {
           if (stack_ptr == &stack[0])
-            return;
+            goto done;
           stack_ptr--;
           if (!stack_ptr->rightp)
             break;
@@ -294,10 +307,52 @@
         (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
--- 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 @@
 #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 @@
 }
 
 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 @@
   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 @@
   list->allocated = count;
 
   return list;
+
+ fail:
+  free (list);
+  return NULL;
 }
 
 static size_t
@@ -116,14 +130,16 @@
   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 @@
 }
 
 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 @@
   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 @@
   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 @@
 }
 
 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 @@
     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 @@
 }
 
 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 @@
     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 @@
 }
 
 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 @@
     /* 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 @@
 }
 
 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 @@
           break;
         }
     }
-  return gl_array_add_at (list, low, elt);
+  return gl_array_nx_add_at (list, low, elt);
 }
 
 static bool
@@ -624,22 +647,22 @@
 
 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 @@
     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
   };
--- 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"
+
+/* 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_list1.h"
 #include "gl_anytree_list2.h"
 
 /* For debugging.  */
@@ -66,22 +68,22 @@
 
 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 @@
     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
   };
--- 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 @@
 
 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 @@
     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
   };
--- 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 @@
 #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 @@
 }
 
 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 @@
   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 @@
   list->allocated = count;
 
   return list;
+
+ fail:
+  free (list);
+  return NULL;
 }
 
 static size_t
@@ -126,8 +140,9 @@
   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 @@
   if (i >= list->allocated)
     i -= list->allocated;
   list->elements[i] = elt;
+  return 0;
 }
 
 static gl_list_node_t
@@ -184,7 +200,7 @@
 }
 
 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 @@
   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 @@
   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 @@
     }
   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 @@
 }
 
 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 @@
 }
 
 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 @@
     /* 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 @@
 }
 
 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 @@
   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 @@
   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 @@
 }
 
 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 @@
           break;
         }
     }
-  return gl_carray_add_at (list, low, elt);
+  return gl_carray_nx_add_at (list, low, elt);
 }
 
 static bool
@@ -819,22 +840,22 @@
 
 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 @@
     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
   };
--- 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 @@
     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
   };
--- 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 @@
   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 @@
 
 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 @@
     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
   };
--- 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 @@
          ->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_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_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_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
--- a/lib/gl_list.h
+++ b/lib/gl_list.h
@@ -129,11 +129,19 @@
    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 @@
    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 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 @@
 /* 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 @@
 
 /* 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 @@
 /* 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 @@
 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 @@
                                         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_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 @@
          ->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 @@
          ->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 @@
          ->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 @@
                                        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
--- 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"
+
+/* 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_list1.h"
 #include "gl_anytree_list2.h"
 
 /* For debugging.  */
@@ -67,22 +69,22 @@
 
 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 @@
     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
   };
--- 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 @@
 
 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 @@
     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
   };
--- 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 @@
 #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 @@
   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 @@
 }
 
 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 @@
 }
 
 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 @@
 }
 
 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 @@
 
 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 @@
     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 */
--- 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 @@
      - 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
new file mode 100644
--- /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
new file mode 100644
--- /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 */
new file mode 100644
--- /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
new file mode 100644
--- /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 */
--- a/modules/array-list
+++ b/modules/array-list
@@ -7,7 +7,6 @@
 
 Depends-on:
 list
-xalloc
 xsize
 
 configure.ac:
--- a/modules/array-list-tests
+++ b/modules/array-list-tests
@@ -9,5 +9,4 @@
 Makefile.am:
 TESTS += test-array_list
 check_PROGRAMS += test-array_list
-test_array_list_LDADD = $(LDADD) @LIBINTL@
 
--- a/modules/array-oset-tests
+++ b/modules/array-oset-tests
@@ -2,6 +2,7 @@
 tests/test-array_oset.c
 
 Depends-on:
+xlist
 array-list
 progname
 
--- a/modules/avltree-list
+++ b/modules/avltree-list
@@ -11,7 +11,6 @@
 
 Depends-on:
 list
-xalloc
 
 configure.ac:
 
--- a/modules/avltree-list-tests
+++ b/modules/avltree-list-tests
@@ -10,4 +10,3 @@
 Makefile.am:
 TESTS += test-avltree_list
 check_PROGRAMS += test-avltree_list
-test_avltree_list_LDADD = $(LDADD) @LIBINTL@
--- a/modules/avltreehash-list
+++ b/modules/avltreehash-list
@@ -17,7 +17,6 @@
 list
 avltree-oset
 stdint
-xalloc
 xsize
 
 configure.ac:
--- a/modules/avltreehash-list-tests
+++ b/modules/avltreehash-list-tests
@@ -10,5 +10,4 @@
 Makefile.am:
 TESTS += test-avltreehash_list
 check_PROGRAMS += test-avltreehash_list
-test_avltreehash_list_LDADD = $(LDADD) @LIBINTL@
 
--- a/modules/carray-list
+++ b/modules/carray-list
@@ -7,7 +7,6 @@
 
 Depends-on:
 list
-xalloc
 xsize
 
 configure.ac:
--- a/modules/carray-list-tests
+++ b/modules/carray-list-tests
@@ -10,5 +10,4 @@
 Makefile.am:
 TESTS += test-carray_list
 check_PROGRAMS += test-carray_list
-test_carray_list_LDADD = $(LDADD) @LIBINTL@
 
--- a/modules/clean-temp
+++ b/modules/clean-temp
@@ -18,6 +18,7 @@
 xalloc
 xmalloca
 linkedhash-list
+xlist
 gettext-h
 
 configure.ac:
--- a/modules/git-merge-changelog
+++ b/modules/git-merge-changelog
@@ -10,7 +10,7 @@
 progname
 error
 read-file
-list
+xlist
 array-list
 linkedhash-list
 linked-list
--- a/modules/linked-list
+++ b/modules/linked-list
@@ -9,7 +9,6 @@
 
 Depends-on:
 list
-xalloc
 
 configure.ac:
 
--- a/modules/linked-list-tests
+++ b/modules/linked-list-tests
@@ -10,4 +10,3 @@
 Makefile.am:
 TESTS += test-linked_list
 check_PROGRAMS += test-linked_list
-test_linked_list_LDADD = $(LDADD) @LIBINTL@
--- a/modules/linkedhash-list
+++ b/modules/linkedhash-list
@@ -12,7 +12,6 @@
 Depends-on:
 list
 stdint
-xalloc
 xsize
 
 configure.ac:
--- a/modules/linkedhash-list-tests
+++ b/modules/linkedhash-list-tests
@@ -10,4 +10,3 @@
 Makefile.am:
 TESTS += test-linkedhash_list
 check_PROGRAMS += test-linkedhash_list
-test_linkedhash_list_LDADD = $(LDADD) @LIBINTL@
--- a/modules/rbtree-list
+++ b/modules/rbtree-list
@@ -11,7 +11,6 @@
 
 Depends-on:
 list
-xalloc
 
 configure.ac:
 
--- a/modules/rbtree-list-tests
+++ b/modules/rbtree-list-tests
@@ -10,4 +10,3 @@
 Makefile.am:
 TESTS += test-rbtree_list
 check_PROGRAMS += test-rbtree_list
-test_rbtree_list_LDADD = $(LDADD) @LIBINTL@
--- a/modules/rbtreehash-list
+++ b/modules/rbtreehash-list
@@ -17,7 +17,6 @@
 list
 rbtree-oset
 stdint
-xalloc
 xsize
 
 configure.ac:
--- a/modules/rbtreehash-list-tests
+++ b/modules/rbtreehash-list-tests
@@ -10,4 +10,3 @@
 Makefile.am:
 TESTS += test-rbtreehash_list
 check_PROGRAMS += test-rbtreehash_list
-test_rbtreehash_list_LDADD = $(LDADD) @LIBINTL@
--- a/modules/sublist
+++ b/modules/sublist
@@ -7,7 +7,6 @@
 
 Depends-on:
 list
-xalloc
 
 configure.ac:
 
new file mode 100644
--- /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
new file mode 100644
--- /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
--- 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 @@
       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 @@
                 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 @@
             {
               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 @@
             {
               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 @@
               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 @@
               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);
--- 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"
 
--- a/tests/test-avltree_list.c
+++ b/tests/test-avltree_list.c
@@ -91,16 +91,19 @@
       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 @@
                 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 @@
             {
               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 @@
             {
               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 @@
               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 @@
               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);
--- 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 @@
       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 @@
                 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 @@
             {
               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 @@
             {
               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 @@
               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 @@
               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);
--- 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 @@
       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 @@
                 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 @@
             {
               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 @@
             {
               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 @@
               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 @@
               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);
--- 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 @@
       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 @@
                 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 @@
             {
               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 @@
             {
               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 @@
               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 @@
               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);
--- 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 @@
       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 @@
                 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 @@
             {
               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 @@
             {
               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 @@
               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 @@
               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);
--- 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 @@
       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 @@
                 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 @@
             {
               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 @@
             {
               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 @@
               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 @@
               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);
--- 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 @@
       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 @@
                 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 @@
             {
               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 @@
             {
               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 @@
               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 @@
               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);