X-Git-Url: http://erislabs.net/gitweb/?a=blobdiff_plain;f=lib%2Fgl_sublist.c;h=8bf884009a6d42e78bfa20cd3150c8e89902a6ad;hb=3386f3988ce2ab14d65f59659d8f95bf4830ecb3;hp=19158d02d208bb6532917a1aa597b9cefc07f31b;hpb=92877a2d8aef6f0296ff0567f9828151d4d82d64;p=gnulib.git diff --git a/lib/gl_sublist.c b/lib/gl_sublist.c index 19158d02d..8bf884009 100644 --- a/lib/gl_sublist.c +++ b/lib/gl_sublist.c @@ -1,5 +1,5 @@ /* Sequential list data type backed by another list. - Copyright (C) 2006-2008 Free Software Foundation, Inc. + Copyright (C) 2006-2013 Free Software Foundation, Inc. Written by Bruno Haible , 2006. This program is free software: you can redistribute it and/or modify @@ -22,8 +22,6 @@ #include -#include "xalloc.h" - #ifndef uintptr_t # define uintptr_t unsigned long #endif @@ -49,23 +47,23 @@ struct gl_list_impl #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 (); @@ -87,14 +85,16 @@ gl_sublist_node_value (gl_list_t list, gl_list_node_t node) return gl_list_get_at (list->whole, list->start + index); } -static void -gl_sublist_node_set_value (gl_list_t list, gl_list_node_t node, const void *elt) +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 (); - gl_list_set_at (list->whole, list->start + index, elt); + if (gl_list_nx_set_at (list->whole, list->start + index, elt) == NULL) + return -1; + return 0; } static gl_list_node_t @@ -135,18 +135,19 @@ gl_sublist_get_at (gl_list_t list, size_t position) } 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. */ @@ -154,9 +155,9 @@ gl_sublist_search_from_to (gl_list_t list, size_t start_index, size_t end_index, { 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 @@ -166,8 +167,8 @@ gl_sublist_search_from_to (gl_list_t list, size_t start_index, size_t end_index, 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. */ @@ -175,9 +176,9 @@ gl_sublist_indexof_from_to (gl_list_t list, { 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; @@ -185,53 +186,58 @@ gl_sublist_indexof_from_to (gl_list_t list, } 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); } @@ -282,19 +288,19 @@ gl_sublist_iterator (gl_list_t list) 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 (); @@ -311,12 +317,12 @@ gl_sublist_iterator_free (gl_list_iterator_t *iterator) 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 @@ -325,9 +331,9 @@ gl_sublist_sortedlist_search (gl_list_t list, 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; @@ -337,7 +343,7 @@ gl_sublist_sortedlist_search_from_to (gl_list_t list, 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 @@ -346,12 +352,12 @@ gl_sublist_sortedlist_search_from_to (gl_list_t list, 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; @@ -359,9 +365,9 @@ gl_sublist_sortedlist_indexof (gl_list_t list, 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; @@ -370,17 +376,17 @@ gl_sublist_sortedlist_indexof_from_to (gl_list_t list, 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 @@ -390,8 +396,8 @@ gl_sublist_sortedlist_add (gl_list_t list, 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)) @@ -403,22 +409,22 @@ gl_sublist_sortedlist_remove (gl_list_t list, 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_set_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, @@ -431,18 +437,22 @@ static const struct gl_list_implementation gl_sublist_list_implementation = 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 */ @@ -451,17 +461,17 @@ gl_sublist_create (gl_list_t whole_list, size_t start_index, size_t end_index) 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;