diff options
author | Daniel Baumann <daniel.baumann@progress-linux.org> | 2024-04-07 15:38:56 +0000 |
---|---|---|
committer | Daniel Baumann <daniel.baumann@progress-linux.org> | 2024-04-07 15:38:56 +0000 |
commit | 6c20c8ed2cb9ab69a1a57ccb2b9b79969a808321 (patch) | |
tree | f63ce19d57fad3ac4a15bc26dbfbfa2b834111b5 /examples/loadables/asort.c | |
parent | Initial commit. (diff) | |
download | bash-upstream.tar.xz bash-upstream.zip |
Adding upstream version 5.2.15.upstream/5.2.15upstream
Signed-off-by: Daniel Baumann <daniel.baumann@progress-linux.org>
Diffstat (limited to '')
-rw-r--r-- | examples/loadables/asort.c | 279 |
1 files changed, 279 insertions, 0 deletions
diff --git a/examples/loadables/asort.c b/examples/loadables/asort.c new file mode 100644 index 0000000..e847ef8 --- /dev/null +++ b/examples/loadables/asort.c @@ -0,0 +1,279 @@ +/* + Copyright (C) 2020 Free Software Foundation, Inc. + + Bash 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. + + Bash 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 Bash. If not, see <http://www.gnu.org/licenses/>. +*/ +#include <stdlib.h> +#include <string.h> +#include <inttypes.h> + +#include "bashtypes.h" +#include "shell.h" +#include "builtins.h" +#include "common.h" +#include "xmalloc.h" +#include "bashgetopt.h" + +typedef struct sort_element { + ARRAY_ELEMENT *v; // used when sorting array in-place + char *key; // used when sorting assoc array + char *value; // points to value of array element or assoc entry + double num; // used for numeric sort +} sort_element; + +static int reverse_flag; +static int numeric_flag; + +static int +compare(const void *p1, const void *p2) { + const sort_element e1 = *(sort_element *) p1; + const sort_element e2 = *(sort_element *) p2; + + if (numeric_flag) { + if (reverse_flag) + return (e2.num > e1.num) ? 1 : (e2.num < e1.num) ? -1 : 0; + else + return (e1.num > e2.num) ? 1 : (e1.num < e2.num) ? -1 : 0; + } + else { + if (reverse_flag) + return strcoll(e2.value, e1.value); + else + return strcoll(e1.value, e2.value); + } +} + +static int +sort_index(SHELL_VAR *dest, SHELL_VAR *source) { + HASH_TABLE *hash; + BUCKET_CONTENTS *bucket; + sort_element *sa; + ARRAY *array, *dest_array; + ARRAY_ELEMENT *ae; + size_t i, j, n; + char ibuf[INT_STRLEN_BOUND (intmax_t) + 1]; // used by fmtulong + char *key; + + dest_array = array_cell(dest); + + if (assoc_p(source)) { + hash = assoc_cell(source); + n = hash->nentries; + sa = xmalloc(n * sizeof(sort_element)); + i = 0; + for ( j = 0; j < hash->nbuckets; ++j ) { + bucket = hash->bucket_array[j]; + while ( bucket ) { + sa[i].v = NULL; + sa[i].key = bucket->key; + if ( numeric_flag ) + sa[i].num = strtod(bucket->data, NULL); + else + sa[i].value = bucket->data; + i++; + bucket = bucket->next; + } + } + } + else { + array = array_cell(source); + n = array_num_elements(array); + sa = xmalloc(n * sizeof(sort_element)); + i = 0; + + for (ae = element_forw(array->head); ae != array->head; ae = element_forw(ae)) { + sa[i].v = ae; + if (numeric_flag) + sa[i].num = strtod(element_value(ae), NULL); + else + sa[i].value = element_value(ae); + i++; + } + } + + // sanity check + if ( i != n ) { + builtin_error("%s: corrupt array", source->name); + return EXECUTION_FAILURE; + } + + qsort(sa, n, sizeof(sort_element), compare); + + array_flush(dest_array); + + for ( i = 0; i < n; ++i ) { + if ( assoc_p(source) ) + key = sa[i].key; + else + key = fmtulong((long unsigned)sa[i].v->ind, 10, ibuf, sizeof(ibuf), 0); + + array_insert(dest_array, i, key); + } + + return EXECUTION_SUCCESS; +} + +static int +sort_inplace(SHELL_VAR *var) { + size_t i, n; + ARRAY *a; + ARRAY_ELEMENT *ae; + sort_element *sa = 0; + + a = array_cell(var); + n = array_num_elements(a); + + if ( n == 0 ) + return EXECUTION_SUCCESS; + + sa = xmalloc(n * sizeof(sort_element)); + + i = 0; + for (ae = element_forw(a->head); ae != a->head; ae = element_forw(ae)) { + sa[i].v = ae; + if (numeric_flag) + sa[i].num = strtod(element_value(ae), NULL); + else + sa[i].value = element_value(ae); + i++; + } + + // sanity check + if ( i != n ) { + builtin_error("%s: corrupt array", var->name); + return EXECUTION_FAILURE; + } + + qsort(sa, n, sizeof(sort_element), compare); + + // for in-place sort, simply "rewire" the array elements + sa[0].v->prev = sa[n-1].v->next = a->head; + a->head->next = sa[0].v; + a->head->prev = sa[n-1].v; + a->max_index = n - 1; + for (i = 0; i < n; i++) { + sa[i].v->ind = i; + if (i > 0) + sa[i].v->prev = sa[i-1].v; + if (i < n - 1) + sa[i].v->next = sa[i+1].v; + } + xfree(sa); + return EXECUTION_SUCCESS; +} + +int +asort_builtin(WORD_LIST *list) { + SHELL_VAR *var, *var2; + char *word; + int opt, ret; + int index_flag = 0; + + numeric_flag = 0; + reverse_flag = 0; + + reset_internal_getopt(); + while ((opt = internal_getopt(list, "inr")) != -1) { + switch (opt) { + case 'i': index_flag = 1; break; + case 'n': numeric_flag = 1; break; + case 'r': reverse_flag = 1; break; + CASE_HELPOPT; + default: + builtin_usage(); + return (EX_USAGE); + } + } + list = loptend; + + if (list == 0) { + builtin_usage(); + return EX_USAGE; + } + + if (legal_identifier (list->word->word) == 0) { + sh_invalidid (list->word->word); + return EXECUTION_FAILURE; + } + + if ( index_flag ) { + if ( list->next == 0 || list->next->next ) { + builtin_usage(); + return EX_USAGE; + } + if (legal_identifier (list->next->word->word) == 0) { + sh_invalidid (list->next->word->word); + return EXECUTION_FAILURE; + } + var = find_or_make_array_variable(list->word->word, 1); + if (var == 0) + return EXECUTION_FAILURE; + var2 = find_variable(list->next->word->word); + if ( !var2 || ( !array_p(var2) && !assoc_p(var2) ) ) { + builtin_error("%s: Not an array", list->next->word->word); + return EXECUTION_FAILURE; + } + return sort_index(var, var2); + } + + while (list) { + word = list->word->word; + var = find_variable(word); + list = list->next; + + if (var == 0 || array_p(var) == 0) { + builtin_error("%s: Not an array", word); + continue; + } + if (readonly_p(var) || noassign_p(var)) { + if (readonly_p(var)) + err_readonly(word); + continue; + } + + if ( (ret = sort_inplace(var)) != EXECUTION_SUCCESS ) + return ret; + } + return EXECUTION_SUCCESS; + +} + +char *asort_doc[] = { + "Sort arrays in-place.", + "", + "Options:", + " -n compare according to string numerical value", + " -r reverse the result of comparisons", + " -i sort using indices/keys", + "", + "If -i is supplied, SOURCE is not sorted in-place, but the indices (or keys", + "if associative) of SOURCE, after sorting it by its values, are placed as", + "values in the indexed array DEST", + "", + "Associative arrays may not be sorted in-place.", + "", + "Exit status:", + "Return value is zero unless an error happened (like invalid variable name", + "or readonly array).", + (char *)NULL +}; + +struct builtin asort_struct = { + "asort", + asort_builtin, + BUILTIN_ENABLED, + asort_doc, + "asort [-nr] array ... or asort [-nr] -i dest source", + 0 +}; |