Implementing a timed check

[axtroz]

Hello everyone!
I am writing a simple application to check some records in an interval.
Each record has its own checking interval which can be between 5 and 300 seconds.
This is the record structure:

...
typedef struct record_t {
    char name[256];
    time_t last_check;
    unsigned int interval;
    unsigned long amount;
    struct record_t *next;
} struct_t;
...

and the thread that checks records:

...
/* records is a pointer to the first record in the linked list */
while(1) {
    for (current_record = records;
         current_record != NULL;
         current_record = current_record->next)
         {
            if(current_record->last_check + current_record->interval < time(0))
                update_record(current_record);
         }
    sleep(1);
}
...

The record list's length can be very wide (e.g. from 2 to 100 000)
and this will get slower and slower with each element pushed in the list...
Is there a way to optimize it or have a trigger with each record
so instead of checking everything with a loop,
a callback is invoked when the interval passes?

I realize there's a whole bunch of wrong in this code
but I simply lack the knowledge to implement it otherwise.
I'm self-taught from websites like this one and it's like a hobby,
so please excuse my ignorance if the question is rather stupid
or the code is with extremely poor quality.
Thanks!

[kbw]

You've probably recognised you're using the wrong data structure. If you don't know about data structures (as is generally the case with CS graduates these days), it's time you learned.

Part of the problem is that your record has embeded pointer, embedding a linked list into your data. You need to move the pointer out and use a standard container. Then you can choose the container most appropriate, and the strategy to using it.

So, to begin with, your record should look like:

struct struct_t {
    char name[256];
    time_t last_check;
    unsigned int interval;
    unsigned long amount;
};

If you wanted to continue to a linke list, your code would look like:

std::list<struct_t> records;
//..
while (true) {
    for (std::list<sturct_t>::iterator p = records.begin(); p != records.end(); ++p)
        if (p->last_check + p->interval < time(0))
            unpdate_record(*p);
    sleep(1);
}

Anyway, we're not doing that anymore. We could store the record against the complete time. We could leave the records in the linked list, and just store a pointer to it in the linked list.

typedef std::map<time_t, std::list<sturct_t>::iterator> timed_structs_t;

// initialise the map from the content of the list.
timed_structs_t ts;
for (std::list<struct_t>::iterator p records.begin(); p != records.ends(); ++p) {
    ts.insert(std::pair(p->last_check + p->interval, p));
}

Then them the fire loop would look like:

while (true) {
    timed_structs_t::iterator p = ts.begin();
    while (p != ts.end())
    {
        // exit the loop when no more records have hit the time event
        if (p->first > time(0))
            break;

        update_record(*(p->second));

        // reinsert it with the new scheduled time
        ts.insert(std::pair(p->second->last_check + p->second->interval, *(p->second)));
        ts.remove(p); // remove old record

        p = ts.begin();  // start again from the first time to be processed
    }
    sleep(1);
}

... or something like that.

[axtroz]

Thanks for this! I guess I was looking at a C list rather than C++ list :)
I'll re-implement it like this, though is this not getting slower as the list grows?
And also I as concerned about the correctness of using sleep() for checking, as sleeping a whole second with a big amount of records is always more than a second. (it sleeps for a whole second and then starts processing. Until it reaches the last record within the loop it's bound to take more time).

[kbw]

I'll re-implement it like this, though is this not getting slower as the list grows?

It never traverses the whole list.

The map holds events ordered by fire time, last_check + second->interval. So once it hits a future event, it stops searching and drops into the sleep.

        // exit the loop when no more records have hit the time event
        if (p->first > time(0))
            break;

And also I as concerned about the correctness of using sleep() for checking, as sleeping a whole second with a big amount of records is always more than a second.

You could get the time at the start of the loop (see gettimeofday(), http://pubs.opengroup.org/onlinepubs/007908799/xsh/gettimeofday.html).

At the end of the loop, you check how much time it took again, then sleep for the difference with nanosleep. http://pubs.opengroup.org/onlinepubs/007908799/xsh/nanosleep.html

I've just noticed there's atleast one syntax error in the code (along with the grammar in the text). If you're stuck with that I'll put it thru a compiler and fix it, otherwise I'll just leave it.

[axtroz]

Brilliant!
Thanks a lot for the simple (as in easy to understand) explanation and the proposal of doing it the correct way!