X-Git-Url: http://erislabs.net/gitweb/?a=blobdiff_plain;f=lib%2Fgl_array_list.c;h=b61b6cae26658c651392da3216da65d7a81dafe1;hb=1276a2c5f24c0c932426aca9c899fa524d2443f2;hp=2b604ea6e2989eec449bc0b07f826f6561dbf4f8;hpb=407400d9367b16a628b57b2d9b8565bb5a08ffae;p=gnulib.git diff --git a/lib/gl_array_list.c b/lib/gl_array_list.c index 2b604ea6e..b61b6cae2 100644 --- a/lib/gl_array_list.c +++ b/lib/gl_array_list.c @@ -1,11 +1,11 @@ /* Sequential list data type implemented by an array. - Copyright (C) 2006 Free Software Foundation, Inc. + Copyright (C) 2006-2014 Free Software Foundation, Inc. Written by Bruno Haible , 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 @@ -13,8 +13,7 @@ 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 . */ #include @@ -25,8 +24,6 @@ /* Get memcpy. */ #include -#include "xalloc.h" - /* Checked size_t computations. */ #include "xsize.h" @@ -53,17 +50,22 @@ 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, - 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 = - (struct gl_list_impl *) xmalloc (sizeof (struct gl_list_impl)); + (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.hashcode_fn = hashcode_fn; + list->base.dispose_fn = dispose_fn; list->base.allow_duplicates = allow_duplicates; list->elements = NULL; list->count = 0; @@ -73,23 +75,31 @@ 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, - 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 = - (struct gl_list_impl *) xmalloc (sizeof (struct gl_list_impl)); + (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.hashcode_fn = hashcode_fn; + list->base.dispose_fn = dispose_fn; list->base.allow_duplicates = allow_duplicates; if (count > 0) { - list->elements = - (const void **) xmalloc (count * sizeof (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]; @@ -348,6 +381,8 @@ gl_array_remove_node (gl_list_t list, gl_list_node_t node) abort (); position = index; elements = list->elements; + if (list->base.dispose_fn != NULL) + list->base.dispose_fn (elements[position]); for (i = position + 1; i < count; i++) elements[i - 1] = elements[i]; list->count = count - 1; @@ -365,6 +400,8 @@ gl_array_remove_at (gl_list_t list, size_t position) /* Invalid argument. */ abort (); elements = list->elements; + if (list->base.dispose_fn != NULL) + list->base.dispose_fn (elements[position]); for (i = position + 1; i < count; i++) elements[i - 1] = elements[i]; list->count = count - 1; @@ -385,7 +422,23 @@ static void gl_array_list_free (gl_list_t list) { if (list->elements != NULL) - free (list->elements); + { + 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); + } + } + free (list->elements); + } free (list); } @@ -432,25 +485,25 @@ 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--; - iterator->q--; + iterator->p = (const void **) iterator->p - 1; + iterator->q = (const void **) iterator->q - 1; } if (iterator->p < iterator->q) { 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; } @@ -466,75 +519,95 @@ gl_array_iterator_free (gl_list_iterator_t *iterator) /* ---------------------- Sorted gl_list_t Data Type ---------------------- */ static size_t -gl_array_sortedlist_indexof (gl_list_t list, gl_listelement_compar_fn compar, - const void *elt) +gl_array_sortedlist_indexof_from_to (gl_list_t list, + gl_listelement_compar_fn compar, + size_t low, size_t high, + const void *elt) { - size_t count = list->count; - - if (count > 0) + if (!(low <= high && high <= list->count)) + /* Invalid arguments. */ + abort (); + if (low < high) { - size_t low = 0; - size_t high = count; - /* 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. */ } return (size_t)(-1); } +static size_t +gl_array_sortedlist_indexof (gl_list_t list, gl_listelement_compar_fn compar, + const void *elt) +{ + return gl_array_sortedlist_indexof_from_to (list, compar, 0, list->count, + 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) +{ + size_t index = + gl_array_sortedlist_indexof_from_to (list, compar, low, high, elt); + return INDEX_TO_NODE (index); +} + 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 (list, compar, elt); + size_t index = + gl_array_sortedlist_indexof_from_to (list, compar, 0, list->count, elt); return INDEX_TO_NODE (index); } 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; @@ -548,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)) @@ -574,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, @@ -598,7 +672,9 @@ const struct gl_list_implementation gl_array_list_implementation = gl_array_iterator_next, gl_array_iterator_free, gl_array_sortedlist_search, + gl_array_sortedlist_search_from_to, gl_array_sortedlist_indexof, - gl_array_sortedlist_add, + gl_array_sortedlist_indexof_from_to, + gl_array_sortedlist_nx_add, gl_array_sortedlist_remove };