commandidentifier.c

   1 /* Copyright (c) 2018-2022 Adrian Lopez
   2
   3    This software is provided 'as-is', without any express or implied
   4    warranty. In no event will the authors be held liable for any damages
   5    arising from the use of this software.
   6
   7    Permission is granted to anyone to use this software for any purpose,
   8    including commercial applications, and to alter it and redistribute it
   9    freely, subject to the following restrictions:
  10
  11    1. The origin of this software must not be misrepresented; you must not
  12       claim that you wrote the original software. If you use this software
  13       in a product, an acknowledgment in the product documentation would be
  14       appreciated but is not required.
  15    2. Altered source versions must be plainly marked as such, and must not be
  16       misrepresented as being the original software.
  17    3. This notice may not be removed or altered from any source distribution. */
  18
  19 #include <stdlib.h>
  20 #include "commandidentifier.h"
  21
  22 /* insert new node into command identifier tree */
  23 int insert_command_identifier_command(struct command_identifier_node *tree, struct command_map *command, size_t ch)
  24 {
  25   struct command_identifier_node *child;
  26   struct command_identifier_node **alloc_children;
  27   int returned_command;
  28   int c;
  29
  30   /* find node for current character in command name */
  31   child = 0;
  32   for (c = 0; c < tree->num_children; ++c)
  33   {
  34     if (tree->children[c]->character == command->command_name[ch])
  35     {
  36       child = tree->children[c];
  37       break;
  38     }
  39   }
  40
  41   /* if sought node does not exist, create it */
  42   if (child == 0)
  43   {
  44     child = (struct command_identifier_node*) malloc(sizeof(struct command_identifier_node));
  45     if (child == 0)
  46       return COMMAND_RECOGNIZER_OUT_OF_MEMORY;
  47
  48     child->command = COMMAND_UNDEFINED;
  49     child->character = command->command_name[ch];
  50     child->children = 0;
  51     child->num_children = 0;
  52
  53     alloc_children = realloc(tree->children, sizeof(struct command_identifier_node*) * (tree->num_children + 1));
  54     if (alloc_children == 0)
  55       return COMMAND_RECOGNIZER_OUT_OF_MEMORY;
  56
  57     tree->children = alloc_children;
  58
  59     tree->children[tree->num_children++] = child;
  60   }
  61
  62   /* if last character in command name, make child a leaf node */
  63   if (command->command_name[ch] == L'\0')
  64   {
  65     child->command = command->command;
  66     return child->command;
  67   }
  68   else /* grow the tree */
  69   {
  70     returned_command = insert_command_identifier_command(child, command, ch + 1);
  71
  72     /* record whether the tree at this point leads to a single command (abbreviation) or many (ambiguous) */
  73     if (tree->command == COMMAND_UNDEFINED)
  74       tree->command = returned_command;
  75     else
  76       tree->command = COMMAND_AMBIGUOUS;
  77   }
  78
  79   return tree->command;
  80 }
  81
  82 /* compare two command identifier nodes by the characters they match */
  83 int compare_command_identifier_nodes(const void *a, const void *b)
  84 {
  85   const struct command_identifier_node *aa;
  86   const struct command_identifier_node *bb;
  87
  88   aa = *(struct command_identifier_node**)a;
  89   bb = *(struct command_identifier_node**)b;
  90
  91   if (aa->character > bb->character)
  92     return 1;
  93   else if (aa->character < bb->character)
  94     return -1;
  95   else
  96     return 0;
  97 }
  98
  99 /* sort command identifier nodes in alphabetical order */
 100 void sort_command_identifier_nodes(struct command_identifier_node *root)
 101 {
 102   int c;
 103
 104   if (root->num_children > 1)
 105     qsort(root->children, root->num_children, sizeof(struct command_identifier_node *), compare_command_identifier_nodes);
 106
 107   for (c = 0; c < root->num_children; ++c)
 108     sort_command_identifier_nodes(root->children[c]);
 109 }
 110
 111 /* build tree to identify command names through state transitions */
 112 struct command_identifier_node *build_command_identifier_tree(struct command_map *commands)
 113 {
 114   struct command_identifier_node *root;
 115   int c;
 116
 117   root = (struct command_identifier_node*) malloc(sizeof(struct command_identifier_node));
 118   if (root == 0)
 119     return 0;
 120
 121   root->command = COMMAND_UNDEFINED;
 122   root->character = L'\0';
 123   root->children = 0;
 124   root->num_children = 0;
 125
 126   c = 0;
 127   while (commands[c].command_name != 0)
 128   {
 129     insert_command_identifier_command(root, commands + c, 0);
 130     ++c;
 131   }
 132
 133   sort_command_identifier_nodes(root);
 134
 135   return root;
 136 }
 137
 138 /* free memory used by command identifier tree structure */
 139 void free_command_identifier_tree(struct command_identifier_node *tree)
 140 {
 141   int c;
 142
 143   for (c = 0; c < tree->num_children; ++c)
 144     free_command_identifier_tree(tree->children[c]);
 145
 146   free(tree->children);
 147   free(tree);
 148 }
 149
 150 /* find command identifier node matching given character */
 151 struct command_identifier_node *find_command_identifier_node(struct command_identifier_node *root, wchar_t character)
 152 {
 153   long min;
 154   long max;
 155   long mid;
 156
 157   if (root->num_children == 0)
 158     return 0;
 159
 160   min = 0;
 161   max = root->num_children - 1;
 162
 163   do
 164   {
 165     mid = (min + max) / 2;
 166
 167     if (character > root->children[mid]->character)
 168       min = mid + 1;
 169     else if (character < root->children[mid]->character)
 170       max = mid - 1;
 171     else
 172       return root->children[mid];
 173   } while (min <= max);
 174
 175   return 0;
 176 }
 177
 178 /* determine ID for given command string (possibly abbreviated), if found */
 179 int identify_command(struct command_identifier_node *tree, wchar_t *command_buffer, size_t ch)
 180 {
 181   struct command_identifier_node *found;
 182
 183   if (command_buffer[ch] != L' ')
 184     found = find_command_identifier_node(tree, command_buffer[ch]);
 185   else
 186     found = find_command_identifier_node(tree, L'\0');
 187
 188   if (found)
 189   {
 190     if (command_buffer[ch] == L'\0' || command_buffer[ch] == L' ')
 191       return found->command;
 192     else
 193       return identify_command(found, command_buffer, ch + 1);
 194   }
 195   else
 196   {
 197     if (command_buffer[ch] == L'\0' || command_buffer[ch] == L' ')
 198       return tree->command;
 199     else
 200       return COMMAND_UNDEFINED;
 201   }
 202 }