X-Git-Url: http://erislabs.net/gitweb/?a=blobdiff_plain;f=lib%2Fgl_anyavltree_list2.h;h=90a2b0fbd6c52b771c643523b2f321e5b0081495;hb=5c508f686b9a0f986ac5d941d7be237ec047aedb;hp=1ae6df84b3e6c16d8eba98a466911e0006696a7d;hpb=441aa3044f43e5572f58c354f01e6bc070acd5c7;p=gnulib.git

diff --git a/lib/gl_anyavltree_list2.h b/lib/gl_anyavltree_list2.h
index 1ae6df84b..90a2b0fbd 100644
--- a/lib/gl_anyavltree_list2.h
+++ b/lib/gl_anyavltree_list2.h
@@ -1,5 +1,5 @@
 /* Sequential list data type implemented by a binary tree.
-   Copyright (C) 2006-2007 Free Software Foundation, Inc.
+   Copyright (C) 2006-2007, 2009-2013 Free Software Foundation, Inc.
    Written by Bruno Haible <bruno@clisp.org>, 2006.
 
    This program is free software: you can redistribute it and/or modify
@@ -20,18 +20,24 @@
 /* -------------------------- gl_list_t Data Type -------------------------- */
 
 /* Create a subtree for count >= 1 elements.
-   Its height is h where 2^(h-1) <= count <= 2^h - 1.  */
+   Its height is h where 2^(h-1) <= count <= 2^h - 1.
+   Return NULL upon out-of-memory.  */
 static gl_list_node_t
 create_subtree_with_contents (size_t count, const void **contents)
 {
   size_t half1 = (count - 1) / 2;
   size_t half2 = count / 2;
   /* Note: half1 + half2 = count - 1.  */
-  gl_list_node_t node = XMALLOC (struct gl_list_node_impl);
+  gl_list_node_t node =
+    (struct gl_list_node_impl *) malloc (sizeof (struct gl_list_node_impl));
+  if (node == NULL)
+    return NULL;
 
   if (half1 > 0)
     {
       node->left = create_subtree_with_contents (half1, contents);
+      if (node->left == NULL)
+        goto fail1;
       node->left->parent = node;
     }
   else
@@ -42,6 +48,8 @@ create_subtree_with_contents (size_t count, const void **contents)
   if (half2 > 0)
     {
       node->right = create_subtree_with_contents (half2, contents + half1 + 1);
+      if (node->right == NULL)
+        goto fail2;
       node->right->parent = node;
     }
   else
@@ -56,17 +64,28 @@ create_subtree_with_contents (size_t count, const void **contents)
   node->branch_size = count;
 
   return node;
+
+ fail2:
+  if (node->left != NULL)
+    free_subtree (node->left);
+ fail1:
+  free (node);
+  return NULL;
 }
 
 static gl_list_t
-gl_tree_create (gl_list_implementation_t implementation,
-                gl_listelement_equals_fn equals_fn,
-                gl_listelement_hashcode_fn hashcode_fn,
-                gl_listelement_dispose_fn dispose_fn,
-                bool allow_duplicates,
-                size_t count, const void **contents)
+gl_tree_nx_create (gl_list_implementation_t implementation,
+                   gl_listelement_equals_fn equals_fn,
+                   gl_listelement_hashcode_fn hashcode_fn,
+                   gl_listelement_dispose_fn dispose_fn,
+                   bool allow_duplicates,
+                   size_t count, const void **contents)
 {
-  struct gl_list_impl *list = XMALLOC (struct gl_list_impl);
+  struct gl_list_impl *list =
+    (struct gl_list_impl *) malloc (sizeof (struct gl_list_impl));
+
+  if (list == NULL)
+    return NULL;
 
   list->base.vtable = implementation;
   list->base.equals_fn = equals_fn;
@@ -79,24 +98,44 @@ gl_tree_create (gl_list_implementation_t implementation,
     if (estimate < 10)
       estimate = 10;
     list->table_size = next_prime (estimate);
-    list->table = XCALLOC (list->table_size, gl_hash_entry_t);
+    if (size_overflow_p (xtimes (list->table_size, sizeof (gl_hash_entry_t))))
+      goto fail1;
+    list->table =
+      (gl_hash_entry_t *) calloc (list->table_size, sizeof (gl_hash_entry_t));
+    if (list->table == NULL)
+      goto fail1;
   }
 #endif
   if (count > 0)
     {
       list->root = create_subtree_with_contents (count, contents);
+      if (list->root == NULL)
+        goto fail2;
       list->root->parent = NULL;
 
 #if WITH_HASHTABLE
       /* Now that the tree is built, node_position() works.  Now we can
          add the nodes to the hash table.  */
-      add_nodes_to_buckets (list);
+      if (add_nodes_to_buckets (list) < 0)
+        goto fail3;
 #endif
     }
   else
     list->root = NULL;
 
   return list;
+
+#if WITH_HASHTABLE
+ fail3:
+  free_subtree (list->root);
+#endif
+ fail2:
+#if WITH_HASHTABLE
+  free (list->table);
+ fail1:
+#endif
+  free (list);
+  return NULL;
 }
 
 /* Ensure the tree is balanced, after an insertion or deletion operation.
@@ -368,11 +407,142 @@ rebalance (gl_list_t list,
     }
 }
 
+static void
+gl_tree_remove_node_from_tree (gl_list_t list, gl_list_node_t node)
+{
+  gl_list_node_t parent = node->parent;
+
+  if (node->left == NULL)
+    {
+      /* Replace node with node->right.  */
+      gl_list_node_t child = node->right;
+
+      if (child != NULL)
+        child->parent = parent;
+      if (parent == NULL)
+        list->root = child;
+      else
+        {
+          if (parent->left == node)
+            parent->left = child;
+          else /* parent->right == node */
+            parent->right = child;
+
+          /* Update branch_size fields of the parent nodes.  */
+          {
+            gl_list_node_t p;
+
+            for (p = parent; p != NULL; p = p->parent)
+              p->branch_size--;
+          }
+
+          rebalance (list, child, -1, parent);
+        }
+    }
+  else if (node->right == NULL)
+    {
+      /* It is not absolutely necessary to treat this case.  But the more
+         general case below is more complicated, hence slower.  */
+      /* Replace node with node->left.  */
+      gl_list_node_t child = node->left;
+
+      child->parent = parent;
+      if (parent == NULL)
+        list->root = child;
+      else
+        {
+          if (parent->left == node)
+            parent->left = child;
+          else /* parent->right == node */
+            parent->right = child;
+
+          /* Update branch_size fields of the parent nodes.  */
+          {
+            gl_list_node_t p;
+
+            for (p = parent; p != NULL; p = p->parent)
+              p->branch_size--;
+          }
+
+          rebalance (list, child, -1, parent);
+        }
+    }
+  else
+    {
+      /* Replace node with the rightmost element of the node->left subtree.  */
+      gl_list_node_t subst;
+      gl_list_node_t subst_parent;
+      gl_list_node_t child;
+
+      for (subst = node->left; subst->right != NULL; )
+        subst = subst->right;
+
+      subst_parent = subst->parent;
+
+      child = subst->left;
+
+      /* The case subst_parent == node is special:  If we do nothing special,
+         we get confusion about node->left, subst->left and child->parent.
+           subst_parent == node
+           <==> The 'for' loop above terminated immediately.
+           <==> subst == subst_parent->left
+                [otherwise subst == subst_parent->right]
+         In this case, we would need to first set
+           child->parent = node; node->left = child;
+         and later - when we copy subst into node's position - again
+           child->parent = subst; subst->left = child;
+         Altogether a no-op.  */
+      if (subst_parent != node)
+        {
+          if (child != NULL)
+            child->parent = subst_parent;
+          subst_parent->right = child;
+        }
+
+      /* Update branch_size fields of the parent nodes.  */
+      {
+        gl_list_node_t p;
+
+        for (p = subst_parent; p != NULL; p = p->parent)
+          p->branch_size--;
+      }
+
+      /* Copy subst into node's position.
+         (This is safer than to copy subst's value into node, keep node in
+         place, and free subst.)  */
+      if (subst_parent != node)
+        {
+          subst->left = node->left;
+          subst->left->parent = subst;
+        }
+      subst->right = node->right;
+      subst->right->parent = subst;
+      subst->balance = node->balance;
+      subst->branch_size = node->branch_size;
+      subst->parent = parent;
+      if (parent == NULL)
+        list->root = subst;
+      else if (parent->left == node)
+        parent->left = subst;
+      else /* parent->right == node */
+        parent->right = subst;
+
+      /* Rebalancing starts at child's parent, that is subst_parent -
+         except when subst_parent == node.  In this case, we need to use
+         its replacement, subst.  */
+      rebalance (list, child, -1, subst_parent != node ? subst_parent : subst);
+    }
+}
+
 static gl_list_node_t
-gl_tree_add_first (gl_list_t list, const void *elt)
+gl_tree_nx_add_first (gl_list_t list, const void *elt)
 {
   /* Create new node.  */
-  gl_list_node_t new_node = XMALLOC (struct gl_list_node_impl);
+  gl_list_node_t new_node =
+    (struct gl_list_node_impl *) malloc (sizeof (struct gl_list_node_impl));
+
+  if (new_node == NULL)
+    return NULL;
 
   new_node->left = NULL;
   new_node->right = NULL;
@@ -420,7 +590,12 @@ gl_tree_add_first (gl_list_t list, const void *elt)
   /* Add node to the hash table.
      Note that this is only possible _after_ the node has been added to the
      tree structure, because add_to_bucket() uses node_position().  */
-  add_to_bucket (list, new_node);
+  if (add_to_bucket (list, new_node) < 0)
+    {
+      gl_tree_remove_node_from_tree (list, new_node);
+      free (new_node);
+      return NULL;
+    }
   hash_resize_after_add (list);
 #endif
 
@@ -428,10 +603,14 @@ gl_tree_add_first (gl_list_t list, const void *elt)
 }
 
 static gl_list_node_t
-gl_tree_add_last (gl_list_t list, const void *elt)
+gl_tree_nx_add_last (gl_list_t list, const void *elt)
 {
   /* Create new node.  */
-  gl_list_node_t new_node = XMALLOC (struct gl_list_node_impl);
+  gl_list_node_t new_node =
+    (struct gl_list_node_impl *) malloc (sizeof (struct gl_list_node_impl));
+
+  if (new_node == NULL)
+    return NULL;
 
   new_node->left = NULL;
   new_node->right = NULL;
@@ -479,7 +658,12 @@ gl_tree_add_last (gl_list_t list, const void *elt)
   /* Add node to the hash table.
      Note that this is only possible _after_ the node has been added to the
      tree structure, because add_to_bucket() uses node_position().  */
-  add_to_bucket (list, new_node);
+  if (add_to_bucket (list, new_node) < 0)
+    {
+      gl_tree_remove_node_from_tree (list, new_node);
+      free (new_node);
+      return NULL;
+    }
   hash_resize_after_add (list);
 #endif
 
@@ -487,12 +671,17 @@ gl_tree_add_last (gl_list_t list, const void *elt)
 }
 
 static gl_list_node_t
-gl_tree_add_before (gl_list_t list, gl_list_node_t node, const void *elt)
+gl_tree_nx_add_before (gl_list_t list, gl_list_node_t node, const void *elt)
 {
   /* Create new node.  */
-  gl_list_node_t new_node = XMALLOC (struct gl_list_node_impl);
+  gl_list_node_t new_node;
   bool height_inc;
 
+  new_node =
+    (struct gl_list_node_impl *) malloc (sizeof (struct gl_list_node_impl));
+  if (new_node == NULL)
+    return NULL;
+
   new_node->left = NULL;
   new_node->right = NULL;
   new_node->balance = 0;
@@ -538,7 +727,12 @@ gl_tree_add_before (gl_list_t list, gl_list_node_t node, const void *elt)
   /* Add node to the hash table.
      Note that this is only possible _after_ the node has been added to the
      tree structure, because add_to_bucket() uses node_position().  */
-  add_to_bucket (list, new_node);
+  if (add_to_bucket (list, new_node) < 0)
+    {
+      gl_tree_remove_node_from_tree (list, new_node);
+      free (new_node);
+      return NULL;
+    }
   hash_resize_after_add (list);
 #endif
 
@@ -546,12 +740,17 @@ gl_tree_add_before (gl_list_t list, gl_list_node_t node, const void *elt)
 }
 
 static gl_list_node_t
-gl_tree_add_after (gl_list_t list, gl_list_node_t node, const void *elt)
+gl_tree_nx_add_after (gl_list_t list, gl_list_node_t node, const void *elt)
 {
   /* Create new node.  */
-  gl_list_node_t new_node = XMALLOC (struct gl_list_node_impl);
+  gl_list_node_t new_node;
   bool height_inc;
 
+  new_node =
+    (struct gl_list_node_impl *) malloc (sizeof (struct gl_list_node_impl));
+  if (new_node == NULL)
+    return NULL;
+
   new_node->left = NULL;
   new_node->right = NULL;
   new_node->balance = 0;
@@ -597,150 +796,14 @@ gl_tree_add_after (gl_list_t list, gl_list_node_t node, const void *elt)
   /* Add node to the hash table.
      Note that this is only possible _after_ the node has been added to the
      tree structure, because add_to_bucket() uses node_position().  */
-  add_to_bucket (list, new_node);
+  if (add_to_bucket (list, new_node) < 0)
+    {
+      gl_tree_remove_node_from_tree (list, new_node);
+      free (new_node);
+      return NULL;
+    }
   hash_resize_after_add (list);
 #endif
 
   return new_node;
 }
-
-static bool
-gl_tree_remove_node (gl_list_t list, gl_list_node_t node)
-{
-  gl_list_node_t parent;
-
-#if WITH_HASHTABLE
-  /* Remove node from the hash table.
-     Note that this is only possible _before_ the node is removed from the
-     tree structure, because remove_from_bucket() uses node_position().  */
-  remove_from_bucket (list, node);
-#endif
-
-  parent = node->parent;
-
-  if (node->left == NULL)
-    {
-      /* Replace node with node->right.  */
-      gl_list_node_t child = node->right;
-
-      if (child != NULL)
-        child->parent = parent;
-      if (parent == NULL)
-        list->root = child;
-      else
-        {
-          if (parent->left == node)
-            parent->left = child;
-          else /* parent->right == node */
-            parent->right = child;
-
-          /* Update branch_size fields of the parent nodes.  */
-          {
-            gl_list_node_t p;
-
-            for (p = parent; p != NULL; p = p->parent)
-              p->branch_size--;
-          }
-
-          rebalance (list, child, -1, parent);
-        }
-    }
-  else if (node->right == NULL)
-    {
-      /* It is not absolutely necessary to treat this case.  But the more
-         general case below is more complicated, hence slower.  */
-      /* Replace node with node->left.  */
-      gl_list_node_t child = node->left;
-
-      child->parent = parent;
-      if (parent == NULL)
-        list->root = child;
-      else
-        {
-          if (parent->left == node)
-            parent->left = child;
-          else /* parent->right == node */
-            parent->right = child;
-
-          /* Update branch_size fields of the parent nodes.  */
-          {
-            gl_list_node_t p;
-
-            for (p = parent; p != NULL; p = p->parent)
-              p->branch_size--;
-          }
-
-          rebalance (list, child, -1, parent);
-        }
-    }
-  else
-    {
-      /* Replace node with the rightmost element of the node->left subtree.  */
-      gl_list_node_t subst;
-      gl_list_node_t subst_parent;
-      gl_list_node_t child;
-
-      for (subst = node->left; subst->right != NULL; )
-        subst = subst->right;
-
-      subst_parent = subst->parent;
-
-      child = subst->left;
-
-      /* The case subst_parent == node is special:  If we do nothing special,
-         we get confusion about node->left, subst->left and child->parent.
-           subst_parent == node
-           <==> The 'for' loop above terminated immediately.
-           <==> subst == subst_parent->left
-                [otherwise subst == subst_parent->right]
-         In this case, we would need to first set
-           child->parent = node; node->left = child;
-         and later - when we copy subst into node's position - again
-           child->parent = subst; subst->left = child;
-         Altogether a no-op.  */
-      if (subst_parent != node)
-        {
-          if (child != NULL)
-            child->parent = subst_parent;
-          subst_parent->right = child;
-        }
-
-      /* Update branch_size fields of the parent nodes.  */
-      {
-        gl_list_node_t p;
-
-        for (p = subst_parent; p != NULL; p = p->parent)
-          p->branch_size--;
-      }
-
-      /* Copy subst into node's position.
-         (This is safer than to copy subst's value into node, keep node in
-         place, and free subst.)  */
-      if (subst_parent != node)
-        {
-          subst->left = node->left;
-          subst->left->parent = subst;
-        }
-      subst->right = node->right;
-      subst->right->parent = subst;
-      subst->balance = node->balance;
-      subst->branch_size = node->branch_size;
-      subst->parent = parent;
-      if (parent == NULL)
-        list->root = subst;
-      else if (parent->left == node)
-        parent->left = subst;
-      else /* parent->right == node */
-        parent->right = subst;
-
-      /* Rebalancing starts at child's parent, that is subst_parent -
-         except when subst_parent == node.  In this case, we need to use
-         its replacement, subst.  */
-      rebalance (list, child, -1, subst_parent != node ? subst_parent : subst);
-    }
-
-  if (list->base.dispose_fn != NULL)
-    list->base.dispose_fn (node->value);
-  free (node);
-  return true;
-}