From d59aa279c37b7aba07385a3a2cb3057bce6c5fea Mon Sep 17 00:00:00 2001 From: Grissiom Date: Thu, 26 Sep 2013 15:52:02 +0800 Subject: kernel: use skip list to implement timer list Skip list is a "random" data structure that in high possibilities it would get O(log(N)) time complexity in inserting while the old list get O(N). Forthermore, when set RT_TIMER_SKIP_LIST_LEVEL to 1, it will just the same as the old double linked list, both in time and space complexity. Benchmarks shows that when RT_TIMER_SKIP_LIST_LEVEL is 3, the average time of random insertion of new timer is about 2 times faster than the old timer when there are 100 timers and 3 times faster when there are 200 timers. However, it restores the deprecated funcion rt_system_timer_init. BSPs must invoke it upon system startup. --- include/rtdef.h | 11 ++++++++++- 1 file changed, 10 insertions(+), 1 deletion(-) (limited to 'include') diff --git a/include/rtdef.h b/include/rtdef.h index 09574d2233..be8843d85c 100644 --- a/include/rtdef.h +++ b/include/rtdef.h @@ -410,6 +410,15 @@ struct rt_object_information #define RT_TIMER_CTRL_SET_ONESHOT 0x2 /**< change timer to one shot */ #define RT_TIMER_CTRL_SET_PERIODIC 0x3 /**< change timer to periodic */ +#ifndef RT_TIMER_SKIP_LIST_LEVEL +#define RT_TIMER_SKIP_LIST_LEVEL 1 +#endif + +/* 1 or 3 */ +#ifndef RT_TIMER_SKIP_LIST_MASK +#define RT_TIMER_SKIP_LIST_MASK 0x3 +#endif + /** * timer structure */ @@ -417,7 +426,7 @@ struct rt_timer { struct rt_object parent; /**< inherit from rt_object */ - rt_list_t list; /**< the node of timer list */ + rt_list_t row[RT_TIMER_SKIP_LIST_LEVEL]; void (*timeout_func)(void *parameter); /**< timeout function */ void *parameter; /**< timeout function's parameter */ -- cgit v1.3.1