国产xxxx99真实实拍_久久不雅视频_高清韩国a级特黄毛片_嗯老师别我我受不了了小说

資訊專欄INFORMATION COLUMN

Swoole 源碼分析——基礎模塊之 Heap 堆

callmewhy / 1240人閱讀

摘要:中是數據堆的權重,也是數據堆排序的依據,是其在數據堆中的位置。改變數據的權重改變了數據節點的權重之后,需要重新進行堆排序,將數據節點向上提升,或者將數據向下調整。

前言

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;
}

文章版權歸作者所有,未經允許請勿轉載,若此文章存在違規行為,您可以聯系管理員刪除。

轉載請注明本文地址:http://specialneedsforspecialkids.com/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元查看
<