summaryrefslogtreecommitdiff
path: root/src
diff options
context:
space:
mode:
Diffstat (limited to 'src')
-rw-r--r--src/common/timer.c334
-rw-r--r--src/common/timer.h1
2 files changed, 110 insertions, 225 deletions
diff --git a/src/common/timer.c b/src/common/timer.c
index b26282403..9cdeaca53 100644
--- a/src/common/timer.c
+++ b/src/common/timer.c
@@ -2,9 +2,10 @@
// For more information, see LICENCE in the main folder
#include "../common/cbasetypes.h"
+#include "../common/db.h"
#include "../common/malloc.h"
#include "../common/showmsg.h"
-#include "../common/db.h"
+#include "../common/utils.h"
#include "timer.h"
#include <stdio.h>
@@ -26,19 +27,19 @@
#define TIMER_MAX_INTERVAL 1000
// timers (array)
-static struct TimerData* timer_data = NULL;
-static int timer_data_max = 0;
-static int timer_data_num = 0;
+static struct TimerData* timer_data = NULL;
+static int timer_data_max = 0;
+static int timer_data_num = 0;
// free timers (array)
-static int* free_timer_list = NULL;
-static int free_timer_list_max = 0;
-static int free_timer_list_num = 0;
+static int* free_timer_list = NULL;
+static int free_timer_list_max = 0;
+static int free_timer_list_pos = 0;
-// timer heap (binary min heap)
-static int* timer_heap = NULL;
-static int timer_heap_max = 0;
-static int timer_heap_num = 0;
+// timer heap (ordered array of tid's)
+static int timer_heap_num = 0;
+static int timer_heap_max = 0;
+static int* timer_heap = NULL;
// server startup time
time_t start_time;
@@ -146,14 +147,23 @@ unsigned int gettick(void)
* CORE : Timer Heap
*--------------------------------------*/
-// root at index 0
-#define BHEAP_PARENT(pos) ( ((pos) - 1)/2 )
-#define BHEAP_LEFT(pos) ( (pos)*2 + 1 )
-#define BHEAP_RIGHT(pos) ( (pos)*2 + 2 )
+// searches for the target tick's position and stores it in pos (binary search)
+#define HEAP_SEARCH(target,from,to,pos) \
+ do { \
+ int max,pivot; \
+ max = to; \
+ pos = from; \
+ while (pos < max) { \
+ pivot = (pos + max) / 2; \
+ if (DIFF_TICK(target, timer_data[timer_heap[pivot]].tick) < 0) \
+ pos = pivot + 1; \
+ else \
+ max = pivot; \
+ } \
+ } while(0)
/// Adds a timer to the timer_heap
-static
-void push_timer_heap(int tid)
+static void push_timer_heap(int tid)
{
int pos;
@@ -168,179 +178,44 @@ void push_timer_heap(int tid)
memset(timer_heap + (timer_heap_max - 256), 0, sizeof(int)*256);
}
- // add the timer at the end
- pos = timer_heap_num++;
- timer_heap[pos] = tid;
- // restore binary heap properties
- while( pos > 0 )
+ // do a sorting from higher to lower
+ if( timer_heap_num == 0 || DIFF_TICK(timer_data[tid].tick, timer_data[timer_heap[timer_heap_num - 1]].tick) < 0 )
+ timer_heap[timer_heap_num] = tid; // if lower actual item is higher than new
+ else
{
- int parent = BHEAP_PARENT(pos);
- if( DIFF_TICK(timer_data[tid].tick, timer_data[timer_heap[parent]].tick) > 0 )
- break;// done
- swap(timer_heap[pos], timer_heap[parent]);
- pos = parent;
+ // searching position
+ HEAP_SEARCH(timer_data[tid].tick,0,timer_heap_num-1,pos);
+ // move elements
+ memmove(&timer_heap[pos + 1], &timer_heap[pos], sizeof(int) * (timer_heap_num - pos));
+ // save new element
+ timer_heap[pos] = tid;
}
-}
-
-/// Removes a timer from the timer_heap
-static
-bool pop_timer_heap(int tid)
-{
- int pos;
-
- // find the timer
-#if 1
- // trying a simple array search
- ARR_FIND(0, timer_heap_num, pos, timer_heap[pos] == tid);
-#else
- pos = 0;
- while( pos < timer_heap_num )
- {// search in the order current-left-right
- int left = BHEAP_LEFT(pos);
- int right = BHEAP_RIGHT(pos);
-
- if( timer_heap[pos] == tid )
- break;// found the timer
- if( left < timer_heap_num && DIFF_TICK(timer_data[tid].tick, timer_data[timer_heap[left]].tick) >= 0 )
- {// try left child
- pos = left;
- continue;
- }
- if( right < timer_heap_num && DIFF_TICK(timer_data[tid].tick, timer_data[timer_heap[right]].tick) >= 0 )
- {// try right child
- pos = right;
- continue;
- }
- // back and right
- while( true )
- {
- int parent;
- if( pos == 0 )
- return false;// not found
- parent = BHEAP_PARENT(pos);
- right = BHEAP_RIGHT(parent);
- if( pos != right && right < timer_heap_num && DIFF_TICK(timer_data[tid].tick, timer_data[timer_heap[right]].tick) >= 0 )
- break;// try this right
- pos = parent;
- }
- pos = right;
- }
-#endif
- if( pos >= timer_heap_num )
- return false;// not found
-
- // remove timer (replace with last one)
- timer_heap[pos] = timer_heap[--timer_heap_num];
- // restore binary heap properties
- while( pos < timer_heap_num )
- {
- int left = BHEAP_LEFT(pos);
- int right = BHEAP_RIGHT(pos);
- if( left < timer_heap_num && DIFF_TICK(timer_data[timer_heap[pos]].tick, timer_data[timer_heap[left]].tick) > 0 )
- {// left exists and has smaller tick
- if( right < timer_heap_num && DIFF_TICK(timer_data[timer_heap[left]].tick, timer_data[timer_heap[right]].tick) > 0 )
- {// right exists and has even smaller tick
- swap(timer_heap[pos], timer_heap[right]);
- pos = right;
- }
- else
- {
- swap(timer_heap[pos], timer_heap[left]);
- pos = left;
- }
- }
- else if( right < timer_heap_num && DIFF_TICK(timer_data[timer_heap[pos]].tick, timer_data[timer_heap[right]].tick) > 0 )
- {// right exists and has smaller tick
- swap(timer_heap[pos], timer_heap[right]);
- pos = right;
- }
- else
- {
- break;// done
- }
- }
- return true;
+ timer_heap_num++;
}
/*==========================
* Timer Management
*--------------------------*/
-// diff_tick limits (2*24*60*60*1000 is 2 days ; 2*60*60*1000 is 2 hours)
-#define FUTURE_DIFF_TICK ( INT_MIN + 2*24*60*60*1000 )
-#define MAX_DIFF_TICK ( INT_MAX - 2*60*60*1000 )
-#define MIN_DIFF_TICK ( -2*60*60*1000 )
-#define PAST_DIFF_TICK ( -2*24*60*60*1000 )
-
-/// Adjusts the tick value to a valid tick_diff range.
-/// Returns false if the tick is invalid.
-static
-bool adjust_tick(unsigned int* tick)
-{
- int diff;
-
- if( tick == NULL )
- return false;
-
- diff = DIFF_TICK(*tick, gettick());
- if( diff <= FUTURE_DIFF_TICK || diff > MAX_DIFF_TICK )
- {
- ShowWarning("adjust_tick: tick diff too far in the future %d, adjusting to the maximum %d\n", diff, MAX_DIFF_TICK);
- *tick -= (diff - MAX_DIFF_TICK);
- }
- else if( diff < PAST_DIFF_TICK )
- {
- return false;
- }
- else if( diff < MIN_DIFF_TICK )
- {
- ShowWarning("adjust_tick: tick diff too far in the past %d, adjusting to the minimm %d\n", diff, MIN_DIFF_TICK);
- *tick += (diff - MAX_DIFF_TICK);
- }
- return true;
-}
-
-/// Releases a timer.
-static
-void release_timer(int tid)
-{
- if( timer_data[tid].type == 0 )
- return;// already released
-
- memset(&timer_data[tid], 0, sizeof(struct TimerData));
- if( free_timer_list_num >= free_timer_list_max )
- {
- free_timer_list_max += 256;
- if( free_timer_list )
- RECREATE(free_timer_list, int, free_timer_list_max);
- else
- CREATE(free_timer_list, int, free_timer_list_max);
- memset(free_timer_list + (free_timer_list_max - 256), 0, sizeof(int)*256);
- }
- free_timer_list[free_timer_list_num++] = tid;
-}
-
/// Returns a free timer id.
static int acquire_timer(void)
{
int tid;
// select a free timer
- tid = timer_data_num;
- while( free_timer_list_num )
- {
- int pos = --free_timer_list_num;
- if( free_timer_list[pos] < timer_data_num && timer_data[free_timer_list[pos]].type == 0 )
- {// freed and released
- tid = free_timer_list[pos];
- break;
- }
- }
+ if (free_timer_list_pos) {
+ do {
+ tid = free_timer_list[--free_timer_list_pos];
+ } while(tid >= timer_data_num && free_timer_list_pos > 0);
+ } else
+ tid = timer_data_num;
// check available space
- if( tid >= timer_data_max )
- {
+ if( tid >= timer_data_num )
+ for (tid = timer_data_num; tid < timer_data_max && timer_data[tid].type; tid++);
+ if (tid >= timer_data_num && tid >= timer_data_max)
+ {// expand timer array
timer_data_max += 256;
if( timer_data )
RECREATE(timer_data, struct TimerData, timer_data_max);
@@ -360,12 +235,7 @@ static int acquire_timer(void)
int add_timer(unsigned int tick, TimerFunc func, int id, intptr data)
{
int tid;
-
- if( !adjust_tick(&tick) )
- {
- ShowError("add_timer: tick out of range (tick=%u %08x[%s] id=%d data=%d diff_tick=%d)\n", tick, (int)func, search_timer_func_list(func), id, data, DIFF_TICK(tick, gettick()));
- return INVALID_TIMER;
- }
+
tid = acquire_timer();
timer_data[tid].tick = tick;
timer_data[tid].func = func;
@@ -379,7 +249,7 @@ int add_timer(unsigned int tick, TimerFunc func, int id, intptr data)
}
/// Starts a new timer that automatically restarts itself (infinite loop until manually removed).
-/// Returns the timer's id, or -1 if it fails.
+/// Returns the timer's id, or INVALID_TIMER if it fails.
int add_timer_interval(unsigned int tick, TimerFunc func, int id, intptr data, int interval)
{
int tid;
@@ -389,12 +259,7 @@ int add_timer_interval(unsigned int tick, TimerFunc func, int id, intptr data, i
ShowError("add_timer_interval: invalid interval (tick=%u %08x[%s] id=%d data=%d diff_tick=%d)\n", tick, (int)func, search_timer_func_list(func), id, data, DIFF_TICK(tick, gettick()));
return INVALID_TIMER;
}
- if( !adjust_tick(&tick) )
- {
- ShowError("add_timer_interval: tick out of range (tick=%u %08x[%s] id=%d data=%d diff_tick=%d)\n", tick, (int)func, search_timer_func_list(func), id, data, DIFF_TICK(tick, gettick()));
- return INVALID_TIMER;
- }
-
+
tid = acquire_timer();
timer_data[tid].tick = tick;
timer_data[tid].func = func;
@@ -410,9 +275,7 @@ int add_timer_interval(unsigned int tick, TimerFunc func, int id, intptr data, i
/// Retrieves internal timer data
const struct TimerData* get_timer(int tid)
{
- if( tid >= 0 && tid < timer_data_num && timer_data[tid].type != 0 )
- return &timer_data[tid];
- return NULL;
+ return ( tid >= 0 && tid < timer_data_num ) ? &timer_data[tid] : NULL;
}
/// Marks a timer specified by 'id' for immediate deletion once it expires.
@@ -420,7 +283,7 @@ const struct TimerData* get_timer(int tid)
/// Returns 0 on success, < 0 on failure.
int delete_timer(int tid, TimerFunc func)
{
- if( tid < 0 || tid >= timer_data_num || timer_data[tid].type == 0 )
+ if( tid < 0 || tid >= timer_data_num )
{
ShowError("delete_timer error : no such timer %d (%08x(%s))\n", tid, (int)func, search_timer_func_list(func));
return -1;
@@ -431,13 +294,9 @@ int delete_timer(int tid, TimerFunc func)
return -2;
}
- if( timer_data[tid].type&TIMER_REMOVE_HEAP )
- // timer func being executed, make sure it's marked for removal when it ends
- timer_data[tid].type = TIMER_FORCE_REMOVE|TIMER_REMOVE_HEAP;
- else if( pop_timer_heap(tid) )
- release_timer(tid);
- else if( (timer_data[tid].type&TIMER_REMOVE_HEAP) == 0 )
- ShowDebug("delete_timer: failed to remove timer %d (%08x(%s), type=%d)\n", tid, (int)func, search_timer_func_list(func), timer_data[tid].type);
+ timer_data[tid].func = NULL;
+ timer_data[tid].type = TIMER_ONCE_AUTODEL;
+
return 0;
}
@@ -452,25 +311,50 @@ int addtick_timer(int tid, unsigned int tick)
/// Returns the new tick value, or -1 if it fails.
int settick_timer(int tid, unsigned int tick)
{
- if( tid < 0 || tid >= timer_data_num || timer_data[tid].type == 0 )
- {
- ShowError("settick_timer error : no such timer %d\n", tid);
- return -1;
- }
- if( timer_data[tid].tick == tick )
+ int old_pos,pos;
+ unsigned int old_tick;
+
+ old_tick = timer_data[tid].tick;
+ if( old_tick == tick )
return tick;
- if( !adjust_tick(&tick) )
- {
- ShowError("settick_timer: tick out of range, leaving timer unmodified (tid=%d tick=%u %08x[%s] diff_tick=%d)\n", tid, tick, (int)timer_data[tid].func, search_timer_func_list(timer_data[tid].func), DIFF_TICK(tick, gettick()));
- return -1;
+ // search old_tick position
+ HEAP_SEARCH(old_tick,0,timer_heap_num-1,old_pos);
+ while( timer_heap[old_pos] != tid )
+ {// skip timers with the same tick
+ if( old_tick != timer_data[timer_heap[old_pos]].tick )
+ {
+ ShowError("settick_timer: no such timer %d (%08x(%s))\n", tid, (int)timer_data[tid].func, search_timer_func_list(timer_data[tid].func));
+ return -1;
+ }
+ ++old_pos;
}
- pop_timer_heap(tid);
- if( tick == -1 )
- tick = 0;// -1 is reserved for error
- timer_data[tid].type &= ~TIMER_REMOVE_HEAP;
+
+ if( DIFF_TICK(tick,timer_data[tid].tick) < 0 )
+ {// Timer is accelerated, shift timer near the end of the heap.
+ if (old_pos == timer_heap_num-1) //Nothing to shift.
+ pos = old_pos;
+ else {
+ HEAP_SEARCH(tick,old_pos+1,timer_heap_num-1,pos);
+ --pos;
+ if (pos != old_pos)
+ memmove(&timer_heap[old_pos], &timer_heap[old_pos+1], (pos-old_pos)*sizeof(int));
+ }
+ } else
+ {// Timer is delayed, shift timer near the beginning of the heap.
+ if (old_pos == 0) //Nothing to shift.
+ pos = old_pos;
+ else {
+ HEAP_SEARCH(tick,0,old_pos-1,pos);
+ ++pos;
+ if (pos != old_pos)
+ memmove(&timer_heap[pos+1], &timer_heap[pos], (old_pos-pos)*sizeof(int));
+ }
+ }
+
+ timer_heap[pos] = tid;
timer_data[tid].tick = tick;
- push_timer_heap(tid);
+
return tick;
}
@@ -483,13 +367,13 @@ int do_timer(unsigned int tick)
// process all timers one by one
while( timer_heap_num )
{
- int tid = timer_heap[0]; // first element in heap (smallest tick)
+ int tid = timer_heap[timer_heap_num - 1]; // last element in heap (smallest tick)
diff = DIFF_TICK(timer_data[tid].tick, tick);
if( diff > 0 )
break; // no more expired timers to process
- pop_timer_heap(tid);
+ --timer_heap_num; // suppress the actual element from the table
// mark timer as 'to be removed'
timer_data[tid].type |= TIMER_REMOVE_HEAP;
@@ -507,32 +391,34 @@ int do_timer(unsigned int tick)
}
// in the case the function didn't change anything...
- if( timer_data[tid].type & TIMER_REMOVE_HEAP || timer_data[tid].type == TIMER_FORCE_REMOVE )
+ if( timer_data[tid].type & TIMER_REMOVE_HEAP )
{
timer_data[tid].type &= ~TIMER_REMOVE_HEAP;
switch( timer_data[tid].type )
{
- case TIMER_FORCE_REMOVE:
case TIMER_ONCE_AUTODEL:
- release_timer(tid);
- break;
+ timer_data[tid].type = 0;
+ if (free_timer_list_pos >= free_timer_list_max) {
+ free_timer_list_max += 256;
+ RECREATE(free_timer_list,int,free_timer_list_max);
+ memset(free_timer_list + (free_timer_list_max - 256), 0, 256 * sizeof(int));
+ }
+ free_timer_list[free_timer_list_pos++] = tid;
+ break;
case TIMER_INTERVAL:
if( DIFF_TICK(timer_data[tid].tick, tick) < -1000 )
timer_data[tid].tick = tick + timer_data[tid].interval;
else
timer_data[tid].tick += timer_data[tid].interval;
+ timer_data[tid].type &= ~TIMER_REMOVE_HEAP;
push_timer_heap(tid);
- break;
+ break;
}
}
}
- if( diff < TIMER_MIN_INTERVAL )
- return TIMER_MIN_INTERVAL;
- if( diff > TIMER_MAX_INTERVAL )
- return TIMER_MAX_INTERVAL;
- return diff;
+ return cap_value(diff, TIMER_MIN_INTERVAL, TIMER_MAX_INTERVAL);
}
unsigned long get_uptime(void)
diff --git a/src/common/timer.h b/src/common/timer.h
index 980907a70..354a71113 100644
--- a/src/common/timer.h
+++ b/src/common/timer.h
@@ -15,7 +15,6 @@
// timer flags
#define TIMER_ONCE_AUTODEL 0x01
#define TIMER_INTERVAL 0x02
-#define TIMER_FORCE_REMOVE 0x04
#define TIMER_REMOVE_HEAP 0x10
// Struct declaration