/* 
 * Copyright (C) 2000-2001 Computer & Communications Research Laboratories,
 *			   Industrial Technology Research Institute
 */
/* Copyright Telcordia Technologies 1999 */
/* 
 * msgAlarm.c
 *
 * $Id: msgAlarm.c,v 1.28 2001/06/15 09:10:21 hcc Exp $
 */

#define _POSIX_SOURCE 1 /* POSIX signals */
#define __EXTENSIONS__ /* Solaris struct timeval*/

#include <stdlib.h>
#if defined(UNIX)
#include <signal.h>
#include <sys/time.h>
#elif defined(WIN32)
#include <winsock.h> /* struct timeval */
#include <sys\timeb.h> /*time_t */
#include <mmsystem.h>
#pragma comment(lib, "winmm.lib ") /* timeSetEvent() */ 
#endif

#include "msgAlarm.h"
#include "common.h"

/* TO BE DONE

 * DONE
 * when searching for events due to execute, only have to search until
 * you get a positive value, because of heap structure.  Need to be
 * careful, because, for instance, 1, 3, 6 might be zero, with 2, 4,
 * 5, 7 positive.  Might want to use heap up to move things one at a
 * time.

 * DONE
 * no longer need the "due" field, nor the check for CB!=NULL, because
 * the index in heap determines which are active events

 * DONE
 * quantize the delays relative to the length of a tick.  initially
 * set a short time and fetch back the result.  this is the smallest
 * available time unit.  scale all delays to that value (round or
 * ceil?)  -- delay/TICK*TICK.  This will cause events that are close
 * to occur in the same alarm event.
 */

#ifdef WIN32
#define TIME_RESOLUTION_MINISEC		10
CRITICAL_SECTION	CSHold;
UINT			nTimeID;
DWORD			start_t, end_t;
long			time_delay;
#endif

TCR	alrm_tracer = 0;

#define MILLION 1000000
int tickSize;

typedef struct event 
{
	msgAlarmCB	cb;
	void*		data;
	struct timeval	delay;
	int		heapIdx;
} Event;

static Event		*events;
static int		*heap;
int			eventCount, toDo, MAXEVENTS;

/* events[1..MAXEVENTS-1] are event structures that can represent
 * events in the queue.
 *
 * heap[1..eventCount] represent a heap, ordered by events[heap[i]].delay.
 *     CB!=NULL
 * heap[eventCount+1..toDo-1] represent free events.
 *     CB==NULL
 * heap[toDo..MAXEVENTS-1] are events that need to occur in this time 
 *     CB!=NULL
 * interval (only used in doCB)
 * heap[1..MAXEVENTS-1] are a permutation of 1..MAXEVENTS-1, so all 
 * events are known.
 *
 * events[heap[i]].heapIdx == i
 * This lets us go from an index in events (used as the event id) to the
 * heap.
 *
 * N.B. The 0th element of each array is not used because the heap algorithm
 * assumes the root of the heap is element 1.
 */

/* indices are all into heap */
static void heapSwap(int a, int b);
static void heapUp(int i);
static void heapDown(int i);
#ifdef DEBUG
static void heapCheck(char*msg);
#else
#define heapCheck(x)
#endif

/* Delay/timer invariant
 * Active events have cb!=NULL
 * delay is the time *after* the timer expires when the event 
 * should occur.
 * Outside of the scheduling functions (msgAlarmSet and msgAlarmDel)
 * the timer must be set if there are any active events.
 * Complexity of the code is due to the possibility of callbacks 
 * invoking scheduling functions.
 *
 * PROBLEM: RESOLVED use "timerSet" to know whether the timer is set.
 * What if the clock goes from non-zero to zero while processing a 
 * request?  We can suppress the signal, but the zero timer will make it 
 * look like there is no pending event and we will decrement all the clocks.
 * SOLUTION: 
 *  (1) freeze the clock, resetting it appropriately
 *  (2) use a more sensitive means of determining if there is a 
 *      scheduled event.
 *
 * PROBLEM RESOLVED -- use inDoCB to protect inner call
 * nested external functions (doCB calling msgAlarm{Set,Del}) will 
 * unmask the SIGALRM on the inner call
 * SECOND RESOLUTION -- use msgAlarmHold/Release to handle nested 
 * alarm holding.  This allows external blocking as well.
 *
 */

#ifdef DEBUG
#define TRACE(msg,i,tv)	fprintf(stderr,"%s:%d: %d.%06d\n", msg,i,(tv).tv_sec,(tv).tv_usec)
#define CHECKITIMER(x)	if( (x)!=0 ) { \
			fprintf(stderr,"(%d) ", __LINE__); \
			perror("assert failed"); \
			fprintf(stderr, "nextTime=%d.%06d\n", nextTime.it_value.tv_sec, nextTime.it_value.tv_usec); \
			}
#define printDelay(msg, i,delay)	fprintf(stderr, "%s: (%d) = %d.%06d\n", msg, i, delay.tv_sec, delay.tv_usec)
#else
#define TRACE(msg,i,tv)
#define CHECKITIMER(x)   x
#define printDelay(msg, i,delay) 
#endif

static int timerSet;
static struct timeval	TV_ZERO={0,0};

static void decrTimer(struct timeval *delta, struct timeval *nextTime);
static int resetAlarm(struct timeval delay, struct timeval *deltaP); 
static void scheduleAlarm(int e, struct timeval delay);
static void findNextEvent(void);
static TIMECALLBACK doCB;
void msgAlarmHold(void);
void msgAlarmRelease(void);

#define TV_CMP(a,b)	(a.tv_sec==b.tv_sec ? a.tv_usec-b.tv_usec :  \
			a.tv_sec-b.tv_sec)

static int		alarmHolds = 0;

void msgAlarmInit(int maxEvents) 
{
	int i;

#if defined(UNIX)
	struct itimerval minTime;
	struct sigaction act, oact;    

	act.sa_handler = SIG_IGN;
	sigemptyset(&act.sa_mask);
	act.sa_flags = 0;
	sigaction(SIGALRM, &act, &oact);
	
	minTime.it_value.tv_sec = 0;
	minTime.it_value.tv_usec = 1;
	minTime.it_interval = TV_ZERO;

	/* get minimum setable interval */
	setitimer(ITIMER_REAL, &minTime, NULL);
	getitimer(ITIMER_REAL, &minTime);

	/* this rounds tickSize to a factor of MILLION */
	tickSize = MILLION/(MILLION/minTime.it_value.tv_usec);
    
	minTime.it_value = TV_ZERO;
	setitimer(ITIMER_REAL, &minTime, NULL);

	act.sa_handler = doCB;
	sigemptyset(&act.sa_mask);
	act.sa_flags = 0;
	sigaction(SIGALRM, &act, &oact);

#elif defined(WIN32)
	InitializeCriticalSection(&CSHold);
	nTimeID	= 0;
#endif

	MAXEVENTS=maxEvents+1;
	timerSet = 0;
	eventCount = 0;
	toDo = MAXEVENTS;

	events = (Event*)calloc(MAXEVENTS, sizeof(Event));
	heap   = (int*)calloc(MAXEVENTS, sizeof(*heap));

	for( i=1; i<MAXEVENTS; i++ ) {
		events[i].cb=NULL;
		events[i].heapIdx = i;
		heap[i] = i;
	}
}

void msgAlarmClean(void)
{
	free(events);
	free(heap);
#ifdef WIN32
	DeleteCriticalSection(&CSHold);
#endif
}

int msgAlarmSet(struct timeval delay, msgAlarmCB cb, void* data)
{
	int e;

	msgAlarmHold();

	heapCheck("enter Set"); 

	/* find empty event */
	eventCount++;
	if( eventCount>=toDo ) {
		/* ErrorCheck */
		msgAlarmRelease();
		return -1;
	}

	e = heap[eventCount];
	events[e].cb = cb;
	events[e].data = data;

	scheduleAlarm(e,delay);
	heapUp(eventCount);

	heapCheck("exit Set"); 

	msgAlarmRelease();

	return e;
}

void *msgAlarmDel(int e)
{
	int oldHeapPlace;

	msgAlarmHold();

	heapCheck("enter Del"); 

	events[e].cb = NULL;
	/* setting cb==NULL removes the event from the queue 
	 * if this event was scheduled for the next alarm, 
	 * find the new next event.
	 * otherwise everything is already set-up and may be left alone 
	 */
	oldHeapPlace = events[e].heapIdx;
	heapSwap(eventCount, oldHeapPlace);
	eventCount--;

	/* the new value is not necessarily a decendant of the
	 * original value, so oldHeapPlace may be too big or too small
	 * need to protect against the case where it was already eventCount
	 */
	if( oldHeapPlace <= eventCount ) {
		heapDown(oldHeapPlace);
		heapUp(oldHeapPlace);
	}

	if( events[e].delay.tv_sec==0 && events[e].delay.tv_usec==0 ) {
		/* this was scheduled for next alarm */
		findNextEvent();
	}

	heapCheck("exit Del"); 

	msgAlarmRelease();

	return events[e].data;
}

void msgAlarmHold(void) {
#if defined(UNIX)
	sigset_t set, oset;

	if( alarmHolds == 0 ) {
		/* delay any incoming alarms */
		sigemptyset(&set);
		sigaddset(&set, SIGALRM);
		sigprocmask(SIG_BLOCK, &set, &oset);
	}
	alarmHolds++;

#elif defined(WIN32)
	EnterCriticalSection(&CSHold);
#endif
}

void msgAlarmRelease(void) {
#if defined(UNIX)
	sigset_t set, oset;

	alarmHolds--;    
	if( alarmHolds==0 ) {
		sigemptyset(&set);
		sigaddset(&set, SIGALRM);
		sigprocmask(SIG_UNBLOCK, &set, &oset);		
	}
#elif defined(WIN32)
	LeaveCriticalSection(&CSHold);
#endif
}

/* subtract nextTime from delta. make 0<=usec<MILLION */
static void decrTimer(struct timeval *delta, struct timeval *nextTime)
{
	delta->tv_sec  -= nextTime->tv_sec;
	delta->tv_usec -= nextTime->tv_usec;
	while( delta->tv_usec < 0 ) {
		delta->tv_usec += MILLION;
		delta->tv_sec--;
	} 
	while( delta->tv_usec >= MILLION ) {
		delta->tv_usec -= MILLION;
		delta->tv_sec++;
	}
}

static void tickRound(time_t * t) 
{
	*t = ((*t+tickSize-1)/tickSize)*tickSize;
	if( *t==MILLION ) *t -= 1;	/* avoid rounding up to MILLION */
}

/* set the alarm for delay
 * if alarm already set for longer period, reset for delay
 * return *delta == delay-alarm  
 * return value: 1 if timer was reset, 0 otherwise
 *
 * Problem: RESOLVED by returning value to indicate timer change
 * when alarm == 0, but there are events  already scheduled
 * because we had used delta==delay to indicate this is the next event.
 */
static int resetAlarm(struct timeval delay, struct timeval *deltaP) 
{
#if defined(UNIX)
	struct itimerval nextTime;
#elif defined(WIN32)
	struct timeval nextTime;
#endif
    
	if( TV_CMP(delay, TV_ZERO) == 0 ){	/* Turn-off alarm */
#if defined(UNIX)
		nextTime.it_interval = TV_ZERO;
		nextTime.it_value = TV_ZERO;
		CHECKITIMER(setitimer(ITIMER_REAL, &nextTime, NULL));
#elif defined(WIN32)
		if (nTimeID) {
			timeKillEvent(nTimeID);
			nTimeID = 0;
		}
#endif
		timerSet = 0;
		*deltaP = TV_ZERO;
		return 0;
	}

	*deltaP = delay;
#if defined(UNIX)
	CHECKITIMER(getitimer(ITIMER_REAL, &nextTime));
	/* round nextTime and delay to nearest tickSize */
	tickRound(&nextTime.it_value.tv_usec);
	tickRound(&delay.tv_usec);
	decrTimer(deltaP, &nextTime.it_value);
#elif defined(WIN32)
	end_t = GetTickCount();
	nextTime.tv_sec = 0;
	nextTime.tv_usec = (time_delay - (end_t - start_t)) * 1000;
	decrTimer(deltaP, &nextTime);
#endif

	if( deltaP->tv_sec < 0	/* this is sooner than next event */
		|| !timerSet) {	/* timer not set, adjust time */	
		/* re-set timer, this is next */
#if defined(UNIX)
		printDelay("next was", 0, nextTime.it_value);
		nextTime.it_interval = TV_ZERO;
		nextTime.it_value = delay;
		CHECKITIMER(setitimer(ITIMER_REAL, &nextTime, NULL));
#elif defined(WIN32)
		if (nTimeID) {
			timeKillEvent(nTimeID);
			nTimeID = 0;
		}
		time_delay = delay.tv_sec * 1000 + delay.tv_usec / 1000;
		nTimeID = timeSetEvent(time_delay, TIME_RESOLUTION_MINISEC, doCB, 0, TIME_ONESHOT | TIME_CALLBACK_FUNCTION);
		start_t = GetTickCount();
#endif
		timerSet = 1;
		return 1;
	}
	return 0;
}

/* If delay is zero, alarm is already set, leave alone 
 * Determine delta for event, relative to current alarm 
 * If delta is positive, set events[e].delay = delta 
 * If delta is negative (sooner than alarm), reset alarm to delay 
 * and adjust all other delays 
 * If delta=delay, there is no previously scheduled event, so this is next
 */
static void scheduleAlarm(int e, struct timeval delay) 
{
	struct timeval delta;
	int changed;

	TRACE("scheduleAlarm", e,delay);
	if( TV_CMP(delay, TV_ZERO) == 0 ) return;

	changed = resetAlarm(delay, &delta);
	TRACE("resetAlarm",-1,delta);
	events[e].delay = delta;
	printDelay("setting", e, events[e].delay);

	if( changed ) {	/* adjust all relative times */
		int i;
		for( i=1; i<=eventCount; i++ ) {
			decrTimer(&events[heap[i]].delay, &delta);
#ifdef DEBUG
			if( events[heap[i]].delay.tv_sec<0 
				||  events[heap[i]].delay.tv_usec<0 ) {
				printDelay("after ", i, events[heap[i]].delay);
				printDelay("delta", *(int*)(events[heap[i]].data), delta);
			}
#endif
		}
	}
}


/* this code must be re-entrant in case the callback creates or
 * destroys events. 
 */
#if defined(UNIX)
static void doCB(int dummy)
#elif defined(WIN32)
static void CALLBACK doCB(UINT uTimerID, UINT uMsg, DWORD dwUser, DWORD dw1, DWORD dw2)
#endif
{
	msgAlarmCB cb;
	void *data;

	msgAlarmHold();

#ifdef DEBUG
	fprintf(stderr, "in doCB\n");
#endif

	heapCheck("enter doCB"); 

	timerSet = 0;
	while( 1<=eventCount 
		&& events[heap[1]].delay.tv_sec==0 
		&& events[heap[1]].delay.tv_usec==0) {
		/* this event should occur.  */
		heapSwap(1,eventCount); 
		heapSwap(eventCount, toDo-1);
		eventCount--; toDo--;	    
		heapDown(1);
	}

	findNextEvent();	/* re-establish invariant */

	for( ; toDo < MAXEVENTS; toDo++ ) {
		/* now do scheduled events */
		cb = events[heap[toDo]].cb;
		data = events[heap[toDo]].data;
#ifdef	WIN32
		LeaveCriticalSection(&CSHold);
#endif
		(*cb)(data);
#ifdef	WIN32
		EnterCriticalSection(&CSHold);
#endif
		events[heap[toDo]].cb = NULL;
	}
	heapCheck("exit doCB"); 

	msgAlarmRelease();
}

/* determine next event and reset alarm. */
static void findNextEvent(void) 
{
	heapCheck("findNext"); 
	if( eventCount > 0 ) {
		scheduleAlarm(heap[1], events[heap[1]].delay);
	}
	heapCheck("findNext exit"); 
}

/* indices are all into heap */
static void heapSwap(int a, int b)
{
	int t;
	
	t = heap[a];
	heap[a] = heap[b];
	heap[b] = t;

	events[heap[a]].heapIdx = a;
	events[heap[b]].heapIdx = b;
}

static void heapUp(int i) 
{
	while( i > 1 && TV_CMP(events[heap[i]].delay, events[heap[i/2]].delay) < 0 ) {
		heapSwap(i,i/2);
		i = i/2;
	}
}

static void heapDown(int i)
{
	int child;
	int smallest;

	for(;;) {
		child = 2*i;
		smallest = i;
		if( child <= eventCount
			&& (TV_CMP(events[heap[smallest]].delay, 
			events[heap[child]].delay) > 0 ) ) {
			smallest = child;
		}
		if( child+1 <= eventCount
			&& (TV_CMP(events[heap[smallest]].delay, 
			events[heap[child+1]].delay) > 0 ) ) {
			smallest = child+1;
		}
		if( smallest == i ) break;
		heapSwap(i,smallest);
		i = smallest;
	}
	heapCheck("down"); 
}

#ifdef DEBUG
static void heapCheck(char*msg)
{
	int i;

	for( i=1;i<MAXEVENTS; i++) {
		if(i!=events[heap[i]].heapIdx)
			fprintf(stderr, "bad back ref %d %d\n", i, events[heap[i]].heapIdx );
	}

	for( i=1;  i*2 <= eventCount; i++ ) {
		if( TV_CMP(events[heap[i]].delay, events[heap[i*2]].delay) > 0 ) {
			fprintf(stderr, "%s: out of order %d=%d.06%d  %d=%d.06%d\n",
					msg,
					i, events[heap[i]].delay.tv_sec, 
					events[heap[i]].delay.tv_usec,
					i*2, events[heap[i*2]].delay.tv_sec, 
					events[heap[i*2]].delay.tv_usec);
		}
		if( i*2+1 <= eventCount &&
			TV_CMP(events[heap[i]].delay, events[heap[i*2+1]].delay) > 0 ) {
			fprintf(stderr, "%s: out of order %d=%d.06%d  %d=%d.06%d\n",
					msg,
					i, events[heap[i]].delay.tv_sec, 
					events[heap[i]].delay.tv_usec,
					i*2+1, events[heap[i*2+1]].delay.tv_sec, 
					events[heap[i*2+1]].delay.tv_usec);
		}
	}
}
#endif

/*========================================================================
// msgAlarm Tracer */
void	msgAlarmSetTracer(TCR tracer)
{
	alrm_tracer = tracer;
}

TCR	msgAlarmGetTracer(void)
{
	return alrm_tracer;
}


