diff options
author | Bruno Haible <bruno@clisp.org> | 2009-12-10 20:28:30 +0100 |
---|---|---|
committer | Bruno Haible <bruno@clisp.org> | 2009-12-10 20:28:30 +0100 |
commit | 441aa3044f43e5572f58c354f01e6bc070acd5c7 (patch) | |
tree | bef236e8058dd3469da28ffcd5a6a287222a4c50 /lib/gl_carray_list.c | |
parent | 039ae97b8ae35a2446c5d62d72b21689c97da7e2 (diff) | |
download | gnulib-441aa3044f43e5572f58c354f01e6bc070acd5c7.tar.gz |
Use spaces for indentation, not tabs.
Diffstat (limited to 'lib/gl_carray_list.c')
-rw-r--r-- | lib/gl_carray_list.c | 500 |
1 files changed, 250 insertions, 250 deletions
diff --git a/lib/gl_carray_list.c b/lib/gl_carray_list.c index 8b43901e2b..719b914d01 100644 --- a/lib/gl_carray_list.c +++ b/lib/gl_carray_list.c @@ -56,10 +56,10 @@ 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, - gl_listelement_dispose_fn dispose_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 = XMALLOC (struct gl_list_impl); @@ -78,11 +78,11 @@ 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, - gl_listelement_dispose_fn dispose_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 = XMALLOC (struct gl_list_impl); @@ -201,7 +201,7 @@ gl_carray_set_at (gl_list_t list, size_t position, const void *elt) static size_t gl_carray_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; @@ -217,53 +217,53 @@ gl_carray_indexof_from_to (gl_list_t list, size_t start_index, size_t end_index, i_end = list->offset + end_index; if (i_end >= allocated) - i_end -= allocated; + i_end -= allocated; if (equals != NULL) - { - size_t i; - - 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; - i++; - if (i == allocated) - i = 0; - if (i == i_end) - break; - } - } + { + size_t i; + + 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; + i++; + if (i == allocated) + i = 0; + if (i == i_end) + break; + } + } else - { - size_t i; - - 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; - i++; - if (i == allocated) - i = 0; - if (i == i_end) - break; - } - } + { + size_t i; + + 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; + i++; + if (i == allocated) + i = 0; + if (i == i_end) + break; + } + } } return (size_t)(-1); } static gl_list_node_t gl_carray_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_carray_indexof_from_to (list, start_index, end_index, elt); return INDEX_TO_NODE (index); @@ -287,29 +287,29 @@ grow (gl_list_t list) { memory = (const void **) xmalloc (memory_size); if (memory == NULL) - /* Out of memory. */ - xalloc_die (); + /* Out of memory. */ + xalloc_die (); if (list->offset + list->count > list->allocated) - { - memcpy (memory, &list->elements[list->offset], - (list->allocated - list->offset) * sizeof (const void *)); - memcpy (memory + (list->allocated - list->offset), list->elements, - (list->offset + list->count - list->allocated) - * sizeof (const void *)); - - } + { + memcpy (memory, &list->elements[list->offset], + (list->allocated - list->offset) * sizeof (const void *)); + memcpy (memory + (list->allocated - list->offset), list->elements, + (list->offset + list->count - list->allocated) + * sizeof (const void *)); + + } else - memcpy (memory, &list->elements[list->offset], - list->count * sizeof (const void *)); + memcpy (memory, &list->elements[list->offset], + list->count * sizeof (const void *)); if (list->elements != NULL) - free (list->elements); + free (list->elements); } else { memory = (const void **) xrealloc (list->elements, memory_size); if (memory == NULL) - /* Out of memory. */ - xalloc_die (); + /* Out of memory. */ + xalloc_die (); } list->elements = memory; list->offset = 0; @@ -366,21 +366,21 @@ gl_carray_add_at (gl_list_t list, size_t position, const void *elt) i2 = list->offset + position; if (i2 >= list->allocated) - { - /* Here we must have list->offset > 0, hence list->allocated > 0. */ - size_t i1 = list->allocated - 1; - i2 -= list->allocated; - for (i = list->offset; i < i1; i++) - elements[i] = elements[i + 1]; - elements[i1] = elements[0]; - for (i = 0; i < i2; i++) - elements[i] = elements[i + 1]; - } + { + /* Here we must have list->offset > 0, hence list->allocated > 0. */ + size_t i1 = list->allocated - 1; + i2 -= list->allocated; + for (i = list->offset; i < i1; i++) + elements[i] = elements[i + 1]; + elements[i1] = elements[0]; + for (i = 0; i < i2; i++) + elements[i] = elements[i + 1]; + } else - { - for (i = list->offset; i < i2; i++) - elements[i] = elements[i + 1]; - } + { + for (i = list->offset; i < i2; i++) + elements[i] = elements[i + 1]; + } elements[i2] = elt; } else @@ -391,28 +391,28 @@ gl_carray_add_at (gl_list_t list, size_t position, const void *elt) i1 = list->offset + position; i3 = list->offset + count; if (i1 >= list->allocated) - { - i1 -= list->allocated; - i3 -= list->allocated; - for (i = i3; i > i1; i--) - elements[i] = elements[i - 1]; - } + { + i1 -= list->allocated; + i3 -= list->allocated; + for (i = i3; i > i1; i--) + elements[i] = elements[i - 1]; + } else if (i3 >= list->allocated) - { - /* Here we must have list->offset > 0, hence list->allocated > 0. */ - size_t i2 = list->allocated - 1; - i3 -= list->allocated; - for (i = i3; i > 0; i--) - elements[i] = elements[i - 1]; - elements[0] = elements[i2]; - for (i = i2; i > i1; i--) - elements[i] = elements[i - 1]; - } + { + /* Here we must have list->offset > 0, hence list->allocated > 0. */ + size_t i2 = list->allocated - 1; + i3 -= list->allocated; + for (i = i3; i > 0; i--) + elements[i] = elements[i - 1]; + elements[0] = elements[i2]; + for (i = i2; i > i1; i--) + elements[i] = elements[i - 1]; + } else - { - for (i = i3; i > i1; i--) - elements[i] = elements[i - 1]; - } + { + for (i = i3; i > i1; i--) + elements[i] = elements[i - 1]; + } elements[i1] = elt; } list->count = count + 1; @@ -462,25 +462,25 @@ gl_carray_remove_at (gl_list_t list, size_t position) i0 = list->offset; i2 = list->offset + position; if (i2 >= list->allocated) - { - /* 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]; - for (i = i1; i > i0; i--) - elements[i] = elements[i - 1]; - } + { + /* 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]; + for (i = i1; i > i0; i--) + elements[i] = elements[i - 1]; + } else - { - if (list->base.dispose_fn != NULL) - list->base.dispose_fn (elements[i2]); - for (i = i2; i > i0; i--) - elements[i] = elements[i - 1]; - } + { + if (list->base.dispose_fn != NULL) + list->base.dispose_fn (elements[i2]); + for (i = i2; i > i0; i--) + elements[i] = elements[i - 1]; + } i0++; list->offset = (i0 == list->allocated ? 0 : i0); @@ -493,34 +493,34 @@ gl_carray_remove_at (gl_list_t list, size_t position) i1 = list->offset + position; i3 = list->offset + count - 1; if (i1 >= list->allocated) - { - 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]; - } + { + 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]; + } else if (i3 >= list->allocated) - { - /* 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]; - for (i = 0; i < i3; i++) - elements[i] = elements[i + 1]; - } + { + /* 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]; + for (i = 0; i < i3; i++) + elements[i] = elements[i + 1]; + } else - { - if (list->base.dispose_fn != NULL) - list->base.dispose_fn (elements[i1]); - for (i = i1; i < i3; i++) - elements[i] = elements[i + 1]; - } + { + if (list->base.dispose_fn != NULL) + list->base.dispose_fn (elements[i1]); + for (i = i1; i < i3; i++) + elements[i] = elements[i + 1]; + } } list->count = count - 1; return true; @@ -554,38 +554,38 @@ gl_carray_list_free (gl_list_t list) if (list->elements != NULL) { 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]); - } - } - } + { + 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); @@ -634,14 +634,14 @@ gl_carray_iterator_from_to (gl_list_t list, size_t start_index, size_t end_index static bool gl_carray_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->i--; @@ -651,10 +651,10 @@ gl_carray_iterator_next (gl_list_iterator_t *iterator, { size_t i = list->offset + iterator->i; if (i >= list->allocated) - i -= list->allocated; + i -= list->allocated; *eltp = list->elements[i]; if (nodep != NULL) - *nodep = INDEX_TO_NODE (iterator->i); + *nodep = INDEX_TO_NODE (iterator->i); iterator->i++; return true; } @@ -671,9 +671,9 @@ gl_carray_iterator_free (gl_list_iterator_t *iterator) static size_t gl_carray_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) { if (!(low <= high && high <= list->count)) /* Invalid arguments. */ @@ -681,61 +681,61 @@ gl_carray_sortedlist_indexof_from_to (gl_list_t list, if (low < high) { /* 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 */ - size_t i_mid; - int cmp; - - i_mid = list->offset + mid; - if (i_mid >= list->allocated) - i_mid -= list->allocated; - - cmp = compar (list->elements[i_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[i_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 */ - size_t i_mid2; - int cmp2; - - i_mid2 = list->offset + mid2; - if (i_mid2 >= list->allocated) - i_mid2 -= list->allocated; - - cmp2 = compar (list->elements[i_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 */ + size_t i_mid; + int cmp; + + i_mid = list->offset + mid; + if (i_mid >= list->allocated) + i_mid -= list->allocated; + + cmp = compar (list->elements[i_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[i_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 */ + size_t i_mid2; + int cmp2; + + i_mid2 = list->offset + mid2; + if (i_mid2 >= list->allocated) + i_mid2 -= list->allocated; + + cmp2 = compar (list->elements[i_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. */ } @@ -744,17 +744,17 @@ gl_carray_sortedlist_indexof_from_to (gl_list_t list, static size_t gl_carray_sortedlist_indexof (gl_list_t list, gl_listelement_compar_fn compar, - const void *elt) + const void *elt) { return gl_carray_sortedlist_indexof_from_to (list, compar, 0, list->count, - elt); + 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) + 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); @@ -763,7 +763,7 @@ gl_carray_sortedlist_search_from_to (gl_list_t list, static gl_list_node_t gl_carray_sortedlist_search (gl_list_t list, gl_listelement_compar_fn compar, - const void *elt) + const void *elt) { size_t index = gl_carray_sortedlist_indexof_from_to (list, compar, 0, list->count, elt); @@ -772,7 +772,7 @@ gl_carray_sortedlist_search (gl_list_t list, gl_listelement_compar_fn compar, static gl_list_node_t gl_carray_sortedlist_add (gl_list_t list, gl_listelement_compar_fn compar, - const void *elt) + const void *elt) { size_t count = list->count; size_t low = 0; @@ -788,26 +788,26 @@ gl_carray_sortedlist_add (gl_list_t list, gl_listelement_compar_fn compar, i_mid = list->offset + mid; if (i_mid >= list->allocated) - i_mid -= list->allocated; + i_mid -= list->allocated; cmp = compar (list->elements[i_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_carray_add_at (list, low, elt); } static bool gl_carray_sortedlist_remove (gl_list_t list, gl_listelement_compar_fn compar, - const void *elt) + const void *elt) { size_t index = gl_carray_sortedlist_indexof (list, compar, elt); if (index == (size_t)(-1)) |