diff options
Diffstat (limited to 'csrc/algorithms')
| -rw-r--r-- | csrc/algorithms/arrays/minmax.h | 220 | ||||
| -rw-r--r-- | csrc/algorithms/arrays/reverse.h | 72 | ||||
| -rw-r--r-- | csrc/algorithms/arrays/rotate.h | 311 | ||||
| -rw-r--r-- | csrc/algorithms/arrays/sorted.h | 250 | ||||
| -rw-r--r-- | csrc/algorithms/make_fun | 40 |
5 files changed, 893 insertions, 0 deletions
diff --git a/csrc/algorithms/arrays/minmax.h b/csrc/algorithms/arrays/minmax.h new file mode 100644 index 0000000..a9fb382 --- /dev/null +++ b/csrc/algorithms/arrays/minmax.h @@ -0,0 +1,220 @@ +/** + * Copyright © 2014 Mattias Andrée (maandree@member.fsf.org) + * + * This program is free software: you can redistribute it and/or modify + * it under the terms of the GNU Affero 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 Affero General Public License for more details. + * + * You should have received a copy of the GNU Affero General Public License + * along with this program. If not, see <http://www.gnu.org/licenses/>. + */ +#ifndef ALGO_ALGORITHMS_ARRAYS_MINMAX_H +#define ALGO_ALGORITHMS_ARRAYS_MINMAX_H + + +/* NB! This will not play nice if the placeholder `T` is + * not set to a type only containing [0-9A-Za-z_] (and $ + * in GNU C). Therefore, with the exception of `char`, + * `short`, `int`, `long`, `float` and `double`, you + * should only use `typedef`:ed types. */ + + +#include <stddef.h> + + +/** + * Find the minimum and maximum values in an array. + * + * `algo_make_implementation_of_get_bounds(T)` is used to make + * this function available for a particular data type `T`. And + * implementation without modifiers and attributes will be + * expanded. You may add `static`, `inline` and `__attribute__` + * before calling `algo_make_implementation_of_get_bounds(T)`. + * + * `algo_make_prototype_of_get_bounds(T)` is the prototype + * counterpart of `algo_make_implementation_of_get_bounds(T)`. + * It too is will not add any modifiers or attributes by + * default. It will neither add a semicolon at the end of + * the prototype. + * + * `algo_get_bounds(T)` is used to get the version of the + * function that supports the data type `T`. + * `&(algo_get_bounds(T))` gets the address of this function + * and `algo_get_bounds(T)(items, n, min, max)` calls the + * function. + * + * This function is not pure since it will edit the value + * of `min` and `max`. This function does not accept `NULL` + * arguments, if you are using GCC you should add + * `__attribute__((nonnull))` to its prototype. + * + * Undefined behaviour is invoked `n == 0`. + * + * @param items The items over to search. + * @param n The number of elements in `items`. + * @param min Output parameter for the minimum value. + * @param max Output parameter for the maximum value. + */ +//>fun () { +void algo_get_bounds__##T(const T* restrict items, size_t n, T* min, T* max) +{ + const T* end = items + n; + T maxv, minv, cur; + size_t i; + + max = min = *items++; + + while (items != end) + { + cur = *items++; + if (cur > maxv) maxv = cur; + else if (cur < minv) minv = cur; + } + + *min = min; + *max = max; +} +//>} ; . ../make_fun + + +/** + * Find the minimum and maximum values in an array. + * + * This variant of `algo_get_bounds` is suitable for + * non-numeric data. + * + * `algo_make_implementation_of_get_bounds_cmp(T)` is used to make + * this function available for a particular data type `T`. And + * implementation without modifiers and attributes will be + * expanded. You may add `static`, `inline` and `__attribute__` + * before calling `algo_make_implementation_of_get_bounds_cmp(T)`. + * + * `algo_make_prototype_of_get_bounds_cmp(T)` is the prototype + * counterpart of `algo_make_implementation_of_get_bounds_cmp(T)`. + * It too is will not add any modifiers or attributes by + * default. It will neither add a semicolon at the end of + * the prototype. + * + * `algo_get_bounds_cmp(T)` is used to get the version of the + * function that supports the data type `T`. + * `&(algo_get_bounds_cmp(T))` gets the address of this function + * and `algo_get_bounds_cmp(T)(items, n, cmp, min, max)` calls + * the function. + * + * This function is not pure since it will edit the value + * of `min` and `max`, and `cmp` is not necessarily pure. + * This function does not accept `NULL` arguments, if you + * are using GCC you should add `__attribute__((nonnull))` + * to its prototype. + * + * Undefined behaviour is invoked `n == 0`. + * + * @param items The items over to search. + * @param n The number of elements in `items`. + * @param cmp Function used to compare two items, it should return a. + * negative value if its first parameter is the lesser, a. + * positive value if its second parameter is the lesser. + * and zero if the parameters are equal. + * @param min Output parameter for the minimum value. + * @param max Output parameter for the maximum value. + */ +//>fun () { +void algo_get_bounds_cmp__##T(const T* restrict items, size_t n, + int (*cmp)(const T*, const T*), + T* min, T* max) +{ + const T* end = items + n; + T maxv, minv, cur; + size_t i; + + max = min = *items++; + + while (items != end) + { + cur = *items++; + if (cmp(cur, maxv) > 0) maxv = cur; + else if (cmp(cur, minv) < 0) minv = cur; + } + + *min = min; + *max = max; +} +//>} ; . ../make_fun + + +/** + * Find the minimum and maximum values in an array. + * + * This variant of `algo_get_bounds_cmp` allows you to + * store data needed for the comparison in a thread-safe + * way. It is reentrant. + * + * `algo_make_implementation_of_get_bounds_cmp_r(T)` is used to make + * this function available for a particular data type `T`. And + * implementation without modifiers and attributes will be + * expanded. You may add `static`, `inline` and `__attribute__` + * before calling `algo_make_implementation_of_get_bounds_cmp_r(T)`. + * + * `algo_make_prototype_of_get_bounds_cmp(T)` is the prototype + * counterpart of `algo_make_implementation_of_get_bounds_cmp_r(T)`. + * It too is will not add any modifiers or attributes by + * default. It will neither add a semicolon at the end of + * the prototype. + * + * `algo_get_bounds_cmp_r(T)` is used to get the version of the + * function that supports the data type `T`. + * `&(algo_get_bounds_cmp_r(T))` gets the address of this function + * and `algo_get_bounds_cmp_r(T)(items, n, cmp, data, min, max)` + * calls the function. + * + * This function is not pure since it will edit the value + * of `min` and `max`, and `cmp` is not necessarily pure. + * This function does not accept `NULL` arguments, if you + * are using GCC you should add `__attribute__((nonnull))` + * to its prototype. + * + * Undefined behaviour is invoked `n == 0`. + * + * @param items The items over to search. + * @param n The number of elements in `items`. + * @param cmp Function used to compare two items, it should return a + * negative value if its first parameter is the lesser, a + * positive value if its second parameter is the lesser + * and zero if the parameters are equal. `data` will be + * input as `cmp`'s third argument. + * @param data Arbitrary data (may be `NULL`) to pass throught to `cmp`. + * @param min Output parameter for the minimum value. + * @param max Output parameter for the maximum value. + */ +//>fun () { +void algo_get_bounds_cmp_r__##T(const T* restrict items, size_t n, + int (*cmp)(const T*, const T*, void*), + void* data, T* min, T* max) +{ + const T* end = items + n; + T maxv, minv, cur; + size_t i; + + max = min = *items++; + + while (items != end) + { + cur = *items++; + if (cmp(cur, maxv, data) > 0) maxv = cur; + else if (cmp(cur, minv, data) < 0) minv = cur; + } + + *min = min; + *max = max; +} +//>} ; . ../make_fun + + +#endif + diff --git a/csrc/algorithms/arrays/reverse.h b/csrc/algorithms/arrays/reverse.h new file mode 100644 index 0000000..88a7f27 --- /dev/null +++ b/csrc/algorithms/arrays/reverse.h @@ -0,0 +1,72 @@ +/** + * Copyright © 2014 Mattias Andrée (maandree@member.fsf.org) + * + * This program is free software: you can redistribute it and/or modify + * it under the terms of the GNU Affero 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 Affero General Public License for more details. + * + * You should have received a copy of the GNU Affero General Public License + * along with this program. If not, see <http://www.gnu.org/licenses/>. + */ +#ifndef ALGO_ALGORITHMS_ARRAYS_REVERSE_H +#define ALGO_ALGORITHMS_ARRAYS_REVERSE_H + + +/* NB! This will not play nice if the placeholder `T` is + * not set to a type only containing [0-9A-Za-z_] (and $ + * in GNU C). Therefore, with the exception of `char`, + * `short`, `int`, `long`, `float` and `double`, you + * should only use `typedef`:ed types. */ + + +#include <stddef.h> + + +/** + * Reverses an array. + * + * `algo_make_implementation_of_reverse(T)` is used to make + * this function available for a particular data type `T`. And + * implementation without modifiers and attributes will be + * expanded. You may add `static`, `inline` and `__attribute__` + * before calling `algo_make_implementation_of_reverse(T)`. + * + * `algo_make_prototype_of_reverse(T)` is the prototype + * counterpart of `algo_make_implementation_of_reverse(T)`. + * It too is will not add any modifiers or attributes by + * default. It will neither add a semicolon at the end of + * the prototype. + * + * `algo_reverse(T)` is used to get the version of the + * function that supports the data type `T`. + * `&(algo_reverse(T))` gets the address of this function + * and `algo_reverse(T)(items, n)` calls the function. + * + * @param items The array to reverse. + * @param n The number of elements in `items`. + */ +//>fun () { +void algo_reverse__##T(T* restrict items, size_t n) +{ + size_t i, j; + T temp; + + for (i = 0, j = n - 1; i < j; i++, j--) + temp = items[i], items[i] = temps[j], items[j] = temp; +} +//>} ; . ../make_fun + +/* For integer data (a ^= b, b ^= a, a ^= b) can be used. + * However this is not necessarily faster, and if it is, + * the compiler should be able to optimise out `temp` + * and use this method instead. */ + + +#endif + diff --git a/csrc/algorithms/arrays/rotate.h b/csrc/algorithms/arrays/rotate.h new file mode 100644 index 0000000..9791838 --- /dev/null +++ b/csrc/algorithms/arrays/rotate.h @@ -0,0 +1,311 @@ +/** + * Copyright © 2014 Mattias Andrée (maandree@member.fsf.org) + * + * This program is free software: you can redistribute it and/or modify + * it under the terms of the GNU Affero 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 Affero General Public License for more details. + * + * You should have received a copy of the GNU Affero General Public License + * along with this program. If not, see <http://www.gnu.org/licenses/>. + */ +#ifndef ALGO_ALGORITHMS_ARRAYS_ROTATE_H +#define ALGO_ALGORITHMS_ARRAYS_ROTATE_H + + +/* NB! This will not play nice if the placeholder `T` is + * not set to a type only containing [0-9A-Za-z_] (and $ + * in GNU C). Therefore, with the exception of `char`, + * `short`, `int`, `long`, `float` and `double`, you + * should only use `typedef`:ed types. */ + + +#include <stddef.h> + + +#define algo_macro_swap_items() \ + (temp = items[i], items[i] = temps[j], items[j] = temp) + + +/** + * Rotate an array. + * + * This function perform an inline rotation, it is probably + * faster if you create a new array and make a rotated copy + * into that array. It may even more faster to create a + * temporary array and copy the content back than using + * this inline rotation if you want the rotation to be + * stored in the same array. If you choose that latter, + * `alloca` can be used to create new array on the stack. + * + * `algo_make_implementation_of_rotate(T)` is used to make + * this function available for a particular data type `T`. And + * implementation without modifiers and attributes will be + * expanded. You may add `static`, `inline` and `__attribute__` + * before calling `algo_make_implementation_of_rotate(T)`. + * + * `algo_make_prototype_of_rotate(T)` is the prototype + * counterpart of `algo_make_implementation_of_rotate(T)`. + * It too is will not add any modifiers or attributes by + * default. It will neither add a semicolon at the end of + * the prototype. + * + * `algo_rotate(T)` is used to get the version of the + * function that supports the data type `T`. + * `&(algo_rotate(T))` gets the address of this function + * and `algo_rotate(T)(items, n)` calls the function. + * + * Undefined behaviour is invoked if `steps >= n`. + * + * @param items The array to rotate. + * @param n The number of elements in `items`. + * @param steps The number of steps to rotate the array + * rightwards. If you want a leftwards + * rotation you used call + * `algo_rotate(T)(items, n, (n - steps) % n)`. + */ +//>fun () { +void algo_rotate__##T(T* restrict items, size_t n, size_t steps) +{ + size_t i, j; + T temp; + + steps = (n - steps) % n; + for (i = 0, j = steps - 1; i < j; i++, j--) algo_macro_swap_items(); + for (i = steps, j = n - 1; i < j; i++, j--) algo_macro_swap_items(); + for (i = 0, j = n - 1; i < j; i++, j--) algo_macro_swap_items(); +} +//>} ; . ../make_fun + + +/** + * Rotate an array and reverse it afterwords. + * + * `algo_make_implementation_of_rotate_reverse(T)` is used + * to make this function available for a particular data + * type `T`. And implementation without modifiers and + * attributes will be expanded. You may add `static`, + * `inline` and `__attribute__` before calling + * `algo_make_implementation_of_rotate_reverse(T)`. + * + * `algo_make_prototype_of_rotate_reverse(T)` is the prototype + * counterpart of `algo_make_implementation_of_rotate_reverse(T)`. + * It too is will not add any modifiers or attributes by + * default. It will neither add a semicolon at the end of + * the prototype. + * + * `algo_rotate_reverse(T)` is used to get the version of the + * function that supports the data type `T`. + * `&(algo_rotate_reverse(T))` gets the address of this function + * and `algo_rotate_reverse(T)(items, n)` calls the function. + * + * Undefined behaviour is invoked if `steps >= n`. + * + * @param items The array to rotate. + * @param n The number of elements in `items`. + * @param steps The number of steps to rotate the array + * rightwards. If you want a leftwards + * rotation you used call + * `algo_rotate_reverse(T)(items, n, (n - steps) % n)`. + */ +//>fun () { +void algo_rotate_reverse__##T(T* restrict items, size_t n, size_t steps) +{ + size_t i, j; + T temp; + + steps = (n - steps) % n; + for (i = 0, j = steps - 1; i < j; i++, j--) algo_macro_swap_items(); + for (i = steps, j = n - 1; i < j; i++, j--) algo_macro_swap_items(); +} +//>} ; . ../make_fun + + +/** + * Reverse an array and rotate it afterwords. + * + * `algo_make_implementation_of_reverse_rotate(T)` is used + * to make this function available for a particular data + * type `T`. And implementation without modifiers and + * attributes will be expanded. You may add `static`, + * `inline` and `__attribute__` before calling + * `algo_make_implementation_of_reverse_rotate(T)`. + * + * `algo_make_prototype_of_reverse_rotate(T)` is the prototype + * counterpart of `algo_make_implementation_of_reverse_rotate(T)`. + * It too is will not add any modifiers or attributes by + * default. It will neither add a semicolon at the end of + * the prototype. + * + * `algo_reverse_rotate(T)` is used to get the version of the + * function that supports the data type `T`. + * `&(algo_reverse_rotate(T))` gets the address of this function + * and `algo_reverse_rotate(T)(items, n)` calls the function. + * + * Undefined behaviour is invoked if `steps >= n`. + * + * @param items The array to rotate. + * @param n The number of elements in `items`. + * @param steps The number of steps to rotate the array + * rightwards. If you want a leftwards + * rotation you used call + * `algo_reverse_rotate(T)(items, n, (n - steps) % n)`. + */ +//>fun () { +void algo_reverse_rotate__##T(T* restrict items, size_t n, size_t steps) +{ + size_t i, j; + T temp; + + for (i = 0, j = steps - 1; i < j; i++, j--) algo_macro_swap_items(); + for (i = steps, j = n - 1; i < j; i++, j--) algo_macro_swap_items(); +} +//>} ; . ../make_fun + + +/** + * Write a rotated copy of an array into another array. + * + * `algo_make_implementation_of_rotate_into(T)` is used to make + * this function available for a particular data type `T`. And + * implementation without modifiers and attributes will be + * expanded. You may add `static`, `inline` and `__attribute__` + * before calling `algo_make_implementation_of_rotate_into(T)`. + * + * `algo_make_prototype_of_rotate_into(T)` is the prototype + * counterpart of `algo_make_implementation_of_rotate_into(T)`. + * It too is will not add any modifiers or attributes by + * default. It will neither add a semicolon at the end of + * the prototype. + * + * `algo_rotate_into(T)` is used to get the version of the + * function that supports the data type `T`. + * `&(algo_rotate_into(T))` gets the address of this function + * and `algo_rotate_into(T)(items, n)` calls the function. + * + * Undefined behaviour is invoked if `steps >= n`. + * + * @param items The array to rotate. + * @param out The array to fill with a rotated copy of `items`. + * @param n The number of elements in `items` and in `out`. + * @param steps The number of steps to rotate the array + * rightwards. If you want a leftwards + * rotation you used call + * `algo_rotate_into(T)(items, out, n, (n - steps) % n)`. + */ +//>fun () { +void algo_rotate_into__##T(const T* restrict items, T* restrict out, size_t n, size_t steps) +{ + size_t m = n - steps; + T* restrict out_a = out + steps; + T* restrict out_b = out; + const T* end_a = items + m; + const T* end_b = items + n; + + while (items != end_a) *out_a++ = *items++; + while (items != end_b) *out_b++ = *items++; +} +//>} ; . ../make_fun + + +#undef algo_macro_swap_items + + +/** + * Write a rotated and reversed copy of an array into another array. + * + * `algo_make_implementation_of_rotate_reverse_into(T)` is used to + * make this function available for a particular data type `T`. And + * implementation without modifiers and attributes will be expanded. + * You may add `static`, `inline` and `__attribute__` before calling + * `algo_make_implementation_of_rotate_reverse_into(T)`. + * + * `algo_make_prototype_of_rotate_reverse_into(T)` is the prototype + * counterpart of `algo_make_implementation_of_rotate_reverse_into(T)`. + * It too is will not add any modifiers or attributes by default. It + * will neither add a semicolon at the end of the prototype. + * + * `algo_rotate_reverse_into(T)` is used to get the version of the + * function that supports the data type `T`. + * `&(algo_rotate_reverse_into(T))` gets the address of this function + * and `algo_rotate_reverse_into(T)(items, n)` calls the function. + * + * Undefined behaviour is invoked if `steps >= n`. + * + * @param items The array to rotate. + * @param out The array to fill with a rotated copy of `items`. + * @param n The number of elements in `items` and in `out`. + * @param steps The number of steps to rotate the array + * rightwards. If you want a leftwards + * rotation you used call + * `algo_rotate_reverse_into(T)(items, out, n, (n - steps) % n)`. + */ +//>fun () { +void algo_rotate_reverse_into__##T(const T* restrict items, T* restrict out, size_t n, size_t steps) +{ + size_t m = n - steps; + T* restrict out_a = out + n - steps; + T* restrict out_b = out + n; + const T* end_a = items + m; + const T* end_b = items + n; + + while (items != end_a) *--out_a = *items++; + while (items != end_b) *--out_b = *items++; +} +//>} ; . ../make_fun + + +/** + * Write a reversed and rotated copy of an array into another array. + * + * `algo_make_implementation_of_reverse_rotate_into(T)` is used to + * make this function available for a particular data type `T`. And + * implementation without modifiers and attributes will be expanded. + * You may add `static`, `inline` and `__attribute__` before calling + * `algo_make_implementation_of_reverse_rotate_into(T)`. + * + * `algo_make_prototype_of_reverse_rotate_into(T)` is the prototype + * counterpart of `algo_make_implementation_of_reverse_rotate_into(T)`. + * It too is will not add any modifiers or attributes by default. It + * will neither add a semicolon at the end of the prototype. + * + * `algo_reverse_rotate_into(T)` is used to get the version of the + * function that supports the data type `T`. + * `&(algo_reverse_rotate_into(T))` gets the address of this function + * and `algo_reverse_rotate_into(T)(items, n)` calls the function. + * + * Undefined behaviour is invoked if `steps >= n`. + * + * @param items The array to rotate. + * @param out The array to fill with a rotated copy of `items`. + * @param n The number of elements in `items` and in `out`. + * @param steps The number of steps to rotate the array + * rightwards. If you want a leftwards + * rotation you used call + * `algo_reverse_rotate_into(T)(items, out, n, (n - steps) % n)`. + */ +//>fun () { +void algo_reverse_rotate_into__##T(const T* restrict items, T* restrict out, size_t n, size_t steps) +{ + size_t m = n - steps; + T* restrict out_a = out + steps; + T* restrict out_b = out; + const T* end_a = out + n; + const T* end_b = out + steps; + + while (out_a != end_a) *out_a++ = *--items; + while (out_b != end_b) *out_b++ = *--items; +} +//>} ; . ../make_fun + + +#undef algo_macro_swap_items + + +#endif + diff --git a/csrc/algorithms/arrays/sorted.h b/csrc/algorithms/arrays/sorted.h new file mode 100644 index 0000000..71037ab --- /dev/null +++ b/csrc/algorithms/arrays/sorted.h @@ -0,0 +1,250 @@ +/** + * Copyright © 2014 Mattias Andrée (maandree@member.fsf.org) + * + * This program is free software: you can redistribute it and/or modify + * it under the terms of the GNU Affero 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 Affero General Public License for more details. + * + * You should have received a copy of the GNU Affero General Public License + * along with this program. If not, see <http://www.gnu.org/licenses/>. + */ +#ifndef ALGO_ALGORITHMS_ARRAYS_SORTED_H +#define ALGO_ALGORITHMS_ARRAYS_SORTED_H + + +/* NB! This will not play nice if the placeholder `T` is + * not set to a type only containing [0-9A-Za-z_] (and $ + * in GNU C). Therefore, with the exception of `char`, + * `short`, `int`, `long`, `float` and `double`, you + * should only use `typedef`:ed types. */ + + +#include <stddef.h> + + +/** + * The order elements are sorted in. + */ +typedef enum algo_sorted_order + { + /** + The array is not sorted. + */ + UNORDERED, + + /** + * The array is sorted in ascending (normal) order. + */ + ASCENDING_ORDER, + + /** + * The array is sorted in descending (reverse normal) order. + */ + DESCENDING_ORDER, + + /** + * All elements in the array are mutually equal or the array + * contains less than two elements. This is the bitwise OR of + * `ASCENDING_ORDER` and `DESCENDING_ORDER`. + */ + FLAT + + } algo_sorted_order_t; + + +/** + * Gets whether an array is sorted and in which order it is sorted. + * + * `algo_make_implementation_of_is_sorted(T)` is used to make + * this function available for a particular data type `T`. And + * implementation without modifiers and attributes will be + * expanded. You may add `static`, `inline` and `__attribute__` + * before calling `algo_make_implementation_of_is_sorted(T)`. + * + * `algo_make_prototype_of_is_sorted(T)` is the prototype + * counterpart of `algo_make_implementation_of_is_sorted(T)`. + * It too is will not add any modifiers or attributes by + * default. It will neither add a semicolon at the end of + * the prototype. + * + * `algo_is_sorted(T)` is used to get the version of the + * function that supports the data type `T`. + * `&(algo_is_sorted(T))` gets the address of this function + * and `algo_is_sorted(T)(items, n)` calls the function. + * + * This function is pure, if you use GCC you should add + * `__attribute__((pure))` to its prototype. + * + * @param items The items to check if they are ordered. + * @param n The number of elements in `items`. + * @return The order elements are sorted in. + */ +//>fun () { +algo_sorted_order_t algo_is_sorted__##T(const T* restrict items, size_t n) +{ + const T* end = items + n; + T last, cur; + algo_sorted_order_t order = FLAT; + + if (n == 0) + return FLAT; + + for (last = *items++; items != end; last = cur) + if (cur = *items++, last < cur) + { + if (order == FLAT) order = ASCENDING_ORDER; + else if (order == DESCENDING_ORDER) return UNORDERED; + } + else if (last > cur) + { + if (order == FLAT) order = DESCENDING_ORDER; + else if (order == ASCENDING_ORDER) return UNORDERED; + } + + return order; +} +//>} ; . ../make_fun + + +/** + * Gets whether an array is sorted and in which order it is sorted. + * + * This variant of `algo_is_sorted` is suitable for + * non-numeric data. + * + * `algo_make_implementation_of_is_sorted_cmp(T)` is used to make + * this function available for a particular data type `T`. And + * implementation without modifiers and attributes will be + * expanded. You may add `static`, `inline` and `__attribute__` + * before calling `algo_make_implementation_of_is_sorted_cmp(T)`. + * + * `algo_make_prototype_of_is_sorted_cmp(T)` is the prototype + * counterpart of `algo_make_implementation_of_is_sorted_cmp(T)`. + * It too is will not add any modifiers or attributes by + * default. It will neither add a semicolon at the end of + * the prototype. + * + * `algo_is_sorted_cmp(T)` is used to get the version of the + * function that supports the data type `T`. + * `&(algo_is_sorted_cmp(T))` gets the address of this function + * and `algo_is_sorted_cmp(T)(items, n, cmp)` calls the function. + * + * This function is not pure because `cmp` is not necessarily pure. + * + * @param items The items to check if they are ordered. + * @param n The number of elements in `items`. + * @param cmp Function used to compare two items, it should return a + * negative value if its first parameter is the lesser, a + * positive value if its second parameter is the lesser + * and zero if the parameters are equal. + * @return The order elements are sorted in. + */ +//>fun () { +algo_sorted_order_t algo_is_sorted_cmp__##T(const T* restrict items, size_t n, + int (*cmp)(const T*, const T*)) +{ + const T* end = items + n; + T last, cur; + algo_sorted_order_t order = FLAT; + int comparison; + + if (n == 0) + return FLAT; + + for (last = *items++; items != end; last = cur) + { + comparison = cmp(last, cur = *items++); + if (comparison < 0) + { + if (order == FLAT) order = ASCENDING_ORDER; + else if (order == DESCENDING_ORDER) return UNORDERED; + } + else if (comparison > 0) + { + if (order == FLAT) order = DESCENDING_ORDER; + else if (order == ASCENDING_ORDER) return UNORDERED; + } + } + + return order; +} +//>} ; . ../make_fun + + +/** + * Gets whether an array is sorted and in which order it is sorted. + * + * This variant of `algo_is_sorted_cmp` allows you to + * store data needed for the comparison in a thread-safe + * way. It is reentrant. + * + * `algo_make_implementation_of_is_sorted_cmp_r(T)` is used to make + * this function available for a particular data type `T`. And + * implementation without modifiers and attributes will be + * expanded. You may add `static`, `inline` and `__attribute__` + * before calling `algo_make_implementation_of_is_sorted_cmp_r(T)`. + * + * `algo_make_prototype_of_is_sorted_cmp_r(T)` is the prototype + * counterpart of `algo_make_implementation_of_is_sorted_cmp_r(T)`. + * It too is will not add any modifiers or attributes by + * default. It will neither add a semicolon at the end of + * the prototype. + * + * `algo_is_sorted_cmp_r(T)` is used to get the version of the + * function that supports the data type `T`. + * `&(algo_is_sorted_cmp_r(T))` gets the address of this function + * and `algo_is_sorted_cmp_r(T)(items, n, cmp)` calls the function. + * + * This function is not pure because `cmp` is not necessarily pure. + * + * @param items The items to check if they are ordered. + * @param n The number of elements in `items`. + * @param cmp Function used to compare two items, it should return a + * negative value if its first parameter is the lesser, a + * positive value if its second parameter is the lesser + * and zero if the parameters are equal. `data` will be + * input as `cmp`'s third argument. + * @param data Arbitrary data (may be `NULL`) to pass throught to `cmp`. + * and zero if the parameters are equal. + * @return The order elements are sorted in. + */ +//>fun () { +algo_sorted_order_t algo_is_sorted_cmp_r__##T(const T* restrict items, size_t n, + int (*cmp)(const T*, const T*, void*), void* data) +{ + const T* end = items + n; + T last, cur; + algo_sorted_order_t order = FLAT; + int comparison; + + if (n == 0) + return FLAT; + + for (last = *items++; items != end; last = cur) + { + comparison = cmp(last, cur = *items++, data); + if (comparison < 0) + { + if (order == FLAT) order = ASCENDING_ORDER; + else if (order == DESCENDING_ORDER) return UNORDERED; + } + else if (comparison > 0) + { + if (order == FLAT) order = DESCENDING_ORDER; + else if (order == ASCENDING_ORDER) return UNORDERED; + } + } + + return order; +} +//>} ; . ../make_fun + + +#endif + diff --git a/csrc/algorithms/make_fun b/csrc/algorithms/make_fun new file mode 100644 index 0000000..2e763ec --- /dev/null +++ b/csrc/algorithms/make_fun @@ -0,0 +1,40 @@ +# -*- shell-script -*- +# Copyright © 2014 Mattias Andrée (maandree@member.fsf.org) +# +# This program is free software: you can redistribute it and/or modify +# it under the terms of the GNU Affero 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 Affero General Public License for more details. +# +# You should have received a copy of the GNU Affero General Public License +# along with this program. If not, see <http://www.gnu.org/licenses/>. + +fun_name="$(fun | head -n 1 | cut -d \( -f 1 | cut -d \ -f 2 | sed -e 's/^algo_\(.*\)__.*$/\1/')" + +macroise () +{ + sed -e 's/$/\\/' | sed -e ':a;N;$!ba;s/\(.*\)\\$/\1/' +} +remove_empty_gpp_lines() +{ + sed -e '/^\x1b[0-9]*\x1b$/d' +} + +cat << EOF | macroise +#define algo_${fun_name}(T) +algo_${fun_name}__##T +EOF + +(cat << EOF ; fun) | macroise +#define algo_make_implementation_of_${fun_name}(T) +EOF + +(cat << EOF ; fun) | sed -e ':a;N;$!ba;s/^\([^{]*\).*$/\1/' | remove_empty_gpp_lines | macroise +#define algo_make_prototype_of_${fun_name}(T) +EOF + |