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