[数据结构与算法]定时器的设计

实现定时器的结构

实现定时器的底层结构，一般有
1、红黑树
2、时间轮
3、跳表
4、最小堆

定时器的作用

1、超时控制
2、定时任务

问一下，想要实现一个定时器，数据结构需要具备哪些特性？
插入数据的时候，查找和插入的速度都得要快才行（时间复杂度）
同时要保证，结构的有序性

跳表实现定时器

redis中的zset类型， 当插入的元素个数超过128个时，用跳表来实现的。
那么redis的定时器时怎么实现的，redis是用无序的双端链表来实现的定时器的。

但作者说了，这种无序的双端链表的时间复杂度为O(N)。可以用跳表的方法来实现。
跳表 的 增删改查 事件的复杂度， 大概率是趋向于 O(logN）。

现在让我们来用跳表来实现一个定时器的功能。

内部定时器：
1） 插入，删除 （任意节点和头节点） O（logN）
2） 过期时间，只需要跟第一个节点比较（节点的score存放的是时间戳）
外部定时器需要提供一下的这些接口：
1、初始化
2、添加定时器
3、删除定时器
4、定时器过期函数

我们还可以沿用redis源码中的跳表的一些结构。

skiplist.h

#define ZSKIPLIST_MAXLEVEL 32 /* Should be enough for 2^64 elements */
#define ZSKIPLIST_P 0.25      /* Skiplist P = 1/4 */

typedef struct zskiplistNode zskiplistNode;
typedef void (*handler_pt) (zskiplistNode *node);
struct zskiplistNode {
    // sds ele;
    // double score;
    unsigned long score; // 时间戳
    handler_pt handler;
    /* struct zskiplistNode *backward; 从后向前遍历时使用*/
    struct zskiplistLevel {
        struct zskiplistNode *forward;
        /* unsigned long span; 这个存储的level间节点的个数，在定时器中并不需要*/ 
    } level[];
};

typedef struct zskiplist {
    // 添加一个free的函数
    struct zskiplistNode *header/*, *tail 并不需要知道最后一个节点*/;
    int length;
    int level;
} zskiplist;

zskiplist *zslCreate(void);
void zslFree(zskiplist *zsl);
zskiplistNode *zslInsert(zskiplist *zsl, unsigned long score, handler_pt func);
zskiplistNode* zslMin(zskiplist *zsl);
void zslDeleteHead(zskiplist *zsl);
void zslDelete(zskiplist *zsl, zskiplistNode* zn); 

void zslPrint(zskiplist *zsl);

skiplist.c

#include <stdlib.h>
#include <stdio.h>
#include "skiplist.h"

void defaultHandler(zskiplistNode *node) {
}

/* Create a skiplist node with the specified number of levels. */
zskiplistNode *zslCreateNode(int level, unsigned long score, handler_pt func) {
    zskiplistNode *zn =
        malloc(sizeof(*zn)+level*sizeof(struct zskiplistLevel));
    zn->score = score;
    zn->handler = func;
    return zn;
}

zskiplist *zslCreate(void) {
    int j;
    zskiplist *zsl;

    zsl = malloc(sizeof(*zsl));
    zsl->level = 1;
    zsl->length = 0;
    zsl->header = zslCreateNode(ZSKIPLIST_MAXLEVEL,0,defaultHandler);
    for (j = 0; j < ZSKIPLIST_MAXLEVEL; j++) {
        zsl->header->level[j].forward = NULL;
    }
    return zsl;
}

/* Free a whole skiplist. */
void zslFree(zskiplist *zsl) {
    zskiplistNode *node = zsl->header->level[0].forward, *next;

    free(zsl->header);
    while(node) {
        next = node->level[0].forward;
        free(node);
        node = next;
    }
    free(zsl);
}

int zslRandomLevel(void) {
    int level = 1;
    while ((arc4random()&0xFFFF) < (ZSKIPLIST_P * 0xFFFF))
        level += 1;
    return (level<ZSKIPLIST_MAXLEVEL) ? level : ZSKIPLIST_MAXLEVEL;
}

zskiplistNode *zslInsert(zskiplist *zsl, unsigned long score, handler_pt func) {
    zskiplistNode *update[ZSKIPLIST_MAXLEVEL], *x;
    int i, level;

    x = zsl->header;
    for (i = zsl->level-1; i >= 0; i--) {
        while (x->level[i].forward &&
                x->level[i].forward->score < score)
        {
            x = x->level[i].forward;
        }
        update[i] = x;
    }
    level = zslRandomLevel();
    printf("zskiplist add node level = %d\n", level);
    if (level > zsl->level) {
        for (i = zsl->level; i < level; i++) {
            update[i] = zsl->header;
        }
        zsl->level = level;
    }
    x = zslCreateNode(level,score,func);
    for (i = 0; i < level; i++) {
        x->level[i].forward = update[i]->level[i].forward;
        update[i]->level[i].forward = x;
    }

    zsl->length++;
    return x;
}

zskiplistNode* zslMin(zskiplist *zsl) {
    zskiplistNode *x;
    x = zsl->header;
    return x->level[0].forward;
}

void zslDeleteHead(zskiplist *zsl) {
    zskiplistNode *update[ZSKIPLIST_MAXLEVEL];
    zskiplistNode *x = zslMin(zsl);
    if (!x) return;
    int i;
    for (i = zsl->level-1; i >= 0; i--) {
        if (zsl->header->level[i].forward == x) {
            zsl->header->level[i].forward = x->level[i].forward;
        }
    }
    while(zsl->level > 1 && zsl->header->level[zsl->level-1].forward == NULL)
        zsl->level--;
    zsl->length--;
}

void zslDeleteNode(zskiplist *zsl, zskiplistNode *x, zskiplistNode **update) {
    int i;
    for (i = 0; i < zsl->level; i++) {
        if (update[i]->level[i].forward == x) {
            update[i]->level[i].forward = x->level[i].forward;
        }
    }
    while(zsl->level > 1 && zsl->header->level[zsl->level-1].forward == NULL)
        zsl->level--;
    zsl->length--;
}

void zslDelete(zskiplist *zsl, zskiplistNode* zn) {
    zskiplistNode *update[ZSKIPLIST_MAXLEVEL], *x;
    int i;

    x = zsl->header;
    for (i = zsl->level-1; i >= 0; i--) {
        while (x->level[i].forward &&
                x->level[i].forward->score < zn->score)
        {
            x = x->level[i].forward;
        }
        update[i] = x;
    }
    x = x->level[0].forward;
    if (x && zn->score == x->score) {
        zslDeleteNode(zsl, x, update);
        free(x);
    }
}

void zslPrint(zskiplist *zsl) {
    zskiplistNode *x;
    x = zsl->header;
    x = x->level[0].forward;
    printf("start print skiplist level = %d\n", zsl->level);
    int i;
    for (i = 0; i < zsl->length; i++) {
        printf("skiplist ele %d: score = %lu\n", i+1, x->score);
        x = x->level[0].forward;
    }
}

红黑树实现定时器

二叉树 有可能因为某些数据的插入，退化为单链表。为了平衡，于是有了AVL，AVL树 左右子树高度差为1，但AVL平衡操作太重度了。

而红黑树，维护一个黑高度 一致，解决平衡操作太重度

查找过期定时器，
需要查找最左边的节点， 效率比较差一些
如果数据足够大，查找最左边的节点，要查找很多。

nginx里面就有红黑树的实现。
沿用nginx框架中的， rbtree.c, rbtree.h文件。 来实现定时器

rbtree.h

/*
 * Copyright (C) Igor Sysoev
 * Copyright (C) Nginx, Inc.
 */


#ifndef _NGX_RBTREE_H_INCLUDED_
#define _NGX_RBTREE_H_INCLUDED_


typedef unsigned int  ngx_rbtree_key_t;
typedef unsigned int  ngx_uint_t;
typedef int   ngx_rbtree_key_int_t;
typedef unsigned char u_char;
#ifndef NULL
    #define NULL ((void*)0)
#endif


typedef struct ngx_rbtree_node_s  ngx_rbtree_node_t;

struct ngx_rbtree_node_s {
    ngx_rbtree_key_t       key;
    ngx_rbtree_node_t     *left;
    ngx_rbtree_node_t     *right;
    ngx_rbtree_node_t     *parent;
    u_char                 color;
    u_char                 data;
};


typedef struct ngx_rbtree_s  ngx_rbtree_t;

typedef void (*ngx_rbtree_insert_pt) (ngx_rbtree_node_t *root,
    ngx_rbtree_node_t *node, ngx_rbtree_node_t *sentinel);

struct ngx_rbtree_s {
    ngx_rbtree_node_t     *root;
    ngx_rbtree_node_t     *sentinel;
    ngx_rbtree_insert_pt   insert;
};


#define ngx_rbtree_init(tree, s, i)                                           \
    ngx_rbtree_sentinel_init(s);                                              \
    (tree)->root = s;                                                         \
    (tree)->sentinel = s;                                                     \
    (tree)->insert = i


void ngx_rbtree_insert(ngx_rbtree_t *tree, ngx_rbtree_node_t *node);
void ngx_rbtree_delete(ngx_rbtree_t *tree, ngx_rbtree_node_t *node);
void ngx_rbtree_insert_value(ngx_rbtree_node_t *root, ngx_rbtree_node_t *node,
    ngx_rbtree_node_t *sentinel);
void ngx_rbtree_insert_timer_value(ngx_rbtree_node_t *root,
    ngx_rbtree_node_t *node, ngx_rbtree_node_t *sentinel);
ngx_rbtree_node_t *ngx_rbtree_next(ngx_rbtree_t *tree,
    ngx_rbtree_node_t *node);


#define ngx_rbt_red(node)               ((node)->color = 1)
#define ngx_rbt_black(node)             ((node)->color = 0)
#define ngx_rbt_is_red(node)            ((node)->color)
#define ngx_rbt_is_black(node)          (!ngx_rbt_is_red(node))
#define ngx_rbt_copy_color(n1, n2)      (n1->color = n2->color)

/* a sentinel must be black */

#define ngx_rbtree_sentinel_init(node)  ngx_rbt_black(node)


static inline ngx_rbtree_node_t *
ngx_rbtree_min(ngx_rbtree_node_t *node, ngx_rbtree_node_t *sentinel)
{
    while (node->left != sentinel) {
        node = node->left;
    }

    return node;
}


#endif /* _NGX_RBTREE_H_INCLUDED_ */

rbtree.cpp

/*
 * Copyright (C) Igor Sysoev
 * Copyright (C) Nginx, Inc.
 */


#include "rbtree.h"


/*
 * The red-black tree code is based on the algorithm described in
 * the "Introduction to Algorithms" by Cormen, Leiserson and Rivest.
 */


static inline void ngx_rbtree_left_rotate(ngx_rbtree_node_t **root,
    ngx_rbtree_node_t *sentinel, ngx_rbtree_node_t *node);
static inline void ngx_rbtree_right_rotate(ngx_rbtree_node_t **root,
    ngx_rbtree_node_t *sentinel, ngx_rbtree_node_t *node);


void
ngx_rbtree_insert(ngx_rbtree_t *tree, ngx_rbtree_node_t *node)
{
    ngx_rbtree_node_t  **root, *temp, *sentinel;

    /* a binary tree insert */

    root = &tree->root;
    sentinel = tree->sentinel;

    if (*root == sentinel) {
        node->parent = NULL;
        node->left = sentinel;
        node->right = sentinel;
        ngx_rbt_black(node);
        *root = node;

        return;
    }

    tree->insert(*root, node, sentinel);

    /* re-balance tree */

    while (node != *root && ngx_rbt_is_red(node->parent)) {

        if (node->parent == node->parent->parent->left) {
            temp = node->parent->parent->right;

            if (ngx_rbt_is_red(temp)) {
                ngx_rbt_black(node->parent);
                ngx_rbt_black(temp);
                ngx_rbt_red(node->parent->parent);
                node = node->parent->parent;

            } else {
                if (node == node->parent->right) {
                    node = node->parent;
                    ngx_rbtree_left_rotate(root, sentinel, node);
                }

                ngx_rbt_black(node->parent);
                ngx_rbt_red(node->parent->parent);
                ngx_rbtree_right_rotate(root, sentinel, node->parent->parent);
            }

        } else {
            temp = node->parent->parent->left;

            if (ngx_rbt_is_red(temp)) {
                ngx_rbt_black(node->parent);
                ngx_rbt_black(temp);
                ngx_rbt_red(node->parent->parent);
                node = node->parent->parent;

            } else {
                if (node == node->parent->left) {
                    node = node->parent;
                    ngx_rbtree_right_rotate(root, sentinel, node);
                }

                ngx_rbt_black(node->parent);
                ngx_rbt_red(node->parent->parent);
                ngx_rbtree_left_rotate(root, sentinel, node->parent->parent);
            }
        }
    }

    ngx_rbt_black(*root);
}


void
ngx_rbtree_insert_value(ngx_rbtree_node_t *temp, ngx_rbtree_node_t *node,
    ngx_rbtree_node_t *sentinel)
{
    ngx_rbtree_node_t  **p;

    for ( ;; ) {

        p = (node->key < temp->key) ? &temp->left : &temp->right;

        if (*p == sentinel) {
            break;
        }

        temp = *p;
    }

    *p = node;
    node->parent = temp;
    node->left = sentinel;
    node->right = sentinel;
    ngx_rbt_red(node);
}


void
ngx_rbtree_insert_timer_value(ngx_rbtree_node_t *temp, ngx_rbtree_node_t *node,
    ngx_rbtree_node_t *sentinel)
{
    ngx_rbtree_node_t  **p;

    for ( ;; ) {

        /*
         * Timer values
         * 1) are spread in small range, usually several minutes,
         * 2) and overflow each 49 days, if milliseconds are stored in 32 bits.
         * The comparison takes into account that overflow.
         */

        /*  node->key < temp->key */
        p = ((ngx_rbtree_key_int_t) (node->key - temp->key) < 0)
            ? &temp->left : &temp->right;

        if (*p == sentinel) {
            break;
        }

        temp = *p;
    }

    *p = node;
    node->parent = temp;
    node->left = sentinel;
    node->right = sentinel;
    ngx_rbt_red(node);
}


void
ngx_rbtree_delete(ngx_rbtree_t *tree, ngx_rbtree_node_t *node)
{
    ngx_uint_t           red;
    ngx_rbtree_node_t  **root, *sentinel, *subst, *temp, *w;

    /* a binary tree delete */

    root = &tree->root;
    sentinel = tree->sentinel;

    if (node->left == sentinel) {
        temp = node->right;
        subst = node;

    } else if (node->right == sentinel) {
        temp = node->left;
        subst = node;

    } else {
        subst = ngx_rbtree_min(node->right, sentinel);

        if (subst->left != sentinel) {
            temp = subst->left;
        } else {
            temp = subst->right;
        }
    }

    if (subst == *root) {
        *root = temp;
        ngx_rbt_black(temp);

        /* DEBUG stuff */
        node->left = NULL;
        node->right = NULL;
        node->parent = NULL;
        node->key = 0;

        return;
    }

    red = ngx_rbt_is_red(subst);

    if (subst == subst->parent->left) {
        subst->parent->left = temp;

    } else {
        subst->parent->right = temp;
    }

    if (subst == node) {

        temp->parent = subst->parent;

    } else {

        if (subst->parent == node) {
            temp->parent = subst;

        } else {
            temp->parent = subst->parent;
        }

        subst->left = node->left;
        subst->right = node->right;
        subst->parent = node->parent;
        ngx_rbt_copy_color(subst, node);

        if (node == *root) {
            *root = subst;

        } else {
            if (node == node->parent->left) {
                node->parent->left = subst;
            } else {
                node->parent->right = subst;
            }
        }

        if (subst->left != sentinel) {
            subst->left->parent = subst;
        }

        if (subst->right != sentinel) {
            subst->right->parent = subst;
        }
    }

    /* DEBUG stuff */
    node->left = NULL;
    node->right = NULL;
    node->parent = NULL;
    node->key = 0;

    if (red) {
        return;
    }

    /* a delete fixup */

    while (temp != *root && ngx_rbt_is_black(temp)) {

        if (temp == temp->parent->left) {
            w = temp->parent->right;

            if (ngx_rbt_is_red(w)) {
                ngx_rbt_black(w);
                ngx_rbt_red(temp->parent);
                ngx_rbtree_left_rotate(root, sentinel, temp->parent);
                w = temp->parent->right;
            }

            if (ngx_rbt_is_black(w->left) && ngx_rbt_is_black(w->right)) {
                ngx_rbt_red(w);
                temp = temp->parent;

            } else {
                if (ngx_rbt_is_black(w->right)) {
                    ngx_rbt_black(w->left);
                    ngx_rbt_red(w);
                    ngx_rbtree_right_rotate(root, sentinel, w);
                    w = temp->parent->right;
                }

                ngx_rbt_copy_color(w, temp->parent);
                ngx_rbt_black(temp->parent);
                ngx_rbt_black(w->right);
                ngx_rbtree_left_rotate(root, sentinel, temp->parent);
                temp = *root;
            }

        } else {
            w = temp->parent->left;

            if (ngx_rbt_is_red(w)) {
                ngx_rbt_black(w);
                ngx_rbt_red(temp->parent);
                ngx_rbtree_right_rotate(root, sentinel, temp->parent);
                w = temp->parent->left;
            }

            if (ngx_rbt_is_black(w->left) && ngx_rbt_is_black(w->right)) {
                ngx_rbt_red(w);
                temp = temp->parent;

            } else {
                if (ngx_rbt_is_black(w->left)) {
                    ngx_rbt_black(w->right);
                    ngx_rbt_red(w);
                    ngx_rbtree_left_rotate(root, sentinel, w);
                    w = temp->parent->left;
                }

                ngx_rbt_copy_color(w, temp->parent);
                ngx_rbt_black(temp->parent);
                ngx_rbt_black(w->left);
                ngx_rbtree_right_rotate(root, sentinel, temp->parent);
                temp = *root;
            }
        }
    }

    ngx_rbt_black(temp);
}


static inline void
ngx_rbtree_left_rotate(ngx_rbtree_node_t **root, ngx_rbtree_node_t *sentinel,
    ngx_rbtree_node_t *node)
{
    ngx_rbtree_node_t  *temp;

    temp = node->right;
    node->right = temp->left;

    if (temp->left != sentinel) {
        temp->left->parent = node;
    }

    temp->parent = node->parent;

    if (node == *root) {
        *root = temp;

    } else if (node == node->parent->left) {
        node->parent->left = temp;

    } else {
        node->parent->right = temp;
    }

    temp->left = node;
    node->parent = temp;
}


static inline void
ngx_rbtree_right_rotate(ngx_rbtree_node_t **root, ngx_rbtree_node_t *sentinel,
    ngx_rbtree_node_t *node)
{
    ngx_rbtree_node_t  *temp;

    temp = node->left;
    node->left = temp->right;

    if (temp->right != sentinel) {
        temp->right->parent = node;
    }

    temp->parent = node->parent;

    if (node == *root) {
        *root = temp;

    } else if (node == node->parent->right) {
        node->parent->right = temp;

    } else {
        node->parent->left = temp;
    }

    temp->right = node;
    node->parent = temp;
}


ngx_rbtree_node_t *
ngx_rbtree_next(ngx_rbtree_t *tree, ngx_rbtree_node_t *node)
{
    ngx_rbtree_node_t  *root, *sentinel, *parent;

    sentinel = tree->sentinel;

    if (node->right != sentinel) {
        return ngx_rbtree_min(node->right, sentinel);
    }

    root = tree->root;

    for ( ;; ) {
        parent = node->parent;

        if (node == root) {
            return NULL;
        }

        if (node == parent->left) {
            return parent;
        }

        node = parent;
    }
}

rbt_timer.c

#include <stdio.h>
#include <stdint.h>
#include <unistd.h>
#include <stdlib.h>
#include <stddef.h>
#include <time.h>
#include "rbtree.h"

ngx_rbtree_t              timer;
static ngx_rbtree_node_t  sentinel;

typedef struct timer_entry_s timer_entry_t;
typedef void (*timer_handler_pt)(timer_entry_t *ev);

struct timer_entry_s {
    ngx_rbtree_node_t timer;
    timer_handler_pt handler;
};

static uint32_t
current_time() {
	uint32_t t;
#if !defined(__APPLE__) || defined(AVAILABLE_MAC_OS_X_VERSION_10_12_AND_LATER)
	struct timespec ti;
	clock_gettime(CLOCK_MONOTONIC, &ti);
	t = (uint32_t)ti.tv_sec * 1000;
	t += ti.tv_nsec / 1000000;
#else
	struct timeval tv;
	gettimeofday(&tv, NULL);
	t = (uint32_t)tv.tv_sec * 1000;
	t += tv.tv_usec / 1000;
#endif
	return t;
}

// map、set 插入的时候，就更新
int init_timer() {
    // 如果时间戳相同，key相同，插入操作变成修改操作。
    ngx_rbtree_init(&timer, &sentinel, ngx_rbtree_insert_timer_value);
    return 0;
}

void add_timer(timer_entry_t *te, uint32_t msec) {
    msec += current_time();
    printf("add_timer expire at msec = %u\n", msec);
    te->timer.key = msec;
    ngx_rbtree_insert(&timer, &te->timer);
}

void del_timer(timer_entry_t *te) {
    ngx_rbtree_delete(&timer, &te->timer);
}

void expire_timer() {
    timer_entry_t *te;
    ngx_rbtree_node_t *sentinel, *root, *node;
    sentinel = timer.sentinel;
    uint32_t now = current_time();
    for (;;) {
        root = timer.root;
        if (root == sentinel) break;
        node = ngx_rbtree_min(root, sentinel);
        if (node->key > now) break;
        printf("touch timer expire time=%u, now = %u\n", node->key, now);
        te = (timer_entry_t *) ((char *) node - offsetof(timer_entry_t, timer));
        te->handler(te);
        ngx_rbtree_delete(&timer, &te->timer);
        free(te);
    }
}

void print_hello(timer_entry_t *te) {
    printf("hello world time = %u\n", te->timer.key);
}

int main()
{
    init_timer();
    timer_entry_t *te = malloc(sizeof(timer_entry_t));
    memset(te, 0, sizeof(timer_entry_t));
    te->handler = print_hello;
    add_timer(te, 3000);
    for (;;) {
        expire_timer();
        usleep(10000); 
    }
    return 0;
}

问一下，红黑树和跳表 多线程环境下应该怎么加锁？
整体加锁，互斥锁

简单的时间轮定时器方案

假设检测连接超时，根据心跳包，如果10s，没收到，就断开连接。
一般的做法：
map<fd, connect*> 每S轮询，检查所有连接是否超时。
收到心跳包就记录一下 时间戳，然后检测是否超时。
效率非常差 O（N）
如果有刚刚收到连接或者刚刚收到心跳包，没有必要检测

分治的办法来解决：
只检测快要过期的连接，不检测刚刚

数组 + 链表 hash数组大小该设置为10还是16？
为啥设置为16.

为啥不设置8？
为啥redis hash 2的N次方？

对数据取余的时候，设置为2的N次方的时候，速度最快。
开发经验值， 设置成16

redis hash 16 10000 15 & 1111
对16取余
即 该数 & 1111

#include <unistd.h>
#include <iostream>
#include <vector>
#include <list>
using namespace std;

class CTimerNode {
public:
    CTimerNode(int fd) : id(fd), ref(0) {}

    void Offline() {
        this->ref = 0;
    }

    bool TryKill() {
        if (this->ref == 0) return true;
        DecrRef();
        if (this->ref == 0) {
            cout << id << " is killed down" << endl;
            return true;
        }
        cout << id << " ref is " << ref << endl;
        return false;
    }

    void IncrRef() {
        this->ref++;
    }

protected:
    void DecrRef() {
        this->ref--;
    }

private:
    int ref;
    int id;
};

const int TW_SIZE = 16;
const int EXPIRE = 10;
const int TW_MASK = TW_SIZE - 1;
static size_t iRealTick = 0;
typedef list<CTimerNode*> TimeList;
typedef TimeList::iterator TimeListIter;
typedef vector<TimeList> TimeWheel;

void AddTimeout(TimeWheel &tw, CTimerNode *p) {
    if (p) {
        p->IncrRef();
        TimeList &le = tw[(iRealTick+EXPIRE) & TW_MASK];
        le.push_back(p);
    }
}

// 用来表示delay时间后调用 AddTimeout
void AddTimeoutDelay(TimeWheel &tw, CTimerNode *p, size_t delay) {
    if (p) {
        p->IncrRef();
        TimeList &le = tw[(iRealTick+EXPIRE+delay) & TW_MASK];
        le.push_back(p);
    }
}

void TimerShift(TimeWheel &tw)
{
    size_t tick = iRealTick;
    iRealTick++;
    TimeList &le = tw[tick & TW_MASK];
    TimeListIter iter = le.begin();
    for (; iter != le.end();iter++) {
        CTimerNode *p = *iter;
        if (p && p->TryKill()) {
            delete p;
        }
    }
    le.clear();
}

static time_t
current_time() {
	time_t t;
#if !defined(__APPLE__) || defined(AVAILABLE_MAC_OS_X_VERSION_10_12_AND_LATER)
	struct timespec ti;
	clock_gettime(CLOCK_MONOTONIC, &ti);
	t = (time_t)ti.tv_sec;
#else
	struct timeval tv;
	gettimeofday(&tv, NULL);
	t = (time_t)tv.tv_sec;
#endif
	return t;
}

int main ()
{
    TimeWheel tw(TW_SIZE);

    CTimerNode *p = new CTimerNode(10001);

    AddTimeout(tw, p);

    AddTimeoutDelay(tw, p, 5);

    time_t start = current_time();
    for (;;) {
        time_t now = current_time();
        if (now - start > 0) {
            for (int i=0; i<now-start; i++)
                TimerShift(tw);
            start = now;
            cout << "check timer shift " << iRealTick <<  endl;
        }
        usleep(2500);
    }

    return 0;
}

skynet中的时间轮定时器

// skynet 定时器的结构
struct timer_event {        //记录每个节点回复消息的信息，存储在节点的后面
    uint32_t handle;        //记录定位服务的编号
    int session;            //记录用于接收消息响应时，定位到是响应哪一条消息，由发送消息的服务生成
};

struct timer_node {  //时间节点
    struct timer_node *next;

    //保存该节点的timer_event消息回复事件的触发时间片为：添加时的时间片加上延时触发的时间
    uint32_t expire; 
};
struct link_list {  // 链表
    struct timer_node head;
    struct timer_node *tail;
};
struct timer {
    struct link_list near[256];  // 即将到来的定时器
    struct link_list t[4][64]; // 相对较遥远的定时器
    struct spinlock lock;
    uint32_t time;  // 当前的时间片，单位位1/100秒

	//系统的开始实时时间，从UTC1970-1-1 0:0:0开始计时，精确到秒
    uint64_t starttime;  

	//从开始时刻到现在的时长，精确到1/100秒
    uint64_t current;

	//系统启动时长，精确到1/100秒
    uint64_t current_point;
};

// 定时器的初始化
// skynet_start.c
// skynet 启动入口
void
skynet_start(struct skynet_config * config) {
    ...
    skynet_timer_init();
    ...
}
// skynet_timer.c
void
skynet_timer_init(void) {
    // 创建全局timer结构 TI
    TI  = timer_create_timer();
    uint32_t current = 0;

    //获取系统初始化时的UTC时间
    systime(&TI->starttime, &current);  

    TI->current = current;
    TI->current_point = gettime();
}

// 添加定时器
// TI为全局的定时器指针
static struct timer * TI = NULL; 
int skynet_timeout(uint32_t handle, int time, int session) {
    ...
    struct timer_event event;
    event.handle = handle;  // callback
    eveng.session = session;
    // 添加新的定时器节点
    timer_add(TI, &event, sizeof(event), time);
    return session;
}
// 添加新的定时器节点
static void timer_add(struct timer *T, void *arg, size_t sz, int time) {
    // 给timer_node指针分配空间，还需要分配timer_node + timer_event大小的空间，
    // 之后通过node + 1可获得timer_event数据
    struct timer_node *node = (struct timer_node *)skynet_malloc(sizeof(*node)+sz);
    memcpy(node+1,arg,sz);
    SPIN_LOCK(T);

    //记录回复的时间片
    node->expire=time+T->time;

    //添加节点到相应的链表
    add_node(T, node);
    SPIN_UNLOCK(T);
}

// 添加到定时器链表里，如果定时器的到期滴答数跟当前比较近(<2^8)，
// 表示即将触发定时器添加到T->near数组里
// 否则根据差值大小添加到对应的T->T[i]中
static void add_node(struct timer *T,struct timer_node *node) {
    uint32_t time=node->expire;            //回复的时间片
    uint32_t current_time=T->time;

    //TIME_NEAR_MASK=0xff，如果高24位相等则将该节点添加到底8位中对应的链表
    if ((time|TIME_NEAR_MASK)==(current_time|TIME_NEAR_MASK)) {        
        link(&T->near[time&TIME_NEAR_MASK],node);    //将该节点加入低8位对应的链表
    } else {
        int i;
        uint32_t mask=TIME_NEAR << TIME_LEVEL_SHIFT;        //TIME_NEAR=256，TIME_LEVEL_SHIFT=6初始化为低14位的掩码
        for (i=0;i<3;i++) {
            if ((time|(mask-1))==(current_time|(mask-1))) {
                break;
            }
            mask <<= TIME_LEVEL_SHIFT;    //往左移6位，即依次产生20位，26位，32位掩码
        }

        //将该节点加入高24位对应的链表 TIME_NEAR_SHIFT=8，TIME_LEVEL_MASK=0x3f
        link(&T->t[i][((time>>(TIME_NEAR_SHIFT + i*TIME_LEVEL_SHIFT)) & TIME_LEVEL_MASK)],node);    
    }
}


// 驱动方式  skynet启动时，会创建一个线程专门跑定时器，每帧(0.0025s)调用skynet_updatetime()
// skynet_start.c
static void * 
thread_timer(void *p) {
    struct monitor * m = p;
    skynet_initthread(THREAD_TIMER);
    for (;;) {
        skynet_updatetime();  // 调用timer_update
        skynet_socket_updatetime();
        CHECK_ABORT
        wakeup(m,m->count-1);
        usleep(2500);  // 2500微秒 = 0.0025s
        if (SIG) {
            signal_hup();
            SIG = 0;
        }
    }
    ...
}

// skynet_timer.c
void 
skynet_updatetime(void) {
    ...
    uint32_t diff = (uint32_t)(cp - TI->current_point); 
    TI->current_point = cp;
    TI->current += diff;
    // diff单位为0.01s
    for (i = 0; i < diff; i++){
        timer_update(TI);        
    }
}
static void
timer_update(struct timer *T) {
    SPIN_LOCK(T);
    timer_execute(T); // 检查T->near是否位空，有就处理到期定时器
    timer_shift(T);  // 时间片time++，移动高24位的链表
    timer_execute(T);
    SPIN_UNLOCK(T);
}
// 每帧从T->near中触发到期得定时器
static inline void
timer_execute(struct timer *T) {
  ...
}
// 遍历处理定时器链表中所有的定时器
static inline void
dispatch_list(struct timer_node *current) {
    ...
}
// 将高24位对应的4个6位的数组中的各个元素的链表往低位移
static void
timer_shift(struct timer *T) {
    ...
}
// 将level层的idx位置的定时器链表从当前位置删除，并重新add_node
static void move_list(struct timer *T, int level, int idx) {

}