Dogcows Code - chaz/tint2/blob - src/util/timer.c

   1 /**************************************************************************
   2 *
   3 * Copyright (C) 2009 Andreas.Fink (Andreas.Fink85@gmail.com)
   4 *
   5 * This program is free software; you can redistribute it and/or
   6 * modify it under the terms of the GNU General Public License version 2
   7 * as published by the Free Software Foundation.
   8 *
   9 * This program is distributed in the hope that it will be useful,
  10 * but WITHOUT ANY WARRANTY; without even the implied warranty of
  11 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  12 * GNU General Public License for more details.
  13 * You should have received a copy of the GNU General Public License
  14 * along with this program; if not, write to the Free Software
  15 * Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA  02110-1301, USA.
  16 **************************************************************************/
  17
  18 #include <time.h>
  19 #include <sys/time.h>
  20 #include <stdlib.h>
  21 #include <stdio.h>
  22
  23 #include "timer.h"
  24
  25 GSList* timeout_list = 0;
  26 struct timeval next_timeout;
  27
  28
  29 // functions and structs for multi timeouts
  30 typedef struct {
  31         int current_count;
  32         int count_to_expiration;
  33 } multi_timeout;
  34
  35 typedef struct {
  36         GSList* timeout_list;
  37         timeout* parent_timeout;
  38 } multi_timeout_handler;
  39
  40 struct _timeout {
  41         int interval_msec;
  42         struct timespec timeout_expires;
  43         void (*_callback)(void*);
  44         void* arg;
  45         multi_timeout* multi_timeout;
  46 };
  47
  48 void add_timeout_intern(int value_msec, int interval_msec, void(*_callback)(void*), void* arg, timeout* t);
  49 gint compare_timeouts(gconstpointer t1, gconstpointer t2);
  50 gint compare_timespecs(const struct timespec* t1, const struct timespec* t2);
  51 int timespec_subtract(struct timespec* result, struct timespec* x, struct timespec* y);
  52 struct timespec add_msec_to_timespec(struct timespec ts, int msec);
  53
  54
  55 int align_with_existing_timeouts(timeout* t);
  56 void create_multi_timeout(timeout* t1, timeout* t2);
  57 void append_multi_timeout(timeout* t1, timeout* t2);
  58 int calc_multi_timeout_interval(multi_timeout_handler* mth);
  59 void update_multi_timeout_values(multi_timeout_handler* mth);
  60 void callback_multi_timeout(void* mth);
  61 void remove_from_multi_timeout(timeout* t);
  62 void stop_multi_timeout(timeout* t);
  63
  64 GHashTable* multi_timeouts = 0;
  65
  66 /** Implementation notes for timeouts: The timeouts are kept in a GSList sorted by their
  67         * expiration time.
  68         * That means that update_next_timeout() only have to consider the first timeout in the list,
  69         * and callback_timeout_expired() only have to consider the timeouts as long as the expiration time
  70         * is in the past to the current time.
  71         * As time measurement we use clock_gettime(CLOCK_MONOTONIC) because this refers to a timer, which
  72         * reference point lies somewhere in the past and cannot be changed, but just queried.
  73         * If a single shot timer is installed it will be automatically deleted. I.e. the returned value
  74         * of add_timeout will not be valid anymore. You do not need to call stop_timeout for these timeouts,
  75         * however it's save to call it.
  76 **/
  77
  78 timeout* add_timeout(int value_msec, int interval_msec, void (*_callback)(void*), void* arg)
  79 {
  80         timeout* t = malloc(sizeof(timeout));
  81         t->multi_timeout = 0;
  82         add_timeout_intern(value_msec, interval_msec, _callback, arg, t);
  83         return t;
  84 }
  85
  86
  87 void change_timeout(timeout *t, int value_msec, int interval_msec, void(*_callback)(), void* arg)
  88 {
  89         if ( g_slist_find(timeout_list, t) == 0 && g_hash_table_lookup(multi_timeouts, t) == 0)
  90                 printf("programming error: timeout already deleted...");
  91         else {
  92                 if (t->multi_timeout)
  93                         remove_from_multi_timeout((timeout*)t);
  94                 else
  95                         timeout_list = g_slist_remove(timeout_list, t);
  96                 add_timeout_intern(value_msec, interval_msec, _callback, arg, (timeout*)t);
  97         }
  98 }
  99
 100
 101 void update_next_timeout()
 102 {
 103         if (timeout_list) {
 104                 timeout* t = timeout_list->data;
 105                 struct timespec cur_time;
 106                 struct timespec next_timeout2 = { .tv_sec=next_timeout.tv_sec, .tv_nsec=next_timeout.tv_usec*1000 };
 107                 clock_gettime(CLOCK_MONOTONIC, &cur_time);
 108                 if (timespec_subtract(&next_timeout2, &t->timeout_expires, &cur_time)) {
 109                         next_timeout.tv_sec = 0;
 110                         next_timeout.tv_usec = 0;
 111                 }
 112                 else {
 113                         next_timeout.tv_sec = next_timeout2.tv_sec;
 114                         next_timeout.tv_usec = next_timeout2.tv_nsec/1000;
 115                 }
 116         }
 117         else
 118                 next_timeout.tv_sec = -1;
 119 }
 120
 121
 122 void callback_timeout_expired()
 123 {
 124         struct timespec cur_time;
 125         timeout* t;
 126         while (timeout_list) {
 127                 clock_gettime(CLOCK_MONOTONIC, &cur_time);
 128                 t = timeout_list->data;
 129                 if (compare_timespecs(&t->timeout_expires, &cur_time) <= 0) {
 130                         // it's time for the callback function
 131                         t->_callback(t->arg);
 132                         if (g_slist_find(timeout_list, t)) {
 133                                 // if _callback() calls stop_timeout(t) the timeout 't' was freed and is not in the timeout_list
 134                                 timeout_list = g_slist_remove(timeout_list, t);
 135                                 if (t->interval_msec > 0)
 136                                         add_timeout_intern(t->interval_msec, t->interval_msec, t->_callback, t->arg, t);
 137                                 else
 138                                         free(t);
 139                         }
 140                 }
 141                 else
 142                         return;
 143         }
 144 }
 145
 146
 147 void stop_timeout(timeout* t)
 148 {
 149         // if not in the list, it was deleted in callback_timeout_expired
 150         if (g_slist_find(timeout_list, t) || g_hash_table_lookup(multi_timeouts, t)) {
 151                 if (t->multi_timeout)
 152                         remove_from_multi_timeout((timeout*)t);
 153                 timeout_list = g_slist_remove(timeout_list, t);
 154                 free((void*)t);
 155         }
 156 }
 157
 158
 159 void stop_all_timeouts()
 160 {
 161         while (timeout_list) {
 162                 timeout* t = timeout_list->data;
 163                 if (t->multi_timeout)
 164                         stop_multi_timeout(t);
 165                 free(t);
 166                 timeout_list = g_slist_remove(timeout_list, t);
 167         }
 168 }
 169
 170
 171 void add_timeout_intern(int value_msec, int interval_msec, void(*_callback)(), void* arg, timeout *t)
 172 {
 173         t->interval_msec = interval_msec;
 174         t->_callback = _callback;
 175         t->arg = arg;
 176         struct timespec cur_time;
 177         clock_gettime(CLOCK_MONOTONIC, &cur_time);
 178         t->timeout_expires = add_msec_to_timespec(cur_time, value_msec);
 179
 180         int can_align = 0;
 181         if (interval_msec > 0 && !t->multi_timeout)
 182                 can_align = align_with_existing_timeouts(t);
 183         if (!can_align)
 184                 timeout_list = g_slist_insert_sorted(timeout_list, t, compare_timeouts);
 185 }
 186
 187
 188 gint compare_timeouts(gconstpointer t1, gconstpointer t2)
 189 {
 190         return compare_timespecs(&((timeout*)t1)->timeout_expires,
 191                                                                                                          &((timeout*)t2)->timeout_expires);
 192 }
 193
 194
 195 gint compare_timespecs(const struct timespec* t1, const struct timespec* t2)
 196 {
 197         if (t1->tv_sec < t2->tv_sec)
 198                 return -1;
 199         else if (t1->tv_sec == t2->tv_sec) {
 200                 if (t1->tv_nsec < t2->tv_nsec)
 201                         return -1;
 202                 else if (t1->tv_nsec == t2->tv_nsec)
 203                         return 0;
 204                 else
 205                         return 1;
 206         }
 207         else
 208                 return 1;
 209 }
 210
 211 int timespec_subtract(struct timespec* result, struct timespec* x, struct timespec* y)
 212 {
 213         /* Perform the carry for the later subtraction by updating y. */
 214         if (x->tv_nsec < y->tv_nsec) {
 215                 int nsec = (y->tv_nsec - x->tv_nsec) / 1000000000 + 1;
 216                 y->tv_nsec -= 1000000000 * nsec;
 217                 y->tv_sec += nsec;
 218         }
 219         if (x->tv_nsec - y->tv_nsec > 1000000000) {
 220                 int nsec = (x->tv_nsec - y->tv_nsec) / 1000000000;
 221                 y->tv_nsec += 1000000000 * nsec;
 222                 y->tv_sec -= nsec;
 223         }
 224
 225         /* Compute the time remaining to wait. tv_nsec is certainly positive. */
 226         result->tv_sec = x->tv_sec - y->tv_sec;
 227         result->tv_nsec = x->tv_nsec - y->tv_nsec;
 228
 229         /* Return 1 if result is negative. */
 230         return x->tv_sec < y->tv_sec;
 231 }
 232
 233
 234 struct timespec add_msec_to_timespec(struct timespec ts, int msec)
 235 {
 236         ts.tv_sec += msec / 1000;
 237         ts.tv_nsec += (msec % 1000)*1000000;
 238         if (ts.tv_nsec >= 1000000000) {  // 10^9
 239                 ts.tv_sec++;
 240                 ts.tv_nsec -= 1000000000;
 241         }
 242         return ts;
 243 }
 244
 245
 246 int align_with_existing_timeouts(timeout *t)
 247 {
 248         GSList* it = timeout_list;
 249         while (it) {
 250                 timeout* t2 = it->data;
 251                 if (t2->interval_msec > 0) {
 252                         if (t->interval_msec % t2->interval_msec == 0 || t2->interval_msec % t->interval_msec == 0) {
 253                                 if (multi_timeouts == 0)
 254                                         multi_timeouts = g_hash_table_new(0, 0);
 255                                 if (!t->multi_timeout && !t2->multi_timeout)
 256                                         // both timeouts can be aligned, but there is no multi timeout for them
 257                                         create_multi_timeout(t, t2);
 258                                 else
 259                                         // there is already a multi timeout, so we append the new timeout to the multi timeout
 260                                         append_multi_timeout(t, t2);
 261                                 return 1;
 262                         }
 263                 }
 264                 it = it->next;
 265         }
 266         return 0;
 267 }
 268
 269
 270 int calc_multi_timeout_interval(multi_timeout_handler* mth)
 271 {
 272         GSList* it = mth->timeout_list;
 273         timeout* t = it->data;
 274         int min_interval = t->interval_msec;
 275         it = it->next;
 276         while (it) {
 277                 t = it->data;
 278                 if (t->interval_msec < min_interval)
 279                         min_interval = t->interval_msec;
 280                 it = it->next;
 281         }
 282         return min_interval;
 283 }
 284
 285
 286 void create_multi_timeout(timeout* t1, timeout* t2)
 287 {
 288         multi_timeout* mt1 = malloc(sizeof(multi_timeout));
 289         multi_timeout* mt2 = malloc(sizeof(multi_timeout));
 290         multi_timeout_handler* mth = malloc(sizeof(multi_timeout_handler));
 291         timeout* real_timeout = malloc(sizeof(timeout));
 292
 293         mth->timeout_list = 0;
 294         mth->timeout_list = g_slist_prepend(mth->timeout_list, t1);
 295         mth->timeout_list = g_slist_prepend(mth->timeout_list, t2);
 296         mth->parent_timeout = real_timeout;
 297
 298         g_hash_table_insert(multi_timeouts, t1, mth);
 299         g_hash_table_insert(multi_timeouts, t2, mth);
 300         g_hash_table_insert(multi_timeouts, real_timeout, mth);
 301
 302         t1->multi_timeout = mt1;
 303         t2->multi_timeout = mt2;
 304         // set real_timeout->multi_timeout to something, such that we see in add_timeout_intern that
 305         // it is already a multi_timeout (we never use it, except of checking for 0 ptr)
 306         real_timeout->multi_timeout = (void*)real_timeout;
 307
 308         timeout_list = g_slist_remove(timeout_list, t1);
 309         timeout_list = g_slist_remove(timeout_list, t2);
 310
 311         update_multi_timeout_values(mth);
 312 }
 313
 314
 315 void append_multi_timeout(timeout* t1, timeout* t2)
 316 {
 317         if (t2->multi_timeout) {
 318                 // swap t1 and t2 such that t1 is the multi timeout
 319                 timeout* tmp = t2;
 320                 t2 = t1;
 321                 t1 = tmp;
 322         }
 323
 324         multi_timeout* mt = malloc(sizeof(multi_timeout));
 325         multi_timeout_handler* mth = g_hash_table_lookup(multi_timeouts, t1);
 326
 327         mth->timeout_list = g_slist_prepend(mth->timeout_list, t2);
 328         g_hash_table_insert(multi_timeouts, t2, mth);
 329
 330         t2->multi_timeout = mt;
 331
 332         update_multi_timeout_values(mth);
 333 }
 334
 335
 336 void update_multi_timeout_values(multi_timeout_handler* mth)
 337 {
 338         int interval = calc_multi_timeout_interval(mth);
 339         int next_timeout_msec = interval;
 340
 341         struct timespec cur_time;
 342         clock_gettime(CLOCK_MONOTONIC, &cur_time);
 343
 344         GSList* it = mth->timeout_list;
 345         struct timespec diff_time;
 346         while (it) {
 347                 timeout* t = it->data;
 348                 t->multi_timeout->count_to_expiration = t->interval_msec / interval;
 349                 timespec_subtract(&diff_time, &t->timeout_expires, &cur_time);
 350                 int msec_to_expiration = diff_time.tv_sec*1000 + diff_time.tv_nsec/1000000;
 351                 int count_left = msec_to_expiration / interval + (msec_to_expiration%interval != 0);
 352                 t->multi_timeout->current_count = t->multi_timeout->count_to_expiration - count_left;
 353                 if (msec_to_expiration < next_timeout_msec)
 354                         next_timeout_msec = msec_to_expiration;
 355                 it = it->next;
 356         }
 357
 358         mth->parent_timeout->interval_msec = interval;
 359         timeout_list = g_slist_remove(timeout_list, mth->parent_timeout);
 360         add_timeout_intern(next_timeout_msec, interval, callback_multi_timeout, mth, mth->parent_timeout);
 361 }
 362
 363
 364 void callback_multi_timeout(void* arg)
 365 {
 366         multi_timeout_handler* mth = arg;
 367         struct timespec cur_time;
 368         clock_gettime(CLOCK_MONOTONIC, &cur_time);
 369         GSList* it = mth->timeout_list;
 370         while (it) {
 371                 timeout* t = it->data;
 372                 if (++t->multi_timeout->current_count >= t->multi_timeout->count_to_expiration) {
 373                         t->_callback(t->arg);
 374                         t->multi_timeout->current_count = 0;
 375                         t->timeout_expires = add_msec_to_timespec(cur_time, t->interval_msec);
 376                 }
 377                 it = it->next;
 378         }
 379 }
 380
 381
 382 void remove_from_multi_timeout(timeout* t)
 383 {
 384         multi_timeout_handler* mth = g_hash_table_lookup(multi_timeouts, t);
 385         g_hash_table_remove(multi_timeouts, t);
 386
 387         mth->timeout_list = g_slist_remove(mth->timeout_list, t);
 388         free(t->multi_timeout);
 389         t->multi_timeout = 0;
 390
 391         if (g_slist_length(mth->timeout_list) == 1) {
 392                 timeout* last_timeout = mth->timeout_list->data;
 393                 free(last_timeout->multi_timeout);
 394                 last_timeout->multi_timeout = 0;
 395                 g_hash_table_remove(multi_timeouts, last_timeout);
 396                 g_hash_table_remove(multi_timeouts, mth->parent_timeout);
 397                 mth->parent_timeout->multi_timeout = 0;
 398                 stop_timeout(mth->parent_timeout);
 399                 free(mth);
 400
 401                 struct timespec cur_time, diff_time;
 402                 clock_gettime(CLOCK_MONOTONIC, &cur_time);
 403                 timespec_subtract(&diff_time, &t->timeout_expires, &cur_time);
 404                 int msec_to_expiration = diff_time.tv_sec*1000 + diff_time.tv_nsec/1000000;
 405                 add_timeout_intern(msec_to_expiration, last_timeout->interval_msec, last_timeout->_callback, last_timeout->arg, last_timeout);
 406         }
 407         else
 408                 update_multi_timeout_values(mth);
 409 }
 410
 411
 412 void stop_multi_timeout(timeout* t)
 413 {
 414         multi_timeout_handler* mth = g_hash_table_lookup(multi_timeouts, t);
 415         g_hash_table_remove(multi_timeouts, mth->parent_timeout);
 416         while (mth->timeout_list) {
 417                 timeout* t1 = mth->timeout_list->data;
 418                 mth->timeout_list = g_slist_remove(mth->timeout_list, t1);
 419                 g_hash_table_remove(multi_timeouts, t1);
 420                 free(t1->multi_timeout);
 421                 free(t1);
 422         }
 423         free(mth);
 424 }