大佬教程收集整理的这篇文章主要介绍了你了解红黑树么?告诉你一个不一样的红黑树,说点有意思的吧!,大佬教程大佬觉得挺不错的,现在分享给大家,也给大家做个参考。
// libuv定时器使用回调函数来比较key的大小,这里的key就是到期时间timeout
static int timer_less_than(const struct heap_node* ha,
const struct heap_node* hb) {
const uv_timer_t* a;
const uv_timer_t* b;
a = container_of(ha, uv_timer_t, heap_nodE);
b = container_of(hb, uv_timer_t, heap_nodE);
if (a->timeout < b->timeout)
return 1;
if (b->timeout < a->timeout)
return 0;
/* Compare start_id when both have the same timeout. start_id is
* allocated with loop->timer_counter in uv_timer_start().
*/
// 如果两者过期时间相同,则采用start_id来判断谁先执行
// 这个start_id是个自增变量,后加入堆中的定时器的start_id要大于早加入堆中的定时器
return a->start_id < b->start_id;
}
// 定时器启动并加入到堆中的函数
int uv_timer_start(uv_timer_t* handle,
uv_timer_cb cb,
uint64_t timeout,
uint64_t repeat) {
uint64_t clamped_timeout;
if (uv__is_closing(handlE) || cb == NULL)
return UV_EINVAL;
if (uv__is_active(handlE))
uv_timer_stop(handlE);
clamped_timeout = handle->loop->time + timeout;
if (clamped_timeout < timeout)
clamped_timeout = (uint64_t) -1;
handle->timer_cb = cb;
handle->timeout = clamped_timeout;
handle->repeat = repeat;
/* start_id is the second index to be compared in timer_less_than() */
handle->start_id = handle->loop->timer_counter++;
// 将定时器插入堆中,并使用timer_less_than函数进行堆排序
heap_insert(timer_heap(handle->loop),
(struct heap_node*) &handle->heap_node,
timer_less_than);
uv__handle_start(handlE);
return 0;
}
@H_262_2@libuv使用的是最小堆来保存和管理多个定时器,在排序的过程中如果发现时间相等的节点(见上面函数 timer_less_than),则采用start_id来比较大小,这个start_id是个自增变量,后加入堆中的定时器的start_id要大于早加入堆中的定时器 。从而来判断键值相等的到期事件谁先执行。
@H_262_2@回到上面很2的红黑树,如果你仔细观察这颗树的创建过程@R_702_10585@,对于键值相同的节点是有时间顺序的,插入晚的默认为大值,放在后面,也就是说红黑树自动实现了按时间轴存储键值的功能。即使到期事件相等(键值Key相等),我们也可以根据其插入红黑树的时间顺序来取出最小到期事件去执行。
@H_262_2@nginx使用的就是红黑树的方式来存储和管理多个定时器。这里就不再介绍了,可以问度娘要源码分析。
以上是大佬教程为你收集整理的你了解红黑树么?告诉你一个不一样的红黑树,说点有意思的吧!全部内容,希望文章能够帮你解决你了解红黑树么?告诉你一个不一样的红黑树,说点有意思的吧!所遇到的程序开发问题。
如果觉得大佬教程网站内容还不错,欢迎将大佬教程推荐给程序员好友。
本图文内容来源于网友网络收集整理提供,作为学习参考使用,版权属于原作者。
如您有任何意见或建议可联系处理。小编QQ:384754419,请注明来意。