CODEWITHSUNDEEP
cparsingconsole
Katya Veselnitskaya
Katya Veselnitskaya

Reputation: 60

Tab Completion and Partial Completion

I would like to make a program which accepts commands in a way similar to that of ip on Linux. For example, I want to have a full command of show interface options but the user could type in just show in options or even just s i o if they did not conflict with other commands.

I have some ideas of how to go about this, and I would like to do this in C. So the question is what would be a good way of going about this while remaining as portable as possible between Linux/UNIX systems.

My first thought is to have a linked list. Each list item to point to the next command in an array of strings, with the final command having the address to a function call (please excuse my sloppy pseudocode).

header.h

typedef int8_t (__cdecl *proc_stub)(void *data, uint16_t len);
typedef struct s_proc_stub
{
    char command[16];
    proc_stub proc;
    struct s_proc_stub *next;
};
struct s_proc_stub proc_list[] =
{
    { "cmd", CommandFunction, ... },
    { "set", SetFunction, ... },
    ...
};

I feel like one downfall of this may be extra CPU and RAM utilisation. It may also be prone to error which can lead to vulnerabilities. This process will be facing the Internet, so I would like to ensure the security of the code.

My next thought was to use strtok() and just do an strnicmp() against each token. Another alternative is to use pointer arithmetic to simulate strtok() faster and without modifying the buffer. I feel like strtok is the most straight forward approach and the least error prone, but I want to say that I recall strtok() has some extra overhead compared to the other two methods.

The target platform for this is a Raspberry Pi, which has only about 2GB of RAM to work with. The drives are frequently quite small, and the CPU is okay but not ideal for heavy processing. I anticipate the processes being under heavy load from command processing, so I would like the ideal solution for minimising the amount of RAM and CPU usage. I would love to hear some methods that I am not aware of! :)

Upvotes: 0

Views: 73

Answers (2)

Neil
Neil

Reputation: 1922

I think a trie (prefix tree) data-structure is appropriate, https://en.wikipedia.org/wiki/Trie; specifically, minimising the amount of memory, one may prefer a compact prefix tree, (radix tree.) From, https://en.wikipedia.org/wiki/Radix_tree:

In a trie, all comparisons require constant time, but it takes m comparisons to look up a string of length m. Radix trees can perform these operations with fewer comparisons, and require many fewer nodes.

Here is an implementation, https://stackoverflow.com/a/31718868/2472827.

Upvotes: 1

Guilherme Borges
Guilherme Borges

Reputation: 165

I don't know if this might be useful or not, but if you don't want to reinvent the wheel, take a look at GNU readline, the library used for this kind of stuff in GNU/Linux.

Upvotes: 1

Related Questions