timers.c

The Kannel Open Source WAP and SMS gateway works as both an SMS gateway, for implementing keyword b

        heap_insert(timers->heap, timer);
        wakeup = timer->index == 0;  /* Do we have a new top? */
    }

    if (event != NULL) {
	wap_event_destroy(timer->event);
	timer->event = event;
    }

    unlock(timers);

    if (wakeup)
        gwthread_wakeup(timers->thread);
}

void gwtimer_stop(Timer *timer)
{
    gw_assert(initialized);
    gw_assert(timer != NULL);
    lock(timers);

    /*
     * If the timer is active, make it inactive and remove it from
     * the heap.
     */
    if (timer->elapses > 0) {
        timer->elapses = -1;
        gw_assert(timers->heap->tab[timer->index] == timer);
        heap_delete(timers->heap, timer->index);
    }

    abort_elapsed(timer);

    unlock(timers);
}

static void lock(Timerset *set)
{
    gw_assert(set != NULL);
    mutex_lock(set->mutex);
}

static void unlock(Timerset *set)
{
    gw_assert(set != NULL);
    mutex_unlock(set->mutex);
}

/*
 * Go back and remove this timer's elapse event from the output list,
 * to pretend that it didn't elapse after all.  This is necessary
 * to deal with some races between the timer thread and the caller's
 * start/stop actions.
 */
static void abort_elapsed(Timer *timer)
{
    long count;

    if (timer->elapsed_event == NULL)
        return;

    count = list_delete_equal(timer->output, timer->elapsed_event);
    if (count > 0) {
        debug("timers", 0, "Aborting %s timer.",
              wap_event_name(timer->elapsed_event->type));
        wap_event_destroy(timer->elapsed_event);
    }
    timer->elapsed_event = NULL;
}

/*
 * Create a new timer heap.
 */
static TimerHeap *heap_create(void)
{
    TimerHeap *heap;

    heap = gw_malloc(sizeof(*heap));
    heap->tab = gw_malloc(sizeof(heap->tab[0]));
    heap->size = 1;
    heap->len = 0;

    return heap;
}

static void heap_destroy(TimerHeap *heap)
{
    if (heap == NULL)
        return;

    gw_free(heap->tab);
    gw_free(heap);
}

/*
 * Remove a timer from the heap.  Do this by swapping it with the element
 * in the last position, then shortening the heap, then moving the
 * swapped element up or down to maintain the partial ordering.
 */
static void heap_delete(TimerHeap *heap, long index)
{
    long last;

    gw_assert(index >= 0);
    gw_assert(index < heap->len);
    gw_assert(heap->tab[index]->index == index);

    last = heap->len - 1;
    heap_swap(heap, index, last);
    heap->tab[last]->index = -1;
    heap->len--;
    if (index != last)
        heap_adjust(heap, index);
}

/*
 * Add a timer to the heap.  Do this by adding it at the end, then
 * moving it up or down as necessary to achieve partial ordering.
 */
static void heap_insert(TimerHeap *heap, Timer *timer)
{
    heap->len++;
    if (heap->len > heap->size) {
        heap->tab = gw_realloc(heap->tab,
                                heap->len * sizeof(heap->tab[0]));
        heap->size = heap->len;
    }
    heap->tab[heap->len - 1] = timer;
    timer->index = heap->len - 1;
    heap_adjust(heap, timer->index);
}

/*
 * Swap two elements of the heap, and update their index fields.
 * This is the basic heap operation.
 */
static void heap_swap(TimerHeap *heap, long index1, long index2)
{
    Timer *t;

    gw_assert(index1 >= 0);
    gw_assert(index1 < heap->len);
    gw_assert(index2 >= 0);
    gw_assert(index2 < heap->len);

    if (index1 == index2)
        return;

    t = heap->tab[index1];
    heap->tab[index1] = heap->tab[index2];
    heap->tab[index2] = t;
    heap->tab[index1]->index = index1;
    heap->tab[index2]->index = index2;
}

/*
 * The current element has broken the partial ordering of the
 * heap (see explanation in the definition of Timerset), and
 * it has to be moved up or down until the ordering is restored.
 * Return 1 if the timer at the heap's top is now earlier than
 * before this operation, otherwise 0.
 */
static int heap_adjust(TimerHeap *heap, long index)
{
    Timer *t;
    Timer *parent;
    long child_index;

    /*
     * We can assume that the heap was fine before this element's
     * elapse time was changed.  There are three cases to deal
     * with:
     *  - Element's new elapse time is too small; it should be
     *    moved toward the top.
     *  - Element's new elapse time is too large; it should be
     *    moved toward the bottom.
     *  - Element's new elapse time still fits here, we don't
     *    have to do anything.
     */

    gw_assert(index >= 0);
    gw_assert(index < heap->len);

    /* Move to top? */
    t = heap->tab[index];
    parent = heap->tab[index / 2];
    if (t->elapses < parent->elapses) {
        /* This will automatically terminate when it reaches
         * the top, because in that t == parent. */
        do {
            heap_swap(heap, index, index / 2);
            index = index / 2;
            parent = heap->tab[index / 2];
        } while (t->elapses < parent->elapses);
        /* We're done.  Return 1 if we changed the top. */
        return index == 0;
    }

    /* Move to bottom? */
    for (; ; ) {
        child_index = index * 2;
        if (child_index >= heap->len)
            return 0;   /* Already at bottom */
        if (child_index == heap->len - 1) {
            /* Only one child */
            if (heap->tab[child_index]->elapses < t->elapses)
                heap_swap(heap, index, child_index);
            break;
        }

        /* Find out which child elapses first */
        if (heap->tab[child_index + 1]->elapses <
            heap->tab[child_index]->elapses) {
            child_index++;
        }

        if (heap->tab[child_index]->elapses < t->elapses) {
            heap_swap(heap, index, child_index);
            index = child_index;
        } else {
            break;
        }
    }

    return 0;
}

/*
 * This timer has elapsed.  Do the housekeeping.  We have its set locked.
 */
static void elapse_timer(Timer *timer)
{
    gw_assert(timer != NULL);
    gw_assert(timers != NULL);
    /* This must be true because abort_elapsed is always called
     * before a timer is activated. */
    gw_assert(timer->elapsed_event == NULL);

    debug("timers", 0, "%s elapsed.", wap_event_name(timer->event->type));

    timer->elapsed_event = wap_event_duplicate(timer->event);
    list_produce(timer->output, timer->elapsed_event);
    timer->elapses = -1;
}

/*
 * Main function for timer thread.
 */
static void watch_timers(void *arg)
{
    Timerset *set;
    long top_time;
    long now;

    set = arg;

    while (!set->stopping) {
        lock(set);

	now = time(NULL);

	while (set->heap->len > 0 && set->heap->tab[0]->elapses <= now) {
	    elapse_timer(set->heap->tab[0]);
	    heap_delete(set->heap, 0);
	}

	/*
	 * Now sleep until the next timer elapses.  If there isn't one,
	 * then just sleep very long.  We will get woken up if the
	 * top of the heap changes before we wake.
	 */

        if (set->heap->len == 0) {
            unlock(set);
            gwthread_sleep(1000000.0);
        } else {
	    top_time = set->heap->tab[0]->elapses;
	    unlock(set);
	    gwthread_sleep(top_time - now);
	}
    }
}