examples/loadables/asort.c

   1 /*
   2    Copyright (C) 2020 Free Software Foundation, Inc.
   3
   4    Bush is free software: you can redistribute it and/or modify
   5    it under the terms of the GNU General Public License as published by
   6    the Free Software Foundation, either version 3 of the License, or
   7    (at your option) any later version.
   8
   9    Bush is distributed in the hope that it will be useful,
  10    but WITHOUT ANY WARRANTY; without even the implied warranty of
  11    MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  12    GNU General Public License for more details.
  13
  14    You should have received a copy of the GNU General Public License
  15    along with Bush.  If not, see <http://www.gnu.org/licenses/>.
  16 */
  17 #include <stdlib.h>
  18 #include <string.h>
  19 #include <inttypes.h>
  20
  21 #include "bushtypes.h"
  22 #include "shell.h"
  23 #include "builtins.h"
  24 #include "common.h"
  25 #include "xmalloc.h"
  26 #include "bushgetopt.h"
  27
  28 typedef struct sort_element {
  29     ARRAY_ELEMENT *v;   // used when sorting array in-place
  30     char *key;          // used when sorting assoc array
  31     char *value;        // points to value of array element or assoc entry
  32     double num;         // used for numeric sort
  33 } sort_element;
  34
  35 static int reverse_flag;
  36 static int numeric_flag;
  37
  38 static int
  39 compare(const void *p1, const void *p2) {
  40     const sort_element e1 = *(sort_element *) p1;
  41     const sort_element e2 = *(sort_element *) p2;
  42
  43     if (numeric_flag) {
  44         if (reverse_flag)
  45             return (e2.num > e1.num) ? 1 : (e2.num < e1.num) ? -1 : 0;
  46         else
  47             return (e1.num > e2.num) ? 1 : (e1.num < e2.num) ? -1 : 0;
  48     }
  49     else {
  50         if (reverse_flag)
  51             return strcoll(e2.value, e1.value);
  52         else
  53             return strcoll(e1.value, e2.value);
  54     }
  55 }
  56
  57 static int
  58 sort_index(SHELL_VAR *dest, SHELL_VAR *source) {
  59     HASH_TABLE *hash;
  60     BUCKET_CONTENTS *bucket;
  61     sort_element *sa;
  62     ARRAY *array, *dest_array;
  63     ARRAY_ELEMENT *ae;
  64     size_t i, j, n;
  65     char ibuf[INT_STRLEN_BOUND (intmax_t) + 1]; // used by fmtulong
  66     char *key;
  67
  68     dest_array = array_cell(dest);
  69
  70     if (assoc_p(source)) {
  71         hash = assoc_cell(source);
  72         n = hash->nentries;
  73         sa = xmalloc(n * sizeof(sort_element));
  74         i = 0;
  75         for ( j = 0; j < hash->nbuckets; ++j ) {
  76             bucket = hash->bucket_array[j];
  77             while ( bucket ) {
  78                 sa[i].v = NULL;
  79                 sa[i].key = bucket->key;
  80                 if ( numeric_flag )
  81                     sa[i].num = strtod(bucket->data, NULL);
  82                 else
  83                     sa[i].value = bucket->data;
  84                 i++;
  85                 bucket = bucket->next;
  86             }
  87         }
  88     }
  89     else {
  90         array = array_cell(source);
  91         n = array_num_elements(array);
  92         sa = xmalloc(n * sizeof(sort_element));
  93         i = 0;
  94
  95         for (ae = element_forw(array->head); ae != array->head; ae = element_forw(ae)) {
  96             sa[i].v = ae;
  97             if (numeric_flag)
  98                 sa[i].num = strtod(element_value(ae), NULL);
  99             else
 100                 sa[i].value = element_value(ae);
 101             i++;
 102         }
 103     }
 104
 105     // sanity check
 106     if ( i != n ) {
 107         builtin_error("%s: corrupt array", source->name);
 108         return EXECUTION_FAILURE;
 109     }
 110
 111     qsort(sa, n, sizeof(sort_element), compare);
 112
 113     array_flush(dest_array);
 114
 115     for ( i = 0; i < n; ++i ) {
 116         if ( assoc_p(source) )
 117             key = sa[i].key;
 118         else
 119             key = fmtulong((long unsigned)sa[i].v->ind, 10, ibuf, sizeof(ibuf), 0);
 120
 121         array_insert(dest_array, i, key);
 122     }
 123
 124     return EXECUTION_SUCCESS;
 125 }
 126
 127 static int
 128 sort_inplace(SHELL_VAR *var) {
 129     size_t i, n;
 130     ARRAY *a;
 131     ARRAY_ELEMENT *ae;
 132     sort_element *sa = 0;
 133
 134     a = array_cell(var);
 135     n = array_num_elements(a);
 136
 137     if ( n == 0 )
 138         return EXECUTION_SUCCESS;
 139
 140     sa = xmalloc(n * sizeof(sort_element));
 141
 142     i = 0;
 143     for (ae = element_forw(a->head); ae != a->head; ae = element_forw(ae)) {
 144         sa[i].v = ae;
 145         if (numeric_flag)
 146             sa[i].num = strtod(element_value(ae), NULL);
 147         else
 148             sa[i].value = element_value(ae);
 149         i++;
 150     }
 151
 152     // sanity check
 153     if ( i != n ) {
 154         builtin_error("%s: corrupt array", var->name);
 155         return EXECUTION_FAILURE;
 156     }
 157
 158     qsort(sa, n, sizeof(sort_element), compare);
 159
 160     // for in-place sort, simply "rewire" the array elements
 161     sa[0].v->prev = sa[n-1].v->next = a->head;
 162     a->head->next = sa[0].v;
 163     a->head->prev = sa[n-1].v;
 164     a->max_index = n - 1;
 165     for (i = 0; i < n; i++) {
 166         sa[i].v->ind = i;
 167         if (i > 0)
 168             sa[i].v->prev = sa[i-1].v;
 169         if (i < n - 1)
 170             sa[i].v->next = sa[i+1].v;
 171     }
 172     xfree(sa);
 173     return EXECUTION_SUCCESS;
 174 }
 175
 176 int
 177 asort_builtin(WORD_LIST *list) {
 178     SHELL_VAR *var, *var2;
 179     char *word;
 180     int opt, ret;
 181     int index_flag = 0;
 182
 183     numeric_flag = 0;
 184     reverse_flag = 0;
 185
 186     reset_internal_getopt();
 187     while ((opt = internal_getopt(list, "inr")) != -1) {
 188         switch (opt) {
 189             case 'i': index_flag = 1; break;
 190             case 'n': numeric_flag = 1; break;
 191             case 'r': reverse_flag = 1; break;
 192             CASE_HELPOPT;
 193             default:
 194                 builtin_usage();
 195                 return (EX_USAGE);
 196         }
 197     }
 198     list = loptend;
 199
 200     if (list == 0) {
 201         builtin_usage();
 202         return EX_USAGE;
 203     }
 204
 205     if (legal_identifier (list->word->word) == 0) {
 206         sh_invalidid (list->word->word);
 207         return EXECUTION_FAILURE;
 208     }
 209
 210     if ( index_flag ) {
 211         if ( list->next == 0 || list->next->next ) {
 212             builtin_usage();
 213             return EX_USAGE;
 214         }
 215         if (legal_identifier (list->next->word->word) == 0) {
 216             sh_invalidid (list->next->word->word);
 217             return EXECUTION_FAILURE;
 218         }
 219         var = find_or_make_array_variable(list->word->word, 1);
 220         if (var == 0)
 221             return EXECUTION_FAILURE;
 222         var2 = find_variable(list->next->word->word);
 223         if ( !var2 || ( !array_p(var2) && !assoc_p(var2) ) ) {
 224             builtin_error("%s: Not an array", list->next->word->word);
 225             return EXECUTION_FAILURE;
 226         }
 227         return sort_index(var, var2);
 228     }
 229
 230     while (list) {
 231         word = list->word->word;
 232         var = find_variable(word);
 233         list = list->next;
 234
 235         if (var == 0 || array_p(var) == 0) {
 236             builtin_error("%s: Not an array", word);
 237             continue;
 238         }
 239         if (readonly_p(var) || noassign_p(var)) {
 240             if (readonly_p(var))
 241                 err_readonly(word);
 242             continue;
 243         }
 244
 245         if ( (ret = sort_inplace(var)) != EXECUTION_SUCCESS )
 246             return ret;
 247     }
 248     return EXECUTION_SUCCESS;
 249
 250 }
 251
 252 char *asort_doc[] = {
 253     "Sort arrays in-place.",
 254     "",
 255     "Options:",
 256     "  -n  compare according to string numerical value",
 257     "  -r  reverse the result of comparisons",
 258     "  -i  sort using indices/keys",
 259     "",
 260     "If -i is supplied, SOURCE is not sorted in-place, but the indices (or keys",
 261     "if associative) of SOURCE, after sorting it by its values, are placed as",
 262     "values in the indexed array DEST",
 263     "",
 264     "Associative arrays may not be sorted in-place.",
 265     "",
 266     "Exit status:",
 267     "Return value is zero unless an error happened (like invalid variable name",
 268     "or readonly array).",
 269     (char *)NULL
 270 };
 271
 272 struct builtin asort_struct = {
 273     "asort",
 274     asort_builtin,
 275     BUILTIN_ENABLED,
 276     asort_doc,
 277     "asort [-nr] array ...  or  asort [-nr] -i dest source",
 278     0
 279 };