fdupes  2.1.2
About: FDUPES finds duplicate files in a given set of directories.
  Fossies Dox: fdupes-2.1.2.tar.gz  ("unofficial" and yet experimental doxygen-generated source code documentation)  

commandidentifier.c
Go to the documentation of this file.
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)
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)
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 */
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)
109 }
110 
111 /* build tree to identify command names through state transitions */
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 
134 
135  return root;
136 }
137 
138 /* free memory used by command identifier tree structure */
140 {
141  int c;
142 
143  for (c = 0; c < tree->num_children; ++c)
145 
146  free(tree->children);
147  free(tree);
148 }
149 
150 /* find command identifier node matching given 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 }
compare_command_identifier_nodes
int compare_command_identifier_nodes(const void *a, const void *b)
Definition: commandidentifier.c:83
command_identifier_node::character
wchar_t character
Definition: commandidentifier.h:38
command_identifier_node::children
struct command_identifier_node ** children
Definition: commandidentifier.h:39
COMMAND_RECOGNIZER_OUT_OF_MEMORY
#define COMMAND_RECOGNIZER_OUT_OF_MEMORY
Definition: commandidentifier.h:24
commandidentifier.h
find_command_identifier_node
struct command_identifier_node * find_command_identifier_node(struct command_identifier_node *root, wchar_t character)
Definition: commandidentifier.c:151
free_command_identifier_tree
void free_command_identifier_tree(struct command_identifier_node *tree)
Definition: commandidentifier.c:139
command_identifier_node::command
int command
Definition: commandidentifier.h:37
COMMAND_AMBIGUOUS
#define COMMAND_AMBIGUOUS
Definition: commandidentifier.h:25
insert_command_identifier_command
int insert_command_identifier_command(struct command_identifier_node *tree, struct command_map *command, size_t ch)
Definition: commandidentifier.c:23
COMMAND_UNDEFINED
#define COMMAND_UNDEFINED
Definition: commandidentifier.h:26
command_identifier_node::num_children
size_t num_children
Definition: commandidentifier.h:40
command_map
Definition: commandidentifier.h:29
identify_command
int identify_command(struct command_identifier_node *tree, wchar_t *command_buffer, size_t ch)
Definition: commandidentifier.c:179
command_identifier_node
Definition: commandidentifier.h:36
build_command_identifier_tree
struct command_identifier_node * build_command_identifier_tree(struct command_map *commands)
Definition: commandidentifier.c:112
sort_command_identifier_nodes
void sort_command_identifier_nodes(struct command_identifier_node *root)
Definition: commandidentifier.c:100