diff options
Diffstat (limited to 'libGL/range_alloc.c')
| -rwxr-xr-x | libGL/range_alloc.c | 195 |
1 files changed, 195 insertions, 0 deletions
diff --git a/libGL/range_alloc.c b/libGL/range_alloc.c new file mode 100755 index 0000000..bb66508 --- /dev/null +++ b/libGL/range_alloc.c @@ -0,0 +1,195 @@ +/* + * Copyright (c) 2007 Even Rouault + * + * Permission is hereby granted, free of charge, to any person obtaining a copy + * of this software and associated documentation files (the "Software"), to deal + * in the Software without restriction, including without limitation the rights + * to use, copy, modify, merge, publish, distribute, sublicense, and/or sell + * copies of the Software, and to permit persons to whom the Software is + * furnished to do so, subject to the following conditions: + * + * The above copyright notice and this permission notice shall be included in + * all copies or substantial portions of the Software. + * + * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR + * IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY, + * FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL + * THE AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER + * LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, + * OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN + * THE SOFTWARE. + */ + +#include <stdio.h> +#include <stdlib.h> +#include <string.h> + +#include "range_alloc.h" +#include "log.h" + +void alloc_value(RangeAllocator* range, unsigned int value) +{ + if (value == 0) return; + if (range->nbValues >= 1) + { + int lower = 0; + int upper = range->nbValues-1; + while(1) + { + int mid = (lower + upper) / 2; + if (range->values[mid] > value) + upper = mid; + else if (range->values[mid] < value) + lower = mid; + else + break; + if (upper - lower <= 1) + { + if (value < range->values[lower]) + { + range->values = realloc(range->values, (range->nbValues+1) * sizeof(int)); + memmove(&range->values[lower+1], &range->values[lower], (range->nbValues - lower) * sizeof(int)); + range->values[lower] = value; + range->nbValues++; + } + else if (value == range->values[lower]) + { + } + else if (value < range->values[upper]) + { + range->values = realloc(range->values, (range->nbValues+1) * sizeof(int)); + memmove(&range->values[upper+1], &range->values[upper], (range->nbValues - upper) * sizeof(int)); + range->values[upper] = value; + range->nbValues++; + } + else if (value == range->values[upper]) + { + } + else + { + upper++; + + range->values = realloc(range->values, (range->nbValues+1) * sizeof(int)); + memmove(&range->values[upper+1], &range->values[upper], (range->nbValues - upper) * sizeof(int)); + range->values[upper] = value; + range->nbValues++; + } + break; + } + } + } + else + { + range->values = malloc(sizeof(int)); + range->values[0] = value; + range->nbValues = 1; + } +} + +/* return first value */ +unsigned int alloc_range(RangeAllocator* range, int n, unsigned int* values) +{ + int i, j; + if (range->nbValues == 0) + { + range->nbValues = n; + range->values = malloc(n * sizeof(int)); + for(i=0;i<n;i++) + { + range->values[i] = i+1; + if (values) + values[i] = range->values[i]; + } + return 1; + } + else + { + int lastValue = 1; + for(i=0;i<range->nbValues;i++) + { + if ((int)range->values[i] - (int)lastValue - 1 >= n) + { + range->values = realloc(range->values, (range->nbValues+n) * sizeof(int)); + memmove(&range->values[i+n], &range->values[i], (range->nbValues - i) * sizeof(int)); + for(j=0;j<n;j++) + { + range->values[i+j] = lastValue + 1 + j; + if (values) + values[j] = range->values[i+j]; + } + range->nbValues += n; + break; + } + else + lastValue = range->values[i]; + } + if (i == range->nbValues) + { + range->values = realloc(range->values, (range->nbValues+n) * sizeof(int)); + for(j=0;j<n;j++) + { + range->values[i+j] = lastValue + 1 + j; + if (values) + values[j] = range->values[i+j]; + } + range->nbValues += n; + } + return lastValue + 1; + } +} + +void delete_value(RangeAllocator* range, unsigned int value) +{ + if (value == 0) + return; + if (range->nbValues >= 1) + { + int lower = 0; + int upper = range->nbValues-1; + while(1) + { + int mid = (lower + upper) / 2; + if (range->values[mid] > value) + upper = mid; + else if (range->values[mid] < value) + lower = mid; + else + { + lower = upper = mid; + } + if (upper - lower <= 1) + { + if (value == range->values[lower]) + { + memmove(&range->values[lower], &range->values[lower+1], (range->nbValues - lower-1) * sizeof(int)); + range->nbValues--; + } + else if (value == range->values[upper]) + { + memmove(&range->values[upper], &range->values[upper+1], (range->nbValues - upper-1) * sizeof(int)); + range->nbValues--; + } + break; + } + } + } +} + +void delete_range(RangeAllocator* range, int n, const unsigned int* values) +{ + int i; + for(i=0;i<n;i++) + { + delete_value(range, values[i]); + } +} + +void delete_consecutive_values(RangeAllocator* range, unsigned int first, int n) +{ + int i; + for(i=0;i<n;i++) + { + delete_value(range, first + i); + } +} + |