X-Git-Url: http://erislabs.net/gitweb/?a=blobdiff_plain;f=lib%2Fgl_array_list.c;h=f82d01b0b31cd9eac13fa321ac1152918b4c5294;hb=df1da811f288a89eb524a4176c6fd62bacfb954a;hp=2b604ea6e2989eec449bc0b07f826f6561dbf4f8;hpb=407400d9367b16a628b57b2d9b8565bb5a08ffae;p=gnulib.git diff --git a/lib/gl_array_list.c b/lib/gl_array_list.c index 2b604ea6e..f82d01b0b 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-2008 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 @@ -56,14 +55,15 @@ 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) { - struct gl_list_impl *list = - (struct gl_list_impl *) xmalloc (sizeof (struct gl_list_impl)); + struct gl_list_impl *list = XMALLOC (struct gl_list_impl); 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; @@ -76,20 +76,20 @@ 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) { - struct gl_list_impl *list = - (struct gl_list_impl *) xmalloc (sizeof (struct gl_list_impl)); + struct gl_list_impl *list = XMALLOC (struct gl_list_impl); 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 *)); + list->elements = XNMALLOC (count, const void *); memcpy (list->elements, contents, count * sizeof (const void *)); } else @@ -116,6 +116,16 @@ gl_array_node_value (gl_list_t list, gl_list_node_t node) return list->elements[index]; } +static void +gl_array_node_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; +} + static gl_list_node_t gl_array_next_node (gl_list_t list, gl_list_node_t node) { @@ -348,6 +358,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 +377,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 +399,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); } @@ -442,8 +472,8 @@ gl_array_iterator_next (gl_list_iterator_t *iterator, 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) { @@ -466,16 +496,16 @@ 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 @@ -524,11 +554,31 @@ gl_array_sortedlist_indexof (gl_list_t list, gl_listelement_compar_fn compar, 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) { - 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); } @@ -578,6 +628,7 @@ const struct gl_list_implementation gl_array_list_implementation = gl_array_create, gl_array_size, gl_array_node_value, + gl_array_node_set_value, gl_array_next_node, gl_array_previous_node, gl_array_get_at, @@ -598,7 +649,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_indexof_from_to, gl_array_sortedlist_add, gl_array_sortedlist_remove };