/*
    SDL - Simple DirectMedia Layer
    Copyright (C) 1997-2010 Sam Lantinga

    This library is free software; you can redistribute it and/or
    modify it under the terms of the GNU Lesser General Public
    License as published by the Free Software Foundation; either
    version 2.1 of the License, or (at your option) any later version.

    This library is distributed in the hope that it will be useful,
    but WITHOUT ANY WARRANTY; without even the implied warranty of
    MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
    Lesser General Public License for more details.

    You should have received a copy of the GNU Lesser General Public
    License along with this library; if not, write to the Free Software
    Foundation, Inc., 51 Franklin St, Fifth Floor, Boston, MA  02110-1301  USA

    Sam Lantinga
    slouken@libsdl.org
*/
#include "SDL_config.h"

#include "SDL_timer.h"
#include "SDL_timer_c.h"
#include "SDL_atomic.h"
#include "SDL_thread.h"

/* #define DEBUG_TIMERS */

typedef struct _SDL_Timer
{
    int timerID;
    SDL_TimerCallback callback;
    void *param;
    Uint32 interval;
    Uint32 scheduled;
    volatile SDL_bool canceled;
    struct _SDL_Timer *next;
} SDL_Timer;

typedef struct _SDL_TimerMap
{
    int timerID;
    SDL_Timer *timer;
    struct _SDL_TimerMap *next;
} SDL_TimerMap;

/* A reasonable guess */
#define CACHELINE_SIZE  128

/* The timers are kept in a sorted list */
typedef struct {
    /* Data used by the main thread */
    SDL_Thread *thread;
    SDL_atomic_t nextID;
    SDL_TimerMap *timermap;
    SDL_mutex *timermap_lock;

    /* Padding to separate cache lines between threads */
    char pad[CACHELINE_SIZE];

    /* Data used to communicate with the timer thread */
    SDL_SpinLock lock;
    SDL_sem *sem;
    SDL_Timer * volatile pending;
    SDL_Timer * volatile freelist;
    volatile SDL_bool active;

    /* List of timers - this is only touched by the timer thread */
    SDL_Timer *timers;
} SDL_TimerData;

static SDL_TimerData SDL_timer_data;


/* The idea here is that any thread might add a timer, but a single
 * thread manages the active timer queue, sorted by scheduling time.
 *
 * Timers are removed by simply setting a canceled flag
 */

static void
SDL_AddTimerInternal(SDL_TimerData *data, SDL_Timer *timer)
{
    SDL_Timer *prev, *curr;

    prev = NULL;
    for (curr = data->timers; curr; prev = curr, curr = curr->next) {
        if ((Sint32)(timer->scheduled-curr->scheduled) < 0) {
            break;
        }
    }

    /* Insert the timer here! */
    if (prev) {
        prev->next = timer;
    } else {
        data->timers = timer;
    }
    timer->next = curr;
}

static int
SDL_TimerThread(void *_data)
{
    SDL_TimerData *data = (SDL_TimerData *)_data;
    SDL_Timer *pending;
    SDL_Timer *current;
    SDL_Timer *freelist_head = NULL;
    SDL_Timer *freelist_tail = NULL;
    Uint32 tick, now, interval, delay;

    /* Threaded timer loop:
     *  1. Queue timers added by other threads
     *  2. Handle any timers that should dispatch this cycle
     *  3. Wait until next dispatch time or new timer arrives
     */
    for ( ; ; ) {
        /* Pending and freelist maintenance */
        SDL_AtomicLock(&data->lock);
        {
            /* Get any timers ready to be queued */
            pending = data->pending;
            data->pending = NULL;

            /* Make any unused timer structures available */
            if (freelist_head) {
                freelist_tail->next = data->freelist;
                data->freelist = freelist_head;
            }
        }
        SDL_AtomicUnlock(&data->lock);

        /* Sort the pending timers into our list */
        while (pending) {
            current = pending;
            pending = pending->next;
            SDL_AddTimerInternal(data, current);
        }
        freelist_head = NULL;
        freelist_tail = NULL;

        /* Check to see if we're still running, after maintenance */
        if (!data->active) {
            break;
        }

        /* Initial delay if there are no timers */
        delay = SDL_MUTEX_MAXWAIT;

        tick = SDL_GetTicks();

        /* Process all the pending timers for this tick */
        while (data->timers) {
            current = data->timers;

            if ((Sint32)(tick-current->scheduled) < 0) {
                /* Scheduled for the future, wait a bit */
                delay = (current->scheduled - tick);
                break;
            }

            /* We're going to do something with this timer */
            data->timers = current->next;

            if (current->canceled) {
                interval = 0;
            } else {
                interval = current->callback(current->interval, current->param);
            }

            if (interval > 0) {
                /* Reschedule this timer */
                current->scheduled = tick + interval;
                SDL_AddTimerInternal(data, current);
            } else {
                if (!freelist_head) {
                    freelist_head = current;
                }
                if (freelist_tail) {
                    freelist_tail->next = current;
                }
                freelist_tail = current;

                current->canceled = SDL_TRUE;
            }
        }

        /* Adjust the delay based on processing time */
        now = SDL_GetTicks();
        interval = (now - tick);
        if (interval > delay) {
            delay = 0;
        } else {
            delay -= interval;
        }

        /* Note that each time a timer is added, this will return
           immediately, but we process the timers added all at once.
           That's okay, it just means we run through the loop a few
           extra times.
         */
        SDL_SemWaitTimeout(data->sem, delay);
    }
    return 0;
}

int
SDL_TimerInit(void)
{
    SDL_TimerData *data = &SDL_timer_data;

    if (!data->active) {
        data->timermap_lock = SDL_CreateMutex();
        if (!data->timermap_lock) {
            return -1;
        }

        data->sem = SDL_CreateSemaphore(0);
        if (!data->sem) {
            SDL_DestroyMutex(data->timermap_lock);
            return -1;
        }

        data->active = SDL_TRUE;
        data->thread = SDL_CreateThread(SDL_TimerThread, data);
        if (!data->thread) {
            SDL_TimerQuit();
            return -1;
        }

        SDL_AtomicSet(&data->nextID, 1);
    }
    return 0;
}

void
SDL_TimerQuit(void)
{
    SDL_TimerData *data = &SDL_timer_data;
    SDL_Timer *timer;
    SDL_TimerMap *entry;

    if (data->active) {
        data->active = SDL_FALSE;

        /* Shutdown the timer thread */
        if (data->thread) {
            SDL_SemPost(data->sem);
            SDL_WaitThread(data->thread, NULL);
            data->thread = NULL;
        }

        SDL_DestroySemaphore(data->sem);
        data->sem = NULL;

        /* Clean up the timer entries */
        while (data->timers) {
            timer = data->timers;
            data->timers = timer->next;
            SDL_free(timer);
        }
        while (data->freelist) {
            timer = data->freelist;
            data->freelist = timer->next;
            SDL_free(timer);
        }
        while (data->timermap) {
            entry = data->timermap;
            data->timermap = entry->next;
            SDL_free(entry);
        }

        SDL_DestroyMutex(data->timermap_lock);
        data->timermap_lock = NULL;
    }
}

SDL_TimerID
SDL_AddTimer(Uint32 interval, SDL_TimerCallback callback, void *param)
{
    SDL_TimerData *data = &SDL_timer_data;
    SDL_Timer *timer;
    SDL_TimerMap *entry;

    if (!data->active) {
        int status = 0;

        SDL_AtomicLock(&data->lock);
        if (!data->active) {
            status = SDL_TimerInit();
        }
        SDL_AtomicUnlock(&data->lock);

        if (status < 0) {
            return 0;
        }
    }

    SDL_AtomicLock(&data->lock);
    timer = data->freelist;
    if (timer) {
        data->freelist = timer->next;
    }
    SDL_AtomicUnlock(&data->lock);

    if (timer) {
        SDL_RemoveTimer(timer->timerID);
    } else {
        timer = (SDL_Timer *)SDL_malloc(sizeof(*timer));
        if (!timer) {
            SDL_OutOfMemory();
            return 0;
        }
    }
    timer->timerID = SDL_AtomicIncRef(&data->nextID);
    timer->callback = callback;
    timer->param = param;
    timer->interval = interval;
    timer->scheduled = SDL_GetTicks() + interval;
    timer->canceled = SDL_FALSE;
 
    entry = (SDL_TimerMap *)SDL_malloc(sizeof(*entry));
    if (!entry) {
        SDL_free(timer);
        SDL_OutOfMemory();
        return 0;
    }
    entry->timer = timer;
    entry->timerID = timer->timerID;

    SDL_mutexP(data->timermap_lock);
    entry->next = data->timermap;
    data->timermap = entry;
    SDL_mutexV(data->timermap_lock);

    /* Add the timer to the pending list for the timer thread */
    SDL_AtomicLock(&data->lock);
    timer->next = data->pending;
    data->pending = timer;
    SDL_AtomicUnlock(&data->lock);

    /* Wake up the timer thread if necessary */
    SDL_SemPost(data->sem);

    return entry->timerID;
}

SDL_bool
SDL_RemoveTimer(SDL_TimerID id)
{
    SDL_TimerData *data = &SDL_timer_data;
    SDL_TimerMap *prev, *entry;
    SDL_bool canceled = SDL_FALSE;

    /* Find the timer */
    SDL_mutexP(data->timermap_lock);
    prev = NULL;
    for (entry = data->timermap; entry; prev = entry, entry = entry->next) {
        if (entry->timerID == id) {
            if (prev) {
                prev->next = entry->next;
            } else {
                data->timermap = entry->next;
            }
            break;
        }
    }
    SDL_mutexV(data->timermap_lock);

    if (entry) {
        if (!entry->timer->canceled) {
            entry->timer->canceled = SDL_TRUE;
            canceled = SDL_TRUE;
        }
        SDL_free(entry);
    }
    return canceled;
}

/* vi: set ts=4 sw=4 expandtab: */