• 服务器正文23：定时器设计与实现(8/7)

    文章目录

    一、定时器按组织方式分类（按市面上的定时器设计举例）

    1）时间序列（经过固定时间后触发或在某个时刻触发）

    • 红黑树
      nginx

    • 最小堆
      libevent（二叉树）、libev和go都是四叉树

    2）执行序列（按照固定频率周期性触发）

    • 时间轮
      netty、skynet、kafka、Linux内核延时任务

    3）应用方式

    • 单线程（红黑树或最小堆）
      nginx、libevent、libev

    • 多线程（但是时间轮并不一定是多线程专用的）
      skynet、kafka

    4）定时器API接口

    1)初始化定时器
void init_timer()

2)添加定时器
Node * add_timer(int expirer,callback cb)

3)删除定时器
bool del_timer(Node* node)

4)找到最近要发生的定时任务
Node* find_nearest_timer()

5)更新检测定时器
void update_timer()

6)//清除定时器
void clear_timer()

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17

    5）如何判断一个任务是否到期呢？

    1）轮询，每隔一个时间片去检查最近的任务是否到期。
    2）睡眠/唤醒，不停的查找deadline最近的任务最近的任务，到期就执行；否则sleep直到其到期。在sleep是，如果有任务被add或者delete，则deadline可能会被改变，那么线程就会被唤醒重新查找deadline

    二、定时器与其他模块的关系

    1）参与与网络模块协同处理

    2）基于事件驱动业务的开展

    3）除了协同网路处理，复用系统调用

    三、定时器实现

    0）前提数据结构评测

    • 链表
      时间复杂度O(n)
    • 二叉树
      由于可能会退化成链表，所以才有了平衡二叉树的诞生
    • 平衡二叉树
      ①在已经插入大量数据后，进行查找时，查找次数跟树的高度正相关
      ②为了让树扁平点，把二路改成多路，所以就有了B树和B+树
    • 红黑树
      引入了颜色，当插入或删除数据时，只需要进行O(1)次数的旋转以及变色就能保证基本的平衡，不需要像AVL树进行O(lgn)次数的旋转
    • 最小堆
      查找最小节点的事件复杂度是O(1)（对比map的优点）
    • 跳表
      对于增删查，时间复杂度为O (log2N)；最小节点为最左边节点，查找这个最小节点时间复杂度为O(1);对于增删查，时间复杂度为O(1) ；空间复杂度是 O(n)
      ​
    • 多层时间轮
      任务特别多建议用时间轮，由于map做了很多无效的检测，所以时间轮比map效率好

    1）最小堆

    • 代码

    1）头文件

    #pragma once

#include 
#include 
using namespace std;

typedef void (*TimerHandler) (struct TimerNode *node);

//定时器节点
struct TimerNode {
    int idx = 0;               //索引
    int id = 0;                //唯一ID
    unsigned int expire = 0;   //过期时间
    TimerHandler cb = NULL;    //回调函数
};

//定时器节点管理器
class MinHeapTimer {
public:
    MinHeapTimer() {
        _heap.clear();
        _map.clear();
    }
    static inline int Count() {
        return ++_count;
    }

    //增加定时器
    int AddTimer(uint32_t expire, TimerHandler cb);
    //删除定时器
    bool DelTimer(int id);
    //主循环处理定时器
    void ExpireTimer();

private:

    //堆排序比较函数
    inline bool _lessThan(int lhs, int rhs) {
        return _heap[lhs]->expire < _heap[rhs]->expire;
    }
    
    //堆排序相关函数

    //比较左右节点是否需要交换(小的过期时间放在左边)
    bool _shiftDown(int pos);

    //比较父节点和自己是否需要交换
    void _shiftUp(int pos);
    void _delNode(TimerNode *node);

private:
    vector<TimerNode*>  _heap;
    map<int, TimerNode*> _map;
    static int _count;              //节点个数
};

int MinHeapTimer::_count = 0;


    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23
    • 24
    • 25
    • 26
    • 27
    • 28
    • 29
    • 30
    • 31
    • 32
    • 33
    • 34
    • 35
    • 36
    • 37
    • 38
    • 39
    • 40
    • 41
    • 42
    • 43
    • 44
    • 45
    • 46
    • 47
    • 48
    • 49
    • 50
    • 51
    • 52
    • 53
    • 54
    • 55
    • 56
    • 57
    • 58

    2）.cc文件

    #include 
#if defined(__APPLE__)
#include 
#include 
#include 
#include 
#else
#include 
#endif

#include 

#include "minheap.h"

//返回当前时间戳
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;
}

int MinHeapTimer::AddTimer(uint32_t expire, TimerHandler cb) {
    int64_t timeout = current_time() + expire;
    TimerNode* node = new TimerNode;
    int id = Count();
    node->id = id;
    node->expire = timeout;
    node->cb = cb;
    node->idx = (int)_heap.size();
    _heap.push_back(node);
    _shiftUp((int)_heap.size() - 1);
    _map.insert(make_pair(id, node));
    return id;
}

bool MinHeapTimer::DelTimer(int id)
{
    auto iter = _map.find(id);
    if (iter == _map.end())
        return false;
    _delNode(iter->second);
    return true;
}

void MinHeapTimer::_delNode(TimerNode *node)
{
    int last = (int)_heap.size() - 1;
    int idx = node->idx;
    if (idx != last) {
        //与尾节点交换
        std::swap(_heap[idx], _heap[last]);
        _heap[idx]->idx = idx;

        //若作为左节点比右节点过期时间大，那就交换
        if (!_shiftDown(idx)) {
            _shiftUp(idx);
        }
    }
    _heap.pop_back();
    _map.erase(node->id);
    delete node;
}

void MinHeapTimer::ExpireTimer()
{
    if (_heap.empty()) return;
    uint32_t now = current_time();
    do {
        TimerNode* node = _heap.front();
        if (now < node->expire)
            break;
        for (int i = 0; i < _heap.size();  i++)
            std::cout << "touch    idx: " << _heap[i]->idx 
                << " id: " << _heap[i]->id << " expire: "
                << _heap[i]->expire << std::endl;
        if (node->cb) {
            node->cb(node);
        }
        _delNode(node);
    } while(!_heap.empty());
}

bool MinHeapTimer::_shiftDown(int pos){
    int last = (int)_heap.size()-1;
    int idx = pos;
    for (;;) {
        int left = 2 * idx + 1;
        //若左节点就是尾节点，则表示往上偏移，不是往下偏移
        if ((left >= last) || (left < 0)) {
            break;
        }
        int min = left; // left child
        int right = left + 1;//右节点下标 
        //判断左节点过期时间是否小于右节点过期时间
        if (right < last && !_lessThan(left, right)) {
            //左边过期时间大，右边节点过期时间小
            min = right; // right child
        }

        //判断右节点是否依旧大于左节点，真的有必要？
        if (!_lessThan(min, idx)) {
            break;
        }

        //交换左右节点
        std::swap(_heap[idx], _heap[min]);
        _heap[idx]->idx = idx;
        _heap[min]->idx = min;
        idx = min;
    }
    return idx > pos;
}


void MinHeapTimer::_shiftUp(int pos)
{
    for (;;) {
        int parent = (pos - 1) / 2; // parent node
        if (parent == pos || !_lessThan(pos, parent)) {
            break;
        }
        std::swap(_heap[parent], _heap[pos]);
        _heap[parent]->idx = parent;
        _heap[pos]->idx = pos;
        pos = parent;
    }
}


void print_hello(TimerNode *te) {
    std::cout <<  "hello world time = " << te->idx << "\t" << te->id << std::endl;
}

int main() {
    MinHeapTimer mht;
    mht.AddTimer(0, print_hello);
    mht.AddTimer(1000, print_hello);
    mht.AddTimer(7000, print_hello);
    mht.AddTimer(2000, print_hello);
    mht.AddTimer(9000, print_hello);
    mht.AddTimer(10000, print_hello);
    mht.AddTimer(6000, print_hello);
    mht.AddTimer(3000, print_hello);
    for (;;) {
        mht.ExpireTimer();
        usleep(10000);
    }
    return 0;
}


    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23
    • 24
    • 25
    • 26
    • 27
    • 28
    • 29
    • 30
    • 31
    • 32
    • 33
    • 34
    • 35
    • 36
    • 37
    • 38
    • 39
    • 40
    • 41
    • 42
    • 43
    • 44
    • 45
    • 46
    • 47
    • 48
    • 49
    • 50
    • 51
    • 52
    • 53
    • 54
    • 55
    • 56
    • 57
    • 58
    • 59
    • 60
    • 61
    • 62
    • 63
    • 64
    • 65
    • 66
    • 67
    • 68
    • 69
    • 70
    • 71
    • 72
    • 73
    • 74
    • 75
    • 76
    • 77
    • 78
    • 79
    • 80
    • 81
    • 82
    • 83
    • 84
    • 85
    • 86
    • 87
    • 88
    • 89
    • 90
    • 91
    • 92
    • 93
    • 94
    • 95
    • 96
    • 97
    • 98
    • 99
    • 100
    • 101
    • 102
    • 103
    • 104
    • 105
    • 106
    • 107
    • 108
    • 109
    • 110
    • 111
    • 112
    • 113
    • 114
    • 115
    • 116
    • 117
    • 118
    • 119
    • 120
    • 121
    • 122
    • 123
    • 124
    • 125
    • 126
    • 127
    • 128
    • 129
    • 130
    • 131
    • 132
    • 133
    • 134
    • 135
    • 136
    • 137
    • 138
    • 139
    • 140
    • 141
    • 142
    • 143
    • 144
    • 145
    • 146
    • 147
    • 148
    • 149
    • 150
    • 151
    • 152
    • 153
    • 154
    • 155
    • 156
    • 157
    • 158
    • 159
    • 160
    • 161

    2）红黑树

    • 特点
      1）红黑树是平衡二叉搜索树
      2）采用中序遍历，从begin到end遍历是有序的
      3）节点两边黑节点高度一致（不维护这个的话，会退化成单链表，查找变成O(n)）
      4）对于增删查，时间复杂度为O(log2N)，对于红黑树最小节点（也就是最左节点），时间复杂度为O(log2N)
      5）通过比较key维持有序的
      6）红黑树平衡高度看黑节点，不是严格的O(log2n)，有可能左右子树高度差很大
      7）根节点必为黑色
      8）所有叶子节点都是黑色
      9）不会有连续的红色节点

    • 代码

    1）红黑树

    /*
 * 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;
    }
}

/*
 * 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 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_ */


    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23
    • 24
    • 25
    • 26
    • 27
    • 28
    • 29
    • 30
    • 31
    • 32
    • 33
    • 34
    • 35
    • 36
    • 37
    • 38
    • 39
    • 40
    • 41
    • 42
    • 43
    • 44
    • 45
    • 46
    • 47
    • 48
    • 49
    • 50
    • 51
    • 52
    • 53
    • 54
    • 55
    • 56
    • 57
    • 58
    • 59
    • 60
    • 61
    • 62
    • 63
    • 64
    • 65
    • 66
    • 67
    • 68
    • 69
    • 70
    • 71
    • 72
    • 73
    • 74
    • 75
    • 76
    • 77
    • 78
    • 79
    • 80
    • 81
    • 82
    • 83
    • 84
    • 85
    • 86
    • 87
    • 88
    • 89
    • 90
    • 91
    • 92
    • 93
    • 94
    • 95
    • 96
    • 97
    • 98
    • 99
    • 100
    • 101
    • 102
    • 103
    • 104
    • 105
    • 106
    • 107
    • 108
    • 109
    • 110
    • 111
    • 112
    • 113
    • 114
    • 115
    • 116
    • 117
    • 118
    • 119
    • 120
    • 121
    • 122
    • 123
    • 124
    • 125
    • 126
    • 127
    • 128
    • 129
    • 130
    • 131
    • 132
    • 133
    • 134
    • 135
    • 136
    • 137
    • 138
    • 139
    • 140
    • 141
    • 142
    • 143
    • 144
    • 145
    • 146
    • 147
    • 148
    • 149
    • 150
    • 151
    • 152
    • 153
    • 154
    • 155
    • 156
    • 157
    • 158
    • 159
    • 160
    • 161
    • 162
    • 163
    • 164
    • 165
    • 166
    • 167
    • 168
    • 169
    • 170
    • 171
    • 172
    • 173
    • 174
    • 175
    • 176
    • 177
    • 178
    • 179
    • 180
    • 181
    • 182
    • 183
    • 184
    • 185
    • 186
    • 187
    • 188
    • 189
    • 190
    • 191
    • 192
    • 193
    • 194
    • 195
    • 196
    • 197
    • 198
    • 199
    • 200
    • 201
    • 202
    • 203
    • 204
    • 205
    • 206
    • 207
    • 208
    • 209
    • 210
    • 211
    • 212
    • 213
    • 214
    • 215
    • 216
    • 217
    • 218
    • 219
    • 220
    • 221
    • 222
    • 223
    • 224
    • 225
    • 226
    • 227
    • 228
    • 229
    • 230
    • 231
    • 232
    • 233
    • 234
    • 235
    • 236
    • 237
    • 238
    • 239
    • 240
    • 241
    • 242
    • 243
    • 244
    • 245
    • 246
    • 247
    • 248
    • 249
    • 250
    • 251
    • 252
    • 253
    • 254
    • 255
    • 256
    • 257
    • 258
    • 259
    • 260
    • 261
    • 262
    • 263
    • 264
    • 265
    • 266
    • 267
    • 268
    • 269
    • 270
    • 271
    • 272
    • 273
    • 274
    • 275
    • 276
    • 277
    • 278
    • 279
    • 280
    • 281
    • 282
    • 283
    • 284
    • 285
    • 286
    • 287
    • 288
    • 289
    • 290
    • 291
    • 292
    • 293
    • 294
    • 295
    • 296
    • 297
    • 298
    • 299
    • 300
    • 301
    • 302
    • 303
    • 304
    • 305
    • 306
    • 307
    • 308
    • 309
    • 310
    • 311
    • 312
    • 313
    • 314
    • 315
    • 316
    • 317
    • 318
    • 319
    • 320
    • 321
    • 322
    • 323
    • 324
    • 325
    • 326
    • 327
    • 328
    • 329
    • 330
    • 331
    • 332
    • 333
    • 334
    • 335
    • 336
    • 337
    • 338
    • 339
    • 340
    • 341
    • 342
    • 343
    • 344
    • 345
    • 346
    • 347
    • 348
    • 349
    • 350
    • 351
    • 352
    • 353
    • 354
    • 355
    • 356
    • 357
    • 358
    • 359
    • 360
    • 361
    • 362
    • 363
    • 364
    • 365
    • 366
    • 367
    • 368
    • 369
    • 370
    • 371
    • 372
    • 373
    • 374
    • 375
    • 376
    • 377
    • 378
    • 379
    • 380
    • 381
    • 382
    • 383
    • 384
    • 385
    • 386
    • 387
    • 388
    • 389
    • 390
    • 391
    • 392
    • 393
    • 394
    • 395
    • 396
    • 397
    • 398
    • 399
    • 400
    • 401
    • 402
    • 403
    • 404
    • 405
    • 406
    • 407
    • 408
    • 409
    • 410
    • 411
    • 412
    • 413
    • 414
    • 415
    • 416
    • 417
    • 418
    • 419
    • 420
    • 421
    • 422
    • 423
    • 424
    • 425
    • 426
    • 427
    • 428
    • 429
    • 430
    • 431
    • 432
    • 433
    • 434
    • 435
    • 436
    • 437
    • 438
    • 439
    • 440
    • 441
    • 442
    • 443
    • 444
    • 445
    • 446
    • 447
    • 448
    • 449
    • 450
    • 451
    • 452
    • 453
    • 454
    • 455
    • 456
    • 457
    • 458
    • 459
    • 460
    • 461
    • 462
    • 463
    • 464
    • 465
    • 466
    • 467
    • 468
    • 469
    • 470
    • 471
    • 472
    • 473
    • 474
    • 475
    • 476
    • 477
    • 478
    • 479
    • 480
    • 481
    • 482
    • 483
    • 484
    • 485
    • 486
    • 487
    • 488
    • 489
    • 490
    • 491
    • 492
    • 493

    2）定时器

    #include 
#include 
#include "rbt-timer.h"

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;
}

#ifndef _MARK_RBT_
#define _MARK_RBT_

#include 
#include 
#include 
#include 
#include 

#if defined(__APPLE__)
#include 
#include 
#include 
#include 
#else
#include 
#endif

#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;
}

int init_timer() {
    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);
    }
}

#endif

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23
    • 24
    • 25
    • 26
    • 27
    • 28
    • 29
    • 30
    • 31
    • 32
    • 33
    • 34
    • 35
    • 36
    • 37
    • 38
    • 39
    • 40
    • 41
    • 42
    • 43
    • 44
    • 45
    • 46
    • 47
    • 48
    • 49
    • 50
    • 51
    • 52
    • 53
    • 54
    • 55
    • 56
    • 57
    • 58
    • 59
    • 60
    • 61
    • 62
    • 63
    • 64
    • 65
    • 66
    • 67
    • 68
    • 69
    • 70
    • 71
    • 72
    • 73
    • 74
    • 75
    • 76
    • 77
    • 78
    • 79
    • 80
    • 81
    • 82
    • 83
    • 84
    • 85
    • 86
    • 87
    • 88
    • 89
    • 90
    • 91
    • 92
    • 93
    • 94
    • 95
    • 96
    • 97
    • 98
    • 99
    • 100
    • 101
    • 102
    • 103
    • 104
    • 105
    • 106
    • 107
    • 108
    • 109

    3）跳表

    • 代码
      1）skiplist.h
    #ifndef _MARK_SKIPLIST_
#define _MARK_SKIPLIST_

/* ZSETs use a specialized version of Skiplists */
#define ZSKIPLIST_MAXLEVEL 32 /* Should be enough for 2^64 elements */
#define ZSKIPLIST_P 0.25      /* Skiplist P = 1/2 */

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; 从后向前遍历时使用*/

    //用一个数组的结构存放next指针
    struct zskiplistLevel {
        struct zskiplistNode *forward; 
        /* unsigned long span; 这个存储的level间节点的个数，在定时器中并不需要*/ 
    } level[];
};

//比如说原始链表【0】A->B->C->D->E，一级索引是A->C->E->G->,二级索引是A->E->I,三级索引是A->E
//节点A.level[0].forward = 节点B  ，这是原始链表
//节点A.level[1].forward = 节点C  ，这是一级索引
//节点A.level[2].forward = 节点E  ，这是二级索引
//节点A.level[3].forward = 节点I  ，这是三级索引

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);                       //打印跳表节点信息
#endif


    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23
    • 24
    • 25
    • 26
    • 27
    • 28
    • 29
    • 30
    • 31
    • 32
    • 33
    • 34
    • 35
    • 36
    • 37
    • 38
    • 39
    • 40
    • 41
    • 42
    • 43
    • 44
    • 45
    • 46
    • 47
    • 48

    2）skiplist.c

    #include 
#include 
#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) {
    //给节点配置最大level的空间
    zskiplistNode *zn =
        malloc(sizeof(*zn)+level*sizeof(struct zskiplistLevel));
    zn->score = score;   //头结点过期时间是0
    zn->handler = func;  //头结点默认绑定函数是defaultHandler
    return zn;
}

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

    zsl = (zskiplist *)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;//头结点的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;
#if defined(__APPLE__)
    while ((arc4random()&0xFFFF) < (ZSKIPLIST_P * 0xFFFF))
#else
    //ZSKIPLIST_P * 0xFFFF = 16384
    //rand()&0xFFFF  取低4位16进制数
    //小于1/4的65536就继续
    //原始链表提取到一级索引概率1/4,原始链表提取到二级索引的概率是1/16
    while ((rand()&0xFFFF) < (ZSKIPLIST_P * 0xFFFF))
#endif
        level += 1;
    //这里level表示需要在第一层到第k层添加索引
    //比如说随机到2，只需要在第一层和第二层插入索引
    return (level<ZSKIPLIST_MAXLEVEL) ? level : ZSKIPLIST_MAXLEVEL;
}

/*
score  过期时间
*/
zskiplistNode *zslInsert(zskiplist *zsl, unsigned long score, handler_pt func) {
    zskiplistNode *update[ZSKIPLIST_MAXLEVEL] = {0}; 
    zskiplistNode *x = NULL;
    int i = 0;
    int level = 0;

    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;//插第一个节点时，这个数组的0号元素是头结点，其他不做改变
    }

    //随机一个level层数出来
    level = zslRandomLevel();
    printf("zskiplist add node level = %d\n", level);
    
    //高层跳表链表在上面，越底层越接近原始链表
    //如果随机出来的level层数比现在跳表结构的大，那就把数组用头结点填满
    //并更新最大level层
    if (level > zsl->level) {
        for (i = zsl->level; i < level; i++) {
            update[i] = zsl->header;
        }
        zsl->level = level;
    }

    //根据过期时间、回调函数、这个节点的层数 来 创建新节点
    x = zslCreateNode(level,score,func);

    //从第一层到第level层里面都加上这个节点
    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 = NULL;
    x = zsl->header;
    return x->level[0].forward;
}

void zslDeleteHead(zskiplist *zsl) {
    zskiplistNode *update[ZSKIPLIST_MAXLEVEL] = {0};
    zskiplistNode *x = zslMin(zsl);
    if (!x) return;
    int i = 0;
    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 = 0;
    for (i = 0; i < zsl->level; i++) {
        //若前置节点的后面有要删除的节点，那么就更新forward指针，把该点从单链表删除
        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) {
    //数组update专门记录前置节点  
    zskiplistNode *update[ZSKIPLIST_MAXLEVEL] = 0;
    zskiplistNode *x = NULL;
    int i = 0;

    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;

    //如果在原始链表找到该节点(因为前面已经替换到首节点了)
    //传入参数x就是要删除的节点
    if (x && zn->score == x->score) {
        zslDeleteNode(zsl, x, update);
        free(x);
    }
}

//只打印第一层的？
void zslPrint(zskiplist *zsl) {
    zskiplistNode *x = NULL;
    x = zsl->header;
    x = x->level[0].forward;
    printf("start print skiplist level = %d\n", zsl->level);
    int i = 0;
    for (i = 0; i < zsl->length; ++i)
    {
        printf("skiplist ele %d: score = %lu\n", i+1, x->score);
        x = x->level[0].forward;//从前往后遍历
    }
}


    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23
    • 24
    • 25
    • 26
    • 27
    • 28
    • 29
    • 30
    • 31
    • 32
    • 33
    • 34
    • 35
    • 36
    • 37
    • 38
    • 39
    • 40
    • 41
    • 42
    • 43
    • 44
    • 45
    • 46
    • 47
    • 48
    • 49
    • 50
    • 51
    • 52
    • 53
    • 54
    • 55
    • 56
    • 57
    • 58
    • 59
    • 60
    • 61
    • 62
    • 63
    • 64
    • 65
    • 66
    • 67
    • 68
    • 69
    • 70
    • 71
    • 72
    • 73
    • 74
    • 75
    • 76
    • 77
    • 78
    • 79
    • 80
    • 81
    • 82
    • 83
    • 84
    • 85
    • 86
    • 87
    • 88
    • 89
    • 90
    • 91
    • 92
    • 93
    • 94
    • 95
    • 96
    • 97
    • 98
    • 99
    • 100
    • 101
    • 102
    • 103
    • 104
    • 105
    • 106
    • 107
    • 108
    • 109
    • 110
    • 111
    • 112
    • 113
    • 114
    • 115
    • 116
    • 117
    • 118
    • 119
    • 120
    • 121
    • 122
    • 123
    • 124
    • 125
    • 126
    • 127
    • 128
    • 129
    • 130
    • 131
    • 132
    • 133
    • 134
    • 135
    • 136
    • 137
    • 138
    • 139
    • 140
    • 141
    • 142
    • 143
    • 144
    • 145
    • 146
    • 147
    • 148
    • 149
    • 150
    • 151
    • 152
    • 153
    • 154
    • 155
    • 156
    • 157
    • 158
    • 159
    • 160
    • 161
    • 162
    • 163
    • 164
    • 165
    • 166
    • 167
    • 168
    • 169
    • 170
    • 171
    • 172
    • 173
    • 174
    • 175
    • 176
    • 177
    • 178
    • 179
    • 180
    • 181
    • 182
    • 183
    • 184
    • 185
    • 186

    3）定时器事件

    #include 
#include 
#include 
#include 
#include 
#if defined(__APPLE__)
#include 
#include 
#include 
#include 
#else
#include 
#endif
#include "skiplist.h"

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;
}

zskiplist *init_timer() {
    return zslCreate();
}

zskiplistNode *add_timer(zskiplist *zsl, uint32_t msec, handler_pt func) {
    msec += current_time();
    printf("add_timer expire at msec = %u\n", msec);
    return zslInsert(zsl, msec, func);
}

void del_timer(zskiplist *zsl, zskiplistNode *zn) {
    zslDelete(zsl, zn);
}

void expire_timer(zskiplist *zsl) {
    zskiplistNode *x = NULL;
    uint32_t now = current_time();
    for (;;) {
        x = zslMin(zsl);
        if (!x) break;
        if (x->score > now) break;
        printf("touch timer expire time=%lu, now = %u\n", x->score, now);
        x->handler(x);
        zslDeleteHead(zsl);
    }
}

void print_hello(zskiplistNode *zn) {
    printf("hello world time = %lu\n", zn->score);
}

int main()
{
    //1.创建跳表和头结点
    zskiplist *zsl = init_timer();
    
    //2.插入定时器
    add_timer(zsl, 3010, print_hello);
    add_timer(zsl, 3004, print_hello);
    
    zskiplistNode *zn = add_timer(zsl, 3005, print_hello);
    del_timer(zsl, zn);

    add_timer(zsl, 3008, print_hello);
    add_timer(zsl, 3003, print_hello);
    // zslPrint(zsl);


    for (;;) {
        expire_timer(zsl);
        usleep(10000);
    }
    return 0;
}


    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23
    • 24
    • 25
    • 26
    • 27
    • 28
    • 29
    • 30
    • 31
    • 32
    • 33
    • 34
    • 35
    • 36
    • 37
    • 38
    • 39
    • 40
    • 41
    • 42
    • 43
    • 44
    • 45
    • 46
    • 47
    • 48
    • 49
    • 50
    • 51
    • 52
    • 53
    • 54
    • 55
    • 56
    • 57
    • 58
    • 59
    • 60
    • 61
    • 62
    • 63
    • 64
    • 65
    • 66
    • 67
    • 68
    • 69
    • 70
    • 71
    • 72
    • 73
    • 74
    • 75
    • 76
    • 77
    • 78
    • 79
    • 80
    • 81
    • 82
    • 83
    • 84
    • 85
    • 86
    • 87

    4）多层时间轮

    （1）总体思路

        //1、创建8个线程
    //2、初始化定时器
    //3.增加定时器节点，延迟6s后改变推退出标签
    //4、创建8个线程管理器管理线程，这个几个线程负责往链表数组添加节点
    //5、循环遍历数组，执行要过期节点和将高维要过期节点放到低维数组链表里面
    //6、回收线程等其他资源

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6

    （2）基础数据结构

    struct timer_node {
	struct timer_node *next;
	uint32_t expire;			//过期时间
    handler_pt callback;		//回调函数
    uint8_t cancel;				//表示这个节点是否取消执行，是就是1
	int id; 					//线程索引，从1开始
};

//链表
typedef struct link_list {
	timer_node_t head;   	//节点
	timer_node_t *tail;   	//后续节点
}link_list_t;

//定时器管理器
typedef struct timer {
	link_list_t near[TIME_NEAR];
	link_list_t t[4][TIME_LEVEL];
	struct spinlock lock;			//锁
	uint32_t time;					
	uint64_t current;
	uint64_t current_point;  		//记录当前时间
}s_timer_t;



    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23
    • 24
    • 25

    （3）代码

    1)timewheel.h

    #ifndef _MARK_TIMEWHEEL_
#define _MARK_TIMEWHEEL_

#include 

#define TIME_NEAR_SHIFT 8
#define TIME_NEAR (1 << TIME_NEAR_SHIFT)  	//
#define TIME_LEVEL_SHIFT 6
#define TIME_LEVEL (1 << TIME_LEVEL_SHIFT)
#define TIME_NEAR_MASK (TIME_NEAR-1)		//
#define TIME_LEVEL_MASK (TIME_LEVEL-1)		//

typedef struct timer_node timer_node_t;
typedef void (*handler_pt) (struct timer_node *node);

struct timer_node {
	struct timer_node *next;
	uint32_t expire;			//过期时间
    handler_pt callback;		//回调函数
    uint8_t cancel;				//表示这个节点是否取消执行，是就是1
	int id; 					//线程索引，从1开始
};

timer_node_t* add_timer(int time, handler_pt func, int threadid);

void expire_timer(void);

void del_timer(timer_node_t* node);

void init_timer(void);

void clear_timer();

#endif

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23
    • 24
    • 25
    • 26
    • 27
    • 28
    • 29
    • 30
    • 31
    • 32
    • 33
    • 34

    2）tw-timer.c

    #include 
#include 

#include 
#include 
#include 
#include "timewheel.h"

struct context {
	int quit;
    int thread;
};

struct thread_param {
	struct context *ctx;
	int id;
};

static struct context ctx = {0};

void do_timer(timer_node_t *node) {
    printf("timer expired:%d - thread-id:%d\n", node->expire, node->id);
}

//线程执行函数
void* thread_worker(void *p) {
	struct thread_param *tp = p;
	int id = tp->id;                            //表示是第几个线程
    struct context *ctx = tp->ctx;              //
	while (!ctx->quit) {
        int expire = rand() % 200;              //随机过期时间
        add_timer(expire, do_timer, id);        //把随机出来的过期时间作为节点加入定时器
        usleep(expire*(10-1)*1000);
    }
    printf("thread_worker:%d exit!\n", id);
    return NULL;
}

void do_quit(timer_node_t * node) {
    ctx.quit = 1;
}

int main() {
    srand(time(NULL));
    ctx.thread = 8;
    //1、创建8个线程
    pthread_t pid[ctx.thread];

    //2、初始化定时器
    init_timer();

    //3.增加定时器节点，延迟6s后改变推退出标签
    add_timer(6000, do_quit, 100);

    //4、创建8个线程管理器管理线程，这个几个线程负责往链表数组添加节点
    struct thread_param task_thread_p[ctx.thread];
    int i;
    for (i = 0; i < ctx.thread; i++) {
        task_thread_p[i].id = i;
        task_thread_p[i].ctx = &ctx;
        if (pthread_create(&pid[i], NULL, thread_worker, &task_thread_p[i])) {
            fprintf(stderr, "create thread failed\n");
            exit(1);
        }
    }

    //5、循环遍历数组，执行要过期节点和将高维要过期节点放到低维数组链表里面
    while (!ctx.quit) {
        expire_timer();
        usleep(2500);
    }

    //6、回收线程
    clear_timer();
    for (i = 0; i < ctx.thread; i++) {
		pthread_join(pid[i], NULL);
    }
    printf("all thread is closed\n");
    return 0;
}

// gcc tw-timer.c timewheel.c -o tw -I./ -lpthread 

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23
    • 24
    • 25
    • 26
    • 27
    • 28
    • 29
    • 30
    • 31
    • 32
    • 33
    • 34
    • 35
    • 36
    • 37
    • 38
    • 39
    • 40
    • 41
    • 42
    • 43
    • 44
    • 45
    • 46
    • 47
    • 48
    • 49
    • 50
    • 51
    • 52
    • 53
    • 54
    • 55
    • 56
    • 57
    • 58
    • 59
    • 60
    • 61
    • 62
    • 63
    • 64
    • 65
    • 66
    • 67
    • 68
    • 69
    • 70
    • 71
    • 72
    • 73
    • 74
    • 75
    • 76
    • 77
    • 78
    • 79
    • 80
    • 81
    • 82

    3）timerwheel.c

    #include "spinlock.h"
#include "timewheel.h"
#include 
#include 
#include 

#if defined(__APPLE__)
#include 
#include 
#include 
#include 
#else
#include 
#endif

typedef struct link_list {
	timer_node_t head;   	//节点
	timer_node_t *tail;   	//后续节点
}link_list_t;

typedef struct timer {
	link_list_t near[TIME_NEAR];
	link_list_t t[4][TIME_LEVEL];
	struct spinlock lock;
	uint32_t time;					//10ms?
	uint64_t current;
	uint64_t current_point;  		//记录当前时间
}s_timer_t;

static s_timer_t * TI = NULL;     	//静态的定时器管理器

timer_node_t *
link_clear(link_list_t *list) {
	//返回当前列表的首个元素，然后将当前列表清空
	timer_node_t * ret = list->head.next;
	list->head.next = 0;
	list->tail = &(list->head);

	return ret;
}

//尾插节点到链表里面
void
link(link_list_t *list, timer_node_t *node) {
	list->tail->next = node;
	list->tail = node;
	node->next=0;
}

void
add_node(s_timer_t *T, timer_node_t *node) {
	uint32_t time=node->expire;
	uint32_t current_time=T->time;
	uint32_t msec = time - current_time;
	if (msec < TIME_NEAR) { //[0, 0x100)
		link(&T->near[time&TIME_NEAR_MASK],node);
	} else if (msec < (1 << (TIME_NEAR_SHIFT+TIME_LEVEL_SHIFT))) {//[0x100, 0x4000)
		link(&T->t[0][((time>>TIME_NEAR_SHIFT) & TIME_LEVEL_MASK)],node);	
	} else if (msec < (1 << (TIME_NEAR_SHIFT+2*TIME_LEVEL_SHIFT))) {//[0x4000, 0x100000)
		link(&T->t[1][((time>>(TIME_NEAR_SHIFT + TIME_LEVEL_SHIFT)) & TIME_LEVEL_MASK)],node);	
	} else if (msec < (1 << (TIME_NEAR_SHIFT+3*TIME_LEVEL_SHIFT))) {//[0x100000, 0x4000000)
		link(&T->t[2][((time>>(TIME_NEAR_SHIFT + 2*TIME_LEVEL_SHIFT)) & TIME_LEVEL_MASK)],node);	
	} else {//[0x4000000, 0xffffffff]
		link(&T->t[3][((time>>(TIME_NEAR_SHIFT + 3*TIME_LEVEL_SHIFT)) & TIME_LEVEL_MASK)],node);	
	}
}

// 约定 time 为 10ms 为单位，若传进来 1000 则是10秒
timer_node_t*
add_timer(int time, handler_pt func, int threadid) {
	//初始化节点
	timer_node_t *node = (timer_node_t *)malloc(sizeof(*node));
	spinlock_lock(&TI->lock);
	node->expire = time+TI->time;  	//更新过期时间
	node->callback = func;			//回调函数
	node->id = threadid;			//线程索引，从1开始
	if (time <= 0) {				//--若不开延迟，即直接执行回调函数
		node->callback(node);		//执行回调函数
		spinlock_unlock(&TI->lock);	//解锁
		free(node);					//释放节点
		return NULL;
	}
	add_node(TI, node);				//增加节点
	spinlock_unlock(&TI->lock);		//解锁(对共享资源操作)
	return node;
}

void
move_list(s_timer_t *T, int level, int idx) {
	timer_node_t *current = link_clear(&T->t[level][idx]);
	while (current) {
		timer_node_t *temp=current->next;
		add_node(T,current);
		current=temp;
	}
}

//将t这个双重数组的节点按照过期时间重新挂到新的链表上去
void
timer_shift(s_timer_t *T) {
	int mask = TIME_NEAR;
	uint32_t ct = ++T->time;//将time自增
	if (ct == 0) {
		move_list(T, 3, 0);
	} else {
		// ct / 256
		uint32_t time = ct >> TIME_NEAR_SHIFT;
		int i=0;
		// ct % 256 == 0
		while ((ct & (mask-1))==0) {
			int idx=time & TIME_LEVEL_MASK;
			if (idx!=0) {
				move_list(T, i, idx);
				break;				
			}
			mask <<= TIME_LEVEL_SHIFT;
			time >>= TIME_LEVEL_SHIFT;
			++i;
		}
	}
}

//执行这个节点
void
dispatch_list(timer_node_t *current) {
	do {
		timer_node_t * temp = current;
		current=current->next;
        if (temp->cancel == 0)
            temp->callback(temp);
		free(temp);
	} while (current);
}

//执行定时器节点
void
timer_execute(s_timer_t *T) {
	int idx = T->time & TIME_NEAR_MASK;
	
	while (T->near[idx].head.next) {
		timer_node_t *current = link_clear(&T->near[idx]);
		spinlock_unlock(&T->lock);
		dispatch_list(current);
		spinlock_lock(&T->lock);
	}
}

void 
timer_update(s_timer_t *T) {
	spinlock_lock(&T->lock);
	timer_execute(T);				//执行最近要过期的节点
	timer_shift(T);					//将高级链表按照过期时间挂到near数组中去
	timer_execute(T);				//执行最近要过期的节点
	spinlock_unlock(&T->lock);
}

void
del_timer(timer_node_t *node) {
    node->cancel = 1;
}

s_timer_t *
timer_create_timer() {
	s_timer_t *r=(s_timer_t *)malloc(sizeof(s_timer_t));
	memset(r,0,sizeof(*r));
	int i = 0;
	int j = 0;
	for (i=0;i<TIME_NEAR;i++) {
		link_clear(&r->near[i]);
	}

	//将t这个双重数组清空
	for (i=0;i<4;i++) {
		for (j=0;j<TIME_LEVEL;j++) {
			link_clear(&r->t[i][j]);
		}
	}

	//初始化锁
	spinlock_init(&r->lock);

	//记录当前的定时器？？？
	r->current = 0;
	return r;
}

uint64_t
gettime() {
	uint64_t t;
#if !defined(__APPLE__) || defined(AVAILABLE_MAC_OS_X_VERSION_10_12_AND_LATER)
	struct timespec ti;
	clock_gettime(CLOCK_MONOTONIC, &ti);
	t = (uint64_t)ti.tv_sec * 100;
	t += ti.tv_nsec / 10000000;
#else
	struct timeval tv;
	gettimeofday(&tv, NULL);
	t = (uint64_t)tv.tv_sec * 100;
	t += tv.tv_usec / 10000;
#endif
	return t;
}

//
void
expire_timer(void) {
	uint64_t cp = gettime();
	if (cp != TI->current_point) {
		uint32_t diff = (uint32_t)(cp - TI->current_point);
		TI->current_point = cp;
		int i;
		for (i=0; i<diff; i++) {
			timer_update(TI);
		}
	}
}

void 
init_timer(void) {
	TI = timer_create_timer();
	TI->current_point = gettime();
}

void
clear_timer() {
	int i,j;
	for (i=0;i<TIME_NEAR;i++) {
		link_list_t * list = &TI->near[i];
		timer_node_t* current = list->head.next;
		while(current) {
			timer_node_t * temp = current;
			current = current->next;
			free(temp);
		}
		link_clear(&TI->near[i]);
	}
	for (i=0;i<4;i++) {
		for (j=0;j<TIME_LEVEL;j++) {
			link_list_t * list = &TI->t[i][j];
			timer_node_t* current = list->head.next;
			while (current) {
				timer_node_t * temp = current;
				current = current->next;
				free(temp);
			}
			link_clear(&TI->t[i][j]);
		}
	}
}


    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23
    • 24
    • 25
    • 26
    • 27
    • 28
    • 29
    • 30
    • 31
    • 32
    • 33
    • 34
    • 35
    • 36
    • 37
    • 38
    • 39
    • 40
    • 41
    • 42
    • 43
    • 44
    • 45
    • 46
    • 47
    • 48
    • 49
    • 50
    • 51
    • 52
    • 53
    • 54
    • 55
    • 56
    • 57
    • 58
    • 59
    • 60
    • 61
    • 62
    • 63
    • 64
    • 65
    • 66
    • 67
    • 68
    • 69
    • 70
    • 71
    • 72
    • 73
    • 74
    • 75
    • 76
    • 77
    • 78
    • 79
    • 80
    • 81
    • 82
    • 83
    • 84
    • 85
    • 86
    • 87
    • 88
    • 89
    • 90
    • 91
    • 92
    • 93
    • 94
    • 95
    • 96
    • 97
    • 98
    • 99
    • 100
    • 101
    • 102
    • 103
    • 104
    • 105
    • 106
    • 107
    • 108
    • 109
    • 110
    • 111
    • 112
    • 113
    • 114
    • 115
    • 116
    • 117
    • 118
    • 119
    • 120
    • 121
    • 122
    • 123
    • 124
    • 125
    • 126
    • 127
    • 128
    • 129
    • 130
    • 131
    • 132
    • 133
    • 134
    • 135
    • 136
    • 137
    • 138
    • 139
    • 140
    • 141
    • 142
    • 143
    • 144
    • 145
    • 146
    • 147
    • 148
    • 149
    • 150
    • 151
    • 152
    • 153
    • 154
    • 155
    • 156
    • 157
    • 158
    • 159
    • 160
    • 161
    • 162
    • 163
    • 164
    • 165
    • 166
    • 167
    • 168
    • 169
    • 170
    • 171
    • 172
    • 173
    • 174
    • 175
    • 176
    • 177
    • 178
    • 179
    • 180
    • 181
    • 182
    • 183
    • 184
    • 185
    • 186
    • 187
    • 188
    • 189
    • 190
    • 191
    • 192
    • 193
    • 194
    • 195
    • 196
    • 197
    • 198
    • 199
    • 200
    • 201
    • 202
    • 203
    • 204
    • 205
    • 206
    • 207
    • 208
    • 209
    • 210
    • 211
    • 212
    • 213
    • 214
    • 215
    • 216
    • 217
    • 218
    • 219
    • 220
    • 221
    • 222
    • 223
    • 224
    • 225
    • 226
    • 227
    • 228
    • 229
    • 230
    • 231
    • 232
    • 233
    • 234
    • 235
    • 236
    • 237
    • 238
    • 239
    • 240
    • 241
    • 242
    • 243
    • 244
    • 245
    • 246
    • 247
    • 248
    • 249
    • 250

    5）epoll配合C++14、map（暂时略）

    • 代码
    

    • 1

    6）内存池优化版本（游戏专用，只提供思路）

    • 思路
      1）节点存在内存池里面
      2）时间轮的每个元素都是一个linked_list
      3）时间轮的链表数组都放在一大块共享内存里面，涉及到的数据结构结构都是自定义的链表或map，不用stl
      4）一般可以设定50ms为一个tick，1s有20个tick，然后按照tick去建立对应的Linked_list
      5）节点的查找可以按照linked_List的成员拿到对象
  • 相关阅读:
    Linux: network: demux 解释
    java基于springboot+vue+elementui的校园疫情防控系统 前后端分离
    【教学类-38】A4红纸-国旗灯笼（庆祝中华人民共和国成立74周年）
    面向过程 VS 面向对象
    Vue 路由使用
    el-select与el-tree的联动，切换勾选保存回显功能（全部代码）
    凭着这份java面试一战到底，直接碾压面试官
    Spring Boot和Spring MVC的区别
    中断和异常理论详解，Linux操作系统原理与应用
    Matlab中如何设置Scope
  • 原文地址：https://blog.csdn.net/weixin_43679037/article/details/126194105