Writing generic Search function for linked list in C?

Question

I am trying to write a generic Search function on a linked list in C. The function is as follows:

void* get_when_true(linked_list *l,
                    int (*condition)(const void*)) {
        node **walk = &l->head;
        while (*walk != NULL && !condition((*walk)->data)) {
                walk = &((*walk)->next);
        }
        return (*walk)->data;
}

Basically condition is a function pointer to a function which will be tested against each element of linked list and whenever this function returns true that particular node will be returned.

Each of the node in my linked list stores some ID. My problem is if I wan't to search for a specific ID I have to write a separate search function which can only check for that particular ID. Basically if I wan't to look for ID 10. I have to write a function

int isID_10(const void *a) {
    // cast A to appropriate poitner
    return a->ID == 10;
}

If I want to test for some other ID say 30, I will have to write a different function again..I think you got my point.

I can only think of currying to solve this problem..but unfortunately C doesn't provide currying and I can't use some compiler specific work arounds because my code should compile on all platforms.

Using global variable for the search ID is one solution but I wan't to avoid it.

How to solve this problem?

But tomorrow if I am using my linked list to store some structures, ints and chars and I want to compare all of them then the structure format will change and my get_when_true function won't remain generic any more — Nullpointer, Sep 18 '16 at 15:18

score 3 · Answer 1 · edited May 23 '17 at 10:27

You should add another parameter to get_when_true that is passed to your callback. This can be just another void * so it can point to a structure of any type.

void* get_when_true(linked_list *l, void *ctx,
                    int (*condition)(const void* data, void *ctx)) {
        node **walk = &l->head;
        while (*walk != NULL && !condition((*walk)->data, ctx)) {
                walk = &((*walk)->next);
        }
        return (*walk)->data;
}

Here's a callback:

int isID(const void *data, void *ctx) {
    int id = (int)ctx;
    const struct whatever *a = data;
    return a->ID == id;
}

Used like this:

get_when_true(list, (void*)10, isID);

Here I didn't even need a structure so I "cheat" and just cast the single integer to a void*.

Since C doesn't natively support closures, where there is data "attached" to a (callback) function pointer, any function I write that accepts a callback also takes a void* that is passed to the callback.

While C doesn't support closures, there is a GNU extension that provides nested functions which can access variables in the parent function's scope. So, using your original code (without my additional parameters):

int get_when_id(linked_list *l, int id) {
    int condition(const void *data) {
        const struct whatever *a = data;
        return a->ID == id;  // id is "closed over" from parent
    }

    return get_when_true(list, condition);
}

This requires an executable stack. If you look at the disassembly, you'll see that the function pointer actually passed to get_when_true is not the address of condition itself. Rather, the address of an executable thunk is generated on the stack is passed. This thunk passes a pointer to the closed-over variables to the actual condition function, so they're automatically made available there.

Writing generic Search function for linked list in C?

1 Answers1