"Fossies" - the Fresh Open Source Software Archive

Member "fdupes-2.1.2/commandidentifier.c" (12 Aug 2020, 5791 Bytes) of package /linux/privat/fdupes-2.1.2.tar.gz:


As a special service "Fossies" has tried to format the requested source page into HTML format using (guessed) C and C++ source code syntax highlighting (style: standard) with prefixed line numbers and code folding option. Alternatively you can here view or download the uninterpreted source code file. For more information about "commandidentifier.c" see the Fossies "Dox" file reference documentation.

    1 /* Copyright (c) 2018 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 }