CODEWITHSUNDEEP
arraysdata-structures
Josh Brittain
Josh Brittain

Reputation: 2212

What is the fastest way to find an integer in an array?

Problem: Given a userID (integer) quickly find which group the user belongs to. Groups will contain no more than 15 users. Additionally, I am using libev which gives me no control over the parameters passed into the read I/O event, so the userID (file descriptor/integer) is really the only thing I can use.

My solution: hash once on the userID into a hash table containing groupID and userID pairs. Hash a second time on the groupID to a hash table containing groupID and array of 15 userID pairs.

The solution works, but this is server code that will be executed an ungodly amount of times. I wonder if the double hashing will be inefficient and if there may be a better solution.

Upvotes: 0

Views: 276

Answers (1)

icktoofay
icktoofay

Reputation: 129079

You say that libev only gives you a limited amount of data—the ev_io handle itself—and conclude that all there is useful in there is the file descriptor. Well, normally, you're probably right, but there's a neat trick you can do.

Since with libev, you allocate the structures yourself and then have libev initialize them, there's nothing stopping you from allocating too much space. Since libev won't be touching that extra space, you can put your own stuff in there. Success!

So how does this work in practice? You create a new structure containing an ev_io as the first member, and then put all the rest of your data after it, say like this:

struct my_mutant_io {
    ev_io handle;
    int group_id;
};

Now, wherever you allocate a uv_io, allocate a my_mutant_io instead. Put your data in there however you'd like and once you need to pass it to a libuv function, just take the address of handle instead:

struct my_mutant_io *mutant = malloc(sizeof(struct my_mutant_io));
if(!mutant) {
    abort();
}
mutant->group_id = /* ... */;
ev_io_init(&mutant, some_callback, fd, EV_READ);

You've given libev a ev_io, and it's none-the-wiser that it's actually just a part of a larger struct. Now let's move on to the callback. You'll get your ev_io back, but wait! Since the ev_io is the first member of the struct, its address is the same as the address of our mutant. We can cast the ev_io * right back to a struct my_mutant_io * and use it. (Just don't tell the strict-aliasing gods.)

A struct like this is most commonly called a baton.

Upvotes: 2

Related Questions