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

原 作者 张敏睿 | 发表于 | 分类于 2022级

知识要点

  1. 字符串
  2. 面向对象的C语言设计
  3. 动态内存分配
  4. Linux 文件 API
  5. 获取线路

正文

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

在这里插入图片描述

//初始化 sb 结构体，容量为 alloc。
void strbuf_init(struct strbuf *sb, size_t alloc)//数据类型解释见下
{
   
    sb->len=0;
    sb->alloc=alloc;
    sb->buf=(char *)malloc(sizeof(char)*alloc);//强制类型转换（void*--char*）
    strcpy(sb->buf,"");
}


//将字符串填充到 sb 中，长度为 len, 容量为 alloc。
void strbuf_attach(struct strbuf *sb, void *str, size_t len, size_t alloc)
{
   
    sb->buf=(char*)str;//强制类型转换（void*--char*）
    sb->len=len;
    sb->alloc=alloc;
}


//释放 sb 结构体的内存。
void strbuf_release(struct strbuf *sb)
{
   
    free(sb->buf);//参数是malloc()返回的地址，当时用buf存该地址
    sb->buf=NULL;//把指针设为NULL
    sb->len=0;
    sb->alloc=0;
}


//交换两个 strbuf。
void strbuf_swap(struct strbuf *a, struct strbuf *b)
{
   
    struct strbuf t;
    
法一：
    t=*a;
    *a=*b;
    *b=t;
    
法二：
    t.len=a->len;
    t.alloc=a->alloc;
    t.buf=a->buf;
    
    a->len=b->len;
    a->alloc=b->alloc;
    a->buf=b->buf;

    b->len=t.len;
    b->alloc=t.alloc;
    b->buf=t.buf;
    
}


//将 sb 中的原始内存取出，并将 sz 设置为其 alloc 大小 。
char *strbuf_detach(struct strbuf *sb, size_t *sz)
{
   
    *sz=sb->alloc;//sz=&(sb->alloc)编译错误
                  //因为cannot convert ‘int*’ to ‘size_t*’ {aka ‘long unsigned int*’} in assignment
    return sb->buf;//注意函数的返回类型
}


//比较两个 strbuf 的内存是否相同。
int strbuf_cmp(const struct strbuf *first, const struct strbuf *second)
{
   
	// int tag=1;错
    // if(first->len!=second->len)tag=0;
    // if(first->alloc!=second->alloc)tag=0;
    // if(strcmp(first->buf,second->buf)!=0)tag=0;
    // return tag;//相同‘1’,不同‘0’
    
    if(first->len>second->len)
        return 1;
    if(first->len<second->len)
        return -1;
    else 
        return 0;
}


//清空 sb 。
void strbuf_reset(struct strbuf *sb)//清空指的是让内存没有东西，而非释放(128G内存恢复出场设置)
{
   
	// sb->len=0;错
    // sb->alloc=0;
    // free(sb->buf);
    // sb->buf=NULL;

法一：
    int i; 
    for(i=0;i<sb->len;i++){
   
        sb->buf[i]='\0';
     }
     sb->len=0;
    // sb->alloc=0  因为alloc是申请到的内存大小，所以不能令为零（否则恢复出场设置后128G空间都没了）

法二：
    memset(sb->buf,0,sb->len);//函数解释见下
    sb->len=0;
    
}

size_t

无符号整数，32位下为unsigned int，64位下为unsigned long
在数组下标和内存管理函数之类的地方广泛使用

memset

void *memset(void *s, int c, size_t n);

  • s指向要填充的内存块。
    c是要被设置的值。
    n是要被设置该值的字符数。
    返回类型是一个指向存储区s的指针。

在这里插入图片描述

//确保在 len 之后 strbuf 中至少有 extra 个字节的空闲空间可用。
  //（128G总内存空间在已用100G后，确保至少有30G空闲空间可以用）->如果不够，再申请一块内存（再买内存卡）
void strbuf_grow(struct strbuf *sb, size_t extra)
{
   
    if(sb->alloc-sb->len < extra){
   
        sb->buf=(char*)realloc(sb->buf,sb->alloc+extra);//默认buf之前申请过一块内存，返回值为刚申请到的内存首地址
        sb->alloc += extra;                             //函数解释见下
    }
}


//向 sb 追加长度为 len 的数据 data 。
void strbuf_add(struct strbuf *sb, const void *data, size_t len)
{
   
    // if(sb->len+len <= sb->alloc){ //错
    //     sb->buf=strcat(sb->buf,(const char*)data);//(要不要强制类型转换为char*？)要！
    // }
    // else {
   
    //     strbuf_grow(sb,sb->alloc);//再来一倍
    //     sb->buf=strcat(sb->buf,(const char*)data);
    // }
    // sb->len+=len;
    
法一：
    if(sb->len+len >= sb->alloc)
    {
   
        sb->buf=(char*)realloc(sb->buf,sb->len+len+1);//包括\0
        sb->alloc=sb->len+len+1;//更新扩容后的内存大小256G
    }
    
法二：
	strbuf_grow(sb->buf,len+1);
	
    memcpy(sb->buf+sb->len,data,len);//函数解释见下
    sb->len+=len;
    // sb->buf+sb->len='\0'; //错
    //*(sb->buf+sb->len)='\0';  //ok!
    sb->buf[sb->len]='\0';

}


//向 sb 追加一个字符 c。
void strbuf_addch(struct strbuf *sb, int c)
{
   
    // char a[1];
    // a[0]=c;
	// if(sb->len+1 <= sb->alloc)
	//     sb->buf=strcat(sb->buf,a);
	// else {
   
	//     strbuf_grow(sb,sb->alloc);
	//     sb->buf=strcat(sb->buf,a);
	// }
	// sb->len+=1;

法一：
    if(sb->len+1 >= sb->alloc){
   
        sb->buf=(char*)realloc(sb->buf,(sb->alloc)*2);//内存翻两倍
        sb->alloc=sb->alloc*2;
    }
    memcpy(sb->buf+sb->len,&c,1);
    sb->len+=1;
    sb->buf[sb->len]='\0';

法二：
	strbuf_add(sb,&c,1);

}


//向 sb 追加一个字符串 s。
void strbuf_addstr(struct strbuf *sb, const char *s)
{
   
法一：
    int n=strlen(s);
    if(sb->len+n >= sb->alloc){
   
        sb->buf=(char*)realloc(sb->buf,sb->len+n+1);
        sb->alloc=sb->len+n+1;
    }
    memcpy(sb->buf+sb->len,s,n);
    // sb->buf=strcat(sb->buf,s); 错->解释见下
    sb->len+=n;
    sb->buf[sb->len]='\0';

法二：
	strbuf_add(sb,s,strlen(s));
}


//向一个 sb 追加另一个 strbuf 的数据。
void strbuf_addbuf(struct strbuf *sb, const struct strbuf *sb2)//追加一个结构体
{
   
法一：
    if(sb->len+sb2->len >= sb->alloc){
   
        sb->buf=(char*)realloc(sb->buf,sb->len+sb2->len+1);
        sb->alloc=sb->len+sb2->len+1;
    }
    sb->buf=strcat(sb->buf,sb2->buf);
    sb->len+=sb2->len;

法二：
	strbuf_addstr(sb,sb2->buf);
}


//设置 sb 的长度 len。
void strbuf_setlen(struct strbuf *sb, size_t len)
{
   
    if(len >= sb->alloc)//（要安装应用，先判断是否装的下）
    {
   
        sb->buf=(char*)realloc(sb->buf,len+1);
        sb->alloc=len+1;
    }
    sb->len=len;
    sb->buf[sb->len]='\0';
}


//计算 sb 目前仍可以向后追加的字符串长度。
size_t strbuf_avail(const struct strbuf *sb)
{
   
    return (sb->alloc-(sb->len+1));//末尾的\0
}


//向 sb 内存坐标为 pos 位置插入长度为 len 的数据 data 。
void strbuf_insert(struct strbuf *sb, size_t pos, const void *data, size_t len)
{
   
    if(sb->len+len > sb->alloc){
   
        strbuf_grow(sb,len+1);
    }
    // int i;错
    // char a[len];
    // strcpy(a,(const char*)data);
    // for(i=0;i<len;i++){
   
    //     sb->buf[pos+i]=a[i];  //默认原来位置没有数据->不行
    // }
    memmove(sb->buf+pos+len,sb->buf+pos,sb->len-pos);//把pos位置后面的数据移到pos+len的地方，空出来的len长度来存放data,函数解释见下
    memcpy(sb->buf+pos,data,len);//sb->buf[pos]错
    sb->len+=len;
    sb->buf[sb->len]='\0';
}

realloc

void* realloc(void* memblock, size_t size)

  • memblock: 先前开辟的内存块的指针（也就是malloc或calloc之前申请的那块内存空间，即需要调整大小的内存空间）
  • size: New size in bytes,新的字节数，注意不是增加的字节数，而是新开辟的那块内存空间的字节数（sizeof(…)）
  • 返回值: 新内存的起始地址（一般要xx=realloc）

memcpy

void *memcpy(void *dest, void *source, size_t n)

  • dest：指向用于存储复制内容的目标数组
  • source：指向要复制的数据源
  • n ：要被复制的 字节数（sizeof(…)）
  • 返回值：指向dest的指针（一般不用xx=，而是直接调用即可）

1.正常在复制字符串时用strcpy，而需要复制其他类型数据时则一般用memcpy
2.strcpy不需要指定长度，它遇到被复制字符的串结束符"\0"才结束，所以容易溢出。memcpy则可控制需要复制长短n
3.source和destin所指的内存区域可能重叠，但是如果source和dest所指的内存区域重叠,那么这个函数并不能够确保source所在重叠区域在拷贝之前不被覆盖。而使用memmove可以用来处理重叠区域。

memmove

void *memmove(void *dest, const void *source, size_t n)

  • dest：指向用于存储复制内容的目标数组
  • source：指向要复制的数据源
  • n：要被复制的 字节数
  • 返回值：指向dest的指针（一般不用xx=，而是直接调用即可）

能够对本身进行覆盖拷贝的函数，其又同时兼备了 memcpy函数 可做的事

在这里插入图片描述

//去除 sb 缓冲区左端的所有 空格，tab,'\t'。
void strbuf_ltrim(struct strbuf *sb)
{
   
    while((*(sb->buf)==' '||sb->buf[0]=='\t')&&sb->buf[0]!='\0')//这两种都可以，就是不行sb->buf==' '，因为
    {
                                                           //C++ forbids comparison between pointer and integer
        sb->buf=(char*)memmove(sb->buf,sb->buf+1,sb->len-1);//全部向左平移一位
        sb->len--;
    }
}


//去除 sb 缓冲区右端的所有 空格，tab, '\t'。
void strbuf_rtrim(struct strbuf *sb)
{
   
    while((sb->buf[(sb->len)-1]==' '||sb->buf[(sb->len)-1]=='\t')&&sb->buf[(sb->len)-1]!='\0')
    {
   
        // sb->buf+(sb->len)-1='\0';错
        // sb->buf=(char*)memmove(sb->buf+(sb->len)-1,sb->buf+(sb->len),1);
        sb->buf[(sb->len)-1]='\0';
        sb->len--;
    }
}


//删除 sb 缓冲区从 pos 坐标长度为 len 的内容。
void strbuf_remove(struct strbuf *sb, size_t pos, size_t len)
{
   
    // int i;多此一举
    // for(i=0;i<len;i++){
   
    //     sb->buf[pos+i]=0;
    // }
    memmove(sb->buf+pos,sb->buf+pos+len,sb->len-pos-len);//strlen(sb->buf+pos+len)+1  OK！
    sb->len=sb->len-len;
    sb->buf[sb->len]='\0';
}

在这里插入图片描述

//sb 增长 hint ? hint : 8192 大小， 然后将文件描述符为 fd 的所有文件内容追加到 sb 中。
ssize_t strbuf_read(struct strbuf *sb, int fd, size_t hint)//数据类型解释见下
{
   
    ssize_t result; //根据函数返回值定数据类型
    sb->buf=(char*)realloc(sb->buf,sb->alloc+(hint ? hint : 8192));//不是sb->len+(...)
    sb->alloc+=(hint ? hint : 8192);
    
    result=read(fd,sb->buf+sb->len,sb->alloc-sb->len-1);//函数解释见下
    if(result){
   
        sb->len+=result;
        sb->buf[sb->len]='\0';
    }
    return result;
}


//将 将文件句柄为 fp 的一行内容（抛弃换行符）读取到 sb 。
int strbuf_getline(struct strbuf *sb, FILE *fp)
{
   
	char ch;
	// ch=fgetc(fp); //返回值为int,然后再ch!=EOF ->ok因为EOF=-1
	法一：
	while((ch = fgetc(fp))!='\n' && ch!=EOF)
	{
   	
		strbuf_addch(sb, ch);
	}
	法二：
	while((ch = fgetc(fp))!='\n' && feof(fp)==0)//顺序不能错，函数解释见下
	{
   	
		strbuf_addch(sb, ch);
	}
    return 1;
}

read

ssize_t read(int fd ,void *buf, size_t count);
作用：从文件描述符对应的文件读取数据，调用成功返回读出的字节数
头文件：include<unistd.h>

  • fd：文件描述符
  • buf：读出数据的缓冲区（将文件中读出目标数据，放入buf缓冲区中）
  • count：每次读取的 字节数（是请求读取的字节数，读上来的数据保存在缓冲区buf中，同时文件的当前读写位置向后移）
  • 返回值：成功返回读出的字节数；失败返回-1；EOF返回0

ssize_t

有符号整型，在32位机器上等同与int，在64位机器上等同与long int

文件描述符

  • 操作系统利用文件描述符来访问文件。
  • 文件描述符是非负整数。
  • 打开现存文件或新建文件时，内核会返回一个文件描述符。
  • 读写文件也需要使用文件描述符来指定待读写的文件。
  • 只要获取到文件描述符，就可以找到对应的文件

文件句柄pf/fp

在这里插入图片描述
在这里插入图片描述
在这里插入图片描述
出错返回NULL

fgetc

int fgetc(FILE *filename)

  • 在文件处理中，通过fgetc()函数，我们从输入流中获取下一个字符，并将文件指针加1 （调用一次，filename向后移动一位）
  • 返回一个整数值，该值是无符号char的转换。 它还返回EOF ，而EOF也是一个整数值-1 。

在这里插入图片描述

feof

int feof(FILE *fp)

  • 当文件被打开，光标处于默认的开头时，光标后都有信息，这时候调用feof()来查看光标后是否还有内容，就没意义
  • 先使用getc(),从文件中读取一个字符，让光标向后移动一个字符。这时空文件的光标就已经移动到EOF的后面，这时使用feof()就会返回1了
  • 原理：站在光标所在位置，向后看看还有没有字符。如果有，返回0；如果没有，返回非0。它并不会读取相关信息，只是查看光标后是否还有内容。

在这里插入图片描述

//实现字符串切割
//将长度为 len 的字符串 str 根据切割字符 terminator 切成多个 strbuf,并从结果返回，
//max 可以用来限定最大切割数量。返回 struct strbuf 的指针数组，数组的最后元素为 NULL
struct strbuf **strbuf_split_buf(const char *str, size_t len, int terminator, int max)
{
   
//分配内存
    struct strbuf **p=(struct strbuf**)malloc(sizeof(struct strbuf*)*(max+1));//切3次，有3+1块
                   //由于要返回struct strbuf的指针数组，因此定义**p，相当于*p[],
                   //即数组p里面每个单元都是一个struct strbuf*指针，单独指向一个结构体（而每个结构体的buf指向一块内存空间，所以下面需要两次申请malloc）
//指针保存被切割字符串的首末地址
    const char *begin=str;
    const char *end=str+len;  // 字符串str \0的位置
    const char *next;
    int i=0;
    int len2;
//首元素是被切割字符的话，就直接跳过（p[]里放空内容没有意义）
    while(*begin==terminator)
        begin++;
//从第一个非切割字符开始，往后遍历整个str，找切割字符terminator
    for (next=begin;next<=end;next++)
    {
   
        if (*next==terminator||next==end)//注意是否要*
        {
   
            len2=next-begin;//地址之差，长度即为小块的字符串
            p[i]=(struct strbuf*)malloc(sizeof(struct strbuf));//为指针p[i]所指向的结构体申请一块内存，用于存放结构体（然后p[i]指向了这块空间，也就指向了那个结构体）
            p[i]->len=len2;
            p[i]->alloc=len2+1;
            p[i]->buf=(char*)malloc(sizeof(char)*(len2+1));// 因为结构体里的buf为指针，又指向了一块内存，所以向上面各个函数一样，malloc！（注意\0)
            memcpy(p[i]->buf,begin,len2);//len2长度的限制，从而实现将一小块字符串拷贝到buf中
            *(p[i]->buf+len2)='\0';
            i++;
           //连续的切割字符没有意义，跳过
            while(*next==terminator&&next<=end)
                next++;
           //新的头（每切一块，头就向后移动对应的长度）
            begin=next;
        }
        if(i==max)
            break;
    }
    p[i]=NULL;
    return p;
}


//实现判断一个 strbuf 是否以指定字符串开头的功能
//target_str:目标字符串，str:前缀字符串，strnlen:target_str 长度，前缀相同返回 true 失败返回 false
bool strbuf_begin_judge(char* target_str, const char* str, int strnlen)//返回值解释见下
{
   
法一：
     if(strnlen==0 || memcmp(target_str,str,strlen(str))==0)//相同返回0,函数解释见下
         return true;
     else 
         return false;

法二：
    int i;
    for(i=0;i<strlen;i++){
   
        if(str[i]=='\0')
            break;
        if(target_str[i]!=str[i])
            return false;
    }
    return true;
}


//获取字符串从坐标 [begin, end) 的所有内容（可以分成引用和拷贝两个模式）
//target_str:目标字符串，begin:开始下标，end:结束下标，len:target_buf的长度
//下标从0开始，[begin, end)区间，参数不合法返回 NULL
char* strbuf_get_mid_buf(char* target_buf, int begin, int end, int len)
{
   
    if(end<begin||target_buf==NULL)// <= 错
        return NULL;
        
    char *a;
    a=(char*)malloc(end-begin+1);
    memcpy(a,target_buf+begin,end-begin);
    a[end-begin]='\0';
    return a;
    
}

memcmp

int memcmp(const void *str1, const void *str2, size_t n)

  • str1 : 指向内存块的指针
  • str2 : 指向内存块的指针
  • n : 要被比较的 字节数
  • 返回值 ：当str1<str2时，返回值<0
         当str1=str2时，返回值=0
         当str1>str2时，返回值>0

如果两个字符串相同而且n大于字符串长度的话，memcmp不会在\0处停下来，会继续比较\0后面的内存单元，直到_res不为零或者达到n的次数。

  • 但strncmp必定会在最短的字符串的末尾停下来，即使count还未为零

boll

头文件：include<stdbool.h>
只能用来存放两个值:true (1) 和 false (0)