一、定时器作用
定时器主要被用来执行定时任务，比如：游戏角色技能的冷却时间、优惠券的过期时间等。
就跟你设置的早上6点的闹钟一样，一到6点，闹钟响起，然后，然后当然是关掉继续睡啊~~
二、定时器数据结构选取
2.1 选取准则
- 有序性
- 高效地插入定时任务、删除定时任务
- 快速找到将要执行的定时任务
2.2 几种数据结构对比
- 有序链表：插入时间复杂度O(n)， 删除时间复杂度O(1)，取待执行定时任务间复杂度O(1)
- 小顶堆：插入时间复杂度O(logn)， 删除时间复杂度O(logn)，取待执行定时任务间复杂度O(1)
说明：小顶堆底层是二叉树，堆顶元素就是即将过期的任务，其他元素相对有序。 - 红黑树，插入时间复杂度O(logn)， 删除时间复杂度O(logn)，取待执行定时任务间复杂度O(logn)
说明：红黑树底层也是二叉树，与小顶堆不同的是，红黑树内部元素严格有序。 - 跳表，插入时间复杂度O(logn)， 删除时间复杂度O(logn)，取待执行定时任务间复杂度O(logn)
不同开源框架定时器实现方式不一，如，libuv采用最小堆来实现，nginx采用红黑树实现，redis采用跳表实现，linux内核和skynet采用时间轮算法实现等等。
三、定时器接口设计
- 创建定时器
- 添加定时任务
- 删除定时任务
- 执行到期任务
四、定时器代码具体实现
4.1 开源框架Nginx红黑树代码（站在巨人的肩膀上~~）
定时器头接口声明及实现，rbt-time.h
#ifndef _PANDA_RBT_ #define _PANDA_RBT_ #include <stdio.h> #include <stdint.h> // 整数 #include <unistd.h> // usleep #include <stdlib.h> // malloc 注意需要强转 #include <stddef.h> //offsetof #if defined(__APPLE__) #include <AvailabilityMacros.h> #include <sys/time.h> #include <mach/task.h> #include <mach/mach.h> #else #include <time.h> #endif #include "rbtree.h" static ngx_rbtree_t timer; static ngx_rbtree_node_t sentinel; // extern ngx_rbtree_t *timer; // extern ngx_rbtree_node_t *sentinel; typedef struct timer_entry_s timer_entry_t; // typedef void (*timer_handler_pt)(timer_entry_t *ev); typedef void (*timer_handler_pt)(timer_entry_t *ev); struct timer_entry_s { ngx_rbtree_node_t rbnode; 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; } ngx_rbtree_t * init_timer(); //创建定时器 void add_timer(int fd, timer_entry_t *te, uint32_t msec, timer_handler_pt func); //添加定时任务 void del_timer(timer_entry_t *te); //删除定时任务 int find_nearest_expire_timer(); // 找最近要触发的任务 void expire_timer(); //执行过期任务 #endif // _PANDA_RBT_
rbt-timer.c
#include <stdio.h> #include <string.h> #include <sys/epoll.h> #include "rbt-timer.h" ngx_rbtree_t * init_timer() { ngx_rbtree_init(&timer, &sentinel, ngx_rbtree_insert_timer_value); return &timer; } void add_timer(uint32_t msec, timer_handler_pt func) { timer_entry_t *te = malloc(sizeof(timer_entry_t)); memset(te, 0, sizeof(timer_entry_t)); te->handler = func; msec += current_time(); te->rbnode.data = msec; ngx_rbtree_insert(&timer, &te->rbnode); } void del_timer(timer_entry_t *te) { ngx_rbtree_delete(&timer, &te->rbnode); } int find_nearest_expire_timer() { ngx_rbtree_node_t *node; if (timer.root == &sentinel) { return 0; } node = ngx_rbtree_min(timer.root, timer.sentinel); int diff = (int)node->key - (int)current_time(); // printf("current diff = %d...\n", diff); return diff > 0 ? diff : 0; } 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, rbnode)); te->handler(te); ngx_rbtree_delete(&timer, &te->rbnode); } } void Timeout_Handler(timer_entry_t *te) { printf("Timeout_Handler time = %u\n", te->rbnode.data); return; } int main() { init_timer(); add_timer(10000, Timeout_Handler); add_timer(10010, Timeout_Handler); add_timer(12000, Timeout_Handler); int epfd = epoll_create(1); struct epoll_event events[512]; for (;;) { int nearest = find_nearest_expire_timer(); int n = epoll_wait(epfd, events, 512, nearest); int i = 0; for (; i < n; i++) { // } expire_timer(); } return 0; } #endif
红黑树节点及接口声明，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; typedef unsigned int ngx_rbtree_data_t; typedef int ngx_rbtree_data_int_t; // #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_int_t key; ngx_rbtree_data_int_t data; ngx_rbtree_node_t *left; ngx_rbtree_node_t *right; ngx_rbtree_node_t *parent; u_char color; }; 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_ */
rbtree.c
/* * 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 = nullptr; 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 = nullptr; node->right = nullptr; node->parent = nullptr; 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 = nullptr; node->right = nullptr; node->parent = nullptr; 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 nullptr; } if (node == parent->left) { return parent; } node = parent; } }
