標準容器 (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
head->next == head && head->prev == head 表示空表,統一插入/刪除邏輯,無需特判空表。next/prev 形成環,支援雙向遍歷、O(1) 尾部插入 (head->prev)。addr 生命週期,remove/clear 同步釋放。__sync_lock_test_and_set,適合短關鍵區。生產環境建議改用 std::mutex 或無鎖隊列。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)。std::atomic + memory_order 實作無鎖版本 (Michael-Scott Queue)。自訂雙向循環鏈表以哨兵節點簡化邊界條件,明確資料擁有權與同步策略,能高效管理變長記憶體區塊。理解其結構不變量 (循環、雙向、哨兵),是除錯與擴充的關鍵。