/* Sequential list data type backed by another list.
- Copyright (C) 2006-2007 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
+ This program is free software: you can redistribute it and/or modify
it under the terms of the GNU General Public License as published by
- the Free Software Foundation; either version 2, or (at your option)
- any later version.
+ the Free Software Foundation; either version 3 of the License, or
+ (at your option) any later version.
This program is distributed in the hope that it will be useful,
but WITHOUT ANY WARRANTY; without even the implied warranty of
GNU General Public License for more details.
You should have received a copy of the GNU General Public License
- along with this program; if not, write to the Free Software Foundation,
- Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301, USA. */
+ along with this program. If not, see <http://www.gnu.org/licenses/>. */
#include <config.h>
#include <stdlib.h>
-#include "xalloc.h"
-
#ifndef uintptr_t
# define uintptr_t unsigned long
#endif
#define NODE_TO_INDEX(node) ((uintptr_t)(node) - 1)
static gl_list_t
-gl_sublist_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_sublist_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)
{
/* Shouldn't be called. */
abort ();
}
static gl_list_t
-gl_sublist_create_fill (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_sublist_nx_create_fill (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)
{
/* Shouldn't be called. */
abort ();
return gl_list_get_at (list->whole, list->start + index);
}
+static int
+gl_sublist_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->end - list->start))
+ /* Invalid argument. */
+ abort ();
+ if (gl_list_nx_set_at (list->whole, list->start + index, elt) == NULL)
+ return -1;
+ return 0;
+}
+
static gl_list_node_t
gl_sublist_next_node (gl_list_t list, gl_list_node_t node)
{
}
static gl_list_node_t
-gl_sublist_set_at (gl_list_t list, size_t position, const void *elt)
+gl_sublist_nx_set_at (gl_list_t list, size_t position, const void *elt)
{
if (!(position < list->end - list->start))
/* Invalid argument. */
abort ();
- gl_list_set_at (list->whole, list->start + position, elt);
+ if (gl_list_nx_set_at (list->whole, list->start + position, elt) == NULL)
+ return NULL;
return INDEX_TO_NODE (position);
}
static gl_list_node_t
gl_sublist_search_from_to (gl_list_t list, size_t start_index, size_t end_index,
- const void *elt)
+ const void *elt)
{
if (!(start_index <= end_index && end_index <= list->end - list->start))
/* Invalid arguments. */
{
size_t index =
gl_list_indexof_from_to (list->whole,
- list->start + start_index,
- list->start + end_index,
- elt);
+ list->start + start_index,
+ list->start + end_index,
+ elt);
if (index != (size_t)(-1))
return INDEX_TO_NODE (index - list->start);
else
static size_t
gl_sublist_indexof_from_to (gl_list_t list,
- size_t start_index, size_t end_index,
- const void *elt)
+ size_t start_index, size_t end_index,
+ const void *elt)
{
if (!(start_index <= end_index && end_index <= list->end - list->start))
/* Invalid arguments. */
{
size_t index =
gl_list_indexof_from_to (list->whole,
- list->start + start_index,
- list->start + end_index,
- elt);
+ list->start + start_index,
+ list->start + end_index,
+ elt);
if (index != (size_t)(-1))
index -= list->start;
return index;
}
static gl_list_node_t
-gl_sublist_add_first (gl_list_t list, const void *elt)
+gl_sublist_nx_add_first (gl_list_t list, const void *elt)
{
- gl_list_add_at (list->whole, list->start, elt);
+ if (gl_list_nx_add_at (list->whole, list->start, elt) == NULL)
+ return NULL;
list->end++;
return INDEX_TO_NODE (0);
}
static gl_list_node_t
-gl_sublist_add_last (gl_list_t list, const void *elt)
+gl_sublist_nx_add_last (gl_list_t list, const void *elt)
{
- gl_list_add_at (list->whole, list->end, elt);
+ if (gl_list_nx_add_at (list->whole, list->end, elt) == NULL)
+ return NULL;
list->end++;
return INDEX_TO_NODE (list->end - list->start - 1);
}
static gl_list_node_t
-gl_sublist_add_before (gl_list_t list, gl_list_node_t node, const void *elt)
+gl_sublist_nx_add_before (gl_list_t list, gl_list_node_t node, const void *elt)
{
size_t position = NODE_TO_INDEX (node);
if (!(position < list->end - list->start))
/* Invalid argument. */
abort ();
- gl_list_add_at (list->whole, list->start + position, elt);
+ if (gl_list_nx_add_at (list->whole, list->start + position, elt) == NULL)
+ return NULL;
list->end++;
return INDEX_TO_NODE (position);
}
static gl_list_node_t
-gl_sublist_add_after (gl_list_t list, gl_list_node_t node, const void *elt)
+gl_sublist_nx_add_after (gl_list_t list, gl_list_node_t node, const void *elt)
{
size_t position = NODE_TO_INDEX (node);
if (!(position < list->end - list->start))
/* Invalid argument. */
abort ();
position++;
- gl_list_add_at (list->whole, list->start + position, elt);
+ if (gl_list_nx_add_at (list->whole, list->start + position, elt) == NULL)
+ return NULL;
list->end++;
return INDEX_TO_NODE (position);
}
static gl_list_node_t
-gl_sublist_add_at (gl_list_t list, size_t position, const void *elt)
+gl_sublist_nx_add_at (gl_list_t list, size_t position, const void *elt)
{
if (!(position <= list->end - list->start))
/* Invalid argument. */
abort ();
- gl_list_add_at (list->whole, list->start + position, elt);
+ if (gl_list_nx_add_at (list->whole, list->start + position, elt) == NULL)
+ return NULL;
list->end++;
return INDEX_TO_NODE (position);
}
static gl_list_iterator_t
gl_sublist_iterator_from_to (gl_list_t list,
- size_t start_index, size_t end_index)
+ size_t start_index, size_t end_index)
{
if (!(start_index <= end_index && end_index <= list->end - list->start))
/* Invalid arguments. */
abort ();
return gl_list_iterator_from_to (list->whole,
- list->start + start_index,
- list->start + end_index);
+ list->start + start_index,
+ list->start + end_index);
}
static bool
gl_sublist_iterator_next (gl_list_iterator_t *iterator,
- const void **eltp, gl_list_node_t *nodep)
+ const void **eltp, gl_list_node_t *nodep)
{
/* Shouldn't be called. */
abort ();
static gl_list_node_t
gl_sublist_sortedlist_search (gl_list_t list,
- gl_listelement_compar_fn compar,
- const void *elt)
+ gl_listelement_compar_fn compar,
+ const void *elt)
{
size_t index =
gl_sortedlist_indexof_from_to (list->whole, compar,
- list->start, list->end, elt);
+ list->start, list->end, elt);
if (index != (size_t)(-1))
return INDEX_TO_NODE (index - list->start);
else
static gl_list_node_t
gl_sublist_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;
index =
gl_sortedlist_indexof_from_to (list->whole, compar,
- list->start + low, list->start + high, elt);
+ list->start + low, list->start + high, elt);
if (index != (size_t)(-1))
return INDEX_TO_NODE (index - list->start);
else
static size_t
gl_sublist_sortedlist_indexof (gl_list_t list,
- gl_listelement_compar_fn compar,
- const void *elt)
+ gl_listelement_compar_fn compar,
+ const void *elt)
{
size_t index =
gl_sortedlist_indexof_from_to (list->whole, compar, list->start, list->end,
- elt);
+ elt);
if (index != (size_t)(-1))
index -= list->start;
return index;
static size_t
gl_sublist_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)
{
size_t index;
abort ();
index = gl_sortedlist_indexof_from_to (list->whole, compar,
- list->start + low, list->start + high,
- elt);
+ list->start + low, list->start + high,
+ elt);
if (index != (size_t)(-1))
index -= list->start;
return index;
}
static gl_list_node_t
-gl_sublist_sortedlist_add (gl_list_t list,
- gl_listelement_compar_fn compar,
- const void *elt)
+gl_sublist_sortedlist_nx_add (gl_list_t list,
+ gl_listelement_compar_fn compar,
+ const void *elt)
{
/* It's impossible to implement this method without risking to put the
whole list into unsorted order (namely, when the given ELT is smaller
static bool
gl_sublist_sortedlist_remove (gl_list_t list,
- gl_listelement_compar_fn compar,
- const void *elt)
+ gl_listelement_compar_fn compar,
+ const void *elt)
{
size_t index = gl_sublist_sortedlist_indexof (list, compar, elt);
if (index == (size_t)(-1))
static const struct gl_list_implementation gl_sublist_list_implementation =
{
- gl_sublist_create_empty,
- gl_sublist_create_fill,
+ gl_sublist_nx_create_empty,
+ gl_sublist_nx_create_fill,
gl_sublist_size,
gl_sublist_node_value,
+ gl_sublist_node_nx_set_value,
gl_sublist_next_node,
gl_sublist_previous_node,
gl_sublist_get_at,
- gl_sublist_set_at,
+ gl_sublist_nx_set_at,
gl_sublist_search_from_to,
gl_sublist_indexof_from_to,
- gl_sublist_add_first,
- gl_sublist_add_last,
- gl_sublist_add_before,
- gl_sublist_add_after,
- gl_sublist_add_at,
+ gl_sublist_nx_add_first,
+ gl_sublist_nx_add_last,
+ gl_sublist_nx_add_before,
+ gl_sublist_nx_add_after,
+ gl_sublist_nx_add_at,
gl_sublist_remove_node,
gl_sublist_remove_at,
gl_sublist_remove,
gl_sublist_sortedlist_search_from_to,
gl_sublist_sortedlist_indexof,
gl_sublist_sortedlist_indexof_from_to,
- gl_sublist_sortedlist_add,
+ gl_sublist_sortedlist_nx_add,
gl_sublist_sortedlist_remove
};
gl_list_t
-gl_sublist_create (gl_list_t whole_list, size_t start_index, size_t end_index)
+gl_sublist_nx_create (gl_list_t whole_list, size_t start_index, size_t end_index)
{
if (!(start_index <= end_index && end_index <= gl_list_size (whole_list)))
/* Invalid arguments. */
abort ();
{
- 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 = &gl_sublist_list_implementation;
list->base.equals_fn = whole_list->base.equals_fn; /* actually unused */
list->base.allow_duplicates = whole_list->base.allow_duplicates; /* unused */
if (whole_list->base.vtable == &gl_sublist_list_implementation)
{
- /* Optimization of a sublist of a sublist: Collapse the two
- indirections into a single indirection. */
- list->whole = whole_list->whole;
- list->start = whole_list->start + start_index;
- list->end = whole_list->start + end_index;
+ /* Optimization of a sublist of a sublist: Collapse the two
+ indirections into a single indirection. */
+ list->whole = whole_list->whole;
+ list->start = whole_list->start + start_index;
+ list->end = whole_list->start + end_index;
}
else
{
- list->whole = whole_list;
- list->start = start_index;
- list->end = end_index;
+ list->whole = whole_list;
+ list->start = start_index;
+ list->end = end_index;
}
return list;