X-Git-Url: http://erislabs.net/gitweb/?a=blobdiff_plain;f=lib%2Fgl_anytreehash_list1.h;h=d3b8a0623481ebf60c4d89f84b0e40b2fdfc9da8;hb=b344de996cd51f8a2f2558a3172016b64d99c622;hp=45418cfb2c297931cb7323a9fc1b0b7d13563e2e;hpb=441aa3044f43e5572f58c354f01e6bc070acd5c7;p=gnulib.git

diff --git a/lib/gl_anytreehash_list1.h b/lib/gl_anytreehash_list1.h
index 45418cfb2..d3b8a0623 100644
--- a/lib/gl_anytreehash_list1.h
+++ b/lib/gl_anytreehash_list1.h
@@ -1,5 +1,5 @@
 /* Sequential list data type implemented by a hash table with a binary tree.
-   Copyright (C) 2006-2007 Free Software Foundation, Inc.
+   Copyright (C) 2006-2007, 2009-2011 Free Software Foundation, Inc.
    Written by Bruno Haible <bruno@clisp.org>, 2006.
 
    This program is free software: you can redistribute it and/or modify
@@ -101,11 +101,12 @@ gl_oset_first (gl_oset_t set)
 
 /* Add a node to the hash table structure.
    If duplicates are allowed, this function performs in average time
-   O((log n)^2): gl_oset_add may need to add an element to an ordered set of
-   size O(n), needing O(log n) comparison function calls.  The comparison
+   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,8 +135,7 @@ add_to_bucket (gl_list_t list, gl_list_node_t new_node)
                     {
                       /* Found already multiple nodes with the same value.
                          Add the new_node to it.  */
-                      gl_oset_add (nodes, new_node);
-                      return;
+                      return gl_oset_nx_add (nodes, new_node);
                     }
                 }
               else
@@ -150,19 +150,30 @@ add_to_bucket (gl_list_t list, gl_list_node_t new_node)
                       struct gl_multiple_nodes *multi_entry;
 
                       nodes =
-                        gl_oset_create_empty (OSET_TREE_FLAVOR,
-                                              compare_by_position, NULL);
+                        gl_oset_nx_create_empty (OSET_TREE_FLAVOR,
+                                                 compare_by_position, NULL);
+                      if (nodes == NULL)
+                        return -1;
 
-                      gl_oset_add (nodes, node);
-                      gl_oset_add (nodes, new_node);
+                      if (gl_oset_nx_add (nodes, node) < 0)
+                        goto fail;
+                      if (gl_oset_nx_add (nodes, new_node) < 0)
+                        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;
                     }
                 }
             }
@@ -171,7 +182,13 @@ add_to_bucket (gl_list_t list, gl_list_node_t new_node)
   /* If no duplicates are allowed, multiple nodes are not needed.  */
   new_node->h.hash_next = list->table[bucket];
   list->table[bucket] = &new_node->h;
+  return 0;
 }
+/* Tell GCC that the likely return value is 0.  */
+#if __GNUC__ >= 3
+# define add_to_bucket(list,node) \
+    __builtin_expect ((add_to_bucket) (list, node), 0)
+#endif
 
 /* Remove a node from the hash table structure.
    If duplicates are allowed, this function performs in average time
@@ -253,8 +270,9 @@ remove_from_bucket (gl_list_t list, gl_list_node_t old_node)
 }
 
 /* Build up the hash table during initialization: Store all the nodes of
-   list->root in the hash table.  */
-static inline void
+   list->root in the hash table.
+   Return 0 upon success, -1 upon out-of-memory.  */
+static inline int
 add_nodes_to_buckets (gl_list_t list)
 {
   /* Iterate across all nodes.  */
@@ -278,7 +296,7 @@ add_nodes_to_buckets (gl_list_t list)
       for (;;)
         {
           if (stack_ptr == &stack[0])
-            return;
+            goto done;
           stack_ptr--;
           if (!stack_ptr->rightp)
             break;
@@ -289,10 +307,52 @@ add_nodes_to_buckets (gl_list_t list)
         (list->base.hashcode_fn != NULL
          ? list->base.hashcode_fn (node->value)
          : (size_t)(uintptr_t) node->value);
-      add_to_bucket (list, node);
+      if (add_to_bucket (list, node) < 0)
+        goto fail;
       /* Descend on right branch.  */
       stack_ptr->rightp = true;
       node = node->right;
       stack_ptr++;
     }
+ done:
+  return 0;
+
+ fail:
+  /* Undo everything.  */
+  for (;;)
+    {
+      /* Descend on left branch.  */
+      stack_ptr->rightp = false;
+      node = node->left;
+      stack_ptr++;
+      /* Descend on right branch.  */
+      for (;;)
+        {
+          if (node == NULL)
+            break;
+          stack_ptr->node = node;
+          stack_ptr->rightp = true;
+          node = node->right;
+          stack_ptr++;
+        }
+      /* Climb up again.  */
+      for (;;)
+        {
+          if (stack_ptr == &stack[0])
+            goto fail_done;
+          stack_ptr--;
+          if (stack_ptr->rightp)
+            break;
+        }
+      node = stack_ptr->node;
+      /* Remove the current node from the hash table.  */
+      remove_from_bucket (list, node);
+    }
+ fail_done:
+  return -1;
 }
+/* Tell GCC that the likely return value is 0.  */
+#if __GNUC__ >= 3
+# define add_nodes_to_buckets(list) \
+    __builtin_expect ((add_nodes_to_buckets) (list), 0)
+#endif