Long IF tree with strings

Question

I have a C program which uses Lua for scripting. In order to keep readability and avoid importing several constants within the individual Lua states, I condense a large amount of functions within a simple call (such as "ObjectSet(id, "ANGLE", 45)"), by using an "action" string.

To do this I have a large if tree comparing the action string to a list (such as "if(stringcompare(action, "ANGLE") ... else if (stringcompare(action, "X")... etc")

This approach works well, and within the program it's not really slow, and is fairly quick to add a new action. But I kind of feel perfectionist. Is there a better way to do this in C?

And having Lua in heavy use, maybe there is a way to use it for this purpose? (embedded "chunks" making a dictionary?) Although this part is mostly curiosity.

Edit: I should note I am not using C++

Answer 1

you could always play around with ternary operators. For example, instead of doing something like

   if(condition){
        a=b+c;
   }else{
        a=b+d;
   }

you can replace it with

   a=b+(condition?c:d);

there are a lot of small situation where the code can be whittled down(at a small cost of readability and no real speed boost). But if not there aren't any real ways to do it better. The exception to this is if you could describe it as a state machine and then you could use a switch case system.

Answer 2

You can build yourself an automata that checks character by character, like

if (curChar == 'a')
{
  curChar = next;
  if (curChar == 'b')
  {
     // all strings that begin with "ab"
  }
}

This will optimize comparisons having O(n) instead that O(n*m) for the whole if chain. Of course you won't have to do it by hand: you can search for an automated tool that can build your matching automaton from the strings you need.. actually this is similar to what a regexp matcher does.

Otherwise, if you want O(1) O(nlogn) (sorry, thought it used an hashmap instead that a binary tree) you can use an std::map and store strings as keys and pointers to functions as values, they represent what is the behaviour of every different string execution. In this way with O(1) you obtain the right pointer and then you call that function.

Ok so you just want C. You will have to implement your own hashmap (or use a preexistent one, you can find many) or binary tree structure.

Using the former approach you will effectively have O(1) (unless the hashmap is too small compared to number of strings), with the other one you will end up having a smilar approach of the automaton.

For the hashmap you just need:

• a way to calculate an hashcode of the string: you can just do int hash = string[0]^31 + string[1]^30 + ... to obtain a good unique number representing your string.
• then with a good hash function check here you can trasform the hashcode into an index of an array of pointers to functions and obtain the desired element.
• you'll need a way to handle collisions (two strings ending un on same index of the hashtable)

Of course this solution is quite over-sized for a simple task like yours, on the other hand it will be funny and it will teach you many things.. but think twice if you really need it!

Sorry if I suggested C++ but didn't consider you were asking about plain C, std::map is a component of the standard template library that is used to store pairs of values <key, value>. In your case you will have <string, funcPointer> but as suggested in comments complexity will be of O(nlogn) to search for them.

Answer 3

You could switch to using an enum and a case statement. While the function will just be replacing an if tree with a large case statement, the comparisons won't need to do string comparison each time, but instead just a numerical comparison.

typedef enum objectsetAction {
  objectset_angle = 0,
  objectset_other,
  ...
} objectsetAction;

Then define the ObjectSet function to take an objectsetAction argument instead of a string.

That way you can just write

switch(action) {
  case objectset_angle:
    //dostuff
    break;
  case objectset_other:
    //dostuff
    break;
  ...
}

Answer 4

The easy way:
A trivial replacement would be to replace your "action strings" with an enum that you define; it'll work exactly the same way, except a switch statement on an enum (essentially, an integer) is a lot quicker than doing string comparisons. A switch will also look a lot prettier (imo :)) than an if-tree like you're describing.

The powerful way:
The more concise solution would be to use function pointers - as long as all the different actions you need to perform can be contained within separate functions all having the same signature, you could simply bind the appropriate function, and have it be called automatically.

Answer 5

There is a datastructure called trie that is good for selecting on strings quickly in a memory efficient way. It would probably be the right thing to do if this was a big performance bottleneck and the fact that you pass strings something you couldn't possibly change.

However I think it's making things too complicated. If you keep some kind of enumeration in lua and C in sync and do a switch case or create a jump table for it, it will give better performance and it's easier to develop.

Answer 6

Since you specify C and not C++, sorted parallel arrays:

#define VERB_COUNT 10
void *context_data;
char *verbs[VERB_COUNT] = { "ABC", "DEF", "GHI", ... }; // sorted list
int (*actions[VERB_COUNT])(void *) = { abc_func, def_func, ghi_func, ... };
int idx, ret = -1;

int idx = bsearch(action, verbs, VERB_COUNT, sizeof char*, strcmp); // I think I got these in the right order
if (idx >= 0)
   ret = (*actions[idx])(context_data);
return ret;

Answer 7

Since you have Lua embedded and available, you can use it. A Lua table is an associative array that can be indexed by any Lua value (except nil) and store any value. Strings work well as keys, and functions as values.

You can easily turn a call like ObjectSet(id, "ANGLE", 45) into a call like actions.ANGLE(id,45).

To do this, arrange to create the actions table containing functions to implement each action. The easy way is likely to involve a block of Lua code that intializes the table, but it certainly could also be done from the C side.

actions = {
  ANGLE = function(id,theta)
              -- do something with id and theta 
          end,
  X = function (id, x)
      -- do something with id and x
      end,
}

or perhaps more clearly as

module("actions")
function ANGLE(id,theta)
  -- ...
end

function X(id,theta)
  -- ...
end

From C, you could implement ObjectSet() something like this (untested):

void ObjectSet(int id, const char *action, int arg) {
    lua_getglobal(L,"actions");
    lua_getfield(L,-1,action);
    lua_remove(L,-2);
    lua_pushinteger(L,arg);
    if (lua_pcall(L,1,0,0)) {
        fprintf(stderr, "Lua error: %s\n", lua_tostring(L,-1));
    }
    return;
}

Real error handling is left as an exercise. Note that lua_pcall() is used here so that Lua errors do not propagate out of ObjectSet(). If you are using C++, you need to be careful because Lua uses setjmp() and longjmp() for errors which generally must be translated into C++ exceptions by catching the Lua error and throwing a suitable exception.

I've also naturally left associating the object id with the actual object on the Lua side as an exercise. However, you could implement all of the functions in the actions table in C, and largely evade this issue.

Answer 8

It's hard to say exactly what might be better, since you're not very clear about what your constraints are. Other answers show what you could do if you were willing to export more symbols into Lua or delegate more work to Lua. My answer addresses a narrow question: how could you refactor your C code without changing the way you interact with Lua? I propose you make your code table-driven.

Here's a design sketch:

typedef struct action {
    const char *name;
    int (*doit)(lua_State *L, int idx);
} *Action;

static Action my_actions[] = {
  { "angle", set_angle },
  { "color", set_color },
  ...
  { NULL, NULL }
};

int i_replace_nest_of_ifs(lua_State *L) {
  const char *action = luaL_checkstring(L, 1);
  for (int i = 0; my_actions[i].name && strcmp(my_actions[i].name, action); i++)
    ;
  if (my_actions[i].name) 
    return my_actions[i].doit(L, 2);
  else
    return luaL_error("Asked for unknown action '%s'", action);
}

If the linear search through actions gets too expensive, you can sort by name when you open the library, then call bsearch.