設計一個 C 語言的動态擴容緩沖區

知識要點：字元串、面向對象的 C 語言設計、動态記憶體配置設定、Linux File API、getline。

文章目錄

設計一個 C 語言的動态擴容緩沖區
- 代碼編寫及講解
- - Part 2A
  - - void strbuf_init(struct strbuf *sb, size_t alloc);
    - void strbuf_attach(struct strbuf *sb, void *str, size_t len, size_t alloc);
    - void strbuf_release(struct strbuf *sb);
    - void strbuf_swap(struct strbuf *a, struct strbuf *b);
    - char *strbuf_detach(struct strbuf *sb, size_t *sz);
    - int strbuf_cmp(const struct strbuf *first, const struct strbuf *second);
    - void strbuf_reset(struct strbuf *sb);
  - Part 2B
  - - void strbuf_grow(struct strbuf *sb, size_t extra);
    - void strbuf_add(struct strbuf *sb, const void *data, size_t len);
    - void strbuf_addch(struct strbuf *sb, int c);
    - void strbuf_addstr(struct strbuf *sb, const char *s);
    - void strbuf_addbuf(struct strbuf *sb, const struct strbuf *sb2);
    - void strbuf_setlen(struct strbuf *sb, size_t len);
    - size_t strbuf_avail(const struct strbuf *sb);
    - void strbuf_insert(struct strbuf *sb, size_t pos, const void *data, size_t len);
  - Part 2C
  - - void strbuf_rtrim(struct strbuf *sb);
    - void strbuf_ltrim(struct strbuf *sb);
    - void strbuf_remove(struct strbuf *sb, size_t pos, size_t len);
  - Part 2D
  - - ssize_t strbuf_read(struct strbuf *sb, int fd, size_t hint);
    - int strbuf_getline(struct strbuf *sb, FILE *fp);
  - CHALLENGE
  - - struct strbuf **strbuf_split_buf(const char *str, size_t len, int terminator, int max);
    - bool strbuf_begin_judge(char* target_str, const char* str, int strlen);
    - char* strbuf_get_mid_buf(char* target_buf, int begin, int end, int len);
- 參考資料

代碼編寫及講解

緩沖區類的定義

struct strbuf {
  int len;     //目前緩沖區（字元串）長度
  int alloc;   //目前緩沖區（字元串）容量
  char *buf;   //緩沖區（字元串）
};

HINT

strbuf 的成員 len 代表的是 buf 緩沖區的長度，每次我們将字元串追加入 strbuf 中，我們都應該使用 strbuf_setlen() 去更新 strbuf 的長度 len ，注意 123\0456 的長度不是 3，而是 7。

strbuf 的成員 alloc 代表的是 buf 緩沖區的容量，也就是我們每次動态配置設定的數組大小，每當我們需要向 sb 内追加一個字元串，我們需要計算目前的字元串長度加上追加的字元串長度，如果超過了目前的容量，我們就需要把容量擴大一倍，然後将字元串添加進去。

Part 2A

實作字元串緩沖區類 strbuf 簡單的初始化，填充，釋放，交換，比較，清空等操作。

void strbuf_init(struct strbuf *sb, size_t alloc);

初始化 sb 結構體，容量為 alloc 。

初始化時要為緩沖區寫入容量大小，在記憶體中申請空間，寫入長度大小，并将緩沖區設定為空字元串。

void strbuf_init(struct strbuf *sb, size_t alloc) {
    sb->alloc = alloc;
    sb->buf = (char *) malloc(alloc);
    sb->buf[sb->len = 0] = '\0';
}

void strbuf_attach(struct strbuf sb, void str, size_t len, size_t alloc);

将字元串填充到 sb 中，長度為 len , 容量為 alloc 。

字元串

已經有其對應的長度、容量、内容資訊，直接将其對應填入緩沖區即可。

void strbuf_attach(struct strbuf *sb, void *str, size_t len, size_t alloc) {
    sb->len = len;
    sb->alloc = alloc;
    sb->buf = (char *) str;
}

void strbuf_release(struct strbuf *sb);

釋放 sb 結構體的記憶體。

釋放緩沖區記憶體，将容量大小、長度資訊歸零，并為緩沖區賦予空指針，防止重複釋放記憶體時報錯。

void strbuf_release(struct strbuf *sb) {
    free(sb->buf);
    strbuf_attach(sb, NULL, 0, 0);
}

void strbuf_swap(struct strbuf a, struct strbuf b);

交換兩個 strbuf 。

交換時，可以利用結構體淺拷貝特性，通過增加一個臨時的緩沖區變量，實作兩個緩沖區的交換。

void strbuf_swap(struct strbuf *a, struct strbuf *b) {
    struct strbuf tmp = *a;
    *a = *b;
    *b = tmp;
}

char strbuf_detach(struct strbuf sb, size_t *sz);

将 sb 中的原始記憶體取出，并将 sz 設定為其 alloc 大小。

将緩沖區的容量資訊賦給

sz

，并傳回緩沖區的指針。

char *strbuf_detach(struct strbuf *sb, size_t *sz) {
    *sz = sb->alloc;
    return sb->buf;
}

int strbuf_cmp(const struct strbuf first, const struct strbuf second);

比較兩個 strbuf 的記憶體是否相同。

緩沖區中可能有

'\0'

存在，是以需要比較長度範圍内的所有資訊，不能使用

strcmp()

。

可以先比較長度，如果長度不同則傳回長度的差，如果長度相同則使用

memcmp()

比較長度内的資訊。

int strbuf_cmp(const struct strbuf *first, const struct strbuf *second) {
    return first->len - second->len || memcmp(first->buf, second->buf, first->len);
}

void strbuf_reset(struct strbuf *sb);

清空 sb 。

清空緩沖區，則需要将長度歸零，并将空字元串填入緩沖區。

void strbuf_reset(struct strbuf *sb) {
    sb->buf[sb->len = 0] = '\0';
}

Part 2B

實作字元串緩沖區類 strbuf 擴容，(追加|插入)字元，字元串等操作。

void strbuf_grow(struct strbuf *sb, size_t extra);

確定在 len 之後 strbuf 中至少有 extra 個位元組的空閑空間可用。

先計算可用空間，如果可用空間不足，則重新申請記憶體，将記憶體指針賦給緩沖區，并更新容量資訊。

void strbuf_grow(struct strbuf *sb, size_t extra) {
    if (sb->alloc - sb->len < extra)
        sb->buf = (char *) realloc(sb->buf, sb->alloc += extra);
}

void strbuf_add(struct strbuf sb, const void data, size_t len);

向 sb 追加長度為 len 的資料 data 。

追加資料前，先保證容量足夠，然後将追加内容拷貝進緩沖區，并更新長度、字元串結束标志。

void strbuf_add(struct strbuf *sb, const void *data, size_t len) {
    strbuf_grow(sb, len + 1);
    memcpy(sb->buf + sb->len, data, len);
    sb->buf[sb->len += len] = '\0';
}

void strbuf_addch(struct strbuf *sb, int c);

向 sb 追加一個字元 c 。

使用追加函數向緩沖區追加字元，長度為1。

void strbuf_addch(struct strbuf *sb, int c) {
    strbuf_add(sb, &c, 1);
}

void strbuf_addstr(struct strbuf sb, const char s);

向 sb 追加一個字元串 s 。

使用追加函數向緩沖區追加字元串，長度為

strlen(s)

。

void strbuf_addstr(struct strbuf *sb, const char *s) {
    strbuf_add(sb, s, strlen(s));
}

void strbuf_addbuf(struct strbuf sb, const struct strbuf sb2);

向一個 sb 追加另一個 strbuf 的資料。

使用追加字元串函數向緩沖區追加另一個緩沖區的内容。

這種做法并不規範！标準做法是使用追加函數向緩沖區追加另一個緩沖區的内容，長度為緩沖區的長度。

void strbuf_addbuf(struct strbuf *sb, const struct strbuf *sb2) {
    strbuf_addstr(sb, sb2->buf);
}

void strbuf_setlen(struct strbuf *sb, size_t len);

設定 sb 的長度 len 。

如果設定的長度大于緩沖區容量，則先增加緩沖區容量。設定長度，并在對應位置增加字元串結束标志

'\0'

。

這種做法并不規範！函數預設：設定的長度一定小于容量。是以不需要判斷長度或者增加容量，遇到問題應該直接抛出錯誤。

void strbuf_setlen(struct strbuf *sb, size_t len) {
    if (len > sb->alloc) strbuf_grow(sb, len - sb->len + 1);
    sb->buf[sb->len = len] = '\0';
}

size_t strbuf_avail(const struct strbuf *sb);

計算 sb 目前仍可以向後追加的字元串長度。

傳回緩沖區容量減去字元串長度再減一的值。

size_t strbuf_avail(const struct strbuf *sb) {
    return sb->alloc - sb->len - 1;
}

void strbuf_insert(struct strbuf sb, size_t pos, const void data, size_t len);

向 sb 記憶體坐标為 pos 位置插入長度為 len 的資料 data 。

設定緩沖區長度為插入後的長度，将插入字元串處的緩沖區内容移動到插入内容結束的位置，并使用

memcpy()

拷貝長度為

len

的内容到插入的位置。

void strbuf_insert(struct strbuf *sb, size_t pos, const void *data, size_t len) {
    strbuf_setlen(sb, sb->len + len);
    memmove(sb->buf + pos + len, sb->buf + pos, sb->len - pos);
    memcpy(sb->buf + pos, data, len);
}

Part 2C

void strbuf_rtrim(struct strbuf *sb);

去除 sb 緩沖區右端的所有空格，tab,‘\t’。

如果讀到結尾處時空格或者制表符，則填充字元串結束标志

'\0'

，并減少長度，直到結尾處不是空格或者制表符。

void strbuf_rtrim(struct strbuf *sb) {
    while (sb->buf[sb->len - 1] == ' ' || sb->buf[sb->len - 1] == '\t')
        sb->buf[--sb->len] = '\0';
}

void strbuf_ltrim(struct strbuf *sb);

去除 sb 緩沖區左端的所有空格，tab,‘\t’。

聲明一個修剪位置變量為緩沖區内容開頭的相對位置，如果讀到修剪位置處時空格或者制表符，則增加修剪位置，直到修剪位置處不是空格或者制表符。

将修剪位置處開始，長度為緩沖區長度減去修剪位置+1的緩沖區内容移動到緩沖區内容開頭，并将緩沖區長度減去修剪位置，就完成了緩沖區左端的修剪操作。

void strbuf_ltrim(struct strbuf *sb) {
    int trimpos = 0;
    while (sb->buf[trimpos] == ' ' || sb->buf[trimpos] == '\t') trimpos++;
    memmove(sb->buf, sb->buf + trimpos, (sb->len -= trimpos) + 1);
}

void strbuf_remove(struct strbuf *sb, size_t pos, size_t len);

删除 sb 緩沖區從 pos 坐标長度為 len 的内容。

将删除坐标加删除長度處，長度為緩沖區長度減删除長度減相對删除位置+1的内容，移動到絕對删除位置處，并将緩沖區長度減去删除長度，便完成了删除緩沖區指定位置處指定長度内容的操作。

void strbuf_remove(struct strbuf *sb, size_t pos, size_t len) {
    memmove(sb->buf + pos, sb->buf + pos + len, (sb->len -= len) - pos + 1);
}

Part 2D

ssize_t strbuf_read(struct strbuf *sb, int fd, size_t hint);

sb 增長 hint ? hint : 8192 大小，然後将檔案描述符為 fd 的所有檔案内容追加到 sb 中。

先使用

strbuf_grow()

增長記憶體空間，再使用

fdopen()

讀取檔案到檔案指針

*fp

。使用

fgetc()

逐字元讀取，并使用

strbuf_addch()

将字元加入緩沖區，直到讀到檔案末尾結束，傳回讀取的檔案長度。

ssize_t strbuf_read(struct strbuf *sb, int fd, size_t hint) {
    strbuf_grow(sb, hint ? hint : 8192);
    FILE *fp = fdopen(fd, "r");
    for (char ch; (ch = fgetc(fp)) != EOF;) strbuf_addch(sb, ch);
    return sb->len;
}

int strbuf_getline(struct strbuf sb, FILE fp);

将檔案句柄為 fp 的一行内容（抛棄換行符）讀取到 sb 。

使用

fgetc()

逐字元讀取檔案指針

*fp

，并使用

strbuf_addch()

将字元加入緩沖區，直到讀到換行符或者檔案末尾結束，傳回讀取的檔案長度。

int strbuf_getline(struct strbuf *sb, FILE *fp) {
    for (char ch; (ch = fgetc(fp)) != '\n' && ch != EOF;) strbuf_addch(sb, ch);
    return sb->len;
}

CHALLENGE

1.實作字元串切割（C 系字元串函數的一個痛點）。

struct strbuf **strbuf_split_buf(const char *str, size_t len, int terminator, int max);

将長度為 len 的字元串 str 根據切割字元 terminator 切成多個 strbuf,并從結果傳回，max 可以用來限定最大切割數量。傳回 struct strbuf 的指針數組，數組的最後元素為 NULL 。

剛開始，我嘗試使用

strtok()

實作，但是由于緩沖區内容含有

'\0'

，此後的内容被舍棄了，是以并沒有達成目标。

struct strbuf **strbuf_split_buf(const char *str, size_t len, int terminator, int max) {
    struct strbuf **ret = (struct strbuf **) malloc(sizeof(struct strbuf *) * (max + 1));
    char s[len + 1], delim[2] = {(char) terminator};
    memcpy(s, str, len + 1);
    char *token = strtok(s, delim);
    for (int i = 0; token && i < max; ret[++i] = NULL) {
        ret[i] = (struct strbuf *) malloc(sizeof(struct strbuf));
        strbuf_init(ret[i], 0);
        strbuf_addstr(ret[i], token);
        token = strtok(NULL, delim);
    }
    return ret;
}

後來，則标記字串的起始位置和結束位置，通過循環來逐字元判斷，滿足條件則切割，循環完畢即輸出。

struct strbuf **strbuf_split_buf(const char *str, size_t len, int terminator, int max) {
    struct strbuf **ret = (struct strbuf **) malloc(sizeof(struct strbuf *) * (max + 1));
    for (int pos = 0, flag = 0, n = 0; pos <= len && n < max; pos++) {
        while (str[flag] == terminator) pos = flag++ + 2;
        if (pos == len || pos > flag && str[pos] == terminator) {
            ret[n] = (struct strbuf *) malloc(sizeof(struct strbuf));
            strbuf_init(ret[n], 0);
            strbuf_add(ret[n], str + flag, pos - flag);
            // printf("[%d]: %s (%d~%d, %d)\n", n, ret[n]->buf, flag, pos, pos - flag);
            while (str[pos] == terminator) flag = pos++;
            ret[++n] = NULL;
        }
    }
    return ret;
}

2.實作判斷一個strbuf是否以指定字元串開頭的功能（C系字元串函數的另一個痛點）。

bool strbuf_begin_judge(char* target_str, const char* str, int strlen);

target_str：目标字元串，str：字首字元串，strlen：target_str長度，字首相同傳回true失敗傳回false

字首字元串為空則傳回

true

，否則使用

strncmp()

對比目标字元串的前

strlen

位元組是否與字首字元串相同，如果相同結果為0傳回

true

，否則傳回

false

。

bool strbuf_begin_judge(char *target_str, const char *str, int strnlen) {
    return str == NULL || !strncmp(target_str, str, strlen(str));
}

3.擷取字元串從坐标 [begin, end) 的所有内容（可以分成引用和拷貝兩個模式）。

char* strbuf_get_mid_buf(char* target_buf, int begin, int end, int len);

target_str：目标字元串，begin：開始下标，end：結束下标，len：target_buf的長度。參數不合法傳回NULL。下标從0開始，[begin, end)區間。

如果參數不合法（起始大于結束、結束大于長度）傳回

NULL

。

否則為字元串申請結束下标減開始下标+1的空間，将指定位置指定長度的字元串填入，并在末尾加上字元串結束标志

'\0'

，傳回字元串。

char *strbuf_get_mid_buf(char *target_buf, int begin, int end, int len) {
    if (begin > end || end >= len) return NULL;
    char *str = (char *) malloc(end - begin + 1);
    memcpy(str, target_buf + begin, end - begin);
    str[end - begin] = '\0';
    return str;
}

參考資料

adlternative, zhoukuo123, Y7n05h, fansehep, hiyoyolumi, Vincil Lau, yegetables. Plan/strbuf.md at main · xiyou-linuxer/Plan. 2023-01-01 (CC BY-SA 4.0)

StrBuf - 簡單C語言字元串緩沖區編寫及講解設計一個 C 語言的動态擴容緩沖區