资讯专栏INFORMATION COLUMN

Swoole 源码分析——基础模块之 Heap 堆

callmewhy / 1239人阅读

摘要:中是数据堆的权重,也是数据堆排序的依据,是其在数据堆中的位置。改变数据的权重改变了数据节点的权重之后,需要重新进行堆排序,将数据节点向上提升,或者将数据向下调整。

前言

heap 堆是 swoole 实现定时器最重要的数据结构,定时器将各个定时任务按照其下一次执行的时间构建最小堆,快速进行插入与删除。

heap 数据结构

heapnum 是现有数据堆的数量,size 是数据堆的大小,type 用于确定数据堆是最大堆还是最小堆,nodes 是数据堆的节点。swHeap_nodepriority 是数据堆的权重,也是数据堆排序的依据,position 是其在数据堆中的位置。

typedef struct swHeap_node
{
    uint64_t priority;
    uint32_t position;
    void *data;
} swHeap_node;

typedef struct _swHeap
{
    uint32_t num;
    uint32_t size;
    uint8_t type;
    swHeap_node **nodes;
} swHeap;

heap 数据堆 swHeap_new 创建数据堆

创建一个数据堆就是初始化 swHeap 的各个属性。

swHeap *swHeap_new(size_t n, uint8_t type)
{
    swHeap *heap = sw_malloc(sizeof(swHeap));
    if (!heap)
    {
        return NULL;
    }
    if (!(heap->nodes = sw_malloc((n + 1) * sizeof(void *))))
    {
        sw_free(heap);
        return NULL;
    }
    heap->num = 1;
    heap->size = (n + 1);
    heap->type = type;
    return heap;
}
swHeap_push 数据入堆

数据入堆首先要检查 heapsize 是否已经足够,如果不够那么需要扩容。

swHeap_bubble_up 函数负责将数据节点提升到数据堆中相应的位置。方法很简单,新的数据节点不断的和父节点进行对比,符合条件就进行替换,不符合条件就停止,结束。

swHeap_node* swHeap_push(swHeap *heap, uint64_t priority, void *data)
{
    void *tmp;
    uint32_t i;
    uint32_t newsize;

    if (heap->num >= heap->size)
    {
        newsize = heap->size * 2;
        if (!(tmp = sw_realloc(heap->nodes, sizeof(void *) * newsize)))
        {
            return NULL;
        }
        heap->nodes = tmp;
        heap->size = newsize;
    }

    swHeap_node *node = sw_malloc(sizeof(swHeap_node));
    if (!node)
    {
        return NULL;
    }
    node->priority = priority;
    node->data = data;
    i = heap->num++;
    heap->nodes[i] = node;
    swHeap_bubble_up(heap, i);
    return node;
}

#define left(i)   ((i) << 1)
#define right(i)  (((i) << 1) + 1)
#define parent(i) ((i) >> 1)

static void swHeap_bubble_up(swHeap *heap, uint32_t i)
{
    swHeap_node *moving_node = heap->nodes[i];
    uint32_t parent_i;

    for (parent_i = parent(i);
            (i > 1) && swHeap_compare(heap->type, heap->nodes[parent_i]->priority, moving_node->priority);
            i = parent_i, parent_i = parent(i))
    {
        heap->nodes[i] = heap->nodes[parent_i];
        heap->nodes[i]->position = i;
    }

    heap->nodes[i] = moving_node;
    moving_node->position = i;
}

static sw_inline int swHeap_compare(uint8_t type, uint64_t a, uint64_t b)
{
    if (type == SW_MIN_HEAP)
    {
        return a > b;
    }
    else
    {
        return a < b;
    }
}
swHeap_change_priority 改变数据的权重

改变了数据节点的权重之后,需要重新进行堆排序,将数据节点向上提升,或者将数据向下调整。向下调整方法也很简单,不断的和两个子节点进行比较,调整该数据节点和子节点的顺序。

void swHeap_change_priority(swHeap *heap, uint64_t new_priority, void* ptr)
{
    swHeap_node *node = ptr;
    uint32_t pos = node->position;
    uint64_t old_pri = node->priority;

    node->priority = new_priority;
    if (swHeap_compare(heap->type, old_pri, new_priority))
    {
        swHeap_bubble_up(heap, pos);
    }
    else
    {
        swHeap_percolate_down(heap, pos);
    }
}

static void swHeap_percolate_down(swHeap *heap, uint32_t i)
{
    uint32_t child_i;
    swHeap_node *moving_node = heap->nodes[i];

    while ((child_i = swHeap_maxchild(heap, i))
            && swHeap_compare(heap->type, moving_node->priority, heap->nodes[child_i]->priority))
    {
        heap->nodes[i] = heap->nodes[child_i];
        heap->nodes[i]->position = i;
        i = child_i;
    }

    heap->nodes[i] = moving_node;
    moving_node->position = i;
}

static uint32_t swHeap_maxchild(swHeap *heap, uint32_t i)
{
    uint32_t child_i = left(i);
    if (child_i >= heap->num)
    {
        return 0;
    }
    swHeap_node * child_node = heap->nodes[child_i];
    if ((child_i + 1) < heap->num && swHeap_compare(heap->type, child_node->priority, heap->nodes[child_i + 1]->priority))
    {
        child_i++;
    }
    return child_i;
}
swHeap_pop 弹出堆顶元素

弹出堆顶元素后,需要重新调整整个数据堆。方法是将尾部元素和堆顶元素进行交换,然后再对堆顶元素进行排序。

void *swHeap_pop(swHeap *heap)
{
    swHeap_node *head;
    if (!heap || heap->num == 1)
    {
        return NULL;
    }

    head = heap->nodes[1];
    heap->nodes[1] = heap->nodes[--heap->num];
    swHeap_percolate_down(heap, 1);

    void *data = head->data;
    sw_free(head);
    return data;
}

swHeap_remove 删除元素

删除堆节点元素和弹出堆顶元素类似,都是先将该元素和尾部元素进行替换,然后再对其进行排序。由于尾部元素不一定比待删除的元素权重高,因此需要先判断其权重,再决定是提升还是降低。

int swHeap_remove(swHeap *heap, swHeap_node *node)
{
    uint32_t pos = node->position;
    heap->nodes[pos] = heap->nodes[--heap->num];

    if (swHeap_compare(heap->type, node->priority, heap->nodes[pos]->priority))
    {
        swHeap_bubble_up(heap, pos);
    }
    else
    {
        swHeap_percolate_down(heap, pos);
    }
    return SW_OK;
}

文章版权归作者所有,未经允许请勿转载,若此文章存在违规行为,您可以联系管理员删除。

转载请注明本文地址:https://www.ucloud.cn/yun/30855.html

相关文章

  • Swoole 源码分析——Server模块Timer模块与时间轮算法

    摘要:当其就绪时,会调用执行定时函数。进程超时停止进程将要停止时,并不会立刻停止,而是会等待事件循环结束后停止,这时为了防止进程不退出,还设置了的延迟,超过就会停止该进程。当允许空闲时间小于时,统一每隔检测空闲连接。 前言 swoole 的 timer 模块功能有三个:用户定时任务、剔除空闲连接、更新 server 时间。timer 模块的底层有两种,一种是基于 alarm 信号,一种是基于...

    qieangel2013 评论0 收藏0
  • Python 的 heapq 模块源码分析

    摘要:原文链接起步模块实现了适用于列表的最小堆排序算法。本文内容将分为三个部分,第一个部分简单介绍模块的使用第二部分回顾堆排序算法第三部分分析中的实现。总结堆排序结合图来理解还是比较好理解的。 原文链接:https://www.hongweipeng.com/i... 起步 heapq 模块实现了适用于Python列表的最小堆排序算法。 showImg(https://segmentfaul...

    CoderBear 评论0 收藏0
  • Swoole 源码分析——基础模块Queue队列

    摘要:消息队列的接受消息队列的接受是利用函数,其中是消息的类型,该参数会取出指定类型的消息,如果设定的是争抢模式,该值会统一为,否则该值就是消息发送目的的。环形队列的消息入队发送消息首先要确定环形队列的队尾。取模操作可以优化 前言 swoole 的底层队列有两种:进程间通信 IPC 的消息队列 swMsgQueue,与环形队列 swRingQueue。IPC 的消息队列用于 task_wor...

    jollywing 评论0 收藏0
  • Swoole 源码分析——基础模块 Channel 队列

    摘要:前言内存数据结构,类似于的通道,底层基于共享内存互斥锁实现,可实现用户态的高性能内存队列。是当前队列占用的内存大小,用来指定是否使用共享内存是否使用锁是否使用通知。 前言 内存数据结构 Channel,类似于 Go 的 chan 通道,底层基于 共享内存 + Mutex 互斥锁实现,可实现用户态的高性能内存队列。Channel 可用于多进程环境下,底层在读取写入时会自动加锁,应用层不需...

    txgcwm 评论0 收藏0
  • JavaScript 内存分析新工具 OneHeap

    摘要:关注于运行中的内存信息的展示,用可视化的方式还原了,有助于理解内存管理。背景运行过程中的大部分数据都保存在堆中,所以性能分析另一个比较重要的方面是内存,也就是堆的分析。上周发布了工具,可以用来动态地展示的结果,分析各种函数的调用关系。 OneHeap 关注于运行中的 JavaScript 内存信息的展示,用可视化的方式还原了 HeapGraph,有助于理解 v8 内存管理。 ...

    zilu 评论0 收藏0

发表评论

0条评论

最新活动
阅读需要支付1元查看
<