Larbin 開源爬蟲核心資料結構剖析：FIFO、Vector、檔案讀取

前言

Larbin 是經典 C++ 開源網頁爬蟲，其核心資料結構簡潔高效，無外部依賴。本文深度解析 readfile、Fifo、Vector 三大模組，展示生產級 C++ 容器與 I/O 實作細節。

一、readfile：動態緩衝讀取整個檔案

char* readfile(int fd) {
    size_t pos = 0, size = 512;
    char buf[500];
    ssize_t n;
    char* res = new char[size];

    while (true) {
        n = read(fd, buf, 500);
        if (n == 0) break;           // EOF
        if (n < 0) {                 // 錯誤
            if (errno != EINTR && errno != EIO) break;
            continue;
        }
        // 擴容策略：倍增
        if (pos + n >= size) {
            size *= 2;
            char* tmp = new char[size];
            memcpy(tmp, res, pos);
            delete[] res;
            res = tmp;
        }
        memcpy(res + pos, buf, n);
        pos += n;
    }
    res[pos] = '\0';
    return res; // 呼叫端負責 delete[]
}

亮點：定長堆疊緩衝 buf[500] 減少系統呼叫、指數級擴容攤還 O(1)、處理 EINTR 重試。

二、Fifo：環狀佇列 + 自動擴容

template <class T>
class Fifo {
    uint in, out, size;
    T** tab; // 指標陣列

public:
    Fifo(uint sz = 2000) : in(0), out(0), size(sz) {
        tab = new T*[size];
    }
    ~Fifo() { delete[] tab; }

    // 讀取但不移除
    inline T* read() { return tab[out]; }
    T* tryRead() { return (in==out) ? nullptr : tab[out]; }

    // 取出並移除
    T* get() {
        assert(in != out);
        T* tmp = tab[out];
        out = (out + 1) % size;
        return tmp;
    }
    T* tryGet() {
        if (in == out) return nullptr;
        T* tmp = tab[out];
        out = (out + 1) % size;
        return tmp;
    }

    // 放入，滿則倍增
    void put(T* obj) {
        tab[in] = obj;
        in = (in + 1) % size;
        if (in == out) { // 滿
            T** tmp = new T*[2*size];
            for (uint i = out; i < size; ++i) tmp[i] = tab[i];
            for (uint i = 0; i < in; ++i) tmp[i+size] = tab[i];
            in += size;
            size *= 2;
            delete[] tab;
            tab = tmp;
        }
    }

    // 歸還剛取出的元素（回退）
    void rePut(T* obj) {
        out = (out + size - 1) % size;
        tab[out] = obj;
    }

    int getLength() { return (in + size - out) % size; }
    bool isEmpty() { return in == out; }
};

設計點：

• 儲存 T* 而非 T，避免大物件複製，語意為擁有權轉移
• 環狀索引 (idx+1)%size，rePut 支援回退語意
• 擴容時重新排列邏輯順序，保持 out 指向舊頭部

三、Vector：指標陣列 + 手動記憶體管理

template <class T>
class Vector {
    T** tab;
    uint pos, size;
public:
    Vector(uint sz = 100) : pos(0), size(sz) { tab = new T*[size]; }
    ~Vector() { for (uint i=0;i sz) { size = sz; delete[] tab; tab = new T*[size]; }
        pos = 0;
    }

    void addElement(T* elt) {
        if (pos == size) { // 擴容
            size *= 2;
            T** tmp = new T*[size];
            for (uint i=0;i