首页 > 代码库 > 时间轮
时间轮
老早之前就听说时间轮算法特别高效,Linux内核都用的它,这两天抽空实现了遍……嗯,被差一bug搞死(~ ̄▽ ̄~) 啊哈
网上扣来的图,原理好懂:轮子里的每格代表一小段时间(精度),连起来就能表示时间点了(我去年买了个表),格子内含链表,中存回调函数;时间指针每次转动一格,指向某格时,取出链表里的回调函数依次执行,后清空链表,等待下一次转动。
加入节点逻辑也简单:在轮子可表示的时间范围内(格子数*格子精度),配合当前时针位置,对格子总数取余,即得本节点需放哪个格子。
进一步为扩大时间轮的表示范围,使用分级方式,跟时分秒一样,上一级转一圈,下一级动一格。
对吧,很容易理解……然后coding是另一码事(╯‵□′)╯︵┴─┴
首先,最重要的,数据结构:用了环形链表,方便增删。
struct NodeLink { NodeLink* prev; NodeLink* next; NodeLink() { prev = next = this; } //circle }; struct stWheel { NodeLink* slots; //每个slot维护的node链表为一个环,slot->next为node链表中第一个节点,prev为node的最后一个节点 const uint32 size; uint32 slotIdx; stWheel(uint32 n) : size(n), slotIdx(0){ slots = new NodeLink[size]; } ~stWheel() { if (slots) { for (uint32 j = 0; j < size; ++j) { NodeLink* link = (slots + j)->next; while (link != slots + j) { TimerNode* node = (TimerNode*)link; link = node->link.next; delete node; } } delete[]slots; } } };
具体时间节点的数据结构如下:
struct TimerNode { Pool_Obj_Define(TimerNode, 32) //内存池声明,不含数据 NodeLink link; //must in the head uint32 timeDead; uint32 interval; //间隔多久 int loop; //总共循环多久 std::function<void()> func; };
TimeNode里保存上下关系,stWheel的NodeLink辅助用的,环状链表的头,没实际数据,用以记录首尾TimeNode。
核心代码如下:
——增删节点——
void CTimerMgr::_AddTimerNode(uint32 milseconds, TimerNode* node) { NodeLink* slot = NULL; uint32 tickCnt = milseconds / TIME_TICK_LEN; if (tickCnt < WHEEL_CAP[0]) { uint32 index = (_wheels[0]->slotIdx + tickCnt) & (WHEEL_SIZE[0] - 1); //2的N次幂位操作取余 slot = _wheels[0]->slots + index; } else { for (int i = 1; i < WHEEL_NUM; ++i) { if (tickCnt < WHEEL_CAP[i]) { uint32 preCap = WHEEL_CAP[i - 1]; //上一级总容量即为本级的一格容量 uint32 index = (_wheels[i]->slotIdx + tickCnt / preCap - 1) & (WHEEL_SIZE[i] - 1); //勿忘-1 slot = _wheels[i]->slots + index; break; } } } NodeLink* link = &(node->link); link->prev = slot->prev; //插入格子的prev位置(尾节点) link->prev->next = link; link->next = slot; slot->prev = link; } void CTimerMgr::RemoveTimer(TimerNode* node) { LOG_TRACK("node[%p], timeDead[%lld]", node, node->timeDead); NodeLink* link = &(node->link); if (link->prev) { link->prev->next = link->next; } if (link->next) { link->next->prev = link->prev; } link->prev = link->next = NULL; delete node; }
——轮子启动——
void CTimerMgr::CheckTimerList(const uint32 timenow) { uint32 tickCnt = timenow > _checkTime ? (timenow - _checkTime) / TIME_TICK_LEN : 0; //if (tickCnt) Printf(); for (uint32 i = 0; i < tickCnt; ++i) { //扫过的slot均超时 stWheel* wheel = _wheels[0]; NodeLink* slot = wheel->slots + wheel->slotIdx; NodeLink* link = slot->next; slot->next = slot->prev = slot; //清空当前格子 while (link != slot) { //环形链表遍历 TimerNode* node = (TimerNode*)link; link = node->link.next; //得放在前面,后续函数调用,可能会更改node的链接关系 AddToReadyNode(node); } if (++(wheel->slotIdx) >= wheel->size) { wheel->slotIdx = 0; Cascade(1, timenow); //跳级 } _checkTime += TIME_TICK_LEN; } DoTimeOutCallBack(); } uint32 CTimerMgr::Cascade(uint32 wheelIdx, const uint32 timenow) { if (wheelIdx < 1 || wheelIdx >= WHEEL_NUM) { return 0; } int casCnt = 0; stWheel* wheel = _wheels[wheelIdx]; NodeLink* slot = wheel->slots + wheel->slotIdx; NodeLink* link = slot->next; slot->next = slot->prev = slot; //清空当前格子 while (link != slot) { TimerNode* node = (TimerNode*)link; link = node->link.next; if (node->timeDead <= timenow) { AddToReadyNode(node); } else { _AddTimerNode(node->timeDead - timenow, node); //本级精度下已超时,精度提升,重新加一遍 ++casCnt; LOG_TRACK("wheelIdx[%u], link[%p], milseconds[%u]", wheelIdx, link, node->timeDead - timenow); } } if (++(wheel->slotIdx) >= wheel->size) { wheel->slotIdx = 0; casCnt += Cascade(++wheelIdx, timenow); } return casCnt; }
那么问题来了:大于,大于等于,边界,减一……搞错几多次 ○(* ̄︶ ̄*)○ 吃饱睡好
源码地址:https://github.com/3workman/Tools/tree/master/src/Timer
时间轮
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。