summaryrefslogtreecommitdiffstats
path: root/examples/loadables/asort.c
diff options
context:
space:
mode:
Diffstat (limited to 'examples/loadables/asort.c')
-rw-r--r--examples/loadables/asort.c279
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
+};
generated by cgit v1.2.3 (git 2.39.1) at 2024-11-05 07:25:12 +0000