/* Sequential list data type implemented by an array.
- Copyright (C) 2006-2008 Free Software Foundation, Inc.
+ Copyright (C) 2006-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
/* Get memcpy. */
#include <string.h>
-#include "xalloc.h"
-
/* Checked size_t computations. */
#include "xsize.h"
#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;
}
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;
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
list->allocated = count;
return list;
+
+ fail:
+ free (list);
+ return NULL;
}
static size_t
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
}
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;
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;
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];
}
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);
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];
}
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);
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];
}
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;
/* 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];
}
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;
break;
}
}
- return gl_array_add_at (list, low, elt);
+ return gl_array_nx_add_at (list, low, elt);
}
static bool
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,
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
};