X-Git-Url: http://erislabs.net/gitweb/?a=blobdiff_plain;f=lib%2Fgl_array_list.c;h=b61b6cae26658c651392da3216da65d7a81dafe1;hb=cd56634a4a8179fd5a4419fbb3e27211b042ab1c;hp=deb83aea60177621d4b3616d25da958785c06e03;hpb=57fdfd3f8ec62b105c53bcdf6f127c35c7fe7391;p=gnulib.git

diff --git a/lib/gl_array_list.c b/lib/gl_array_list.c
index deb83aea6..b61b6cae2 100644
--- a/lib/gl_array_list.c
+++ b/lib/gl_array_list.c
@@ -1,5 +1,5 @@
 /* Sequential list data type implemented by an array.
-   Copyright (C) 2006-2007 Free Software Foundation, Inc.
+   Copyright (C) 2006-2014 Free Software Foundation, Inc.
    Written by Bruno Haible <bruno@clisp.org>, 2006.
 
    This program is free software: you can redistribute it and/or modify
@@ -24,8 +24,6 @@
 /* Get memcpy.  */
 #include <string.h>
 
-#include "xalloc.h"
-
 /* Checked size_t computations.  */
 #include "xsize.h"
 
@@ -52,13 +50,17 @@ struct gl_list_impl
 #define NODE_TO_INDEX(node) ((uintptr_t)(node) - 1)
 
 static gl_list_t
-gl_array_create_empty (gl_list_implementation_t implementation,
-		       gl_listelement_equals_fn equals_fn,
-		       gl_listelement_hashcode_fn hashcode_fn,
-		       gl_listelement_dispose_fn dispose_fn,
-		       bool allow_duplicates)
+gl_array_nx_create_empty (gl_list_implementation_t implementation,
+                          gl_listelement_equals_fn equals_fn,
+                          gl_listelement_hashcode_fn hashcode_fn,
+                          gl_listelement_dispose_fn dispose_fn,
+                          bool allow_duplicates)
 {
-  struct gl_list_impl *list = XMALLOC (struct gl_list_impl);
+  struct gl_list_impl *list =
+    (struct gl_list_impl *) malloc (sizeof (struct gl_list_impl));
+
+  if (list == NULL)
+    return NULL;
 
   list->base.vtable = implementation;
   list->base.equals_fn = equals_fn;
@@ -73,14 +75,18 @@ gl_array_create_empty (gl_list_implementation_t implementation,
 }
 
 static gl_list_t
-gl_array_create (gl_list_implementation_t implementation,
-		 gl_listelement_equals_fn equals_fn,
-		 gl_listelement_hashcode_fn hashcode_fn,
-		 gl_listelement_dispose_fn dispose_fn,
-		 bool allow_duplicates,
-		 size_t count, const void **contents)
+gl_array_nx_create (gl_list_implementation_t implementation,
+                    gl_listelement_equals_fn equals_fn,
+                    gl_listelement_hashcode_fn hashcode_fn,
+                    gl_listelement_dispose_fn dispose_fn,
+                    bool allow_duplicates,
+                    size_t count, const void **contents)
 {
-  struct gl_list_impl *list = XMALLOC (struct gl_list_impl);
+  struct gl_list_impl *list =
+    (struct gl_list_impl *) malloc (sizeof (struct gl_list_impl));
+
+  if (list == NULL)
+    return NULL;
 
   list->base.vtable = implementation;
   list->base.equals_fn = equals_fn;
@@ -89,7 +95,11 @@ gl_array_create (gl_list_implementation_t implementation,
   list->base.allow_duplicates = allow_duplicates;
   if (count > 0)
     {
-      list->elements = XNMALLOC (count, const void *);
+      if (size_overflow_p (xtimes (count, sizeof (const void *))))
+        goto fail;
+      list->elements = (const void **) malloc (count * sizeof (const void *));
+      if (list->elements == NULL)
+        goto fail;
       memcpy (list->elements, contents, count * sizeof (const void *));
     }
   else
@@ -98,6 +108,10 @@ gl_array_create (gl_list_implementation_t implementation,
   list->allocated = count;
 
   return list;
+
+ fail:
+  free (list);
+  return NULL;
 }
 
 static size_t
@@ -116,6 +130,18 @@ gl_array_node_value (gl_list_t list, gl_list_node_t node)
   return list->elements[index];
 }
 
+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
 gl_array_next_node (gl_list_t list, gl_list_node_t node)
 {
@@ -155,7 +181,7 @@ gl_array_get_at (gl_list_t list, size_t position)
 }
 
 static gl_list_node_t
-gl_array_set_at (gl_list_t list, size_t position, const void *elt)
+gl_array_nx_set_at (gl_list_t list, size_t position, const void *elt)
 {
   size_t count = list->count;
 
@@ -168,7 +194,7 @@ gl_array_set_at (gl_list_t list, size_t position, const void *elt)
 
 static size_t
 gl_array_indexof_from_to (gl_list_t list, size_t start_index, size_t end_index,
-			  const void *elt)
+                          const void *elt)
 {
   size_t count = list->count;
 
@@ -180,45 +206,46 @@ gl_array_indexof_from_to (gl_list_t list, size_t start_index, size_t end_index,
     {
       gl_listelement_equals_fn equals = list->base.equals_fn;
       if (equals != NULL)
-	{
-	  size_t i;
-
-	  for (i = start_index;;)
-	    {
-	      if (equals (elt, list->elements[i]))
-		return i;
-	      i++;
-	      if (i == end_index)
-		break;
-	    }
-	}
+        {
+          size_t i;
+
+          for (i = start_index;;)
+            {
+              if (equals (elt, list->elements[i]))
+                return i;
+              i++;
+              if (i == end_index)
+                break;
+            }
+        }
       else
-	{
-	  size_t i;
-
-	  for (i = start_index;;)
-	    {
-	      if (elt == list->elements[i])
-		return i;
-	      i++;
-	      if (i == end_index)
-		break;
-	    }
-	}
+        {
+          size_t i;
+
+          for (i = start_index;;)
+            {
+              if (elt == list->elements[i])
+                return i;
+              i++;
+              if (i == end_index)
+                break;
+            }
+        }
     }
   return (size_t)(-1);
 }
 
 static gl_list_node_t
 gl_array_search_from_to (gl_list_t list, size_t start_index, size_t end_index,
-			 const void *elt)
+                         const void *elt)
 {
   size_t index = gl_array_indexof_from_to (list, start_index, end_index, elt);
   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;
@@ -230,24 +257,26 @@ grow (gl_list_t list)
   memory_size = xtimes (new_allocated, sizeof (const void *));
   if (size_overflow_p (memory_size))
     /* Overflow, would lead to out of memory.  */
-    xalloc_die ();
-  memory = (const void **) xrealloc (list->elements, memory_size);
+    return -1;
+  memory = (const void **) realloc (list->elements, memory_size);
   if (memory == NULL)
     /* Out of memory.  */
-    xalloc_die ();
+    return -1;
   list->elements = memory;
   list->allocated = new_allocated;
+  return 0;
 }
 
 static gl_list_node_t
-gl_array_add_first (gl_list_t list, const void *elt)
+gl_array_nx_add_first (gl_list_t list, const void *elt)
 {
   size_t count = list->count;
   const void **elements;
   size_t i;
 
   if (count == list->allocated)
-    grow (list);
+    if (grow (list) < 0)
+      return NULL;
   elements = list->elements;
   for (i = count; i > 0; i--)
     elements[i] = elements[i - 1];
@@ -257,19 +286,20 @@ gl_array_add_first (gl_list_t list, const void *elt)
 }
 
 static gl_list_node_t
-gl_array_add_last (gl_list_t list, const void *elt)
+gl_array_nx_add_last (gl_list_t list, const void *elt)
 {
   size_t count = list->count;
 
   if (count == list->allocated)
-    grow (list);
+    if (grow (list) < 0)
+      return NULL;
   list->elements[count] = elt;
   list->count = count + 1;
   return INDEX_TO_NODE (count);
 }
 
 static gl_list_node_t
-gl_array_add_before (gl_list_t list, gl_list_node_t node, const void *elt)
+gl_array_nx_add_before (gl_list_t list, gl_list_node_t node, const void *elt)
 {
   size_t count = list->count;
   uintptr_t index = NODE_TO_INDEX (node);
@@ -282,7 +312,8 @@ gl_array_add_before (gl_list_t list, gl_list_node_t node, const void *elt)
     abort ();
   position = index;
   if (count == list->allocated)
-    grow (list);
+    if (grow (list) < 0)
+      return NULL;
   elements = list->elements;
   for (i = count; i > position; i--)
     elements[i] = elements[i - 1];
@@ -292,7 +323,7 @@ gl_array_add_before (gl_list_t list, gl_list_node_t node, const void *elt)
 }
 
 static gl_list_node_t
-gl_array_add_after (gl_list_t list, gl_list_node_t node, const void *elt)
+gl_array_nx_add_after (gl_list_t list, gl_list_node_t node, const void *elt)
 {
   size_t count = list->count;
   uintptr_t index = NODE_TO_INDEX (node);
@@ -305,7 +336,8 @@ gl_array_add_after (gl_list_t list, gl_list_node_t node, const void *elt)
     abort ();
   position = index + 1;
   if (count == list->allocated)
-    grow (list);
+    if (grow (list) < 0)
+      return NULL;
   elements = list->elements;
   for (i = count; i > position; i--)
     elements[i] = elements[i - 1];
@@ -315,7 +347,7 @@ gl_array_add_after (gl_list_t list, gl_list_node_t node, const void *elt)
 }
 
 static gl_list_node_t
-gl_array_add_at (gl_list_t list, size_t position, const void *elt)
+gl_array_nx_add_at (gl_list_t list, size_t position, const void *elt)
 {
   size_t count = list->count;
   const void **elements;
@@ -325,7 +357,8 @@ gl_array_add_at (gl_list_t list, size_t position, const void *elt)
     /* Invalid argument.  */
     abort ();
   if (count == list->allocated)
-    grow (list);
+    if (grow (list) < 0)
+      return NULL;
   elements = list->elements;
   for (i = count; i > position; i--)
     elements[i] = elements[i - 1];
@@ -391,19 +424,19 @@ gl_array_list_free (gl_list_t list)
   if (list->elements != NULL)
     {
       if (list->base.dispose_fn != NULL)
-	{
-	  size_t count = list->count;
-
-	  if (count > 0)
-	    {
-	      gl_listelement_dispose_fn dispose = list->base.dispose_fn;
-	      const void **elements = list->elements;
-
-	      do
-		dispose (*elements++);
-	      while (--count > 0);
-	    }
-	}
+        {
+          size_t count = list->count;
+
+          if (count > 0)
+            {
+              gl_listelement_dispose_fn dispose = list->base.dispose_fn;
+              const void **elements = list->elements;
+
+              do
+                dispose (*elements++);
+              while (--count > 0);
+            }
+        }
       free (list->elements);
     }
   free (list);
@@ -452,14 +485,14 @@ gl_array_iterator_from_to (gl_list_t list, size_t start_index, size_t end_index)
 
 static bool
 gl_array_iterator_next (gl_list_iterator_t *iterator,
-			const void **eltp, gl_list_node_t *nodep)
+                        const void **eltp, gl_list_node_t *nodep)
 {
   gl_list_t list = iterator->list;
   if (iterator->count != list->count)
     {
       if (iterator->count != list->count + 1)
-	/* Concurrent modifications were done on the list.  */
-	abort ();
+        /* Concurrent modifications were done on the list.  */
+        abort ();
       /* The last returned element was removed.  */
       iterator->count--;
       iterator->p = (const void **) iterator->p - 1;
@@ -470,7 +503,7 @@ gl_array_iterator_next (gl_list_iterator_t *iterator,
       const void **p = (const void **) iterator->p;
       *eltp = *p;
       if (nodep != NULL)
-	*nodep = INDEX_TO_NODE (p - list->elements);
+        *nodep = INDEX_TO_NODE (p - list->elements);
       iterator->p = p + 1;
       return true;
     }
@@ -487,9 +520,9 @@ gl_array_iterator_free (gl_list_iterator_t *iterator)
 
 static size_t
 gl_array_sortedlist_indexof_from_to (gl_list_t list,
-				     gl_listelement_compar_fn compar,
-				     size_t low, size_t high,
-				     const void *elt)
+                                     gl_listelement_compar_fn compar,
+                                     size_t low, size_t high,
+                                     const void *elt)
 {
   if (!(low <= high && high <= list->count))
     /* Invalid arguments.  */
@@ -497,47 +530,47 @@ gl_array_sortedlist_indexof_from_to (gl_list_t list,
   if (low < high)
     {
       /* At each loop iteration, low < high; for indices < low the values
-	 are smaller than ELT; for indices >= high the values are greater
-	 than ELT.  So, if the element occurs in the list, it is at
-	 low <= position < high.  */
+         are smaller than ELT; for indices >= high the values are greater
+         than ELT.  So, if the element occurs in the list, it is at
+         low <= position < high.  */
       do
-	{
-	  size_t mid = low + (high - low) / 2; /* low <= mid < high */
-	  int cmp = compar (list->elements[mid], elt);
-
-	  if (cmp < 0)
-	    low = mid + 1;
-	  else if (cmp > 0)
-	    high = mid;
-	  else /* cmp == 0 */
-	    {
-	      /* We have an element equal to ELT at index MID.  But we need
-		 the minimal such index.  */
-	      high = mid;
-	      /* At each loop iteration, low <= high and
-		   compar (list->elements[high], elt) == 0,
-		 and we know that the first occurrence of the element is at
-		 low <= position <= high.  */
-	      while (low < high)
-		{
-		  size_t mid2 = low + (high - low) / 2; /* low <= mid2 < high */
-		  int cmp2 = compar (list->elements[mid2], elt);
-
-		  if (cmp2 < 0)
-		    low = mid2 + 1;
-		  else if (cmp2 > 0)
-		    /* The list was not sorted.  */
-		    abort ();
-		  else /* cmp2 == 0 */
-		    {
-		      if (mid2 == low)
-			break;
-		      high = mid2 - 1;
-		    }
-		}
-	      return low;
-	    }
-	}
+        {
+          size_t mid = low + (high - low) / 2; /* low <= mid < high */
+          int cmp = compar (list->elements[mid], elt);
+
+          if (cmp < 0)
+            low = mid + 1;
+          else if (cmp > 0)
+            high = mid;
+          else /* cmp == 0 */
+            {
+              /* We have an element equal to ELT at index MID.  But we need
+                 the minimal such index.  */
+              high = mid;
+              /* At each loop iteration, low <= high and
+                   compar (list->elements[high], elt) == 0,
+                 and we know that the first occurrence of the element is at
+                 low <= position <= high.  */
+              while (low < high)
+                {
+                  size_t mid2 = low + (high - low) / 2; /* low <= mid2 < high */
+                  int cmp2 = compar (list->elements[mid2], elt);
+
+                  if (cmp2 < 0)
+                    low = mid2 + 1;
+                  else if (cmp2 > 0)
+                    /* The list was not sorted.  */
+                    abort ();
+                  else /* cmp2 == 0 */
+                    {
+                      if (mid2 == low)
+                        break;
+                      high = mid2 - 1;
+                    }
+                }
+              return low;
+            }
+        }
       while (low < high);
       /* Here low == high.  */
     }
@@ -546,17 +579,17 @@ gl_array_sortedlist_indexof_from_to (gl_list_t list,
 
 static size_t
 gl_array_sortedlist_indexof (gl_list_t list, gl_listelement_compar_fn compar,
-			     const void *elt)
+                             const void *elt)
 {
   return gl_array_sortedlist_indexof_from_to (list, compar, 0, list->count,
-					      elt);
+                                              elt);
 }
 
 static gl_list_node_t
 gl_array_sortedlist_search_from_to (gl_list_t list,
-				    gl_listelement_compar_fn compar,
-				    size_t low, size_t high,
-				    const void *elt)
+                                    gl_listelement_compar_fn compar,
+                                    size_t low, size_t high,
+                                    const void *elt)
 {
   size_t index =
     gl_array_sortedlist_indexof_from_to (list, compar, low, high, elt);
@@ -565,7 +598,7 @@ gl_array_sortedlist_search_from_to (gl_list_t list,
 
 static gl_list_node_t
 gl_array_sortedlist_search (gl_list_t list, gl_listelement_compar_fn compar,
-			    const void *elt)
+                            const void *elt)
 {
   size_t index =
     gl_array_sortedlist_indexof_from_to (list, compar, 0, list->count, elt);
@@ -573,8 +606,8 @@ gl_array_sortedlist_search (gl_list_t list, gl_listelement_compar_fn compar,
 }
 
 static gl_list_node_t
-gl_array_sortedlist_add (gl_list_t list, gl_listelement_compar_fn compar,
-			 const void *elt)
+gl_array_sortedlist_nx_add (gl_list_t list, gl_listelement_compar_fn compar,
+                            const void *elt)
 {
   size_t count = list->count;
   size_t low = 0;
@@ -588,21 +621,21 @@ gl_array_sortedlist_add (gl_list_t list, gl_listelement_compar_fn compar,
       int cmp = compar (list->elements[mid], elt);
 
       if (cmp < 0)
-	low = mid + 1;
+        low = mid + 1;
       else if (cmp > 0)
-	high = mid;
+        high = mid;
       else /* cmp == 0 */
-	{
-	  low = mid;
-	  break;
-	}
+        {
+          low = mid;
+          break;
+        }
     }
-  return gl_array_add_at (list, low, elt);
+  return gl_array_nx_add_at (list, low, elt);
 }
 
 static bool
 gl_array_sortedlist_remove (gl_list_t list, gl_listelement_compar_fn compar,
-			    const void *elt)
+                            const void *elt)
 {
   size_t index = gl_array_sortedlist_indexof (list, compar, elt);
   if (index == (size_t)(-1))
@@ -614,21 +647,22 @@ gl_array_sortedlist_remove (gl_list_t list, gl_listelement_compar_fn compar,
 
 const struct gl_list_implementation gl_array_list_implementation =
   {
-    gl_array_create_empty,
-    gl_array_create,
+    gl_array_nx_create_empty,
+    gl_array_nx_create,
     gl_array_size,
     gl_array_node_value,
+    gl_array_node_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,
@@ -641,6 +675,6 @@ const struct gl_list_implementation gl_array_list_implementation =
     gl_array_sortedlist_search_from_to,
     gl_array_sortedlist_indexof,
     gl_array_sortedlist_indexof_from_to,
-    gl_array_sortedlist_add,
+    gl_array_sortedlist_nx_add,
     gl_array_sortedlist_remove
   };