• 定时器设计--红黑树

    目录

    1. 定时器触发方式

    1.1 网络事件和定时事件在一个线程中处理

    1.2 网络事件和定时事件在不同线程中处理；

    2. 定时器设计

    2.1 接口设计

    2.2 数据结构设计

    2.3 整体思路

    2.3.1 获取当前时间的接口

    2.3.2 相同触发时间的定时任务处理

    2.3.3 完整代码

    2.3.4 运行结果

    3. 扩展知识

    3.1 std::function

    3.2 lambda表达式

    3.3 结构体的构造函数

    3.4 using的用法

    1. 定时器触发方式

    1.1 网络事件和定时事件在一个线程中处理

    例如：nginx、redis、memcached；

            定时器通常是与网络组件一起工作，⽹络事件和时间事件在⼀个线程当中配合使⽤；例如nginx、redis，我们将epoll_wait的第四个参数timeout设置为最近要触发的定时器的时间差来触发定时器，来执行任务。

    1. // 网络事件和定时事件在一个线程中处理
    2. while (!quit) {
    3. 	int timeout = get_nearest_timer() - now();
    4. 	if (timeout < 0) timeout = -1;
    5. 	int nevent = epoll_wait(epfd, ev, nev,timeout);
    6. 	for (int i=0; i<nevent; i++) {
    7. 		// ... 处理网络事件
    8. 	}
    9. 	// 处理定时事件
    10. 	update_timer();
    11. }

    1.2 网络事件和定时事件在不同线程中处理；

    例如：skynet，...；在单独的线程来检测定时器。通过usleep来触发定时器，定时任务的执行通过信号或者插入执行队列让其他线程执行。

    1. // 网络事件和定时事件在不同线程中处理
    2. void * thread_timer(void *thread_param) {
    3. 	init_timer();
    4. 	while (!quit) {
    5. 		update_timer();
    6. 		sleep(t);
    7. 	}
    8. 	clear_timer();
    9. 	return NULL;
    10. }
    11. pthread_create(&pid, NULL, thread_timer,&thread_param);

    2. 定时器设计

    2.1 接口设计

    1. // 初始化定时器
    2. void init_timer();
    3. // 添加定时器
    4. Node* add_timer(int expire, callback cb);
    5. // 删除定时器
    6. bool del_timer(Node* node);
    7. // 找到最近要触发的定时任务
    8. Node* find_nearest_timer();
    9. // 更新检测定时器
    10. void update_timer();
    11. // 清除定时器
    12. // void clear_timer();

    2.2 数据结构设计

    对定时任务的组织本质是要处理对定时任务优先级的处理；由此产生两类数据结构；

    1.按触发时间进行顺序组织
             要求数据结构有序（红黑树、跳表），或者相对有序（最小堆）；
             能快速查找最近触发的定时任务；
             需要考虑怎么处理相同时间触发的定时任务；
    2.按执行顺序进行组织
             时间轮

    2.3 整体思路

    选择set容器（红黑树实现）

    2.3.1 获取当前时间的接口

    1. //获取当前时间
    2. //定义静态成员，类共享
    3. static time_t GetTick() {
    4. 	//chrono是c++ 11中的时间库，提供计时，时钟等功能
    5. 	//毫秒：std::chrono::milliseconds
    6. 	//time_point_cast对时间点进行转换
    7. 	//chrono::steady_clock进行程序耗时的时长，只要启动就会进行时间的累加，并且不能被修改，非常适合于进行耗时的统计。
    8.     auto sc = chrono::time_point_cast<chrono::milliseconds>(chrono::steady_clock::now());
    9. 	//time_since_epoch 获取对象经过的时间间隔
    10.     auto temp = chrono::duration_cast<chrono::milliseconds>(sc.time_since_epoch());
    11.     return temp.count();
    12. }

    2.3.2 相同触发时间的定时任务处理

    2.3.3 完整代码

    1. #include <sys/epoll.h>
    2. #include <functional>
    3. #include <chrono>
    4. #include <set>
    5. #include <memory>
    6. #include <iostream>
    7.  
    8. using namespace std;
    9.  
    10.  
    11. struct TimerNodeBase {
    12.     time_t expire;
    13.     int64_t id;
    14. };
    15.  
    16. //公有继承
    17. struct TimerNode : public TimerNodeBase {
    18. 	//std::function是一个可调用对象包装器，是一个类模板
    19. 	//相当于 typedef  std::function<void(const TimerNode &node)>   Callback;
    20.     using Callback = std::function<void(const TimerNode &node)>;
    21.     Callback func; 
    22. 	
    23. 	//结构体定义构造函数
    24. 	//成员func = 形参func
    25.     TimerNode(int64_t id, time_t expire, Callback func) : func(func) {
    26. 		//形参名与成员变量名相同，则用{this->成员变量名=形参名;}
    27.         this->expire = expire;
    28.         this->id = id;
    29.     }
    30. };
    31.  
    32. //运算符重载
    33. bool operator < (const TimerNodeBase &lhd, const TimerNodeBase &rhd) {
    34.     if (lhd.expire < rhd.expire)
    35.         return true;
    36.     else if (lhd.expire > rhd.expire) 
    37.         return false;
    38.     return lhd.id < rhd.id;
    39. }
    40.  
    41.  
    42. class Timer {
    43. public:
    44.     static time_t GetTick() {
    45. 		//chrono是c++ 11中的时间库，提供计时，时钟等功能。
    46. 		//毫秒：std::chrono::milliseconds
    47. 		//time_point_cast对时间点进行转换
    48. 		//chrono::steady_clock进行程序耗时的时长，只要启动就会进行时间的累加，并且不能被修改，非常适合于进行耗时的统计。
    49.         auto sc = chrono::time_point_cast<chrono::milliseconds>(chrono::steady_clock::now());
    50. 		//time_since_epoch 获取对象经过的时间间隔
    51.         auto temp = chrono::duration_cast<chrono::milliseconds>(sc.time_since_epoch());
    52.         return temp.count();
    53.     }
    54.  
    55. 	//添加
    56.     TimerNodeBase AddTimer(time_t msec, TimerNode::Callback func) {
    57.         time_t expire = GetTick() + msec;
    58. 		//emplace() 返回的迭代器指向新插入的元素
    59.         auto ele = timermap.emplace(GenID(), expire, func);
    60.         return static_cast<TimerNodeBase>(*ele.first);
    61.     }
    62.     
    63. 	//移除
    64.     bool DelTimer(TimerNodeBase &node) {
    65.         auto iter = timermap.find(node);
    66.         if (iter != timermap.end()) {
    67.             timermap.erase(iter);
    68.             return true;
    69.         }
    70.         return false;
    71.     }
    72.  
    73. 	//查询
    74.     bool CheckTimer() {
    75.         auto iter = timermap.begin();
    76.         if (iter != timermap.end() && iter->expire <= GetTick()) {
    77.             iter->func(*iter);
    78.             timermap.erase(iter);
    79.             return true;
    80.         }
    81.         return false;
    82.     }
    83.  
    84. 	//时间差
    85.     time_t TimeToSleep() {
    86.         auto iter = timermap.begin();
    87.         if (iter == timermap.end()) {
    88.             return -1;
    89.         }
    90.         time_t diss = iter->expire-GetTick();
    91.         return diss > 0 ? diss : 0;
    92.     }
    93. private:
    94.     static int64_t GenID() {
    95.         return gid++;
    96.     }
    97.     static int64_t gid;
    98. 	
    99. 	//std::less<T>是一个类的名称，是C++官方给你写好了的一个Comparator，里面的operator()也帮你重载好了的。
    100.     set<TimerNode, std::less<>> timermap;
    101. };
    102. int64_t Timer::gid = 0;
    103.  
    104.  
    105. int main() {
    106.     int epfd = epoll_create(1);
    107.  
    108.     unique_ptr<Timer> timer = make_unique<Timer>();
    109.  
    110.     int i =0;
    111. 	
    112. 	//[&]：以引用形式捕获所有外部变量，也就是外部变量均可用
    113.     timer->AddTimer(1000, [&](const TimerNode &node) {
    114.         cout << Timer::GetTick() << "node id:" << node.id << " revoked times:" << ++i << endl;
    115.     });
    116.  
    117.     timer->AddTimer(1000, [&](const TimerNode &node) {
    118.         cout << Timer::GetTick() << "node id:" << node.id << " revoked times:" << ++i << endl;
    119.     });
    120.  
    121.     timer->AddTimer(3000, [&](const TimerNode &node) {
    122.         cout << Timer::GetTick() << "node id:" << node.id << " revoked times:" << ++i << endl;
    123.     });
    124.  
    125. 	//auto：当编译器能够在一个变量的声明时候就推断出它的类型，那么你就能够用auto关键字来作为他们的类型
    126.     auto node = timer->AddTimer(2100, [&](const TimerNode &node) {
    127.         cout << Timer::GetTick() << "node id:" << node.id << " revoked times:" << ++i << endl;
    128.     });
    129.  
    130.     timer->DelTimer(node);
    131.  
    132.     cout << "now time:" << Timer::GetTick() << endl;
    133.     epoll_event ev[64] = {0};
    134.  
    135.     while (true) {
    136.         /*
    137.             -1 永久阻塞
    138.             0 没有事件立刻返回，有事件就拷贝到 ev 数组当中
    139.             t > 0  阻塞等待 t ms， 
    140.             timeout  最近触发的定时任务离当前的时间
    141.         */
    142.         int n = epoll_wait(epfd, ev, 64, timer->TimeToSleep());
    143.         for (int i = 0; i < n; i++) {
    144.             /**/
    145.         }
    146.         /* 处理定时事件*/
    147.         while(timer->CheckTimer());
    148.     }
    149.     
    150.     return 0;
    151. }

    2.3.4 运行结果

    3. 扩展知识

    3.1 std::function

            std::function对C++中各种可调用实体(普通函数、Lambda表达式、函数指针、以及其它函数对象等)的封装，形成一个新的可调用的std::function对象，简化调用

    1. # include <iostream>
    2. # include <functional>
    3.  
    4. typedef std::function<int(int, int)> comfun;
    5.  
    6. // 普通函数
    7. int add(int a, int b) { return a + b; }
    8.  
    9. // lambda表达式
    10. auto mod = [](int a, int b){ return a % b; };
    11.  
    12. // 函数对象类
    13. struct divide{
    14.     int operator()(int denominator, int divisor){
    15.         return denominator/divisor;
    16.     }
    17. };
    18.  
    19. int main(){
    20. 	comfun a = add;
    21. 	comfun b = mod;
    22. 	comfun c = divide();
    23.     std::cout << a(5, 3) << std::endl;
    24.     std::cout << b(5, 3) << std::endl;
    25.     std::cout << c(5, 3) << std::endl;
    26. }

    3.2 lambda表达式

            lambda是匿名的，lambda表达式就是一段可调用的代码。主要适合于只用到一两次的简短代码段。

    1. # include <iostream>
    2. int fun3(int x, int y){
    3. 	auto f = [](int x, int y) { return x + y; };  //创建lambda表达式,如果参数列表为空，可以省去() 
    4. 	std::cout << f(x, y) << std::endl;            //调用lambda表达式
    5. }
    6. int main(){
    7.     fun3(300, 300);
    8. }

    3.3 结构体的构造函数

    类似于成员函数，但是在初始化成员方面，构造函数显然更方便。

    注意：

    1. 构造函数冒号的左边和构造函数相同，名字与结构体名相同，还有一个形参列表

    2. 如果形参名与成员变量名不同，则可以用成员变量名(形参名)（示例grade变量），多个成员用逗号分割。如果形参名与成员变量名相同，则用{this->成员变量名=形参名;}（示例name变量）来初始化，注意用“->”访问成员变量

    3. 可以直接用变量名(值)（示例name变量）直接给变量赋值

    4. {}一定要有，即使没有用到this来初始化变量，也要加上{}

    5. 形参列表可以为空，然后用第3点的方法初始化变量

    6. 若无构造函数，系统会赠送初始值

    7. this是指向本身的指针，所以访问成员变量用->

    3.4 using的用法

    1. 命令空间的using声明

    using std::cin;  //必须每一个都有独立的using声明

    using std::cout;  using std::endl;   //写在同一行也需要独立声明

    2. 在子类中引用基类成员

    3. 使用using起别名

    typedef   std::vector intvec;

    using       intvec       = std::vector;  //这两个写法是等价的

     推荐一个不错的学习网站 C/C++后台高级服务器https://ke.qq.com/course/417774?flowToken=1010783  

  • 相关阅读:
    DRL基础（十一）——近端策略优化算法PPO【附代码】
    Istio Ambient Mesh七层服务治理图文详解
    arm day 8
    Vue知识框架
    SQL*PLUS对文本长度的限制
    Go常见错误第12篇：冗余的嵌套代码
    【零基础入门SpringMVC】第四期——RESTFUL专题
    数据结构与算法之美笔记06（栈）
    使用 ES 实现疫情地图或者外卖点餐功能（含代码及数据）
    UE5数字孪生制作（一） - QGIS 学习笔记
  • 原文地址：https://blog.csdn.net/kakaka666/article/details/126756097