X-Git-Url: http://erislabs.net/gitweb/?a=blobdiff_plain;f=lib%2Fgl_carray_list.c;h=90113e0305c06184be67b582afc02d2c3dffd118;hb=5d0b385594bc914e6233988bfb6bc1b92a2184b5;hp=7df371caf1437f389b87a875e9cb997c45306a2d;hpb=5a0d317d0459a0f0955c6f4751d75730ab4b4055;p=gnulib.git diff --git a/lib/gl_carray_list.c b/lib/gl_carray_list.c index 7df371caf..90113e030 100644 --- a/lib/gl_carray_list.c +++ b/lib/gl_carray_list.c @@ -1,5 +1,5 @@ /* Sequential list data type implemented by a circular array. - Copyright (C) 2006 Free Software Foundation, Inc. + Copyright (C) 2006-2007 Free Software Foundation, Inc. Written by Bruno Haible , 2006. This program is free software; you can redistribute it and/or modify @@ -57,16 +57,17 @@ struct gl_list_impl 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, - bool allow_duplicates) + 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->offset = 0; @@ -78,22 +79,22 @@ gl_carray_create_empty (gl_list_implementation_t implementation, static gl_list_t gl_carray_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_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 @@ -185,16 +186,22 @@ gl_carray_set_at (gl_list_t list, size_t position, const void *elt) } static size_t -gl_carray_indexof (gl_list_t list, const void *elt) +gl_carray_indexof_from_to (gl_list_t list, size_t start_index, size_t end_index, + const void *elt) { size_t count = list->count; - if (count > 0) + + if (!(start_index <= end_index && end_index <= count)) + /* Invalid arguments. */ + abort (); + + if (start_index < end_index) { gl_listelement_equals_fn equals = list->base.equals_fn; size_t allocated = list->allocated; size_t i_end; - i_end = list->offset + list->count; + i_end = list->offset + end_index; if (i_end >= allocated) i_end -= allocated; @@ -202,7 +209,11 @@ gl_carray_indexof (gl_list_t list, const void *elt) { size_t i; - for (i = list->offset;;) + i = list->offset + start_index; + if (i >= allocated) /* can only happen if start_index > 0 */ + i -= allocated; + + for (;;) { if (equals (elt, list->elements[i])) return (i >= list->offset ? i : i + allocated) - list->offset; @@ -217,7 +228,11 @@ gl_carray_indexof (gl_list_t list, const void *elt) { size_t i; - for (i = list->offset;;) + i = list->offset + start_index; + if (i >= allocated) /* can only happen if start_index > 0 */ + i -= allocated; + + for (;;) { if (elt == list->elements[i]) return (i >= list->offset ? i : i + allocated) - list->offset; @@ -233,9 +248,10 @@ gl_carray_indexof (gl_list_t list, const void *elt) } static gl_list_node_t -gl_carray_search (gl_list_t list, const void *elt) +gl_carray_search_from_to (gl_list_t list, size_t start_index, size_t end_index, + const void *elt) { - size_t index = gl_carray_indexof (list, elt); + size_t index = gl_carray_indexof_from_to (list, start_index, end_index, elt); return INDEX_TO_NODE (index); } @@ -436,6 +452,8 @@ gl_carray_remove_at (gl_list_t list, size_t position) /* Here we must have list->offset > 0, hence list->allocated > 0. */ size_t i1 = list->allocated - 1; i2 -= list->allocated; + if (list->base.dispose_fn != NULL) + list->base.dispose_fn (elements[i2]); for (i = i2; i > 0; i--) elements[i] = elements[i - 1]; elements[0] = elements[i1]; @@ -444,6 +462,8 @@ gl_carray_remove_at (gl_list_t list, size_t position) } else { + if (list->base.dispose_fn != NULL) + list->base.dispose_fn (elements[i2]); for (i = i2; i > i0; i--) elements[i] = elements[i - 1]; } @@ -462,6 +482,8 @@ gl_carray_remove_at (gl_list_t list, size_t position) { i1 -= list->allocated; i3 -= list->allocated; + if (list->base.dispose_fn != NULL) + list->base.dispose_fn (elements[i1]); for (i = i1; i < i3; i++) elements[i] = elements[i + 1]; } @@ -470,6 +492,8 @@ gl_carray_remove_at (gl_list_t list, size_t position) /* Here we must have list->offset > 0, hence list->allocated > 0. */ size_t i2 = list->allocated - 1; i3 -= list->allocated; + if (list->base.dispose_fn != NULL) + list->base.dispose_fn (elements[i1]); for (i = i1; i < i2; i++) elements[i] = elements[i + 1]; elements[i2] = elements[0]; @@ -478,6 +502,8 @@ gl_carray_remove_at (gl_list_t list, size_t position) } else { + if (list->base.dispose_fn != NULL) + list->base.dispose_fn (elements[i1]); for (i = i1; i < i3; i++) elements[i] = elements[i + 1]; } @@ -501,7 +527,7 @@ gl_carray_remove_node (gl_list_t list, gl_list_node_t node) static bool gl_carray_remove (gl_list_t list, const void *elt) { - size_t position = gl_carray_indexof (list, elt); + size_t position = gl_carray_indexof_from_to (list, 0, list->count, elt); if (position == (size_t)(-1)) return false; else @@ -512,7 +538,42 @@ static void gl_carray_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; + size_t i1 = list->offset; + size_t i3 = list->offset + count - 1; + + if (i3 >= list->allocated) + { + /* Here we must have list->offset > 0, hence + list->allocated > 0. */ + size_t i2 = list->allocated - 1; + size_t i; + + i3 -= list->allocated; + for (i = i1; i <= i2; i++) + dispose (elements[i]); + for (i = 0; i <= i3; i++) + dispose (elements[i]); + } + else + { + size_t i; + + for (i = i1; i <= i3; i++) + dispose (elements[i]); + } + } + } + free (list->elements); + } free (list); } @@ -595,16 +656,16 @@ gl_carray_iterator_free (gl_list_iterator_t *iterator) /* ---------------------- Sorted gl_list_t Data Type ---------------------- */ static size_t -gl_carray_sortedlist_indexof (gl_list_t list, gl_listelement_compar_fn compar, - const void *elt) +gl_carray_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 @@ -667,11 +728,31 @@ gl_carray_sortedlist_indexof (gl_list_t list, gl_listelement_compar_fn compar, return (size_t)(-1); } +static size_t +gl_carray_sortedlist_indexof (gl_list_t list, gl_listelement_compar_fn compar, + const void *elt) +{ + return gl_carray_sortedlist_indexof_from_to (list, compar, 0, list->count, + elt); +} + +static gl_list_node_t +gl_carray_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_carray_sortedlist_indexof_from_to (list, compar, low, high, elt); + return INDEX_TO_NODE (index); +} + static gl_list_node_t gl_carray_sortedlist_search (gl_list_t list, gl_listelement_compar_fn compar, const void *elt) { - size_t index = gl_carray_sortedlist_indexof (list, compar, elt); + size_t index = + gl_carray_sortedlist_indexof_from_to (list, compar, 0, list->count, elt); return INDEX_TO_NODE (index); } @@ -732,8 +813,8 @@ const struct gl_list_implementation gl_carray_list_implementation = gl_carray_previous_node, gl_carray_get_at, gl_carray_set_at, - gl_carray_search, - gl_carray_indexof, + gl_carray_search_from_to, + gl_carray_indexof_from_to, gl_carray_add_first, gl_carray_add_last, gl_carray_add_before, @@ -748,7 +829,9 @@ const struct gl_list_implementation gl_carray_list_implementation = gl_carray_iterator_next, gl_carray_iterator_free, gl_carray_sortedlist_search, + gl_carray_sortedlist_search_from_to, gl_carray_sortedlist_indexof, + gl_carray_sortedlist_indexof_from_to, gl_carray_sortedlist_add, gl_carray_sortedlist_remove };