• G
    kernel: use skip list to implement timer list · d59aa279
    Grissiom 提交于
    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.
    d59aa279
thread.c 19.2 KB