/* Sequential list data type implemented by a circular array.
- Copyright (C) 2006-2008 Free Software Foundation, Inc.
+ Copyright (C) 2006-2010 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_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;
}
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;
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[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;
if (i >= list->allocated)
i -= list->allocated;
list->elements[i] = elt;
+ return 0;
}
static gl_list_node_t
}
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;
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 ();
+ 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],
}
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;
}
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;
}
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;
/* Invalid argument. */
abort ();
if (count == list->allocated)
- grow (list);
+ if (grow (list) < 0)
+ return NULL;
elements = list->elements;
if (position <= (count / 2))
{
}
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);
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);
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
}
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;
break;
}
}
- return gl_carray_add_at (list, low, elt);
+ return gl_carray_nx_add_at (list, low, elt);
}
static bool
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,
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
};