A pattern for command table

我們常常會需要比對字串/指令後, 執行對應的function, 常見的就是用for loop把command table比對過一次, 但是如果command table大, 效率就不好, 可以用qsort()+bsearch()做binary search以提升效率.

#include <stdio.h>
#include <string.h>

typedef void (*cmd_fp)(char *cmd);


/*
 * command function
 */
void hello(char *cmd)
{
    printf("%s(#%d)\n", __FUNCTION__, __LINE__);
}


/*
 * command function
 */
void world(char *cmd)
{
    printf("%s(#%d)\n", __FUNCTION__, __LINE__);
}

/* The structure for command entry */
struct cmd_ent {
    char const * cmd;
    cmd_fp fp;
} 
/* Command table - a command array */
cmd_tab[] = {
    {"hello", hello},
    {"world", world},
};

#define AR_SZ(a) (sizeof(a)/sizeof(a[0]))

int main(int argc, char *argv[])
{
    char cmd[64];
    int i;
    while(fgets(cmd, sizeof(cmd) - 1, stdin)) {
        cmd[strlen(cmd) - 1] = 0;
        for (i = 0; i < AR_SZ(cmd_tab); i++) {
            if (strcmp(cmd, cmd_tab[i].cmd) == 0) {
                cmd_tab[i].fp(cmd);
                break;
            }
        }
        if (i == AR_SZ(cmd_tab)) {
            printf("cmd not found\n");
        }
    }
}

qsort() + bsearch() version

#include <stdio.h>
#include <string.h>
#include <stdlib.h>

typedef void (*cmd_fp)(char *cmd);


/*
 * command function
 */
void hello(char *cmd)
{
    printf("%s(#%d)\n", __FUNCTION__, __LINE__);
}


/*
 * command function
 */
static void world(char *cmd)
{
    printf("%s(#%d)\n", __FUNCTION__, __LINE__);
}


/* The structure for command entry */
struct cmd_ent {
    char const * cmd;
    cmd_fp fp;
};


/* Command table that is qsort() + bsearch() version */
static struct cmd_tab {
    int sz; // total htab size
    int count; // how many comand entry stored in htab.
    struct cmd_ent *htab;
} cmd_tab;

/*
 * increas htab. it will be invoked once htab is full.
 */
static struct cmd_ent * realloc_htab_and_copy(int new_sz, struct cmd_ent *otab, int num)
{
    struct cmd_ent *ntab;
    ntab = (struct cmd_ent *) malloc(sizeof(struct cmd_ent) * new_sz);
    memset(ntab, 0, sizeof(struct cmd_ent) * new_sz);
    if (num) {
        memcpy(ntab, otab, sizeof(struct cmd_ent) * num);
        free(otab);
    }
    return ntab;
}

/* compare function is used for qsort()/sorting or bsearch()/searching */
static int compmi(const void *v1, const void *v2)
{
    struct cmd_ent* e1 = (struct cmd_ent*) v1;
    struct cmd_ent* e2 = (struct cmd_ent*) v2;
    return strcmp(e1->cmd, e2->cmd);
}

/* used for registering a new "cmd"/"fp" into comand table */
static void reg_cmd(char *cmd, cmd_fp fp)
{
    if (cmd_tab.sz == cmd_tab.count) {
        cmd_tab.sz = (cmd_tab.sz + 16) * 2;
        cmd_tab.htab = realloc_htab_and_copy(cmd_tab.sz, cmd_tab.htab, cmd_tab.count);
    }
    cmd_tab.htab[cmd_tab.count].cmd = cmd;
    cmd_tab.htab[cmd_tab.count].fp = fp;

    cmd_tab.count++;
    qsort(cmd_tab.htab, cmd_tab.count, sizeof(struct cmd_ent), compmi);
}

/* an example to register two commands into command table */
static void reg_cmds(void)
{
   reg_cmd("hello", hello);
   reg_cmd("world", world);
}

int main(int argc, char *argv[])
{
    char cmd[64];
    struct cmd_ent key, *res;
    int i;
    reg_cmds();
    while(fgets(cmd, sizeof(cmd) - 1, stdin)) {
       /* main body for command searching */
        cmd[strlen(cmd) - 1] = 0;
        key.cmd = cmd;
        res = bsearch(&key, cmd_tab.htab, cmd_tab.count, sizeof(struct cmd_ent), compmi);
        if (res == NULL) {
            printf("cmd not found\n");
        } else {
            res->fp(cmd);
        }
    }
}