文章目录
一、定时器按组织方式分类（按市面上的定时器设计举例）
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()
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 <vector>
#include <map>
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;
2）.cc文件
#include <unistd.h>
#if defined(__APPLE__)
#include <AvailabilityMacros.h>
#include <sys/time.h>
#include <mach/task.h>
#include <mach/mach.h>
#else
#include <time.h>
#endif
#include <iostream>
#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;
}
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_ */
2）定时器
#include <stdio.h>
#include <string.h>
#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 <stdio.h>
#include <stdint.h>
#include <unistd.h>
#include <stdlib.h>
#include <stddef.h>
#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"
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
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
2）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) {
//给节点配置最大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;//从前往后遍历
}
}
3）定时器事件
#include <stdio.h>
#include <stdint.h>
#include <unistd.h>
#include <stdlib.h>
#include <stddef.h>
#if defined(__APPLE__)
#include <AvailabilityMacros.h>
#include <sys/time.h>
#include <mach/task.h>
#include <mach/mach.h>
#else
#include <time.h>
#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;
}
4）多层时间轮
（1）总体思路
//1、创建8个线程
//2、初始化定时器
//3.增加定时器节点，延迟6s后改变推退出标签
//4、创建8个线程管理器管理线程，这个几个线程负责往链表数组添加节点
//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;
（3）代码
1)timewheel.h
#ifndef _MARK_TIMEWHEEL_
#define _MARK_TIMEWHEEL_
#include <stdint.h>
#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
2）tw-timer.c
#include <stdio.h>
#include <unistd.h>
#include <pthread.h>
#include <time.h>
#include <stdlib.h>
#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
3）timerwheel.c
#include "spinlock.h"
#include "timewheel.h"
#include <string.h>
#include <stddef.h>
#include <stdlib.h>
#if defined(__APPLE__)
#include <AvailabilityMacros.h>
#include <sys/time.h>
#include <mach/task.h>
#include <mach/mach.h>
#else
#include <time.h>
#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]);
}
}
}
5）epoll配合C++14、map（暂时略）
- 代码
6）内存池优化版本（游戏专用，只提供思路）
-
思路
1）节点存在内存池里面
2）时间轮的每个元素都是一个linked_list
3）时间轮的链表数组都放在一大块共享内存里面，涉及到的数据结构结构都是自定义的链表或map，不用stl
4）一般可以设定50ms为一个tick，1s有20个tick，然后按照tick去建立对应的Linked_list
5）节点的查找可以按照
linked_List的成员
拿到对象