Edit
kc3-lang/gnulib/lib/gl_array_oset.c
Paul Eggert
- lib/gl_array_oset.c
-
/* Ordered set data type implemented by an array. Copyright (C) 2006-2007, 2009-2015 Free Software Foundation, Inc. Written by Bruno Haible <bruno@clisp.org>, 2006. 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 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 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the 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, see <http://www.gnu.org/licenses/>. */ #include <config.h> /* Specification. */ #include "gl_array_oset.h" #include <stdlib.h> /* Checked size_t computations. */ #include "xsize.h" /* -------------------------- gl_oset_t Data Type -------------------------- */ /* Concrete gl_oset_impl type, valid for this file only. */ struct gl_oset_impl { struct gl_oset_impl_base base; /* An array of ALLOCATED elements, of which the first COUNT are used. 0 <= COUNT <= ALLOCATED. */ const void **elements; size_t count; size_t allocated; }; static gl_oset_t gl_array_nx_create_empty (gl_oset_implementation_t implementation, gl_setelement_compar_fn compar_fn, gl_setelement_dispose_fn dispose_fn) { struct gl_oset_impl *set = (struct gl_oset_impl *) malloc (sizeof (struct gl_oset_impl)); if (set == NULL) return NULL; set->base.vtable = implementation; set->base.compar_fn = compar_fn; set->base.dispose_fn = dispose_fn; set->elements = NULL; set->count = 0; set->allocated = 0; return set; } static size_t gl_array_size (gl_oset_t set) { return set->count; } static size_t gl_array_indexof (gl_oset_t set, const void *elt) { size_t count = set->count; if (count > 0) { gl_setelement_compar_fn compar = set->base.compar_fn; 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. */ do { size_t mid = low + (high - low) / 2; /* low <= mid < high */ int cmp = (compar != NULL ? compar (set->elements[mid], elt) : (set->elements[mid] > elt ? 1 : set->elements[mid] < elt ? -1 : 0)); 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. */ return mid; } while (low < high); } return (size_t)(-1); } static bool gl_array_search (gl_oset_t set, const void *elt) { return gl_array_indexof (set, elt) != (size_t)(-1); } static bool gl_array_search_atleast (gl_oset_t set, gl_setelement_threshold_fn threshold_fn, const void *threshold, const void **eltp) { size_t count = set->count; if (count > 0) { size_t low = 0; size_t high = count; /* At each loop iteration, low < high; for indices < low the values are smaller than THRESHOLD; for indices >= high the values are nonexistent. So, if an element >= THRESHOLD occurs in the list, it is at low <= position < high. */ do { size_t mid = low + (high - low) / 2; /* low <= mid < high */ if (! threshold_fn (set->elements[mid], threshold)) low = mid + 1; else { /* We have an element >= THRESHOLD at index MID. But we need the minimal such index. */ high = mid; /* At each loop iteration, low <= high and compar (list->elements[high], value) >= 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 */ if (! threshold_fn (set->elements[mid2], threshold)) low = mid2 + 1; else high = mid2; } *eltp = set->elements[low]; return true; } } while (low < high); } return false; } /* Ensure that set->allocated > set->count. Return 0 upon success, -1 upon out-of-memory. */ static int grow (gl_oset_t set) { size_t new_allocated; size_t memory_size; const void **memory; new_allocated = xtimes (set->allocated, 2); new_allocated = xsum (new_allocated, 1); memory_size = xtimes (new_allocated, sizeof (const void *)); if (size_overflow_p (memory_size)) /* Overflow, would lead to out of memory. */ return -1; memory = (const void **) realloc (set->elements, memory_size); if (memory == NULL) /* Out of memory. */ return -1; set->elements = memory; set->allocated = new_allocated; return 0; } /* Add the given element ELT at the given position, 0 <= position <= gl_oset_size (set). Return 1 upon success, -1 upon out-of-memory. */ static int gl_array_nx_add_at (gl_oset_t set, size_t position, const void *elt) { size_t count = set->count; const void **elements; size_t i; if (count == set->allocated) if (grow (set) < 0) return -1; elements = set->elements; for (i = count; i > position; i--) elements[i] = elements[i - 1]; elements[position] = elt; set->count = count + 1; return 1; } /* Remove the element at the given position, 0 <= position < gl_oset_size (set). */ static void gl_array_remove_at (gl_oset_t set, size_t position) { size_t count = set->count; const void **elements; size_t i; elements = set->elements; if (set->base.dispose_fn != NULL) set->base.dispose_fn (elements[position]); for (i = position + 1; i < count; i++) elements[i - 1] = elements[i]; set->count = count - 1; } static int gl_array_nx_add (gl_oset_t set, const void *elt) { size_t count = set->count; size_t low = 0; if (count > 0) { gl_setelement_compar_fn compar = set->base.compar_fn; 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. */ do { size_t mid = low + (high - low) / 2; /* low <= mid < high */ int cmp = (compar != NULL ? compar (set->elements[mid], elt) : (set->elements[mid] > elt ? 1 : set->elements[mid] < elt ? -1 : 0)); if (cmp < 0) low = mid + 1; else if (cmp > 0) high = mid; else /* cmp == 0 */ return false; } while (low < high); } return gl_array_nx_add_at (set, low, elt); } static bool gl_array_remove (gl_oset_t set, const void *elt) { size_t index = gl_array_indexof (set, elt); if (index != (size_t)(-1)) { gl_array_remove_at (set, index); return true; } else return false; } static void gl_array_free (gl_oset_t set) { if (set->elements != NULL) { if (set->base.dispose_fn != NULL) { size_t count = set->count; if (count > 0) { gl_setelement_dispose_fn dispose = set->base.dispose_fn; const void **elements = set->elements; do dispose (*elements++); while (--count > 0); } } free (set->elements); } free (set); } /* --------------------- gl_oset_iterator_t Data Type --------------------- */ static gl_oset_iterator_t gl_array_iterator (gl_oset_t set) { gl_oset_iterator_t result; result.vtable = set->base.vtable; result.set = set; result.count = set->count; result.p = set->elements + 0; result.q = set->elements + set->count; #ifdef lint result.i = 0; result.j = 0; #endif return result; } static bool gl_array_iterator_next (gl_oset_iterator_t *iterator, const void **eltp) { gl_oset_t set = iterator->set; if (iterator->count != set->count) { if (iterator->count != set->count + 1) /* Concurrent modifications were done on the set. */ abort (); /* The last returned element was removed. */ iterator->count--; 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; iterator->p = p + 1; return true; } else return false; } static void gl_array_iterator_free (gl_oset_iterator_t *iterator) { } const struct gl_oset_implementation gl_array_oset_implementation = { gl_array_nx_create_empty, gl_array_size, gl_array_search, gl_array_search_atleast, gl_array_nx_add, gl_array_remove, gl_array_free, gl_array_iterator, gl_array_iterator_next, gl_array_iterator_free };