diff options
| author | Grissiom <[email protected]> | 2013-09-26 15:52:02 +0800 |
|---|---|---|
| committer | Grissiom <[email protected]> | 2013-10-12 22:48:29 +0800 |
| commit | d59aa279c37b7aba07385a3a2cb3057bce6c5fea (patch) | |
| tree | f31c60b9e357c6c0f62485069ffad7fa52315868 /include/rtdef.h | |
| parent | 83bb05419f7aba80f6a10a48f88a2838a356737a (diff) | |
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.
Diffstat (limited to 'include/rtdef.h')
| -rw-r--r-- | include/rtdef.h | 11 |
1 files changed, 10 insertions, 1 deletions
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 */ |