萬盛學電腦網

您现在的位置: 萬盛學電腦網 >> 程式設計 >  >> 網路程式設計 >> 程式語言綜合

C++ 封裝雙向循環鏈表儲存記憶體區塊:完整原始碼與設計解析

設計目標

標準容器 (std::list) 針對固定型別元素優化。當需儲存變長記憶體區塊 (如網路封包、序列化資料) 且要求 O(1) 插入/刪除、雙向遍歷、執行緒同步鎖時,自訂雙向循環鏈表更靈活。

標頭檔

#ifndef NET_DATA_H
#define NET_DATA_H

#include <cstdio>
#include <cstdlib>
#include <cassert>

using uint = unsigned int;

struct DataBuf {
    char *addr;          // 區塊起始位址
    uint len;            // 區塊長度
    DataBuf *next;       // 後繼節點
    DataBuf *prev;       // 前驅節點
};

class NetData {
public:
    using Node = DataBuf*;

    NetData() : head(nullptr), locked(false) {}
    ~NetData() { clear(); }

    // 執行緒同步簡易自旋鎖
    void lock()   { while (__sync_lock_test_and_set(&locked, 1)) ; }
    void unlock() { __sync_lock_release(&locked); }
    void waitUnlock() { while (locked) ; }

    // 節點操作
    static void setNodeData(Node n, char *addr, uint len) {
        n->addr = addr; n->len = len;
    }
    static void printNode(Node n) {
        printf("Node %p: addr=%p len=%u\n", (void*)n, (void*)n->addr, n->len);
    }
    void printList() const {
        if (!head) return;
        Node p = head;
        do { printNode(p); p = p->next; } while (p != head);
    }
    int getLength() const {
        if (!head) return 0;
        int len = 0;
        Node p = head;
        do { ++len; p = p->next; } while (p != head);
        return len;
    }

    // 建立頭節點 (哨兵節點,不存資料)
    Node createHead() {
        Node n = (Node)malloc(sizeof(DataBuf));
        assert(n);
        n->next = n->prev = n; // 指向自己形成空循環
        n->addr = nullptr; n->len = 0;
        return n;
    }

    // 在 existing 節點後插入新節點
    Node insertAfter(Node pos, char *addr, uint len) {
        Node n = (Node)malloc(sizeof(DataBuf));
        assert(n);
        setNodeData(n, addr, len);
        n->next = pos->next;
        n->prev = pos;
        pos->next->prev = n;
        pos->next = n;
        return n;
    }

    // 刪除 pos 節點 (pos 不可為 head)
    bool remove(Node pos) {
        if (!head || pos == head) return false;
        pos->prev->next = pos->next;
        pos->next->prev = pos->prev;
        free(pos->addr); // 釋放資料區塊
        free(pos);       // 釋放節點本身
        return true;
    }

    // 清空整個列表
    void clear() {
        if (!head) return;
        Node cur = head->next;
        while (cur != head) {
            Node nxt = cur->next;
            free(cur->addr);
            free(cur);
            cur = nxt;
        }
        free(head);
        head = nullptr;
    }

private:
    Node head;      // 哨兵頭節點
    volatile int locked; // 簡易自旋鎖 (GCC/Clang builtin)
};

#endif // NET_DATA_H

關鍵設計細節

  1. 哨兵頭節點:head->next == head && head->prev == head 表示空表,統一插入/刪除邏輯,無需特判空表。
  2. 循環雙向:next/prev 形成環,支援雙向遍歷、O(1) 尾部插入 (head->prev)。
  3. 記憶體擁有權:節點負責 addr 生命週期,remove/clear 同步釋放。
  4. 自旋鎖:使用 GCC/Clang 内建原子操作 __sync_lock_test_and_set,適合短關鍵區。生產環境建議改用 std::mutex 或無鎖隊列。
  5. C 風格介面:malloc/free、assert、printf,便於嵌入式/C 混合專案;C++ 專案可改用 new/delete、std::unique_ptr、iostream。

使用範例

NetData queue;
queue.head = queue.createHead();

queue.lock();
queue.insertAfter(queue.head, (char*)"Packet1", 7); // 插入頭部後
queue.insertAfter(queue.head->prev, (char*)"Packet2", 7); // 插入尾部
queue.unlock();

queue.printList();
// Node 0x...: addr=0x... len=7
// Node 0x...: addr=0x... len=7

queue.lock();
queue.remove(queue.head->next); // 移除第一個資料節點
queue.unlock();

擴充建議

  • 加入 find_if 依資料內容查找。
  • 實作 pop_front/pop_back 返回資料所有權 (std::unique_ptr)。
  • 提供迭代器介面符合 STL 慣例。
  • 使用 std::atomic + memory_order 實作無鎖版本 (Michael-Scott Queue)。

結語

自訂雙向循環鏈表以哨兵節點簡化邊界條件,明確資料擁有權與同步策略,能高效管理變長記憶體區塊。理解其結構不變量 (循環、雙向、哨兵),是除錯與擴充的關鍵。

copyright © 萬盛學電腦網 all rights reserved