延庆宜昌网站建设,去哪找wordpress主题,asp故障解答网站模板,网站内容建设评估老早之前就听说时间轮算法特别高效#xff0c;Linux内核都用的它#xff0c;这两天抽空实现了遍……嗯#xff0c;被差一bug搞死(~#xffe3;▽#xffe3;~) 啊哈 网上扣来的图#xff0c;原理好懂#xff1a;轮子里的每格代表一小段时间#xff08;精度#xff09;…老早之前就听说时间轮算法特别高效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 headuint32 timeDead;uint32 interval; //间隔多久int loop; //总共循环多久std::functionvoid() 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); //勿忘-1slot _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转载于:https://www.cnblogs.com/3workman/p/6063819.html
