Take the 2-minute tour ×
Code Review Stack Exchange is a question and answer site for peer programmer code reviews. It's 100% free, no registration required.

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.

share|improve this question
    
Sort your array and bin search it, no? –  vnp yesterday
    
@vnp Would a binary search be better than a hash search? –  syb0rg yesterday
    
It is much simpler. Hundreds of thousands of commands translate to 30 or so binary steps. If even that is unacceptable, maybe hash is a way to go. However, the hash function must be very very good, for any conflict resolution incurs significant cost. –  vnp yesterday
    
@vnp Sounds like you should be writing an answer ;) –  syb0rg yesterday
add comment

1 Answer

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).

share|improve this answer
    
What would be the best way to sort the array during build time? I would prefer not to do it manually. –  syb0rg yesterday
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.