纸鹿本鹿摘要

设计一个 C 语言的动态扩容缓冲区

知识要点：字符串、面向对象的 C 语言设计、动态内存分配、Linux File API、getline。

缓冲区类的定义

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内追加一个字符串，我们需要计算当前的字符串长度加上追加的字符串长度，如果超过了当前的容量，我们就需要把容量扩大一倍，然后将字符串添加进去。s

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;
}
参考资料
许可协议

本文采用 署名-非商业性使用-相同方式共享 4.0 国际 许可协议，转载请注明出处。

评论区