Scalability of running commands from user input

Question

Here is some code I have that has been extracted and shrunk down from a project of mine.

#include <stdio.h> #include <stdint.h> #include <time.h> #include <string.h> #define streq(x, y) (strcmp((x), (y)) == 0) #define ARRAY_SIZE(x) (sizeof(x)/sizeof(x[0])) typedef struct { const char *cmd; void* (*fn)(void); } __attribute__((__packed__)) Command; void* getTime(void) { return ((void*)((uintptr_t)time(NULL))); } void* getDay(void) { time_t t = time(NULL); struct tm tm = *localtime(&t); return ((void*)((uintptr_t)(tm.tm_wday))); } static Command commands[] = { {"time", getTime}, {"day", getDay}, }; int main(int argc, char *argv[]) { for (int i = 0; i < ARRAY_SIZE(commands); ++i) { Command *p = commands+i; if (streq(argv[1], p->cmd)) printf("%d\n", (int)p->fn()); } } 

When run with some given input, it runs the method associated with that input. Since this is a scaled down version of my project, it can only run two commands.

$ ./test-command day 4 

---

Right now, my implementation should run with \$ O \left( n\right)\$ time complexity. This would be unacceptable with the hundreds of thousands of commands my project could scale to. I am looking for reviews on scalability and optimization, and how well my Command structure and function pointer template would scale as well.

Answer 1

1. Sorting the command list prior to compile time is not that much of a burden. If there a propensity to fail to do so, a simple run-time check in the DEBUG version of code would detect it.

2. Hash is the way to go for high speed, but a simple binary search would be useful to begin with to iron out initial code development issues.

3. To help with string compare speeds have done this ((x[0] == y[0]) && (strcmp((x), (y)) == 0)), but this may be premature optimization.

4. Minor: Suggest replacing void* with some large unsigned integer like uintmax_t as the generic return type for the various functions void* (*fn)(void). Or better yet, a union of the various types.

   typedef union { time_t t; void *p ; int i; } Return_T; 

5. Minor: localtime() could return NULL. Best to test function return value before dereference.

6. Minor: Suggest const. static const Command commands[] = ....

7. Minor: Best to make array indexes size_t: size_t i = 0; ... Command *p = commands+i;

8. Minor: Casting (uintptr_t)time(NULL) and then to int in printf("%d\n", (int)p->fn()); can easily lose significant data. See note #4.

---

bsearch() example: something like the following untested code

static int compar(const void *a, const void *b) { const char *key = (const char *) a; const Command *element = (const Command *) b; return strcmp(key, element->cmd); } void main(int argc, char *argv[]) { Command *match = bsearch(argv[1], commands, ARRAY_SIZE(commands), sizeof commands[0], compar); if (match != NULL) { printf("%d\n", (int) (match->fn())); } } 

Answer 2

As requested.

An unstructured array may only be searched in linear order. To get better asymptotics you need a more search-friendly structure. A simplest solution would be to presort the Command array, and apply a binary search to find the command. A definite advantage here is a possibility to use standard library. You may even have the array sorted during build time.

For hundreds of thousands of commands the binary search would complete in about 20 lookups. If this is unacceptable, and your commands' names let you come up with a perfect hash function, hash is a way to go. Beware that a hash function must be really perfect - that is, almost no conflicts and almost no misses. Otherwise, the asymptotic constant would defeat all the advantages of O(1).

Update: assuming a unixish environment, the best way to sort at the build time is to have a commands.c file as

static Commands commands[] = { #include "command-list.c" }; 

with a command-list.txt text file

"time", getTime "day", getDay 

and a Makefile rule saying something like (may require some backslashes)

%.c: %.txt sort $< | sed -e 's/.*/{&},/' > $@